Language.Syntactic.Sharing.Graph

Representation and manipulation of abstract syntax graphs

Representation

newtype NodeId

Node identifier

Constructors

NodeId

Fields

nodeInteger :: Integer

Instances

Enum NodeId

Eq NodeId

Integral NodeId

Num NodeId

Ord NodeId

Real NodeId

Show NodeId

Ix NodeId

NodeEqEnv dom (EqEnv dom)

VarEqEnv (EqEnv dom)

data Node ctx a where

Placeholder for a syntax tree

Constructors

Node :: Sat ctx a => NodeId -> Node ctx (Full a)

Instances

WitnessCons (Node ctx)

ToTree (Node ctx)

Render (Node ctx)

(AlphaEq dom dom dom env, NodeEqEnv dom env) => AlphaEq (Node ctx) (Node ctx) dom env

showNode :: NodeId -> String

data SomeAST dom where

An ASTF with hidden result type

Constructors

SomeAST :: Typeable a => ASTF dom a -> SomeAST dom

Instances

NodeEqEnv dom (EqEnv dom)

VarEqEnv (EqEnv dom)

class NodeEqEnv dom a where

Environment for alpha-equivalence

Methods

prjNodeEqEnv :: a -> NodeEnv dom

modNodeEqEnv :: (NodeEnv dom -> NodeEnv dom) -> a -> a

Instances

NodeEqEnv dom (EqEnv dom)

type EqEnv dom = ([(VarId, VarId)], NodeEnv dom)

type NodeEnv dom = (Array NodeId Hash, Array NodeId (SomeAST dom))

data ASG ctx dom a

"Abstract Syntax Graph"

A representation of a syntax tree with explicit sharing. An ASG is valid if and only if inlineAll succeeds (and the numNodes field is correct).

Constructors

ASG

Fields

topExpression :: ASTF (Node ctx :+: dom) a

Top-level expression

graphNodes :: [(NodeId, SomeAST (Node ctx :+: dom))]

Mapping from node id to sub-expression

numNodes :: NodeId

Total number of nodes

showASG :: ToTree dom => ASG ctx dom a -> String

Show syntax graph using ASCII art

drawASG :: ToTree dom => ASG ctx dom a -> IO ()

Print syntax graph using ASCII art

reindexNodesAST :: (NodeId -> NodeId) -> AST (Node ctx :+: dom) a -> AST (Node ctx :+: dom) a

Update the node identifiers in an AST using the supplied reindexing function

reindexNodes :: (NodeId -> NodeId) -> ASG ctx dom a -> ASG ctx 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.

reindexNodesFrom0 :: ASG ctx dom a -> ASG ctx dom a

Reindex the nodes to be in the range [0 .. l-1], where l is the number of nodes in the graph

nubNodes :: ASG ctx dom a -> ASG ctx dom a

Remove duplicate nodes from a graph. The function only looks at the NodeId of each node. The numNodes field is updated accordingly.

liftSome2 :: (forall a b. ASTF (Node ctx :+: dom) a -> ASTF (Node ctx :+: dom) b -> c) -> SomeAST (Node ctx :+: dom) -> SomeAST (Node ctx :+: dom) -> c

Folding

data SyntaxPF dom a where

Pattern functor representation of an AST with Nodes

Constructors

AppPF :: a -> a -> SyntaxPF dom a

NodePF :: NodeId -> a -> SyntaxPF dom a

DomPF :: dom b -> SyntaxPF dom a

Instances

Functor (SyntaxPF dom)

foldGraph :: forall ctx dom a b. (SyntaxPF dom b -> b) -> ASG ctx dom a -> (b, (Array NodeId b, [(NodeId, b)]))

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.

Inlining

inlineAll :: forall ctx dom a. Typeable a => ASG ctx dom a -> ASTF dom a

Convert an ASG to an AST by inlining all nodes

nodeChildren :: ASG ctx dom a -> [(NodeId, [NodeId])]

Find the child nodes of each node in an expression. The child nodes of a node n are the first nodes along all paths from n.

occurrences :: ASG ctx dom a -> Array NodeId Int

Count the number of occurrences of each node in an expression

inlineSingle :: forall ctx dom a. Typeable a => ASG ctx dom a -> ASG ctx dom a

Inline all nodes that are not shared

Sharing

hashNodes :: ExprEq dom => ASG ctx dom a -> (Array NodeId Hash, [(NodeId, Hash)])

Compute a table (both array and list representation) of hash values for each node

partitionNodes :: forall ctx dom a. (ExprEq dom, AlphaEq dom dom (Node ctx :+: dom) (EqEnv (Node ctx :+: dom))) => ASG ctx dom a -> [[NodeId]]

Partitions the nodes such that two nodes are in the same sub-list if and only if they are alpha-equivalent.

cse :: (ExprEq dom, AlphaEq dom dom (Node ctx :+: dom) (EqEnv (Node ctx :+: dom))) => ASG ctx dom a -> ASG ctx dom a

Common sub-expression elimination based on alpha-equivalence