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 infixl 1

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)

Symbol sym => NFData (AST sym sig)

Syntactic (ASTF sym a)

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

type SmartSym (AST sym sig) = sym

type SmartSig (ASTF sym a -> f) = (:->) a (SmartSig f)

type SmartSig (AST sym sig) = sig

type Domain (ASTF sym a) = sym

type Internal (ASTF sym a) = a

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

Eq a => Eq (Full a)

Show a => Show (Full a)

Signature (Full a)

Render sym => Show (ASTF sym a)

Syntactic (ASTF sym a)

Typeable (* -> *) Full

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

type SmartFun sym (Full a) = ASTF sym a

type LiftReader env (Full a) = Full (Reader env a)

type DenotationM m (Full a) = m a

type DenResult (Full a) = a

type LowerReader (Full a) = Full (UnReader a)

type Denotation (Full a) = a

type SmartSig (ASTF sym a -> f) = (:->) a (SmartSig f)

type Domain (ASTF sym a) = sym

type Internal (ASTF sym a) = a

newtype a :-> sig infixr 9

Signature of a partially applied (or unapplied) symbol

Constructors

Partial (a -> sig)

Instances

Functor ((:->) a)

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

Typeable (* -> * -> *) (:->)

type SmartFun sym ((:->) a sig) = ASTF sym a -> SmartFun sym sig

type LiftReader env ((:->) a sig) = (:->) (Reader env a) (LiftReader env sig)

type DenotationM m ((:->) a sig) = m a -> DenotationM m sig

type DenResult ((:->) a sig) = DenResult sig

type LowerReader ((:->) a sig) = (:->) (UnReader a) (LowerReader sig)

type Denotation ((:->) a sig) = a -> Denotation sig

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

Valid symbol signatures

Methods

signature :: SigRep sig

Instances

Signature (Full a)

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

type family DenResult sig

The result type of a symbol with the given signature

Instances

type DenResult (Full a) = a

type DenResult ((:->) a sig) = DenResult sig

class Symbol sym where

Valid symbols to use in an AST

Minimal complete definition

symSig

Methods

rnfSym :: sym sig -> ()

Force a symbol to normal form

symSig :: sym sig -> SigRep sig

Reify the signature of a symbol

Instances

Symbol BindingWS

Symbol BindingT

Symbol Binding

Symbol Construct

Symbol (MONAD m)

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

Symbol sym => Symbol ((:&:) sym info)

size :: AST sym sig -> Int

Count the number of symbols in an AST

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

Instances

type SmartFun sym (Full a) = ASTF sym a

type SmartFun sym ((:->) a sig) = ASTF sym a -> SmartFun sym sig

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

Instances

type SmartSig (ASTF sym a -> f) = (:->) a (SmartSig f)

type SmartSig (AST sym sig) = sig

type family SmartSym f :: * -> *

Returns the symbol in the result of a smart constructor

Instances

type SmartSym (a -> f) = SmartSym f

type SmartSym (AST sym sig) = sym

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) sig where infixr 9

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)

(Symbol sym1, Symbol sym2) => Symbol ((:+:) 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