\documentclass{beamer}

%include lhs2TeX.fmt
%include polycode.fmt

%format gram  = "\mathbf{gram}"
%format prod  = "\mathbf{prod}"
%format attr  = "\mathbf{attr}"
%format inh   = "\mathbf{inh}"
%format syn   = "\mathbf{syn}"
%format sem   = "\mathbf{sem}"
%format visit = "\mathbf{visit}"
%format itf   = "\mathbf{itf}"
%format barrier = "\mathbf{barrier}"
%format child = "\mathbf{child}"
%format invoke = "\mathbf{invoke}"
%format merge = "\mathbf{merge}"
%format term  = "\mathbf{term}"
%format nonterm = "\mathbf{nonterm}"
%format plan = "\mathbf{plan}"
%format yield = "\mathbf{yield}"
%format trap = "\mathbf{trap}"
%format catch = "\mathbf{catch}"
%format commit = "\mathbf{commit}"
%format as = "\mathbf{as}"
%format raised = "\mathbf{raised}"
%format ^^   = "\;"
%format ^^^  = "\hspace{1em}"
%format .    = "."
%format (sub(x)(y))  = "{" x "}_{" y "}"
%format (sup(x)(y))  = "{" x "}^{" y "}"
%format (io(x)(y)(z)) = "{" x "}_{" y "}^{" z "}"
%format emptyset  = "\emptyset{}"
%format activate  = "\mathbf{activate}"
%format raise     = "\mathbf{raise}"
%format (many(x)) = "\overline{" x "}"
%format return    = "\mathbf{return}"
%format child     = "\mathbf{child}"

\usepackage{color}
\usepackage{xcolor}
\usetheme{uucs}
\usepackage{tikz}

\usetikzlibrary{trees,arrows,decorations,shapes,fit,backgrounds}

\author{Arie Middelkoop}
\title{Stepwise Attribute Grammar Evaluation\\Or: \emph{Tweaking} AG Evaluation}

\institute{%
  Dept.\ of Information and Computing Sciences, Utrecht University\\%
  P.O.\ Box 80.089, 3508 TB Utrecht, The Netherlands\\%
  Web page: \url{http://www.cs.uu.nl/wiki/Center}}
\date{LDTA, 27 March '11}

\begin{document}

\frontmatter

\begin{frame}
  \titlepage
\end{frame}

\mainmatter

\begin{frame}
  \frametitle{Introduction}
  
  Contents of talk:
  \begin{itemize}
  \item Computations over tree structures with attribute grammars
  \item \emph{Crazy Idea}: Control evaluation!
  \item Different setting: construct tree while evaluating attributes
  \item Deal with: BFS, side-effect, graphs, parallelism
  \end{itemize}
  
  \begin{itemize}
  \item Type inference: proof search
  \item Breadth-first mini-max
  \end{itemize}
  
  \begin{itemize}
  \item Implementation in UUAG (using Haskell)
  \item Proof of concept Java example
  \item Extended version: \url{www.cs.uu.nl/~ariem/thesis.pdf}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Relation to Yesterday's Talks}
  
  \begin{itemize}
  \item Control stategies to direct evaluation of children;
        in an AG, such strategies are implicit
  \item Relation to Rinus' workflows.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{What is an Attribute Grammar? (notation)}
  
  \begin{code}
  gram Pred  -- grammar
    prod Var  term nm :: String
    prod Or And
      nonterm p : Pred
      nonterm q : Pred
  
  attr Pred  -- attributes
    inh env :: Map String Bool
    syn val :: Bool
  
  sem Pred   -- rules
    prod Var   ^^^  lhs.val = find nm lhs.env
    prod Or         lhs.val  = p.val || q.val
    prod And        lhs.val  = p.val && q.val
    prod Or And
      p.env  = lhs.env
      q.env  = lhs.env
  \end{code}
\end{frame}

\begin{frame}
  \frametitle{Visualization}
  
  \begin{center}
  \begin{tikzpicture}
    [ nd/.style={circle, minimum size=12mm, thick, draw=blue!50!black!50, top color=white, bottom color=blue!50!black!20,font=\footnotesize}
    , attr/.style={rectangle, minimum size=4mm, node distance=6mm, thick, draw=black!50, top color=white, bottom color=black!20,font=\footnotesize}
    , arr/.style={->,dashed, very thick}
    , lab/.style={font=\footnotesize}
    ]
    \node[nd](n1){|Or|}
      [sibling distance=30mm, level distance=18mm]
      child {
        node[nd](n2){|And|}
          child {
            node[nd](n3){|Var x|}
          }
          child {
            node[nd](n4){|Var y|}
          }
      }
      child {
        node[nd](n5){|Var z|}
      };
    
    \pause
    
    \node[attr,left of=n1] (n1i) {};
    \node[attr,right of=n1] (n1s) {};
    \node[attr,left of=n2] (n2i) {};
    \node[attr,right of=n2] (n2s) {};
    \node[attr,left of=n3] (n3i) {};
    \node[attr,right of=n3] (n3s) {};
    \node[attr,left of=n4] (n4i) {};
    \node[attr,right of=n4] (n4s) {};
    \node[attr,left of=n5] (n5i) {};
    \node[attr,right of=n5] (n5s) {};
    
    \pause
    
    \draw[arr] (n1i) to (n2i);
    \draw[arr] (n1i) to (n5i);
    \draw[arr] (n2i) to (n3i);
    \draw[arr] (n2i) to (n4i);
    \draw[arr] (n2s) to (n1s);
    \draw[arr] (n5s) to (n1s);
    \draw[arr] (n3s) to (n2s);
    \draw[arr] (n4s) to (n2s);
    
    \node[lab,left of=n1i,xshift=-5mm]{|x:T,y:F,z:T|};
    \node[lab,left of=n2i,xshift=-5mm]{|x:T,y:F,z:T|};
    \node[lab,left of=n3i,xshift=-5mm]{|x:T,y:F,z:T|};
    
    \node[lab,right of=n3s,xshift=-5mm]{|T|};
    \node[lab,right of=n5s,xshift=-5mm]{|T|};
    \node[lab,right of=n1s,xshift=-5mm]{|T|};
    \node[lab,right of=n4s,xshift=-5mm]{|F|};
    \node[lab,right of=n2s,xshift=-5mm]{|F|};
  \end{tikzpicture}
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{What is an Attribute Grammar? (model)}
  
  \begin{itemize}
    \item Rules: (Pure) functions between attributes
    \item Declarative! \pause Evaluation algorithm?
  \end{itemize}

  Freedom: several algorithms with different properties.
  \pause
  
  \begin{itemize}
    \item On-demand evaluation
    \begin{itemize}
      \item Evaluator performs the least evaluation for an attribute
      \item As supported by UUAG, JastAdd, Silver, ...
    \end{itemize}
    \pause
    \item But also: \emph{eager evaluation}
      \begin{itemize}
      \item Evaluator dictates evaluation order
      \item Kennedy-Warren '76
      \item Kastens '80
      \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{While Working on my Ph.D...}
  
  Type inference seems a typical task for AGs.
  Nice example: UHC.
  
  However, what about:
  \begin{itemize}
  \item Proof structure deviates from AST structure
  \item Multiple candidate solutions
  \item Sharing in proofs - graphs?
  \item Information about type variables discovered during evaluation.
        How to distribute this information?
        Is a single pass sufficient?
  \end{itemize}
  %% \pause
  %% Existing solutions: party with AGs, partly with dedicated technology
  \pause
  Are these issues only related to type inference?
\end{frame}

\begin{frame}
  \frametitle{My Everyday Problems...}
  
  \begin{itemize}
  \item Layout algorithms for hierarchical HTML menus
    \uncover<2->{
    \begin{itemize}
    \item Side Effect!
    \end{itemize}}
  \item Compute back edges of control flow graph
    \uncover<2->{
    \begin{itemize}
    \item Graph node has multiple parents
    \item However, depth-first traversal can be represented as a tree
    \end{itemize}}
  \item In an AG for aspect-oriented programming,
        independent computations for each joint point.
    \uncover<2->{
    \begin{itemize}
    \item Parallelism!
    \end{itemize}}
  \item Operational semantics for a language with a nondeterministic choice
    \uncover<2->{
    \begin{itemize}
    \item Breadth-first evaluation!
    \end{itemize}}
  \end{itemize}
  
  Remarkable similarities
\end{frame}

\begin{frame}
  \frametitle{Reflection}
  
  \begin{itemize}
  \item A nice and essential aspect of AGs is that the evaluation order of
        rules is implicit.
  \item Consequently, there are algorithms that we would like to express as AGs, but cannot do so straightforwardly.
  \pause
  \item Can we control the evaluation order while keeping the advantages of AGs?
        (unordered rules, compositionality)
  \end{itemize}
\end{frame}

\section*{Visits to Children Explicit}

\begin{frame}
  \frametitle{Mix AGs with Visitors}
  
  \begin{itemize}
  \item Be able to describe visits to children
  \item Be able to restrict their relative order
  \item GPCE'10 paper
    \begin{code}
      attr Pred visit eval
          inh env :: Map String Bool
          syn val :: Bool
      
      sem Pred | Or visit eval
          invoke eval of q
          invoke eval of p
    \end{code}
  \pause
  \item Define \emph{external functions} (possibly with side effect) as virtual children
  \end{itemize}
\end{frame}

\section*{Evaluation Algorithms Revisited}

\begin{frame}
  \frametitle{Typical Evaluation}
  
  \begin{center}
  \begin{tikzpicture}
    [ nd/.style={circle, minimum size=12mm, thick, draw=blue!50!black!50, top color=white, bottom color=blue!50!black!20,font=\footnotesize}
    , attr/.style={rectangle, minimum size=4mm, node distance=6mm, thick, draw=black!50, top color=white, bottom color=black!20,font=\footnotesize}
    , arr/.style={->,dashed, very thick}
    , lab/.style={font=\footnotesize}
    ]
    \node[nd](n1){|Or|}
      [sibling distance=30mm, level distance=18mm]
      child {
        node[nd](n2){|And|}
          child {
            node[nd](n3){|Var x|}
          }
          child {
            node[nd](n4){|Var y|}
          }
      }
      child {
        node[nd](n5){|Var z|}
      };
    
    \node[attr,left of=n1] (n1i) {};
    \node[attr,right of=n1] (n1s) {};
    \node[attr,left of=n2] (n2i) {};
    \node[attr,right of=n2] (n2s) {};
    \node[attr,left of=n3] (n3i) {};
    \node[attr,right of=n3] (n3s) {};
    \node[attr,left of=n4] (n4i) {};
    \node[attr,right of=n4] (n4s) {};
    \node[attr,left of=n5] (n5i) {};
    \node[attr,right of=n5] (n5s) {};
  \end{tikzpicture}
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Kastens Style Evaluation}
  
  \begin{code}
  plan Or   ^^^  p.env = lhs.env
                 q.env = lhs.env
                 invoke p
                 invoke q
                 lhs.val = p.val || q.val
                 yield Done
  
  plan And  ^^^  p.env = lhs.env
                 invoke p
                 q.env = lhs.env
                 invoke q
                 lhs.val = p.val && q.val
                 yield Done

  plan Var  ^^^  lhs.val = find nm lhs.env
                 yield Done
  \end{code}
\end{frame}

\section*{Stepwise Evaluation}

\begin{frame}
  \frametitle{Example Instrumented with Events}
  
  %% Want to control evaluation of p and q, so introduce a controller node (black)
  %% It masquerates itself as one or more conventional children
  %% except that it does not take inherited attrs, but has access to the values of its parent.
  
  %% Smarter style of evaluation:
  %% if children would give us some information what they are doing
  
  \begin{center}
  \begin{tikzpicture}
    [ nd/.style={circle, minimum size=12mm, thick, draw=blue!50!black!50, top color=white, bottom color=blue!50!black!20,font=\footnotesize}
    , merge/.style={rectangle, minimum size=6mm, thick, draw=black,top color=black, bottom color=black,font=\footnotesize}
    , attr/.style={rectangle, minimum size=4mm, node distance=6mm, thick, draw=black!50, top color=white, bottom color=black!20,font=\footnotesize}
    , arr/.style={->,dashed, very thick}
    , lab/.style={font=\footnotesize}
    ]
    \node[merge,font=\footnotesize]{}
    child {
    node[nd,yshift=2mm](n1){|Or|}
     child {
     node[merge,yshift=5mm](n6){}
      [sibling distance=30mm, level distance=18mm]
      child {
        node[nd](n2){|And|}
          child {
            node[nd](n3){|Var x|}
          }
          child {
            node[nd](n4){|Var y|}
          }
      }
      child {
        node[nd](n5){|Var z|}
      }}};
    \node[lab,above of=n2,yshift=-2mm]{|p|};
    \node[lab,above of=n5,yshift=-2mm]{|q|};
    
    \node[attr,left of=n1] (n1i) {};
    \node[attr,right of=n1] (n1s) {};
    \node[attr,left of=n2] (n2i) {};
    \node[attr,right of=n2] (n2s) {};
    \node[attr,left of=n3] (n3i) {};
    \node[attr,right of=n3] (n3s) {};
    \node[attr,left of=n4] (n4i) {};
    \node[attr,right of=n4] (n4s) {};
    \node[attr,left of=n5] (n5i) {};
    \node[attr,right of=n5] (n5s) {};
    \node[attr,right of=n6] (n6s) {};
    
    \pause
    
    \node[lab,below of=n2,yshift=2mm] {|Work|};
    \pause
    \node[lab,below of=n5,yshift=2mm] {|Work|};
    \pause
    \node[lab,below of=n6,yshift=2mm] {|Work|};
    \pause
    \node[lab,below of=n3,yshift=2mm] {|Work|};
    \pause
    \node[lab,below of=n4,yshift=2mm] {|Work|};
  \end{tikzpicture}
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Modified Evaluation Algorithm}
  
  \begin{itemize}
  \item Eager algorithm - Kastens
  \item Coroutines
  \end{itemize}
  
  Modifications:
  \begin{itemize}
  \item Do not simply \emph{yield} attribute values, but an \emph{execution trace}
  \item Execution trace is composed from the traces of the children
  \item Man-in-the-middle mergers consume traces of children, and present themselves
        as replacement for these children with a transformed trace.
  \item At the root: repeatedly evaluate up to the next event
  \item Simplification: assume single-visit for each child
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Execution trace and Inversion of Control}
  
  An execution trace of a child of (a single-visit) nonterminal |N|
  is a sequence of events:
  
  \begin{code}
  (sub(E)(1)), ..., (sub(E)(n)), (sub(Done)(N))
  \end{code}
  
  An event |(sub(E)(i)) = io(X)(I)(O)| is user-defined and has:
  \begin{itemize}
  \item A name |X|
  \item Values |O| provided by the child that yields the event, usable to the parent
  \item Values |I| usable by the continuation of the child, provided by the parent
  \end{itemize}

  The terminator |sub(Done)(N)| carries |N|'s synthesized attributes.
\end{frame}

%if False
\begin{frame}
  \frametitle{Visualisation}
  
  \begin{center}
  \begin{tikzpicture}
    [ nd/.style={circle, minimum size=12mm, thick, draw=blue!50!black!50, top color=white, bottom color=blue!50!black!20,font=\footnotesize}
    , merge/.style={rectangle, minimum size=6mm, thick, draw=black,top color=black, bottom color=black,font=\footnotesize}
    , attr/.style={rectangle, minimum size=4mm, node distance=6mm, thick, draw=black!50, top color=white, bottom color=black!20,font=\footnotesize}
    , arr/.style={->,dashed, very thick}
    , lab/.style={font=\footnotesize}
    ]
    \node[nd](n1){|Or|}
     [sibling distance=30mm, level distance=18mm]
      child {
        node[nd](n2){|And|}
          child {
            node[nd](n3){|Var x|}
          }
          child {
            node[nd](n4){|Var y|}
          }
      }
      child {
        node[nd](n5){|Var z|}
      };

    \node[attr,left of=n1] (n1i) {};
    \node[attr,right of=n1] (n1s) {};
    \node[attr,left of=n2] (n2i) {};
    \node[attr,right of=n2] (n2s) {};
    \node[attr,left of=n3] (n3i) {};
    \node[attr,right of=n3] (n3s) {};
    \node[attr,left of=n4] (n4i) {};
    \node[attr,right of=n4] (n4s) {};
    \node[attr,left of=n5] (n5i) {};
    \node[attr,right of=n5] (n5s) {};
    \end{tikzpicture}
  \end{center}
\end{frame}
%endif

\begin{frame}
  \frametitle{With Merging}

\begin{center}
\begin{tikzpicture}
  [ nd/.style={circle, minimum size=12mm, thick, draw=blue!50!black!50, top color=white, bottom color=blue!50!black!20,font=\footnotesize}
  , merge/.style={rectangle, minimum size=6mm, thick, draw=black,top color=black, bottom color=black,font=\footnotesize}
  , attr/.style={rectangle, minimum size=4mm, node distance=6mm, thick, draw=black!50, top color=white, bottom color=black!20,font=\footnotesize}
  , arr/.style={->,dashed, very thick}
  , lab/.style={font=\footnotesize}
  ]
  \node[nd](n1){|Or|}
   child {
   node[merge,yshift=5mm](n6){}
    [sibling distance=30mm, level distance=18mm]
    child {
      node[nd](n2){|And|}
        child {
          node[nd](n3){|Var x|}
        }
        child {
          node[nd](n4){|Var y|}
        }
    }
    child {
      node[nd](n5){|Var z|}
    }};
  \node[lab,above of=n2,yshift=-2mm]{|p|};
  \node[lab,above of=n5,yshift=-2mm]{|q|};
  
  \node[attr,left of=n1] (n1i) {};
  \node[attr,right of=n1] (n1s) {};
  \node[attr,left of=n2] (n2i) {};
  \node[attr,right of=n2] (n2s) {};
  \node[attr,left of=n3] (n3i) {};
  \node[attr,right of=n3] (n3s) {};
  \node[attr,left of=n4] (n4i) {};
  \node[attr,right of=n4] (n4s) {};
  \node[attr,left of=n5] (n5i) {};
  \node[attr,right of=n5] (n5s) {};
  \node[attr,right of=n6] (n6s) {};
  
  \node[lab,below of=n3,yshift=2mm] (n3l) {|Work|};
  \node[lab,below of=n5,yshift=2mm] (n5l) {|Work|};
  \node[lab,below of=n4,yshift=2mm] (n4l) {|Work|};
  
  \pause
  
  \node[lab,below of=n3l,yshift=5mm,font=\normalsize] {\color{uuxred}?};
  \node[lab,below of=n4l,yshift=5mm,font=\normalsize] {\color{uuxred}?};
  \node[lab,below of=n5l,yshift=5mm,font=\normalsize] {\color{uuxred}?};
  
  \pause
  
  \node[lab,left of=n6,xshift=4mm,font=\normalsize] {\color{uuxred}?};
\end{tikzpicture}
\end{center}
\end{frame}

\begin{frame}
  \frametitle{Yielding Events}
  
  \begin{code}
  gram Yield | Yield
  attr Yield inh emptyset syn emptyset
  
  sem Pred | Var
    lhs.val  = find nm lhs.env
    invoke z
    
    merge as z : Yield = do
      raise (sup(Work)(emptyset))
      commit z $ wrap $ Syn_Yield {}
  \end{code}
\end{frame}

\begin{frame}
  \frametitle{Controlling Events}
  
  \begin{code}
  sem Pred | Or
    p.env    = lhs.env
    q.env    = lhs.env
    lhs.val  = z.val

    merge p,q as z : Pred = catch
      p raised Done | p.val  -> commit z p
      q raised Done | q.val  -> commit z q
      p raised (sub(Work)(emptyset)) ^^^ q raised (sub(Work)(emptyset)) -> do
        r <- raise (sup(Work)(emptyset))
        return (r, r)
  \end{code}
\end{frame}

%format c1
%format k1
%format N1
\begin{frame}
  \frametitle{Static Semantics of Merge}

  \begin{code}
  merge c1, ..., (sub c n) as k1 : N1, ..., (sub k m) : (sub N m)  = e
  \end{code}

  \begin{itemize}
  \item |n>=0, m >= 1|
  \item |c1, ..., (sub c n)|: must be provided values for inhs, but may not refer to their syns
  \item |k1, ..., (sub k m)|: may refer to their syns, but not their inhs
  \item Monadic expression |e| that must ultimately commit semantics for each of the created children
  \end{itemize}
\end{frame}

\section*{Other Possibilities}

\begin{frame}
  \frametitle{Other Possibilities}
  
  Allow IO in monadic merge functions...
  \begin{itemize}
  \item Merge based on side-effect: encode graph traversal. Choose child depending on
        whether we visited the intended target already before.
  \item Run left and right child up till a couple of steps in parallel
  \item Create a nonterminal ApplySubst which takes a type variable as inherited attribute and its
        currently known expansion as synthesized attribute.
  \item Fixed-point computations: repeat evaluation of child, but with each iteration tweaked
        inherited attributes
  \end{itemize}
  Etc...
\end{frame}

\begin{frame}
  \frametitle{Conclusion}
  
  \begin{itemize}
  \item The rules remained purely functional, and can still be automatically composed
  \item We pay a price:
    \begin{itemize}
    \item Evaluation of children explicit
    \item Explicit allocation of attributes to visits (to a certain degree)
    \end{itemize}
  \item We gain: control over evaluation, traversals of more complex structures
  \item Overkill?
  \end{itemize}
  More information: \url{www.cs.uu.nl/~ariem/thesis.pdf}
\end{frame}

\end{document}