
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<presentation>{
 \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<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Parse Trees\end{tabular}}
+
+\mbox{\lstinputlisting[language=while]{../progs/fib.while}}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}An Interpreter\end{tabular}}
 
 \begin{center}
-\bl{\begin{tabular}{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<presentation>{
+\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<presentation>{
 \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<presentation>{
+\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<presentation>{
-\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<presentation>{
 \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}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   




