--- a/slides/slides07.tex Tue Nov 20 13:23:51 2018 +0000
+++ b/slides/slides07.tex Tue Nov 20 13:37:40 2018 +0000
@@ -1,14 +1,13 @@
\documentclass[dvipsnames,14pt,t]{beamer}
\usepackage{../slides}
-\usepackage{../graphics}
\usepackage{../langs}
\usepackage{../data}
-
+\usepackage{../graphics}
+\usepackage{../grammar}
% beamer stuff
\renewcommand{\slidecaption}{CFL 07, King's College London}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
-%\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
\begin{document}
@@ -26,392 +25,106 @@
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
Office: & N\liningnums{7.07} (North Wing, Bush House)\\
- Slides: & KEATS (also home work is there)\\
+ Slides: & KEATS (also homework is there)\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Bird's Eye View}
-\newcommand{\qq}{\mbox{\texttt{"}}}
+\begin{center}
+\begin{tikzpicture}
+\node (rexp) {\bl{\bf Lexer}};
+\node (nfa) [right=of rexp] {\bl{\bf Parser}};
+\node (dfa) [right=of nfa]
+ {\bl{\begin{tabular}{c}\bf Machine Code/\\\bf Java Byte Code\end{tabular}}};
+\path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}token\\[-1mm]
+sequence\end{tabular}} (nfa);
+\path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}parse\\[-1mm] tree\end{tabular}}(dfa);
+\end{tikzpicture}\\
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{CFGs}
+\begin{textblock}{10}(0.5,0.5)
+ \LARGE
+ \fontspec{Hoefler Text Black}
+ \textcolor{ProcessBlue}{JVM\\ Code}
+ \\[12mm]
+
+ \normalsize
+ Jasmin\\
+ Krakatau\\
+ ASM lib
+\end{textblock}
+
-A \alert{context-free} grammar (CFG) \bl{$G$} consists of:
+\fontsize{8}{10}\selectfont
+%\footnotesize
+\mbox{}\\[-8mm]\mbox{}
+
+\begin{columns}
+\begin{column}{2cm}
+\lstinputlisting[numbers=none]{../progs/appHa.j}
+\end{column}
+
+\begin{column}{2cm}
+\lstinputlisting[numbers=none]{../progs/appHb.j}
+\end{column}
+
+\end{columns}
-\begin{itemize}
-\item a finite set of nonterminal symbols (upper case)
-\item a finite terminal symbols or tokens (lower case)
-\item a start symbol (which must be a nonterminal)
-\item a set of rules
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+
\begin{center}
-\bl{$A \rightarrow \text{rhs}_1 | \text{rhs}_2 | \ldots$}
+\bl{\begin{tabular}{@{}lcl@{}}
+\\[-12mm]
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-where \bl{rhs} are sequences involving terminals and nonterminals (can also be empty).\medskip\pause
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Fibonacci Numbers\end{tabular}}
-\end{itemize}
+\mbox{}\\[-18mm]\mbox{}
+
+{\lstset{language=While}\fontsize{10}{12}\selectfont
+\texttt{\lstinputlisting{../progs/fib.while}}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Hierarchy of Languages\end{tabular}}
-
-Recall that languages are sets of strings.
-
-\begin{center}
-\begin{tikzpicture}
-[rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}]
-
-\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
-\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
-\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
-\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
-\draw (0,-1.4) node [rect] {regular languages};
-\end{tikzpicture}
-
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}
-
-A grammar for arithmetic expressions and numbers:
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$E$ & $\rightarrow$ & $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\
-$N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\: \ldots \;|\; 9$
-\end{tabular}}
-\end{center}
-
-Unfortunately it is left-recursive (and ambiguous).\medskip\\
-A problem for \alert{recursive descent parsers} (e.g.~parser combinators).
-\bigskip\pause
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Numbers\end{tabular}}
-
-
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\
-\end{tabular}}
-\end{center}
-
-A non-left-recursive, non-ambiguous grammar for numbers:
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $0 \cdot N \;|\;1 \cdot N \;|\;\ldots\;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\
-\end{tabular}}
-\end{center}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Operator Precedences\end{tabular}}
-
-
-To disambiguate
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$E$ & $\rightarrow$ & $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\
-\end{tabular}}
-\end{center}
-
-Decide on how many precedence levels, say\medskip\\
-\hspace{5mm}highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+}
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$E_{low}$ & $\rightarrow$ & $E_{med} \cdot + \cdot E_{low} \;|\; E_{med}$ \\
-$E_{med}$ & $\rightarrow$ & $E_{hi} \cdot * \cdot E_{med} \;|\; E_{hi}$\\
-$E_{hi}$ & $\rightarrow$ & $( \cdot E_{low} \cdot ) \;|\;N$ \\
-\end{tabular}}
-\end{center}\pause
-
-\small What happens with \bl{$1 + 3 + 4$}?
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Removing Left-Recursion\end{tabular}}
-
-The rule for numbers is directly left-recursive:
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1\;\;\;\;(\ldots)$
-\end{tabular}}
-\end{center}
-
-Translate
-
-\begin{center}
-\begin{tabular}{ccc}
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $N \cdot \alpha$\\
- & $\;|\;$ & $\beta$\\
- \\
-\end{tabular}}
-& {\Large$\Rightarrow$} &
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $\beta \cdot N'$\\
-$N'$ & $\rightarrow$ & $\alpha \cdot N'$\\
- & $\;|\;$ & $\epsilon$
-\end{tabular}}
-\end{tabular}
-\end{center}\pause
-
-Which means
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1 \cdot N'$\\
-$N'$ & $\rightarrow$ & $N \cdot N' \;|\; \epsilon$\\
-\end{tabular}}
-\end{center}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Chomsky Normal Form\end{tabular}}
-
-All rules must be of the form
-
-\begin{center}
-\bl{$A \rightarrow a$}
-\end{center}
-
-or
-
-\begin{center}
-\bl{$A \rightarrow B\cdot C$}
-\end{center}
-
-No rule can contain \bl{$\epsilon$}.
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}$\epsilon$-Removal\end{tabular}}
-
-\begin{enumerate}
-\item If \bl{$A\rightarrow \alpha \cdot B \cdot \beta$} and \bl{$B \rightarrow \epsilon$} are in the grammar,
-then add \bl{$A\rightarrow \alpha \cdot \beta$} (iterate if necessary).
-\item Throw out all \bl{$B \rightarrow \epsilon$}.
-\end{enumerate}
-
-\small
-\begin{center}
-\begin{tabular}{ccc}
-\bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
-$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'$\\
-$N'$ & $\rightarrow$ & $N \cdot N'\;|\;\epsilon$\\
-\\
-\\
-\\
-\\
-\\
-\end{tabular}} &
-\bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
-\\
-$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
-$N'$ & $\rightarrow$ & $N \cdot N'\;|\;N\;|\;\epsilon$\\
-\\
-$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
-$N'$ & $\rightarrow$ & $N \cdot N'\;|\;N$\\
-\end{tabular}}
-\end{tabular}
-\end{center}
-
-\pause\normalsize
-\begin{center}
-\bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
-$N$ & $\rightarrow$ & $0 \cdot N\;|\; 1\cdot N\;|\;0\;|\;1$\\
-\end{tabular}}
-
-\end{center}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}
-
-If grammar is in Chomsky normalform \ldots
-
-\begin{center}
-\bl{\begin{tabular}{@ {}lcl@ {}}
-$S$ & $\rightarrow$ & $N\cdot P$ \\
-$P$ & $\rightarrow$ & $V\cdot N$ \\
-$N$ & $\rightarrow$ & $N\cdot N$ \\
-$N$ & $\rightarrow$ & $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\
-$V$ & $\rightarrow$ & $\texttt{trains}$
-\end{tabular}}
-\end{center}
-
-\bl{\texttt{Jeff trains geometry students}}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}
-
-
-\begin{itemize}
-\item fastest possible algorithm for recognition problem
-\item runtime is \bl{$O(n^3)$}\bigskip
-\item grammars need to be transferred into CNF
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Hierarchy of Languages\end{tabular}}
-
-Recall that languages are sets of strings.
-
-\begin{center}
-\begin{tikzpicture}
-[rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}]
-
-\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
-\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
-\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
-\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
-\draw (0,-1.4) node [rect] {regular languages};
-\end{tikzpicture}
-
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Context Sensitive Grms\end{tabular}}
-
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$S$ & $\Rightarrow$ & $bSAA\;|\; \epsilon$\\
-$A$ & $\Rightarrow$ & $a$\\
-$bA$ & $\Rightarrow$ & $Ab$\\
-\end{tabular}}
-\end{center}\pause
-
-\begin{center}
-\bl{$S \Rightarrow\ldots\Rightarrow^? "ababaa"$}
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{center}
-\bl{\begin{tabular}{@{}lcl@{}}
-\textit{Stmt} & $\rightarrow$ & $\texttt{skip}$\\
- & $|$ & \textit{Id}\;\texttt{:=}\;\textit{AExp}\\
- & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Block} \;\texttt{else}\; \textit{Block}\\
- & $|$ & \texttt{while}\; \textit{BExp} \;\texttt{do}\; \textit{Block}\\
- & $|$ & \texttt{read}\;\textit{Id}\\
- & $|$ & \texttt{write}\;\textit{Id}\\
- & $|$ & \texttt{write}\;\textit{String}\medskip\\
-\textit{Stmts} & $\rightarrow$ & \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\
- & $|$ & \textit{Stmt}\medskip\\
-\textit{Block} & $\rightarrow$ & \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\
- & $|$ & \textit{Stmt}\medskip\\
-\textit{AExp} & $\rightarrow$ & \ldots\\
-\textit{BExp} & $\rightarrow$ & \ldots\\
-\end{tabular}}
-\end{center}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\mbox{\lstinputlisting[language=while]{../progs/fib.while}}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}An Interpreter\end{tabular}}
-
-\begin{center}
-\bl{\begin{tabular}{l}
-$\{$\\
-\;\;$x := 5 \text{;}$\\
-\;\;$y := x * 3\text{;}$\\
-\;\;$y := x * 4\text{;}$\\
-\;\;$x := u * 3$\\
-$\}$
-\end{tabular}}
-\end{center}
-
-\begin{itemize}
-\item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause
-\item \bl{\text{eval}(stmt, env)}
-\end{itemize}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Interpreter\end{tabular}}
+\frametitle{Interpreter}
\begin{center}
\bl{\begin{tabular}{@{}lcl@{}}
@@ -426,12 +139,12 @@
\end{tabular}}
\end{center}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}}
+\frametitle{Interpreter (2)}
\begin{center}
\bl{\begin{tabular}{@{}lcl@{}}
@@ -450,27 +163,42 @@
\end{tabular}}
\end{center}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Test Program\end{tabular}}
+\frametitle{Test Program}
\mbox{}\\[-18mm]\mbox{}
-{\lstset{language=While}%%\fontsize{10}{12}\selectfont
+{\lstset{language=While}\fontsize{10}{12}\selectfont
\texttt{\lstinputlisting{../progs/loops.while}}}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
+\fontsize{7}{9}\selectfont
+
+
+\begin{columns}
+\begin{column}{7cm}
+\lstinputlisting[numbers=none]{../progs/appHa.j}
+\end{column}
+
+\begin{column}{7cm}
+\lstinputlisting[numbers=none]{../progs/appHb.j}
+\end{column}
+\end{columns}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}}
+\frametitle{Interpreted Code}
\begin{center}
\begin{tikzpicture}
@@ -480,13 +208,12 @@
\end{tikzpicture}
\end{center}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Java Virtual Machine\end{tabular}}
+\frametitle{Java Virtual Machine}
\begin{itemize}
\item introduced in 1995
@@ -494,12 +221,673 @@
\item contains a JIT compiler
\item many languages take advantage of JVM's infrastructure (JRE)
\item is garbage collected $\Rightarrow$ no buffer overflows
-\item some languages compile to the JVM: Scala, Clojure\ldots
+\item some languages compiled to the JVM: Scala, Clojure\ldots
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t,fragile]
+\frametitle{Compiling AExps}
+
+For example \liningnums{\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}[t,fragile]
+\frametitle{Compiling AExps}
+
+\liningnums{\textbf{\Large\bl{1 + 2 + 3}}}
+
+\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm]
+ldc 1
+ldc 2
+iadd
+ldc 3
+iadd
+\end{lstlisting}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t,fragile]
+\frametitle{Compiling AExps}
+
+\liningnums{\textbf{\Large\bl{1 + (2 + 3)}}}
+
+\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm]
+ldc 1
+ldc 2
+ldc 3
+iadd
+iadd
+\end{lstlisting}
+\bigskip\pause
+\vfill
+
+\textcolor{codepurple}{\textbf{\texttt{dadd}}},
+\textcolor{codepurple}{\textbf{\texttt{fadd}}},
+\textcolor{codepurple}{\textbf{\texttt{ladd}}}, \ldots
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Compiling AExps}
+
+\begin{center}
+\bl{\begin{tabular}{@{}lcl@{}}
+$\text{compile}(n)$ & $\dn$ & $\text{ldc}\;n$\\
+$\text{compile}(a_1 + a_2)$ & $\dn$\\
+\multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\;\text{compile}(a_2)\;@\; \text{iadd}$}\smallskip\\
+$\text{compile}(a_1 - a_2)$ & $\dn$\\
+\multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{isub}$}\smallskip\\
+$\text{compile}(a_1 * a_2)$ & $\dn$\\
+\multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{imul}$}\smallskip\\
+\end{tabular}}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t,fragile]
+\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}
+
+\liningnums{\textbf{\Large\bl{1 $+$ 2 $*$ 3 $+$ (4 $-$ 3)}}}
+
+\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm]
+ldc 1
+ldc 2
+ldc 3
+imul
+ldc 4
+ldc 3
+isub
+iadd
+iadd
+\end{lstlisting}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Variables}
+\liningnums{\textbf{\Large\bl{x $:=$ 5 $+$ y $*$ 2}}}\bigskip\pause
+
+\begin{itemize}
+\item lookup: \bl{$\textcolor{codepurple}{\textbf{\texttt{iload}}}\; index$}
+\item store: \bl{$\textcolor{codepurple}{\textbf{\texttt{istore}}}\; index$}
+\end{itemize}\bigskip\pause
+
+while compilating we have to maintain a map between our identifiers and the
+Java bytecode indices
+
+\begin{center}
+\bl{$\text{compile}(a, E)$}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Compiling AExps}
+
+\begin{center}
+\bl{\begin{tabular}{@{}lcl@{}}
+$\text{compile}(n, E)$ & $\dn$ & $\text{ldc}\;n$\\
+$\text{compile}(a_1 + a_2, E)$ & $\dn$\\
+\multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\;\text{compile}(a_2, E)\;@\; \text{iadd}$}\smallskip\\
+$\text{compile}(a_1 - a_2, E)$ & $\dn$\\
+\multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{isub}$}\smallskip\\
+$\text{compile}(a_1 * a_2, E)$ & $\dn$\\
+\multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{imul}$}\bigskip\\
+$\text{compile}(x, E)$ & $\dn$ & $\text{iload}\;E(x)$\\
+\end{tabular}}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c, fragile]
+\frametitle{Mathematical Functions}
+
+Compilation of some mathematical functions:
+
+\begin{center}
+\begin{tabular}{lcl}
+\texttt{Aop("+", a1, a2)} & $\Rightarrow$ & \texttt{...iadd}\\
+\texttt{Aop("-", a1, a2)} & $\Rightarrow$ & \texttt{...isub}\\
+\texttt{Aop("*", a1, a2)} & $\Rightarrow$ & \texttt{...imul}\\
+\texttt{Aop("/", a1, a2)} & $\Rightarrow$ & \texttt{...idiv}\\
+\texttt{Aop("\%", a1, a2)} & $\Rightarrow$ & \texttt{...irem}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Compiling Statements}
+
+We return a list of instructions and an environment for the
+variables
+
+\begin{center}
+\bl{\begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
+$\text{compile}(\text{skip}, E)$ & $\dn$ & $(\textit{Nil}, E)$\bigskip\\
+$\text{compile}(x := a, E)$ & $\dn$\\
+\multicolumn{3}{l}{$(\text{compile}(a, E) \;@\;\text{istore}\;index, E(x\mapsto index))$}\\
+\end{tabular}}
+\end{center}\medskip
+
+where \bl{$index$} is \bl{$E(x)$} if it is already defined,
+or if it is not, then the largest index not yet seen
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Compiling Assignments}
+
+\liningnums{\textbf{\Large\bl{x $:=$ x $+$ 1}}}
+
+\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm]
+iload /*@\bl{$n_x$}@*/
+ldc 1
+iadd
+istore /*@\bl{$n_x$}@*/
+\end{lstlisting}\medskip
+
+where \bl{$n_x$} is the index corresponding to the variable~\bl{$x$}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Compiling Ifs}
+
+{\Large\bl{$\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2$}}\bigskip\bigskip
+
+\onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:}
+
+\begin{center}
+\begin{tikzpicture}[node distance=2mm and 4mm,
+ block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},
+ point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},
+ skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]
+\node (A1) [point] {};
+\node (b) [block, right=of A1] {code of \bl{$b$}};
+\node (A2) [point, right=of b] {};
+\node (cs1) [block, right=of A2] {code of \bl{$cs_1$}};
+\node (A3) [point, right=of cs1] {};
+\node (cs2) [block, right=of A3] {code of \bl{$cs_2$}};
+\node (A4) [point, right=of cs2] {};
+
+\only<2>{
+\draw (A1) edge [->, red, line width=1mm] (b);
+\draw (b) edge [->, red, line width=1mm] (cs1);
+\draw (cs1) edge [->, red, line width=1mm] (A3);
+\draw (A3) edge [->,skip loop] (A4);
+\node [below=of cs2] {\raisebox{-5mm}{\small{}jump}};}
+\only<3>{
+\draw (A1) edge [->, red, line width=1mm] (b);
+\draw (b) edge [->, red, line width=1mm] (A2);
+\draw (A2) edge [skip loop] (A3);
+\draw (A3) edge [->, red, line width=1mm] (cs2);
+\draw (cs2) edge [->,red, line width=1mm] (A4);
+\node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};}
+\end{tikzpicture}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t,fragile]
+\frametitle{Conditional Jumps}
+
+\begin{minipage}{1.1\textwidth}
+\begin{itemize}
+\item \textcolor{codepurple}{\textbf{\texttt{if\_icmpeq}}} \bl{$label$}
+ if two ints are equal, then jump\medskip
+\item \textcolor{codepurple}{\textbf{\texttt{if\_icmpne}}} \bl{$label$}
+ if two ints aren't equal, then jump\medskip
+\item \textcolor{codepurple}{\textbf{\texttt{if\_icmpge}}} \bl{$label$}
+ if one int is greater or equal then another, then jump
+\item[]\ldots
+\end{itemize}
+\end{minipage}\pause
+
+\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=2cm]
+/*@\bl{$L_1$:}@*/
+ if_icmpeq /*@\bl{$L_2$}@*/
+ iload 1
+ ldc 1
+ iadd
+ if_icmpeq /*@\bl{$L_1$}@*/
+/*@\bl{$L_2$:}@*/
+\end{lstlisting}
+
+
+\begin{textblock}{3.5}(11,12)
+\only<3>{labels must be unique}
+\end{textblock}
+\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}[t]
+\frametitle{Compiling BExps}
+
+{\Large\bl{$a_1 = a_2$}}
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$\text{compile}(a_1 = a_2, E, lab)$ & $\dn$\\
+\multicolumn{3}{l}{$\quad\text{compile}(a_1, E) \;@\;\text{compile}(a_2, E)\;@\; \text{if\_icmpne}\;lab$}
+\end{tabular}}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c, fragile]
+\frametitle{Boolean Expressions}
+
+Compilation of boolean expressions:
+
+\begin{center}
+\begin{tikzpicture}[node distance=2mm and 4mm,
+ block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},
+ point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},
+ skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]
+\node (A1) [point] {};
+\node (b) [block, right=of A1] {code of \bl{$b$}};
+\node (A2) [point, right=of b] {};
+\node (cs1) [block, right=of A2] {code of \bl{$cs_1$}};
+\node (A3) [point, right=of cs1] {};
+\node (cs2) [block, right=of A3] {code of \bl{$cs_2$}};
+\node (A4) [point, right=of cs2] {};
+
+\only<1>{
+\draw (A1) edge [->, red, line width=1mm] (b);
+\draw (b) edge [->, red, line width=1mm] (A2);
+\draw (A2) edge [skip loop] (A3);
+\draw (A3) edge [->, red, line width=1mm] (cs2);
+\draw (cs2) edge [->,red, line width=1mm] (A4);
+\node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};}
+\end{tikzpicture}
+\end{center}
+
+\begin{center}
+\begin{tabular}{lcl}
+\texttt{Bop("==", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpne...}\\
+\texttt{Bop("!=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpeq...}\\
+\texttt{Bop("<", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpge...}\\
+\texttt{Bop("<=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpgt...}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Compiling Ifs}
+
+{\Large\bl{if $b$ then $cs_1$ else $cs_2$}}
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$\text{compile}(\text{if}\;b\;\text{then}\; cs_1\;\text{else}\; cs_2, E)$ & $\dn$\\
+\multicolumn{3}{l}{$\quad l_{ifelse}\;$ \textcolor{black}{(fresh label)}}\\
+\multicolumn{3}{l}{$\quad l_{ifend}\;$ \textcolor{black}{(fresh label)}}\\
+\multicolumn{3}{l}{$\quad (is_1, E') = \text{compile}(cs_1, E)$}\\
+\multicolumn{3}{l}{$\quad (is_2, E'') = \text{compile}(cs_2, E')$}\\
+\multicolumn{3}{l}{$\quad(\text{compile}(b, E, l_{ifelse})$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;is_1$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{ifend}$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifelse}:$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;is_2$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifend}:, E'')$}\\
+\end{tabular}}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Compiling Whiles}
+
+{\Large\bl{$\text{while}\;b\;\text{do}\;cs$}}\bigskip\bigskip
+
+\onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:}
+
+\begin{center}
+\begin{tikzpicture}[node distance=2mm and 4mm,
+ block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},
+ point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},
+ skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]
+\node (A0) [point, left=of A1] {};
+\node (A1) [point] {};
+\node (b) [block, right=of A1] {code of \bl{$b$}};
+\node (A2) [point, right=of b] {};
+\node (cs1) [block, right=of A2] {code of \bl{$cs$}};
+\node (A3) [point, right=of cs1] {};
+\node (A4) [point, right=of A3] {};
+
+\only<2>{
+\draw (A0) edge [->, red, line width=1mm] (b);
+\draw (b) edge [->, red, line width=1mm] (cs1);
+\draw (cs1) edge [->, red, line width=1mm] (A3);
+\draw (A3) edge [->,skip loop] (A1);}
+\only<3>{
+\draw (A0) edge [->, red, line width=1mm] (b);
+\draw (b) edge [->, red, line width=1mm] (A2);
+\draw (A2) edge [skip loop] (A3);
+\draw (A3) edge [->, red, line width=1mm] (A4);}
+\end{tikzpicture}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Compiling Whiles}
+
+{\Large\bl{while $b$ do $cs$}}
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$\text{compile}(\text{while}\; b\; \text{do} \;cs, E)$ & $\dn$\\
+\multicolumn{3}{l}{$\quad l_{wbegin}\;$ \textcolor{black}{(fresh label)}}\\
+\multicolumn{3}{l}{$\quad l_{wend}\;$ \textcolor{black}{(fresh label)}}\\
+\multicolumn{3}{l}{$\quad (is, E') = \text{compile}(cs_1, E)$}\\
+\multicolumn{3}{l}{$\quad(l_{wbegin}:$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;\text{compile}(b, E, l_{wend})$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;is$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{wbegin}$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;l_{wend}:, E')$}\\
+\end{tabular}}
+\end{center}
+
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Next Compiler Phases\end{tabular}}
+
+\begin{itemize}
+\item assembly $\Rightarrow$ byte code (class file)
+\item labels $\Rightarrow$ absolute or relative jumps\bigskip\bigskip
+\item \texttt{javap} is a disassembler for class files
\end{itemize}
\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiled Code\end{tabular}}
+
+\begin{center}
+\begin{tikzpicture}
+\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
+\addplot+[smooth] file {compiled.data};
+\end{axis}
+\end{tikzpicture}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiler vs.~Interpreter\end{tabular}}
+
+\begin{center}
+\begin{tikzpicture}
+\begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs,
+ xlabel=n,
+ enlargelimits=0.05,
+ ybar interval=0.7, legend style=small]
+\addplot file {interpreted2.data};
+\addplot file {compiled2.data};
+%\legend{interpreted, compiled}
+\end{axis}
+\end{tikzpicture}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{Backend}
+
+\begin{center}
+\begin{tikzpicture}
+\node (rexp) {\bl{\bf Lexer}};
+\node (nfa) [right=of rexp] {\bl{\bf Parser}};
+\node (dfa) [right=of nfa] {\bl{\begin{tabular}{c}\bf Optimizations\end{tabular}}};
+\path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}token\\[-1mm]
+sequence\end{tabular}} (nfa);
+\node (final) [below=of dfa] {\bl{\begin{tabular}{c}\bf Machine Code/\\\bf Byte Code\end{tabular}}};
+\path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}parse\\[-1mm] tree
+\end{tabular}}(dfa);
+\path[->, red, line width=2mm] (dfa) edge (final);
+\end{tikzpicture}\\
+\end{center}
+
+\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}What is Next\end{tabular}}
+
+\begin{itemize}
+\item register spilling
+\item dead code removal
+\item loop optimisations
+\item instruction selection
+\item type checking
+\item concurrency
+\item fuzzy testing
+\item verification\bigskip\\
+
+\item GCC, LLVM, tracing JITs
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
\end{document}
--- a/slides/slides08.tex Tue Nov 20 13:23:51 2018 +0000
+++ b/slides/slides08.tex Tue Nov 20 13:37:40 2018 +0000
@@ -1,14 +1,28 @@
\documentclass[dvipsnames,14pt,t]{beamer}
+\usepackage{xcolor}
\usepackage{../slides}
\usepackage{../langs}
\usepackage{../data}
\usepackage{../graphics}
\usepackage{../grammar}
-% beamer stuff
-\renewcommand{\slidecaption}{CFL 07, King's College London}
+\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -17,80 +31,26 @@
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-2mm]
- \LARGE Formal Languages (7)\\[3mm]
+ \LARGE Formal Languages (8)\\[3mm]
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
- Office: & N\liningnums{7.07} (North Wing, Bush House)\\
- Slides: & KEATS (also homework is there)\\
+ Office: & N7.07 (North Wing, Bush House)\\
+ Slides: & KEATS (also home work is there)\\
\end{tabular}
\end{center}
\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{Bird's Eye View}
-
-\begin{center}
-\begin{tikzpicture}
-\node (rexp) {\bl{\bf Lexer}};
-\node (nfa) [right=of rexp] {\bl{\bf Parser}};
-\node (dfa) [right=of nfa]
- {\bl{\begin{tabular}{c}\bf Machine Code/\\\bf Java Byte Code\end{tabular}}};
-\path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}token\\[-1mm]
-sequence\end{tabular}} (nfa);
-\path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}parse\\[-1mm] tree\end{tabular}}(dfa);
-\end{tikzpicture}\\
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\begin{textblock}{10}(0.5,0.5)
- \LARGE
- \fontspec{Hoefler Text Black}
- \textcolor{ProcessBlue}{JVM\\ Code}
- \\[12mm]
-
- \normalsize
- Jasmin\\
- Krakatau\\
- ASM lib
-\end{textblock}
-
-
-\fontsize{8}{10}\selectfont
-%\footnotesize
-\mbox{}\\[-8mm]\mbox{}
-
-\begin{columns}
-\begin{column}{2cm}
-\lstinputlisting[numbers=none]{../progs/appHa.j}
-\end{column}
-
-\begin{column}{2cm}
-\lstinputlisting[numbers=none]{../progs/appHb.j}
-\end{column}
-
-\end{columns}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
\begin{center}
\bl{\begin{tabular}{@{}lcl@{}}
-\\[-12mm]
\meta{Stmt} & $::=$ & $\texttt{skip}$\\
& $|$ & \textit{Id}\;\texttt{:=}\;\meta{AExp}\\
& $|$ & \texttt{if}\; \meta{BExp} \;\texttt{then}\; \meta{Block} \;\texttt{else}\; \meta{Block}\\
@@ -109,141 +69,21 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Fibonacci Numbers\end{tabular}}
-
-\mbox{}\\[-18mm]\mbox{}
-
-{\lstset{language=While}\fontsize{10}{12}\selectfont
-\texttt{\lstinputlisting{../progs/fib.while}}}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Interpreter}
-
-\begin{center}
-\bl{\begin{tabular}{@{}lcl@{}}
-$\text{eval}(n, E)$ & $\dn$ & $n$\\
-$\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\
-$\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\
-$\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\
-$\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\
-$\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\
-$\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\
-$\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\
-\end{tabular}}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Interpreter (2)}
-
-\begin{center}
-\bl{\begin{tabular}{@{}lcl@{}}
-$\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\
-$\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\
-\multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\
-\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\;
-\text{eval}(cs_1,E)$}\\
-\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\
-\multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\
-\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\
-\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\;
-\text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\
-\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\
-$\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\
-\end{tabular}}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Test Program}
-
-\mbox{}\\[-18mm]\mbox{}
-
-{\lstset{language=While}\fontsize{10}{12}\selectfont
-\texttt{\lstinputlisting{../progs/loops.while}}}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\fontsize{7}{9}\selectfont
-
-
-\begin{columns}
-\begin{column}{7cm}
-\lstinputlisting[numbers=none]{../progs/appHa.j}
-\end{column}
-
-\begin{column}{7cm}
-\lstinputlisting[numbers=none]{../progs/appHb.j}
-\end{column}
-\end{columns}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Interpreted Code}
-
-\begin{center}
-\begin{tikzpicture}
-\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
-\addplot+[smooth] file {interpreted.data};
-\end{axis}
-\end{tikzpicture}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Java Virtual Machine}
-
-\begin{itemize}
-\item introduced in 1995
-\item is a stack-based VM (like Postscript, CLR of .Net)
-\item contains a JIT compiler
-\item many languages take advantage of JVM's infrastructure (JRE)
-\item is garbage collected $\Rightarrow$ no buffer overflows
-\item some languages compiled to the JVM: Scala, Clojure\ldots
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t,fragile]
\frametitle{Compiling AExps}
-For example \liningnums{\bl{$1 + ((2 * 3) + (4 - 3))$}}:\medskip
-
+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}}
+\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{column}{.3\textwidth}
\begin{lstlisting}[language=JVMIS,numbers=none]
ldc 1
ldc 2
@@ -263,261 +103,30 @@
stack-machine
\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t,fragile]
-\frametitle{Compiling AExps}
-
-\liningnums{\textbf{\Large\bl{1 + 2 + 3}}}
-
-\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm]
-ldc 1
-ldc 2
-iadd
-ldc 3
-iadd
-\end{lstlisting}
-
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t,fragile]
-\frametitle{Compiling AExps}
-
-\liningnums{\textbf{\Large\bl{1 + (2 + 3)}}}
-
-\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm]
-ldc 1
-ldc 2
-ldc 3
-iadd
-iadd
-\end{lstlisting}
-\bigskip\pause
-\vfill
-
-\textcolor{codepurple}{\textbf{\texttt{dadd}}},
-\textcolor{codepurple}{\textbf{\texttt{fadd}}},
-\textcolor{codepurple}{\textbf{\texttt{ladd}}}, \ldots
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Compiling AExps}
-
-\begin{center}
-\bl{\begin{tabular}{@{}lcl@{}}
-$\text{compile}(n)$ & $\dn$ & $\text{ldc}\;n$\\
-$\text{compile}(a_1 + a_2)$ & $\dn$\\
-\multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\;\text{compile}(a_2)\;@\; \text{iadd}$}\smallskip\\
-$\text{compile}(a_1 - a_2)$ & $\dn$\\
-\multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{isub}$}\smallskip\\
-$\text{compile}(a_1 * a_2)$ & $\dn$\\
-\multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{imul}$}\smallskip\\
-\end{tabular}}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t,fragile]
-\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}
-
-\liningnums{\textbf{\Large\bl{1 $+$ 2 $*$ 3 $+$ (4 $-$ 3)}}}
-
-\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm]
-ldc 1
-ldc 2
-ldc 3
-imul
-ldc 4
-ldc 3
-isub
-iadd
-iadd
-\end{lstlisting}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Variables}
-\liningnums{\textbf{\Large\bl{x $:=$ 5 $+$ y $*$ 2}}}\bigskip\pause
-
-\begin{itemize}
-\item lookup: \bl{$\textcolor{codepurple}{\textbf{\texttt{iload}}}\; index$}
-\item store: \bl{$\textcolor{codepurple}{\textbf{\texttt{istore}}}\; index$}
-\end{itemize}\bigskip\pause
-
-while compilating we have to maintain a map between our identifiers and the
-Java bytecode indices
-
-\begin{center}
-\bl{$\text{compile}(a, E)$}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Compiling AExps}
-
-\begin{center}
-\bl{\begin{tabular}{@{}lcl@{}}
-$\text{compile}(n, E)$ & $\dn$ & $\text{ldc}\;n$\\
-$\text{compile}(a_1 + a_2, E)$ & $\dn$\\
-\multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\;\text{compile}(a_2, E)\;@\; \text{iadd}$}\smallskip\\
-$\text{compile}(a_1 - a_2, E)$ & $\dn$\\
-\multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{isub}$}\smallskip\\
-$\text{compile}(a_1 * a_2, E)$ & $\dn$\\
-\multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{imul}$}\bigskip\\
-$\text{compile}(x, E)$ & $\dn$ & $\text{iload}\;E(x)$\\
-\end{tabular}}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c, fragile]
-\frametitle{Mathematical Functions}
-
-Compilation of some mathematical functions:
-
-\begin{center}
-\begin{tabular}{lcl}
-\texttt{Aop("+", a1, a2)} & $\Rightarrow$ & \texttt{...iadd}\\
-\texttt{Aop("-", a1, a2)} & $\Rightarrow$ & \texttt{...isub}\\
-\texttt{Aop("*", a1, a2)} & $\Rightarrow$ & \texttt{...imul}\\
-\texttt{Aop("/", a1, a2)} & $\Rightarrow$ & \texttt{...idiv}\\
-\texttt{Aop("\%", a1, a2)} & $\Rightarrow$ & \texttt{...irem}\\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Compiling Statements}
-
-We return a list of instructions and an environment for the
-variables
-
-\begin{center}
-\bl{\begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
-$\text{compile}(\text{skip}, E)$ & $\dn$ & $(\textit{Nil}, E)$\bigskip\\
-$\text{compile}(x := a, E)$ & $\dn$\\
-\multicolumn{3}{l}{$(\text{compile}(a, E) \;@\;\text{istore}\;index, E(x\mapsto index))$}\\
-\end{tabular}}
-\end{center}\medskip
-
-where \bl{$index$} is \bl{$E(x)$} if it is already defined,
-or if it is not, then the largest index not yet seen
-
-\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
-\frametitle{Compiling Assignments}
-
-\liningnums{\textbf{\Large\bl{x $:=$ x $+$ 1}}}
+\frametitle{Compiling AExps}
-\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm]
-iload /*@\bl{$n_x$}@*/
-ldc 1
-iadd
-istore /*@\bl{$n_x$}@*/
-\end{lstlisting}\medskip
-
-where \bl{$n_x$} is the index corresponding to the variable~\bl{$x$}
+\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}[t]
-\frametitle{Compiling Ifs}
-
-{\Large\bl{$\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2$}}\bigskip\bigskip
-
-\onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:}
-
-\begin{center}
-\begin{tikzpicture}[node distance=2mm and 4mm,
- block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},
- point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},
- skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]
-\node (A1) [point] {};
-\node (b) [block, right=of A1] {code of \bl{$b$}};
-\node (A2) [point, right=of b] {};
-\node (cs1) [block, right=of A2] {code of \bl{$cs_1$}};
-\node (A3) [point, right=of cs1] {};
-\node (cs2) [block, right=of A3] {code of \bl{$cs_2$}};
-\node (A4) [point, right=of cs2] {};
-
-\only<2>{
-\draw (A1) edge [->, red, line width=1mm] (b);
-\draw (b) edge [->, red, line width=1mm] (cs1);
-\draw (cs1) edge [->, red, line width=1mm] (A3);
-\draw (A3) edge [->,skip loop] (A4);
-\node [below=of cs2] {\raisebox{-5mm}{\small{}jump}};}
-\only<3>{
-\draw (A1) edge [->, red, line width=1mm] (b);
-\draw (b) edge [->, red, line width=1mm] (A2);
-\draw (A2) edge [skip loop] (A3);
-\draw (A3) edge [->, red, line width=1mm] (cs2);
-\draw (cs2) edge [->,red, line width=1mm] (A4);
-\node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};}
-\end{tikzpicture}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t,fragile]
-\frametitle{Conditional Jumps}
-
-\begin{minipage}{1.1\textwidth}
-\begin{itemize}
-\item \textcolor{codepurple}{\textbf{\texttt{if\_icmpeq}}} \bl{$label$}
- if two ints are equal, then jump\medskip
-\item \textcolor{codepurple}{\textbf{\texttt{if\_icmpne}}} \bl{$label$}
- if two ints aren't equal, then jump\medskip
-\item \textcolor{codepurple}{\textbf{\texttt{if\_icmpge}}} \bl{$label$}
- if one int is greater or equal then another, then jump
-\item[]\ldots
-\end{itemize}
-\end{minipage}\pause
-
-\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=2cm]
-/*@\bl{$L_1$:}@*/
- if_icmpeq /*@\bl{$L_2$}@*/
- iload 1
- ldc 1
- iadd
- if_icmpeq /*@\bl{$L_1$}@*/
-/*@\bl{$L_2$:}@*/
-\end{lstlisting}
-
-
-\begin{textblock}{3.5}(11,12)
-\only<3>{labels must be unique}
-\end{textblock}
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
@@ -545,156 +154,10 @@
\end{lstlisting}
\end{center}
-\begin{tikzpicture}[remember picture,overlay]
- \draw[->,very thick] (A) edge [->,to path={-- ++(10mm,0mm)
+\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}[t]
-\frametitle{Compiling BExps}
-
-{\Large\bl{$a_1 = a_2$}}
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$\text{compile}(a_1 = a_2, E, lab)$ & $\dn$\\
-\multicolumn{3}{l}{$\quad\text{compile}(a_1, E) \;@\;\text{compile}(a_2, E)\;@\; \text{if\_icmpne}\;lab$}
-\end{tabular}}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c, fragile]
-\frametitle{Boolean Expressions}
-
-Compilation of boolean expressions:
-
-\begin{center}
-\begin{tikzpicture}[node distance=2mm and 4mm,
- block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},
- point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},
- skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]
-\node (A1) [point] {};
-\node (b) [block, right=of A1] {code of \bl{$b$}};
-\node (A2) [point, right=of b] {};
-\node (cs1) [block, right=of A2] {code of \bl{$cs_1$}};
-\node (A3) [point, right=of cs1] {};
-\node (cs2) [block, right=of A3] {code of \bl{$cs_2$}};
-\node (A4) [point, right=of cs2] {};
-
-\only<1>{
-\draw (A1) edge [->, red, line width=1mm] (b);
-\draw (b) edge [->, red, line width=1mm] (A2);
-\draw (A2) edge [skip loop] (A3);
-\draw (A3) edge [->, red, line width=1mm] (cs2);
-\draw (cs2) edge [->,red, line width=1mm] (A4);
-\node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};}
-\end{tikzpicture}
-\end{center}
-
-\begin{center}
-\begin{tabular}{lcl}
-\texttt{Bop("==", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpne...}\\
-\texttt{Bop("!=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpeq...}\\
-\texttt{Bop("<", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpge...}\\
-\texttt{Bop("<=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpgt...}\\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Compiling Ifs}
-
-{\Large\bl{if $b$ then $cs_1$ else $cs_2$}}
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$\text{compile}(\text{if}\;b\;\text{then}\; cs_1\;\text{else}\; cs_2, E)$ & $\dn$\\
-\multicolumn{3}{l}{$\quad l_{ifelse}\;$ \textcolor{black}{(fresh label)}}\\
-\multicolumn{3}{l}{$\quad l_{ifend}\;$ \textcolor{black}{(fresh label)}}\\
-\multicolumn{3}{l}{$\quad (is_1, E') = \text{compile}(cs_1, E)$}\\
-\multicolumn{3}{l}{$\quad (is_2, E'') = \text{compile}(cs_2, E')$}\\
-\multicolumn{3}{l}{$\quad(\text{compile}(b, E, l_{ifelse})$}\\
-\multicolumn{3}{l}{$\quad\phantom{(}@\;is_1$}\\
-\multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{ifend}$}\\
-\multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifelse}:$}\\
-\multicolumn{3}{l}{$\quad\phantom{(}@\;is_2$}\\
-\multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifend}:, E'')$}\\
-\end{tabular}}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Compiling Whiles}
-
-{\Large\bl{$\text{while}\;b\;\text{do}\;cs$}}\bigskip\bigskip
-
-\onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:}
-
-\begin{center}
-\begin{tikzpicture}[node distance=2mm and 4mm,
- block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},
- point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},
- skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]
-\node (A0) [point, left=of A1] {};
-\node (A1) [point] {};
-\node (b) [block, right=of A1] {code of \bl{$b$}};
-\node (A2) [point, right=of b] {};
-\node (cs1) [block, right=of A2] {code of \bl{$cs$}};
-\node (A3) [point, right=of cs1] {};
-\node (A4) [point, right=of A3] {};
-
-\only<2>{
-\draw (A0) edge [->, red, line width=1mm] (b);
-\draw (b) edge [->, red, line width=1mm] (cs1);
-\draw (cs1) edge [->, red, line width=1mm] (A3);
-\draw (A3) edge [->,skip loop] (A1);}
-\only<3>{
-\draw (A0) edge [->, red, line width=1mm] (b);
-\draw (b) edge [->, red, line width=1mm] (A2);
-\draw (A2) edge [skip loop] (A3);
-\draw (A3) edge [->, red, line width=1mm] (A4);}
-\end{tikzpicture}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Compiling Whiles}
-
-{\Large\bl{while $b$ do $cs$}}
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$\text{compile}(\text{while}\; b\; \text{do} \;cs, E)$ & $\dn$\\
-\multicolumn{3}{l}{$\quad l_{wbegin}\;$ \textcolor{black}{(fresh label)}}\\
-\multicolumn{3}{l}{$\quad l_{wend}\;$ \textcolor{black}{(fresh label)}}\\
-\multicolumn{3}{l}{$\quad (is, E') = \text{compile}(cs_1, E)$}\\
-\multicolumn{3}{l}{$\quad(l_{wbegin}:$}\\
-\multicolumn{3}{l}{$\quad\phantom{(}@\;\text{compile}(b, E, l_{wend})$}\\
-\multicolumn{3}{l}{$\quad\phantom{(}@\;is$}\\
-\multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{wbegin}$}\\
-\multicolumn{3}{l}{$\quad\phantom{(}@\;l_{wend}:, E')$}\\
-\end{tabular}}
-\end{center}
+ -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (D.east);
\end{tikzpicture}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -729,13 +192,11 @@
\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}
+ -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (LD.east);
\end{tikzpicture}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Compiling Writes}
@@ -760,9 +221,9 @@
\end{lstlisting}
\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Compiling Main}
@@ -793,101 +254,532 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Next Compiler Phases\end{tabular}}
+\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{itemize}
-\item assembly $\Rightarrow$ byte code (class file)
-\item labels $\Rightarrow$ absolute or relative jumps\bigskip\bigskip
-\item \texttt{javap} is a disassembler for class files
-\end{itemize}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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{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}}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% Almost what is implemented - Exp ; Exp is left-recursive
+%
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Compiled Code\end{tabular}}
+\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{Idea}
+
+Compile \texttt{exp} 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{center}
-\begin{tikzpicture}
-\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
-\addplot+[smooth] file {compiled.data};
-\end{axis}
-\end{tikzpicture}
-\end{center}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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
+
-\end{frame}}
+\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Compiler vs.~Interpreter\end{tabular}}
+\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}
-\begin{center}
-\begin{tikzpicture}
-\begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs,
- xlabel=n,
- enlargelimits=0.05,
- ybar interval=0.7, legend style=small]
-\addplot file {interpreted2.data};
-\addplot file {compiled2.data};
-%\legend{interpreted, compiled}
-\end{axis}
-\end{tikzpicture}
-\end{center}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c, fragile]
+\frametitle{Stack Estimation}
+\small
+\mbox{}\\[-15mm]
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{Backend}
+\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{center}
-\begin{tikzpicture}
-\node (rexp) {\bl{\bf Lexer}};
-\node (nfa) [right=of rexp] {\bl{\bf Parser}};
-\node (dfa) [right=of nfa] {\bl{\begin{tabular}{c}\bf Optimizations\end{tabular}}};
-\path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}token\\[-1mm]
-sequence\end{tabular}} (nfa);
-\node (final) [below=of dfa] {\bl{\begin{tabular}{c}\bf Machine Code/\\\bf Byte Code\end{tabular}}};
-\path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}parse\\[-1mm] tree
-\end{tabular}}(dfa);
-\path[->, red, line width=2mm] (dfa) edge (final);
-\end{tikzpicture}\\
-\end{center}
+\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{Factorial}
-\end{frame}}
+\begin{textblock}{7}(1,1.8)\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}What is Next\end{tabular}}
+\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}[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 register spilling
-\item dead code removal
-\item loop optimisations
-\item instruction selection
-\item type checking
-\item concurrency
-\item fuzzy testing
-\item verification\bigskip\\
-
-\item GCC, LLVM, tracing JITs
+\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}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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}