\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 child     = "\mathbf{child}"
%format invoke = "\mathbf{invoke}"
%format term  = "\mathbf{term}"
%format nonterm = "\mathbf{nonterm}"
%format yield = "\mathbf{yield}"
%format down = "\mathbf{down}"
%format up = "\mathbf{up}"
%format decorate = "\mathbf{decorate}"
%format parallel = "\mathbf{parallel}"
%format ^^   = "\;"
%format ^^^  = "\hspace{1em}"
%format .    = "."
%format <<   = "\prec"
%format (sub(x)(y))  = "{" x "}_{" y "}"
%format (sup(x)(y))  = "{" x "}^{" y "}"
%format (io(x)(y)(z)) = "{" x "}_{" y "}^{" z "}"
%format emptyset  = "\emptyset{}"
%format (many(x)) = "\overline{" x "}"
%format f1
%format f2
%format f3
%format f4
%format (att a b c) = a "." c "_{" b "}"
%format `subset` = "\subseteq"

%format yellow = "{\color{atyellow}\Varid{yellow}}"
%format orange = "{\color{atorange}\Varid{orange}}"
%format purple = "{\color{atpurple}\Varid{purple}}"
%format blue   = "{\color{atblue}\Varid{blue}}"

\usepackage{color}
\usepackage{xcolor}
%% \usetheme{uucs}
\usepackage{tikz}
\usepackage{hyperref}
\usepackage{wasysym}  %% for the music symbols
\usepackage{soul}     %% for the strike through

\definecolor{atyellow}{RGB}{120,170,70}
\definecolor{atorange}{RGB}{240,150,0}
\definecolor{atpurple}{RGB}{53,53,173}
\definecolor{atblue}{RGB}{21,84,225}

\definecolor{uuxred}{RGB}{240,20,20}
\newcommand\frontmatter{}
\newcommand\mainmatter{}

\usetikzlibrary{trees,arrows,decorations,shapes,shapes.callouts,decorations.text}

\author[A. Middelkoop]{Arie Middelkoop}
\title[Controlling AG Evaluation]{Attribute-directed Hints for Controlling Ordered Attribute Grammar Evaluation}
\subtitle{Let's go parallel!\\(Ongoing work on UUAGC, Universiteit Utrecht)}
\date[06.01.12]{6. Januar 2012}
\subject{Ordered Attribute Grammar Evaluation}
\keywords{attribute grammars, evaluation, static analysis, parallel}

\institute{%
  amiddelk@@gmail.com\\
  Laboratoire d'Informatique de Paris 6\\
  Universit\'{e} Pierre et Marie Curie, Paris
  }
\date{FP dag '12 at the last day of Christmas \\ {\color{darkgray}\twonotes~\emph{On the twelfth day of Christmas, my true love sent to me:\\12 Attributes, 11 Rules, ..., 3 Productions, 2 Nonterminals,\\and an Abstract Syntax Tree!}~\twonotes}}

\beamertemplatenavigationsymbolsempty
\setbeamertemplate{footline}[frame number]

\begin{document}

\frontmatter

\begin{frame}[plain]
  \titlepage
\end{frame}

\mainmatter

\begin{frame}

\begin{block}{Christmas wish}
\begin{description}
\item[If] you write your compiler in a declarative language
\item[Then] you can get a parallelized compiler for free
\end{description}
\end{block}

\begin{block}{Santa's answer}
\begin{description}
\item[Problem]  General parallelization schemes are inefficient
\item[Solution] Exploit domain-specific knowledge
\end{description}
\end{block}

\begin{block}{This talk}
\begin{itemize}
\item Simple parallelization of attribute grammars
\item Programmer specifies where parallelism is appropriate
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\begin{block}{Why \emph{declarative} matters}
\begin{description}
\item[Conciseness] Higher-level of understanding
\item[Automation]  Programs too large for manual labour
\item[Correctness] Analyses for checking the description
\item[Performance] Code generator searches for fast code
\item[Hints]       Apply domain knowledge
\end{description}
\end{block}
\end{frame}

\section[Attribute grammars]{Attribute grammars}

\begin{frame}[plain]
\begin{center}\Large
Attribute grammars
\end{center}
\end{frame}

\begin{frame}
\frametitle{Attribute Grammars (Knuth, 1968)}
\begin{block}{What is an Attribute Grammar?}
An AG describes the decoration of a christmas tree.
\end{block}
\pause
\begin{block}{... also used for}
\begin{description}
\item[General] Computations over trees
  \begin{itemize}
  \item Declarative
  \item Compositional
  \item Generic abstractions
  \end{itemize}
\item[Theory] To specify semantics of context-free languages
\item[Practice] To implement compilers
\end{description}
\end{block}
\end{frame}

\begin{frame}
\frametitle{The Pine Tree}

\begin{columns}
\column{.6\textwidth}
\begin{code}
nonterm Tree
  prod Star
    nonterm  root    : Odd

nonterm Odd
  prod Segment
    nonterm  end     : Even

nonterm Even
  prod Fork
    nonterm  left    : Odd
    nonterm  right   : Odd
  prod Tip
\end{code}
\column{.4\textwidth}
%include dia/pine.lhs
\end{columns}
\end{frame}

\begin{frame}
\frametitle{The Christmas Tree}

\begin{columns}
\column{.6\textwidth}
\begin{code}
attr Odd
  inh  purple  :: Ball
  syn  blue    :: Ball

attr Even
  inh  orange  :: Ball
  syn  yellow  :: Ball
\end{code}
\onslide<2->{
\begin{code}
sem Even  prod Tip
  lhs.yellow    =  f1  lhs.orange

sem Even  prod Fork
  left.purple   =  f2  lhs.orange
  right.purple  =  f3  lhs.orange
  lhs.yellow    =  f4  left.blue
                       right.blue
\end{code}}
\column{.4\textwidth}
%include dia/tree.lhs
\end{columns}
\end{frame}

\begin{frame}
\frametitle{Executing the AG}

\begin{description}
\item[Declarative] Algorithmic freedom
  \begin{itemize}
    \item Tree walking automaton (Aho, 1969)
  \end{itemize}
\item[Algorithm]   Reasoning about parallelism
  \begin{itemize}
    \item Parallel visits
  \end{itemize}
\item<2->[Interaction]
  Break abstraction to exploit domain knowledge
  \begin{itemize}
  \item Programmer adds attributes/rules that specify where
        parallelism is appropriate
  \item Passed as hint to the automaton
  \end{itemize}
\end{description}

\begin{center}
\begin{tikzpicture}
\node[rectangle,draw,thick,fill=blue!20](a){AG};
\node[rectangle,draw,thick,fill=blue!20,below of=a](b){Automaton};
\node[rectangle,draw,thick,fill=blue!20,below of=b](c){Code};

\node[right of=a, anchor=west]{Declarative (presented so far)};
\node[right of=b, anchor=west]{Algorithm (coming up now)};
%% \node[right of=c, anchor=west]{(not so relevant)};

\draw[->] (a) to (b);
\draw[->] (b) to (c);
\end{tikzpicture}
\end{center}
\end{frame}

\section[Tree walkers]{Tree walkers}

\begin{frame}[plain]
\begin{center}\Large
Tree walkers
\end{center}
\end{frame}

\begin{frame}
\frametitle{Tree Walking \st{Automaton} Elf}

\begin{columns}
\column{0.4\textwidth}
\includegraphics[width=4cm]{pics/Elf.png}
\column{0.6\textwidth}
\begin{block}{Automaton visits nodes}
Produces decorations with each visit
\end{block}
\begin{block}{Protocol between parent and child}
\begin{itemize}
\item Which visits per nonterminal
\item Which attributes per visit
\end{itemize}
\end{block}
\begin{block}{Commands\tikz[remember picture] \node (a) {\vphantom{X}};}
\begin{itemize}
\item |decorate  pat = expr|
\item |down childname, protocol|
\item |up|
\end{itemize}
\end{block}
\begin{block}{Static plan\tikz[remember picture] \node (c) {\vphantom{X}};}
Commands $\times$ production $\times$ protocol
\end{block}
\end{columns}
\pause
\begin{tikzpicture}[remember picture,overlay]
\node[anchor=west,above of=c,xshift=1cm,ellipse callout,fill=uuxred!50,opacity=.9,callout absolute pointer={(c.mid)}]{For any tree generated by the grammar};
\end{tikzpicture}
\pause
\begin{tikzpicture}[remember picture,overlay]
\node[anchor=west,above of=a,xshift=1cm,ellipse callout,fill=uuxred!50,opacity=.9,callout absolute pointer={(a.mid)}]{similar to zippers (Huet, 1997)};
\end{tikzpicture}
\end{frame}

\begin{frame}
\begin{itemize}
\item Production |Fork| (nonterm |Even|, children |left| and |right|)
  \begin{center}
  %include dia/fork.lhs
  \end{center}
\item One-visit protocol: inh |orange|, computing syn |yellow|
\end{itemize}
\begin{code}

decorate  ^^^  left.purple   =  f2  lhs.orange
decorate       right.purple  =  f3  lhs.orange
down           left,   ^^^ [ inh purple, syn blue ]
down           right,  ^^^ [ inh purple, syn blue ]
decorate       lhs.yellow    =  f4  left.blue right.blue
up
\end{code}
\end{frame}

\begin{frame}
\begin{block}{Absolutely noncircular AGs}
\begin{description}
\item[Practice] Property of many `compiler' AGs
\item[How] Cycle analysis (Knuth, 1968)
\item[Advantages]
  \begin{itemize}
  \item Define-before-use consistency check
  \item Finite traversal for finite trees
  \end{itemize}
\end{description}
\end{block}
\begin{center}
%include dia/pdg.lhs
\end{center}
\end{frame}

\begin{frame}
\begin{block}{Absolutely noncircular AGs have statically determined protocols and plans}
\begin{description}
\item[How] Abstract interpretation (Kennedy, 1976)
%% \item[Disadvantage] Possibly many plans for a production
\item[Where] Implementation in UUAGC (Bransen, 2012)
  \begin{itemize}
  \item Prioritizes independent visits
  \item On-demand strategy
  \item Robust to program changes
  \end{itemize}
\item[Advantages]
  \begin{itemize}
  \item Strict evaluation
  \item Play with evaluation order
  \end{itemize}
\end{description}
\end{block}
\end{frame}

\begin{frame}
\begin{block}{Translation from static plans to Haskell}
\begin{description}
\item[How] Translation (my thesis, chapter 4)
\item[Where] Implemented in UUAGC
\end{description}
\begin{description}
  \item[Visits]    Coroutines (Conway 1963, Warren 1976)
  \item[Protocols] Type indices (Cheney 2003)
  \end{description}
\end{block}
\renewcommand{\hscodestyle}{\small}
\begin{code}
sem_Even_Fork :: T_Odd  -> T_Odd  -> T_Even
sem_Even_Fork left right = \ (att lhs I orange) -> do

  (att left I purple)   <- return $ f2 (att lhs I orange)
  (att right I purple)  <- return $ f3 (att lhs I orange)

  (att left S blue)     <- left (att left I purple)
  (att right S blue)    <- right (att right I purple)

  (att lhs S yellow)    <- return $ f4 (att left S blue) (att right S blue)
  return $ (att lhs S yellow)
\end{code}
\renewcommand{\hscodestyle}{}
\end{frame}

\begin{frame}
\begin{block}{Independent visits to children}
\texths
\begin{code}
down (sup([childname, protocol])(+))
\end{code}
\plainhs
\begin{itemize}
\item Needed inh attrs independent of to be computed syn attrs.
\item 1+ new syn attrs in each protocol
\end{itemize}
\end{block}
\begin{block}{Parallelizable\tikz[remember picture] \node (d) {};\tikz[remember picture] \node (b) {};}
\begin{description}
\item[What] Visit the children simultaneously
\item[How]  Taskpool approach
\item[Overhead]
  Task coordination, cache refilling,
  memory usage and bandwidth, synchronization on lazy values
\item[Parallelism]
  \begin{itemize}
  \item Coarse-grained: data parallelism (tree) instead of
        task parallelism (rules)
  \item Same machine, few cores
  \end{itemize}
\end{description}
\end{block}
\pause
\begin{tikzpicture}[remember picture,overlay]
\node[anchor=west,above of=d,xshift=1cm,ellipse callout,fill=uuxred!50,opacity=.9,callout absolute pointer={(d.mid)}]{More sophistication possible here};
\end{tikzpicture}
\pause
\begin{tikzpicture}[remember picture,overlay]
\node[anchor=west,above of=b,xshift=1cm,ellipse callout,fill=uuxred!50,opacity=.9,callout absolute pointer={(b.mid)}]{Computation needs to be large enough};
\end{tikzpicture}
\end{frame}

\begin{frame}
\frametitle{Code of visit invocations}

\begin{block}{Sequential}
\begin{code}
  (att left S blue)     <- left (att left I purple)
  (att right S blue)    <- right (att right I purple)
\end{code}
\end{block}

\begin{block}{Parallel}
%format sync1
\begin{code}
  sync1                 <- newEmptyMVar
  forkIO (left (att left I purple) >>= putMVar sync1)
  (att right S blue)    <- right (att right I purple)
  (att left S blue)     <- takeMVar sync1
\end{code}
\end{block}
\end{frame}

\section[Hints]{Hints}

\begin{frame}[plain]
\begin{center}\Large
Hints
\end{center}
\end{frame}

\begin{frame}
\begin{description}
\item[Question] Execute the visit in parallel or sequentially?
\item[Answer] Depends on runtime information
  \begin{itemize}
  \item The actual tree
  \item Expected complexity of the computations
  \end{itemize}
\item[Solution] Specified by programmer
  \begin{itemize}
  \item The decision as attribute
  \end{itemize}
\end{description}
\pause
\begin{description}
\item[Problem] Visits implicit in the AG description
\item[Solution]
  \begin{itemize}
  \item Runtime parallel/sequential switch per node
  \item By default set to sequential
  \item Can be toggled via side effects in a rule
  \item Rule needs to be handled with care
  \end{itemize}
\end{description}
\end{frame}

\begin{frame}
\begin{block}{Hint}
Additional attributes + heuristic
\begin{description}
\item[Attribute] Compute the depth as attribute
\item[Heuristic] Allow parallel only when:
\begin{code}
lhs.depth <= 2 || lhs.depth `mod` 4 == 0
\end{code}
\end{description}
\end{block}

\begin{block}{Heurisic}
Special kind of rule
\end{block}

\end{frame}

\begin{frame}
\frametitle{Depth attribute}

\begin{columns}
\column{0.4\textwidth}
\hfill
%include dia/depth.lhs
\column{0.6\textwidth}
\begin{code}
attr Even Odd
  inh depth   :: Int

sem Tree | Star
  root.depth  = 0

sem Odd | Segment
  end.depth   = lhs.depth + 1
\end{code}
\end{columns}
\end{frame}

%if False
\begin{frame}
\frametitle{Height attribute}

\begin{code}
attr Even Odd
  syn height  :: Int

sem Odd | Segment
  lhs.height  = @end.height + 1

sem Even | Tip
  lhs.height = 0

sem Even | Fork
  loc.height = left.height `max` right.height
  lhs.height = loc.height
\end{code}
\end{frame}
%endif

\begin{frame}
\frametitle{Heuristic}

\begin{block}{Monadic rule}
\texths
\begin{code}
sem Even | Fork

  ()  <-  if lhs.depth <= 2 || lhs.depth `mod` 4 == 0
          then  enableParallel
          else  return ()
\end{code}
\plainhs
\end{block}

\begin{block}{API}
\texths
\begin{code}
enableParallel   :: IO ()
disableParallel  :: IO ()
\end{code}
\plainhs
\end{block}
\pause
\begin{block}{Execution (final part of presentation)}
\begin{itemize}
\item The rule does not define any attributes
\item When is it executed?
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Implementation}

\begin{code}
  allowRef_ <-  newIORef False
  let allowParallel = writeIORef allowRef_ True
  ...
  ()  <-  if (att lhs I depth) <= 2 || (att lhs I depth) `mod` 4 == 0
          then  enableParallel
          else  return ()
  ...
  sync1   <-  newEmptyMVar
  allow_  <-  readIORef allowRef
  let fork_  | allow_     = forkIO
             | otherwise  = id

  fork_ (left (att left I depth) (att left I purple) >>= putMVar sync1)

  (att right S blue)  <- right (att right I depth) (att right I purple)
  (att left S blue)   <- takeMVar sync1
  ...
\end{code}
\end{frame}

\section[Ordering]{Evaluation order}

\begin{frame}[plain]
\begin{center}\Large
Ordering
\end{center}
\end{frame}

\begin{frame}
\frametitle{Challenge}

\begin{block}{When to schedule the rule?}
\begin{itemize}
\item Before the \emph{germane} visits to |left| and |right|
\item But: visits are implicit in the AG description!
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Ad-hoc solution}

\begin{center}
%include dia/pdgfork.lhs
\end{center}

\begin{block}{Name the rule + enforce before visit}
\texths
\begin{code}
sem Even | Fork

  loc.anchor  <-  if lhs.depth <= 2 || lhs.depth `mod` 4 == 0
                  then  allowParallel
                  else  return ()

  loc.anchor  <<  left.purple
  loc.anchor  <<  right.purple
\end{code}
\plainhs
\pause
\begin{description}
\item[Bad]  Need to know the germane inh attrs
\item[Bad]  Dependencies are verbose and error prone
\end{description}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Improvement}

\begin{block}{Dependency on syn attrs}
\begin{code}
  loc.anchor  <<  left.blue
  loc.anchor  <<  right.blue
\end{code}
\begin{description}
\item[Semantics] |loc.anchor| before any visits that computes |left.blue| and |right.blue|
\item[Good] syn attrs abstract from the visits
\item[Bad]  Still: verbose, error prone
\end{description}
\end{block}

\begin{block}{Sugar}
\texths
\begin{code}
sem Even | Fork
  parallel ^^^ left.blue right.blue ^^^ if  lhs.depth `mod` 4 == 0
\end{code}
\plainhs
\end{block}
\end{frame}

\begin{frame}
\frametitle{More complex solution}

\begin{block}{Schedule monadic rule}
\begin{itemize}
\item As early as possible (discussed later)
\item But only when the inherited attributes it needs are available
\item Rule does not force unexpected evaluation
\end{itemize}
\end{block}

\begin{block}{Zombie attributes}
\begin{itemize}
\item Attributes only needed by monadic rules
\item E.g. |height|
\item Schedule when the other attributes needed by the monadic
      have been scheduled.
\item As early as possible (discussed later)
\item Zombie attributes do not force unexpected evaluation
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Implementation}

\begin{block}{Monadic rule}
\begin{itemize}
\item Let |I| be the |lhs|-inherited attributes
      (indirectly) needed by monadic rule |R|
\item |R| must be and only be scheduled in the first visit where
      |I| is available (part of the protocol)
\item Schedule |R| \emph{early} (discussed later)
\end{itemize}
\end{block}

\begin{block}{Zombie attributes}
\begin{itemize}
\item Take largest |L `subset` I| so that each |a `elem` L| is \emph{live}
\item Schedule |a `elem` I - L| \emph{eventually} when |L| is available
\item Schedule |a| \emph{early} (discussed later)
\end{itemize}
\end{block}

\begin{block}{Attribute is live when}
\begin{itemize}
\item syn attr of a start symbol
\item Dependency of a rule that computes a live attribute
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Can of worms}

\begin{block}{Eventually}
  \begin{itemize}
  \item Attrs in |I-L| may depend on an attrs in |L|
  \item Cannot always be in the same visit as the last
        attrs of |L| in the protocol
  \end{itemize}
\end{block}
\begin{block}{Early}
  \begin{itemize}
  \item Must be predictable
  \item Must be a local property
  \item Some ideas in Chapter 3 of my thesis
  \end{itemize}
\end{block}
\end{frame}

\section[Conclusion]{Conclusion}

\begin{frame}[plain]
\begin{center}\Large
Conclusion
\end{center}
\end{frame}

\begin{frame}
\frametitle{Benchmarks on UHC}

\begin{block}{Cycle analysis}
\begin{itemize}
\item Usually statically acyclic (except fixpoint)
\item Execution time less than a second
\end{itemize}
\end{block}

\begin{block}{Protocol inference}
\begin{itemize}
\item Execution time less than a minute
\item Exponential blow-up of protocols does not occur
\end{itemize}
\end{block}

\begin{block}{Parallelism}
Performance/speedup: to be done...
\end{block}
\end{frame}

\begin{frame}
\begin{block}{Summary}
\begin{description}
\item[Static order] Allows control over evaluation
\item[Parallelism] Perform visits in parallel
\item[Hints]   Attributes + monadic rules
\item[Order]   Evaluate monadic rules first
\end{description}
\end{block}

\begin{block}{Other uses}
\begin{description}
\item[Debugging] Conditional breakpoints
\item[Contracts] Check invariants
\end{description}
\end{block}

\begin{block}{Ongoing work}
\begin{itemize}
\item Ordering of monadic rules
\item More fine-grained concurrency
\item Search for: UUAG + Universiteit Utrecht
\item (Hard) copy of my thesis: @amiddelk@@gmail.com@
\end{itemize}
\end{block}
\end{frame}

\end{document}