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)

Methods

inj :: sub a -> AST sup a

Project sub sup => Project sub (AST sup)

Methods

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

Functor sym => Functor (AST sym)

Methods

fmap :: (a -> b) -> AST sym a -> AST sym b

(<$) :: a -> AST sym b -> AST sym a

Equality sym => Equality (AST sym)

Methods

equal :: AST sym a -> AST sym b -> Bool

hash :: AST sym a -> Hash

BindingDomain sym => BindingDomain (AST sym)

Methods

prVar :: AST sym sig -> Maybe Name

prLam :: AST sym sig -> Maybe Name

renameBind :: (Name -> Name) -> AST sym sig -> AST sym sig

NFData1 sym => NFData (AST sym sig)

Methods

rnf :: AST sym sig -> ()

Syntactic (ASTF sym a)

Associated Types

type Domain (ASTF sym a) :: * -> *

type Internal (ASTF sym a) :: *

Methods

desugar :: ASTF sym a -> ASTF (Domain (ASTF sym a)) (Internal (ASTF sym a))

sugar :: ASTF (Domain (ASTF sym a)) (Internal (ASTF sym a)) -> ASTF sym a

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

Methods

desugarN :: (a -> f) -> AST sym (Full ia) -> fi

sugarN :: (AST sym (Full ia) -> fi) -> a -> f

type SmartSym (AST sym sig)

type SmartSym (AST sym sig) = sym

type SmartSig (ASTF sym a -> f)

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

type SmartSig (AST sym sig)

type SmartSig (AST sym sig) = sig

type Domain (ASTF sym a)

type Domain (ASTF sym a) = sym

type Internal (ASTF sym a)

type Internal (ASTF sym a) = a

type ASTF sym a = AST sym (Full a)

Fully applied abstract syntax tree

newtype ASTFull sym a

Fully applied abstract syntax tree

This type is like AST, but being a newtype, it is a proper type constructor that can be partially applied.

Constructors

ASTFull

Fields

• unASTFull :: ASTF sym a

Instances

Syntactic (ASTFull sym a)

Associated Types

type Domain (ASTFull sym a) :: * -> *

type Internal (ASTFull sym a) :: *

Methods

desugar :: ASTFull sym a -> ASTF (Domain (ASTFull sym a)) (Internal (ASTFull sym a))

sugar :: ASTF (Domain (ASTFull sym a)) (Internal (ASTFull sym a)) -> ASTFull sym a

type Domain (ASTFull sym a)

type Domain (ASTFull sym a) = sym

type Internal (ASTFull sym a)

type Internal (ASTFull sym a) = a

newtype Full a

Signature of a fully applied symbol

Constructors

Full

Fields

• result :: a

Instances

Functor Full

Methods

fmap :: (a -> b) -> Full a -> Full b

(<$) :: a -> Full b -> Full a

Eq a => Eq (Full a)

Methods

(==) :: Full a -> Full a -> Bool

(/=) :: Full a -> Full a -> Bool

Show a => Show (Full a)

Methods

showsPrec :: Int -> Full a -> ShowS

show :: Full a -> String

showList :: [Full a] -> ShowS

Signature (Full a)

Methods

signature :: SigRep (Full a)

Syntactic (ASTF sym a)

Associated Types

type Domain (ASTF sym a) :: * -> *

type Internal (ASTF sym a) :: *

Methods

desugar :: ASTF sym a -> ASTF (Domain (ASTF sym a)) (Internal (ASTF sym a))

sugar :: ASTF (Domain (ASTF sym a)) (Internal (ASTF sym a)) -> ASTF sym a

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

Methods

desugarN :: (a -> f) -> AST sym (Full ia) -> fi

sugarN :: (AST sym (Full ia) -> fi) -> a -> f

type SmartFun sym (Full a)

type SmartFun sym (Full a) = ASTF sym a

type DenotationM m (Full a)

type DenotationM m (Full a) = m a

type LiftReader env (Full a)

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

type DenResult (Full a)

type DenResult (Full a) = a

type Denotation (Full a)

type Denotation (Full a) = a

type LowerReader (Full a)

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

type SmartSig (ASTF sym a -> f)

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

type Domain (ASTF sym a)

type Domain (ASTF sym a) = sym

type Internal (ASTF sym a)

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)

Methods

fmap :: (a -> b) -> (a :-> a) -> a :-> b

(<$) :: a -> (a :-> b) -> a :-> a

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

Methods

signature :: SigRep (a :-> sig)

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

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

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

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

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

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

type DenResult ((:->) a sig)

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

type Denotation ((:->) a sig)

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

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

Minimal complete definition

signature

Methods

signature :: SigRep sig

Instances

Signature (Full a)

Methods

signature :: SigRep (Full a)

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

Methods

signature :: SigRep (a :-> sig)

type family DenResult sig

The result type of a symbol with the given signature

Instances

type DenResult (Full a)

type DenResult (Full a) = a

type DenResult ((:->) a sig)

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

class Symbol sym where

Valid symbols to use in an AST

Minimal complete definition

symSig

Methods

symSig :: sym sig -> SigRep sig

Reify the signature of a symbol

Instances

Symbol Let

Methods

symSig :: Let sig -> SigRep sig

Symbol BindingT

Methods

symSig :: BindingT sig -> SigRep sig

Symbol Binding

Methods

symSig :: Binding sig -> SigRep sig

Symbol Construct

Methods

symSig :: Construct sig -> SigRep sig

Symbol Literal

Methods

symSig :: Literal sig -> SigRep sig

Symbol BindingWS

Methods

symSig :: BindingWS sig -> SigRep sig

Symbol Tuple

Methods

symSig :: Tuple sig -> SigRep sig

Symbol (MONAD m)

Methods

symSig :: MONAD m sig -> SigRep sig

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

Methods

symSig :: (sym1 :+: sym2) sig -> SigRep sig

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

Methods

symSig :: (sym :&: info) sig -> SigRep sig

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)

type SmartFun sym (Full a) = ASTF sym a

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

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)

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

type SmartSig (AST sym sig)

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)

type SmartSym (a -> f) = SmartSym f

type SmartSym (AST sym sig)

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)

Methods

inj :: sym1 a -> (sym2 :+: sym3) a

sym1 :<: ((:+:) sym1 sym2)

Methods

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

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

Methods

prj :: (sym2 :+: sym3) a -> Maybe (sym1 a)

Project sym1 ((:+:) sym1 sym2)

Methods

prj :: (sym1 :+: sym2) a -> Maybe (sym1 a)

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

Methods

fmap :: (a -> b) -> (sym1 :+: sym2) a -> (sym1 :+: sym2) b

(<$) :: a -> (sym1 :+: sym2) b -> (sym1 :+: sym2) a

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

Methods

fold :: Monoid m => (sym1 :+: sym2) m -> m

foldMap :: Monoid m => (a -> m) -> (sym1 :+: sym2) a -> m

foldr :: (a -> b -> b) -> b -> (sym1 :+: sym2) a -> b

foldr' :: (a -> b -> b) -> b -> (sym1 :+: sym2) a -> b

foldl :: (b -> a -> b) -> b -> (sym1 :+: sym2) a -> b

foldl' :: (b -> a -> b) -> b -> (sym1 :+: sym2) a -> b

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

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

toList :: (sym1 :+: sym2) a -> [a]

null :: (sym1 :+: sym2) a -> Bool

length :: (sym1 :+: sym2) a -> Int

elem :: Eq a => a -> (sym1 :+: sym2) a -> Bool

maximum :: Ord a => (sym1 :+: sym2) a -> a

minimum :: Ord a => (sym1 :+: sym2) a -> a

sum :: Num a => (sym1 :+: sym2) a -> a

product :: Num a => (sym1 :+: sym2) a -> a

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

Methods

traverse :: Applicative f => (a -> f b) -> (sym1 :+: sym2) a -> f ((sym1 :+: sym2) b)

sequenceA :: Applicative f => (sym1 :+: sym2) (f a) -> f ((sym1 :+: sym2) a)

mapM :: Monad m => (a -> m b) -> (sym1 :+: sym2) a -> m ((sym1 :+: sym2) b)

sequence :: Monad m => (sym1 :+: sym2) (m a) -> m ((sym1 :+: sym2) a)

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

Methods

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

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

Methods

symSig :: (sym1 :+: sym2) sig -> SigRep sig

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

Methods

stringTreeSym :: [Tree String] -> (sym1 :+: sym2) a -> Tree String

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

Methods

renderSym :: (sym1 :+: sym2) sig -> String

renderArgs :: [String] -> (sym1 :+: sym2) sig -> String

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

Methods

equal :: (sym1 :+: sym2) a -> (sym1 :+: sym2) b -> Bool

hash :: (sym1 :+: sym2) a -> Hash

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

Methods

evalSym :: (s :+: t) sig -> Denotation sig

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

Methods

prVar :: (sym1 :+: sym2) sig -> Maybe Name

prLam :: (sym1 :+: sym2) sig -> Maybe Name

renameBind :: (Name -> Name) -> (sym1 :+: sym2) sig -> (sym1 :+: sym2) sig

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

Methods

compileSym :: proxy env -> (sym1 :+: sym2) sig -> DenotationM (Reader env) sig

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 :+: ...).

Minimal complete definition

prj

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.

Methods

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

Project sym sym

Methods

prj :: sym a -> Maybe (sym a)

Project sub sup => Project sub (Typed sup)

Methods

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

Project sub sup => Project sub (AST sup)

Methods

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

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

Methods

prj :: (sym2 :+: sym3) a -> Maybe (sym1 a)

Project sym1 ((:+:) sym1 sym2)

Methods

prj :: (sym1 :+: sym2) a -> Maybe (sym1 a)

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

Methods

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

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

Symbol injection

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

Minimal complete definition

inj

Methods

inj :: sub a -> sup a

Injection from sub to sup

Instances

sym :<: sym

Methods

inj :: sym a -> sym a

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

Methods

inj :: sub a -> AST sup a

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

Methods

inj :: sym1 a -> (sym2 :+: sym3) a

sym1 :<: ((:+:) sym1 sym2)

Methods

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

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

Methods

stringTreeSym :: [Tree String] -> Empty a -> Tree String

Render Empty

Methods

renderSym :: Empty sig -> String

renderArgs :: [String] -> Empty sig -> String

Equality Empty

Methods

equal :: Empty a -> Empty b -> Bool

hash :: Empty a -> Hash

Eval Empty

Methods

evalSym :: Empty sig -> Denotation sig

EvalEnv Empty env

Methods

compileSym :: proxy env -> Empty sig -> DenotationM (Reader env) sig

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)

Methods

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

StringTree sym => StringTree (Typed sym)

Methods

stringTreeSym :: [Tree String] -> Typed sym a -> Tree String

Render sym => Render (Typed sym)

Methods

renderSym :: Typed sym sig -> String

renderArgs :: [String] -> Typed sym sig -> String

Equality sym => Equality (Typed sym)

Methods

equal :: Typed sym a -> Typed sym b -> Bool

hash :: Typed sym a -> Hash

BindingDomain sym => BindingDomain (Typed sym)

Methods

prVar :: Typed sym sig -> Maybe Name

prLam :: Typed sym sig -> Maybe Name

renameBind :: (Name -> Name) -> Typed sym sig -> Typed sym sig

EvalEnv sym env => EvalEnv (Typed sym) env

Methods

compileSym :: proxy env -> Typed sym sig -> DenotationM (Reader env) sig

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

Methods

rnf1 :: c a -> ()

Force a symbol to normal form

Instances

NFData1 BindingT

Methods

rnf1 :: BindingT a -> ()

NFData1 Binding

Methods

rnf1 :: Binding a -> ()

NFData1 BindingWS

Methods

rnf1 :: BindingWS a -> ()

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

Methods

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

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

Methods

rnf1 :: (sym :&: info) a -> ()

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