Representation and manipulation of abstract syntax graphs
- newtype NodeId = NodeId {}
- data Node ctx a where
- showNode :: NodeId -> String
- prjNode :: (Node ctx) :<: sup => Proxy ctx -> sup a -> Maybe (Node ctx a)
- data SomeAST dom where
- data ASG ctx dom a = ASG {}
- showASG :: ToTree dom => ASG ctx dom a -> String
- drawASG :: ToTree dom => ASG ctx dom a -> IO ()
- reindexNodesAST :: (NodeId -> NodeId) -> AST (Node ctx :+: dom) a -> AST (Node ctx :+: dom) a
- reindexNodes :: (NodeId -> NodeId) -> ASG ctx dom a -> ASG ctx dom a
- reindexNodesFrom0 :: ASG ctx dom a -> ASG ctx dom a
- nubNodes :: ASG ctx dom a -> ASG ctx dom a
- liftSome2 :: (forall a b. ASTF (Node ctx :+: dom) a -> ASTF (Node ctx :+: dom) b -> c) -> SomeAST (Node ctx :+: dom) -> SomeAST (Node ctx :+: dom) -> c
- data SyntaxPF dom a where
- foldGraph :: forall ctx dom a b. (SyntaxPF dom b -> b) -> ASG ctx dom a -> (b, (Array NodeId b, [(NodeId, b)]))
- inlineAll :: forall ctx dom a. Typeable a => ASG ctx dom a -> ASTF dom a
- nodeChildren :: ASG ctx dom a -> [(NodeId, [NodeId])]
- occurrences :: ASG ctx dom a -> Array NodeId Int
- inlineSingle :: forall ctx dom a. Typeable a => ASG ctx dom a -> ASG ctx dom a
- hashNodes :: ExprEq dom => ASG ctx dom a -> (Array NodeId Hash, [(NodeId, Hash)])
- partitionNodes :: forall ctx dom a. ((Lambda ctx) :<: dom, (Variable ctx) :<: dom, ExprEq dom) => ASG ctx dom a -> [[NodeId]]
- cse :: ((Lambda ctx) :<: dom, (Variable ctx) :<: dom, ExprEq dom) => ASG ctx dom a -> ASG ctx dom a
Representation
Node identifier
Placeholder for a syntax tree
prjNode :: (Node ctx) :<: sup => Proxy ctx -> sup a -> Maybe (Node ctx a)Source
Partial Node
projection with explicit context
An ASTF
with hidden result type
reindexNodesAST :: (NodeId -> NodeId) -> AST (Node ctx :+: dom) a -> AST (Node ctx :+: dom) aSource
Update the node identifiers in an AST
using the supplied reindexing
function
reindexNodes :: (NodeId -> NodeId) -> ASG ctx dom a -> ASG ctx dom aSource
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 aSource
Reindex the nodes to be in the range [0 .. l-1]
, where l
is the number
of nodes in the graph
liftSome2 :: (forall a b. ASTF (Node ctx :+: dom) a -> ASTF (Node ctx :+: dom) b -> c) -> SomeAST (Node ctx :+: dom) -> SomeAST (Node ctx :+: dom) -> cSource
Folding
foldGraph :: forall ctx dom a b. (SyntaxPF dom b -> b) -> ASG ctx dom a -> (b, (Array NodeId b, [(NodeId, b)]))Source
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
nodeChildren :: ASG ctx dom a -> [(NodeId, [NodeId])]Source
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 IntSource
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 aSource
Inline all nodes that are not shared
Sharing
hashNodes :: ExprEq dom => ASG ctx dom a -> (Array NodeId Hash, [(NodeId, Hash)])Source
Compute a table (both array and list representation) of hash values for each node