--- 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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%