diff -r 3f4fc76dab2f -r 3db4970ad0aa slides/slides08.tex --- 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{ -\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{ -\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{ -\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{ -\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{ -\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}