
diff -r 610f14009c0b -r cd0ceaf89c1d slides01.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/slides01.tex	Sun May 05 22:02:29 2019 +0100
@@ -0,0 +1,914 @@
+\documentclass[dvipsnames,14pt,t,xelatex]{beamer}
+\usepackage{./slides}
+\usepackage{./graph}
+\usepackage{./langs}
+\usepackage{./data}
+
+\hfuzz=220pt 
+
+\lstset{language=Scala,
+        style=mystyle,
+        numbersep=0pt,
+        numbers=none,
+        xleftmargin=0mm}
+
+\newcommand{\bl}[1]{\textcolor{blue}{#1}}     
+ 
+% beamer stuff 
+\renewcommand{\slidecaption}{CFL 01, King's College London}
+
+
+\begin{filecontents}{re-python2.data}
+1 0.033
+5 0.036
+10 0.034
+15 0.036
+18 0.059
+19 0.084 
+20 0.141
+21 0.248
+22 0.485
+23 0.878
+24 1.71
+25 3.40
+26 7.08
+27 14.12
+28 26.69
+\end{filecontents}
+
+\begin{filecontents}{re-java.data}
+5  0.00298
+10  0.00418
+15  0.00996
+16  0.01710
+17  0.03492
+18  0.03303
+19  0.05084
+20  0.10177
+21  0.19960
+22  0.41159
+23  0.82234
+24  1.70251
+25  3.36112
+26  6.63998
+27  13.35120
+28  29.81185
+\end{filecontents} 
+
+\begin{filecontents}{re-java9.data}
+1000  0.01410
+2000  0.04882
+3000  0.10609
+4000  0.17456
+5000  0.27530
+6000  0.41116
+7000  0.53741
+8000  0.70261
+9000  0.93981
+10000 0.97419
+11000 1.28697
+12000 1.51387
+14000 2.07079
+16000 2.69846
+20000 4.41823
+24000 6.46077
+26000 7.64373
+30000 9.99446
+34000 12.966885
+38000 16.281621
+42000 19.180228
+46000 21.984721
+50000 26.950203
+60000 43.0327746
+\end{filecontents}
+
+
+
+\begin{document}
+
+
+
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{%  
+  \begin{tabular}{@ {}c@ {}}
+  \\[-3mm]
+  \LARGE Compilers and \\[-1mm] 
+  \LARGE Formal Languages (1)\\[-3mm] 
+  \end{tabular}}
+
+  \begin{center}
+  %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm}
+  %\includegraphics[scale=0.31]{pics/ante2.jpg}\\
+  %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)}
+  \end{center}
+
+  \normalsize
+  \begin{center}
+  \begin{tabular}{ll}
+  Email:  & christian.urban at kcl.ac.uk\\
+  Office: & N\liningnums{7.07} (North Wing, Bush House)\\
+  Slides: & KEATS
+  \end{tabular}
+  \end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Why Study Compilers?}
+
+John Regehr {\small(Univ.~Utah, LLVM compiler hacker)}\smallskip\\
+
+\begin{bubble}[10.5cm]
+  \bf ``\ldots{}It’s effectively a perpetual
+  employment act for solid compiler hackers.''
+\end{bubble}
+
+\onslide<1->{
+\only<2>{
+\begin{itemize}
+\item {\bf Hardware is getting weirder
+  rather than getting clocked faster}
+
+\begin{itemize}
+\item  Almost all processors are
+  multicores nowadays and it looks like there is increasing asymmetry in
+  resources across cores. Processors come with vector units, crypto
+  accelerators etc. We have DSPs, GPUs,
+  ARM big.little, and Xeon Phi. This is only scratching the
+  surface.
+\end{itemize}  
+\end{itemize}}
+\only<3>{
+\begin{itemize}
+\item {\bf We’re getting tired of low-level languages and
+    their associated security disasters}
+  
+\begin{itemize}
+\item 
+  We want to write new code, to
+  whatever extent possible, in safer, higher-level
+  languages. Compilers are caught right in the middle of these
+  opposing trends: one of their main jobs is to help bridge the large
+  and growing gap between increasingly high-level languages and
+  increasingly wacky platforms.
+\end{itemize}  
+\end{itemize}}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Why Bother?}
+
+\begin{columns}[t]
+\begin{column}{.5\textwidth}
+Ruby, Python, Java 8\medskip\\
+\begin{tikzpicture}\footnotesize
+\begin{axis}[
+    xlabel={$n$},
+    x label style={at={(1.05,0.0)}},
+    ylabel={time in secs},
+    enlargelimits=false,
+    xtick={0,5,...,30},
+    xmax=33,
+    ymax=35,
+    ytick={0,5,...,30},
+    scaled ticks=false,
+    axis lines=left,
+    width=5.5cm,
+    height=4cm, 
+    legend entries={Python,Ruby},  
+    legend pos=north west,
+    legend cell align=left]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
+\addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data};
+\end{axis}
+\end{tikzpicture}
+\begin{tikzpicture}\footnotesize
+\begin{axis}[
+    xlabel={$n$},
+    x label style={at={(1.05,0.0)}},
+    ylabel={time in secs},
+    enlargelimits=false,
+    xtick={0,5,...,30},
+    xmax=33,
+    ymax=35,
+    ytick={0,5,...,30},
+    scaled ticks=false,
+    axis lines=left,
+    width=5.5cm,
+    height=4cm, 
+    legend entries={Python, Java 8},  
+    legend pos=north west,
+    legend cell align=left]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};   
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\end{axis}
+\end{tikzpicture}
+
+\end{column}
+\begin{column}{.5\textwidth}
+Us (after next lecture)\medskip\\
+\begin{tikzpicture}\footnotesize
+\begin{axis}[
+    xlabel={$n$},
+    x label style={at={(1.07,0.0)}},
+    ylabel={time in secs},
+    enlargelimits=false,
+    xtick={0,5000,...,10000},
+    xmax=11000,
+    ymax=35,
+    ytick={0,5,...,30},
+    scaled ticks=false,
+    axis lines=left,
+    width=5.5cm,
+    height=4cm]
+\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
+\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
+\end{axis}
+\end{tikzpicture}
+\begin{tikzpicture}\footnotesize
+\begin{axis}[
+    xlabel={$n$},
+    x label style={at={(1.07,0.0)}},
+    ylabel={time in secs},
+    enlargelimits=false,
+    ymax=35,
+    ytick={0,5,...,30},
+    scaled ticks=false,
+    axis lines=left,
+    width=5.5cm,
+    height=4cm]
+\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
+\end{axis}
+\end{tikzpicture}
+\end{column}
+\end{columns}\bigskip
+
+\small\centering
+matching \texttt{[a?]\{n\}[a]\{n\}} and \texttt{(a*)*b}
+against $\underbrace{\texttt{a}...\texttt{a}}_n$
+\end{frame} 
+
+\begin{frame}
+\begin{column}{.5\textwidth}
+\begin{tikzpicture}
+\begin{axis}[
+    xlabel={$n$},
+    x label style={at={(1.05,0.0)}},
+    ylabel={time in secs},
+    y label style={at={(0.06,0.5)}},
+    enlargelimits=false,
+    xtick={0,5,...,30},
+    xmax=33,
+    ymax=45,
+    ytick={0,10,...,40},
+    scaled ticks=false,
+    axis lines=left,
+    width=6cm,
+    height=4.5cm, 
+    legend entries={Python, Java 8},  
+    legend pos=north west]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\end{axis}
+\end{tikzpicture}
+\begin{tikzpicture}
+\begin{axis}[
+    xlabel={$n$},
+    x label style={at={(1.05,0.0)}},
+    ylabel={time in secs},
+    y label style={at={(0.06,0.5)}},
+    %enlargelimits=false,
+    %xtick={0,5000,...,30000},
+    xmax=65000,
+    ymax=45,
+    ytick={0,10,...,40},
+    scaled ticks=false,
+    axis lines=left,
+    width=6cm,
+    height=4.5cm, 
+    legend entries={Java 9},  
+    legend pos=north west]
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data};
+\end{axis}
+\end{tikzpicture}
+\end{column}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Evil Regular Expressions}
+
+\begin{itemize}
+\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\medskip
+\item Evil regular expressions\medskip
+\begin{itemize}
+\item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}
+\item \bl{$(a^*)^*\cdot b$}
+\item \bl{$([a$\,-\,$z]^+)^*$}
+\item \bl{$(a + a \cdot a)^*$}
+\item \bl{$(a + a^?)^*$}
+\end{itemize}
+
+\item sometimes also called \alert{catastrophic backtracking}
+\item this is a problem for \alert{N}etwork \alert{I}ntrusion
+  \alert{D}etection systems, StackExchange, Atom editor
+\item \url{https://vimeo.com/112065252}  
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{The Goal of this Module}
+
+\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 write a compiler};
+
+  \node (0) at (-2.3,0) {};  
+  \node [above=5mm of 0]
+  {\makebox[0mm]{\footnotesize
+      \begin{tabular}{@{}l@{}}input\\[-1mm]program\end{tabular}}}; 
+     
+  \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};
+
+  \node (C) at (6,0)  [node] {};
+  \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen};
+
+  \node (1) at (8.4,0) {};
+  \node [above=5mm of 1]
+  {\makebox[0mm]{\footnotesize
+      \begin{tabular}{@{}r@{}}binary\\[-1mm]code\end{tabular}}};
+
+  \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{center}
+
+\only<2,3,4>{
+\begin{textblock}{1}(1,2.1)
+\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}}
+
+\only<3,4>{
+\begin{textblock}{1}(6,7.8)
+\begin{tabular}{c}
+\includegraphics[scale=0.2]{rosetta.jpg}\\[-2mm]
+\footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta)
+\end{tabular}
+\end{textblock}}
+
+\only<4>{
+\begin{textblock}{1}(0.5,12)\small
+\begin{tabular}{l@{}c@{}l}
+  \pcode{if}    & $\;\Rightarrow\;$ & keyword\\
+  \pcode{iffoo} & $\;\Rightarrow\;$ & identifier\\
+\end{tabular}  
+\end{textblock}}
+
+\only<5>{
+\begin{textblock}{1}(1,1.5)
+\begin{bubble}[8.5cm]
+\normalsize
+parser input: a sequence of tokens\smallskip\\
+
+{\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\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}}
+
+\only<6,7>{
+\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}}
+
+\only<7>{
+\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]
+\frametitle{The Acad.~Subject is Mature}
+
+\begin{itemize}
+\item Turing Machines, 1936
+\item Regular Expressions, 1956\\
+\item The first compiler for COBOL, 1957\\ (Grace Hopper)
+\item But surprisingly research papers are still published nowadays\\
+\item ``Parsing: The Solved Problem That Isn't''
+\end{itemize}
+
+\begin{flushright}
+\includegraphics[scale=0.3]{hopper.jpg}\\
+\footnotesize\textcolor{gray}{Grace Hopper}
+\end{flushright}
+
+
+\begin{flushright}
+\mbox{}\\[-6mm]
+{\footnotesize\textcolor{gray}{(she made it to David Letterman's Tonight Show,\\[-2mm]
+ \url{http://www.youtube.com/watch?v=aZOxtURhfEU})}}
+\end{flushright}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Lectures 1 - 5}
+
+transforming strings into structured data\\[10mm]
+
+{\LARGE\bf Lexing} {\hfill{}based 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]{rosetta.jpg}\\[-2mm]
+\footnotesize Stone of Rosetta
+\end{tabular}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Familiar Regular Expr.}
+\small
+\begin{center}
+\texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{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-z A-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{Today}
+
+\begin{itemize}
+\item While the ultimate goal is to implement a small compiler for the JVM
+  \ldots\bigskip
+\end{itemize}
+
+Let's start with:
+
+\begin{itemize}
+\item a web-crawler
+\item an email harvester
+%\item \textcolor{gray}{(a web-scraper)}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{A Web-Crawler}
+
+\mbox{}\\[10mm]
+
+\begin{enumerate}
+\item given an URL, read the corresponding webpage
+\item extract all links from it
+\item call the web-crawler again for all these links
+\end{enumerate}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{A Web-Crawler}
+
+\mbox{}\\[10mm]
+
+
+\begin{enumerate}
+\item given an URL, read the corresponding webpage
+\item if not possible print, out a problem
+\item if possible, extract all links from it
+\item call the web-crawler again for all these links
+\end{enumerate}\bigskip\pause
+
+\small (we need a bound for the number of recursive calls)
+
+\small (the purpose is to check all links on my own webpage)
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{textblock}{1}(2,5)
+\begin{tabular}{c}
+\includegraphics[scale=0.15]{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]{laptop.png}\\[-2mm]
+\small Browser
+\end{tabular}
+\end{textblock}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+  
+
+ 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{A Regular Expression}
+
+\begin{itemize}
+\item \ldots{} is a pattern or template for specifying strings
+\end{itemize}\bigskip
+  
+\begin{center}  
+\only<1>{\scode{"https?://[^"]*"}}%
+\only<2>{\scode{""""https?://[^"]*"""".r}}
+\end{center}\bigskip\bigskip
+
+matches for example\smallskip\\  
+\hspace{2mm}\code{"http://www.foobar.com"}\\
+\hspace{2mm}\code{"https://www.tls.org"}\smallskip\\
+
+but not\smallskip\\  
+\hspace{2mm}\code{"http://www."foo"bar.com"}\\
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Finding Operations in Scala}
+
+{\bf\code{rexp.findAllIn(string)}}\medskip
+  
+returns a list of all (sub)strings that match the 
+regular expression
+\bigskip\bigskip  
+  
+
+{\bf\code{rexp.findFirstIn(string)}}\medskip
+ 
+returns either 
+
+\begin{itemize}
+\item \code{None} if no (sub)string matches or 
+\item \code{Some(s)} with the first (sub)string
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Regular Expressions}
+
+Their inductive definition:
+
+
+\begin{textblock}{6}(2,7.5)
+  \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
+  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & nothing\\
+         & \bl{$\mid$} & \bl{$\ONE$}       & empty string / \pcode{""} / $[]$\\
+         & \bl{$\mid$} & \bl{$c$}                         & character\\
+         & \bl{$\mid$} & \bl{$r_1 + r_2$}  & alternative / choice\\
+         & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\
+         & \bl{$\mid$} & \bl{$r^*$}            & star (zero or more)\\
+  \end{tabular}
+  \end{textblock}
+  
+  
+  
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\begin{frame}[t]
+%\frametitle{Regular Expressions}
+%
+%\small
+%In Scala:\bigskip
+%
+%\footnotesize
+%\lstinputlisting{../progs/app51.scala}
+%
+%  
+%\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Strings}
+
+\ldots are lists of characters. For example \code{"hello"}
+
+\begin{center}
+\bl{$[h, e, l, l, o]$} or just \bl{$hello$}
+\end{center}
+
+the empty string: \bl{$[]$} or \bl{\pcode{""}}\bigskip\\
+
+the concatenation of two strings:
+
+\begin{center}
+\bl{$s_1 \,@\, s_2$}
+\end{center}
+
+\bl{\textit{foo $@$ bar = foobar}, \textit{baz $@\, []$ = baz}}
+  
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Languages, Strings}
+
+\begin{itemize}
+\item \alert{\bf Strings} are lists of characters, for example
+\begin{center}
+\bl{$[]$},\;\bl{$abc$}  \hspace{2cm}(Pattern match: \bl{$c\!::\!s$})
+\end{center}\bigskip
+
+
+\item A \alert{\bf language} is a set of strings, for example\medskip
+\begin{center}
+\bl{$\{[], hello, \textit{foobar}, a, abc\}$}
+\end{center}\bigskip
+
+\item \alert{\bf Concatenation} of strings and languages
+
+\begin{center}
+\begin{tabular}{rcl}
+\bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\
+\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$}
+\end{tabular}
+\end{center}
+
+%\item The \alert{\bf meaning} of a regular expression is a set of 
+%  strings, or language.
+\end{itemize}  
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] 
+  Regular Expression\end{tabular}}
+
+\begin{textblock}{15}(1,4)
+ \begin{tabular}{rcl}
+ \bl{$L(\ZERO)$}  & \bl{$\dn$} & \bl{$\{\}$}\\
+ \bl{$L(\ONE)$}     & \bl{$\dn$} & \bl{$\{[]\}$}\\
+ \bl{$L(c)$}            & \bl{$\dn$} & \bl{$\{[c]\}$}\\
+ \bl{$L(r_1 + r_2)$}    & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
+ \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\
+ \bl{$L(r^*)$}           & \bl{$\dn$} & \onslide<4->{\bl{$\bigcup_{0 \le n} L(r)^n$}}\\
+  \end{tabular}\bigskip
+  
+\onslide<2->{
+\hspace{5mm}\bl{$L(r)^0 \;\dn\; \{[]\}$}\\
+\bl{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}\hspace{9mm}\onslide<3->{\small\textcolor{gray}{(append on sets)}\\
+\small\hspace{5cm}\textcolor{gray}{$\{ s_1 @ s_2 \;|\; s_1\in L(r) \wedge s_2 \in L(r)^n \}$}}
+}  
+    \end{textblock}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{The Meaning of Matching}
+
+\begin{bubble}[10cm]
+\large\bf 
+A regular expression \bl{$r$} matches a string~\bl{$s$} 
+provided
+
+\begin{center}
+\bl{$s \in L(r)$}\\ 
+\end{center}
+\end{bubble}\bigskip\bigskip
+
+\ldots and the point of the next lecture is 
+to decide this problem as fast as possible (unlike Python,
+Ruby, Java)
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Written Exam}
+
+\begin{itemize}
+\item Accounts for 80\%.\bigskip
+
+\item The question ``\textit{Is this relevant for
+      the exam?}'' is very demotivating for the lecturer!\bigskip\\
+
+\item Deal: Whatever is in the homework (and is not marked
+      ``\textit{optional}'') is relevant for the exam.\bigskip
+      
+\item Each lecture has also a handout. There are also handouts about
+notation and Scala.      
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Coursework}
+
+\begin{itemize}
+\item Accounts for 20\%. Two strands. Choose \alert{\bf one}!\bigskip
+\end{itemize}
+
+\begin{columns}[t]
+\begin{column}{.5\textwidth}
+\underline{\bf Strand 1}\medskip
+\begin{itemize}
+\item four programming tasks:
+\begin{itemize}
+\item matcher (4\%, 12.10.) 
+\item lexer (5\%, 02.11.)
+\item parser (5\%, 23.11.)
+\item compiler (6\%, 14.12.)
+\end{itemize}
+\item in any lang.~you like,\\ but I want to see the code
+\end{itemize}
+\end{column}
+
+\hspace{-45pt}\vrule{}\hspace{10pt}
+\begin{column}{.5\textwidth}
+\underline{\bf Strand 2}\smallskip\begin{itemize}
+\item one task: prove the correctness of a regular expression matcher in 
+the \underline{Isabelle} theorem prover
+\item 20\%, submission on~14.12.\hspace{-5mm}\mbox{}
+\end{itemize}
+\end{column}
+\end{columns}\medskip
+
+\small
+\begin{itemize}
+\item Solving more than one strand will {\bf not} give you more 
+marks.
+
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Lecture Capture}
+
+\begin{itemize}
+\item Hope it works\ldots\pause actually no, it does not!\medskip\pause
+\item It is important to use lecture capture wisely\\ (it is only the ``baseline''):
+\begin{itemize}  
+\item Lecture recordings are a study and revision aid.
+\item Statistically, there is a clear and direct link between attendance and
+  attainment: Students who do not attend lectures, do less well in exams.
+\end{itemize}
+
+\item Attending a lecture is more than watching it online -- if you do not
+attend, you miss out!  
+  
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}\\[3cm]\alert{Questions?}\end{tabular}}
+
+\mbox{}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+\end{document}
+
+%%% Local Variables:  
+%%% mode: latex
+%%% TeX-master: t
+%%% End: 
+




