# HG changeset patch # User Christian Urban # Date 1542721060 0 # Node ID 3db4970ad0aa87b2d5c859d0d1dbec9cb8c07e74 # Parent 3f4fc76dab2fafeeadd68984ba7cb600d71764c2 updated diff -r 3f4fc76dab2f -r 3db4970ad0aa slides/slides07.pdf Binary file slides/slides07.pdf has changed diff -r 3f4fc76dab2f -r 3db4970ad0aa slides/slides07.tex --- 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{ \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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\begin{frame}[c] - -\mbox{\lstinputlisting[language=while]{../progs/fib.while}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\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{ -\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{ \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{ \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{ +\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{ \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 ()V + aload_0 + invokenonvirtual java/lang/Object/()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{ +\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{ +\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{ +\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{ +\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{ +\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} diff -r 3f4fc76dab2f -r 3db4970ad0aa slides/slides08.pdf Binary file slides/slides08.pdf has changed 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}