Safe Haskell | None |
---|---|
Language | Haskell2010 |
Basics for implementing functional EDSLs
- newtype Name = Name Integer
- data Literal sig where
- data Construct sig where
- Construct :: Signature sig => String -> Denotation sig -> Construct sig
- data Binding sig where
- maxLam :: Project Binding s => AST s a -> Name
- lam_template :: Project Binding sym => (Name -> sym (Full a)) -> (Name -> sym (b :-> Full (a -> b))) -> (ASTF sym a -> ASTF sym b) -> ASTF sym (a -> b)
- lam :: Binding :<: sym => (ASTF sym a -> ASTF sym b) -> ASTF sym (a -> b)
- fromDeBruijn :: Binding :<: sym => ASTF sym a -> ASTF sym a
- data BindingT sig where
- maxLamT :: Project BindingT sym => AST sym a -> Name
- lamT_template :: Project BindingT sym => (Name -> sym (Full a)) -> (Name -> sym (b :-> Full (a -> b))) -> (ASTF sym a -> ASTF sym b) -> ASTF sym (a -> b)
- lamT :: (BindingT :<: sym, Typeable a) => (ASTF sym a -> ASTF sym b) -> ASTF sym (a -> b)
- lamTyped :: (sym ~ Typed s, BindingT :<: s, Typeable a, Typeable b) => (ASTF sym a -> ASTF sym b) -> ASTF sym (a -> b)
- class BindingDomain sym where
- data Let sig where
- data MONAD m sig where
- newtype Remon sym m a where
- desugarMonad :: (MONAD m :<: sym, Typeable a, Typeable m) => Remon sym m (ASTF sym a) -> ASTF sym (m a)
- desugarMonadTyped :: (MONAD m :<: s, sym ~ Typed s, Typeable a, Typeable m) => Remon sym m (ASTF sym a) -> ASTF sym (m a)
- freeVars :: BindingDomain sym => AST sym sig -> Set Name
- allVars :: BindingDomain sym => AST sym sig -> Set Name
- type AlphaEnv = [(Name, Name)]
- alphaEq' :: (Equality sym, BindingDomain sym) => AlphaEnv -> ASTF sym a -> ASTF sym b -> Bool
- alphaEq :: (Equality sym, BindingDomain sym) => ASTF sym a -> ASTF sym b -> Bool
- type family Denotation sig
- class Eval s where
- evalSym :: s sig -> Denotation sig
- evalDen :: Eval s => AST s sig -> Denotation sig
- type family DenotationM m sig
- liftDenotationM :: forall m sig proxy1 proxy2. Monad m => SigRep sig -> proxy1 m -> proxy2 sig -> Denotation sig -> DenotationM m sig
- type RunEnv = [(Name, Dynamic)]
- class EvalEnv sym env where
- compileSym :: proxy env -> sym sig -> DenotationM (Reader env) sig
- compileSymDefault :: forall proxy env sym sig. Eval sym => SigRep sig -> proxy env -> sym sig -> DenotationM (Reader env) sig
- evalOpen :: EvalEnv sym env => env -> ASTF sym a -> a
- evalClosed :: EvalEnv sym RunEnv => ASTF sym a -> a
Syntactic constructs
Variable name
Literal
data Construct sig where Source
Generic N-ary syntactic construct
Construct
gives a quick way to introduce a syntactic construct by giving its name and semantic
function.
Construct :: Signature sig => String -> Denotation sig -> Construct sig |
Variables and binders
NFData1 Binding Source | |
Symbol Binding Source | |
StringTree Binding Source | |
Render Binding Source | |
Equality Binding Source |
|
BindingDomain Binding Source |
:: Project Binding sym | |
=> (Name -> sym (Full a)) | Variable constructor |
-> (Name -> sym (b :-> Full (a -> b))) | Lambda constructor |
-> (ASTF sym a -> ASTF sym b) | |
-> ASTF sym (a -> b) |
Higher-order interface for variable binding for domains based on Binding
Assumptions:
- The body
f
does not inspect its argument. - Applying
f
to a term with ordered binders results in a term with ordered binders [1].
[1] Ordered binders means that the names of Lam
nodes are decreasing along every path from
the root.
See "Using Circular Programs for Higher-Order Syntax" (ICFP 2013, http://www.cse.chalmers.se/~emax/documents/axelsson2013using.pdf).
lam :: Binding :<: sym => (ASTF sym a -> ASTF sym b) -> ASTF sym (a -> b) Source
Higher-order interface for variable binding
This function is lamT_template
specialized to domains sym
satisfying
(
.Binding
:<:
sym)
data BindingT sig where Source
Typed variables and binders
VarT :: Typeable a => Name -> BindingT (Full a) | |
LamT :: Typeable a => Name -> BindingT (b :-> Full (a -> b)) |
NFData1 BindingT Source | |
Symbol BindingT Source | |
StringTree BindingT Source | |
Render BindingT Source | |
Equality BindingT Source |
|
BindingDomain BindingT Source | |
EvalEnv BindingT RunEnv Source |
:: Project BindingT sym | |
=> (Name -> sym (Full a)) | Variable constructor |
-> (Name -> sym (b :-> Full (a -> b))) | Lambda constructor |
-> (ASTF sym a -> ASTF sym b) | |
-> ASTF sym (a -> b) |
Higher-order interface for variable binding
Assumptions:
- The body
f
does not inspect its argument. - Applying
f
to a term with ordered binders results in a term with ordered binders [1].
[1] Ordered binders means that the names of LamT
nodes are decreasing along every path from
the root.
See "Using Circular Programs for Higher-Order Syntax" (ICFP 2013, http://www.cse.chalmers.se/~emax/documents/axelsson2013using.pdf).
lamT :: (BindingT :<: sym, Typeable a) => (ASTF sym a -> ASTF sym b) -> ASTF sym (a -> b) Source
Higher-order interface for variable binding
This function is lamT_template
specialized to domains sym
satisfying
(
.BindingT
:<:
sym)
lamTyped :: (sym ~ Typed s, BindingT :<: s, Typeable a, Typeable b) => (ASTF sym a -> ASTF sym b) -> ASTF sym (a -> b) Source
Higher-order interface for variable binding
This function is lamT_template
specialized to domains sym
satisfying
(sym ~
.Typed
s, BindingT
:<:
s)
class BindingDomain sym where Source
Domains that "might" include variables and binders
BindingDomain sym Source | |
BindingDomain BindingT Source | |
BindingDomain Binding Source | |
BindingDomain sym => BindingDomain (Typed sym) Source | |
BindingDomain sym => BindingDomain (AST sym) Source | |
(BindingDomain sym1, BindingDomain sym2) => BindingDomain ((:+:) sym1 sym2) Source | |
BindingDomain sym => BindingDomain ((:&:) sym i) Source |
A symbol for let bindings
This symbol is just an application operator. The actual binding has to be done by a lambda that constructs the second argument.
Monadic constructs
See "Generic Monadic Constructs for Embedded Languages" (Persson et al., IFL 2011 http://www.cse.chalmers.se/~emax/documents/persson2011generic.pdf).
newtype Remon sym m a where Source
Reifiable monad
See "Generic Monadic Constructs for Embedded Languages" (Persson et al., IFL 2011 http://www.cse.chalmers.se/~emax/documents/persson2011generic.pdf).
It is advised to convert to/from Remon
using the Syntactic
instance
provided in the modules Language.Syntactic.Sugar.Monad or
Language.Syntactic.Sugar.MonadT.
desugarMonad :: (MONAD m :<: sym, Typeable a, Typeable m) => Remon sym m (ASTF sym a) -> ASTF sym (m a) Source
One-layer desugaring of monadic actions
desugarMonadTyped :: (MONAD m :<: s, sym ~ Typed s, Typeable a, Typeable m) => Remon sym m (ASTF sym a) -> ASTF sym (m a) Source
One-layer desugaring of monadic actions
Free and bound variables
freeVars :: BindingDomain sym => AST sym sig -> Set Name Source
Get the set of free variables in an expression
allVars :: BindingDomain sym => AST sym sig -> Set Name Source
Get the set of variables (free, bound and introduced by lambdas) in an expression
Alpha-equivalence
alphaEq' :: (Equality sym, BindingDomain sym) => AlphaEnv -> ASTF sym a -> ASTF sym b -> Bool Source
alphaEq :: (Equality sym, BindingDomain sym) => ASTF sym a -> ASTF sym b -> Bool Source
Alpha-equivalence
Evaluation
type family Denotation sig Source
Semantic function type of the given symbol signature
type Denotation (Full a) = a Source | |
type Denotation ((:->) a sig) = a -> Denotation sig Source |
evalSym :: s sig -> Denotation sig Source
evalDen :: Eval s => AST s sig -> Denotation sig Source
Evaluation
type family DenotationM m sig Source
Monadic denotation; mapping from a symbol signature
a :-> b :-> Full c
to
m a -> m b -> m c
type DenotationM m (Full a) = m a Source | |
type DenotationM m ((:->) a sig) = m a -> DenotationM m sig Source |
liftDenotationM :: forall m sig proxy1 proxy2. Monad m => SigRep sig -> proxy1 m -> proxy2 sig -> Denotation sig -> DenotationM m sig Source
Lift a Denotation
to DenotationM
class EvalEnv sym env where Source
Evaluation
Nothing
compileSym :: proxy env -> sym sig -> DenotationM (Reader env) sig Source
EvalEnv Empty env Source | |
EvalEnv Let env Source | |
EvalEnv BindingT RunEnv Source | |
EvalEnv Construct env Source | |
EvalEnv Literal env Source | |
EvalEnv Tuple env Source | |
EvalEnv sym env => EvalEnv (Typed sym) env Source | |
Monad m => EvalEnv (MONAD m) env Source | |
(EvalEnv sym1 env, EvalEnv sym2 env) => EvalEnv ((:+:) sym1 sym2) env Source | |
EvalEnv sym env => EvalEnv ((:&:) sym info) env Source |
compileSymDefault :: forall proxy env sym sig. Eval sym => SigRep sig -> proxy env -> sym sig -> DenotationM (Reader env) sig Source
Simple implementation of compileSym
from a Denotation