syntactic-2.0: Generic representation and manipulation of abstract syntax

Safe HaskellNone

Data.Syntactic.Syntax

Contents

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

Syntax trees

data AST sym sig whereSource

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 

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) 
Syntactic (ASTF sym a) 
(Syntactic a, ~ (* -> *) (Domain a) sym, ~ * ia (Internal a), SyntacticN f fi) => SyntacticN (a -> f) (AST sym (Full ia) -> fi) 

type ASTF sym a = AST sym (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 
Typeable1 Full 
Eq a => Eq (Full a) 
Show a => Show (Full a) 
Signature (Full a) 
Render sym => Show (ASTF sym a) 
Syntactic (ASTF sym a) 
(Syntactic a, ~ (* -> *) (Domain a) sym, ~ * ia (Internal a), SyntacticN f fi) => SyntacticN (a -> f) (AST sym (Full ia) -> fi) 

newtype a :-> sig Source

Signature of a partially applied (or unapplied) symbol

Constructors

Partial (a -> sig) 

Instances

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

size :: AST sym sig -> IntSource

Count the number of symbols in an AST

type family DenResult sig Source

The result type of a symbol with the given signature

data SigRep sig whereSource

Witness of the arity of a symbol signature

Constructors

SigFull :: SigRep (Full a) 
SigMore :: SigRep sig -> SigRep (a :-> sig) 

class Signature sig whereSource

Symbol signatures

Methods

signature :: SigRep sigSource

Instances

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

type family SmartFun sym sig Source

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

type family SmartSig f Source

Maps a smart constructor type to the corresponding symbol signature: 

 SmartSig (ASTF sym a -> ASTF sym b -> ... -> ASTF sym x) = a :-> b :-> ... :-> Full x

type family SmartSym f :: * -> *Source

Returns the symbol in the result of a smart constructor

smartSym' :: forall sig f sym. (Signature sig, f ~ SmartFun sym sig, sig ~ SmartSig f, sym ~ SmartSym f) => sym sig -> fSource

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) a whereSource

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) 
(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 whereSource

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

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 whereSource

Symbol injection

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

Methods

inj :: sub a -> sup aSource

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 -> fSource

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 Source

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

Existential quantification

data E e whereSource

Existential quantification

Constructors

E :: e a -> E e 

liftE :: (forall a. e a -> b) -> E e -> bSource

liftE2 :: (forall a b. e a -> e b -> c) -> E e -> E e -> cSource

data EF e whereSource

Existential quantification of Full-indexed type

Constructors

EF :: e (Full a) -> EF e 

liftEF :: (forall a. e (Full a) -> b) -> EF e -> bSource

liftEF2 :: (forall a b. e (Full a) -> e (Full b) -> c) -> EF e -> EF e -> cSource

Type inference

symType :: Proxy sym -> sym sig -> sym sigSource

Constrain a symbol to a specific type

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

Projection to a specific symbol type