Safe Haskell	None
Language	Haskell2010

Language.Syntactic.Syntax

Contents

Syntax trees
Symbol domains
Type inference

Description

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

Synopsis

data AST dom sig where
- Sym :: dom sig -> AST dom sig
- (:$) :: AST dom (a :-> sig) -> AST dom (Full a) -> AST dom sig
type ASTF dom a = AST dom (Full a)
newtype Full a = Full {
- result :: a
}
newtype a :-> sig = Partial (a -> sig)
size :: AST dom sig -> Int
class ApplySym sig f dom | sig dom -> f, f -> sig dom where
type family DenResult sig
data (dom1 :+: dom2) a where
- InjL :: dom1 a -> (dom1 :+: dom2) a
- InjR :: dom2 a -> (dom1 :+: dom2) a
class Project sub sup where
class Project sub sup => sub :<: sup where
appSym :: (ApplySym sig f dom, sym :<: AST dom) => sym sig -> f
symType :: P sym -> sym sig -> sym sig
prjP :: Project sub sup => P sub -> sup sig -> Maybe (sub sig)

Syntax trees

data AST dom sig where Source #

Generic abstract syntax tree, parameterized by a symbol domain

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

Constructors

Sym :: dom sig -> AST dom sig
(:$) :: AST dom (a :-> sig) -> AST dom (Full a) -> AST dom sig infixl 1

Instances

sub :<: sup => sub :<: (AST sup) Source #
Instance details Defined in Language.Syntactic.Syntax Methods inj :: sub a -> AST sup a Source #
Project sub sup => Project sub (AST sup) Source #
Instance details Defined in Language.Syntactic.Syntax Methods prj :: AST sup a -> Maybe (sub a) Source #
(InjectC sub sup a, Sat (AST sup) a) => InjectC sub (AST sup) a Source #
Instance details Defined in Language.Syntactic.Constraint Methods injC :: DenResult sig ~ a => sub sig -> AST sup sig Source #
Functor dom => Functor (AST dom) Source #
Instance details Defined in Language.Syntactic.Syntax Methods fmap :: (a -> b) -> AST dom a -> AST dom b # (<$) :: a -> AST dom b -> AST dom a #
Eval dom => Eval (AST dom) Source #
Instance details Defined in Language.Syntactic.Interpretation.Evaluation Methods evaluate :: AST dom a -> Denotation a Source #
Equality dom => Equality (AST dom) Source #
Instance details Defined in Language.Syntactic.Interpretation.Equality Methods equal :: AST dom a -> AST dom b -> Bool Source # exprHash :: AST dom a -> Hash Source #
Constrained dom => Constrained (AST dom) Source #
Instance details Defined in Language.Syntactic.Constraint Associated Types type Sat (AST dom) :: * -> Constraint Source # Methods exprDict :: AST dom a -> Dict (Sat (AST dom) (DenResult a)) Source #
ApplySym (Full a) (ASTF dom a) dom Source #
Instance details Defined in Language.Syntactic.Syntax Methods appSym' :: AST dom (Full a) -> ASTF dom a Source #
Equality dom => Eq (AST dom a) #
Instance details Defined in Language.Syntactic.Interpretation.Equality Methods (==) :: AST dom a -> AST dom a -> Bool # (/=) :: AST dom a -> AST dom a -> Bool #
Render dom => Show (ASTF dom a) #
Instance details Defined in Language.Syntactic.Interpretation.Render Methods showsPrec :: Int -> ASTF dom a -> ShowS # show :: ASTF dom a -> String # showList :: [ASTF dom a] -> ShowS #
Syntactic (ASTF dom a) Source #
Instance details Defined in Language.Syntactic.Sugar Associated Types type Domain (ASTF dom a) :: * -> * Source # type Internal (ASTF dom a) :: * Source # Methods desugar :: ASTF dom a -> ASTF (Domain (ASTF dom a)) (Internal (ASTF dom a)) Source # sugar :: ASTF (Domain (ASTF dom a)) (Internal (ASTF dom a)) -> ASTF dom a Source #
(Syntactic a, Domain a ~ dom, ia ~ Internal a, SyntacticN b ib) => SyntacticN (a -> b) (AST dom (Full ia) -> ib) Source #
Instance details Defined in Language.Syntactic.Sugar Methods desugarN :: (a -> b) -> AST dom (Full ia) -> ib Source # sugarN :: (AST dom (Full ia) -> ib) -> a -> b Source #
ApplySym sig f dom => ApplySym (a :-> sig) (ASTF dom a -> f) dom Source #
Instance details Defined in Language.Syntactic.Syntax Methods appSym' :: AST dom (a :-> sig) -> ASTF dom a -> f Source #
type Sat (AST dom) Source #
Instance details Defined in Language.Syntactic.Constraint type Sat (AST dom) = Sat dom
type Domain (ASTF dom a) Source #
Instance details Defined in Language.Syntactic.Sugar type Domain (ASTF dom a) = dom
type Internal (ASTF dom a) Source #
Instance details Defined in Language.Syntactic.Sugar type Internal (ASTF dom a) = a

type ASTF dom a = AST dom (Full a) Source #

Fully applied abstract syntax tree

newtype Full a Source #

Signature of a fully applied symbol

Constructors

Full
Fields result :: a

Instances

Functor Full Source #
Instance details Defined in Language.Syntactic.Syntax Methods fmap :: (a -> b) -> Full a -> Full b # (<$) :: a -> Full b -> Full a #
Eq a => Eq (Full a) Source #
Instance details Defined in Language.Syntactic.Syntax Methods (==) :: Full a -> Full a -> Bool # (/=) :: Full a -> Full a -> Bool #
Show a => Show (Full a) Source #
Instance details Defined in Language.Syntactic.Syntax Methods showsPrec :: Int -> Full a -> ShowS # show :: Full a -> String # showList :: [Full a] -> ShowS #
ApplySym (Full a) (ASTF dom a) dom Source #
Instance details Defined in Language.Syntactic.Syntax Methods appSym' :: AST dom (Full a) -> ASTF dom a Source #
Render dom => Show (ASTF dom a) #
Instance details Defined in Language.Syntactic.Interpretation.Render Methods showsPrec :: Int -> ASTF dom a -> ShowS # show :: ASTF dom a -> String # showList :: [ASTF dom a] -> ShowS #
Syntactic (ASTF dom a) Source #
Instance details Defined in Language.Syntactic.Sugar Associated Types type Domain (ASTF dom a) :: * -> * Source # type Internal (ASTF dom a) :: * Source # Methods desugar :: ASTF dom a -> ASTF (Domain (ASTF dom a)) (Internal (ASTF dom a)) Source # sugar :: ASTF (Domain (ASTF dom a)) (Internal (ASTF dom a)) -> ASTF dom a Source #
(Syntactic a, Domain a ~ dom, ia ~ Internal a, SyntacticN b ib) => SyntacticN (a -> b) (AST dom (Full ia) -> ib) Source #
Instance details Defined in Language.Syntactic.Sugar Methods desugarN :: (a -> b) -> AST dom (Full ia) -> ib Source # sugarN :: (AST dom (Full ia) -> ib) -> a -> b Source #
ApplySym sig f dom => ApplySym (a :-> sig) (ASTF dom a -> f) dom Source #
Instance details Defined in Language.Syntactic.Syntax Methods appSym' :: AST dom (a :-> sig) -> ASTF dom a -> f Source #
type DenResult (Full a) Source #
Instance details Defined in Language.Syntactic.Syntax type DenResult (Full a) = a
type Denotation (Full a) Source #
Instance details Defined in Language.Syntactic.Interpretation.Semantics type Denotation (Full a) = a
type Domain (ASTF dom a) Source #
Instance details Defined in Language.Syntactic.Sugar type Domain (ASTF dom a) = dom
type Internal (ASTF dom a) Source #
Instance details Defined in Language.Syntactic.Sugar type Internal (ASTF dom a) = a

newtype a :-> sig infixr 9 Source #

Signature of a partially applied (or unapplied) symbol

Constructors

Partial (a -> sig)

Instances

Functor ((:->) a) Source #
Instance details Defined in Language.Syntactic.Syntax Methods fmap :: (a0 -> b) -> (a :-> a0) -> a :-> b # (<$) :: a0 -> (a :-> b) -> a :-> a0 #
ApplySym sig f dom => ApplySym (a :-> sig) (ASTF dom a -> f) dom Source #
Instance details Defined in Language.Syntactic.Syntax Methods appSym' :: AST dom (a :-> sig) -> ASTF dom a -> f Source #
type DenResult (a :-> sig) Source #
Instance details Defined in Language.Syntactic.Syntax type DenResult (a :-> sig) = DenResult sig
type Denotation (a :-> sig) Source #
Instance details Defined in Language.Syntactic.Interpretation.Semantics type Denotation (a :-> sig) = a -> Denotation sig

size :: AST dom sig -> Int Source #

Count the number of symbols in an expression

class ApplySym sig f dom | sig dom -> f, f -> sig dom where Source #

Class for the type-level recursion needed by appSym

Minimal complete definition

appSym'

Methods

appSym' :: AST dom sig -> f Source #

Instances

ApplySym (Full a) (ASTF dom a) dom Source #
Instance details Defined in Language.Syntactic.Syntax Methods appSym' :: AST dom (Full a) -> ASTF dom a Source #
ApplySym sig f dom => ApplySym (a :-> sig) (ASTF dom a -> f) dom Source #
Instance details Defined in Language.Syntactic.Syntax Methods appSym' :: AST dom (a :-> sig) -> ASTF dom a -> f Source #

type family DenResult sig Source #

The result type of a symbol with the given signature

Instances

type DenResult (Full a) Source #
Instance details Defined in Language.Syntactic.Syntax type DenResult (Full a) = a
type DenResult (a :-> sig) Source #
Instance details Defined in Language.Syntactic.Syntax type DenResult (a :-> sig) = DenResult sig

Symbol domains

data (dom1 :+: dom2) a where infixr 9 Source #

Direct sum of two symbol domains

Constructors

InjL :: dom1 a -> (dom1 :+: dom2) a
InjR :: dom2 a -> (dom1 :+: dom2) a

Instances

expr1 :<: expr3 => expr1 :<: (expr2 :+: expr3) Source #
Instance details Defined in Language.Syntactic.Syntax Methods inj :: expr1 a -> (expr2 :+: expr3) a Source #
expr1 :<: (expr1 :+: expr2) Source #
Instance details Defined in Language.Syntactic.Syntax Methods inj :: expr1 a -> (expr1 :+: expr2) a Source #
Project expr1 expr3 => Project expr1 (expr2 :+: expr3) Source #
Instance details Defined in Language.Syntactic.Syntax Methods prj :: (expr2 :+: expr3) a -> Maybe (expr1 a) Source #
Project expr1 (expr1 :+: expr2) Source #
Instance details Defined in Language.Syntactic.Syntax Methods prj :: (expr1 :+: expr2) a -> Maybe (expr1 a) Source #
InjectC expr1 expr3 a => InjectC expr1 (expr2 :+: expr3) a Source #
Instance details Defined in Language.Syntactic.Constraint Methods injC :: DenResult sig ~ a => expr1 sig -> (expr2 :+: expr3) sig Source #
InjectC expr1 (expr1 :+: expr2) a Source #
Instance details Defined in Language.Syntactic.Constraint Methods injC :: DenResult sig ~ a => expr1 sig -> (expr1 :+: expr2) sig Source #
(Functor dom1, Functor dom2) => Functor (dom1 :+: dom2) Source #
Instance details Defined in Language.Syntactic.Syntax Methods fmap :: (a -> b) -> (dom1 :+: dom2) a -> (dom1 :+: dom2) b # (<$) :: a -> (dom1 :+: dom2) b -> (dom1 :+: dom2) a #
(StringTree dom1, StringTree dom2) => StringTree (dom1 :+: dom2) Source #
Instance details Defined in Language.Syntactic.Interpretation.Render Methods stringTreeSym :: [Tree String] -> (dom1 :+: dom2) a -> Tree String Source #
(Render expr1, Render expr2) => Render (expr1 :+: expr2) Source #
Instance details Defined in Language.Syntactic.Interpretation.Render Methods renderSym :: (expr1 :+: expr2) sig -> String Source # renderArgs :: [String] -> (expr1 :+: expr2) sig -> String Source #
(Eval expr1, Eval expr2) => Eval (expr1 :+: expr2) Source #
Instance details Defined in Language.Syntactic.Interpretation.Evaluation Methods evaluate :: (expr1 :+: expr2) a -> Denotation a Source #
(Equality expr1, Equality expr2) => Equality (expr1 :+: expr2) Source #
Instance details Defined in Language.Syntactic.Interpretation.Equality Methods equal :: (expr1 :+: expr2) a -> (expr1 :+: expr2) b -> Bool Source # exprHash :: (expr1 :+: expr2) a -> Hash Source #
Constrained (sub1 :+: sub2) Source #
Instance details Defined in Language.Syntactic.Constraint Associated Types type Sat (sub1 :+: sub2) :: * -> Constraint Source # Methods exprDict :: (sub1 :+: sub2) a -> Dict (Sat (sub1 :+: sub2) (DenResult a)) Source #
(EvalBind sub1, EvalBind sub2) => EvalBind (sub1 :+: sub2) Source #
Instance details Defined in Language.Syntactic.Constructs.Binding Methods evalBindSym :: (EvalBind dom, ConstrainedBy dom Typeable, Typeable (DenResult sig)) => (sub1 :+: sub2) sig -> Args (AST dom) sig -> Reader [(VarId, Dynamic)] (DenResult sig) Source #
(Optimize sub1, Optimize sub2) => Optimize (sub1 :+: sub2) Source #
Instance details Defined in Language.Syntactic.Constructs.Binding.Optimize Methods optimizeSym :: Optimize' dom => ConstFolder dom -> ((sub1 :+: sub2) sig -> AST dom sig) -> (sub1 :+: sub2) sig -> Args (AST dom) sig -> Writer (Set VarId) (ASTF dom (DenResult sig)) Source #
TupleSat dom2 p => TupleSat (dom1 :+: dom2) p Source #
Instance details Defined in Language.Syntactic.Frontend.TupleConstrained
TupleSat ((Tuple :\|\| p) :+: dom2) p Source #
Instance details Defined in Language.Syntactic.Frontend.TupleConstrained
TupleSat ((Select :\|\| p) :+: dom2) p Source #
Instance details Defined in Language.Syntactic.Frontend.TupleConstrained
(AlphaEq subA1 subB1 dom env, AlphaEq subA2 subB2 dom env) => AlphaEq (subA1 :+: subA2) (subB1 :+: subB2) dom env Source #
Instance details Defined in Language.Syntactic.Constructs.Binding Methods alphaEqSym :: (subA1 :+: subA2) a -> Args (AST dom) a -> (subB1 :+: subB2) b -> Args (AST dom) b -> Reader env Bool Source #
(Equality expr1, Equality expr2) => Eq ((expr1 :+: expr2) a) #
Instance details Defined in Language.Syntactic.Interpretation.Equality Methods (==) :: (expr1 :+: expr2) a -> (expr1 :+: expr2) a -> Bool # (/=) :: (expr1 :+: expr2) a -> (expr1 :+: expr2) a -> Bool #
IsHODomain (HODomain dom p pVar) p pVar Source #
Instance details Defined in Language.Syntactic.Constructs.Binding.HigherOrder Methods lambda :: (p (a -> b), p a, pVar a) => (ASTF (HODomain dom p pVar) a -> ASTF (HODomain dom p pVar) b) -> ASTF (HODomain dom p pVar) (a -> b) Source #
type Sat (sub1 :+: sub2) Source #
Instance details Defined in Language.Syntactic.Constraint type Sat (sub1 :+: sub2) = Top

class Project sub sup where Source #

Symbol projection

Minimal complete definition

prj

Methods

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

Partial projection from sup to sub

Instances

Project expr expr Source #
Instance details Defined in Language.Syntactic.Syntax Methods prj :: expr a -> Maybe (expr a) Source #
Project sub sup => Project sub (AST sup) Source #
Instance details Defined in Language.Syntactic.Syntax Methods prj :: AST sup a -> Maybe (sub a) Source #
Project expr1 expr3 => Project expr1 (expr2 :+: expr3) Source #
Instance details Defined in Language.Syntactic.Syntax Methods prj :: (expr2 :+: expr3) a -> Maybe (expr1 a) Source #
Project expr1 (expr1 :+: expr2) Source #
Instance details Defined in Language.Syntactic.Syntax Methods prj :: (expr1 :+: expr2) a -> Maybe (expr1 a) Source #
Project sub sup => Project sub (sup :\|\| pred) Source #
Instance details Defined in Language.Syntactic.Constraint Methods prj :: (sup :\|\| pred) a -> Maybe (sub a) Source #
Project sub sup => Project sub (sup :\| pred) Source #
Instance details Defined in Language.Syntactic.Constraint Methods prj :: (sup :\| pred) a -> Maybe (sub a) Source #
Project sub sup => Project sub (Decor info sup) Source #
Instance details Defined in Language.Syntactic.Constructs.Decoration Methods prj :: Decor info sup a -> Maybe (sub a) Source #
Project sub sup => Project sub (SubConstr1 c sup p) Source #
Instance details Defined in Language.Syntactic.Constraint Methods prj :: SubConstr1 c sup p a -> Maybe (sub a) Source #
Project sub sup => Project sub (SubConstr2 c sup pa pb) Source #
Instance details Defined in Language.Syntactic.Constraint Methods prj :: SubConstr2 c sup pa pb a -> Maybe (sub a) Source #

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

Symbol subsumption

Minimal complete definition

inj

Methods

inj :: sub a -> sup a Source #

Injection from sub to sup

Instances

expr :<: expr Source #
Instance details Defined in Language.Syntactic.Syntax Methods inj :: expr a -> expr a Source #
sub :<: sup => sub :<: (AST sup) Source #
Instance details Defined in Language.Syntactic.Syntax Methods inj :: sub a -> AST sup a Source #
expr1 :<: expr3 => expr1 :<: (expr2 :+: expr3) Source #
Instance details Defined in Language.Syntactic.Syntax Methods inj :: expr1 a -> (expr2 :+: expr3) a Source #
expr1 :<: (expr1 :+: expr2) Source #
Instance details Defined in Language.Syntactic.Syntax Methods inj :: expr1 a -> (expr1 :+: expr2) a Source #

appSym :: (ApplySym sig f dom, sym :<: AST dom) => sym sig -> f Source #

Generic symbol application

appSym has any type of the form:

appSym :: (expr :<: AST dom)
    => expr (a :-> b :-> ... :-> Full x)
    -> (ASTF dom a -> ASTF dom b -> ... -> ASTF dom x)

Type inference

symType :: P sym -> sym sig -> sym sig Source #

Constrain a symbol to a specific type

prjP :: Project sub sup => P sub -> sup sig -> Maybe (sub sig) Source #

Projection to a specific symbol type