slides/slides04.tex
author Christian Urban <christian.urban@kcl.ac.uk>
Sat, 21 Oct 2023 09:09:09 +0100
changeset 943 5365ef60707e
parent 940 46eee459a999
child 953 5e070fb0332a
permissions -rw-r--r--
updated

% !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: & Thurdays 15 -- 16\\  
  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{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{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]
  \frametitle{Week 3 Feedback}
  \begin{center}
  \includegraphics[scale=0.30]{s0.png}
  \end{center}
\end{frame}


\begin{frame}[c]
  \begin{center}
  \begin{tabular}{cc}  
  \includegraphics[scale=0.20]{s1.png} &
  \includegraphics[scale=0.20]{s2.png} \\
  \includegraphics[scale=0.20]{s3.png} &
  \includegraphics[scale=0.20]{s4.png} \\
  \end{tabular}                                      
  \end{center}
\end{frame}

\begin{frame}[c]
  \begin{center}
  \begin{tabular}{cc}  
  \includegraphics[scale=0.20]{s5.png} &
  \includegraphics[scale=0.20]{s6.png} \\
  \includegraphics[scale=0.20]{s7.png} &
  \includegraphics[scale=0.20]{s8.png} \\
  \end{tabular}                                      
  \end{center}
\end{frame}

\begin{frame}[c]
  \begin{center}
  \begin{tabular}{cc}  
    \includegraphics[scale=0.20]{s9.png} &
    \includegraphics[scale=0.20]{s10.png} 
  \end{tabular}                                      
  \end{center}
\end{frame}



\begin{frame}[c]
  \small
  \begin{itemize}
  \item[$\bullet$] Great lecturer. Looking forward to the next lecture!
    
  \item[$\bullet$] Would it be possible for you to post the answer of
    the homework to KEATS after sgts each week? It will be very
    helpful for us to prepare for the exam. Thank you.

  \item[$\bullet$] A lot of the parts of the LGT are going through
    what was covered in the videos. While this is helpful to refresh
    students' minds, I think it would be better if the Pollev
    questions were checked more regularly to focus on what students
    want support with
  \end{itemize}\bigskip

  $\Rightarrow$ Reluctant, but I am prepared for selected questions to
  make the answers public.

  $\Rightarrow$ The content viewing numbers are a bit worrying. Therefore
  the reflex on my side to lecture the content again.
\end{frame}

\begin{frame}[c]
  \small
  \begin{minipage}{1.3\textwidth}
  \begin{itemize}
  \item[$\bullet$]
    Regarding module content, the content is not only interesting but relevant, up-to-date, and applicable to the real world. The practical, real-world application of the module is made abundantly clear through the coursework-focused delivery of the module. The content of the module progresses fast, but that is due to the nature of the content and the aims of the module. The learning aims and assessment are clearly explained.

Regarding teaching, Dr. Urban is incredibly helpful both inside (and even outside) contact hours. I can tell the lecturer is very passionate about teaching the module. TAs are on hand to help with all aspects of the module, with the lecturer having taken care to have dedicated TAs for resolving technical issues. Discussions both on the forum and in lessons are encouraged, and the module is structured so that high engagement with the content and live lessons will make it easier for students to do the module (which is, of course, a good thing).

Only 3 weeks in I would very highly recommend the module. It is a difficult subject, but a pleasure to study at the same time.
\end{itemize}
\end{minipage}
\end{frame}

\begin{frame}[c]
  \small
  \begin{minipage}{1.2\textwidth}
  \begin{itemize}  
  \item[$\bullet$] Professor Christian is incredibly patient. He always stays longer after live session lectures to answer additional questions, even though he doesn't need to. He made me feel that no questions are stupid. Thanks so much!
    
  \item[$\bullet$] I am enjoying your module at the moment, I think you clearly explain every point and answer all questions during the live tutorial.
    
  \item[$\bullet$] It would be helpful to be given the full set of coursework templates on GitHub so that there is less ambiguity regarding future courseworks.
    
\item[$\bullet$] Maybe some additional exercises in the LGT would be useful
\item[$\bullet$] This module handout are the most useful thing I have ever seen in this uni.
\item[$\bullet$] This module is structured very well and is very interesting. Thank you
\end{itemize}
$\Rightarrow$ In case of CW3 the starting files are comb1.sc and comb2.sc uploaded to KEATS.
\end{minipage}
\end{frame}


\begin{frame}[c]
  \begin{center}
    \includegraphics[scale=0.30]{~/Desktop/feynman-teaching.jpeg}
  \end{center}
\end{frame}

\end{document}


%%% Local Variables:  
%%% mode: latex
%%% TeX-master: t
%%% End: