\documentclass[dvipsnames,14pt,t]{beamer}
\usepackage{../slides}
\usepackage{../langs}
\usepackage{../data}
\usepackage{../graphics}
\usepackage{../grammar}
\usepackage{soul}

\tikzset{onslide/.code args={<#1>#2}{%
  \only<#1>{\pgfkeysalso{#2}} % \pgfkeysalso doesn't change the path
}}

\makeatletter
\newenvironment<>{btHighlight}[1][]
{\begin{onlyenv}#2\begingroup\tikzset{bt@Highlight@par/.style={#1}}\begin{lrbox}{\@tempboxa}}
{\end{lrbox}\bt@HL@box[bt@Highlight@par]{\@tempboxa}\endgroup\end{onlyenv}}

\newcommand<>\btHL[1][]{%
  \only#2{\begin{btHighlight}[#1]\bgroup\aftergroup\bt@HL@endenv}%
}
\def\bt@HL@endenv{%b jm 
  \end{btHighlight}%   
  \egroup
}
\newcommand{\bt@HL@box}[2][]{%
  \tikz[#1]{%
    \pgfpathrectangle{\pgfpoint{1pt}{0pt}}{\pgfpoint{\wd #2}{\ht #2}}%
    \pgfusepath{use as bounding box}%
    \node[anchor=base west, fill=orange!30,outer sep=0pt,inner xsep=1pt, inner ysep=0pt, rounded corners=3pt, minimum height=\ht\strutbox+1pt,#1]{\raisebox{1pt}{\strut}\strut\usebox{#2}};
  }%
}
\makeatother

\lstset{morekeywords={def,if,then,else,write,read},keywordstyle=\color{codepurple}\bfseries}

% beamer stuff
\renewcommand{\slidecaption}{CFL 09, King's College London}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}       


\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
  \begin{tabular}{@ {}c@ {}}
  \\[-3mm]
  \LARGE Compilers and \\[-2mm] 
  \LARGE Formal Languages (9)\\[3mm] 
  \end{tabular}}

  \normalsize
  \begin{center}
  \begin{tabular}{ll}
  Email:  & christian.urban at kcl.ac.uk\\
  Office: & S1.27 (1st floor Strand Building)\\
  Slides: & KEATS (also home work is there)\\
  \end{tabular}
  \end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t,fragile]
\frametitle{Compiling AExps}

For example \bl{$1 + ((2 * 3) + (4 - 3))$}:\medskip

\begin{columns}[T]
\begin{column}{.3\textwidth}
\begin{center}
\bl{\begin{tikzpicture}
\tikzset{level distance=12mm,sibling distance=4mm}
\tikzset{edge from parent/.style={draw,very thick}}
\Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]]
\end{tikzpicture}}
\end{center}
\end{column}
\begin{column}{.3\textwidth}
\begin{lstlisting}[language=JVMIS,numbers=none]
ldc 1 
ldc 2 
ldc 3 
imul 
ldc 4 
ldc 3 
isub 
iadd 
iadd
\end{lstlisting}
\end{column}
\end{columns}\bigskip

\small
Traverse tree in post-order \bl{$\Rightarrow$} code for 
stack-machine

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Compiling AExps}

\bl{
\begin{center}
\begin{tabular}{lcl}
$\textit{compile}(n, E)$ & $\dn$ & $\pcode{ldc}\;n$\smallskip\\
$\textit{compile}(a_1 + a_2, E)$ & $\dn$ \\
\multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\;\textit{compile}(a_2, E)\;@\; \pcode{iadd}$}\smallskip\\
$\textit{compile}(a_1 - a_2, E)$ & $\dn$ \\
\multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{isub}$}\smallskip\\
$\textit{compile}(a_1 * a_2, E)$ & $\dn$ \\
\multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{imul}$}\smallskip\\
$\textit{compile}(a_1 \backslash a_2, E)$ & $\dn$\\ 
\multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{idiv}$}\smallskip\\
$\textit{compile}(x, E)$ & $\dn$ & $\pcode{iload}\;E(x)$\\
\end{tabular}
\end{center}}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Compiling Ifs}

For example

\begin{lstlisting}[mathescape,numbers=none,language=While]
if 1 = 1 then x := 2 else y := 3
\end{lstlisting}


\begin{center}
\begin{lstlisting}[mathescape,language=JVMIS,numbers=none]
   ldc 1
   ldc 1
   if_icmpne L_ifelse $\quad\tikz[remember picture] \node (C) {\mbox{}};$
   ldc 2
   istore 0
   goto L_ifend $\quad\tikz[remember picture] \node (A) {\mbox{}};$
L_ifelse: $\quad\tikz[remember picture] \node[] (D) {\mbox{}};$
   ldc 3
   istore 1
L_ifend: $\quad\tikz[remember picture] \node[] (B) {\mbox{}};$
\end{lstlisting}
\end{center}

\begin{tikzpicture}[remember picture,overlay]
  \draw[->,very thick] (A) edge [->,to path={-- ++(10mm,0mm) 
           -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (B.east);
  \draw[->,very thick] (C) edge [->,to path={-- ++(10mm,0mm) 
           -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (D.east);
\end{tikzpicture}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Compiling Whiles}

For example

\begin{lstlisting}[mathescape,numbers=none,language=While]
while x <= 10 do x := x + 1
\end{lstlisting}


\begin{center}
\begin{lstlisting}[mathescape,language=JVMIS,numbers=none]
L_wbegin: $\quad\tikz[remember picture] \node[] (LB) {\mbox{}};$
   iload 0
   ldc 10
   if_icmpgt L_wend $\quad\tikz[remember picture] \node (LC) {\mbox{}};$
   iload 0
   ldc 1
   iadd
   istore 0
   goto L_wbegin $\quad\tikz[remember picture] \node (LA) {\mbox{}};$
L_wend: $\quad\tikz[remember picture] \node[] (LD) {\mbox{}};$
\end{lstlisting}
\end{center}

\begin{tikzpicture}[remember picture,overlay]
  \draw[->,very thick] (LA) edge [->,to path={-- ++(12mm,0mm) 
           -- ++(0mm,17.3mm) |- (\tikztotarget)},line width=1mm] (LB.east);
  \draw[->,very thick] (LC) edge [->,to path={-- ++(12mm,0mm) 
           -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (LD.east);
\end{tikzpicture}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Compiling Writes}

\small
\begin{lstlisting}[language=JVMIS,mathescape,
                   numbers=none,xleftmargin=-6mm]
.method public static write(I)V 
  .limit locals 1 
  .limit stack 2 
  getstatic java/lang/System/out 
                            Ljava/io/PrintStream; 
  iload 0
  invokevirtual java/io/PrintStream/println(I)V 
  return 
.end method



iload $E(x)$ 
invokestatic XXX/XXX/write(I)V
\end{lstlisting}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Compiling Main}

\footnotesize
\begin{lstlisting}[language=JVMIS,mathescape,
                   numbers=none,xleftmargin=-6mm]
.class public XXX.XXX
.super java/lang/Object

.method public <init>()V
    aload_0
    invokenonvirtual java/lang/Object/<init>()V
    return
.end method

.method public static main([Ljava/lang/String;)V
    .limit locals 200
    .limit stack 200

      $\textit{\ldots{}here comes the compiled code\ldots}$

    return
.end method
\end{lstlisting}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Functional Programming}

\footnotesize
\begin{textblock}{13}(0.9,3)
\begin{lstlisting}[]numbers=none]
def fib(n) = if n == 0 then 0 
             else if n == 1 then 1 
             else fib(n - 1) + fib(n - 2);

def fact(n) = if n == 0 then 1 else n * fact(n - 1);

def ack(m, n) = if m == 0 then n + 1
                else if n == 0 then ack(m - 1, 1)
                else ack(m - 1, ack(m, n - 1));
                
def gcd(a, b) = if b == 0 then a else gcd(b, a % b);                
\end{lstlisting}
\end{textblock}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Fun Grammar}
\bl{
\begin{plstx}[rhs style=]
: \meta{Exp} ::= \meta{Var} | \meta{Num}{\hspace{3cm}}
             |   \meta{Exp} + \meta{Exp} | ... | (\meta{Exp})
             |   \code{if} \meta{BExp} \code{then} \meta{Exp} \code{else} \meta{Exp}
             |   \code{write} \meta{Exp} {\hspace{3cm}}
             |   \meta{Exp} ; \meta{Exp}
             |   \textit{FunName} (\meta{Exp}, ... , \meta{Exp})\\
: \meta{BExp} ::= ...\\
: \meta{Decl} ::= \meta{Def} ; \meta{Decl}
             | \meta{Exp}\\
: \meta{Def} ::= \code{def} \textit{FunName} ($\hspace{0.4mm}x_1$, ... , $x_n$) = \meta{Exp}\\               
\end{plstx}}



\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c, fragile]
\frametitle{Abstract Syntax Trees}

\footnotesize
\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
abstract class Exp
abstract class BExp 
abstract class Decl

case class Var(s: String) extends Exp
case class Num(i: Int) extends Exp
case class Aop(o: String, a1: Exp, a2: Exp) extends Exp
case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
case class Write(e: Exp) extends Exp
case class Sequ(e1: Exp, e2: Exp) extends Exp
case class Call(name: String, args: List[Exp]) extends Exp

case class Bop(o: String, a1: Exp, a2: Exp) extends BExp

case class Def(name: String, 
               args: List[String], 
               body: Exp) extends Decl
case class Main(e: Exp) extends Decl
\end{lstlisting}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c, fragile]
\frametitle{Sequences}

Compiling \texttt{exp1 ; exp2}:\bigskip


\begin{lstlisting}[mathescape,language=JVMIS, numbers=none]
$\textit{compile}$(exp1)
pop
$\textit{compile}$(exp2)
\end{lstlisting}
  
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c, fragile]
\frametitle{Write}

Compiling call to \texttt{write(1+2)}:\bigskip


\begin{lstlisting}[mathescape,language=JVMIS, numbers=none]
$\textit{compile}$(1+2)
dup
invokestatic XXX/XXX/write(I)V
\end{lstlisting}\bigskip

\small
needs the helper method

\footnotesize
\begin{lstlisting}[language=JVMIS, 
                   xleftmargin=2mm, 
                   numbers=none]
.method public static write(I)V 
   .limit locals 1
   .limit stack 2
   getstatic java/lang/System/out Ljava/io/PrintStream; 
   iload 0 
   invokevirtual java/io/PrintStream/println(I)V 
   return 
.end method
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t, fragile]
\frametitle{Function Definitions}

\footnotesize
\begin{lstlisting}[language=JVMIS, 
                   xleftmargin=2mm, 
                   numbers=none]
.method public static write(I)V 
   .limit locals 1
   .limit stack 2
   getstatic java/lang/System/out Ljava/io/PrintStream; 
   iload 0 
   invokevirtual java/io/PrintStream/println(I)V 
   return 
.end method
\end{lstlisting}\bigskip

\small We will need for definitions, like\footnotesize\medskip

\begin{lstlisting}[language=JVMIS, 
                   xleftmargin=2mm, 
                   numbers=none]
def fname (x1, ... , xn) = ...                   
                   
.method public static fname (I...I)I
  .limit locals ??
  .limit stack ?? 
  ??
.end method
\end{lstlisting}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c, fragile]
\frametitle{Stack Estimation}
\small
\mbox{}\\[-15mm]

\bl{\begin{center}
\begin{tabular}{@{\hspace{-4mm}}l@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
$\textit{estimate}(n)$ & $\dn$ & $1$\\
$\textit{estimate}(x)$ & $\dn$ & $1$\\
$\textit{estimate}(a_1\;aop\;a_2)$ & $\dn$ &
$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\
$\textit{estimate}(\pcode{if}\;b\;\pcode{then}\;e_1\;\pcode{else}\;e_2)$ & $\dn$ & 
$\textit{estimate}(b) +$\\ 
& & $\quad max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\
$\textit{estimate}(\pcode{write}(e))$ & $\dn$ & 
$\textit{estimate}(e) + 1$\\
$\textit{estimate}(e_1 ; e_2)$ & $\dn$ & 
$max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\
$\textit{estimate}(f(e_1, ..., e_n))$ & $\dn$ & 
$\sum_{i = 1..n}\;estimate(e_i)$\medskip\\
$\textit{estimate}(a_1\;bop\;a_2)$ & $\dn$ &
$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\
\end{tabular}
\end{center}}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]
\frametitle{Successor Function}

\begin{textblock}{7}(1,2.5)\footnotesize
\begin{minipage}{6cm}
\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]
.method public static suc(I)I 
.limit locals 1
.limit stack 2
  iload 0
  ldc 1
  iadd
  ireturn
.end method 
\end{lstlisting}
\end{minipage}
\end{textblock}

\begin{textblock}{7}(6,8)
\begin{bubble}[5cm]\small
\begin{lstlisting}[language=Lisp,
                   basicstyle=\ttfamily, 
                   numbers=none,
                   xleftmargin=1mm]
def suc(x) = x + 1;
\end{lstlisting}
\end{bubble}
\end{textblock}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]
\frametitle{Addition Function}

\begin{textblock}{7}(1,1.9)\footnotesize
\begin{minipage}{6cm}
\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]
.method public static add(II)I 
.limit locals 2
.limit stack 5
  iload 0
  ldc 0
  if_icmpne If_else
  iload 1
  goto If_end
If_else:
  iload 0
  ldc 1
  isub
  iload 1
  invokestatic XXX/XXX/add(II)I
  invokestatic XXX/XXX/suc(I)I
If_end:
  ireturn
.end method
\end{lstlisting}
\end{minipage}
\end{textblock}

\begin{textblock}{7}(6,6.6)
\begin{bubble}[7cm]\small
\begin{lstlisting}[language=Lisp,
                   basicstyle=\ttfamily, 
                   numbers=none,
                   xleftmargin=1mm]
def add(x, y) = 
    if x == 0 then y 
    else suc(add(x - 1, y));
\end{lstlisting}
\end{bubble}
\end{textblock}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]
\frametitle{Factorial}

\begin{textblock}{7}(1,1.5)\footnotesize
\begin{minipage}{6cm}
\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]
.method public static facT(II)I 
.limit locals 2
.limit stack 6
  iload 0
  ldc 0	
  if_icmpne If_else_2
  iload 1
  goto If_end_3
If_else_2:
  iload 0
  ldc 1
  isub
  iload 0
  iload 1
  imul
  invokestatic fact/fact/facT(II)I
If_end_3:
  ireturn
.end method 
\end{lstlisting}
\end{minipage}
\end{textblock}

\begin{textblock}{7}(6,7)
\begin{bubble}[7cm]\small
\begin{lstlisting}[language=Lisp,
                   basicstyle=\ttfamily, 
                   numbers=none,
                   xleftmargin=1mm]
def facT(n, acc) = 
  if n == 0 then acc 
  else facT(n - 1, n * acc);
\end{lstlisting}
\end{bubble}
\end{textblock}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]

\begin{textblock}{7}(1,-0.2)\footnotesize
\begin{minipage}{6cm}
\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none, escapeinside={(*@}{@*)}]
.method public static facT(II)I 
.limit locals 2
.limit stack 6
(*@\hl{facT\_Start:} @*)
  iload 0
  ldc 0
  if_icmpne If_else_2
  iload 1
  goto If_end_3
If_else_2:
  iload 0
  ldc 1
  isub
  iload 0
  iload 1
  imul
  (*@\hl{istore 1} @*)
  (*@\hl{istore 0} @*)
  (*@\hl{goto facT\_Start} @*)
If_end_3:
  ireturn
.end method 
\end{lstlisting}
\end{minipage}
\end{textblock}

\begin{textblock}{7}(6,7)
\begin{bubble}[7cm]\small
\begin{lstlisting}[language=Lisp,
                   basicstyle=\ttfamily, 
                   numbers=none,
                   xleftmargin=1mm]
def facT(n, acc) = 
  if n == 0 then acc 
  else facT(n - 1, n * acc);
\end{lstlisting}
\end{bubble}
\end{textblock}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c, fragile]
\frametitle{Tail Recursion}

A call to \texttt{f(args)} is usually compiled as\medskip

{\small\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
  args onto stack
  invokestatic  .../f 
\end{lstlisting}}\pause


A call is in tail position provided:\medskip

{\small\begin{itemize}
\item \texttt{if Bexp then \hl{Exp} else \hl{Exp}}
\item \texttt{Exp ; \hl{Exp}}
\item \texttt{Exp  op Exp}
\end{itemize}}\medskip

then a call \texttt{f(args)} can be compiled as\medskip\small

\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
  prepare environment
  jump to start of function
\end{lstlisting}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c, fragile]
\frametitle{Tail Recursive Call}
\footnotesize

\begin{textblock}{13}(-0.3,2)
\begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none]
def compile_expT(a: Exp, env: Mem, name: String): Instrs = 
  ...
  case Call(n, args) => if (name == n) 
  { 
    val stores = args.zipWithIndex.map 
       { case (x, y) => "istore " + y.toString + "\n" } 
    args.flatMap(a => compile_expT(a, env, "")) ++
    stores.reverse ++ 
    List ("goto " + n + "_Start\n") 
  } 
  else 
  {
    val is = "I" * args.length
    args.flatMap(a => compile_expT(a, env, "")) ++
    List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n")
  }
\end{lstlisting}
\end{textblock}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \begin{frame}[c]
  \frametitle{Dijkstra on Testing}
  
  \begin{bubble}[10cm]
  ``Program testing can be a very effective way to show the
  presence of bugs, but it is hopelessly inadequate for showing
  their absence.''
  \end{bubble}\bigskip
  
  \small
  What is good about compilers: the either seem to work,
  or go horribly wrong (most of the time).
  
  \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{\Large Proving Programs to be Correct}

\begin{bubble}[10cm]
\small
{\bf Theorem:} There are infinitely many prime 
numbers.\medskip\\

{\bf Proof} \ldots\\
\end{bubble}\bigskip


similarly\bigskip

\begin{bubble}[10cm]
\small
{\bf Theorem:} The program is doing what 
it is supposed to be doing.\medskip

{\bf Long, long proof} \ldots\\
\end{bubble}\bigskip\medskip

\small This can be a gigantic proof. The only hope is to have
help from the computer. `Program' is here to be understood to be
quite general (compiler, OS, \ldots).

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

\begin{frame}[c]
\frametitle{Can This Be Done?}

\begin{itemize}
\item in 2008, verification of a small C-compiler
\begin{itemize}
\item ``if my input program has a certain behaviour, then the compiled machine code has the same behaviour''
\item is as good as \texttt{gcc -O1}, but much, much less buggy 
\end{itemize}
\end{itemize}

\begin{center}
  \includegraphics[scale=0.12]{../pics/compcert.png}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
\begin{frame}[c]
\frametitle{Fuzzy Testing C-Compilers}

\begin{itemize}
\item tested GCC, LLVM and others by randomly generating 
C-programs
\item found more than 300 bugs in GCC and also
many in LLVM (some of them highest-level critical)\bigskip
\item about CompCert:

\begin{bubble}[10cm]\small ``The striking thing about our CompCert
results is that the middle-end bugs we found in all other
compilers are absent. As of early 2011, the under-development
version of CompCert is the only compiler we have tested for
which Csmith cannot find wrong-code errors. This is not for
lack of trying: we have devoted about six CPU-years to the
task.'' 
\end{bubble} 
\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

\end{document}

%%% Local Variables:  
%%% mode: latex
%%% TeX-master: t
%%% End: