diff -r 9471a0325773 -r 12ef150273ce slides/slides07.tex --- a/slides/slides07.tex Tue Nov 12 22:54:41 2013 +0000 +++ b/slides/slides07.tex Wed Nov 13 06:40:37 2013 +0000 @@ -20,6 +20,7 @@ \usetikzlibrary{calc} \usetikzlibrary{plotmarks} \usepackage{graphicx} +\usepackage{pgfplots} \definecolor{javared}{rgb}{0.6,0,0} % for strings \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments @@ -71,8 +72,32 @@ showspaces=false, showstringspaces=false} +\lstdefinelanguage{While}{ + morekeywords={while, if, then. else, read, write}, + otherkeywords={=>,<-,<\%,<:,>:,\#,@}, + sensitive=true, + morecomment=[l]{//}, + morecomment=[n]{/*}{*/}, + morestring=[b]", + morestring=[b]', + morestring=[b]""" +} + + \setmonofont{Consolas} +\begin{filecontents}{interpreted.data} +%1 0.00503 +200 1.005863 +400 7.8296765 +500 15.43106 +600 27.2321885 +800 65.249271 +1000 135.4493445 +1200 232.134097 +1400 382.527227 +\end{filecontents} + % beamer stuff \renewcommand{\slidecaption}{AFL 07, King's College London, 13.~November 2013} \newcommand{\bl}[1]{\textcolor{blue}{#1}} @@ -424,9 +449,9 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Parse Trees\end{tabular}} + \begin{center} -\begin{tabular}{@{}lcl@{}} +\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}\\ @@ -440,7 +465,7 @@ & $|$ & \textit{Stmt}\medskip\\ \textit{AExp} & $\rightarrow$ & \ldots\\ \textit{BExp} & $\rightarrow$ & \ldots\\ -\end{tabular} +\end{tabular}} \end{center} \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -448,86 +473,109 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Parse Trees\end{tabular}} + +\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}{lcl} -$E$ & $\rightarrow$ & $F \;|\; F \cdot * \cdot F$\\ -$F$ & $\rightarrow$ & $T \;|\; T \cdot + \cdot T \;|\; T \cdot - \cdot T$\\ -$T$ & $\rightarrow$ & $num\_token \;|\; ( \cdot E \cdot )$\\ +\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}} + \begin{center} -\begin{tikzpicture}[level distance=8mm, blue] - \node {$E$} - child {node {$F$} - child {node {$T$} - child {node {(\,$E$\,)} - child {node{$F$ *{} $F$} - child {node {$T$} child {node {2}}} - child {node {$T$} child {node {3}}} - } - } - } - child {node {+}} - child {node {$T$} - child {node {(\,$E$\,)} - child {node {$F$} - child {node {$T$ +{} $T$} - child {node {3}} - child {node {4}} - } - }} - }}; -\end{tikzpicture} +\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} -\begin{textblock}{5}(1, 6.5) -\bl{\texttt{(2*3)+(3+4)}} -\end{textblock} - \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}} - -A CFG is \alert{ambiguous} if there is a string that has at least parse trees. - +\frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}} \begin{center} -\bl{\begin{tabular}{lcl} -$E$ & $\rightarrow$ & $num\_token$ \\ -$E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ -$E$ & $\rightarrow$ & $( \cdot E \cdot )$ +\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} -\bl{\texttt{1 + 2 * 3 + 4}} +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Test Program\end{tabular}} + +\mbox{}\\[-18mm]\mbox{} + +{\lstset{language=While}%%\fontsize{10}{12}\selectfont +\texttt{\lstinputlisting{../progs/loops.while}}} \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Dangling Else\end{tabular}} - -Another ambiguous grammar:\bigskip +\begin{frame}[t] +\frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}} \begin{center} -\bl{\begin{tabular}{lcl} -$E$ & $\rightarrow$ & if $E$ then $E$\\ - & $|$ & if $E$ then $E$ else $E$ \\ - & $|$ & id -\end{tabular}} -\end{center}\bigskip - -\bl{\texttt{if a then if x then y else c}} +\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}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -535,18 +583,16 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}A CFG Derivation\end{tabular}} +\frametitle{\begin{tabular}{c}Java Virtual Machine\end{tabular}} -\begin{enumerate} -\item Begin with a string with only the start symbol \bl{$S$}\bigskip -\item Replace any non-terminal \bl{$X$} in the string by the -right-hand side of some production \bl{$X \rightarrow \text{rhs}$}\bigskip -\item Repeat 2 until there are no non-terminals -\end{enumerate} - -\begin{center} -\bl{$S \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots $} -\end{center} +\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 compile to the JVM: Scala, Clojure\ldots +\end{itemize} \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%