% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../graphicss}
\usepackage{../langs}
\usepackage{../data}
\usetikzlibrary{cd}
\usepackage{listings-rust}
\usepackage{ulem}

\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}



\hfuzz=220pt 

\lstset{language=Scala,
        style=mystyle,
        numbersep=0pt,
        numbers=none,
        xleftmargin=0mm}

\newcommand{\bl}[1]{\textcolor{blue}{#1}}     
 
% beamer stuff 
\renewcommand{\slidecaption}{CFL 01, King's College London}

%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect1/main.pdf
%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect2/main.pdf
%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect3/main.pdf


\begin{document}

%\begin{frame}[t]
%
%\begin{mybox}
%A physical explanation the \emph{dynamic matrix}\\
%lots of text
%\end{mybox}


%\begin{mybox2}{Test}
%A physical explanation the \emph{dynamic matrix}\\
%lots of text
%\end{mybox2}

%\begin{mybox3}{Test}
%A physical explanation the \emph{dynamic matrix}\\
%lots of text
%\end{mybox3}
% \end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[t]
%\frametitle{%  
%  \begin{tabular}{@ {}c@ {}}
%  \\[-3mm]
%  \LARGE Lunch with a Lecturer (29 March)\\[5mm] 
%  \end{tabular}}
%
%  I teach CFL (compilers) and PEP (Scala)\bigskip
%
%  \begin{itemize}
%  \item did undergraduate in Germany
%  \item Master in St Andrews
%  \item PhD in Cambridge  
%  \end{itemize}\bigskip\bigskip
%
%  use mainly the Isabelle theorem prover in my work (see 6CCS3VER)
%
%  write code in functional programming languages (Scala, SML, Ocaml, Haskell)
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c]
% \frametitle{Why Bother with Regexes?}

% \begin{columns}[t,onlytextwidth]
% \begin{column}{1.8cm}
% \mbox{}   
% \end{column}    
% \begin{column}{.5\textwidth}
% \small{}Ruby, Python, Java 8\medskip\\
% \begin{tikzpicture}\footnotesize
% \begin{axis}[
%     xlabel={$n$},
%     x label style={at={(1.05,0.0)}},
%     ylabel={time in secs},
%     enlargelimits=false,
%     xtick={0,5,...,30},
%     xmax=33,
%     ymax=35,
%     ytick={0,5,...,30},
%     scaled ticks=false,
%     axis lines=left,
%     width=\textwidth,
%     height=4cm, 
%     legend entries={Python,Ruby},  
%     legend pos=north west,
%     legend cell align=left]
% \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
% \addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data};
% \end{axis}
% \end{tikzpicture}
% \begin{tikzpicture}\footnotesize
% \begin{axis}[
%     xlabel={$n$},
%     x label style={at={(1.05,0.0)}},
%     ylabel={time in secs},
%     enlargelimits=false,
%     xtick={0,5,...,30},
%     xmax=33,
%     ymax=35,
%     ytick={0,5,...,30},
%     scaled ticks=false,
%     axis lines=left,
%     width=\textwidth,
%     height=4cm, 
%     legend entries={Python, Java 8, JavaScript, Swift},  
%     legend pos=north west,
%     legend cell align=left]
% \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};   
% \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
% \addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
% \addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
% \end{axis}
% \end{tikzpicture}
% %
% \end{column}
% \begin{column}{.5\textwidth}
% \small{}In PEP \& CFL \medskip\\
% \begin{tikzpicture}\footnotesize
% \begin{axis}[
%     xlabel={$n$},
%     x label style={at={(1.07,0.0)}},
%     ylabel={time in secs},
%     enlargelimits=false,
%     xtick={0,5000,...,10000},
%     xmax=11000,
%     ymax=35,
%     ytick={0,5,...,30},
%     scaled ticks=false,
%     axis lines=left,
%     width=\textwidth,
%     height=4cm]
% \addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
% \addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
% \end{axis}
% \end{tikzpicture}
% \begin{tikzpicture}\footnotesize
% \begin{axis}[
%     xlabel={$n$},
%     x label style={at={(1.07,0.0)}},
%     ylabel={time in secs},
%     enlargelimits=false,
%     ymax=35,
%     ytick={0,5,...,30},
%     scaled ticks=false,
%     axis lines=left,
%     width=\textwidth,
%     height=4cm]
% \addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
% \end{axis}
% \end{tikzpicture}
% \end{column}
% \end{columns}
% \medskip

% \begin{textblock}{3}(-0.1,3.3)
% \small\hfill\bl{\texttt{[a?]\{n\}[a]\{n\}}}:
% \end{textblock}

% \begin{textblock}{3}(-0.1,8.7)  
% \small\hfill\bl{\texttt{(a*)*b}}:
% \end{textblock}

% \begin{textblock}{3}(0.3,13)
% \small{}matching with strings
% \bl{$\underbrace{\texttt{a}...\texttt{a}}_n$}  
% \end{textblock}

% \end{frame} 
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c,fragile]
%   \frametitle{Incidents}
    
%   \begin{itemize}
%   \item a global outage on 2 July 2019 at \textbf{Cloudflare} 
%   (first one for six years)\medskip
  
%   \begin{center}\small\color{blue}
%   \begin{verbatim}  
%   (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|
%   null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s
%   |-|~|!|{}|\|\||\+)*.*(?:.*=.*)))  
%   \end{verbatim}
%   \end{center}\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip    
  
%   \item on 20 July 2016 the \textbf{Stack Exchange} webpage went down
%     because of an evil regular expression
%     \here{https://stackstatus.tumblr.com/post/147710624694/outage-postmortem-july-20-2016}    
%   \end{itemize}
  
%   \begin{textblock}{6}(6,7.6)
%     \includegraphics[scale=0.14]{../pics/cloudflare.png}\\
%     \footnotesize
%     It serves more web traffic than Twitter, Amazon, Apple,
%     Instagram, Bing \& Wikipedia combined.
%     \here{https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/}
%     \end{textblock}
  
%   \end{frame}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
    
% %\begin{frame}[c]
% %
% %\frametitle{}
% %\begin{mybox3}{}\it
%  ``This conversation is interesting to me, and I've researched it a little bit... I also disagree with Dr. Urban on the cost/benefit of non-GC languages...[..]\\
%
%  But regardless, Scala is a lot slower than, say, C or Rust. To say it's not is basically wrong (imo)....[..]
%  ''\\
%\mbox{}\hfill-- Oliver Iliffe,  discussion this year in PEP
%\end{mybox3}\pause
%
%\end{frame}

%\begin{frame}<1-10>
%\end{frame}  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%  
  \begin{tabular}{@ {}c@ {}}
  \\[-3mm]
  \LARGE Compilers and \\[-1mm] 
  \LARGE Formal Languages\\[-3mm] 
  \end{tabular}}

  

  \normalsize
  \begin{center}
  \begin{tabular}{ll}
  Email:  & christian.urban at kcl.ac.uk\\
  Office Hour: & Fridays 11:30 -- 12:30\\
  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
          \cellcolor{blue!50}
          1 Introduction, Languages          & 6 While-Language \\
          2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
          3 Automata, Regular Languages      & 8 Compiling Functional Languages \\
          4 Lexing, Tokenising               & 9 Optimisations \\
          5 Grammars, Parsing                & 10 LLVM \\ \hline
        \end{tabular}%
      };
    \end{tikzpicture}
  \end{center}


  \begin{textblock}{5}(12,3)
  \includegraphics[scale=0.35]{qr01}\\
  \small Wifi: IET-Guest
  \end{textblock} 
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}<1-12>[c]
\frametitle{The Goal of this Module\ldots}

\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 \ldots{} you write a compiler};

  \node (0) at (-2.3,0) {};  
  \node [above=5mm of 0]
  {\makebox[0mm]{\footnotesize
      \begin{tabular}{@{}l@{}}input\\[-1mm]program\end{tabular}}}; 
     
  \node (A) at (0,0)  [node] {};
  \node [below right] at (A.north west) {lexer};

  \node (B) at (3,0)  [node] {};
  \node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser};

  \node (C) at (6,0)  [node] {};
  \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen};

  \node (1) at (8.4,0) {};
  \node [above=5mm of 1]
  {\makebox[0mm]{\footnotesize
      \begin{tabular}{@{}r@{}}binary\\[-1mm]code\end{tabular}}};

  \draw [->,line width=3mm] (0) -- (A); 
  \draw [->,line width=3mm] (A) -- (B); 
  \draw [->,line width=3mm] (B) -- (C); 
  \draw [->,line width=3mm] (C) -- (1); 
  \end{tikzpicture}
  \end{center}

\only<2,3,4>{
\begin{textblock}{1}(1,2.1)
\begin{bubble}[9.8cm]
\normalsize
lexer input: a string\smallskip\\
\hspace{5mm}\code{"read(n);"}\medskip\\
lexer output: a sequence of tokens\smallskip\\
\hspace{5mm}\code{key(read) lpar id(n) rpar semi}
\end{bubble}
\end{textblock}} 

\only<3,4>{
\begin{textblock}{1}(6,7.8)
\begin{tabular}{c}
\includegraphics[scale=0.2]{../pics/rosetta.jpg}\\[-2mm]
\footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta)
\end{tabular}
\end{textblock}}

\only<4>{
\begin{textblock}{1}(0.5,12)\small
\begin{tabular}{l@{}c@{}l}
  \pcode{if}    & $\;\Rightarrow\;$ & keyword\\
  \pcode{iffoo} & $\;\Rightarrow\;$ & identifier\\
\end{tabular}  
\end{textblock}}

\only<6>{
\begin{textblock}{1}(1,1.5)
\begin{bubble}[8.5cm]
\normalsize
parser input: a sequence of tokens\smallskip\\

{\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\

parser output: an abstract syntax tree\smallskip\\
\footnotesize
\hspace{2cm}\begin{tikzpicture}
  \node {\code{read}}
    child {node {\code{lpar}}}
    child {node {\code{n}}}
    child {node {\code{rpar}}};
\end{tikzpicture}
\end{bubble}
\end{textblock}}

\only<8,9>{
\begin{textblock}{1}(1,1.5)
\begin{bubble}[4cm]
\normalsize
code generation:\smallskip\\
\hspace{5mm}\code{istore 2}\\ 
\hspace{5mm}\code{iload 2}\\ 
\hspace{5mm}\code{ldc 10}\\
\hspace{5mm}\code{isub}\\
\hspace{5mm}\code{ifeq Label2}\\ 
\hspace{5mm}\code{iload 2}\\
\hspace{5mm}\code{...}\\
\end{bubble}
\end{textblock}}

\only<9>{
\begin{textblock}{6}(8.4,7)
\begin{bubble}[5cm]
\mbox{\begin{tikzpicture}[scale=0.58,rounded corners=0mm]
\begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs,
    xlabel=n,
    enlargelimits=0.05,
    ybar interval=0.7, legend style=small]
\addplot file {interpreted2.data};
\addplot file {compiled2.data};
%\legend{interpreted, compiled}
\end{axis}
\end{tikzpicture}}
\end{bubble}
\end{textblock}}

\only<10>{
\begin{textblock}{6}(1,3)
  \begin{bubble}[11cm]
    Compiler explorers, e.g.: \url{https://gcc.godbolt.org} \;\video{https://youtu.be/ysaBmhMEyUg}
  \begin{tikzpicture}[]
  \node (0) at (-2.3,0) {\includegraphics[scale=0.3]{pics/csource.png}};
  \node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}}; 
  \draw [->,line width=4mm, red] (0) -- (1);   
  \node (2) [below=20mm] at (0) {\LARGE\bf source};
  \node (3) [right=40mm] at (2) {\LARGE\bf binary};
  \draw [->,line width=1mm] (2) -- (3);   
\end{tikzpicture}
\end{bubble}

\end{textblock}}
\only<11>{
\begin{textblock}{6}(1,3)
  \begin{bubble}[11cm]
    Compiler explorer for Java: \url{https://javap.yawk.at} 
  \begin{tikzpicture}[]
  \node (0) at (-2.3,0) {\includegraphics[scale=0.4]{pics/jsource.png}};
  \node (1) [right=35mm] at (0) {\includegraphics[scale=0.4]{pics/jassmbl.png}}; 
  \draw [->,line width=4mm, red] (0) -- (1);   
  \node (2) [below=20mm] at (0) {\LARGE\bf source};
  \node (3) [right=40mm] at (2) {\LARGE\bf byte code};
  \draw [->,line width=1mm] (2) -- (3);   
\end{tikzpicture}
\end{bubble}
\end{textblock}}


\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Why Study Compilers?}


John Regehr {\small(Univ.~Utah, LLVM compiler hacker)}
\here{https://blog.regehr.org/archives/1419}
\smallskip\\

\begin{bubble}[10.5cm]
  \bf ``\ldots{}It’s effectively a perpetual
  employment act for solid compiler hackers.''
\end{bubble}

\onslide<1->{
\only<2>{
\begin{itemize}
\item {\bf Hardware is getting weirder
  rather than getting clocked faster.}

\begin{itemize}
\item[]  ``Almost all processors are multicores nowadays and it looks
  like there is increasing asymmetry in resources across cores.
  Processors come with vector units, crypto accelerators etc. We have
  DSPs, GPUs, ARM big.little, and Xeon Phi. This is only scratching the
  surface.''
\end{itemize}  
\end{itemize}}
\only<3>{
\begin{itemize}
\item {\bf We’re getting tired of low-level languages and
    their associated security disasters.}
  
\begin{itemize}
\item [] ``We want to write new code, to whatever extent possible, in
  safer, higher-level languages. Compilers are caught right in the
  middle of these opposing trends: one of their main jobs is to help
  bridge the large and growing gap between increasingly high-level
  languages and increasingly wacky platforms.''
\end{itemize}  
\end{itemize}}}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% {
% \setbeamercolor{background canvas}{bg=cream}
% \begin{frame}[c]

% \frametitle{}
% \begin{mybox3}{}\it
%    ``I enjoyed the module - it was genuinely the stand out academic
% experience of my undergraduate degree, and very much influenced my
% career interests. In fact I am currently working at ARM, in their Open
% Source Software group, on AArch64 specific optimisations for the
% Java/Kotlin compiler that forms part of the Android Runtime.''\\
% \mbox{}\hfill-- Hari Limaye in year 2021/22
% \end{mybox3}\pause


% Student numbers in CFL\medskip\\
% \begin{tabular}{ll}
% 2019: & 32\\  
% 2020: & 59\\  
% 2021: & 109\\
% 2022: & 121\\  
% \end{tabular}  

% \end{frame}
% }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Why Bother with Compilers?}
  
\textbf{Boeing 777's}: First flight in 1994. They want to achieve
triple redundancy for potential hardware faults.
\here{https://ieeexplore.ieee.org/document/495891}\bigskip
  
They compile 1 Ada program to\medskip
  
\begin{itemize}
  \item Intel 80486
  \item Motorola 68040 (old Macintosh's)
  \item AMD 29050 (RISC chips used often in laser printers)
\end{itemize}\medskip\medskip
  
using 3 independent compilers.\bigskip\pause
  
\small Airbus uses C and static analysers. Recently started using CompCert.

\only<1->{%
\begin{textblock}{6}(8,4.5)
\includegraphics[scale=0.28]{../pics/777.png}
\end{textblock}}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{What Do Compilers Do?}

Remember BF*** from PEP?

\begin{center}
\begin{tabular}{rcl}
\bl{\texttt{>}} & $\Rightarrow$ & move one cell right\\
\bl{\texttt{<}} & $\Rightarrow$ & move one cell left\\
\bl{\texttt{+}} & $\Rightarrow$ & increase cell by one\\
\bl{\texttt{-}} & $\Rightarrow$ & decrease cell by one\\
\bl{\texttt{.}} & $\Rightarrow$ & print current cell\\
\bl{\texttt{,}} & $\Rightarrow$ & input current cell\\
\bl{\texttt{[}} & $\Rightarrow$ & loop begin\\
\bl{\texttt{]}} & $\Rightarrow$ & loop end\medskip\\
                & $\Rightarrow$ & everything else is a comment\\
\end{tabular}  
\end{center}  

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
  \frametitle{A ``Compiler'' for BF*** to C}
  
  \begin{center}
  \begin{tabular}{rcl}
  \bl{\texttt{>}} & $\Rightarrow$ & \texttt{ptr++}\\
  \bl{\texttt{<}} & $\Rightarrow$ & \texttt{ptr--}\\
  \bl{\texttt{+}} & $\Rightarrow$ & \texttt{(*ptr)++}\\
  \bl{\texttt{-}} & $\Rightarrow$ & \texttt{(*ptr)--}\\
  \bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\
  \bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\
  \bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\
  \bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\
                  & $\Rightarrow$ & ignore everything else\\
  \end{tabular}  
  \end{center}\bigskip  
  
  \texttt{char field[30000]\\ char *ptr = \&field[15000]}
  
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
  \frametitle{Another~``Compiler''~for~BF~to~C}
  
  \begin{center}
  \begin{tabular}{rcl}
  \bl{\texttt{>\ldots>}} & $\Rightarrow$ & \texttt{ptr += n}\\
  \bl{\texttt{<\ldots<}} & $\Rightarrow$ & \texttt{ptr -= n}\\
  \bl{\texttt{+\ldots+}} & $\Rightarrow$ & \texttt{(*ptr) += n}\\
  \bl{\texttt{-\ldots-}} & $\Rightarrow$ & \texttt{(*ptr) -= n}\\
  \bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\
  \bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\
  \bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\
  \bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\
                  & $\Rightarrow$ & ignore everything else\\
  \end{tabular}  
  \end{center}\bigskip  
  
  \texttt{char field[30000]\\ char *ptr = \&field[15000]}
  
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{A Brief Compiler History}

\bigskip
\begin{itemize}
\item Turing Machines, 1936 (a tape as memory)
\item Regular Expressions, 1956\\
\item The first compiler for COBOL, 1957\\ (Grace Hopper)\medskip
\item But surprisingly research papers are still published nowadays\\
\item ``Parsing: The Solved Problem That Isn't''
  \here{https://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt.html}
\end{itemize}


\begin{textblock}{8.5}(5,7.6)
\begin{flushright}
\includegraphics[scale=0.3]{pics/hopper.jpg}\\
\footnotesize\textcolor{gray}{Grace Hopper}\smallskip\\

{\small\textcolor{gray}{(she made it to David Letterman's Tonight Show
    \here{https://youtu.be/oE2uls6iIEU})}}
\end{flushright}
\end{textblock}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c]
\frametitle{How to study for CFL?}

My recommendation for each week: 

\begin{itemize}
\item read the handout
\item watch the videos
\item re-read the handout
\item do the HW to be discussed at the SGT
\item \textcolor{red}{play with the uploaded code}
\item later on do the CW
\end{itemize}


\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c]
\frametitle{Some Housekeeping}

\textbf{Exam will be computer-based, invigilated in some big examination hall:}\bigskip

\begin{itemize}
\item final exam in January (\textbf{40\%})
\item coursework (\textbf{60\%- the first part is optional}) 
\end{itemize}\bigskip\bigskip\pause


\textbf{Weekly Homework (optional):}
\begin{itemize}
\item uploaded on KEATS - solutions will be discussed during the SGTs
\item \alert{\bf all} questions in the exam will be in some close shape or form from the HWs!!
\end{itemize}  

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c]
\frametitle{Homework}

Until 3 years ago: I did not give out solutions; students
sent emails to me and I responded to them individually.\bigskip\\

Now: TAs will review the homework mainly during the SGTs.\bigskip\\\pause

Do not harass your TAs for the solutions!

\end{frame}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
{\definecolor{rred}{HTML}{C0504D}
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c]
\frametitle{Students in CFL}

\begin{center}
\begin{tikzpicture}
  \begin{axis}[symbolic x coords={2016,2017,2018,2019,2020,2021,2022,2023,2024,2025},
    width  = 1.2\textwidth,
    height = 5cm,
    bar width=8mm,
    nodes near coords,
    axis lines = left,
    text=black,
    ymin=0,
    clip=false,
    hide y axis,
    axis line style={-},
    name=mygraph
    ]

\only<1>{\addplot[ybar,style={rred,fill=rred!75,mark=none},text=black] coordinates {
(2025,181)
(2024,173)
(2023,169)
(2022,111)
(2021,98)
(2020,59)
(2019,38)
(2018,20)
(2017,22)
(2016,8)}};
\end{axis}
\node[anchor=north, yshift=-10mm] at (mygraph.south) {\small{}Student numbers since the start of the compiler module.};

\end{tikzpicture}
\end{center}


\end{frame}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c]
\frametitle{Some Housekeeping}

\textbf{Coursework (4 parts accounting for 60\%; submission deadline \underline{5th January 2026}):}\bigskip

\begin{itemize}
\item matcher \xout{(5\%)}\;\;\textcolor{red}{optional}
\item lexer (10\%)
\item parser / interpreter (15\%)
\item JVM compiler (15\%)
\item LLVM compiler (20\%) 
\end{itemize}
\end{frame}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c]
\frametitle{Some Housekeeping}

\begin{itemize}
\item you can use any code I show you and is uploaded to KEATS; therefore 
  most students use Scala/Ammonite
\item but you can use \alert{any} programming language you like (Haskell, Rust, Swift\ldots you have to show me how to run your code)
\pause
\item \textcolor{red}{\textbf{you can even use AI for CW}}\pause\bigskip 
\item \textbf{BUT YOU CANNOT COPY FROM OR COLLABORATE WITH OTHER STUDENTS!}
\end{itemize}
\end{frame}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%{
%\setbeamercolor{background canvas}{bg=cream}
%\begin{frame}[c,fragile]
%\end{frame}  
%}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c,fragile]
%%\frametitle{Scala 3}

I will show you all my code in Scala 3\bigskip

\begin{minipage}{1.4\textwidth}
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
$ scala
Welcome to Scala 3.7.3 (21.0.8, Java OpenJDK 64-Bit Server VM).
Type in expressions for evaluation. Or try :help.

scala> 1 + 2
res0: Int = 3
\end{lstlisting} %% $
\end{minipage}\medskip
\pause

%Since Scala 3.5.0, scala-cli is included in "plain" Scala
%
%\begin{minipage}{1.4\textwidth}
%\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
%$ scala
%Welcome to Scala 3.5.1 (21.0.4, Java OpenJDK 64-Bit Server VM).
%Type in expressions for evaluation. Or try :help.
%
%scala> 
%\end{lstlisting} %% $
%\end{minipage}
\end{frame}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c,fragile]
\frametitle{Ammonite \& Scala 3}

Actually in CFL, I will use Amm / Scala 3

\begin{minipage}{1.4\textwidth}
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
$ amm
Loading...
Welcome to the Ammonite Repl 3.0.2 (Scala 3.3.5 Java 21.0.8)
@ 1 + 2
res0: Int = 3
\end{lstlisting} %% $
\end{minipage}\medskip
\pause

Do not use Amm + Scala 2! Do not use sbt!

\begin{minipage}{1.4\textwidth}
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
$ amm2
Loading...
Welcome to the Ammonite Repl 2.5.9 (Scala 2.13.11 Java 17.0.7)
@ 
\end{lstlisting} %% $
\end{minipage}
\end{frame}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c]
\frametitle{For Install and GitHub Problems}
 
\begin{itemize}
\item Flavio Melinte Citea\\ (flavio.melinte\_citea@kcl.ac.uk)\bigskip \\
\item Zishan Rahman\\ (zishan.rahman@kcl.ac.uk) 
\end{itemize}
  
\end{frame}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c]

\begin{minipage}{1.3\textwidth}
\begin{mybox3}{}\it\small
Unequivocally the worst module I've taken on this course. The subject
matter is fascinating, however the insistence on the use of this
abomination of a language "Scala" completely ruins it. If you're going
to teach something as complex as this, use a proper language, not some
"object oriented functional" abomination. Use C, you know, the
language that real compilers are written in. I will go to the end of
the earth to dissuade others from taking this module so long as Scala
is still being used.\\
\mbox{}\hfill-- Lone voice in the end-of-year feedback in 2019
\end{mybox3}
\end{minipage}\bigskip

\small (for alternative opinions check ``What the students say'' on KEATS)
  
\end{frame}
}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Lectures 1 - 5}

transforming strings into structured data\\[10mm]

{\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\
\hspace{5mm}(recognising ``words'')\\[6mm]

{\LARGE\bf Parsing}\medskip\\
\hspace{5mm}(recognising ``sentences'')

\begin{textblock}{1}(10,9.1)
\begin{tabular}{c}
\includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm]
\footnotesize Stone of Rosetta
\end{tabular}
\end{textblock}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Lectures 1 - 5}

transforming strings into structured data\\[10mm]

{\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\
\hspace{5mm}(recognising ``words'')\\[6mm]

{\LARGE\bf Parsing}\medskip\\
\hspace{5mm}(recognising ``sentences'')

\begin{textblock}{1}(10,9.1)
\begin{tabular}{c}
\includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm]
\footnotesize Stone of Rosetta
\end{tabular}
\end{textblock}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
  \frametitle{Lectures 5 - 10}
  
  code generation for a small imperative and a small functional language\\[10mm]
  
  {\LARGE\bf Interpreters}\medskip\\
  \hspace{5mm}(directly runs a program)\\[6mm]
  
  {\LARGE\bf Compilers}\medskip\\
  \hspace{5mm}(generate JVM code and LLVM-IR code)
  
  \begin{textblock}{1}(8.8,8.1)
  \begin{tabular}{c@{}c}
    \includegraphics[scale=0.4]{../pics/javaduke.png} &
    \includegraphics[scale=0.23]{../pics/llvmlogo.png}
  \end{tabular}
  \end{textblock}
  
  \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Familiar Regular Expresssions}
\small
\begin{center}
\texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{2,6\}}
\end{center}\smallskip

\begin{center}
\begin{tabular}{@{}lp{8.5cm}@{}}
\pcode{re*} & matches 0 or more times\\
\pcode{re+} & matches 1 or more times\\
\pcode{re?} & matches 0 or 1 times\\
\pcode{re\{n\}}	& matches exactly \pcode{n} number of times\\
\pcode{re\{n,m\}} & matches at least \pcode{n} and at most {\tt m} times\\
\pcode{[...]} & matches any single character inside the brackets\\
\pcode{[^...]} & matches any single character not inside the 
brackets\\
\pcode{a-z A-Z} & character ranges\\
\pcode{\\d} & matches digits; equivalent to \pcode{[0-9]}\\
\pcode{.} & matches every character except newline\\
\pcode{(re)}	& groups regular expressions and remembers 
the matched text
\end{tabular}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[t]
\frametitle{Notation for REs}
  
\end{frame}  
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[t]
  
\end{frame}  
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Some ``innocent'' examples}

Let's try two examples

\begin{center}
  \bl{\texttt{(a*)*b}}
  \hspace{2cm}
  \bl{\texttt{[a?]\{n\}[a]\{n\}}}
\end{center}\bigskip\pause  

and match them with strings of the form

\begin{center}
  \bl{\texttt{a}},
  \bl{\texttt{aa}},
  \bl{\texttt{aaa}},
  \bl{\texttt{aaaa}},
  \bl{\texttt{aaaaa}},
  \bl{$\underbrace{\texttt{a}...\texttt{a}}_n$}  
\end{center}  

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Why Bother with Regexes?}

\begin{columns}[t,onlytextwidth]
\begin{column}{1.8cm}
\mbox{}   
\end{column}    
\begin{column}{.5\textwidth}
\small{}Ruby, Python, Java 8\medskip\\
\begin{tikzpicture}\footnotesize
\begin{axis}[
    xlabel={$n$},
    x label style={at={(1.05,0.0)}},
    ylabel={time in secs},
    enlargelimits=false,
    xtick={0,5,...,30},
    xmax=33,
    ymax=35,
    ytick={0,5,...,30},
    scaled ticks=false,
    axis lines=left,
    width=\textwidth,
    height=4cm, 
    legend entries={Python,Ruby},  
    legend pos=north west,
    legend cell align=left]
\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
\addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data};
\end{axis}
\end{tikzpicture}
\begin{tikzpicture}\footnotesize
\begin{axis}[
    xlabel={$n$},
    x label style={at={(1.05,0.0)}},
    ylabel={time in secs},
    enlargelimits=false,
    xtick={0,5,...,30},
    xmax=33,
    ymax=35,
    ytick={0,5,...,30},
    scaled ticks=false,
    axis lines=left,
    width=\textwidth,
    height=4cm, 
    legend entries={Python, Java 8, JavaScript, Swift},  
    legend pos=north west,
    legend cell align=left]
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};   
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
\end{axis}
\end{tikzpicture}
%
\end{column}
\begin{column}{.5\textwidth}
\small{}Us (after next lecture)\medskip\\
\begin{tikzpicture}\footnotesize
\begin{axis}[
    xlabel={$n$},
    x label style={at={(1.07,0.0)}},
    ylabel={time in secs},
    enlargelimits=false,
    xtick={0,5000,...,10000},
    xmax=11000,
    ymax=35,
    ytick={0,5,...,30},
    scaled ticks=false,
    axis lines=left,
    width=\textwidth,
    height=4cm]
\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
\end{axis}
\end{tikzpicture}
\begin{tikzpicture}\footnotesize
\begin{axis}[
    xlabel={$n$},
    x label style={at={(1.07,0.0)}},
    ylabel={time in secs},
    enlargelimits=false,
    ymax=35,
    ytick={0,5,...,30},
    scaled ticks=false,
    axis lines=left,
    width=\textwidth,
    height=4cm]
\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
\end{axis}
\end{tikzpicture}
\end{column}
\end{columns}
\medskip

\begin{textblock}{3}(-0.1,3.3)
\small\hfill\bl{\texttt{[a?]\{n\}[a]\{n\}}}:
\end{textblock}

\begin{textblock}{3}(-0.1,8.7)  
\small\hfill\bl{\texttt{(a*)*b}}:
\end{textblock}

\begin{textblock}{3}(0.3,13)
\small{}matching with strings
\bl{$\underbrace{\texttt{a}...\texttt{a}}_n$}  
\end{textblock}

\end{frame} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
  \frametitle{Incidents}
    
  \begin{itemize}
  \item a global outage on 2 July 2019 at \textbf{Cloudflare} 
  (first one for six years)\medskip
  
  \begin{center}\small\color{blue}
  \begin{verbatim}  
  (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|
  null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s
  |-|~|!|{}|\|\||\+)*.*(?:.*=.*)))  
  \end{verbatim}
  \end{center}\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip    
  
  \item on 20 July 2016 the \textbf{Stack Exchange} webpage went down
    because of an evil regular expression
    \here{https://stackstatus.tumblr.com/post/147710624694/outage-postmortem-july-20-2016}    
  \end{itemize}
  
  \begin{textblock}{6}(6,7.6)
    \includegraphics[scale=0.14]{../pics/cloudflare.png}\\
    \footnotesize
    It serves more web traffic than Twitter, Amazon, Apple,
    Instagram, Bing \& Wikipedia combined.
    \here{https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/}
    \end{textblock}
  
  \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Evil Regular Expressions}

\begin{itemize}
\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\medskip
\item Some evil regular expressions:\medskip
\begin{itemize}
\item \bl{\texttt{[a?]\{n\}\;[a]\{n\}}}
\item \bl{\texttt{(a*)*\;b}}  
\item \bl{\texttt{([a-z]+)*}} 
\item \bl{\texttt{(a + aa)*}}
\item \bl{\texttt{(a + a?)*}}
\end{itemize}

\item sometimes also called \alert{catastrophic backtracking}
\item this is a problem for \alert{N}etwork \alert{I}ntrusion
  \alert{D}etection systems, Cloudflare, StackExchange, Atom editor
\item \url{https://vimeo.com/112065252}  
\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
% {
% \setbeamercolor{background canvas}{bg=cream}
% \begin{frame}[c]
% \frametitle{Rust vs.~Scala (from PEP)}

% \mbox{}

% \begin{minipage}{1.3\textwidth}
% \begin{mybox3}{}\it\small
% \textbf{Re: Another question of purely academic interest about regex implementation in cw3}

% This conversation is interesting to me, and I've researched it a
% little bit [...] I also disagree with Dr.~Urban on the cost/benefit of
% non-GC languages [...]\smallskip

% But regardless, Scala is a lot slower than, say, C or Rust. To say
% it's not is basically wrong (imo). Perhaps one could argue that some
% of the guarantees Scala has makes it easier to write multi-threaded
% programs that utilise more of the CPU... but, in my opinion, this is
% also a bit misleading. Most CPUs have something like 4 to 12 cores
% nowadays. It's very possible that a given Scala program runs 4-12x
% slower than its Rust equivalent. Would you rather have your program
% run quickly and use a single core, or have it run equally
% quickly... and... hog your entire CPU for its duration?\ldots{}

% \mbox{}\hfill-- Oliver Iliffe,  discussion from PEP
% \end{mybox3}
% \end{minipage}

% \end{frame}
% }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
% {
% \setbeamercolor{background canvas}{bg=cream}
% \begin{frame}[c]
% \frametitle{Regex Lib in Rust}

% \begin{center}
% \includegraphics[scale=0.34]{../pics/rust-regex.png}
% \end{center}

% \end{frame}
% }



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% {
% \setbeamercolor{background canvas}{bg=cream}
% \begin{frame}[c,fragile]

% \begin{columns}[t,onlytextwidth]
% \begin{column}{1\textwidth}
% \small re: \bl{$(abc)^{\{n\}}$}\quad str: \bl{$\underbrace{abc\ldots{}abc}_n$}\medskip\\  
% \begin{tikzpicture}\footnotesize
% \begin{axis}[
%     xlabel={$n$},
%     x label style={at={(1.07,0.0)}},
%     ylabel={time in secs},
%     enlargelimits=false,
%     xmax=65000,
%     ymax=100,
%     xtick={0,15000,...,60000},
%     ytick={0,10,...,90},
%     scaled ticks=false,
%     axis lines=left,
%     width=7cm,
%     height=5cm]
%     \addplot[black,mark=square*,mark options={fill=red}] table [x=x, y=y, col sep=comma, row sep=crcr]
%     {x, y\\
%       0, 0\\
%      5000, 0.487\\ 
%      10000, 1.650\\
%      15000, 3.617\\
%      20000, 6.462\\
%      25000, 10.736\\
%      30000, 17.665\\
%      35000, 25.662\\
%      40000, 36.422\\
%      45000, 49.119\\
%      50000, 62.058\\
%      55000, 75.941\\
%      60000, 93.022\\
%     };
% \end{axis}
% \end{tikzpicture}
% \end{column}
% \end{columns}

% \begin{textblock}{10}(8.4,3.8)
% \tiny  
% \begin{lstlisting}[language=Rust]
% extern crate regex;

% use regex::Regex;
% use std::time::Instant;

% // bounded regular expression example

% fn main() {
%    for bound in (0..=60000).step_by(5000) {
   
%       let re = Regex::new(&format!("(abc){{{}}}", bound)).unwrap();
%       let text = "abc".repeat(bound);

%       let start_time = Instant::now();
%       let is_match = re.is_match(&text);
%       let elapsed_time = start_time.elapsed().as_secs_f64();

%       println!("Bound: {}, Match: {}, Time: {} seconds", bound, is_match, elapsed_time);
%    }
% }
% \end{lstlisting}    
% \end{textblock}
% \end{frame}
% }  



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Today}
%
%\begin{itemize}
%\item While the ultimate goal is to implement a small compiler for the JVM
%  \ldots\bigskip
%\end{itemize}
%
%Let's start with:
%
%\begin{itemize}
%\item a web-crawler
%\item an email harvester
%\item \textcolor{gray}{(a web-scraper)}
%\end{itemize}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[t]
%\frametitle{A Web-Crawler}
%
%\mbox{}\\[10mm]
%
%\begin{enumerate}
%\item given an URL, read the corresponding webpage
%\item extract all links from it
%\item call the web-crawler again for all these links
%\end{enumerate}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[t]
%\frametitle{A Web-Crawler}
%
%\mbox{}\\[10mm]
%
%
%\begin{enumerate}
%\item given an URL, read the corresponding webpage
%\item if not possible print, out a problem
%\item if possible, extract all links from it
%\item call the web-crawler again for all these links
%\end{enumerate}\bigskip\pause
%
%\small (we need a bound for the number of recursive calls)
%
%\small (the purpose is to check all links on my own webpage)
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%
%\begin{textblock}{1}(2,5)
%\begin{tabular}{c}
%\includegraphics[scale=0.15]{pics/servers.png}\\[-2mm]
%\small Server
%\end{tabular}
%\end{textblock}
%
%\begin{textblock}{1}(5.6,4)
%  \begin{tikzpicture}[scale=1.1]
%  \draw[white] (0,1) node (X) {};
%  \draw[white] (2,1) node (Y) {};
%   \draw[white] (0,0) node (X1) {};
%  \draw[white] (2,0) node (Y1) {};
%   \draw[white] (0,-1) node (X2) {};
%  \draw[white] (2,-1) node (Y2) {};
%  \draw[red, <-, line width = 2mm] (X) -- (Y);
%  \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {};
%  \draw[red, ->, line width = 2mm] (X1) -- (Y1);
%  \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X1)!.5!(Y1) $) {};
%  \draw[red, <-, line width = 2mm] (X2) -- (Y2);
%  \node [inner sep=7pt,label=above:\textcolor{black}{POST data}] at ($ (X2)!.5!(Y2) $) {};
%  \end{tikzpicture}
%\end{textblock}
%
%
%\begin{textblock}{1}(9,5.5)
%\begin{tabular}{c}
%\includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm]
%\small Browser
%\end{tabular}
%\end{textblock}
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Scala}
%
%\small A simple Scala function for reading webpages:
%\bigskip
%
%\footnotesize
%\lstinputlisting{../progs/app0.scala}
%\medskip\pause
%
%\lstinline{get_page("""https://nms.kcl.ac.uk/christian.urban/""")}
%\bigskip\medskip\pause
%
%
%\small A slightly more complicated version for handling errors:
%\smallskip
%
%\footnotesize
%\lstinputlisting[xleftmargin=-4mm]{../progs/app1.scala}
%
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[t]
%\frametitle{A Regular Expression}
%
%\begin{itemize}
%\item \ldots{} is a pattern or template for specifying strings
%\end{itemize}\bigskip
%  
%\begin{center}  
%\only<1>{\scode{"https?://[^"]*"}}%
%\only<2>{\scode{""""https?://[^"]*"""".r}}
%\end{center}\bigskip\bigskip
%
%matches for example\smallskip\\  
%\hspace{2mm}\code{"http://www.foobar.com"}\\
%\hspace{2mm}\code{"https://www.tls.org"}\smallskip\\
%
%but not\smallskip\\  
%\hspace{2mm}\code{"http://www."foo"bar.com"}\\
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Finding Operations in Scala}
%
%{\bf\code{rexp.findAllIn(string)}}\medskip
%  
%returns a list of all (sub)strings that match the 
%regular expression
%\bigskip\bigskip  
%  
%
%{\bf\code{rexp.findFirstIn(string)}}\medskip
% 
%returns either 
%
%\begin{itemize}
%\item \code{None} if no (sub)string matches or 
%\item \code{Some(s)} with the first (sub)string
%\end{itemize}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%
%\footnotesize
%\lstinputlisting{../progs/app2.scala}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%
%\small
%A version that only crawls links in ``my'' domain:\bigskip
%
%\footnotesize
%\lstinputlisting{../progs/app3.scala}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\lstset{xleftmargin=-4mm}
%\small
%A little email harvester:
%
%\footnotesize
%\lstinputlisting{../progs/app4.scala}\bigskip
%
%\tiny
%\url{http://net.tutsplus.com/tutorials/other/8-regular-expressions-you-should-know/}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{(Basic) Regular Expressions}

Their inductive definition:


\begin{textblock}{6}(2,7.5)
  \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & nothing\\
         & \bl{$\mid$} & \bl{$\ONE$}       & empty string / \pcode{""} / $[]$\\
         & \bl{$\mid$} & \bl{$c$}                         & character\\
         & \bl{$\mid$} & \bl{$r_1 + r_2$}  & alternative / choice\\
         & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\
         & \bl{$\mid$} & \bl{$r^*$}            & star (zero or more)\\
  \end{tabular}
  \end{textblock}
  
  
\only<2->{\footnotesize
\begin{textblock}{9}(2,0.5)
\begin{bubble}[9.8cm]
\lstinputlisting{../progs/app01.scala}
\end{bubble}
\end{textblock}}
  
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[t]
%\frametitle{Regular Expressions}
%
%\small
%In Scala:\bigskip
%
%\footnotesize
%\lstinputlisting{../progs/app51.scala}
%
%  
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Strings}

\ldots are lists of characters. For example \code{"hello"}

\begin{center}
\bl{$[h, e, l, l, o]$} or just \bl{$hello$}
\end{center}

the empty string: \bl{$[]$} or \bl{\pcode{""}}\bigskip\\

the concatenation of two strings:

\begin{center}
\bl{$s_1 \,@\, s_2$}
\end{center}

\bl{\textit{foo $@$ bar = foobar}}\\
\bl{\textit{baz $@\, []$ = baz}}
  
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Languages, Strings}

\begin{itemize}
\item \alert{\bf Strings} are lists of characters, for example
\begin{center}
\bl{$[]$},\;\bl{$abc$}  \hspace{2cm}(Pattern match: \bl{$c\!::\!s$})
\end{center}\bigskip


\item A \alert{\bf language} is a set of strings, for example\medskip
\begin{center}
\bl{$\{[], hello, \textit{foobar}, a, abc\}$}
\end{center}\bigskip

\item \alert{\bf Concatenation} of strings and languages

\begin{center}
\begin{tabular}{rcl}
\bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\
\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$}
\end{tabular}
\end{center}

%\item The \alert{\bf meaning} of a regular expression is a set of 
%  strings, or language.
\end{itemize}  

\only<2>{
\begin{textblock}{4}(10.5,8)
\small
Let

\bl{$A = \{foo, bar\}$} \bl{$B = \{a, b\}$}
\[
\bl{A \,@\, B = \{fooa, foob, bara, barb\}}
\]
\end{textblock}}  

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
  \frametitle{Two Corner Cases}
   
  \Large
  \begin{center}
  \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\
  \bl{$A \,@\, \{\} = \;?$}
  \end{center}  
    
  \end{frame}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{The Meaning of a Regex}

 ...all the strings a regular expression can match.   

\begin{center}
 \begin{tabular}{rcl}
 \bl{$L(\ZERO)$}  & \bl{$\dn$} & \bl{$\{\}$}\\
 \bl{$L(\ONE)$}     & \bl{$\dn$} & \bl{$\{[]\}$}\\
 \bl{$L(c)$}            & \bl{$\dn$} & \bl{$\{[c]\}$}\\
 \bl{$L(r_1 + r_2)$}    & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
 \bl{$L(r^*)$}           & \bl{$\dn$} & \\
  \end{tabular}
\end{center}

\begin{textblock}{14}(1.5,13.5)\small
\bl{$L$} is a function from regular expressions to 
sets of strings (languages):\smallskip\\
\bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
\end{textblock}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
  \frametitle{The Power Operation}
  
  \begin{itemize}
  \item The \alert{\textbf{\boldmath$n$th Power}} of a language:
  
  \begin{center}
  \begin{tabular}{lcl}
  \bl{$A^0$}    & \bl{$\dn$} & \bl{$\{[]\}$}\\
  \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$}
  \end{tabular}
  \end{center}\bigskip
  
  \item[] For example
  
  \begin{center}
  \begin{tabular}{lcl@{\hspace{10mm}}l}
  \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\
  \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\
  \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\
  \end{tabular}
  \end{center}
  
  \end{itemize}  
  
  \end{frame}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{The Meaning of a Regex}

\begin{textblock}{15}(1,4)
 \begin{tabular}{rcl}
 \bl{$L(\ZERO)$}  & \bl{$\dn$} & \bl{$\{\}$}\\
 \bl{$L(\ONE)$}     & \bl{$\dn$} & \bl{$\{[]\}$}\\
 \bl{$L(c)$}            & \bl{$\dn$} & \bl{$\{[c]\}$}\\
 \bl{$L(r_1 + r_2)$}    & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\
 \bl{$L(r^*)$}           & \bl{$\dn$} & \onslide<2->{\bl{$\bigcup_{0 \le n} L(r)^n$}}\\
  \end{tabular}\bigskip
  
%\onslide<2->{
%\hspace{5mm}\bl{$L(r)^0 \;\dn\; \{[]\}$}\\
%\bl{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}\hspace{9mm}\onslide<3->{\small\textcolor{gray}{(append on sets)}\\
%\small\hspace{5cm}\textcolor{gray}{$\{ s_1 @ s_2 \;|\; s_1\in L(r) \wedge s_2 \in L(r)^n \}$}}
%}  
\end{textblock}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
  \frametitle{The Star Operation}
  
  \begin{itemize}
  \item The \alert{\bf Kleene Star} of a \underline{language}:
  \bigskip
  
  \begin{center}
  \begin{tabular}{c}
  \bl{$A\star \dn \bigcup_{0\le n} A^n$}
  \end{tabular}
  \end{center}\bigskip
  
  \item[] This expands to 
  
  \[
  \bl{A^0 \cup A^1 \cup A^2 \cup A^3 \cup A^4 \cup \ldots}
  \]
  
  or
  
  \small
  \[
  \bl{\{[]\} \;\cup\; A \;\cup\; A\,@\,A \;\cup\; 
    A\,@\,A\,@\,A \;\cup\; A\,@\,A\,@\,A\,@\,A \cup \ldots}
  \]
  
  \end{itemize}  
  
  \end{frame}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{The Meaning of a Regex}

\begin{textblock}{15}(1,4)
 \begin{tabular}{rcl}
 \bl{$L(\ZERO)$}  & \bl{$\dn$} & \bl{$\{\}$}\\
 \bl{$L(\ONE)$}     & \bl{$\dn$} & \bl{$\{[]\}$}\\
 \bl{$L(c)$}            & \bl{$\dn$} & \bl{$\{[c]\}$}\\
 \bl{$L(r_1 + r_2)$}    & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\
 \bl{$L(r^*)$}           & \bl{$\dn$} & \bl{$(L(r))\star$}\\
  \end{tabular}
  
\end{textblock}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{The Meaning of Matching}

\begin{bubble}[10cm]
\large\bf 
A regular expression \bl{$r$} matches a string~\bl{$s$} 
provided

\begin{center}
\bl{$s \in L(r)$}\\ 
\end{center}
\end{bubble}\bigskip\bigskip

\ldots and the point of the next lecture is 
to decide this problem as fast as possible (unlike Python,
Ruby, Java)

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
  \frametitle{Questions}
  
  \begin{itemize}
  \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip
  
  \item[]
  How many strings are in \bl{$A^4$}\,?
  \bigskip\medskip\pause
  
  
 \item[]
  What if \bl{$A = \{[a],[b],[c],[]\}$};\\ 
  how many strings are then in \bl{$A^4$}\,?
  \end{itemize}  
  
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
  \frametitle{Questions}

  \begin{itemize}
  \item Assume a set $A$ contains 4 strings and a set $B$
  contains 7 strings. None of the strings is the empty
  string.

  \item How many strings are in $A \,@\, B$?
  \end{itemize}

  
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c]

\begin{minipage}{1.3\textwidth}

\end{minipage}
\includegraphics[scale=0.4]{../pics/chatgpt.png}
\end{frame}
}

{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c]
\frametitle{\dots{}for amusement}

\begin{minipage}{1.3\textwidth}
\includegraphics[scale=0.4]{../pics/chatgpt1.png}
\end{minipage}

\end{frame}
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c]
% \frametitle{Languages (Sets of Strings)}

% \begin{itemize}

% \item A \alert{\bf Language} is a set of strings, for example\medskip
% \begin{center}
% \bl{$\{[], hello, foobar, a, abc\}$}
% \end{center}\bigskip

% \item \alert{\bf Concatenation} for strings and languages

% \begin{center}
% \begin{tabular}{rcl}
% \bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\
% \bl{$A\;@\;B$}     & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$}
% \end{tabular}
% \end{center}
% \bigskip

% \small
% \item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$}

% \[
% \bl{A \,@\, B = \{fooa, foob, bara, barb\}}
% \]




% \end{itemize}  
% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c]
%   \frametitle{Two Corner Cases}
   
%   \Large
%   \begin{center}
%   \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\
%   \bl{$A \,@\, \{\} = \;?$}
%   \end{center}  
    
%   \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c]
% \frametitle{The Meaning of a Regex}

%  ...all the strings a regular expression can match.   

% \begin{center}
%  \begin{tabular}{rcl}
%  \bl{$L(\ZERO)$}  & \bl{$\dn$} & \bl{$\{\}$}\\
%  \bl{$L(\ONE)$}     & \bl{$\dn$} & \bl{$\{[]\}$}\\
%  \bl{$L(c)$}            & \bl{$\dn$} & \bl{$\{[c]\}$}\\
%  \bl{$L(r_1 + r_2)$}    & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
%  \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
%  \bl{$L(r^*)$}           & \bl{$\dn$} & \\
%   \end{tabular}
% \end{center}

% \begin{textblock}{14}(1.5,13.5)\small
% \bl{$L$} is a function from regular expressions to 
% sets of strings (languages):\smallskip\\
% \bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
% \end{textblock}

% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c]
% \frametitle{The Power Operation}

% \begin{itemize}
% \item The \alert{\textbf{\boldmath$n$th Power}} of a language:

% \begin{center}
% \begin{tabular}{lcl}
% \bl{$A^0$}    & \bl{$\dn$} & \bl{$\{[]\}$}\\
% \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$}
% \end{tabular}
% \end{center}\bigskip

% \item[] For example

% \begin{center}
% \begin{tabular}{lcl@{\hspace{10mm}}l}
% \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\
% \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\
% \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\
% \end{tabular}
% \end{center}

% \end{itemize}  

% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c]
% \frametitle{Written Exam}

% \begin{itemize}
% \item Accounts for 80\%.\bigskip

% \item The question ``\textit{Is this relevant for
%       the exam?}'' is very demotivating for the lecturer!\bigskip\\

% \item Deal: Whatever is in the homework (and is not marked
%       ``\textit{optional}'') is relevant for the exam.\bigskip
      
% \item Each lecture has also a handout. There are also handouts about
% notation and Scala.      
% \end{itemize}

% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[t]
% \frametitle{Coursework}

% \begin{itemize}
% \item Accounts for 20\%. Two strands. Choose \alert{\bf one}!\bigskip
% \end{itemize}

% \begin{columns}[t]
% \begin{column}{.5\textwidth}
% \underline{\bf Strand 1}\medskip
% \begin{itemize}
% \item 4 programming tasks:
% \begin{itemize}
% \item matcher (4\%, 11.10.) 
% \item lexer (5\%, 04.11.)
% \item parser (5\%, 22.11.)
% \item compiler (6\%, 13.12.)
% \end{itemize}
% \item in any lang.~you like,\\ but I want to see the\\ code
% \end{itemize}
% \end{column}

% \hspace{-45pt}\vrule{}\hspace{10pt}
% \begin{column}{.5\textwidth}
% \underline{\bf Strand 2}\smallskip\begin{itemize}
% \item one task: prove the correctness of a regular expression matcher in 
% the \underline{Isabelle} theorem prover
% \item 20\%, submission on~13.12.\hspace{-5mm}\mbox{}
% \end{itemize}
% \end{column}
% \end{columns}\medskip

% \small
% \begin{itemize}
% \item Solving more than one strand will {\bf not} give you more 
% marks.

% \end{itemize}

% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Lecture Capture}
%
%\begin{itemize}
%\item Hope it works\ldots\pause actually no, it does not!\medskip\pause
%\item It is important to use lecture capture wisely\\ (it is only the ``baseline''):
%\begin{itemize}  
%\item Lecture recordings are a study and revision aid.
%\item Statistically, there is a clear and direct link between attendance and
%  attainment: students who do not attend lectures, do less well in exams.
%\end{itemize}
%
%\item Attending a lecture is more than watching it online -- if you do not
%attend, you miss out!  
%  
%\end{itemize}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{\begin{tabular}{c}\\[1cm]\alert{Questions?}\end{tabular}}


\begin{tabular}{lll}
  SGT TAs:  & Flavio Melinte Citea\\
            & Zoltan Meszaros\bigskip\\
Amm + Github & Flavio Melinte Citea & (flavio.melinte\_citea@kcl.ac.uk)\\
Helpers     & Zishan Rahman & (zishan.rahman@kcl.ac.uk)\medskip\\
\end{tabular}  
\mbox{}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\begin{mybox3}{What is the trick?}\small
  What was the trick to improve the evil regular expressions matcher
  to have such good results compared to other programming languages?
  Is it working better on casual regular expressions (the ones that
  Python and Java handle pretty well), too? Or was it just optimised
  for these evil ones?
\end{mybox3}
\end{frame}

\begin{frame}[c]
\begin{mybox3}{No Regex at Amazon AWS}\small
My friend who works at Amazon AWS told me they try to avoid 
regexes whenever they can. So kind of echoes this joke from the week 
1 handout.

\begin{quote}
“Sometimes you have a programming problem and it seems like the 
best solution is to use regular expressions; now you have two problems.”
\end{quote}

\end{mybox3}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
  \frametitle{Thanks to Martin Mikusovic}

\bigskip    
\begin{center}
\begin{tikzpicture}
  \begin{axis}[
    xlabel={$n$},
    x label style={at={(1.05,0.0)}},
    ylabel={time in secs},
    enlargelimits=false,
    xtick={0,5,...,30},
    xmax=33,
    ymax=35,
    ytick={0,10,...,30},
    scaled ticks=false,
    axis lines=left,
    width=9cm,
    height=5.5cm, 
    legend entries={Java 8, Python, JavaScript, Swift},  
    legend pos=north west,
    legend cell align=left]
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
\end{axis}
\end{tikzpicture}
\end{center}

Regex: \bl{$(a^*)^* \cdot b$}

Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Same Example in Java 9+}

\begin{center}
\begin{tikzpicture}
  \begin{axis}[
    xlabel={$n$},
    x label style={at={(1.09,-0.15)}},
    ylabel={time in secs},
    scaled x ticks=false,
    enlargelimits=false,
    xtick distance=10000,
    xmax=44000, 
    ytick={0,10,...,30}, 
    ymax=35, 
    axis lines=left,
    width=9cm,
    height=5cm, 
    legend entries={Java \liningnums{9}+},
    legend pos=north west,
    legend cell align=left]
\addplot[blue,mark=square*,mark options={fill=white}] table {re-java9.data};
\end{axis}
\end{tikzpicture}
\end{center}

Regex: \bl{$(a^*)^* \cdot b$}

Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Questions




\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]
\end{frame}

\begin{frame}[c]

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
\end{document}

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

