-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Generic abstract syntax, and utilities for embedded languages
--   
--   This library provides:
--   
--   <ul>
--   <li>Generic representation and manipulation of abstract syntax</li>
--   <li>Composable AST representations (partly based on Data Types à la
--   Carte [1])</li>
--   <li>A collection of common syntactic constructs, including variable
--   binding constructs</li>
--   <li>Utilities for analyzing and transforming generic abstract
--   syntax</li>
--   <li>Utilities for building extensible embedded languages based on
--   generic syntax</li>
--   <li>A small proof-of-concept implementation of the embedded language
--   Feldspar [2] (see the <tt>Examples</tt> directory)</li>
--   </ul>
--   
--   For details, see the paper "A Generic Abstract Syntax Model for
--   Embedded Languages" (ICFP 2012,
--   <a>http://www.cse.chalmers.se/~emax/documents/axelsson2012generic.pdf</a>).
--   
--   The maturity of this library varies between different modules. The
--   core part (<a>Language.Syntactic</a>) is rather stable, but many of
--   the other modules are in a much more experimental state.
--   
--   [1] W. Swierstra. Data Types à la Carte. <i>Journal of Functional
--   Programming</i>, 18(4):423-436, 2008,
--   <a>http://dx.doi.org/10.1017/S0956796808006758</a>.
--   
--   [2] <a>http://hackage.haskell.org/package/feldspar-language</a>
@package syntactic
@version 1.0


-- | Some utility functions used by the other modules
module Language.Syntactic.Sharing.Utils

-- | Difference list
type DList a = [a] -> [a]

-- | Empty list
empty :: DList a

-- | Singleton list
single :: a -> DList a
fromDList :: DList a -> [a]

-- | Given a list <tt>is</tt> of unique natural numbers, returns a function
--   that maps each number in <tt>is</tt> to a unique number in the range
--   <tt>[0 .. length is-1]</tt>. The complexity is O(<tt>maximum is</tt>).
reindex :: (Integral a, Ix a) => [a] -> a -> a

-- | Count the number of occurrences of each element in the list. The
--   result is an array mapping each element to its number of occurrences.
count :: Ix a => (a, a) -> [a] -> Array a Int

-- | Partitions the list such that two elements are in the same sub-list if
--   and only if they satisfy the equivalence check. The complexity is
--   O(n^2).
fullPartition :: (a -> a -> Bool) -> [a] -> [[a]]


-- | Generic representation of typed syntax trees
--   
--   For details, see: A Generic Abstract Syntax Model for Embedded
--   Languages (ICFP 2012,
--   <a>http://www.cse.chalmers.se/~emax/documents/axelsson2012generic.pdf</a>).
module Language.Syntactic.Syntax

-- | Generic abstract syntax tree, parameterized by a symbol domain
--   
--   <tt>(<a>AST</a> dom (a <a>:-&gt;</a> b))</tt> represents a partially
--   applied (or unapplied) symbol, missing at least one argument, while
--   <tt>(<a>AST</a> dom (<a>Full</a> a))</tt> represents a fully applied
--   symbol, i.e. a complete syntax tree.
data AST dom sig
Sym :: dom sig -> AST dom sig
(:$) :: AST dom (a :-> sig) -> AST dom (Full a) -> AST dom sig

-- | Fully applied abstract syntax tree
type ASTF dom a = AST dom (Full a)

-- | Signature of a fully applied symbol
newtype Full a
Full :: a -> Full a
result :: Full a -> a

-- | Signature of a partially applied (or unapplied) symbol
newtype (:->) a sig
Partial :: (a -> sig) -> :-> a sig

-- | Count the number of symbols in an expression
size :: AST dom sig -> Int

-- | Class for the type-level recursion needed by <a>appSym</a>
class ApplySym sig f dom | sig dom -> f, f -> sig dom
appSym' :: ApplySym sig f dom => AST dom sig -> f

-- | The result type of a symbol with the given signature

-- | Direct sum of two symbol domains
data (:+:) dom1 dom2 a
InjL :: dom1 a -> (dom1 :+: dom2) a
InjR :: dom2 a -> (dom1 :+: dom2) a

-- | Symbol projection
class Project sub sup
prj :: Project sub sup => sup a -> Maybe (sub a)

-- | Symbol subsumption
class Project sub sup => (:<:) sub sup
inj :: :<: sub sup => sub a -> sup a

-- | Generic symbol application
--   
--   <a>appSym</a> has any type of the form:
--   
--   <pre>
--   appSym :: (expr :&lt;: AST dom)
--       =&gt; expr (a :-&gt; b :-&gt; ... :-&gt; Full x)
--       -&gt; (ASTF dom a -&gt; ASTF dom b -&gt; ... -&gt; ASTF dom x)
--   </pre>
appSym :: (ApplySym sig f dom, sym :<: AST dom) => sym sig -> f
instance [overlap ok] Typeable1 Full
instance [overlap ok] Typeable2 :->
instance [overlap ok] Eq a => Eq (Full a)
instance [overlap ok] Show a => Show (Full a)
instance [overlap ok] expr1 :<: expr3 => expr1 :<: (expr2 :+: expr3)
instance [overlap ok] expr1 :<: (expr1 :+: expr2)
instance [overlap ok] expr :<: expr
instance [overlap ok] sub :<: sup => sub :<: AST sup
instance [overlap ok] Project expr1 expr3 => Project expr1 (expr2 :+: expr3)
instance [overlap ok] Project expr1 (expr1 :+: expr2)
instance [overlap ok] Project expr expr
instance [overlap ok] Project sub sup => Project sub (AST sup)
instance [overlap ok] ApplySym sig f dom => ApplySym (a :-> sig) (ASTF dom a -> f) dom
instance [overlap ok] ApplySym (Full a) (ASTF dom a) dom


-- | Generic traversals of <a>AST</a> terms
module Language.Syntactic.Traversal

-- | Map a function over all immediate sub-terms, collecting the results in
--   a list (corresponds to the function with the same name in Scrap Your
--   Boilerplate)
gmapQ :: (forall a. ASTF dom a -> b) -> (forall a. ASTF dom a -> [b])

-- | Map a function over all immediate sub-terms (corresponds to the
--   function with the same name in Scrap Your Boilerplate)
gmapT :: (forall a. ASTF dom a -> ASTF dom a) -> (forall a. ASTF dom a -> ASTF dom a)

-- | Apply a transformation bottom-up over an expression (corresponds to
--   <tt>everywhere</tt> in Scrap Your Boilerplate)
everywhereUp :: (forall a. ASTF dom a -> ASTF dom a) -> (forall a. ASTF dom a -> ASTF dom a)

-- | Apply a transformation top-down over an expression (corresponds to
--   <tt>everywhere'</tt> in Scrap Your Boilerplate)
everywhereDown :: (forall a. ASTF dom a -> ASTF dom a) -> (forall a. ASTF dom a -> ASTF dom a)

-- | List of symbol arguments
data Args c sig
Nil :: Args c (Full a)
(:*) :: c (Full a) -> Args c sig -> Args c (a :-> sig)

-- | Map a function over an <a>Args</a> list and collect the results in an
--   ordinary list
listArgs :: (forall a. c (Full a) -> b) -> Args c sig -> [b]

-- | Map a function over an <a>Args</a> list
mapArgs :: (forall a. c1 (Full a) -> c2 (Full a)) -> (forall sig. Args c1 sig -> Args c2 sig)

-- | Map an applicative function over an <a>Args</a> list
mapArgsA :: Applicative f => (forall a. c1 (Full a) -> f (c2 (Full a))) -> (forall sig. Args c1 sig -> f (Args c2 sig))

-- | Map a monadic function over an <a>Args</a> list
mapArgsM :: Monad m => (forall a. c1 (Full a) -> m (c2 (Full a))) -> (forall sig. Args c1 sig -> m (Args c2 sig))

-- | Apply a (partially applied) symbol to a list of argument terms
appArgs :: AST dom sig -> Args (AST dom) sig -> ASTF dom (DenResult sig)

-- | Fold an <a>AST</a> using a list to hold the results of sub-terms
listFold :: (forall sig. dom sig -> [b] -> b) -> (forall a. ASTF dom a -> b)

-- | "Pattern match" on an <a>AST</a> using a function that gets direct
--   access to the top-most symbol and its sub-trees
match :: (forall sig. a ~ DenResult sig => dom sig -> Args (AST dom) sig -> c (Full a)) -> ASTF dom a -> c (Full a)

-- | <i>Deprecated: Please use `match` instead.</i>
query :: (forall sig. a ~ DenResult sig => dom sig -> Args (AST dom) sig -> c (Full a)) -> ASTF dom a -> c (Full a)

-- | A version of <a>match</a> with a simpler result type
simpleMatch :: (forall sig. a ~ DenResult sig => dom sig -> Args (AST dom) sig -> b) -> ASTF dom a -> b

-- | Fold an <a>AST</a> using an <a>Args</a> list to hold the results of
--   sub-terms
fold :: (forall sig. dom sig -> Args c sig -> c (Full (DenResult sig))) -> (forall a. ASTF dom a -> c (Full a))

-- | Simplified version of <a>fold</a> for situations where all
--   intermediate results have the same type
simpleFold :: (forall sig. dom sig -> Args (Const b) sig -> b) -> (forall a. ASTF dom a -> b)

-- | A version of <a>match</a> where the result is a transformed syntax
--   tree, wrapped in a type constructor <tt>c</tt>
matchTrans :: (forall sig. a ~ DenResult sig => dom sig -> Args (AST dom) sig -> c (ASTF dom' a)) -> ASTF dom a -> c (ASTF dom' a)

-- | Can be used to make an arbitrary type constructor indexed by
--   <tt>(<a>Full</a> a)</tt>. This is useful as the type constructor
--   parameter of <a>Args</a>. That is, use
--   
--   <pre>
--   Args (WrapFull c) ...
--   </pre>
--   
--   instead of
--   
--   <pre>
--   Args c ...
--   </pre>
--   
--   if <tt>c</tt> is not indexed by <tt>(<a>Full</a> a)</tt>.
data WrapFull c a
WrapFull :: c a -> WrapFull c (Full a)
unwrapFull :: WrapFull c (Full a) -> c a

module Language.Syntactic.Interpretation.Equality

-- | Equality for expressions
class Equality expr
equal :: Equality expr => expr a -> expr b -> Bool
exprHash :: Equality expr => expr a -> Hash
instance (Equality expr1, Equality expr2) => Eq ((:+:) expr1 expr2 a)
instance (Equality expr1, Equality expr2) => Equality (expr1 :+: expr2)
instance Equality dom => Eq (AST dom a)
instance Equality dom => Equality (AST dom)

module Language.Syntactic.Interpretation.Render

-- | Render an expression as concrete syntax. A complete instance must
--   define either of the methods <a>render</a> and <a>renderArgs</a>.
class Render expr where render = renderArgs [] renderArgs [] a = render a renderArgs args a = "(" ++ unwords (render a : args) ++ ")"
render :: Render expr => expr a -> String
renderArgs :: Render expr => [String] -> expr a -> String

-- | Print an expression
printExpr :: Render expr => expr a -> IO ()
class Render expr => ToTree expr where toTreeArgs args a = Node (render a) args
toTreeArgs :: ToTree expr => [Tree String] -> expr a -> Tree String

-- | Show syntax tree using ASCII art
showAST :: ToTree dom => AST dom a -> String

-- | Print syntax tree using ASCII art
drawAST :: ToTree dom => AST dom a -> IO ()
instance (ToTree expr1, ToTree expr2) => ToTree (expr1 :+: expr2)
instance ToTree dom => ToTree (AST dom)
instance (Render expr1, Render expr2) => Show ((:+:) expr1 expr2 a)
instance (Render expr1, Render expr2) => Render (expr1 :+: expr2)
instance Render dom => Show (AST dom a)
instance Render dom => Render (AST dom)

module Language.Syntactic.Interpretation.Evaluation

-- | The denotation of a symbol with the given signature
class Eval expr
evaluate :: Eval expr => expr a -> Denotation a
instance (Eval expr1, Eval expr2) => Eval (expr1 :+: expr2)
instance Eval dom => Eval (AST dom)


-- | Type constrained syntax trees
module Language.Syntactic.Constraint

-- | Intersection of type predicates
class (c1 a, c2 a) => (:/\:) c1 c2 a

-- | Universal type predicate
class Top a

-- | Evidence that the predicate <tt>sub</tt> is a subset of <tt>sup</tt>
type Sub sub sup = forall a. Dict (sub a) -> Dict (sup a)

-- | Weaken an intersection
weakL :: Sub (c1 :/\: c2) c1

-- | Weaken an intersection
weakR :: Sub (c1 :/\: c2) c2

-- | Subset relation on type predicates
class (:<) sub sup
sub :: :< sub sup => Sub sub sup

-- | Constrain the result type of the expression by the given predicate
data (:|) expr pred sig
C :: expr sig -> (expr :| pred) sig

-- | Constrain the result type of the expression by the given predicate
--   
--   The difference between <a>:||</a> and <a>:|</a> is seen in the
--   instances of the <a>Sat</a> type:
--   
--   <pre>
--   type Sat (dom :|  pred) = pred :/\: Sat dom
--   type Sat (dom :|| pred) = pred
--   </pre>
data (:||) expr pred sig
C' :: expr sig -> (expr :|| pred) sig

-- | Expressions that constrain their result types
class Constrained expr where type family Sat (expr :: * -> *) :: * -> Constraint
exprDict :: Constrained expr => expr a -> Dict (Sat expr (DenResult a))
type ConstrainedBy expr c = (Constrained expr, Sat expr :< c)

-- | A version of <a>exprDict</a> that returns a constraint for a
--   particular predicate <tt>p</tt> as long as <tt>(p :&lt; Sat dom)</tt>
--   holds
exprDictSub :: ConstrainedBy expr p => expr a -> Dict (p (DenResult a))

-- | A version of <a>exprDict</a> that works for domains of the form
--   <tt>(dom1 :+: dom2)</tt> as long as <tt>(Sat dom1 ~ Sat dom2)</tt>
--   holds
exprDictPlus :: (Constrained dom1, Constrained dom2, Sat dom1 ~ Sat dom2) => AST (dom1 :+: dom2) a -> Dict (Sat dom1 (DenResult a))

-- | Symbol injection (like <a>:&lt;:</a>) with constrained result types
class (Project sub sup, Sat sup a) => InjectC sub sup a
injC :: (InjectC sub sup a, DenResult sig ~ a) => sub sig -> sup sig

-- | Generic symbol application
--   
--   <a>appSymC</a> has any type of the form:
--   
--   <pre>
--   appSymC :: InjectC expr (AST dom) x
--       =&gt; expr (a :-&gt; b :-&gt; ... :-&gt; Full x)
--       -&gt; (ASTF dom a -&gt; ASTF dom b -&gt; ... -&gt; ASTF dom x)
--   </pre>
appSymC :: (ApplySym sig f dom, InjectC sym (AST dom) (DenResult sig)) => sym sig -> f

-- | <a>AST</a> with existentially quantified result type
data ASTE dom
ASTE :: ASTF dom a -> ASTE dom
liftASTE :: (forall a. ASTF dom a -> b) -> ASTE dom -> b
liftASTE2 :: (forall a b. ASTF dom a -> ASTF dom b -> c) -> ASTE dom -> ASTE dom -> c

-- | <a>AST</a> with bounded existentially quantified result type
data ASTB dom
ASTB :: ASTF dom a -> ASTB dom
liftASTB :: (forall a. Sat dom a => ASTF dom a -> b) -> ASTB dom -> b
liftASTB2 :: (forall a b. (Sat dom a, Sat dom b) => ASTF dom a -> ASTF dom b -> c) -> ASTB dom -> ASTB dom -> c
instance [overlap ok] InjectC expr1 expr3 sig => InjectC expr1 (expr2 :+: expr3) sig
instance [overlap ok] InjectC expr1 (expr1 :+: expr2) sig
instance [overlap ok] (Sat expr sig) => InjectC expr expr sig
instance [overlap ok] (InjectC sub sup sig, pred sig) => InjectC sub (sup :|| pred) sig
instance [overlap ok] (InjectC sub sup sig, pred sig) => InjectC sub (sup :| pred) sig
instance [overlap ok] InjectC sub sup sig => InjectC sub (AST sup) sig
instance [overlap ok] Constrained (dom :|| pred)
instance [overlap ok] Constrained dom => Constrained (dom :| pred)
instance [overlap ok] Constrained (sub1 :+: sub2)
instance [overlap ok] Constrained dom => Constrained (AST dom)
instance [overlap ok] ToTree dom => ToTree (dom :|| pred)
instance [overlap ok] Eval dom => Eval (dom :|| pred)
instance [overlap ok] Render dom => Render (dom :|| pred)
instance [overlap ok] Equality dom => Equality (dom :|| pred)
instance [overlap ok] Project sub sup => Project sub (sup :|| pred)
instance [overlap ok] ToTree dom => ToTree (dom :| pred)
instance [overlap ok] Eval dom => Eval (dom :| pred)
instance [overlap ok] Render dom => Render (dom :| pred)
instance [overlap ok] Equality dom => Equality (dom :| pred)
instance [overlap ok] Project sub sup => Project sub (sup :| pred)
instance [overlap ok] ps :< q => (p :/\: ps) :< q
instance [overlap ok] (p :/\: ps) :< p
instance [overlap ok] p :< p
instance [overlap ok] Top a
instance [overlap ok] (c1 a, c2 a) => (:/\:) c1 c2 a


-- | "Syntactic sugar"
module Language.Syntactic.Sugar

-- | It is usually assumed that <tt>(<a>desugar</a> (<a>sugar</a> a))</tt>
--   has the same meaning as <tt>a</tt>.
class Syntactic a dom | a -> dom where type family Internal a
desugar :: Syntactic a dom => a -> ASTF dom (Internal a)
sugar :: Syntactic a dom => ASTF dom (Internal a) -> a

-- | Syntactic type casting
resugar :: (Syntactic a dom, Syntactic b dom, Internal a ~ Internal b) => a -> b

-- | N-ary syntactic functions
--   
--   <a>desugarN</a> has any type of the form:
--   
--   <pre>
--   desugarN ::
--       ( Syntactic a dom
--       , Syntactic b dom
--       , ...
--       , Syntactic x dom
--       ) =&gt; (a -&gt; b -&gt; ... -&gt; x)
--         -&gt; (  ASTF dom (Internal a)
--            -&gt; ASTF dom (Internal b)
--            -&gt; ...
--            -&gt; ASTF dom (Internal x)
--            )
--   </pre>
--   
--   ...and vice versa for <a>sugarN</a>.
class SyntacticN a internal | a -> internal
desugarN :: SyntacticN a internal => a -> internal
sugarN :: SyntacticN a internal => internal -> a

-- | "Sugared" symbol application
--   
--   <a>sugarSym</a> has any type of the form:
--   
--   <pre>
--   sugarSym ::
--       ( expr :&lt;: AST dom
--       , Syntactic a dom
--       , Syntactic b dom
--       , ...
--       , Syntactic x dom
--       ) =&gt; expr (Internal a :-&gt; Internal b :-&gt; ... :-&gt; Full (Internal x))
--         -&gt; (a -&gt; b -&gt; ... -&gt; x)
--   </pre>
sugarSym :: (sym :<: AST dom, ApplySym sig b dom, SyntacticN c b) => sym sig -> c

-- | "Sugared" symbol application
--   
--   <a>sugarSymC</a> has any type of the form:
--   
--   <pre>
--   sugarSymC ::
--       ( InjectC expr (AST dom) (Internal x)
--       , Syntactic a dom
--       , Syntactic b dom
--       , ...
--       , Syntactic x dom
--       ) =&gt; expr (Internal a :-&gt; Internal b :-&gt; ... :-&gt; Full (Internal x))
--         -&gt; (a -&gt; b -&gt; ... -&gt; x)
--   </pre>
sugarSymC :: (InjectC sym (AST dom) (DenResult sig), ApplySym sig b dom, SyntacticN c b) => sym sig -> c
instance [overlap ok] (Syntactic a dom, ia ~ Internal a, SyntacticN b ib) => SyntacticN (a -> b) (AST dom (Full ia) -> ib)
instance [overlap ok] (Syntactic a dom, ia ~ AST dom (Full (Internal a))) => SyntacticN a ia
instance [overlap ok] Syntactic (ASTF dom a) dom


-- | Default implementations of some interpretation functions
module Language.Syntactic.Interpretation.Semantics

-- | A representation of a syntactic construct as a <a>String</a> and an
--   evaluation function. It is not meant to be used as a syntactic symbol
--   in an <a>AST</a>. Its only purpose is to provide the default
--   implementations of functions like <a>equal</a> via the <a>Semantic</a>
--   class.
data Semantics a
Sem :: String -> Denotation a -> Semantics a
semanticName :: Semantics a -> String
semanticEval :: Semantics a -> Denotation a

-- | Class of expressions that can be treated as constructs
class Semantic expr
semantics :: Semantic expr => expr a -> Semantics a

-- | Default implementation of <a>equal</a>
equalDefault :: Semantic expr => expr a -> expr b -> Bool

-- | Default implementation of <a>exprHash</a>
exprHashDefault :: Semantic expr => expr a -> Hash

-- | Default implementation of <a>renderArgs</a>
renderArgsDefault :: Semantic expr => [String] -> expr a -> String

-- | Default implementation of <a>evaluate</a>
evaluateDefault :: Semantic expr => expr a -> Denotation a
instance Eval Semantics
instance Render Semantics
instance Equality Semantics


-- | The basic parts of the syntactic library
module Language.Syntactic


-- | Conditional expressions
module Language.Syntactic.Constructs.Condition
data Condition sig
Condition :: Condition (Bool :-> (a :-> (a :-> Full a)))
instance ToTree Condition
instance Eval Condition
instance Render Condition
instance Equality Condition
instance Semantic Condition
instance Constrained Condition


-- | Provides a simple way to make syntactic constructs for prototyping.
--   Note that <a>Construct</a> is quite unsafe as it only uses
--   <a>String</a> to distinguish between different constructs. Also,
--   <a>Construct</a> has a very free type that allows any number of
--   arguments.
module Language.Syntactic.Constructs.Construct
data Construct sig
Construct :: String -> Denotation sig -> Construct sig
instance ToTree Construct
instance Eval Construct
instance Render Construct
instance Equality Construct
instance Semantic Construct
instance Constrained Construct


-- | Construct for decorating expressions with additional information
module Language.Syntactic.Constructs.Decoration

-- | Decorating symbols with additional information
--   
--   One usage of <a>Decor</a> is to decorate every node of a syntax tree.
--   This is done simply by changing
--   
--   <pre>
--   AST dom sig
--   </pre>
--   
--   to
--   
--   <pre>
--   AST (Decor info dom) sig
--   </pre>
--   
--   Injection/projection of an decorated tree is done using
--   <a>injDecor</a> / <a>prjDecor</a>.
data Decor info expr sig
Decor :: info (DenResult sig) -> expr sig -> Decor info expr sig
decorInfo :: Decor info expr sig -> info (DenResult sig)
decorExpr :: Decor info expr sig -> expr sig
injDecor :: sub :<: sup => info (DenResult sig) -> sub sig -> AST (Decor info sup) sig
prjDecor :: sub :<: sup => AST (Decor info sup) sig -> Maybe (info (DenResult sig), sub sig)

-- | Get the decoration of the top-level node
getInfo :: AST (Decor info dom) sig -> info (DenResult sig)

-- | Update the decoration of the top-level node
updateDecor :: (info a -> info a) -> ASTF (Decor info dom) a -> ASTF (Decor info dom) a

-- | Lift a function that operates on expressions with associated
--   information to operate on an <a>Decor</a> expression. This function is
--   convenient to use together with e.g. <tt>queryNodeSimple</tt> when the
--   domain has the form <tt>(<a>Decor</a> info dom)</tt>.
liftDecor :: (expr s -> info (DenResult s) -> b) -> (Decor info expr s -> b)

-- | Collect the decorations of all nodes
collectInfo :: (forall sig. info sig -> b) -> AST (Decor info dom) sig -> [b]

-- | Rendering of decorated syntax trees
toTreeDecor :: (Render info, ToTree dom) => ASTF (Decor info dom) a -> Tree String

-- | Show an decorated syntax tree using ASCII art
showDecor :: (Render info, ToTree dom) => ASTF (Decor info dom) a -> String

-- | Print an decorated syntax tree using ASCII art
drawDecor :: (Render info, ToTree dom) => ASTF (Decor info dom) a -> IO ()

-- | Strip decorations from an <a>AST</a>
stripDecor :: AST (Decor info dom) sig -> AST dom sig
instance Eval expr => Eval (Decor info expr)
instance ToTree expr => ToTree (Decor info expr)
instance Render expr => Render (Decor info expr)
instance Equality expr => Equality (Decor info expr)
instance Project sub sup => Project sub (Decor info sup)
instance Constrained expr => Constrained (Decor info expr)


-- | Identity function
module Language.Syntactic.Constructs.Identity

-- | Identity function
data Identity sig
Id :: Identity (a :-> Full a)
instance ToTree Identity
instance Eval Identity
instance Render Identity
instance Equality Identity
instance Semantic Identity
instance Constrained Identity


-- | Literal expressions
module Language.Syntactic.Constructs.Literal
data Literal sig
Literal :: a -> Literal (Full a)
instance Eval Literal
instance ToTree Literal
instance Render Literal
instance Equality Literal
instance Constrained Literal


-- | Monadic constructs
--   
--   This module is based on the paper <i>Generic Monadic Constructs for
--   Embedded Languages</i> (Persson et al., IFL 2011
--   <a>http://www.cse.chalmers.se/~emax/documents/persson2011generic.pdf</a>).
module Language.Syntactic.Constructs.Monad
data MONAD m sig
Return :: MONAD m (a :-> Full (m a))
Bind :: MONAD m (m a :-> ((a -> m b) :-> Full (m b)))
Then :: MONAD m (m a :-> (m b :-> Full (m b)))
When :: MONAD m (Bool :-> (m () :-> Full (m ())))

-- | Projection with explicit monad type
prjMonad :: MONAD m :<: sup => Proxy (m ()) -> sup sig -> Maybe (MONAD m sig)
instance Monad m => ToTree (MONAD m)
instance Monad m => Eval (MONAD m)
instance Monad m => Render (MONAD m)
instance Monad m => Equality (MONAD m)
instance Monad m => Semantic (MONAD m)
instance Constrained (MONAD m)


-- | Construction and elimination of tuples in the object language
module Language.Syntactic.Constructs.Tuple

-- | Expressions for constructing tuples
data Tuple sig
Tup2 :: Tuple (a :-> (b :-> Full (a, b)))
Tup3 :: Tuple (a :-> (b :-> (c :-> Full (a, b, c))))
Tup4 :: Tuple (a :-> (b :-> (c :-> (d :-> Full (a, b, c, d)))))
Tup5 :: Tuple (a :-> (b :-> (c :-> (d :-> (e :-> Full (a, b, c, d, e))))))
Tup6 :: Tuple (a :-> (b :-> (c :-> (d :-> (e :-> (f :-> Full (a, b, c, d, e, f)))))))
Tup7 :: Tuple (a :-> (b :-> (c :-> (d :-> (e :-> (f :-> (g :-> Full (a, b, c, d, e, f, g))))))))

-- | These families (<a>Sel1'</a> - <a>Sel7'</a>) are needed because of the
--   problem described in:
--   
--   
--   <a>http://emil-fp.blogspot.com/2011/08/fundeps-weaker-than-type-families.html</a>

-- | Expressions for selecting elements of a tuple
data Select a
Sel1 :: Select (a :-> Full b)
Sel2 :: Select (a :-> Full b)
Sel3 :: Select (a :-> Full b)
Sel4 :: Select (a :-> Full b)
Sel5 :: Select (a :-> Full b)
Sel6 :: Select (a :-> Full b)
Sel7 :: Select (a :-> Full b)

-- | Return the selected position, e.g.
--   
--   <pre>
--   selectPos (Sel3 poly :: Select Poly ((Int,Int,Int,Int) :-&gt; Full Int)) = 3
--   </pre>
selectPos :: Select a -> Int
instance (Syntactic a dom, Syntactic b dom, Syntactic c dom, Syntactic d dom, Syntactic e dom, Syntactic f dom, Syntactic g dom, InjectC Tuple dom (Internal a, Internal b, Internal c, Internal d, Internal e, Internal f, Internal g), InjectC Select dom (Internal a), InjectC Select dom (Internal b), InjectC Select dom (Internal c), InjectC Select dom (Internal d), InjectC Select dom (Internal e), InjectC Select dom (Internal f), InjectC Select dom (Internal g)) => Syntactic (a, b, c, d, e, f, g) dom
instance (Syntactic a dom, Syntactic b dom, Syntactic c dom, Syntactic d dom, Syntactic e dom, Syntactic f dom, InjectC Tuple dom (Internal a, Internal b, Internal c, Internal d, Internal e, Internal f), InjectC Select dom (Internal a), InjectC Select dom (Internal b), InjectC Select dom (Internal c), InjectC Select dom (Internal d), InjectC Select dom (Internal e), InjectC Select dom (Internal f)) => Syntactic (a, b, c, d, e, f) dom
instance (Syntactic a dom, Syntactic b dom, Syntactic c dom, Syntactic d dom, Syntactic e dom, InjectC Tuple dom (Internal a, Internal b, Internal c, Internal d, Internal e), InjectC Select dom (Internal a), InjectC Select dom (Internal b), InjectC Select dom (Internal c), InjectC Select dom (Internal d), InjectC Select dom (Internal e)) => Syntactic (a, b, c, d, e) dom
instance (Syntactic a dom, Syntactic b dom, Syntactic c dom, Syntactic d dom, InjectC Tuple dom (Internal a, Internal b, Internal c, Internal d), InjectC Select dom (Internal a), InjectC Select dom (Internal b), InjectC Select dom (Internal c), InjectC Select dom (Internal d)) => Syntactic (a, b, c, d) dom
instance (Syntactic a dom, Syntactic b dom, Syntactic c dom, InjectC Tuple dom (Internal a, Internal b, Internal c), InjectC Select dom (Internal a), InjectC Select dom (Internal b), InjectC Select dom (Internal c)) => Syntactic (a, b, c) dom
instance (Syntactic a dom, Syntactic b dom, InjectC Tuple dom (Internal a, Internal b), InjectC Select dom (Internal a), InjectC Select dom (Internal b)) => Syntactic (a, b) dom
instance ToTree Select
instance Eval Select
instance Render Select
instance Equality Select
instance Semantic Select
instance Constrained Select
instance ToTree Tuple
instance Eval Tuple
instance Render Tuple
instance Equality Tuple
instance Semantic Tuple
instance Constrained Tuple


-- | An alternative to <a>Data.Dynamic</a> with a different constraint on
--   <a>toDyn</a>
module Data.DynamicAlt
data Dynamic
Dynamic :: TypeRep -> Any -> Dynamic
toDyn :: Typeable (a -> b) => Proxy (a -> b) -> a -> Dynamic
fromDyn :: Typeable a => Dynamic -> Maybe a


-- | General binding constructs
module Language.Syntactic.Constructs.Binding

-- | Variable identifier
newtype VarId
VarId :: Integer -> VarId
varInteger :: VarId -> Integer
showVar :: VarId -> String

-- | Variables
data Variable a
Variable :: VarId -> Variable (Full a)

-- | Lambda binding
data Lambda a
Lambda :: VarId -> Lambda (b :-> Full (a -> b))

-- | Let binding
--   
--   <a>Let</a> is just an application operator with flipped argument
--   order. The argument <tt>(a -&gt; b)</tt> is preferably constructed by
--   <a>Lambda</a>.
data Let a
Let :: Let (a :-> ((a -> b) :-> Full b))

-- | Should be a capture-avoiding substitution, but it is currently not
--   correct.
--   
--   Note: Variables with a different type than the new expression will be
--   silently ignored.
subst :: (ConstrainedBy dom Typeable, Project Lambda dom, Project Variable dom) => VarId -> ASTF dom a -> ASTF dom b -> ASTF dom b

-- | Beta-reduction of an expression. The expression to be reduced is
--   assumed to be a <a>Lambda</a>.
betaReduce :: (ConstrainedBy dom Typeable, Project Lambda dom, Project Variable dom) => ASTF dom a -> ASTF dom (a -> b) -> ASTF dom b

-- | Evaluation of expressions with variables
class EvalBind sub
evalBindSym :: (EvalBind sub, EvalBind dom, ConstrainedBy dom Typeable, Typeable (DenResult sig)) => sub sig -> Args (AST dom) sig -> Reader [(VarId, Dynamic)] (DenResult sig)

-- | Evaluation of possibly open expressions
evalBindM :: (EvalBind dom, ConstrainedBy dom Typeable) => ASTF dom a -> Reader [(VarId, Dynamic)] a

-- | Evaluation of closed expressions
evalBind :: (EvalBind dom, ConstrainedBy dom Typeable) => ASTF dom a -> a

-- | Apply a symbol denotation to a list of arguments
appDen :: Denotation sig -> Args Identity sig -> DenResult sig

-- | Convenient default implementation of <a>evalBindSym</a>
evalBindSymDefault :: (Eval sub, EvalBind dom, ConstrainedBy dom Typeable) => sub sig -> Args (AST dom) sig -> Reader [(VarId, Dynamic)] (DenResult sig)

-- | Environments containing a list of variable equivalences
class VarEqEnv a
prjVarEqEnv :: VarEqEnv a => a -> [(VarId, VarId)]
modVarEqEnv :: VarEqEnv a => ([(VarId, VarId)] -> [(VarId, VarId)]) -> (a -> a)

-- | Alpha-equivalence
class AlphaEq sub1 sub2 dom env
alphaEqSym :: AlphaEq sub1 sub2 dom env => sub1 a -> Args (AST dom) a -> sub2 b -> Args (AST dom) b -> Reader env Bool
alphaEqM :: AlphaEq dom dom dom env => ASTF dom a -> ASTF dom b -> Reader env Bool
alphaEqM2 :: AlphaEq dom dom dom env => ASTF dom b -> dom a -> Args (AST dom) a -> Reader env Bool

-- | Alpha-equivalence on lambda expressions. Free variables are taken to
--   be equivalent if they have the same identifier.
alphaEq :: AlphaEq dom dom dom [(VarId, VarId)] => ASTF dom a -> ASTF dom b -> Bool
alphaEqSymDefault :: (Equality sub, AlphaEq dom dom dom env) => sub a -> Args (AST dom) a -> sub b -> Args (AST dom) b -> Reader env Bool
alphaEqChildren :: AlphaEq dom dom dom env => AST dom a -> AST dom b -> Reader env Bool
instance Eq VarId
instance Ord VarId
instance Num VarId
instance Real VarId
instance Integral VarId
instance Enum VarId
instance Ix VarId
instance (AlphaEq dom dom dom env, VarEqEnv env) => AlphaEq Lambda Lambda dom env
instance (AlphaEq dom dom dom env, VarEqEnv env) => AlphaEq Variable Variable dom env
instance (AlphaEq dom dom dom env, Monad m) => AlphaEq (MONAD m) (MONAD m) dom env
instance AlphaEq sub sub dom env => AlphaEq (Decor info sub) (Decor info sub) dom env
instance AlphaEq dom dom dom env => AlphaEq Tuple Tuple dom env
instance AlphaEq dom dom dom env => AlphaEq Select Select dom env
instance AlphaEq dom dom dom env => AlphaEq Literal Literal dom env
instance AlphaEq dom dom dom env => AlphaEq Let Let dom env
instance AlphaEq dom dom dom env => AlphaEq Identity Identity dom env
instance AlphaEq dom dom dom env => AlphaEq Construct Construct dom env
instance AlphaEq dom dom dom env => AlphaEq Condition Condition dom env
instance AlphaEq sub sub dom env => AlphaEq (sub :|| pred) (sub :|| pred) dom env
instance AlphaEq sub sub dom env => AlphaEq (sub :| pred) (sub :| pred) dom env
instance (AlphaEq subA1 subB1 dom env, AlphaEq subA2 subB2 dom env) => AlphaEq (subA1 :+: subA2) (subB1 :+: subB2) dom env
instance VarEqEnv [(VarId, VarId)]
instance EvalBind Lambda
instance EvalBind Variable
instance Monad m => EvalBind (MONAD m)
instance EvalBind Let
instance EvalBind Select
instance EvalBind Tuple
instance EvalBind Condition
instance EvalBind Literal
instance EvalBind Construct
instance EvalBind Identity
instance EvalBind dom => EvalBind (Decor info dom)
instance EvalBind dom => EvalBind (dom :|| pred)
instance EvalBind dom => EvalBind (dom :| pred)
instance (EvalBind sub1, EvalBind sub2) => EvalBind (sub1 :+: sub2)
instance Eval Let
instance ToTree Let
instance Render Let
instance Equality Let
instance Constrained Let
instance ToTree Lambda
instance Render Lambda
instance Equality Lambda
instance Constrained Lambda
instance ToTree Variable
instance Render Variable
instance Equality Variable
instance Constrained Variable
instance Show VarId


-- | This module provides binding constructs using higher-order syntax and
--   a function (<a>reify</a>) for translating to first-order syntax.
--   Expressions constructed using the exported interface (specifically,
--   not introducing <a>Variable</a>s explicitly) are guaranteed to have
--   well-behaved translation.
module Language.Syntactic.Constructs.Binding.HigherOrder

-- | Variables
data Variable a

-- | Let binding
--   
--   <a>Let</a> is just an application operator with flipped argument
--   order. The argument <tt>(a -&gt; b)</tt> is preferably constructed by
--   <a>Lambda</a>.
data Let a
Let :: Let (a :-> ((a -> b) :-> Full b))

-- | Higher-order lambda binding
data HOLambda dom p a
HOLambda :: (ASTF (HODomain dom p) a -> ASTF (HODomain dom p) b) -> HOLambda dom p (Full (a -> b))
type HODomain dom p = (HOLambda dom p :+: (Variable :+: dom)) :|| p

-- | Lambda binding
lambda :: (p a, p (a -> b)) => (ASTF (HODomain dom p) a -> ASTF (HODomain dom p) b) -> ASTF (HODomain dom p) (a -> b)
reifyM :: AST (HODomain dom p) a -> State VarId (AST ((Lambda :+: (Variable :+: dom)) :|| p) a)

-- | Translating expressions with higher-order binding to corresponding
--   expressions using first-order binding
reifyTop :: AST (HODomain dom p) a -> AST ((Lambda :+: (Variable :+: dom)) :|| p) a

-- | Reify an n-ary syntactic function
reify :: Syntactic a (HODomain dom p) => a -> ASTF ((Lambda :+: (Variable :+: dom)) :|| p) (Internal a)
instance (Syntactic a (HODomain dom p), Syntactic b (HODomain dom p), p (Internal a), p (Internal a -> Internal b)) => Syntactic (a -> b) (HODomain dom p)
instance Constrained (HOLambda dom p)


-- | Monadic constructs
--   
--   This module is based on the paper <i>Generic Monadic Constructs for
--   Embedded Languages</i> (Persson et al., IFL 2011
--   <a>http://www.cse.chalmers.se/~emax/documents/persson2011generic.pdf</a>).
module Language.Syntactic.Frontend.Monad

-- | User interface to embedded monadic programs
newtype Mon dom m a
Mon :: (forall r. (Monad m, Typeable r, InjectC (MONAD m) dom (m r)) => Cont (ASTF (HODomain dom Typeable) (m r)) a) -> Mon dom m a
unMon :: Mon dom m a -> forall r. (Monad m, Typeable r, InjectC (MONAD m) dom (m r)) => Cont (ASTF (HODomain dom Typeable) (m r)) a

-- | One-layer desugaring of monadic actions
desugarMonad :: (InjectC (MONAD m) dom (m a), Monad m, Typeable1 m, Typeable a) => Mon dom m (ASTF (HODomain dom Typeable) a) -> ASTF (HODomain dom Typeable) (m a)

-- | One-layer sugaring of monadic actions
sugarMonad :: (Monad m, Typeable1 m, Typeable a) => ASTF (HODomain dom Typeable) (m a) -> Mon dom m (ASTF (HODomain dom Typeable) a)
instance Functor (Mon dom m)
instance (Syntactic a (HODomain dom Typeable), InjectC (MONAD m) dom (m (Internal a)), Monad m, Typeable1 m, Typeable (Internal a)) => Syntactic (Mon dom m a) (HODomain dom Typeable)
instance Monad m => Monad (Mon dom m)


-- | Basic optimization
module Language.Syntactic.Constructs.Binding.Optimize

-- | Constant folder
--   
--   Given an expression and the statically known value of that expression,
--   returns a (possibly) new expression with the same meaning as the
--   original. Typically, the result will be a <a>Literal</a>, if the
--   relevant type constraints are satisfied.
type ConstFolder dom = forall a. ASTF dom a -> a -> ASTF dom a

-- | Basic optimization
class Optimize sym
optimizeSym :: (Optimize sym, Optimize' dom) => ConstFolder dom -> (sym sig -> AST dom sig) -> sym sig -> Args (AST dom) sig -> Writer (Set VarId) (ASTF dom (DenResult sig))
type Optimize' dom = (Optimize dom, EvalBind dom, AlphaEq dom dom dom [(VarId, VarId)], ConstrainedBy dom Typeable)
optimizeM :: Optimize' dom => ConstFolder dom -> ASTF dom a -> Writer (Set VarId) (ASTF dom a)

-- | Optimize an expression
optimize :: Optimize' dom => ConstFolder dom -> ASTF dom a -> ASTF dom a

-- | Convenient default implementation of <a>optimizeSym</a> (uses
--   <a>evalBind</a> to partially evaluate)
optimizeSymDefault :: Optimize' dom => ConstFolder dom -> (sym sig -> AST dom sig) -> sym sig -> Args (AST dom) sig -> Writer (Set VarId) (ASTF dom (DenResult sig))
instance Optimize Lambda
instance Optimize Variable
instance Optimize Condition
instance Optimize Let
instance Optimize Select
instance Optimize Tuple
instance Optimize Literal
instance Optimize Construct
instance Optimize Identity
instance Optimize dom => Optimize (dom :|| p)
instance Optimize dom => Optimize (dom :| p)
instance (Optimize sub1, Optimize sub2) => Optimize (sub1 :+: sub2)


-- | Simple code motion transformation performing common sub-expression
--   elimination and variable hoisting. Note that the implementation is
--   very inefficient.
--   
--   The code is based on an implementation by Gergely Dévai.
module Language.Syntactic.Sharing.SimpleCodeMotion

-- | Interface for binding constructs
data BindDict dom
BindDict :: (forall a. dom a -> Maybe VarId) -> (forall a. dom a -> Maybe VarId) -> (forall a. ASTF dom a -> VarId -> dom (Full a)) -> (forall a b. ASTF dom a -> ASTF dom b -> VarId -> dom (b :-> Full (a -> b))) -> (forall a b. ASTF dom b -> dom (a :-> ((a -> b) :-> Full b))) -> BindDict dom
prjVariable :: BindDict dom -> forall a. dom a -> Maybe VarId
prjLambda :: BindDict dom -> forall a. dom a -> Maybe VarId
injVariable :: BindDict dom -> forall a. ASTF dom a -> VarId -> dom (Full a)
injLambda :: BindDict dom -> forall a b. ASTF dom a -> ASTF dom b -> VarId -> dom (b :-> Full (a -> b))
injLet :: BindDict dom -> forall a b. ASTF dom b -> dom (a :-> ((a -> b) :-> Full b))

-- | Perform common sub-expression elimination and variable hoisting
codeMotion :: (ConstrainedBy dom Typeable, AlphaEq dom dom dom [(VarId, VarId)]) => BindDict dom -> (forall a. dom a -> Bool) -> ASTF dom a -> State VarId (ASTF dom a)
defaultBindDict :: (Variable :<: dom, Lambda :<: dom, Let :<: dom, Constrained dom) => BindDict (dom :|| Typeable)

-- | Like <a>reify</a> but with common sub-expression elimination and
--   variable hoisting
reifySmart :: (AlphaEq dom dom ((Lambda :+: (Variable :+: dom)) :|| Typeable) [(VarId, VarId)], Syntactic a (HODomain dom Typeable)) => BindDict ((Lambda :+: (Variable :+: dom)) :|| Typeable) -> (forall a. ((Lambda :+: (Variable :+: dom)) :|| Typeable) a -> Bool) -> a -> ASTF ((Lambda :+: (Variable :+: dom)) :|| Typeable) (Internal a)
reifySmartDefault :: (Let :<: dom, AlphaEq dom dom ((Lambda :+: (Variable :+: dom)) :|| Typeable) [(VarId, VarId)], Syntactic a (HODomain dom Typeable)) => (forall a. ((Lambda :+: (Variable :+: dom)) :|| Typeable) a -> Bool) -> a -> ASTF ((Lambda :+: (Variable :+: dom)) :|| Typeable) (Internal a)


-- | Representation and manipulation of abstract syntax graphs
module Language.Syntactic.Sharing.Graph

-- | Node identifier
newtype NodeId
NodeId :: Integer -> NodeId
nodeInteger :: NodeId -> Integer
showNode :: NodeId -> String

-- | Placeholder for a syntax tree
data Node a
Node :: NodeId -> Node (Full a)

-- | Environment for alpha-equivalence
class NodeEqEnv dom a
prjNodeEqEnv :: NodeEqEnv dom a => a -> NodeEnv dom
modNodeEqEnv :: NodeEqEnv dom a => (NodeEnv dom -> NodeEnv dom) -> (a -> a)
type EqEnv dom = ([(VarId, VarId)], NodeEnv dom)
type NodeEnv dom = (Array NodeId Hash, Array NodeId (ASTB dom))

-- | "Abstract Syntax Graph"
--   
--   A representation of a syntax tree with explicit sharing. An <a>ASG</a>
--   is valid if and only if <a>inlineAll</a> succeeds (and the
--   <a>numNodes</a> field is correct).
data ASG dom a
ASG :: ASTF (NodeDomain dom) a -> [(NodeId, ASTB (NodeDomain dom))] -> NodeId -> ASG dom a

-- | Top-level expression
topExpression :: ASG dom a -> ASTF (NodeDomain dom) a

-- | Mapping from node id to sub-expression
graphNodes :: ASG dom a -> [(NodeId, ASTB (NodeDomain dom))]

-- | Total number of nodes
numNodes :: ASG dom a -> NodeId
type NodeDomain dom = (Node :+: dom) :|| Sat dom

-- | Show syntax graph using ASCII art
showASG :: ToTree dom => ASG dom a -> String

-- | Print syntax graph using ASCII art
drawASG :: ToTree dom => ASG dom a -> IO ()

-- | Update the node identifiers in an <a>AST</a> using the supplied
--   reindexing function
reindexNodesAST :: (NodeId -> NodeId) -> AST (NodeDomain dom) a -> AST (NodeDomain dom) a

-- | Reindex the nodes according to the given index mapping. The number of
--   nodes is unchanged, so if the index mapping is not 1:1, the resulting
--   graph will contain duplicates.
reindexNodes :: (NodeId -> NodeId) -> ASG dom a -> ASG dom a

-- | Reindex the nodes to be in the range <tt>[0 .. l-1]</tt>, where
--   <tt>l</tt> is the number of nodes in the graph
reindexNodesFrom0 :: ASG dom a -> ASG dom a

-- | Remove duplicate nodes from a graph. The function only looks at the
--   <a>NodeId</a> of each node. The <a>numNodes</a> field is updated
--   accordingly.
nubNodes :: ASG dom a -> ASG dom a

-- | Pattern functor representation of an <a>AST</a> with <a>Node</a>s
data SyntaxPF dom a
AppPF :: a -> a -> SyntaxPF dom a
NodePF :: NodeId -> a -> SyntaxPF dom a
DomPF :: dom b -> SyntaxPF dom a

-- | Folding over a graph
--   
--   The user provides a function to fold a single constructor (an
--   "algebra"). The result contains the result of folding the whole graph
--   as well as the result of each internal node, represented both as an
--   array and an association list. Each node is processed exactly once.
foldGraph :: (SyntaxPF dom b -> b) -> ASG dom a -> (b, (Array NodeId b, [(NodeId, b)]))

-- | Convert an <a>ASG</a> to an <a>AST</a> by inlining all nodes
inlineAll :: ConstrainedBy dom Typeable => ASG dom a -> ASTF dom a

-- | Find the child nodes of each node in an expression. The child nodes of
--   a node <tt>n</tt> are the first nodes along all paths from <tt>n</tt>.
nodeChildren :: ASG dom a -> [(NodeId, [NodeId])]

-- | Count the number of occurrences of each node in an expression
occurrences :: ASG dom a -> Array NodeId Int

-- | Inline all nodes that are not shared
inlineSingle :: ConstrainedBy dom Typeable => ASG dom a -> ASG dom a

-- | Compute a table (both array and list representation) of hash values
--   for each node
hashNodes :: Equality dom => ASG dom a -> (Array NodeId Hash, [(NodeId, Hash)])

-- | Partitions the nodes such that two nodes are in the same sub-list if
--   and only if they are alpha-equivalent.
partitionNodes :: (Equality dom, AlphaEq dom dom (NodeDomain dom) (EqEnv (NodeDomain dom))) => ASG dom a -> [[NodeId]]

-- | Common sub-expression elimination based on alpha-equivalence
cse :: (Equality dom, AlphaEq dom dom (NodeDomain dom) (EqEnv (NodeDomain dom))) => ASG dom a -> ASG dom a
instance Eq NodeId
instance Ord NodeId
instance Num NodeId
instance Real NodeId
instance Integral NodeId
instance Enum NodeId
instance Ix NodeId
instance Functor (SyntaxPF dom)
instance (AlphaEq dom dom dom env, NodeEqEnv dom env) => AlphaEq Node Node dom env
instance VarEqEnv (EqEnv dom)
instance NodeEqEnv dom (EqEnv dom)
instance ToTree Node
instance Render Node
instance Constrained Node
instance Show NodeId

module Language.Syntactic.Sharing.StableName

-- | <a>StableName</a> of a <tt>(c (Full a))</tt> with hidden result type
data StName c
StName :: StableName (c (Full a)) -> StName c
hash :: StName c -> Int

-- | A hash table from <a>StName</a> to <a>NodeId</a> (with <a>hash</a> as
--   the hashing function). I.e. it is assumed that the <a>StName</a>s at
--   each entry all have the same hash, and that this number is equal to
--   the entry's key.
type History c = IntMap [(StName c, NodeId)]

-- | Lookup a name in the history
lookHistory :: History c -> StName c -> Maybe NodeId

-- | Insert the name into the history
remember :: StName c -> NodeId -> History c -> History c

-- | Return a fresh identifier from the given supply
fresh :: (Enum a, MonadIO m) => IORef a -> m a
instance Eq (StName c)


-- | Reifying the sharing in an <a>AST</a>
--   
--   This module is based on the paper <i>Type-Safe Observable Sharing in
--   Haskell</i> (Andy Gill, 2009,
--   <a>http://dx.doi.org/10.1145/1596638.1596653</a>).
module Language.Syntactic.Sharing.Reify

-- | Convert a syntax tree to a sharing-preserving graph
--   
--   This function is not referentially transparent (hence the <a>IO</a>).
--   However, it is well-behaved in the sense that the worst thing that
--   could happen is that sharing is lost. It is not possible to get false
--   sharing.
reifyGraph :: Constrained dom => (forall a. ASTF dom a -> Bool) -> ASTF dom a -> IO (ASG dom a)


-- | This module is similar to <a>Language.Syntactic.Sharing.Reify</a>, but
--   operates on <tt><a>AST</a> (<a>HODomain</a> dom p)</tt> rather than a
--   general <a>AST</a>. The reason for having this module is that when
--   using <a>HODomain</a>, it is important to do simultaneous sharing
--   analysis and <a>HOLambda</a> reification. Obviously we cannot do
--   sharing analysis first (using <a>reifyGraph</a> from
--   <a>Language.Syntactic.Sharing.Reify</a>), since it needs to be able to
--   look inside <a>HOLambda</a>. On the other hand, if we did
--   <a>HOLambda</a> reification first (using <a>reify</a>), we would
--   destroy the sharing.
--   
--   This module is based on the paper <i>Type-Safe Observable Sharing in
--   Haskell</i> (Andy Gill, 2009,
--   <a>http://dx.doi.org/10.1145/1596638.1596653</a>).
module Language.Syntactic.Sharing.ReifyHO

-- | Convert a syntax tree to a sharing-preserving graph
reifyGraphTop :: (forall a. ASTF (HODomain dom p) a -> Bool) -> ASTF (HODomain dom p) a -> IO (ASG ((Lambda :+: (Variable :+: dom)) :|| p) a, VarId)

-- | Reifying an n-ary syntactic function to a sharing-preserving graph
--   
--   This function is not referentially transparent (hence the <a>IO</a>).
--   However, it is well-behaved in the sense that the worst thing that
--   could happen is that sharing is lost. It is not possible to get false
--   sharing.
reifyGraph :: Syntactic a (HODomain dom p) => (forall a. ASTF (HODomain dom p) a -> Bool) -> a -> IO (ASG ((Lambda :+: (Variable :+: dom)) :|| p) (Internal a), VarId)