Language.Syntactic.Sharing.Graph

Representation and manipulation of abstract syntax graphs

Representation

newtype NodeId

Node identifier

Constructors

NodeId

Fields

• nodeInteger :: Integer

Instances

Enum NodeId

Defined in Language.Syntactic.Sharing.Graph

Methods

succ :: NodeId -> NodeId

pred :: NodeId -> NodeId

toEnum :: Int -> NodeId

fromEnum :: NodeId -> Int

enumFrom :: NodeId -> [NodeId]

enumFromThen :: NodeId -> NodeId -> [NodeId]

enumFromTo :: NodeId -> NodeId -> [NodeId]

enumFromThenTo :: NodeId -> NodeId -> NodeId -> [NodeId]

Eq NodeId

Defined in Language.Syntactic.Sharing.Graph

Methods

(==) :: NodeId -> NodeId -> Bool

(/=) :: NodeId -> NodeId -> Bool

Integral NodeId

Defined in Language.Syntactic.Sharing.Graph

Methods

quot :: NodeId -> NodeId -> NodeId

rem :: NodeId -> NodeId -> NodeId

div :: NodeId -> NodeId -> NodeId

mod :: NodeId -> NodeId -> NodeId

quotRem :: NodeId -> NodeId -> (NodeId, NodeId)

divMod :: NodeId -> NodeId -> (NodeId, NodeId)

toInteger :: NodeId -> Integer

Num NodeId

Defined in Language.Syntactic.Sharing.Graph

Methods

(+) :: NodeId -> NodeId -> NodeId

(-) :: NodeId -> NodeId -> NodeId

(*) :: NodeId -> NodeId -> NodeId

negate :: NodeId -> NodeId

abs :: NodeId -> NodeId

signum :: NodeId -> NodeId

fromInteger :: Integer -> NodeId

Ord NodeId

Defined in Language.Syntactic.Sharing.Graph

Methods

compare :: NodeId -> NodeId -> Ordering

(<) :: NodeId -> NodeId -> Bool

(<=) :: NodeId -> NodeId -> Bool

(>) :: NodeId -> NodeId -> Bool

(>=) :: NodeId -> NodeId -> Bool

max :: NodeId -> NodeId -> NodeId

min :: NodeId -> NodeId -> NodeId

Real NodeId

Defined in Language.Syntactic.Sharing.Graph

Methods

toRational :: NodeId -> Rational

Show NodeId

Defined in Language.Syntactic.Sharing.Graph

Methods

showsPrec :: Int -> NodeId -> ShowS

show :: NodeId -> String

showList :: [NodeId] -> ShowS

Ix NodeId

Defined in Language.Syntactic.Sharing.Graph

Methods

range :: (NodeId, NodeId) -> [NodeId]

index :: (NodeId, NodeId) -> NodeId -> Int

unsafeIndex :: (NodeId, NodeId) -> NodeId -> Int

inRange :: (NodeId, NodeId) -> NodeId -> Bool

rangeSize :: (NodeId, NodeId) -> Int

unsafeRangeSize :: (NodeId, NodeId) -> Int

p ~ Sat dom => NodeEqEnv dom (EqEnv dom p)

Defined in Language.Syntactic.Sharing.Graph

Methods

prjNodeEqEnv :: EqEnv dom p -> NodeEnv dom (Sat dom)

modNodeEqEnv :: (NodeEnv dom (Sat dom) -> NodeEnv dom (Sat dom)) -> EqEnv dom p -> EqEnv dom p

VarEqEnv (EqEnv dom p)

Defined in Language.Syntactic.Sharing.Graph

Methods

prjVarEqEnv :: EqEnv dom p -> [(VarId, VarId)]

modVarEqEnv :: ([(VarId, VarId)] -> [(VarId, VarId)]) -> EqEnv dom p -> EqEnv dom p

showNode :: NodeId -> String

data Node a where

Placeholder for a syntax tree

Constructors

Node :: NodeId -> Node (Full a)

Instances

StringTree Node

Defined in Language.Syntactic.Sharing.Graph

Methods

stringTreeSym :: [Tree String] -> Node a -> Tree String

Render Node

Defined in Language.Syntactic.Sharing.Graph

Methods

renderSym :: Node sig -> String

renderArgs :: [String] -> Node sig -> String

Constrained Node

Defined in Language.Syntactic.Sharing.Graph

Associated Types

type Sat Node :: * -> Constraint

Methods

exprDict :: Node a -> Dict (Sat Node (DenResult a))

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

Defined in Language.Syntactic.Sharing.Graph

Methods

alphaEqSym :: Node a -> Args (AST dom) a -> Node b -> Args (AST dom) b -> Reader env Bool

type Sat Node

Defined in Language.Syntactic.Sharing.Graph

type Sat Node = Top

class NodeEqEnv dom a where

Environment for alpha-equivalence

Minimal complete definition

prjNodeEqEnv, modNodeEqEnv

Methods

prjNodeEqEnv :: a -> NodeEnv dom (Sat dom)

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

Instances

p ~ Sat dom => NodeEqEnv dom (EqEnv dom p)

Defined in Language.Syntactic.Sharing.Graph

Methods

prjNodeEqEnv :: EqEnv dom p -> NodeEnv dom (Sat dom)

modNodeEqEnv :: (NodeEnv dom (Sat dom) -> NodeEnv dom (Sat dom)) -> EqEnv dom p -> EqEnv dom p

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

type NodeEnv dom p = (Array NodeId Hash, Array NodeId (ASTB dom p))

data ASG 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 (NodeDomain dom) a

  Top-level expression

• graphNodes :: [(NodeId, ASTSAT (NodeDomain dom))]

  Mapping from node id to sub-expression

• numNodes :: NodeId

  Total number of nodes

type NodeDomain dom = (Node :+: dom) :|| Sat dom

showASG :: forall dom a. StringTree dom => ASG dom a -> String

Show syntax graph using ASCII art

drawASG :: StringTree dom => ASG dom a -> IO ()

Print syntax graph using ASCII art

reindexNodesAST :: (NodeId -> NodeId) -> AST (NodeDomain dom) a -> AST (NodeDomain dom) a

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

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

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

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)

Defined in Language.Syntactic.Sharing.Graph

Methods

fmap :: (a -> b) -> SyntaxPF dom a -> SyntaxPF dom b

(<$) :: a -> SyntaxPF dom b -> SyntaxPF dom a

foldGraph :: forall dom a b. (SyntaxPF dom b -> b) -> ASG 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 dom a. ConstrainedBy dom Typeable => ASG dom a -> ASTF dom a

Convert an ASG to an AST by inlining all nodes

nodeChildren :: ASG 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 dom a -> Array NodeId Int

Count the number of occurrences of each node in an expression

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

Inline all nodes that are not shared

Sharing

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

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

partitionNodes :: forall dom a. (Equality dom, AlphaEq dom dom (NodeDomain dom) (EqEnv (NodeDomain dom) (Sat dom))) => ASG 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 :: (Equality dom, AlphaEq dom dom (NodeDomain dom) (EqEnv (NodeDomain dom) (Sat dom))) => ASG dom a -> ASG dom a

Common sub-expression elimination based on alpha-equivalence