diff -r feb8a2a42625 -r 17acdd516ccd slides/slides09.tex-bak
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/slides/slides09.tex-bak	Wed Nov 29 08:47:22 2017 +0000
@@ -0,0 +1,766 @@
+\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 (8)\\[3mm] 
+  \end{tabular}}
+
+  \normalsize
+  \begin{center}
+  \begin{tabular}{ll}
+  Email:  & christian.urban at kcl.ac.uk\\
+  Office: & N7.07 (North Wing, Bush House)\\
+  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: 
+