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

