Language.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)

NFData1 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)

Syntactic (ASTF sym a)

(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 DenotationM m (Full a) = m a

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

type DenResult (Full a) = a

type Denotation (Full a) = a

type LowerReader (Full a) = Full (UnReader 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)

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

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

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

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

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

type LowerReader ((:->) a sig) = (:->) (UnReader a) (LowerReader 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

Methods

symSig :: sym sig -> SigRep sig

Reify the signature of a symbol

Instances

Symbol Let

Symbol BindingT

Symbol Binding

Symbol Construct

Symbol Literal

Symbol Tuple

Symbol BindingWS

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

Smart constructors

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)

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

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 (Typed sup)

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)

smartSymTyped :: (Signature sig, f ~ SmartFun (Typed sup) sig, sig ~ SmartSig f, Typed sup ~ SmartSym f, sub :<: sup, Typeable (DenResult sig)) => sub sig -> f

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

smartSymTyped :: (sub :<: AST (Typed sup), Typeable x)
    => 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 casting expressions

data Typed sym sig where

"Typed" symbol. Using Typed sym instead of sym gives access to the function castExpr for casting expressions.

Constructors

Typed :: Typeable (DenResult sig) => sym sig -> Typed sym sig

Instances

Project sub sup => Project sub (Typed sup)

StringTree sym => StringTree (Typed sym)

Render sym => Render (Typed sym)

Equality sym => Equality (Typed sym)

BindingDomain sym => BindingDomain (Typed sym)

EvalEnv sym env => EvalEnv (Typed sym) env

injT :: (sub :<: sup, Typeable (DenResult sig)) => sub sig -> AST (Typed sup) sig

Inject a symbol in an AST with a Typed domain

castExpr

Arguments

:: ASTF (Typed sym) a

Expression to cast

-> ASTF (Typed sym) b

Witness for typeability of result

-> Maybe (ASTF (Typed sym) b)

Type cast an expression

Misc.

class NFData1 c where

Higher-kinded version of NFData

Minimal complete definition

Nothing

Methods

rnf1 :: c a -> ()

Force a symbol to normal form

Instances

NFData1 BindingT

NFData1 Binding

NFData1 BindingWS

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

(NFData1 sym, NFData1 info) => NFData1 ((:&:) sym info)

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