%include ../warren/format.lhs

%format use1
%format use2
%format I_ClassDecl_use1


\chapter{AGs on Graphs}
\label{chapt.otherapplications}

This chapter shows how to express attribute grammars on graph structures using
the extensions that we presented in the previous chapters.
Moreover, we show how these extensions form an alternative
to Reference Attributed Grammars (RAGs). Unlike RAGs, these extensions
are compatible with ordered attribute grammars. In fact, these extensions
rely on a static analysis of attribute dependencies.
Finally, this chapter can be seen as a showcase of how the extensions fit
together in a wider context than type inference.

\section{Introduction}

Directed graphs often occur as intermediate representation in compilers.
Graph traversals are inherently more difficult than tree traversals, because
nodes can have multiple predecessors, and graphs can be cyclic.
Yet, the concept of inherited and synthesized attributes
appears attractive to model fixpoint computations
on control flow graphs and dependency graphs, as shown by
Reference Attribute Grammars (RAGs).

In RAGs~\citep{DBLP:journals/scp/MagnussonH07},
references to nodes are first class. A reference to a node provides access to
synthesized attributes of that node. The graph is formed by taking a children of a
node as the node's successors, and the node's optional parent and referenced nodes as
predecessors. There is a subtle different between a parent and a referenced node: inherited
attributes are accessed via the reference to the parent, whereas synthesized attributes
are accessed via references to other nodes.
Attributes that are accessed via a reference are called reference attributes.
In the presence of reference attributes, it is not obvious that all attributes are well-defined.

In a tree, if an inherited attribute of a node |n| depends on an attribute of a subtree, then it also
depends on a synthesized attribute of |n|. Similarly, if a synthesized attribute of a node |n|
depends on an attribute of a parent, then it also depends on an inherited attribute of |n|.
These properties allows us to abstract the dependencies of a subtree
of a production to the dependency graph of the associated nonterminal. These properties thus
allows statical analysis of attribute dependencies, and allow us to compute attributes using
regular treewalks.

In general, the above properties do not hold for graphs. For example, attributes of siblings can
be accessed via a reference without having dependencies on an attribute of a common
ancestor. Moreover, cyclic graphs may cause attributes to be accidentally or
purposefully cyclic, and we may need more control over fixpoint computations in
the latter case.
Consequently, well-definedness of RAGs cannot be determined statically, which complicates
reasoning with attributes.

In this chapter, we show with examples how techniques from Chapter~\tref{chapt.iterative})
provide an alternative to reference attributes in ordered attribute grammars.
Effectively, reference attributes are a means to observe attribute values from other
locations in the tree and produce attribute values that are observable at other locations.
We obtain a similar behavior by shuffling actual children (instead of references) around.
When we detach a child at one location, and attach it at another location,
then we may define and access some of its attributes at that location.
Detached children are first class functional values that can be passed around via
attributes, and may be duplicated.

However, this raises the question what the state a child is (i.e. what attributes of it are computed)
when we detach or attach it.
We showed in Chapter~\rref{chapt.iterative} that when we partition the evaluation of
attributes as a sequence of visits, that each visit to a child represents a state transformation
of that child.
The interface of a nonterminal is a static description of the intermediate states of
the child from the perspective of the parent.
This mechanism allows us to detach and attach children, and still statically guarantee that
their attributes are well-defined.
The catch is that when we attach a child, we are actually required to provide a
value value that represents the child to attach. Typically, we look such a value up in an
environment, which implies that the value must be present in that environment.

The mechanism of shuffling children around still allows us to reason with attributes in
a conventional purely functional way. We demonstrate this mechanism with a control flow
example in Section~\tref{sect.exploit.cfg} and an example based on symbol tables in
Section~\tref{sect.exploit.symbol}.


\section{Analyses on Control Flow Graphs}
\label{sect.exploit.cfg}

We present a relatively simple control flow analysis with AGs. This example is
based on experiences with transformations of bytecode for the AVM2 virtual machine. AVM2
is the runtime of ActionScript version 3 programs.
In bytecode, the body of an ActionScript method is a sequence of AVM2
instructions. The execution of an instruction may have an effect on
the stack. For example, during a call instruction the arguments of the function are popped off the
stack and the result of the method is pushed on the stack.
AVM2 reserves stack space upon entry of the method, and requires a priori knowledge of the maximum
size of the stack after any instruction, given an empty stack upon method entry.
In this section, we show an analysis with AGs that computes this number as an attribute
|maxStack| of a sequence of instructions.

\subsection{Abstract Syntax Tree of Byte Code}

Figure~\ref{fig.exploit.example} shows an example of the AST of a compiled ActionScript method
that represents a repeated invocation of some method |m| that takes an
integer as argument and returns an integer as result.
The following is a simplified representation of such ASTs:
\begin{code}
grammar Method                                  -- nonterminal represents methods bodies
  prod Body           nonterm instrs : Instrs   -- a method is a cons-list of instructions
grammar Instrs                                  -- nonterminal represents instructions
  prod Nil                                                              -- empty sequence
  prod Cons           nonterm hd : Instr  ^^^  nonterm tl : Instrs      -- |hd| followed by |tl|
grammar Instr                                   -- nonterminal represents instructions
  prod Nop                                      -- no-op
  prod Dup                                      -- duplicates top of stack
  prod Push           term  val     :: Int      -- pushes |val| on top of stack
  prod Call           term  method  :: Ident    -- pops args, calls |method|, pushes result
  prod Jump      ^^^  term  index   :: Int      -- execution continues with |index|
  prod JmpZero   ^^^  term  index   :: Int      -- pops top, continues with |index| if zero
\end{code}
By default, AVM2 executes instructions of a method in the order of
appearance. However, after a (conditional) branch instruction, such as |Jump| and |JmpZero|,
the execution continues with the instruction as specified by the branch instruction
(if the condition is met).

\begin{figure}[htb]
\begin{center}
\begin{tikzpicture}
  [
  , nd/.style={circle, minimum size=2mm, node distance=4mm, very thick, draw=black!50, top color=white, bottom color=black!20,font=\scriptsize}
  , lab/.style={xshift=-4mm, font=\footnotesize}
  , lab3/.style={xshift=-4mm, font=\scriptsize}
  , lab2/.style={font=\small}
  , arr/.style={->,thick}
  , conn/.style={-}
  , con2/.style={-,dashed,thin}
  ]

  %% list nodes
  \node[nd](root){};
  \node[nd, below of=root, yshift=-6mm](c1){};
  \node[nd, right of=c1, xshift=12mm, yshift=-2mm](c2){};
  \node[nd, right of=c2, xshift=12mm, yshift=-2mm](c3){};
  \node[nd, right of=c3, xshift=12mm, yshift=-2mm](c4){};
  \node[nd, right of=c4, xshift=12mm, yshift=-2mm](c5){};
  \node[nd, right of=c5, xshift=12mm, yshift=-2mm](c6){};
  \node[nd, right of=c6, xshift=12mm, yshift=-2mm](c7){};
  \node[nd, right of=c7, xshift=6mm, yshift=-2mm](nil){};

  %% instr nodes
  \node[nd, below of=c1, yshift=-6mm](i1){};
  \node[nd, below of=c2, yshift=-6mm](i2){};
  \node[nd, below of=c3, yshift=-6mm](i3){};
  \node[nd, below of=c4, yshift=-6mm](i4){};
  \node[nd, below of=c5, yshift=-6mm](i5){};
  \node[nd, below of=c6, yshift=-6mm](i6){};
  \node[nd, below of=c7, yshift=-6mm](i7){};

  %% graph nodes
  \node[nd, below of=i1, yshift=-18mm](n1){};
  \node[nd, right of=n1, xshift=12mm](n2){};
  \node[nd, right of=n2, xshift=12mm](n3){};
  \node[nd, right of=n3, xshift=12mm](n4){};
  \node[nd, right of=n4, xshift=12mm](n5){};
  \node[nd, right of=n5, xshift=12mm](n6){};
  \node[nd, right of=n6, xshift=12mm](n7){};

  %% edges
  \draw[conn](root) to (c1);
  \draw[conn](c1) to (c2);
  \draw[conn](c2) to (c3);
  \draw[conn](c3) to (c4);
  \draw[conn](c4) to (c5);
  \draw[conn](c5) to (c6);
  \draw[conn](c6) to (c7);
  \draw[conn](c7) to (nil);
  \draw[conn](c1) to (i1);
  \draw[conn](c2) to (i2);
  \draw[conn](c3) to (i3);
  \draw[conn](c4) to (i4);
  \draw[conn](c5) to (i5);
  \draw[conn](c6) to (i6);
  \draw[conn](c7) to (i7);
  \draw[arr](n1) to node[lab2,auto,yshift=-0.5mm]{|1|} (n2);
  \draw[arr](n2) to node[lab2,auto,yshift=-0.5mm]{|2|} (n3);
  \draw[arr](n3) to [in=-142,out=-38] node[lab2,auto,above,yshift=-0.7mm]{|2|} (n6);
  \draw[arr](n4) to node[lab2,auto,yshift=-0.5mm]{|1|} (n5);
  \draw[arr](n5) to node[lab2,auto,yshift=-0.5mm]{|2|} (n6);
  \draw[arr](n6) to node[lab2,auto,yshift=-0.5mm]{|1|} (n7);
  \draw[arr](n6) to [in=-35,out=-145] node[lab2,auto,above,yshift=-0.5mm]{|1|} (n4);
  \draw[con2](i1) to (n1);
  \draw[con2](i2) to (n2);
  \draw[con2](i3) to (n3);
  \draw[con2](i4) to (n4);
  \draw[con2](i5) to (n5);
  \draw[con2](i6) to (n6);
  \draw[con2](i7) to (n7);

  %% labels
  \node[lab3, left of=c1, yshift=-2mm, xshift=11mm]{|1|};
  \node[lab3, left of=c2, yshift=-2mm, xshift=11mm]{|2|};
  \node[lab3, left of=c3, yshift=-2mm, xshift=11mm]{|3|};
  \node[lab3, left of=c4, yshift=-2mm, xshift=11mm]{|4|};
  \node[lab3, left of=c5, yshift=-2mm, xshift=11mm]{|5|};
  \node[lab3, left of=c6, yshift=-2mm, xshift=11mm]{|6|};
  \node[lab3, left of=c7, yshift=-2mm, xshift=11mm]{|7|};
  \node[lab3, left of=n1, yshift=-2mm, xshift=11mm]{|1|};
  \node[lab3, left of=n2, yshift=-2mm, xshift=11mm]{|2|};
  \node[lab3, left of=n3, yshift=-2mm, xshift=11mm]{|3|};
  \node[lab3, left of=n4, yshift=-2mm, xshift=11mm]{|4|};
  \node[lab3, left of=n5, yshift=-2mm, xshift=11mm]{|5|};
  \node[lab3, right of=n6, yshift=-2mm, xshift=-4mm]{|6|};
  \node[lab3, left of=n7, yshift=-2mm, xshift=11mm]{|7|};
  \node[lab, right of=root, yshift=1mm]{|Body|};
  \node[lab, right of=c1, yshift=1mm]{|Cons|};
  \node[lab, right of=c2, yshift=1mm]{|Cons|};
  \node[lab, right of=c3, yshift=1mm]{|Cons|};
  \node[lab, right of=c4, yshift=1mm]{|Cons|};
  \node[lab, right of=c5, yshift=1mm]{|Cons|};
  \node[lab, right of=c6, yshift=1mm]{|Cons|};
  \node[lab, right of=c7, yshift=1mm]{|Cons|};
  \node[lab, right of=nil, yshift=1mm]{|Nil|};
  \node[lab, right of=i1]{|Push 3|};
  \node[lab, right of=i2]{|Push 0|};
  \node[lab, right of=i3]{|Jump 6|};
  \node[lab, right of=i4]{|Call m|};
  \node[lab, right of=i5]{|Dup|};
  \node[lab, right of=i6, xshift=1.5mm]{|JmpZero 4|};
  \node[lab, right of=i7]{|Nop|};
\end{tikzpicture}
\end{center}
\caption{Bytecode AST with CFG.}
\label{fig.exploit.example}
\end{figure}

For such a sequence of instructions, we define our analysis as a synthesized attribute
|maxStack| with the following semantics. In passing, we use an inherited attribute |env|
that specifies the number of arguments and results for each method, and an inherited
attribute |ind| for the sequential numbering of the instructions:
\begin{code}
itf Instrs
  inh env       :: Map Ident (Int,Int)  -- maps method to number of args and results
  inh ind       :: Int                  -- begin index of instruction sequence
  syn maxStack  :: Int                  -- maximum after-stack of instr sequence

sem Method
  prod Body  ^^^  instrs.env = ...      -- obtained from method declarations
                  instrs.ind = 1        -- index of the first instruction

sem Instrs
  prod Nil        lhs.maxStack  = 0
  prod Cons  ^^^  lhs.maxStack  = hd.maxStack `max` tl.maxStack
                  tl.ind        = 1 + lhs.ind  -- index of next instruction
                  hd.env        = lhs.env      -- pass down env
\end{code}
For each instruction |i|, we define the size of the stack |i.after| in terms of
the size of the stack |i.before|:
\begin{code}
itf Instr
  inh env       :: Map Ident (Int,Int)     -- method to number of args and results
  inh before    :: Int                     -- size of stack before this instruction
  syn after     :: Int                     -- size of stack after executing this instr
  syn maxStack  :: Int                     -- max size of stack after this instr

sem Instr
  lhs.after     = lhs.before + loc.effect  -- |loc.effect| different for each instr
  lhs.maxStack  = ...                      -- defined later

  prod Nop Jump   ^^^  loc.effect  = 0     -- exec has no effect on stack size
  prod Dup Push        loc.effect  = +1    -- exec adds one to the stack size
  prod JmpZero         loc.effect  = -1    -- exec pops top of the stack
  prod Call       ^^^  loc.effect  = loc.results - loc.args
                  ^^^  (loc.args,loc.results) = lookup method lhs.env
\end{code}
So far, the analysis appears to be a straightforward attribute grammar. However,
this is not the case when we try to define |hd.before| in
production |Cons|, and |lhs.maxStack| in productions of |Instr|.
The size |i.before| of an instruction |i| is equal to |j.after| for any last
instruction |j| that is executed prior to executing |i|.
Due to branching instructions, there may be several |j.after| sizes
for |i.before| (which all need to be the same), and |i| may be before or after
|j| in the instruction sequence. Such definitions may be cyclic, for example
when |i == j| (e.g. a loop with empty body). It is therefore not obvious
how to define these attributes in terms of the cons-list of instructions.

\subsection{Control Flow Graph}

As solution, we construct a static Control Flow Graph (CFG), and define the remaining
part of the analysis in terms of this graph.
A \emph{control flow graph} is a directed graph where each
instruction uniquely corresponds with a vertex. There is an edge from a vertex |i| to vertex |j|
if the execution may continue with |j| after executing |i|.
Figure~\ref{fig.exploit.example} shows an example of a CFG derived from an
exemplary AST of a method body. Note that there is no edge between
vertex 3 and vertex 4 because of the jump of instruction 3. Also, there is
a \emph{back edge} from vertex 6 to vertex 4 due to the conditional branching of
instruction 6. The analysis labels each edge with the size of the stack after
executing the source vertex of the edge and prior to the execution of the
target vertex of the edge.

The incoming edges of a vertex must be labeled with the same stack size,
similarly for the outgoing edges of a vertex. Instead of labeling the
edges with the stack size, we can thus label the vertices with
the stack size. The analysis then boils down to the following
depth-first traversal.
We start with a stack size of
|0| at vertex |0|. A vertex that is visited via a predecessor with
stack size |s|, has a stack size of |s + loc.effect|,
where |loc.effect| is the effect on the stack of the associated instruction.

There are multiple ways to construct such graphs with attribute grammars.
With RAGs or cyclic AGs, we can construct the graph implicitly. For that,
we introduce an attribute that contains the |after| value for each instruction,
and define a list of predecessors for each instruction, so that we
define the |after| attribute in terms of the |after| values of the predecessors.
However, these AG extensions use a fixpoint computation to
compute the attribute values, which may actually lead to nontermination when the join operation is
naively defined as |max|. The fixpoint computation is also more expensive than
a single depth-first traversal.

As an alternative, we explicitly construct the graph. For that, we introduce attributes
that specify where instructions branch to. An instruction may be followed up
with the next in the sequence, unless attribute |hd.isJump| is |True|. Moreover, an
instruction may be followed up by |hd.branch| if its value is not |Nothing|:
\begin{code}
itf Instr
  syn isJump  :: Bool         -- whether it is the |Jump| instruction
  syn branch  :: Maybe Int    -- non-sequential label to branch to

sem Instr
  lhs.isJump  = False         -- defaults for |isJump| and |branch|
  lhs.branch  = Nothing       -- |Nothing|: no non-sequential branch

  prod Jump            ^^^     lhs.isJump  = True
  prod Jump JmpZero    ^^^     lhs.branch  = Just index  -- branches to instruction |index|
\end{code}
Furthermore, we introduce attributes |vertices| and |edges|. The index of each instruction
is the unique identification of the associated vertex. At the top of the instruction
sequence, we use a graph library to construct a graph from the vertices and edges, and
traverse the graph depth-first to obtain the resulting vertices. Attribute |outcome|
distributes these vertices. We explain below how we actually represent the vertices:
\begin{code}
itf Instrs
  syn vertices   :: Map Int ...     -- vertices of the sequence of instrs
  syn edges      :: [(Int,Int)]     -- edges of the sequence of instrs
  inh outcome    :: Map Int ...     -- contains result vertices of the instrs

sem Instrs
  prod Nil    ^^^  lhs.vertices    = emptyset
                   lhs.edges       = []
  prod Cons   ^^^  lhs.vertices    = insert lhs.index loc.vertex tl.nodes
                   lhs.edges       = [ (lhs.index, s) | s <- loc.succs ] ++ tl.edges
                   loc.succs       = loc.seqts ++ maybeToList hd.branch
                   loc.seqts       = if hd.isJump then [] else [lhs.index+1]

                   loc.vertexOut   = lookup lhs.index lhs.outcome
                   loc.vertexIn    = ...  -- definition of vertex explained below

sem Method prod Body
  instrs.outcome = dfvisit 0 instrs.vertices instrs.edges
\end{code}
As a first approach, we take the |loc.effect| value of |hd| for |loc.vertexIn|,
and replace in |dfvisit| a vertex labelled with effect |e| with |s + e| where |s| is
the stack value of the predecessor of the vertex in the traversal,
or |0| if the vertex does not have a predecessor.
However, this approach has the disadvantage that we manually pack and unpack
context in the graph. For example, we may need to additionally pack
compiler options, and additionally unpack error messages aside from the
stack size.
Also, the logic for each visit belongs with the associated instruction, not
with the top of the instruction sequence.

Therefore, we take a different approach. \emph{The instruction node itself
becomes the vertex in the graph}. The following is the interface for |Instr| again, but
this time with the attributes declared explicitly in three visits:
\begin{code}
itf Instr
  visit analysis
    inh env       :: Map Ident (Int,Int)     -- method to number of args and results
    syn isJump    :: Bool                    -- whether it is the |Jump| instruction
    syn branch    :: Maybe Int               -- non-sequential label to branch to
  visit graph
    inh before    :: Int                     -- size of stack before this instruction
    syn after     :: Int                     -- size of stack after executing this instr
  visit outcome
    syn maxStack  :: Int                     -- max size of stack after this instr
\end{code}
The interface allows us to specify that the |graph| visit is not performed by |hd|, but
performed by some external means. In this example, the |graph| visit is performed by the graph traversal.
We detach |hd| from the |Cons| production as attribute |loc.vertexIn| when it reached the
|graph| state, and attach it again when it is delivered in the |outcome| state as
attribute |loc.vertexOut|:
\begin{code}
sem Instrs prod Cons
  loc.vertexIn  = detach graph of hd             -- detach |hd| in state |graph|
  attach outcome of hd : Instr = loc.vertexOut   -- attach |hd| in state |outcome|
\end{code}
As a minor detail, the |Cons| node does not perform the |graph| visit, therefore it may not access
|hd.after|. However, since the |graph| visit for the instruction node was performed, we may access
these attributes at this node. Thus, we expose this attribute in a later visit as |maxStack|:
\begin{code}
sem Instr  ^^^ lhs.maxStack = asyn.lhs.after     -- |asyn.lhs.after| computed by prev visit
\end{code}
With this mechanism, we thus specify the packing boilerplate (via detach) and unpacking boilerplate (via attach) of the
node as vertex in the graph once. For the definition of the semantics of the node
we conveniently have access to its attributes, and may use the attributes introduced by a visit
that is visited externally in subsequent visits.

\subsection{Discussion}

The depth-first traversal |dfvisit| invokes the |graph| visit (e.g. through the associated
wrapper function) and supplies a value for the |before| attribute. The result of the invocation
is the value of the |after| attribute and the node in the |outcome| state. The former value
forms the input for the visits to the successors of the node, and the latter value is the
transformed value of the vertex. The following definition of |dfvisit| serves as
illustration:
\begin{code}
dfvisit :: alpha -> Map Int (alpha -> (alpha,beta)) -> [(Int,Int)] -> Map Int beta
dfvisit initial vertices edges = visMany initial empty sources where
  sources      = keys vertices `difference` concatMap snd edges
  visMany inp  = foldl (visSingle inp)
  visSingle inp results node
    | member node results  =  results
    | otherwise            =  let  (out,next)  = lookup node vertices inp
                                   succs       = [ t | (s,t) <- edges, s == node ]
                              in visMany out (insert node next results) succs
\end{code}
The attributes of the |graph| visit form the interface with the graph traversal.
Extra attributes
can be defined to tune the traversal. For example, in case of a fixpoint traversal, a synthesized
Boolean attribute may specify that the node's state did not change.
With this mechanism, we thus separated the traversal strategy from the semantics of the node.

When a node is attached again, it is essential that it is an appropriate node.
We do not statically guarantee that this is the case.
A detached node may be duplicated, swapped or lost.
The latter case causes a runtime error when an attempt is made to attach the node, as it is
absent in the |outcome| map. The former two cases may be intended, although we can formulate
a runtime check for them.
Chapter~\tref{chapt.dependent-ags} shows how to statically enforce such invariants.

%if False
\begin{code}
itf Expr
  graph g : Expr :+: Decl
  pred i on g :: Int
  succ s on g :: Bool
\end{code}
Responsibility for defining and obtaining attributes divided between
the the actual parent and predecessors on graphs.
%endif


\section{Subtrees in Symbol Tables}
\label{sect.exploit.symbol}

  Abstraction in programming languages entails that terms of the language can be
  given a name (thus defining or declaring that name), which may then be used at other
  locations in the program by referring to that name.
  Consequently, in an attribute grammar, at a node that uses such a name, we
  refer to properties of the subtree that introduces this name. To access such
  properties, we usually pass these properties around using attributes that
  represent \emph{symbol tables} (maps from name to some value).

  Symbol tables are a technique to explicitly transfer properties of a defining
  node to its use nodes. This technique involves boilerplate code to wrap properties
  of the defining nodes in record-like data structures, and unwrap these properties
  at use nodes. We present a technique to reduce this boilerplate code by transferring
  the tree of the defining node via symbol tables to its use nodes.

  \subsection{Abstract Syntax of an ActionScript Module}

  We present our technique with an example of an analysis that requires information
  from a class declaration to deal with a call to a method of that class.
  Similar to the example of Section~\ref{sect.exploit.cfg}, this example is based
  on our experiences with the transformation of ActionScript bytecode.

  In this setting, a module consist of
  a sequence of declarations, where a declaration is either a class declaration or
  a method body.
  A class declaration specifies the traits of
  an object that is an instance of that class.
  A trait is either a field which stores some
  value, or a method which can be called.
  A method body may be bound to a compatible method-trait of an
  object. A method body consists of a sequence of instructions. Relevant for this
  example is the method call instruction.
  The following is a simplification of the relevant
  abstract syntax:
  \begin{code}
  grammar Module
    prod Module  ^^^  nonterm decls : Decls

  grammar Decl
    prod Class   ^^^  nonterm decl : ClassDecl
    prod Body    ^^^  nonterm decl : MethodBody

  grammar ClassDecl
    prod Class   ^^^  term nm :: Name     ^^^  nonterm traits : Traits

  grammar Traits
    prod Nil
    prod Cons    ^^^  nonterm hd : Trait  ^^^ nonterm tl : Traits

  grammar Trait
    prod Field   ^^^  ...
    prod Method  ^^^  nonterm decl : MethodDecl

  grammar MethodDecl
    prod Method  ^^^  term nm :: Name     ^^^ nonterm params : Params

  grammar Params
    prod Nil
    prod Param   ^^^  term tp :: Type     ^^^ nonterm tl : Params

  grammar Instr
    prod Call    ^^^  term cl :: Name     ^^^ term trait :: Name
  \end{code}
  We omitted some of the intermediate nonterminals (e.g. |Decls| and |MethodBody|)
  that are not relevant for this example.

\begin{figure}[htp]
\begin{center}
\begin{tikzpicture}
  [
  , nd/.style={circle, minimum size=2mm, node distance=4mm, very thick, draw=black!50, top color=white, bottom color=black!20,font=\scriptsize}
  , lab/.style={xshift=-4mm, font=\footnotesize}
  , lab3/.style={xshift=-4mm, font=\scriptsize}
  , lab2/.style={font=\small}
  , arr/.style={->,thick}
  , conn/.style={-}
  , con4/.style={-,thick}
  , con3/.style={-,dashed}
  , con2/.style={-,dashed,thin}
  , marker/.style={font=\tiny}
  ]

  %% Overall tree structure
  \node[nd](root){};

  \node[nd, below of=root, xshift=28mm, yshift=-10mm](decl){};
  \node[nd, below of=decl, xshift=-16mm, yshift=-6mm](c1){};
  \node[nd, right of=c1, xshift=12mm, yshift=-2mm](c2){};
  \node[nd, right of=c2, xshift=12mm, yshift=-2mm](c3){};
  \node[nd, right of=c3, xshift=6mm, yshift=-2mm](nil){};

  \node[nd, below of=root, xshift=-28mm, yshift=-10mm](deref){};
  \node[marker, below of=deref, xshift=12mm, yshift=2mm](t1){};
  \node[marker, below of=t1, xshift=-6mm, yshift=-16mm](t2){};
  \node[marker, below of=t1, xshift=6mm, yshift=-16mm](t3){};
  \node[marker, below of=deref, xshift=-12mm, yshift=2mm](k1){};
  \node[marker, below of=k1, xshift=-4mm, yshift=-6mm](k2){};
  \node[marker, below of=k1, xshift=4mm, yshift=-6mm](k3){};

  \node[nd, below of=c1, yshift=-6mm](i1){};
  \node[nd, below of=c2, yshift=-6mm](i2){};
  \node[nd, below of=c3, yshift=-6mm](i3){};
  \node[nd, below of=i2, xshift=-6mm, yshift=-6mm](p1){};
  \node[nd, right of=p1, xshift=6mm, yshift=-2mm](p2){};
  \node[nd, right of=p2, xshift=6mm, yshift=-2mm](p3){};
  \node[marker,below of=p2,yshift=6mm](bot){};
  \node[marker,below of=t1,yshift=-4mm](xxx){};

  %% Labels
  \node[lab,right of=root]{|Module|};
  \node[lab,right of=decl,xshift=2mm]{|ClassDecl|};
  \node[lab,right of=deref]{|Call|};
  \node[lab,right of=c1,yshift=1mm]{|Cons|};
  \node[lab,right of=c2,yshift=1mm]{|Cons|};
  \node[lab,right of=c3,yshift=1mm]{|Cons|};
  \node[lab,right of=nil]{|Nil|};
  \node[lab,right of=i1]{|Field|};
  \node[lab,right of=i2, xshift=1mm]{|Method|};
  \node[lab,right of=i3]{|Field|};
  \node[lab,right of=p1,yshift=1mm]{|Param|};
  \node[lab,right of=p2,yshift=1mm]{|Param|};
  \node[lab,right of=p3]{|Nil|};

  %% Edges
  \draw[conn](root) to (decl);
  \draw[conn](root) to (deref);
  \draw[conn](deref) to (t1.center);
  \draw[conn](deref) to (k1.center);
  \draw[conn](decl) to (c1);
  \draw[conn](c1) to (c2);
  \draw[conn](c2) to (c3);
  \draw[conn](c3) to (nil);
  \draw[conn](c1) to (i1);
  \draw[conn](c2) to (i2);
  \draw[conn](c3) to (i3);
  \draw[conn](c3) to (nil);
  \draw[conn](i2) to (p1);
  \draw[conn](p1) to (p2);
  \draw[conn](p2) to (p3);

  \draw[con4](t1.center) to (t2.center);
  \draw[con4](t2.center) to (t3.center);
  \draw[con4](t3.center) to (t1.center);
  \draw[con4](k1.center) to (k2.center);
  \draw[con4](k2.center) to (k3.center);
  \draw[con4](k3.center) to (k1.center);

  \draw[con2,->](decl.north) to (t1.center);
  \draw[con2,->](bot.south) to (t3.center);
  \draw[con2,->](i2.north) to (k1.center);
  \draw[con2,->](p3.south) to (k3.center);
  \draw[arr](xxx) to [in=-60,out=-145] (k1);
\end{tikzpicture}
\end{center}
\caption{AST with a method call that needs information from class declarations.}
\label{fig.exploit.symbols}
\end{figure}

  A method call specifies which method of which class to call. When the instruction
  is executed, an object that is an instance of this class must be on top of the
  stack, as well as arguments of the right types.
  For typical compilation tasks for the call instruction
  (e.g. the analysis of Section~\ref{sect.exploit.cfg})
  we need several properties of the relevant class, the relevant trait, and the
  relevant parameters.
  For such properties, the structure in the symbol table
  is typically an abstraction that has a similar structure as the class declaration subtree
  itself.
  Figure~\ref{fig.exploit.symbols} depicts this situation.
  At the call instruction node, we obtain through symbol tables an abstraction of
  the declaration subtree (larger triangle), and extract from that an abstraction
  of the appropriate trait subtree (smaller triangle).

  \subsection{Distribution of Subtrees}

  Instead of creating special data structures to represent the abstractions
  in the symbol table, we
  show how to use the decorated declaration subtree itself as abstraction. For
  that purpose, we partition attributes for the declarations in visits: a |def|
  visit with attributes for the definition node, and visits |use1| and |use2|
  with attributes for the use nodes. These attributes represent typical
  properties of class and method declarations:
  \begin{code}
  itf ClassDecl
    visit def                                  -- more attributes of |def| omitted
      syn nm         :: Name                   -- name of the class
    visit use1
      inh moduleNm   :: Name                   -- context in which the class is used
      syn visible    :: Bool                   -- whether or not the class is visible
    visit use2
      inh methodNm   :: Name                   -- name of method to lookup
      syn method     :: I_MethodDecl_use       -- decl associated with |methodNm|

  itf MethodDecl
    visit def                                  -- more attributes of |def| omitted
      inh index      :: Name                   -- index of trait assigned by parent
      syn nm         :: Name                   -- name of the method
    visit use
      syn slot       :: Int                    -- index of the trait in the object
      syn numParams  :: Int                    -- number of parameters
  \end{code}
  The type |I_ClassDecl_use1| is the type of a detached |ClassDecl| tree in
  the the |use1| state. When we attach a node in this state, we may use the
  |visible| attribute when we provide a value for the |moduleNm| attribute.
  Also, when we provide the name of a method as attribute |methodNm|, we
  obtain the associated detached method as attribute |method|.
  The type |I_MethodDecl_use| is the type of a detached |MethodDecl| that
  can be attached starting with visit |use|.

  We collect detached nodes with the above interfaces in several symbol tables.
  \begin{code}
  itf Traits Trait
    syn  gath  :: Map Name I_MethodDecl_use    -- collects method traits

  itf Decls Decl
    syn  gath  :: Map Name I_ClassDecl_use1    -- collects class declarations

  sem Trait prod Method
    loc.tree  = detach use of decl             -- detach tree in the |use| state
    lhs.gath  = singleton decl.nm loc.tree     -- collected detached tree

  sem Decl prod Class
    loc.tree  = detach use1 of decl            -- detach tree in the |use| state
    lhs.gath  = singleton decl.nm loc.tree     -- collected detached tree

  itf Decls Decl MethodBody Instrs Instr
    inh  dist  :: Map Name I_ClassDecl_use1    -- distribution of symbol table

  sem Module prod Module
    decls.dist = decl.gath                     -- pass down gathered classes

  sem Instr prod Call                          -- attach the trees
    attach use1  of c  : ClassDecl   = lookup cl lhs.dist
    attach use   of m  : MethodDecl  = c.method
  \end{code}
  Aside from the detaching and attaching of the nodes, the collection and
  distribution of the nodes is standard attribute grammar practice.

  We define the properties that are needed at the use node as synthesized
  attributes of the definition node. For the definition of these attributes
  we may use attributes that are in scope of the definition node:
  \begin{code}
  sem ClassDecl prod Class
    lhs.nm          = nm              -- pass name up (visit |def|)
    lhs.visible     = not private || ... lhs.moduleNm ...
    lhs.method      = lookup lhs.methodNm traits.gath

  sem MethodDecl prod Method
    lhs.nm          = nm              -- pass name up (visit |def|)
    lhs.slot        = lhs.index       -- pass the assigned index up (visit |use|)
    lhs.numParams   = params.count    -- pass the number of params up (visit |use|)
  \end{code}
  A particular advantage of this approach is that by adding more synthesized
  attributes, we expose properties of the
  definition node without additional boilerplate code to transfer these
  properties to the use node. At the use node we simply refer to these
  attributes:
  \begin{code}
  sem Instr prod Call
    c.moduleNm  = lhs.moduleNm
    c.methodNm  = trait
    lhs.errors  = if c.visible then [] else [ClassHiddenError]
    lhs.code    = ... t.slot ... t.numParams ...
  \end{code}
  Another advantage is the separation of concerns. At the use node, we
  specify in which module the use node occurs, and at the definition
  node we determine if the class declaration is visible at the
  use node. Similarly,
  at the use node, we just specify the method in which we are
  interested and the definition side provides the relevant
  subtree, and e.g. is responsible for producing error messages.

\subsection{Discussion}

  Accessing information from other locations in the tree is a common
  pattern in compiler implementations, and we typically use symbol
  tables to transfer the information from one location to the other.
  However, when the data stored in the symbol table has a structure
  that mimics the AST itself,
  tedious boilerplate is required to store and retrieve information
  from the symbol table. We showed how to transport subtrees using
  symbol tables, which can then be used to access attributes of
  the remote location.

  RAGs permit access to synthesized attributes to nodes at arbitrary
  locations in the tree through references to these nodes. In
  contrast to RAGs, we permit that use-nodes
  also provide values for inherited attributes, such that the use-node
  is effectively a client and the definition-node a server.
  We can thus provide values for synthesized attributes at the
  definition side, while taking context of the use node into
  account.

  In fact, the interfaces can be seen as a specification of
  queries to a subtree. The caller specifies the query
  as values of the inherited
  attributes, and the subtree responds
  with values for the synthesized attributes.
  We designed this example such that every use node queries
  the definition side in the same way. This is generally
  not the case. For example, for field assignment instructions
  we are interested in the field traits of a class, and not
  the method traits.
  In Section~\tref{depend.sect.depnontermattr} we show how
  to specify alternative interfaces for a nonterminal, which
  can be used to query a nonterminal in different ways.

  A subtree may be duplicated many times. Since we treat
  detached trees as purely functional values, attached
  trees are independent of each other.
  Attributes that do not depend on context of the use node
  can be computed before detaching the tree at the definition
  node and are only evaluated once.
  Attributes that are computed in the visits performed by the use
  node, however, are thus computed once per use node.
  If such an attribute has a non-trivial computation, then
  this is a candidate for memoization, since there
  are typically not many different contexts in a program.

\section{Related Work: Door Attribute Grammars}

  Door Attribute Grammars (DOGs)~\citep{DBLP:conf/cc/Hedin94}
  share commonalities with our approach to reference attributes.
  A DOG introduces a different kind of AST node, called a \emph{door node}.
  Door nodes may not have children, and carry no syntactic content.
  References to door nodes may be passed as attribute values, and
  may be attached as a child.
  These nodes thus serve as interface to attributes of another door node
  at another location in the tree. Inherited attributes at the source
  location become synthesized attributes at reference location.

  An essential difference with our approach is that attributes of
  a DOG are evaluated on demand. In comparison to RAGs, DOGs must
  specify precisely which attributes are exchanged between two
  locations in the tree.

\section{Conclusion}
\label{sect.exploit.conclusion}

We showed how the explicit visits of Chapter~\tref{chapt.iterative} can be
used to shuffle children around. This mechanism forms an alternative to
reference attributes, and can be used to abstract from common patterns in
compiler implementations related to symbol tables and fixpoint computations
over dependency or flow graphs.

These abstractions pay off when implementing mature compilers for larger languages.
For such languages, context information plays an important role. For example,
context information in the form of position
information, error messages, several environments, and runtime options such as
iteration limits.
To have such context available automatically via attributes saves the manual
packing and unpacking of context information into graph representations, which
makes it easier to extend such solving algorithms with more context information.

%% These kind of children-movements require additional documentation?