% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
%%\usepackage{xcolor}
\usepackage{../slides}
\usepackage{../langs}
\usepackage{../data}
\usepackage{../graphicss}
\usepackage{../grammar}
\usepackage[most]{tcolorbox}
\newtcbox{\hl}[1][]{%
size=fbox,
tcbox raise base, nobeforeafter,
enhanced, colframe=gray,
colback=gray!30, boxrule=1pt,
fontupper=\ttfamily,
#1}
\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\\[-3mm]
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
Office Hour: & Fridays 12 -- 14\\
Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS\\
Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\
\end{tabular}
\end{center}
\begin{center}
\begin{tikzpicture}
\node[drop shadow,fill=white,inner sep=0pt]
{\footnotesize\rowcolors{1}{capri!10}{white}
\begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
1 Introduction, Languages & 6 While-Language \\
2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
3 Automata, Regular Languages & \cellcolor{blue!50} 8 Compiling Functional Languages \\
4 Lexing, Tokenising & 9 Optimisations \\
5 Grammars, Parsing & 10 LLVM \\ \hline
\end{tabular}%
};
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t,fragile]
\mbox{}\\[-20mm]\mbox{}
\footnotesize
\begin{textblock}{13}(-0.5,0.2)
\begin{lstlisting}[language=JVMIS2,numbers=none]
.method public static main([Ljava/lang/String;)V
.limit locals 200
.limit stack 200
invokestatic foo/foo/read()I
istore 0
ldc 1
istore 1
Loop_begin_4:
iload 0
ldc 0
if_icmple Loop_end_5
iload 0
iload 1
imul
istore 1
iload 0
ldc 1
isub
istore 0
goto Loop_begin_4
\end{lstlisting}
\end{textblock}
\begin{textblock}{13}(7,8)
\begin{lstlisting}[language=JVMIS2,numbers=none]
Loop_end_5:
iload 1
invokestatic foo/foo/write(I)V
return
.end method
\end{lstlisting}
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t,fragile]
\mbox{}\\[-20mm]\mbox{}
\footnotesize
\begin{textblock}{13}(-0.5,0.2)
\begin{lstlisting}[language=JVMIS2,numbers=none]
.method public static main([Ljava/lang/String;)V
.limit locals 200
.limit stack 200
invokestatic foo/foo/read()I
istore 0 ; n
ldc 1
istore 1 ; res
Loop_begin_4:
iload 0 ; n
ldc 0
if_icmple Loop_end_5
iload 0 ; n
iload 1 ; res
imul
istore 1 ; res
iload 0 ; n
ldc 1
isub
istore 0 ; n
goto Loop_begin_4
\end{lstlisting}
\end{textblock}
\begin{textblock}{13}(7,8)
\begin{lstlisting}[language=JVMIS2,numbers=none]
Loop_end_5:
iload 1 ; res
invokestatic foo/foo/write(I)V
return
.end method
\end{lstlisting}
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t,fragile]
\small
\begin{textblock}{13}(-0.5,1)
\begin{lstlisting}[numbers=none]
def mkeps(r: Rexp) : Val = r match {
...
case PLUS(r) => Stars(List(mkeps(r)))
case OPTIONAL(r) => Stars(Nil)
case NTIMES(r, n) => Stars(List.fill(n)(mkeps(r)))
}
def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
...
case (RANGE(_), Empty) => Chr(c)
case (PLUS(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
case (OPTIONAL(r), v) => Stars(inj(r, c, v)::Nil)
case (NTIMES(r, n), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
}
\end{lstlisting}
\end{textblock}
\begin{textblock}{5}(3,13.5)
\bl{$r^? \dn r^{\{0..1\}}$}
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c]
% \begin{center}
% \bl{\begin{tabular}{@{}lcl@{}}
% \meta{Stmt} & $::=$ & $\texttt{skip}$\\
% & $|$ & \textit{Id}\;\texttt{:=}\;\meta{AExp}\\
% & $|$ & \texttt{if}\; \meta{BExp} \;\texttt{then}\; \meta{Block} \;\texttt{else}\; \meta{Block}\\
% & $|$ & \texttt{while}\; \meta{BExp} \;\texttt{do}\; \meta{Block}\\
% & $|$ & \texttt{read}\;\textit{Id}\\
% & $|$ & \texttt{write}\;\textit{Id}\\
% & $|$ & \texttt{write}\;\textit{String}\medskip\\
% \meta{Stmts} & $::=$ & \meta{Stmt} \;\texttt{;}\; \meta{Stmts}\\
% & $|$ & \meta{Stmt}\medskip\\
% \meta{Block} & $::=$ & \texttt{\{}\,\meta{Stmts}\,\texttt{\}}\\
% & $|$ & \meta{Stmt}\medskip\\
% \meta{AExp} & $::=$ & \ldots\\
% \meta{BExp} & $::=$ & \ldots\\
% \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{4cm}}
| \meta{Exp} + \meta{Exp} | ... | (\meta{Exp})
| \code{if} \meta{BExp} \code{then} \meta{Exp} \code{else} \meta{Exp}
| \code{write} \meta{Exp} {\hspace{5cm}}
| \meta{Exp} ; \meta{Exp}
| \textit{FunName} (\meta{Exp}, ... , \meta{Exp})\\
: \meta{BExp} ::= ...\\
: \meta{Def} ::= \code{def} \textit{FunName} ($\hspace{0.4mm}x_1$, ... , $x_n$) = \meta{Exp}\\
: \meta{Prog} ::= \meta{Def} ; \meta{Prog}
| \meta{Exp} ; \meta{Prog}
| \meta{Exp}\\
\end{plstx}}
% Almost what is implemented - Exp ; Exp is left-recursive
%
\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{Ideas}
Use separate JVM methods for each Fun-function.\bigskip
Compile \bl{\texttt{exp}}s such that the result of the expression
is on top of the stack.\bigskip
\begin{itemize}
\item \texttt{\color{codepurple}{write}}\texttt{(1 + 2)}
\item \texttt{1 + 2; 3 + 4}
\end{itemize}
\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}[t, 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 methods 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,linebackgroundcolor=\color{cream}]
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,linebackgroundcolor=\color{cream}]
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}[c,fragile]
\frametitle{\mbox{}\hspace{5cm}Factorial}
\begin{textblock}{7}(0,1.0)\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,linebackgroundcolor=\color{cream}]
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,linebackgroundcolor=\color{cream}]
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}[t, 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}[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,3)
\begin{lstlisting}[language=Scala, 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) => i"istore $y" }
args.map(a => compile_expT(a, env, "")).mkString ++
stores.reverse.mkString ++
i"goto ${n}_Start"
} else {
val is = "I" * args.length
args.map(a => compile_expT(a, env, "")).mkString ++
i"invokestatic XXX/XXX/${n}(${is})I"
}
\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}<1-13>
\end{frame}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: