% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../graphicss}
\usepackage{../langs}
\usepackage{../data}
\hfuzz=220pt
\pgfplotsset{compat=1.11}
\usepackage{tcolorbox}
\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}
\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}
\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}
% a hand written lexer for SML
% https://ponyo.org/
% https://github.com/eatonphil/ponyo/blob/master/src/Sml/Lexer.sml
\beamertemplateballitem
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
\renewcommand{\slidecaption}{CFL 04, King's College London}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-1mm]
\LARGE Formal Languages\\[-5mm]
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
Office Hour: & Fridays 11 -- 12\\
Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS\\
Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\
\end{tabular}
\end{center}
\begin{center}
\begin{tikzpicture}
\node[drop shadow,fill=white,inner sep=0pt]
{\footnotesize\rowcolors{1}{capri!10}{white}
\begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
1 Introduction, Languages & 6 While-Language \\
2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
3 Automata, Regular Languages & 8 Compiling Functional Languages \\
\cellcolor{blue!50}
4 Lexing, Tokenising & 9 Optimisations \\
5 Grammars, Parsing & 10 LLVM \\ \hline
\end{tabular}%
};
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Coursework}
%
%\begin{itemize}
%\item \bl{$\der\,c\,(r^+) \dn \der\,c (r\cdot r^*)$}\quad given
%that \bl{$r^+ \dn r\cdot r^*$}
%\end{itemize}\bigskip\pause
%\begin{center}
%\begin{tabular}{lcl}
%\bl{$\der\,c\,(r\cdot r^*)$} & \bl{$\dn$} &
%\only<2-4>{if \bl{$nullable\,r$}}%
%\only<5>{\bl{$(\der\,c\,r)\cdot r^*$}}\\
% & &
% \only<2>{then \bl{$(\der\,c\,r)\cdot r^* \,+\, \der\,c\,(r^*)$}}%
% \only<3>{then \bl{$(\der\,c\,r)\cdot r^* \,+\, (\der\,c\,r)\cdot r^*$}}%
% \only<4>{then \bl{$(\der\,c\,r)\cdot r^*$}}\\
% & & \only<2-4>{else \bl{$(\der\,c\,r)\cdot r^*$}}
%\end{tabular}
%\end{center}
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
% \frametitle{Coursework (2)}
%
% \begin{itemize}
% \item \bl{\texttt{CFUN(f: Char => Boolean)}}
% \end{itemize}\medskip
%
% \begin{center}
% \begin{tabular}{l}
% \bl{\texttt{CHAR(c: Char)}} \bl{$\dn$}\\
% \quad\bl{\texttt{CFUN(\_ == c)}}\medskip\\
% \bl{\texttt{RANGE(cs: Set[Char])}} \bl{$\dn$}\\
% \quad\bl{\texttt{CFUN(cs.contains(\_))}}\medskip\\
% \bl{\texttt{ALL}} \bl{$\dn$}\\
% \quad\bl{\texttt{CFUN((c: Char) => true)}}\\
% \end{tabular}
% \end{center}
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{The Goal of this Course}
\mbox{}\\[-26mm]\mbox{}
\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,drop shadow}]
\node at (3.05, 1.8) {\Large\bf Write 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};
\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{center}
Today a lexer.
\only<2>{
\begin{textblock}{1}(6,9.8)
\begin{tabular}{c}
\includegraphics[scale=0.13]{../pics/rosetta.jpg}\\[-2mm]
\footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta)
\end{tabular}
\end{textblock}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Regular Expressions}
In programming languages they are often used to recognise:\medskip
\begin{itemize}
\item operands, digits
\item identifiers
\item numbers (non-leading zeros)
\item keywords
\item comments
\end{itemize}\bigskip
\mbox{}\hfill\bl{\url{http://www.regexper.com}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Lexing: Test Case}
\mbox{\lstinputlisting[language=While]{../progs/while-tests/fib.while}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{?? Test Case}
%
%\mbox{\lstinputlisting[language=While]{../progs/collatz.while}}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\tt
\begin{center}\large
\code{"if true then then 42 else +"}
\end{center}
\begin{tabular}{@{}l}
KEYWORD: \\
\hspace{5mm}{if}, {then}, {else},\\
WHITESPACE:\\
\hspace{5mm}{" "}, {$\backslash$n},\\
IDENTIFIER:\\
\hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + {\_})$^*$\\
NUM:\\
\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {0}\\
OP:\\
\hspace{5mm}+, -, *, \%, <, <=\\
COMMENT:\\
\hspace{5mm}{$\slash$*} $\cdot$ $\sim$(ALL$^*$ $\cdot$ (*$\slash$) $\cdot$ ALL$^*$) $\cdot$ {*$\slash$}
\end{tabular}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\tt
\begin{center}\large
\code{"if true then then 42 else +"}
\end{center}
\only<1>{
\small\begin{tabular}{l}
KEYWORD(if),\\
WHITESPACE,\\
IDENT(true),\\
WHITESPACE,\\
KEYWORD(then),\\
WHITESPACE,\\
KEYWORD(then),\\
WHITESPACE,\\
NUM(42),\\
WHITESPACE,\\
KEYWORD(else),\\
WHITESPACE,\\
OP(+)
\end{tabular}}
\only<2>{
\small\begin{tabular}{l}
KEYWORD(if),\\
IDENT(true),\\
KEYWORD(then),\\
KEYWORD(then),\\
NUM(42),\\
KEYWORD(else),\\
OP(+)
\end{tabular}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
There is one small problem with the tokenizer. How should we
tokenize\ldots?
\begin{center}
\large\code{"x-3"}
\end{center}
\tt
\begin{tabular}{@{}l}
ID: \ldots\\
OP:\\
\hspace{5mm}\texttt{"+"}, \texttt{"-"}\\
NUM:\\
\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {''0''}\\
NUMBER:\\
\hspace{5mm}NUM + (\texttt{"-"} $\cdot$ NUM)\\
\end{tabular}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
The same problem with\medskip
\[
\bl{(ab + a) \cdot (c + bc)}
\]\medskip
and the string $\bl{abc}$.\pause\bigskip
Or, keywords are \code{if} etc and identifiers are
letters followed by ``letters + numbers + \_''$^*$
\[
\bl{\texttt{if}}\qquad\bl{\texttt{iffoo}}
\]
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{POSIX: Two Rules}
\begin{itemize}
\item Longest match rule (``maximal munch rule''): The
longest initial substring matched by any regular expression is taken
as the next token.\bigskip
\item Rule priority:
For a particular longest initial substring, the first regular
expression that can match determines the token.
\end{itemize}\bigskip\bigskip\pause
\small
\hfill most posix matchers are buggy\\
\footnotesize
\hfill
\url{http://www.haskell.org/haskellwiki/Regex_Posix}
\smallskip\pause
\hfill \small traditional lexers are fast, but hairy
%\url{http://www.technologyreview.com/tr10/?year=2011}
%finite deterministic automata/ nondeterministic automaton
%\item problem with infix operations, for example i-12
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Sulzmann \& Lu Matcher}
We want to match the string \bl{$abc$} using \bl{$r_1$}:
\begin{center}
\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
\node (r1) {\bl{$r_1$}};
\node (r2) [right=of r1] {\bl{$r_2$}};
\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};\pause
\node (r3) [right=of r2] {\bl{$r_3$}};
\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};\pause
\node (r4) [right=of r3] {\bl{$r_4$}};
\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};\pause
\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable?$}}};\pause
\node (v4) [below=of r4] {\bl{$v_4$}};
\draw[->,line width=1mm] (r4) -- (v4);\pause
\node (v3) [left=of v4] {\bl{$v_3$}};
\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};\pause
\node (v2) [left=of v3] {\bl{$v_2$}};
\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};\pause
\node (v1) [left=of v2] {\bl{$v_1$}};
\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};\pause
\draw[->,line width=0.5mm] (r3) -- (v3);
\draw[->,line width=0.5mm] (r2) -- (v2);
\draw[->,line width=0.5mm] (r1) -- (v1);
\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Regexes and Values}
Regular expressions and their corresponding values:
\begin{center}
\begin{columns}
\begin{column}{3cm}
\begin{tabular}{@{}rrl@{}}
\bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\
& \bl{$\mid$} & \bl{$\ONE$} \\
& \bl{$\mid$} & \bl{$c$} \\
& \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
& \bl{$\mid$} & \bl{$r_1 + r_2$} \\
\\
& \bl{$\mid$} & \bl{$r^*$} \\
\\
\end{tabular}
\end{column}
\begin{column}{3cm}
\begin{tabular}{@{\hspace{-7mm}}rrl@{}}
\bl{$v$} & \bl{$::=$} & \\
& & \bl{$Empty$} \\
& \bl{$\mid$} & \bl{$Char(c)$} \\
& \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\
& \bl{$\mid$} & \bl{$Left(v)$} \\
& \bl{$\mid$} & \bl{$Right(v)$} \\
& \bl{$\mid$} & \bl{$Stars\,[]$} \\
& \bl{$\mid$} & \bl{$Stars\,[v_1,\ldots\,v_n]$} \\
\end{tabular}
\end{column}
\end{columns}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\small
{\small\lstinputlisting[language=Scala,numbers=none,
xleftmargin=-5mm] {../progs/app01.scala}}
{\small\lstinputlisting[language=Scala,numbers=none,
xleftmargin=-5mm] {../progs/app02.scala}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\begin{textblock}{10}(3,5)
\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
\node (r1) {\bl{$r_1$}};
\node (r2) [right=of r1] {\bl{$r_2$}};
\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
\node (r3) [right=of r2] {\bl{$r_3$}};
\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
\node (r4) [right=of r3] {\bl{$r_4$}};
\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
\node (v4) [below=of r4] {\bl{$v_4$}};
\draw[->,line width=1mm] (r4) -- (v4);
\node (v3) [left=of v4] {\bl{$v_3$}};
\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
\node (v2) [left=of v3] {\bl{$v_2$}};
\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
\node (v1) [left=of v2] {\bl{$v_1$}};
\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
\draw[->,line width=0.5mm] (r3) -- (v3);
\draw[->,line width=0.5mm] (r2) -- (v2);
\draw[->,line width=0.5mm] (r1) -- (v1);
\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
\end{tikzpicture}
\end{textblock}
\only<1->{
\begin{textblock}{6}(1,0.8)
\begin{bubble}[6cm]
\small
\begin{tabular}{ll}
\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\
\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\
\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\
\end{tabular}
\end{bubble}
\end{textblock}}
\only<2->{
\begin{textblock}{6}(5,11.4)
\begin{bubble}[7.6cm]
\small
\begin{tabular}{ll}
\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
\end{tabular}
\end{bubble}
\end{textblock}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Flatten}
Obtaining the string underlying a value:
\begin{center}
\begin{tabular}{lcl}
\bl{$|Empty|$} & \bl{$\dn$} & \bl{$[]$}\\
\bl{$|Char(c)|$} & \bl{$\dn$} & \bl{$[c]$}\\
\bl{$|Left(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\
\bl{$|Right(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\
\bl{$|Seq(v_1,v_2)|$}& \bl{$\dn$} & \bl{$|v_1| \,@\, |v_2|$}\\
\bl{$|Stars\,[v_1,\ldots ,v_n]|$} & \bl{$\dn$} & \bl{$|v_1| \,@\ldots @\, |v_n|$}\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\begin{textblock}{10}(3,5)
\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
\node (r1) {\bl{$r_1$}};
\node (r2) [right=of r1] {\bl{$r_2$}};
\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
\node (r3) [right=of r2] {\bl{$r_3$}};
\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
\node (r4) [right=of r3] {\bl{$r_4$}};
\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
\node (v4) [below=of r4] {\bl{$v_4$}};
\draw[->,line width=1mm] (r4) -- (v4);
\node (v3) [left=of v4] {\bl{$v_3$}};
\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
\node (v2) [left=of v3] {\bl{$v_2$}};
\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
\node (v1) [left=of v2] {\bl{$v_1$}};
\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
\draw[->,line width=0.5mm] (r3) -- (v3);
\draw[->,line width=0.5mm] (r2) -- (v2);
\draw[->,line width=0.5mm] (r1) -- (v1);
\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
\end{tikzpicture}
\end{textblock}
\begin{textblock}{6}(1,0.8)
\begin{bubble}[6cm]
\small
\begin{tabular}{ll}
\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\
\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\
\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\
\end{tabular}
\end{bubble}
\end{textblock}
\begin{textblock}{6}(1,11.4)
\begin{bubble}[7.6cm]
\small
\begin{tabular}{ll}
\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
\end{tabular}
\end{bubble}
\end{textblock}
\begin{textblock}{6}(12,11.4)
\begin{bubble}[2cm]
\small
\begin{tabular}{ll}
\bl{$|v_1|$}: & \bl{$abc$}\\
\bl{$|v_2|$}: & \bl{$bc$}\\
\bl{$|v_3|$}: & \bl{$c$}\\
\bl{$|v_4|$}: & \bl{$[]$}
\end{tabular}
\end{bubble}
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Mkeps}
Finding a (posix) value for recognising the empty string:
\begin{center}
\begin{tabular}{lcl}
\bl{$mkeps\,(\ONE)$} & \bl{$\dn$} & \bl{$Empty$}\\
\bl{$mkeps\,(r_1 + r_2)$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\
& & \bl{then $Left(mkeps(r_1))$}\\
& & \bl{else $Right(mkeps(r_2))$}\\
\bl{$mkeps\,(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\
\bl{$mkeps\,(r^*)$} & \bl{$\dn$} & \bl{$Stars\,[]$} \\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Inject}
\large
\begin{center}
\begin{tikzpicture}[scale=3,node distance=1.2cm,
every node/.style={minimum size=7mm}]
\node (r) {$r$};
\node (rd) [right=of r]{$r_{der}$};
\draw[->,line width=1mm](r)--(rd) node[above,midway] {$\der\,c$};
\node (vd) [below=of r2]{$v_{der}$};
\draw[->,line width=1mm](rd) -- (vd);
\node (v) [left=of vd] {$v$};
\draw[->,line width=1mm](vd)--(v) node[below,midway] {$inj\,c$};
\draw[->,line width=0.5mm,dotted](r) -- (v) node[left,midway,red] {\bf ?};
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Inject}
Injecting (``Adding'') a character to a value\\[-12mm]\mbox{}
\begin{center}
\begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
\bl{$inj\,(c)\,c\,(Empty)$} & \bl{$\dn$} & \bl{$Char\,c$}\\
\bl{$inj\,(r_1 + r_2)\,c\,(Left(v))$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\
\bl{$inj\,(r_1 + r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\
\bl{$inj\,(r_1 \cdot r_2)\,c\,(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
\bl{$inj\,(r_1 \cdot r_2)\,c\,(Left(Seq(v_1,v_2)))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
\bl{$inj\,(r_1 \cdot r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
\bl{$inj\,(r^*)\,c\,(Seq(v,Stars\,vs))$} & \bl{$\dn$} & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}\\
\end{tabular}
\end{center}\bigskip
\footnotesize
\begin{tabular}{l@{\hspace{2mm}}l}
\bl{$inj$}: & 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character;
3rd arg $\mapsto$ a value\\
& result $\mapsto$ a value
\end{tabular}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\begin{center}
\begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
\bl{$inj\,(c)\,c\,(Empty)$} & \bl{$\dn$} & \bl{$Char\,c$}\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\begin{center}
\begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
\bl{$inj\,(r_1 + r_2)\,c\,(Left(v))$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\
\bl{$inj\,(r_1 + r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\begin{center}
\begin{tabular}{@{\hspace{-8mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
\\[-15mm]
\bl{$inj\,(r_1 \cdot r_2)\,c\,(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
\bl{$inj\,(r_1 \cdot r_2)\,c\,(Left(Seq(v_1,v_2)))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
\bl{$inj\,(r_1 \cdot r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
\end{tabular}
\end{center}
\begin{textblock}{13}(1,13.4)
\begin{bubble}[13cm]
\small
\bl{$\der\, c\, (r_1 \cdot r_2)$} \bl{$\dn$} \bl{\textbf{if} $nullable (r_1)$}
\bl{\textbf{then} $(\der\,c\,r_1) \cdot r_2 + \der\, c\, r_2$}
\bl{\textbf{else} $(\der\, c\, r_1) \cdot r_2$}
\end{bubble}
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\begin{center}
\begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
\bl{$inj\,(r^*)\,c\,(Seq(v,Stars\,vs))$} & \bl{$\dn$} & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Lexing}
\begin{center}
\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
\bl{$lex\,r\,[]$} & \bl{$\dn$} & \bl{if $nullable(r)$ then $mkeps(r)$ else $error$}\\
\bl{$lex\,r\,a::s$} & \bl{$\dn$} & \bl{$inj\,r\,a\,lex(der(a,r), s)$}\\
\end{tabular}
\end{center}
\footnotesize
\bl{$lex$}: returns a value
\begin{center}
\begin{tikzpicture}[scale=2,node distance=1.0cm,every node/.style={minimum size=6mm}]
\node (r1) {\bl{$r_1$}};
\node (r2) [right=of r1] {\bl{$r_2$}};
\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
\node (r3) [right=of r2] {\bl{$r_3$}};
\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
\node (r4) [right=of r3] {\bl{$r_4$}};
\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
\node (v4) [below=of r4] {\bl{$v_4$}};
\draw[->,line width=1mm] (r4) -- (v4);
\node (v3) [left=of v4] {\bl{$v_3$}};
\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
\node (v2) [left=of v3] {\bl{$v_2$}};
\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
\node (v1) [left=of v2] {\bl{$v_1$}};
\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
\draw[->,line width=0.5mm] (r3) -- (v3);
\draw[->,line width=0.5mm] (r2) -- (v2);
\draw[->,line width=0.5mm] (r1) -- (v1);
\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Records}
\begin{itemize}
\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
\item \bl{$nullable(x:r) \dn nullable(r)$}
\item \bl{$der\,c\,(x:r) \dn der\,c\,r$}
\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}
\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$}
\end{itemize}\bigskip\bigskip\pause
\small
for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
\begin{textblock}{6}(10,10)
\begin{bubble}[2cm]
\small
\begin{tabular}{l}
\bl{$(id : r_{id})$}\\
\bl{$(key : r_{key})$}\\
\end{tabular}
\end{bubble}
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\begin{itemize}
\item A regular expression for email addresses
\begin{center}
\begin{tabular}{l}
(name: \bl{$[a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+$})\bl{$\cdot @\cdot$}\\
\qquad(domain: \bl{$[a\mbox{-}z0\mbox{-}9\,-]^+$}) \bl{$\cdot .\cdot$}\\
\qquad\qquad(top\_level: \bl{$[a\mbox{-}z\,.]^{\{2,6\}}$})
\end{tabular}
\end{center}
\bl{\[
\texttt{christian.urban@kcl.ac.uk}
\]}
\item the result environment:
\begin{center}
\begin{tabular}{l}
\bl{$[(name:\texttt{christian.urban}),$}\\
\bl{$\phantom{[}(domain:\texttt{kcl}),$}\\
\bl{$\phantom{[}(top\_level:\texttt{ac.uk})]$}
\end{tabular}
\end{center}
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{While Tokens}
\begin{center}
\begin{tabular}{rcl}
\pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\
& & \phantom{(}\pcode{("i" : ID)} +\\
& & \phantom{(}\pcode{("o" : OP)} + \\
& & \phantom{(}\pcode{("n" : NUM)} + \\
& & \phantom{(}\pcode{("s" : SEMI)} +\\
& & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\
& & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\
& & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Simplification}
\begin{itemize}
\item If we simplify after the derivative, then we are building the
value for the simplified regular expression, but \alert{\textbf{not}} for the original
regular expression.
\end{itemize}
\begin{center}
\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
\node (r1) {\bl{$r_1$}};
\node (r2) [right=of r1] {\bl{$r_2$}};
\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
\node (r3) [right=of r2] {\bl{$r_3$}};
\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
\node (r4) [right=of r3] {\bl{$r_4$}};
\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
\node (v4) [below=of r4] {\bl{$v_4$}};
\draw[->,line width=1mm] (r4) -- (v4);
\node (v3) [left=of v4] {\bl{$v_3$}};
\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
\node (v2) [left=of v3] {\bl{$v_2$}};
\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
\node (v1) [left=of v2] {\bl{$v_1$}};
\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
\draw[->,line width=0.5mm] (r3) -- (v3);
\draw[->,line width=0.5mm] (r2) -- (v2);
\draw[->,line width=0.5mm] (r1) -- (v1);
\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
\end{tikzpicture}
\end{center}
\small\pause
\hspace{4.5cm}\bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}
$\mapsto$
\bl{$\ONE$}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
Normally we would have
\begin{center}
\bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}
\end{center}
and answer how this regular expression matches the empty string
with the value
\begin{center}
\bl{$Right(Right(Empty))$}
\end{center}\bigskip
But now we simplify this to \bl{$\ONE$} and would produce \bl{$Empty$} (see \textit{mkeps}).
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Rectification}
\def\arraystretch{1.05}
\begin{center}
\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l@{\hspace{8mm}}l}
& & & \hspace{5mm}rectification \\
& & & \hspace{5mm}functions:\\
\bl{$r \cdot \ZERO$} & $\mapsto$ & \bl{$\ZERO$} & \\
\bl{$\ZERO \cdot r$} & $\mapsto$ & \bl{$\ZERO$} & \\
\bl{$r \cdot \ONE$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,v, f_2\,Empty)$}\\
\bl{$\ONE \cdot r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,Empty, f_2\,v)$}\\
\bl{$r + \ZERO$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$}\\
\bl{$\ZERO + r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Right(f_2\,v)$}\\
\bl{$r + r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$}
\end{tabular}
\end{center}\medskip\pause
\small
old \bl{$simp$} returns a rexp;\\
new \bl{$simp$} returns a rexp and a rectification~function.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Rectification $\_ + \_$}
\begin{center}
\begin{tabular}{l}
\bl{$simp(r)$}:\\
\quad case \bl{$r = r_1 + r_2$}\\
\qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
\qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
\qquad case \bl{$r_{1s} = \ZERO$}:
return \bl{$(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$}\\
\qquad case \bl{$r_{2s} = \ZERO$}:
return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
\qquad case \bl{$r_{1s} = r_{2s}$}:
return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
\qquad otherwise:
return \bl{$(r_{1s} + r_{2s}, f_{alt}(f_{1s}, f_{2s}))$}\\
\end{tabular}
\end{center}
\small
\begin{center}
\begin{tabular}{l@{\hspace{1mm}}l}
\bl{$f_{alt}(f_1, f_2) \dn$}\\
\qquad \bl{$\lambda v.\,$} case \bl{$v = Left(v')$}:
& return \bl{$Left(f_1(v'))$}\\
\qquad \phantom{$\lambda v.\,$} case \bl{$v = Right(v')$}:
& return \bl{$Right(f_2(v'))$}\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
{\footnotesize\lstinputlisting[language=Scala,numbers=none,
xleftmargin=-5mm] {../progs/app05.scala}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Rectification $\_ \cdot \_$}
\begin{center}
\begin{tabular}{@{\hspace{-3mm}}l}
\bl{$simp(r)$}:\ldots\\
\quad case \bl{$r = r_1 \cdot r_2$}\\
\qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
\qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
\qquad case \bl{$r_{1s} = \ZERO$}:
return \bl{$(\ZERO, f_{error})$}\\
\qquad case \bl{$r_{2s} = \ZERO$}:
return \bl{$(\ZERO, f_{error})$}\\
\qquad case \bl{$r_{1s} = \ONE$}:
return \bl{$(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$}\\
\qquad case \bl{$r_{2s} = \ONE$}:
return \bl{$(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$}\\
\qquad otherwise:
return \bl{$(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$}\\
\end{tabular}
\end{center}
\small
\begin{center}
\begin{tabular}{l@{\hspace{1mm}}l}
\bl{$f_{seq}(f_1, f_2) \dn$}\\
\qquad \bl{$\lambda v.\,$ case $v = Seq(v_1, v_2)$}:
& return \bl{$Seq(f_1(v_1), f_2(v_2))$}\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
{\footnotesize\lstinputlisting[language=Scala,numbers=none,
xleftmargin=-5mm] {../progs/app06.scala}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Rectification Example}
\begin{center}
\bl{$\only<1>{(b \cdot c)}%
\only<2-3>{(\underline{b \cdot c})}%
\only<1-3>{+}%
\only<1>{(\ZERO + \ONE)}%
\only<2-3>{(\underline{\ZERO + \ONE})}$}%
\only<4->{%
\bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}%
}
$\mapsto$
\bl{$(b \cdot c) + \ONE$}
\end{center}\bigskip
\onslide<3->{%
\begin{center}
\begin{tabular}{lcl}
\bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\
\bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$}
\end{tabular}
\end{center}}
\only<4>{%
\begin{center}
\begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\
\quad \bl{$\lambda v.\,$}
case \bl{$v = Left(v')$}:
& return \bl{$Left(f_{s1}(v'))$}\\
\quad \phantom{$\lambda v.\,$}
case \bl{$v = Right(v')$}:
& return \bl{$Right(f_{s2}(v'))$}\\
\end{tabular}
\end{center}}%
\only<5->{%
\begin{center}
\begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
\only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\
\quad \bl{$\lambda v.\,$}
case \bl{$v = Left(v')$}:
& return \bl{$Left(v')$}\\
\quad \phantom{$\lambda v.\,$}
case \bl{$v = Right(v')$}:
& return \bl{$Right(Right(v'))$}\\
\end{tabular}
\end{center}}%
\only<6->{%
\begin{center}
\begin{tabular}{@{}l@{\hspace{4mm}}l@{}}
\bl{$\textit{mkeps}$} simplified case: &
\bl{$\textit{Right}(\textit{Empty})$}\\
rectified case: &
\bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$}
\end{tabular}
\end{center}}%
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Lexing with Simplification}
\begin{center}
\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
\bl{$lex\,r\,[]$} & \bl{$\dn$} & \bl{if $nullable(r)$ then $mkeps(r)$ else $error$}\\
\bl{$lex\,r\,c::s$} & \bl{$\dn$} & \bl{let $(r', frect) = simp(der(c, r))$}\smallskip\\
& & \bl{$inj\,r\,c\,(frect(lex(r', s)))$}\\
\end{tabular}
\end{center}\bigskip
\begin{center}\small
\begin{tikzpicture}[node distance=1.1cm,every node/.style={minimum size=7mm}]
\node (r1) {\bl{$r_1$}};
\node (r2) [right=of r1] {\bl{$r_2$}};
\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
\node (r3) [right=of r2] {\bl{$r_3$}};
\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
\node (r4) [right=of r3] {\bl{$r_4$}};
\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
\node (v4) [below=of r4] {\bl{$v_4$}};
\draw[->,line width=1mm] (r4) -- (v4);
\node (v3) [left=of v4] {\bl{$v_3$}};
\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
\node (v2) [left=of v3] {\bl{$v_2$}};
\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
\node (v1) [left=of v2] {\bl{$v_1$}};
\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
\draw[->,line width=0.5mm] (r3) -- (v3);
\draw[->,line width=0.5mm] (r2) -- (v2);
\draw[->,line width=0.5mm] (r1) -- (v1);
\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Environments}
Obtaining the ``recorded'' parts of a value:
\begin{center}
\begin{tabular}{lcl}
\bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\
\bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\
\bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
\bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
\bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\
\bl{$env(Stars\,[v_1,\ldots ,v_n])$} & \bl{$\dn$} &
\bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\
\bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{While Tokens}
\begin{center}
\begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
\pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\
& & \phantom{(}\pcode{("i" : ID)} +\\
& & \phantom{(}\pcode{("o" : OP)} + \\
& & \phantom{(}\pcode{("n" : NUM)} + \\
& & \phantom{(}\pcode{("s" : SEMI)} +\\
& & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\
& & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\
& & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\consolas
\begin{center}
\code{"if true then then 42 else +"}
\end{center}
\only<1>{
\small\begin{tabular}{l}
KEYWORD(if),\\
WHITESPACE,\\
IDENT(true),\\
WHITESPACE,\\
KEYWORD(then),\\
WHITESPACE,\\
KEYWORD(then),\\
WHITESPACE,\\
NUM(42),\\
WHITESPACE,\\
KEYWORD(else),\\
WHITESPACE,\\
OP(+)
\end{tabular}}
\only<2>{
\small\begin{tabular}{l}
KEYWORD(if),\\
IDENT(true),\\
KEYWORD(then),\\
KEYWORD(then),\\
NUM(42),\\
KEYWORD(else),\\
OP(+)
\end{tabular}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Lexer: Two Rules}
\begin{itemize}
\item Longest match rule (``maximal munch rule''): The
longest initial substring matched by any regular expression is taken
as next token.\bigskip
\item Rule priority:
For a particular longest initial substring, the first regular
expression that can match determines the token.
\end{itemize}
%\url{http://www.technologyreview.com/tr10/?year=2011}
%finite deterministic automata/ nondeterministic automaton
%\item problem with infix operations, for example i-12
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\begin{center}
%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
%\bl{$zeroable(\ZERO)$} & \bl{$\dn$} & \bl{$true$}\\
%\bl{$zeroable(\ONE)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\
%\bl{$zeroable(c)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\
%\bl{$zeroable(r_1 + r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \wedge zeroable(r_2)$}\\
%\bl{$zeroable(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \vee zeroable(r_2)$}\\
%\bl{$zeroable(r^*)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\
%\end{tabular}
%\end{center}
%
%\begin{center}
%\bl{$zeroable(r)$} if and only if \bl{$L(r) = \{\}$}
%\end{center}
%
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{\begin{tabular}{c}Last Week\\[-2mm]
% Regexes and Values\end{tabular}}
%
%Regular expressions and their corresponding values:
%
%\begin{center}
%\begin{columns}
%\begin{column}{3cm}
%\begin{tabular}{@{}rrl@{}}
% \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\
% & \bl{$\mid$} & \bl{$\ONE$} \\
% & \bl{$\mid$} & \bl{$c$} \\
% & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
% & \bl{$\mid$} & \bl{$r_1 + r_2$} \\
% \\
% & \bl{$\mid$} & \bl{$r^*$} \\
% \end{tabular}
%\end{column}
%\begin{column}{3cm}
%\begin{tabular}{@{\hspace{-7mm}}rrl@{}}
% \bl{$v$} & \bl{$::=$} & \\
% & & \bl{$Empty$} \\
% & \bl{$\mid$} & \bl{$Char(c)$} \\
% & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\
% & \bl{$\mid$} & \bl{$Left(v)$} \\
% & \bl{$\mid$} & \bl{$Right(v)$} \\
% & \bl{$\mid$} & \bl{$Stars [v_1,\ldots\,v_n]$} \\
% \end{tabular}
%\end{column}
%\end{columns}
%\end{center}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%
%\begin{textblock}{10}(3,5)
%\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
%\node (r1) {\bl{$r_1$}};
%\node (r2) [right=of r1] {\bl{$r_2$}};
%\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
%\node (r3) [right=of r2] {\bl{$r_3$}};
%\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
%\node (r4) [right=of r3] {\bl{$r_4$}};
%\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
%\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
%\node (v4) [below=of r4] {\bl{$v_4$}};
%\draw[->,line width=1mm] (r4) -- (v4);
%\node (v3) [left=of v4] {\bl{$v_3$}};
%\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
%\node (v2) [left=of v3] {\bl{$v_2$}};
%\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
%\node (v1) [left=of v2] {\bl{$v_1$}};
%\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
%\draw[->,line width=0.5mm] (r3) -- (v3);
%\draw[->,line width=0.5mm] (r2) -- (v2);
%\draw[->,line width=0.5mm] (r1) -- (v1);
%\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
%\end{tikzpicture}
%\end{textblock}
%
%\begin{textblock}{6}(1,0.8)
%\begin{bubble}[6cm]
%\small
%\begin{tabular}{ll}
%\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
%\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\
%\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\
%\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\
%\end{tabular}
%\end{bubble}
%\end{textblock}
%
%\begin{textblock}{6}(1,11.4)
%\begin{bubble}[7.6cm]
%\small
%\begin{tabular}{ll}
%\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
%\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
%\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
%\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
%\end{tabular}
%\end{bubble}
%\end{textblock}
%
%\begin{textblock}{6}(12,11.4)
%\begin{bubble}[2cm]
%\small
%\begin{tabular}{ll}
%\bl{$|v_1|$}: & \bl{$abc$}\\
%\bl{$|v_2|$}: & \bl{$bc$}\\
%\bl{$|v_3|$}: & \bl{$c$}\\
%\bl{$|v_4|$}: & \bl{$[]$}
%\end{tabular}
%\end{bubble}
%\end{textblock}
%
%
%%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Simplification}
%
%\begin{itemize}
%\item If we simplify after the derivative, then we are builing the
%value for the simplified regular expression, but \emph{not} for the original
%regular expression.
%\end{itemize}
%
%\begin{center}
%\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
%\node (r1) {\bl{$r_1$}};
%\node (r2) [right=of r1] {\bl{$r_2$}};
%\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
%\node (r3) [right=of r2] {\bl{$r_3$}};
%\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
%\node (r4) [right=of r3] {\bl{$r_4$}};
%\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
%\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
%\node (v4) [below=of r4] {\bl{$v_4$}};
%\draw[->,line width=1mm] (r4) -- (v4);
%\node (v3) [left=of v4] {\bl{$v_3$}};
%\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
%\node (v2) [left=of v3] {\bl{$v_2$}};
%\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
%\node (v1) [left=of v2] {\bl{$v_1$}};
%\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
%\draw[->,line width=0.5mm] (r3) -- (v3);
%\draw[->,line width=0.5mm] (r2) -- (v2);
%\draw[->,line width=0.5mm] (r1) -- (v1);
%\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
%\end{tikzpicture}
%\end{center}
%
%\small
%\hspace{4.5cm}\bl{$(b \cdot c) + (\ZERO + \ONE)$}
%$\mapsto$
%\bl{$(b \cdot c) + \ONE$}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[t]
% \begin{center}
% \bl{$\only<1>{(b \cdot c)}%
% \only<2-3>{(\underline{b \cdot c})}%
% \only<1-3>{+}%
% \only<1>{(\ZERO + \ONE)}%
% \only<2-3>{(\underline{\ZERO + \ONE})}$}%
% \only<4->{%
% \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}%
% }
% $\mapsto$
% \bl{$(b \cdot c) + \ONE$}
% \end{center}\bigskip
% \onslide<3->{%
% \begin{center}
% \begin{tabular}{lcl}
% \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\
% \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$}
% \end{tabular}
% \end{center}}
% \only<4>{%
% \begin{center}
% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
% \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\
% \quad \bl{$\lambda v.\,$}
% case \bl{$v = Left(v')$}:
% & return \bl{$Left(f_{s1}(v'))$}\\
% \quad \phantom{$\lambda v.\,$}
% case \bl{$v = Right(v')$}:
% & return \bl{$Right(f_{s2}(v'))$}\\
% \end{tabular}
% \end{center}}%
% \only<5->{%
% \begin{center}
% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
% \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\
% \quad \bl{$\lambda v.\,$}
% case \bl{$v = Left(v')$}:
% & return \bl{$Left(v')$}\\
% \quad \phantom{$\lambda v.\,$}
% case \bl{$v = Right(v')$}:
% & return \bl{$Right(Right(v'))$}\\
% \end{tabular}
% \end{center}}%
% \only<6->{%
% \begin{center}
% \begin{tabular}{@{}l@{\hspace{4mm}}l@{}}
% \bl{$\textit{mkeps}$} simplified case: &
% \bl{$\textit{Right}(\textit{Empty})$}\\
% rectified case: &
% \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$}
% \end{tabular}
% \end{center}}%
% \end{frame}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Records}
%
%\begin{itemize}
%\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
%
%\item \bl{$nullable(x:r) \dn nullable(r)$}
%\item \bl{$der\,c\,(x:r) \dn der\,c\,r$}
%\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}
%\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$}
%\end{itemize}\bigskip\bigskip\pause
%
%\small
%for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Environments}
Obtaining the ``recorded'' parts of a value:
\begin{center}
\begin{tabular}{lcl}
\bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\
\bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\
\bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
\bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
\bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\
\bl{$env(Stars [v_1,\ldots ,v_n])$} & \bl{$\dn$} &
\bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\
\bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{While Tokens}
\begin{center}
\begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
\pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\
& & \phantom{(}\pcode{("i" : ID)} +\\
& & \phantom{(}\pcode{("o" : OP)} + \\
& & \phantom{(}\pcode{("n" : NUM)} + \\
& & \phantom{(}\pcode{("s" : SEMI)} +\\
& & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\
& & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\
& & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\consolas
\begin{center}
\code{"if true then then 42 else +"}
\end{center}
\only<1>{
\small\begin{tabular}{l}
KEYWORD(if),\\
WHITESPACE,\\
IDENT(true),\\
WHITESPACE,\\
KEYWORD(then),\\
WHITESPACE,\\
KEYWORD(then),\\
WHITESPACE,\\
NUM(42),\\
WHITESPACE,\\
KEYWORD(else),\\
WHITESPACE,\\
OP(+)
\end{tabular}}
\only<2>{
\small\begin{tabular}{l}
KEYWORD(if),\\
IDENT(true),\\
KEYWORD(then),\\
KEYWORD(then),\\
NUM(42),\\
KEYWORD(else),\\
OP(+)
\end{tabular}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Coursework: PLs (16)}
%
%\begin{itemize}
%\item Java (16)
%\item C++, C, C\# (14)
%\item JavaScript (10)
%\item Scala (9)
%\item Python (9)
%\item PHP (6)
%\item Haskell (3)
%\item Ruby (4)
%\item Bash, Perl, Powershell (2)
%\item TypeScript (1)
%\item R (1)
%\item Coconut (1)
%\item Pascal (1)
%\end{itemize}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Coursework: Nullable}
%
%\begin{center}
%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
% \bl{$nullable([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(r^+)$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(r^?)$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(r^{\{n..\}})$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(r^{\{..n\}})$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(r^{\{n..m\}})$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(\sim{}r)$} & \bl{$\dn$} & $?$\\
%
%\end{tabular}
%\end{center}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%%%\frametitle{Coursework: der}
%
%\begin{center}
%\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}}
% \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\
% \bl{$der\, c\, (r^+)$} & \bl{$\dn$} & $?$\\
% \bl{$der\, c\, (r^?)$} & \bl{$\dn$} & $?$\\
% \bl{$der\, c\, (r^{\{n\}})$} & \bl{$\dn$} &
% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\
% \bl{$der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} &
% \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\
% & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\
% \bl{$der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} &
% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\
%
% \bl{$der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} &
% \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\
% \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\
% \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else
% \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\
% \bl{$der\, c\, (\sim{}r)$} & \bl{$\dn$} & $?$\\
%\end{tabular}
%\end{center}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Coursework: CFUN}
%
%\begin{center}
%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
% \bl{$nullable(CFUN(\_))$} & \bl{$\dn$} & \bl{$false$}\\
% \bl{$der\,c\,(CFUN(f))$} & \bl{$\dn$} &
% \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\
% \bl{$CHAR(c)$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\
% \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\
% \bl{$ALL$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\
%\end{tabular}
%\end{center}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}<1-28>[c]
\end{frame}
\begin{frame}[c]
\begin{center}
\begin{tabular}{cc}
\includegraphics[scale=0.27]{s1.png} &
\includegraphics[scale=0.27]{s2.png} \\
\includegraphics[scale=0.27]{s3.png} &
\includegraphics[scale=0.27]{s4.png} \\
\end{tabular}
\end{center}
\end{frame}
\begin{frame}[c]
\begin{center}
\begin{tabular}{cc}
\includegraphics[scale=0.27]{s5.png} &
\includegraphics[scale=0.27]{s6.png} \\
\includegraphics[scale=0.27]{s7.png} &
\includegraphics[scale=0.27]{s8.png} \\
\end{tabular}
\end{center}
\end{frame}
\begin{frame}[c]
\begin{center}
\begin{tabular}{cc}
\includegraphics[scale=0.3]{s9.png} &
\includegraphics[scale=0.3]{s10.png}
\end{tabular}
\end{center}
\end{frame}
\begin{frame}[c]
\small
\begin{itemize}
\item[$\bullet$] I'm impressed by the speed of the answers on KEATS,
even on weekends. It's amazing. Obviously, the lecturer cares about
the students.\pause
\item[$\bullet$] The handouts and materials on KEATS are very
helpful and your explanation is easy to understand especially
after both reading the handout and watch the lectures. The LGT is
also engaging and I will try my best to engage more. I am actually
already impressed by your teaching since 5CCS2PEP.\pause
\item[$\bullet$] I believe the module is great, if possible, it
would be nice to have a small handout that recaps Scala syntax
from PEP last year.
\end{itemize}
\end{frame}
\begin{frame}[c]
\small
\begin{itemize}
\item[$\bullet$] While I understand you want people to attend the
small groups, not providing the solutions to the homework
exercises disadvantages those with disabilities (e.g. processing
difficulties) as most students take notes of the solutions during
the SGTs, and those of us who are unable to do so cannot obtain
the full benefit of the sessions. Even if the exam is based on
those questions, it is closed-book anyway, so there is no harm in
providing the answers. At least allow the TAs to give the
solutions to those who attend the SGTs please?
\item[$\bullet$] Really enjoy the content, but would appreciate
uploads of the tutorial answers as sometimes we do not have time
to go through all of them in the SGTs.
\end{itemize}
\end{frame}
\begin{frame}[c]
\small
\begin{itemize}
\item[$\bullet$] CFL is a very interesting module and the LGTs are
helpful to consolidate information. The homeworks and courseworks
are useful for learning the content. My only criticism is that it
feels like there is too much content crammed into each
week. Between the time taken each week by 2h LGT, 1h SGT, 3-4h of
videos, 1-2h homework and time for courseworks, I find it
difficult making time for all aspects of this module each week.
\end{itemize}
\end{frame}
\begin{frame}[c]
\small
\begin{itemize}
\item[$\bullet$] i like this course
\item[$\bullet$] I could learn the material better if the LGTs could
somehow be recorded because I've sometimes felt a need to go back
to them while revising stuff
\item[$\bullet$] I feel that, as with most modules, there is a lot
happening at once. Since we only went through the first coursework
it's too early to call, but the workload tends to pile up. I
understand it's in the nature of the module, and the work, though
difficult, is enjoyable, but there's gotta be a way to mitigate
this. Other than that, I am enjoying this module and you, Chris,
are a great lecturer!
\end{itemize}
\end{frame}
\begin{frame}[c]
\small
\begin{itemize}
\item[$\bullet$] Strongly advise you, the lecturer, to take into
account that your students have not been studying the subject for
as long as you have. Also, that some of us are still waiting to be
convinced of the interesting-ness and relevance of the subject,
which you often fail to mention in the sessions and in the
videos. I find myself lost trying to find a context for the things
we are learning.
\ldots
I thoroughly enjoy the SGTS where my concerns and questions are
welcomed. But I feel uncomfortable to ask you questions in your
LGTs because of the way I have heard you respond to other
students.
\end{itemize}
\end{frame}
\end{document}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: