Data.Syntactic.Syntax

Generic representation of typed syntax trees

For details, see: A Generic Abstract Syntax Model for Embedded Languages (ICFP 2012, http://www.cse.chalmers.se/~emax/documents/axelsson2012generic.pdf).

Syntax trees

data AST sym sig where

Generic abstract syntax tree, parameterized by a symbol domain

(AST sym (a :-> b)) represents a partially applied (or unapplied) symbol, missing at least one argument, while (AST sym (Full a)) represents a fully applied symbol, i.e. a complete syntax tree.

Constructors

Sym :: sym sig -> AST sym sig

:$ :: AST sym (a :-> sig) -> AST sym (Full a) -> AST sym sig

Instances

:<: sub sup => sub :<: (AST sup)

Project sub sup => Project sub (AST sup)

Functor sym => Functor (AST sym)

Equality sym => Equality (AST sym)

BindingDomain sym => BindingDomain (AST sym)

Equality sym => Eq (AST sym a)

Render sym => Show (ASTF sym a)

Syntactic (ASTF sym a)

(Syntactic a, ~ (* -> *) (Domain a) sym, ~ * ia (Internal a), SyntacticN f fi) => SyntacticN (a -> f) (AST sym (Full ia) -> fi)

type ASTF sym a = AST sym (Full a)

Fully applied abstract syntax tree

newtype Full a

Signature of a fully applied symbol

Constructors

Full

Fields

result :: a

Instances

Functor Full

Typeable1 Full

Eq a => Eq (Full a)

Show a => Show (Full a)

Signature (Full a)

Render sym => Show (ASTF sym a)

Syntactic (ASTF sym a)

(Syntactic a, ~ (* -> *) (Domain a) sym, ~ * ia (Internal a), SyntacticN f fi) => SyntacticN (a -> f) (AST sym (Full ia) -> fi)

newtype a :-> sig

Signature of a partially applied (or unapplied) symbol

Constructors

Partial (a -> sig)

Instances

Typeable2 :->

Functor (:-> a)

Signature sig => Signature (:-> a sig)

size :: AST sym sig -> Int

Count the number of symbols in an AST

type family DenResult sig

The result type of a symbol with the given signature

data SigRep sig where

Witness of the arity of a symbol signature

Constructors

SigFull :: SigRep (Full a)

SigMore :: SigRep sig -> SigRep (a :-> sig)

class Signature sig where

Symbol signatures

Methods

signature :: SigRep sig

Instances

Signature (Full a)

Signature sig => Signature (:-> a sig)

type family SmartFun sym sig

Maps a symbol signature to the type of the corresponding smart constructor:

 SmartFun sym (a :-> b :-> ... :-> Full x) = ASTF sym a -> ASTF sym b -> ... -> ASTF sym x

type family SmartSig f

Maps a smart constructor type to the corresponding symbol signature:

 SmartSig (ASTF sym a -> ASTF sym b -> ... -> ASTF sym x) = a :-> b :-> ... :-> Full x

type family SmartSym f :: * -> *

Returns the symbol in the result of a smart constructor

smartSym' :: forall sig f sym. (Signature sig, f ~ SmartFun sym sig, sig ~ SmartSig f, sym ~ SmartSym f) => sym sig -> f

Make a smart constructor of a symbol. smartSym has any type of the form:

 smartSym
     :: sym (a :-> b :-> ... :-> Full x)
     -> (ASTF sym a -> ASTF sym b -> ... -> ASTF sym x)

Open symbol domains

data (sym1 :+: sym2) a where

Direct sum of two symbol domains

Constructors

InjL :: sym1 a -> (sym1 :+: sym2) a

InjR :: sym2 a -> (sym1 :+: sym2) a

Instances

:<: sym1 sym3 => sym1 :<: (:+: sym2 sym3)

sym1 :<: (:+: sym1 sym2)

Project sym1 sym3 => Project sym1 (:+: sym2 sym3)

Project sym1 (:+: sym1 sym2)

(Functor sym1, Functor sym2) => Functor (:+: sym1 sym2)

(Foldable sym1, Foldable sym2) => Foldable (:+: sym1 sym2)

(Traversable sym1, Traversable sym2) => Traversable (:+: sym1 sym2)

(StringTree sym1, StringTree sym2) => StringTree (:+: sym1 sym2)

(Render sym1, Render sym2) => Render (:+: sym1 sym2)

(Equality sym1, Equality sym2) => Equality (:+: sym1 sym2)

(Eval s, Eval t) => Eval (:+: s t)

(BindingDomain sym1, BindingDomain sym2) => BindingDomain (:+: sym1 sym2)

(EvalEnv sym1 env, EvalEnv sym2 env) => EvalEnv (:+: sym1 sym2) env

(Equality sym1, Equality sym2) => Eq (:+: sym1 sym2 a)

class Project sub sup where

Symbol projection

The class is defined for all pairs of types, but prj can only succeed if sup is of the form (... :+: sub :+: ...).

Methods

prj :: sup a -> Maybe (sub a)

Partial projection from sup to sub

Instances

Project sub sup

If sub is not in sup, prj always returns Nothing.

Project sym sym

Project sub sup => Project sub (AST sup)

Project sym1 sym3 => Project sym1 (:+: sym2 sym3)

Project sym1 (:+: sym1 sym2)

Project sub sup => Project sub (:&: sup info)

class Project sub sup => sub :<: sup where

Symbol injection

The class includes types sub and sup where sup is of the form (... :+: sub :+: ...).

Methods

inj :: sub a -> sup a

Injection from sub to sup

Instances

sym :<: sym

:<: sub sup => sub :<: (AST sup)

:<: sym1 sym3 => sym1 :<: (:+: sym2 sym3)

sym1 :<: (:+: sym1 sym2)

smartSym :: (Signature sig, f ~ SmartFun sup sig, sig ~ SmartSig f, sup ~ SmartSym f, sub :<: sup) => sub sig -> f

Make a smart constructor of a symbol. smartSym has any type of the form:

 smartSym :: (sub :<: AST sup)
     => sub (a :-> b :-> ... :-> Full x)
     -> (ASTF sup a -> ASTF sup b -> ... -> ASTF sup x)

data Empty

Empty symbol type

Can be used to make uninhabited AST types. It can also be used as a terminator in co-product lists (e.g. to avoid overlapping instances):

 (A :+: B :+: Empty)

Instances

StringTree Empty

Render Empty

Equality Empty

Eval Empty

EvalEnv Empty env

Existential quantification

data E e where

Existential quantification

Constructors

E :: e a -> E e

liftE :: (forall a. e a -> b) -> E e -> b

liftE2 :: (forall a b. e a -> e b -> c) -> E e -> E e -> c

data EF e where

Existential quantification of Full-indexed type

Constructors

EF :: e (Full a) -> EF e

liftEF :: (forall a. e (Full a) -> b) -> EF e -> b

liftEF2 :: (forall a b. e (Full a) -> e (Full b) -> c) -> EF e -> EF e -> c

Type inference

symType :: Proxy sym -> sym sig -> sym sig

Constrain a symbol to a specific type

prjP :: Project sub sup => Proxy sub -> sup sig -> Maybe (sub sig)

Projection to a specific symbol type