--- 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: