
diff -r 373cf55a3ca5 -r 49c0beef79a1 slides09.tex
--- a/slides09.tex	Sat Nov 24 07:08:51 2012 +0000
+++ b/slides09.tex	Sat Nov 24 14:58:27 2012 +0000
@@ -20,6 +20,8 @@
 \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
@@ -57,6 +59,7 @@
   morestring=[b]"""
 }
 
+
 \lstset{language=Scala,
 	basicstyle=\ttfamily,
 	keywordstyle=\color{javapurple}\bfseries,
@@ -71,6 +74,29 @@
 	showspaces=false,
 	showstringspaces=false}
 
+\lstdefinelanguage{while}{
+  morekeywords={if,then,else,while,do,true,false},
+  otherkeywords={=,!=,:=,<,>},
+  sensitive=true,
+  morecomment=[n]{/*}{*/},
+}
+
+
+\lstset{language=While,
+	basicstyle=\ttfamily,
+	keywordstyle=\color{javapurple}\bfseries,
+	stringstyle=\color{javagreen},
+	commentstyle=\color{javagreen},
+	morecomment=[s][\color{javadocblue}]{/**}{*/},
+	numbers=left,
+	numberstyle=\tiny\color{black},
+	stepnumber=1,
+	numbersep=10pt,
+	tabsize=2,
+	showspaces=false,
+	showstringspaces=false}
+
+
 % beamer stuff 
 \renewcommand{\slidecaption}{AFL 09, King's College London, 28.~November 2012}
 \newcommand{\bl}[1]{\textcolor{blue}{#1}}       
@@ -78,48 +104,18 @@
 
 
 % The data files, written on the first run.
-\begin{filecontents}{s-grammar1.data}
-1 0.01152
-51 0.07973
-101 0.09726
-151 0.09320
-201 0.10010
-251 0.16997
-301 0.26662
-351 0.46118
-401 0.62516
-451 0.87247
-501 1.16334
-551 1.71152
-601 2.10958
-651 2.44360
-701 2.98488
-751 3.50326
-801 4.11036
-851 4.93394
-901 5.77465
-951 7.39123
+\begin{filecontents}{compiled.data}
+1 0.0207
+5000 0.0217
+10000 0.0297
+50000 0.1034
+100000 0.3873
+500000 1.27949
+1000000 5. 35424
 \end{filecontents}
 
-\begin{filecontents}{s-grammar2.data}
-1 0.01280
-2 0.00064
-3 0.00173
-4 0.00355
-5 0.00965
-6 0.02674
-7 0.06953
-8 0.11166
-9 0.18707
-10 0.09189
-11 0.12724
-12 0.24337
-13 0.59304
-14 1.53594
-15 4.01195
-16 10.73582
-17 29.51587
-#18 73.14163
+\begin{filecontents}{interpreted.data}
+
 \end{filecontents}
 
 
@@ -144,45 +140,54 @@
   \end{tabular}
   \end{center}
 
-
 \end{frame}}
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Building a ``Web Browser''\end{tabular}}
+\frametitle{\begin{tabular}{c}While-Language\end{tabular}}
 
-Using a lexer: assume the following regular expressions
 
 \begin{center}
-\bl{\begin{tabular}{lcl}
-$SY\!M$ & $\dn$ & $(\text{a}..\text{zA}..\text{Z0}..\text{9}..)$\\
-$W\!O\!RD$ & $\dn$ & $SY\!M^+$\\
-$BT\!AG$ & $\dn$ & $<\!W\!O\!RD\!>$\\
-$ET\!AG$ & $\dn$ & $<\!/W\!O\!RD\!>$\\
-$W\!HIT\!E$ & $\dn$ & $\texttt{" "} + \texttt{"}\slash{}n\texttt{"}$\\
+\bl{\begin{tabular}{@{}lcl@{}}
+$Stmt$ & $\rightarrow$ &  $\text{skip}$\\
+              & $|$ & $Id := AExp$\\
+              & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\
+              & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\\
+               & $|$ & $\alert{\text{write}\; Id}$\medskip\\
+$Stmts$ & $\rightarrow$ &  $Stmt \;\text{;}\; Stmts$\\
+              & $|$ & $Stmt$\medskip\\
+$Block$ & $\rightarrow$ &  $\{ Stmts \}$\\
+                & $|$ & $Stmt$\medskip\\
+$AExp$ & $\rightarrow$ & \ldots\\
+$BExp$ & $\rightarrow$ & \ldots\\
 \end{tabular}}
 \end{center}
 
+
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}}
+\frametitle{\begin{tabular}{c}Fibonacci Numbers\end{tabular}}
+
+\mbox{}\\[-18mm]\mbox{}
+
+{\lstset{language=While}\fontsize{10}{12}\selectfont
+\texttt{\lstinputlisting{app9.while}}}
 
-\begin{itemize}
-\item the text should be formatted consistently up to a specified width, say 60 characters 
-\item potential linebreaks are inserted by the formatter (not the input)
-\item repeated whitespaces are ``condensed'' to a single whitepace
-\item \bl{$<\!p\!>$} \bl{$<\!\slash{}p\!>$}  start/end paragraph
-\item \bl{$<\!b\!>$} \bl{$<\!\slash{}b\!>$}  start/end bold
-\item \bl{$<\!red\!>$} \bl{$<\!\slash{}red\!>$}  start/end red (cyan, etc)
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Interpreter\end{tabular}}
 
 
-\end{itemize}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -497,87 +502,39 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Successful Parses\end{tabular}}
-
-\begin{itemize}
-\item input: string
-\item output: \alert{set of} (output\_type, string)
-\end{itemize}\bigskip
-
-a parse is successful whenever the input has been
-fully ``consumed'' (that is the second component is empty)
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-{\lstset{language=Scala}\fontsize{10}{12}\selectfont
-\texttt{\lstinputlisting{app7.scala}}}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-{\lstset{language=Scala}\fontsize{10}{12}\selectfont
-\texttt{\lstinputlisting{app7.scala}}}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-{\lstset{language=Scala}\fontsize{10}{12}\selectfont
-\texttt{\lstinputlisting{app8.scala}}}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Two Grammars\end{tabular}}
-
-Which languages are recognised by the following two grammars?
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiled vs.~Interpreted Code\end{tabular}}
 
 \begin{center}
-\bl{\begin{tabular}{lcl}
-$S$ & $\rightarrow$ &  $1 \cdot S \cdot S$\\
-        & $|$ & $\epsilon$
-\end{tabular}}
-\end{center}\bigskip
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$U$ & $\rightarrow$ &  $1 \cdot U$\\
-        & $|$ & $\epsilon$
-\end{tabular}}
+\begin{tikzpicture}
+\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=mins]
+\addplot file {compiled.data};
+\end{axis}
+\end{tikzpicture}
 \end{center}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[t]
-\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}
+\frametitle{\begin{tabular}{c}Compiled vs.~Interpreted Code\end{tabular}}
 
 \mbox{}\\[-25mm]\mbox{}
 
 \begin{center}
-\begin{tikzpicture}[y=.2cm, x=.009cm]
+\begin{tikzpicture}[y=.4cm, x=.00000009cm]
  	%axis
-	\draw (0,0) -- coordinate (x axis mid) (1000,0);
-    	\draw (0,0) -- coordinate (y axis mid) (0,30);
+	\draw (0,0) -- coordinate (x axis mid) (5,0);
+    	\draw (0,0) -- coordinate (y axis mid) (0,5);
     	%ticks
-    	\foreach \x in {0, 20, 100, 200,...,1000}
+    	\foreach \x in {0, 1000,...,10000}
      		\draw (\x,1pt) -- (\x,-3pt)
-			node[anchor=north] {\small \x};
-    	\foreach \y in {0,5,...,30}
+			node[anchor=north] {\small \x{}00};
+    	\foreach \y in {0,0.5,1, ..., 5.5}
      		\draw (1pt,\y) -- (-3pt,\y) 
      			node[anchor=east] {\small\y}; 
 	%labels      
@@ -585,88 +542,29 @@
 	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};
 
 	%plots
-	\draw[color=blue] plot[mark=*, mark options={fill=white}] 
-		file {s-grammar1.data};
-         \only<2->{\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 
-                  file {s-grammar2.data};}
+	%\draw[color=blue] plot[mark=*, mark options={fill=white}] 
+	%	file {compiled.data};
+         %\only<2->{\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 
+          %        file {interpreted.data};}
 	%legend
-	\begin{scope}[shift={(400,20)}] 
-	\draw[color=blue] (0,0) -- 
-		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 
-		node[right]{\small unambiguous};
-	\only<2->{\draw[yshift=\baselineskip, color=red] (0,0) -- 
-                plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
-                node[right]{\small ambiguous};}  
-	\end{scope}
+	%\begin{scope}[shift={(400,20)}] 
+	%\draw[color=blue] (0,0) -- 
+	%	plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 
+	%	node[right]{\small unambiguous};
+	%\only<2->{\draw[yshift=\baselineskip, color=red] (0,0) -- 
+          %      plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+          %      node[right]{\small ambiguous};}  
+	%\end{scope}
 \end{tikzpicture}
 \end{center}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}What about Left-Recursion?\end{tabular}}
-
-\begin{itemize}
-\item we record when we recursively called a parser\bigskip
-\item whenever the is a recursion, the parser must have consumed something --- so
-we can decrease the input string/list of token by one (at the end)
-\end{itemize}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}While-Language\end{tabular}}
 
 
-\begin{center}
-\bl{\begin{tabular}{@{}lcl@{}}
-$Stmt$ & $\rightarrow$ &  $\text{skip}$\\
-              & $|$ & $Id := AExp$\\
-              & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\
-              & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\
-$Stmts$ & $\rightarrow$ &  $Stmt \;\text{;}\; Stmts$\\
-              & $|$ & $Stmt$\medskip\\
-$Block$ & $\rightarrow$ &  $\{ Stmts \}$\\
-                & $|$ & $Stmt$\medskip\\
-$AExp$ & $\rightarrow$ & \ldots\\
-$BExp$ & $\rightarrow$ & \ldots\\
-\end{tabular}}
-\end{center}
 
 
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\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}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
 \end{document}
 
 %%% Local Variables:  




