diff -r dcd4688690ce -r 96a99237fa42 slides/slides01.tex
--- a/slides/slides01.tex	Sun Sep 21 23:23:43 2014 +0100
+++ b/slides/slides01.tex	Mon Sep 22 01:57:59 2014 +0100
@@ -49,77 +49,119 @@
 
 
 \end{frame}
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
+\frametitle{The Goal of this Course}
 
-\begin{textblock}{1}(2,5)
-\begin{tabular}{c}
-\includegraphics[scale=0.15]{pics/servers.png}\\[-2mm]
-\small Server
-\end{tabular}
-\end{textblock}
+\begin{center}
+  \begin{tikzpicture}[scale=1,
+                      node/.style={
+                      rectangle,rounded corners=3mm,
+                      very thick,draw=black!50,minimum height=18mm, minimum width=20mm,
+                      top color=white,bottom color=black!20}]
+
+  \node at (3.05, 1.8) {\Large\bf A Compiler};
+
+  \node (0) at (-2.3,0) {}; 
+  
+  \node (A) at (0,0)  [node] {};
+  \node [below right] at (A.north west) {lexer};
+
+  \node (B) at (3,0)  [node] {};
+  \node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser};
 
-\begin{textblock}{1}(5.6,4)
-  \begin{tikzpicture}[scale=1.1]
-  \draw[white] (0,1) node (X) {};
-  \draw[white] (2,1) node (Y) {};
-   \draw[white] (0,0) node (X1) {};
-  \draw[white] (2,0) node (Y1) {};
-   \draw[white] (0,-1) node (X2) {};
-  \draw[white] (2,-1) node (Y2) {};
-  \draw[red, <-, line width = 2mm] (X) -- (Y);
-  \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {};
-  \draw[red, ->, line width = 2mm] (X1) -- (Y1);
-  \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X1)!.5!(Y1) $) {};
-  \draw[red, <-, line width = 2mm] (X2) -- (Y2);
-  \node [inner sep=7pt,label=above:\textcolor{black}{POST data}] at ($ (X2)!.5!(Y2) $) {};
+  \node (C) at (6,0)  [node] {};
+  \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen};
+
+  \node (1) at (8.4,0) {}; 
+
+  \draw [->,line width=4mm] (0) -- (A); 
+  \draw [->,line width=4mm] (A) -- (B); 
+  \draw [->,line width=4mm] (B) -- (C); 
+  \draw [->,line width=4mm] (C) -- (1); 
   \end{tikzpicture}
-\end{textblock}
+  \end{center}
 
+\only<2,3>{
+\begin{textblock}{1}(1,2)
+\begin{bubble}[9.8cm]
+\normalsize
+lexer input: a string\smallskip\\
+\hspace{5mm}\code{"read(n);"}\medskip\\
+lexer output: a sequence of tokens\smallskip\\
+\hspace{5mm}\code{key(read); lpar; id(n); rpar; semi}
+\end{bubble}
+\end{textblock}}
 
-\begin{textblock}{1}(9,5.5)
+\only<3>{
+\begin{textblock}{1}(6,7.8)
 \begin{tabular}{c}
-\includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm]
-\small Browser
+\includegraphics[scale=0.2]{../pics/rosetta.jpg}\\[-2mm]
+\footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta)
 \end{tabular}
-\end{textblock}
-  
-\only<2>{  
-\begin{textblock}{10}(2,13.5)
-\begin{itemize}
-\item programming languages, compilers
-\end{itemize}
+\end{textblock}}
+
+\only<4>{
+\begin{textblock}{1}(1,1.5)
+\begin{bubble}[8.5cm]
+\normalsize
+parser input: a sequence of token\smallskip\\
+parser output: an abstract syntax tree\smallskip\\
+\footnotesize
+\hspace{2cm}\begin{tikzpicture}
+  \node {\code{read}}
+    child {node {\code{lpar}}}
+    child {node {\code{n}}}
+    child {node {\code{rpar}}};
+\end{tikzpicture}
+\end{bubble}
 \end{textblock}}
-  
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
+\only<5,6>{
+\begin{textblock}{1}(1,1.5)
+\begin{bubble}[4cm]
+\normalsize
+code generator:\smallskip\\
+\hspace{5mm}\code{istore 2}\\ 
+\hspace{5mm}\code{iload 2}\\ 
+\hspace{5mm}\code{ldc 10}\\
+\hspace{5mm}\code{isub}\\
+\hspace{5mm}\code{ifeq Label2}\\ 
+\hspace{5mm}\code{iload 2}\\
+\hspace{5mm}\code{...}\\
+\end{bubble}
+\end{textblock}}
 
-transforming strings into structured data\\[10mm]
-
-{\LARGE\bf Lexing}\medskip\\
-\hspace{5mm}(recognising ``words'')\\[6mm]
-
-{\LARGE\bf Parsing}\medskip\\
-\hspace{5mm}(recognising ``sentences'')
+\only<6>{
+\begin{textblock}{6}(8.4,7)
+\begin{bubble}[5cm]
+\mbox{\begin{tikzpicture}[scale=0.58,rounded corners=0mm]
+\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{bubble}
+\end{textblock}}
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-
-The subject is quite old:
+\frametitle{The subject is quite old}
 
 \begin{itemize}
 \item Turing Machines, 1936
-\item first compiler for COBOL, 1957 (Grace Hopper)
-\item but surprisingly research papers are still published now
+\item Regular Expressions, 1956\\
+\item The first compiler for COBOL, 1957\\ (Grace Hopper)
+\item But surprisingly research papers are still published nowadays
 \end{itemize}
 
 \begin{flushright}
@@ -127,18 +169,135 @@
 \footnotesize\textcolor{gray}{Grace Hopper}
 \end{flushright}
 
+\mbox{}\\[-10mm]
 {\footnotesize\textcolor{gray}{(she made it to David Letterman's Tonight Show, \url{http://www.youtube.com/watch?v=aZOxtURhfEU})}}
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Why Bother?}
+
+\begin{columns}[b]
+\begin{column}{.5\textwidth}
+Ruby, Python\\ and Others\bigskip\\
+\begin{tikzpicture}[y=.08cm, x=.10cm]
+   %axis
+   \draw (0,0) -- coordinate (x axis mid) (30,0);
+   \draw (0,0) -- coordinate (y axis mid) (0,30);
+   %ticks
+   \foreach \x in {0,5,...,30}
+     \draw (\x,1pt) -- (\x,-3pt) node[anchor=north] {\footnotesize\x};
+   \foreach \y in {0,5,...,30}
+     \draw (1pt,\y) -- (-3pt,\y) node[anchor=east] {\footnotesize\y}; 
+	%labels      
+	\node[below=0.6cm] at (x axis mid) {\footnotesize number of \texttt{a}s};
+	\node[rotate=90,left=1cm] at (y axis mid) {\footnotesize time in secs};
+	%plots
+	\draw[color=blue] plot[mark=*] 
+		file {re-python.data};
+	\draw[color=brown] plot[mark=triangle*] 
+		file {re-ruby.data};	 
+   %legend
+	\begin{scope}[shift={(4,20)}] 
+	\draw[color=blue] (0,0) -- 
+		plot[mark=*] (0.25,0) -- (0.5,0) 
+		node[right]{\small Python};
+	\draw[yshift=-\baselineskip, color=brown] (0,0) -- 
+		plot[mark=triangle*] (0.25,0) -- (0.5,0)
+		node[right]{\small Ruby};
+	\end{scope}	
+\end{tikzpicture}
+\end{column}
+\begin{column}{.5\textwidth}
+Us (after this course)\\\mbox{}\bigskip\\
+\begin{tikzpicture}[y=.08cm, x=.0003cm]
+ 	%axis
+	\draw (0,0) -- coordinate (x axis mid) (12000,0);
+   \draw (0,0) -- coordinate (y axis mid) (0,30);
+   %ticks
+   \foreach \x in {0,4000,...,12000}
+     	\draw (\x,1pt) -- (\x,-3pt) node[anchor=north] {\footnotesize\x};
+   \foreach \y in {0,5,...,30}
+     	\draw (1pt,\y) -- (-3pt,\y) node[anchor=east] {\footnotesize\y}; 
+	%labels      
+	\node[below=0.6cm] at (x axis mid) {\footnotesize number of \texttt{a}s};
+	\node[rotate=90, left=1cm] at (y axis mid) {\footnotesize time in secs};
+
+	%plots
+   \draw[color=green] plot[mark=square*, mark options={fill=white} ] 
+		file {re2b.data};
+	\draw[color=black] plot[mark=square*, mark options={fill=white} ] 
+		file {re3.data};	 
+\end{tikzpicture}
+\end{column}
+\end{columns}\bigskip\medskip
+
+\hspace{2cm}matching \texttt{[a?]\{n\}[a]\{n\}} against 
+$\underbrace{\texttt{a}...\texttt{a}}_n$
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Lectures 1 - 6}
+
+transforming strings into structured data\\[10mm]
+
+\alert<2>{\LARGE\bf Lexing} \onslide<2>{\hfill{}baseed on regular expressions}\medskip\\
+\hspace{5mm}(recognising ``words'')\\[6mm]
+
+{\LARGE\bf Parsing}\medskip\\
+\hspace{5mm}(recognising ``sentences'')
+
+\begin{textblock}{1}(10,9.1)
+\begin{tabular}{c}
+\includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm]
+\footnotesize Stone of Rosetta
+\end{tabular}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[t]
+\frametitle{Familiar Regular Expr.}
+\small
+\begin{center}
+\texttt{[a-z0-9\_.-]+ @ [a-z0-9.-]+ . [a-z.]\{2,6\}}
+\end{center}\smallskip
+
+\begin{center}
+\begin{tabular}{@{}lp{8.5cm}@{}}
+\pcode{re*} & matches 0 or more times\\
+\pcode{re+} & matches 1 or more times\\
+\pcode{re?} & matches 0 or 1 times\\
+\pcode{re\{n\}}	& matches exactly \pcode{n} number of times\\
+\pcode{re\{n,m\}} & matches at least \pcode{n} and at most {\tt m} times\\
+\pcode{[...]} & matches any single character inside the brackets\\
+\pcode{[^...]} & matches any single character not inside the 
+brackets\\
+\pcode{a-zA-Z} & character ranges\\
+\pcode{\\d} & matches digits; equivalent to \pcode{[0-9]}\\
+\pcode{.} & matches every character except newline\\
+\pcode{(re)}	& groups regular expressions and remembers 
+the matched text
+\end{tabular}
+\end{center}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}This Course\end{tabular}}
+\frametitle{Today}
 
 \begin{itemize}
-\item the ultimate goal is to implement a small compiler (a really small one for the JVM)\bigskip
+\item the ultimate goal is to implement a small compiler 
+(a really small one for the JVM)\bigskip
 \end{itemize}
 
 Let's start with:
@@ -149,22 +308,8 @@
 \item a web-scraper
 \end{itemize}
 
-\begin{textblock}{6}(10,7)
-\begin{tikzpicture}[scale=0.38]
-\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{textblock}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
@@ -202,6 +347,46 @@
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{textblock}{1}(2,5)
+\begin{tabular}{c}
+\includegraphics[scale=0.15]{pics/servers.png}\\[-2mm]
+\small Server
+\end{tabular}
+\end{textblock}
+
+\begin{textblock}{1}(5.6,4)
+  \begin{tikzpicture}[scale=1.1]
+  \draw[white] (0,1) node (X) {};
+  \draw[white] (2,1) node (Y) {};
+   \draw[white] (0,0) node (X1) {};
+  \draw[white] (2,0) node (Y1) {};
+   \draw[white] (0,-1) node (X2) {};
+  \draw[white] (2,-1) node (Y2) {};
+  \draw[red, <-, line width = 2mm] (X) -- (Y);
+  \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {};
+  \draw[red, ->, line width = 2mm] (X1) -- (Y1);
+  \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X1)!.5!(Y1) $) {};
+  \draw[red, <-, line width = 2mm] (X2) -- (Y2);
+  \node [inner sep=7pt,label=above:\textcolor{black}{POST data}] at ($ (X2)!.5!(Y2) $) {};
+  \end{tikzpicture}
+\end{textblock}
+
+
+\begin{textblock}{1}(9,5.5)
+\begin{tabular}{c}
+\includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm]
+\small Browser
+\end{tabular}
+\end{textblock}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+  
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Scala}
@@ -405,6 +590,29 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Strings}
+
+\ldots are lists of characters. For example \code{"hello"}
+
+\begin{center}
+\bl{$[h, e, l, l, o]$}
+\end{center}
+
+the empty string: $[]$ or \pcode{""}\bigskip\\
+
+the concatenation of two strings:
+
+\begin{center}
+\bl{$s_1 \,@\, s_2$}
+\end{center}
+
+\textit{foo $@$ bar = foobar}, \textit{baz $@\, []$ = baz}
+  
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] 
@@ -447,26 +655,6 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}This Course\end{tabular}}
-
-We will have a look at:
-
-\begin{itemize}
-\item regular expressions / regular expression matching
-\item derivatives 
-\item automata
-\item parsing
-\item grammars
-\item a small interpreter / compiler
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -493,7 +681,9 @@
 \item Accounts for 25\%. Two strands. Choose \alert{\bf one}!\bigskip
 \end{itemize}
 
-\begin{columns}[t]
\begin{column}{.5\textwidth}
\underline{\bf Strand 1}\medskip
+\begin{columns}[t]
+\begin{column}{.5\textwidth}
+\underline{\bf Strand 1}\medskip
 \begin{itemize}
 \item four programming subtasks:
 \begin{itemize}
@@ -506,8 +696,8 @@
 \end{column}
 
 \hspace{-45pt}\vrule{}\hspace{10pt}
-
\begin{column}{.5\textwidth}
-\underline{\bf Strand 2}\smallskip
\begin{itemize}
+\begin{column}{.5\textwidth}
+\underline{\bf Strand 2}\smallskip\begin{itemize}
 \item one task: prove the correctness of a regular expression matcher in 
 the Isabelle theorem prover
 \item 25\%, submission 12.12.
@@ -526,6 +716,13 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}\\[3cm]\alert{Questions?}\end{tabular}}
+
+\mbox{}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 \end{document}
 
 %%% Local Variables: