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

\tikzset{onslide/.code args={<#1>#2}{%
  \only<#1>{\pgfkeysalso{#2}} % \pgfkeysalso doesn't change the path
}}

\makeatletter
\newenvironment<>{btHighlight}[1][]
{\begin{onlyenv}#2\begingroup\tikzset{bt@Highlight@par/.style={#1}}\begin{lrbox}{\@tempboxa}}
{\end{lrbox}\bt@HL@box[bt@Highlight@par]{\@tempboxa}\endgroup\end{onlyenv}}

\newcommand<>\btHL[1][]{%
  \only#2{\begin{btHighlight}[#1]\bgroup\aftergroup\bt@HL@endenv}%
}
\def\bt@HL@endenv{%
  \end{btHighlight}%   
  \egroup
}
\newcommand{\bt@HL@box}[2][]{%
  \tikz[#1]{%
    \pgfpathrectangle{\pgfpoint{1pt}{0pt}}{\pgfpoint{\wd #2}{\ht #2}}%
    \pgfusepath{use as bounding box}%
    \node[anchor=base west, fill=orange!30,outer sep=0pt,inner xsep=1pt, inner ysep=0pt, rounded corners=3pt, minimum height=\ht\strutbox+1pt,#1]{\raisebox{1pt}{\strut}\strut\usebox{#2}};
  }%
}
\makeatother


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


\begin{document}

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

   \normalsize
  \begin{center}
  \begin{tabular}{ll}
    Email:  & christian.urban at kcl.ac.uk\\
            & I will try to stay on top of my inbox during Christmas\medskip\\
    %%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 \\
          4 Lexing, Tokenising               & 9 Optimisations \\
          5 Grammars, Parsing                & \cellcolor{blue!50}10 LLVM \\ \hline
        \end{tabular}%
      };
    \end{tikzpicture}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

\begin{itemize}
\item sometimes in January
\item 2hs / 23 questions
\item questions taken from HWs with scant changes
\item all but one are text questions (one is true/false)

\end{itemize}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\tikzstyle{sensor}=[draw, fill=blue!20, text width=3.8em, line width=1mm,
    text centered, minimum height=2em,drop shadow]
\tikzstyle{ann} = [above, text width=4em, text centered]
\tikzstyle{sc} = [sensor, text width=7em, fill=red!20, 
    minimum height=6em, rounded corners, drop shadow,line width=1mm]

\begin{frame}[fragile,c]
\frametitle{LLVM: Overview}

\begin{tikzpicture}
    % Validation Layer is the same except that there are a set of nodes and links which are added
   
    \path (0,0) node (IR) [sc] {\textbf{LLVM-IR}\\ Optimisations};
    \path (IR.west)+(-2.2,1.7) node (sou1) [sensor] {C++};
    \path (IR.west)+(-2.2,0.5) node (sou2)[sensor] {C};
    \path (IR.west)+(-2.2,-1.0) node (dots)[ann] {$\vdots$}; 
    \path (IR.west)+(-2.2,-1.8) node (sou3)[sensor] {Haskell};    

    \path [draw,->,line width=1mm] (sou1.east) -- node [above] {} (IR.160);
    \path [draw,->,line width=1mm] (sou2.east) -- node [above] {} (IR.180);
    \path [draw,->,line width=1mm] (sou3.east) -- node [above] {} (IR.200);

    \path (IR.east)+(2.2,2.0)  node (tar1)[sensor] {x86};
    \path (IR.east)+(2.2,0.8)  node (tar2)[sensor] {ARM};
    \path (IR.east)+(2.2,-0.4) node (tar3)[sensor] {MIPS}; 
    \path (IR.east)+(2.2,-1.6) node (tar4)[sensor] {RISC}; 
    \path (IR.east)+(2.2,-2.8) node (tar5)[sensor] {Power PC};
    \path (IR.east)+(2.2,-4.2) node (dots2)[ann] {$\vdots$};

    \path [draw,<-,line width=1mm] (tar1.west) -- node [above] {} (IR.10);
    \path [draw,<-,line width=1mm] (tar2.west) -- node [above] {} (IR.5);
    \path [draw,<-,line width=1mm] (tar3.west) -- node [above] {} (IR.0);
    \path [draw,<-,line width=1mm] (tar4.west) -- node [above] {} (IR.-5);
    \path [draw,<-,line width=1mm] (tar5.west) -- node [above] {} (IR.-10);
    
\end{tikzpicture}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
\begin{frame}[c,fragile]
\frametitle{Static Single-Assignment}  

\bl{$(1 + a) + (3 + (b * 5))$}\bigskip\bigskip  

\begin{lstlisting}[language=LLVMIR,numbers=left]
let tmp0 = add 1 a in   
let tmp1 = mul b 5 in 
let tmp2 = add 3 tmp1 in 
let tmp3 = add tmp0 tmp2
  in tmp3 
\end{lstlisting}  


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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
\begin{frame}[c,fragile]
\small

\mbox{}\bigskip\bigskip\bigskip

\begin{lstlisting}[language=llvm,numbers=left]
define i32 @fact (i32 %n) {
   %tmp_20 = icmp eq i32  %n, 0
   br i1 %tmp_20, label %if_branch_24, label %else_branch_25
 if_branch_24:
   ret i32 1
 else_branch_25:
   %tmp_22 = sub i32  %n, 1
   %tmp_23 = call i32 @fact (i32 %tmp_22)
   %tmp_21 = mul i32  %n, %tmp_23
   ret i32 %tmp_21
}  
\end{lstlisting}  

\begin{lstlisting}[language={},numbers=none]
def fact(n) = if n == 0 then 1 else n * fact(n - 1)
\end{lstlisting}  
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile,c]
\frametitle{LLVM Types}

\tt
\begin{center}
\begin{tabular}{ll}
boolean & i1 \\
byte    & i8 \\
short   & i16\\
char    & i16\\
integer & i32\\
long    & i64\\
float   & float\\
double  & double\\
*\_      & pointer to \\
**\_     & pointer to a pointer to\\
\mbox{}[\_]    & arrays of\\
\end{tabular}
\end{center}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
\begin{frame}[c,fragile]


\begin{lstlisting}[language=LLVM,numbers=none]
br i1 %var, label %if_br, label %else_br
  
icmp eq i32  %x, %y     ; for equal
icmp sle i32 %x, %y     ;   signed less or equal
icmp slt i32 %x, %y     ;   signed less than
icmp ult i32 %x, %y     ;   unsigned less than 

%var = call i32 @foo(...args...)
\end{lstlisting}  

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile,c]
\frametitle{Abstract Syntax Trees}
\footnotesize

\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm]
// Fun language (expressions)
abstract class Exp 
abstract class BExp 

case class Call(name: String, args: List[Exp]) extends Exp
case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
case class Write(e: Exp) extends Exp
case class Var(s: String) extends Exp
case class Num(i: Int) extends Exp
case class Aop(o: String, a1: Exp, a2: Exp) extends Exp
case class Sequence(e1: Exp, e2: Exp) extends Exp
case class Bop(o: String, a1: Exp, a2: Exp) extends BExp  
\end{lstlisting}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile,c]
\frametitle{K-(Intermediate)Language}
\footnotesize

\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm]
abstract class KExp
abstract class KVal

// K-Values
case class KVar(s: String) extends KVal
case class KNum(i: Int) extends KVal
case class Kop(o: String, v1: KVal, v2: KVal) extends KVal
case class KCall(o: String, vrs: List[KVal]) extends KVal
case class KWrite(v: KVal) extends KVal

// K-Expressions
case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp
case class KLet(x: String, v: KVal, e: KExp) extends KExp
case class KReturn(v: KVal) extends KExp
\end{lstlisting}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile,c]
\frametitle{KLet}

\begin{lstlisting}[language=LLVM]
tmp0 = add 1 a   
tmp1 = mul b 5 
tmp2 = add 3 tmp1 
tmp3 = add tmp0 tmp2  
\end{lstlisting}

\begin{lstlisting}[language=LLVMIR]
  KLet tmp0 , add 1 a in  
   KLet tmp1 , mul b 5 in
    KLet tmp2 , add 3 tmp1 in 
     KLet tmp3 , add tmp0 tmp2 in
      ...
\end{lstlisting}

\begin{lstlisting}[language=Scala,numbers=none]
case class KLet(x: String, e1: KVal, e2: KExp)
\end{lstlisting}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile,c]
\frametitle{KLet}

\begin{lstlisting}[language=LLVM]
tmp0 = add 1 a   
tmp1 = mul b 5 
tmp2 = add 3 tmp1 
tmp3 = add tmp0 tmp2  
\end{lstlisting}

\begin{lstlisting}[language=LLVMIR]
  let tmp0 = add 1 a in  
   let tmp1 = mul b 5 in
    let tmp2 = add 3 tmp1 in 
     let tmp3 = add tmp0 tmp2 in
      ...
\end{lstlisting}

\begin{lstlisting}[language=Scala,numbers=none]
case class KLet(x: String, e1: KVal, e2: KExp)
\end{lstlisting}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile,c]
\frametitle{CPS-Translation}
\small

\begin{lstlisting}[language=Scala,numbers=none]
def CPS(e: Exp)(k: KVal => KExp) : KExp = 
  e match { ... }
\end{lstlisting}
\bigskip\bigskip

the continuation \texttt{k} can be thought of:\medskip

\small
\begin{lstlisting}[language=LLVMIR,numbers=none,xleftmargin=30mm,escapeinside={(*@}{@*)}]
let tmp0 = add 1 a in   
let tmp1 = mul (*@$\Box$@*) 5 in 
let tmp2 = add 3 tmp1 in 
let tmp3 = add tmp0 tmp2 in
  KReturn tmp3 
\end{lstlisting}

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



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
\begin{frame}[c,fragile]


\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-6mm]
def fact(n: Int) : Int = {
  if (n == 0) 1 else n * fact(n - 1) 
}


def factC(n: Int, ret: Int => Int) : Int = {
  if (n == 0) ret(1) 
  else factC(n - 1, x => ret(n * x)) 
}

fact(10)
factC(10, identity)
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
\begin{frame}[c,fragile]


\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-6mm]
def fibC(n: Int, ret: Int => Int) : Int = {
  if (n == 0 || n == 1) ret(1) else
  fibC(n - 1,
       r1 => fibC(n - 2,
        r2 => ret(r1 + r2)))
}

fibC(10, identity)
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}<1-15>[c]

\end{frame}  



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

  \Large\bf Are there more strings in \\ \hfill\bl{$L(a^*)$} or
  \bl{$L((a + b)^*)$}?

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Can you remember this HW?}

  \begin{itemize}
  \item (1) How many basic regular expressions are there to match
      the string \bl{$abcd$}? 
  \item (2) How many if they cannot include
      \bl{$\ONE$} and \bl{$\ZERO$}? 
  \item (3) How many if they are also not
      allowed to contain stars? 
  \item (4) How many if they are also
      not allowed to contain \bl{$\_ + \_$}?
   \end{itemize}  

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


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

\Large\bf There are more problems, than there are
programs.\bigskip\bigskip\pause\\

There must be a problem for which there is no program.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

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

\Large
If \bl{$A \subseteq B$} then \bl{$A$} has fewer or equal elements 
than \bl{$B$}\bigskip\bigskip

\Large
\bl{$A \subseteq B$} and \bl{$B \subseteq A$}\bigskip

then \bl{$A = B$}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \begin{frame}[c]
  
  \begin{center}
  \begin{tikzpicture}
  
  \draw (-4,2.5) node [scale=2.5] (X) 
    {\begin{tabular}{l}
     $\{$  
     \!\includegraphics[scale=0.02]{../pics/o1.jpg},
     \includegraphics[scale=0.02]{../pics/o2.jpg},
     \!\includegraphics[scale=0.02]{../pics/o3.jpg},
     \includegraphics[scale=0.02]{../pics/o4.jpg},
     \!\includegraphics[scale=0.027]{../pics/o5.jpg}
     $\}$
    \end{tabular}};
    
    \draw (-5.6,-2.5) node [scale=2.5] (Y) 
    {\begin{tabular}{l}
     $\{$  
     \!\includegraphics[scale=0.059]{../pics/a1.jpg},
     \includegraphics[scale=0.048]{../pics/a2.jpg},
     \includegraphics[scale=0.02]{../pics/a3.jpg}
     $\}$
    \end{tabular}};
    
     \draw (0,1.5) node (X1) {5 elements};
     \draw (0,-3.5) node (y1) {3 elements};
  \end{tikzpicture}
  \end{center}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \begin{frame}[c]
  \frametitle{Newton vs Feynman}
  
  \begin{center}
  \begin{tabular}{cc}
  \includegraphics[scale=0.2]{../pics/newton.jpg} &
  \includegraphics[scale=0.2]{../pics/feynman.jpg}\\
  classical physics & quantum physics
  \end{tabular}
  \end{center}
  \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \begin{frame}[c]
  \frametitle{The Goal of the Talk}
 \large
  \begin{itemize}
  \item show you that something very unintuitive happens with very large sets	
  \bigskip\bigskip
  
  \item convince you that there are more {\bf problems} than {\bf programs}
  \end{itemize}	
  \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
%
  \begin{center}
  \begin{tikzpicture}
 
  \draw (-5,2.5) node [scale=2.3] (X) 
    {\begin{tabular}{@ {\hspace{-3mm}}l}
     \bl{$B$ $=$ $\{$  
     \!\includegraphics[scale=0.02]{../pics/o1.jpg},
     \includegraphics[scale=0.02]{../pics/o2.jpg},
     \!\includegraphics[scale=0.02]{../pics/o3.jpg},
     \includegraphics[scale=0.02]{../pics/o4.jpg},
     \!\includegraphics[scale=0.027]{../pics/o5.jpg}
     $\}$}
    \end{tabular}};
    
    \draw (-6.6,-0.5) node [scale=2.3] (Y) 
    {\begin{tabular}{@ {\hspace{-3mm}}l}
     \bl{$A$ $=$ $\{$  
     \!\includegraphics[scale=0.059]{../pics/a1.jpg},
     \includegraphics[scale=0.048]{../pics/a2.jpg},
     \includegraphics[scale=0.02]{../pics/a3.jpg}
     $\}$}
     \end{tabular}};
  
     \only<1>{\draw (-5, -3) node[scale=2] 
       {\bl{$|A|$ $=$ $5$}, \bl{$|B|$ $=$ $3$}};}
     \only<2>{
       \draw [->, line width=1mm, red] (-7.4, 0.2) -- (-6.1, 2.1);
       \draw [->, line width=1mm, red] (-5.8, 0.2) -- (-3.1, 2.1);
       \draw [->, line width=1mm, red] (-4.5, 0.2) -- (-7.6, 2.1);
       \draw (-5, -3) node[scale=2] {then \bl{$|A|$ $\le$ $|B|$}};
       }
    \only<3>{
       \draw [<-, line width=1mm, red] (-7.5, 0.2) -- (-6.1, 2.1);
       \draw [<-, line width=1mm, red] (-7.3, 0.2) -- (-3.1, 2.1);
       \draw [<-, line width=1mm, red] (-6, 0.2) -- (-7.5, 2.1);
       \draw [<-, line width=1mm, red] (-4.5, 0.2) -- (-4.5, 2.1);
       \draw [<-, line width=1mm, red] (-4.3, 0.2) -- (-1.3, 2.1);
       
       \draw (-5, -3) node[scale=1.5] {\small{}for \bl{$=$}
        has to be a {\bf one-to-one} mapping};
       }

    
  \end{tikzpicture}
  \end{center}

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

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

\Large
\bl{$|A|$} $\dn$ ``how many elements''\bigskip\\

\bl{$A \subseteq B  \Rightarrow |A| \leq |B|$}\bigskip\\\pause

if there is an injective function \bl{$f: A \rightarrow B$} then \bl{$|A| \leq |B|$}\

\begin{center}
\bl{\large$\forall x y.\; f(x) = f(y) \Rightarrow x = y$}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

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

  \begin{center}
  \begin{tikzpicture}
  
  \draw (-6.6,2.5) node [scale=2.3] (X) 
    {\begin{tabular}{@ {\hspace{-3mm}}l}
     $A$ $=$ $\{$  
     \!\includegraphics[scale=0.02]{../pics/o1.jpg},
     \includegraphics[scale=0.02]{../pics/o2.jpg},
     \!\includegraphics[scale=0.02]{../pics/o3.jpg}
     $\}$
    \end{tabular}};
    
    \draw (-6.6,-0.5) node [scale=2.3] (Y) 
    {\begin{tabular}{@ {\hspace{-3mm}}l}
     $B$ $=$ $\{$  
     \!\includegraphics[scale=0.059]{../pics/a1.jpg},
     \includegraphics[scale=0.048]{../pics/a2.jpg},
     \includegraphics[scale=0.02]{../pics/a3.jpg}
     $\}$
     \end{tabular}};
   \onslide<3->{\draw (-7, -3) node[scale=1.5] 
      {then \bl{$|A|$ \alert{$=$} $|B|$}};}
     \only<1>{
       \draw [->, line width=1mm, red] (-7.4, 0.2) -- (-6.1, 2.1);
       \draw [->, line width=1mm, red] (-5.8, 0.2) -- (-4.3, 2.1);
       \draw [->, line width=1mm, red] (-4.5, 0.2) -- (-7.6, 2.1);
     }
    \only<2->{
       \draw [<-, line width=1mm, blue] (-7.5, 0.2) -- (-7.5, 2.1);
       \draw [<-, line width=1mm, blue] (-5.8, 0.2) -- (-4.3, 2.1);
       \draw [<-, line width=1mm, blue] (-4.5, 0.2) -- (-6.1, 2.1);
       }
   
    
  \end{tikzpicture}
  \end{center}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Natural Numbers}

\Large
\bl{$\mathbb{N}$} \bl{$\dn$} \bl{$\{0, 1, 2, 3, .......\}$}\bigskip\pause 

\bl{$A$} is \alert{countable} iff \bl{$|A| \leq |\mathbb{N}|$}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{First Question}

\Large
\bl{$|\mathbb{N} - \{0\}|   \;\;\;\alert{?}\;\;\;  |\mathbb{N}| $}\bigskip\bigskip 

\large
\bl{$\geq$} or \bl{$\leq$} or \bl{$=$} ?
\bigskip\bigskip\bigskip\pause

\bl{$x$ $\mapsto$ $x + 1$},\\  \bl{$|\mathbb{N} - \{0\}|$ $=$  
$|\mathbb{N}|$}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]

\Large
\bl{$|\mathbb{N} - \{0, 1\}|   \;\;\;\alert{?}\;\;\;  |\mathbb{N}| $}\bigskip\pause 

\bl{$|\mathbb{N} - \mathbb{O}|   \;\;\;\alert{?}\;\;\;  |\mathbb{N}| $}\bigskip\bigskip

\normalsize
\bl{$\mathbb{O}$} $\dn$ odd numbers\quad   \bl{$\{1,3,5......\}$}\\ \pause
\bl{$\mathbb{E}$} $\dn$ even numbers\quad   \bl{$\{0,2,4......\}$}\\
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]

\Large
\bl{$|\mathbb{N} \cup \mathbb{-N}|   \;\;\;\alert{?}\;\;\;  |\mathbb{N}| $}\bigskip\bigskip


\normalsize
\bl{$\mathbb{\phantom{-}N}$} $\dn$ positive numbers\quad   \bl{$\{0,1,2,3,......\}$}\\
\bl{$\mathbb{-N}$} $\dn$ negative numbers\quad   \bl{$\{0,-1,-2,-3,......\}$}\\
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]

\Large
\bl{$A$} is \alert{countable} if there exists an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip

\bl{$A$} is \alert{uncountable} if there does not exist an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip\bigskip 


countable:  \bl{$|A| \leq |\mathbb{N}|$}\\
uncountable:  \bl{$|A| > |\mathbb{N}|$}\pause\bigskip


Does there exist such an \bl{$A$} ?

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \mode<presentation>{
  \begin{frame}[c]
  \frametitle{Hilbert's Hotel}

  \begin{center}
 \includegraphics[scale=0.8]{../pics/hilberts_hotel.jpg}
  \end{center}

  \begin{itemize}
  \item \ldots has as many rooms as there are natural numbers
  \end{itemize}

  \end{frame}}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  
  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
 \frametitle{\begin{tabular}{c}Real Numbers between\\[-2mm] 0 and 1\end{tabular}}

  \begin{center}
  \begin{tikzpicture}
  \draw [fill, color=black!50] (1,4) rectangle (2, 3);
  \draw [fill, color=black!50] (2,3) rectangle (3, 2);
  \draw [fill, color=black!50] (3,2) rectangle (4, 1);
  \draw [fill, color=black!50] (4,1) rectangle (5, 0);
  \draw (0, 0) grid (8, 5);
  \draw [line width = 1.mm] (1,0) -- (1, 5);    
  \draw [line width = 1.mm] (0, 4) -- (8, 4);    
  \draw (0.5,3.5) node {$1$};
  \draw (0.5,2.5) node {$2$};
  \draw (0.5,1.5) node {$3$};
  \draw (0.5,0.5) node {$4$};
  
  \draw (1.5,3.5) node {\only<1>{$3$}\only<2->{$4$}};
  \draw (2.5,3.5) node {$3$};
  \draw (3.5,3.5) node {$3$};
  \draw (4.5,3.5) node {$3$};
  \draw (5.5,3.5) node {$3$};
  \draw (6.5,3.5) node {$3$};
  \draw (7.5,3.5) node {$\ldots$};
  
  \draw (1.5,2.5) node {$1$};
  \draw (2.5,2.5) node {\only<1-2>{$2$}\only<3->{$3$}};
  \draw (3.5,2.5) node {$3$};
  \draw (4.5,2.5) node {$4$};
  \draw (5.5,2.5) node {$5$};
  \draw (6.5,2.5) node {$6$};
  \draw (7.5,2.5) node {$7$};

  \draw (1.5,1.5) node {$0$};
  \draw (2.5,1.5) node {$1$};
  \draw (3.5,1.5) node {\only<1-3>{$0$}\only<4->{$1$}};
  \draw (4.5,1.5) node {$1$};
  \draw (5.5,1.5) node {$0$};
  \draw (6.5,1.5) node {$\ldots$};
  
   \draw (1.5,0.5) node {$7$};
  \draw (2.5,0.5) node {$8$};
  \draw (3.5,0.5) node {$5$};
  \draw (4.5,0.5) node {\only<1-4>{$3$}\only<5->{$4$}};
  \draw (5.5,0.5) node {$9$};
  \draw (6.5,0.5) node {$\ldots$};
  
   \draw (1.5,-0.5) node {$\ldots$};
   \draw (8.5,3.5) node {$\ldots$};
  \end{tikzpicture}
  \end{center}
  \mbox{}\\[-20mm]\mbox{}
  
  \onslide<6->{
  \begin{center}
  \Large\bl{$|\mathbb{N}| < |R|$}
  \end{center}
  }

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
 \frametitle{The Set of Problems}

  $\aleph_0$

  \begin{center}
  \begin{tikzpicture}
  \draw [fill, color=black!50] (1,4) rectangle (2, 3);
  \draw [fill, color=black!50] (2,3) rectangle (3, 2);
  \draw [fill, color=black!50] (3,2) rectangle (4, 1);
  \draw [fill, color=black!50] (4,1) rectangle (5, 0);
  \draw (0, 0) grid (8, 5);
  \draw [line width = 1.mm] (1,0) -- (1, 5);    
  \draw [line width = 1.mm] (0, 4) -- (8, 4);    
  \draw (0.5,3.5) node {$1$};
  \draw (0.5,2.5) node {$2$};
  \draw (0.5,1.5) node {$3$};
  \draw (0.5,0.5) node {$4$};
  
  \draw (1.5,4.5) node {$0$};
  \draw (2.5,4.5) node {$1$};
  \draw (3.5,4.5) node {$2$};
  \draw (4.5,4.5) node {$3$};
  \draw (5.5,4.5) node {$4$};
  \draw (6.5,4.5) node {$5$};
  \draw (7.5,4.5) node {$\ldots$}; 
  
  \draw (1.5,3.5) node {$0$};
  \draw (2.5,3.5) node {$1$};
  \draw (3.5,3.5) node {$0$};
  \draw (4.5,3.5) node {$1$};
  \draw (5.5,3.5) node {$0$};
  \draw (6.5,3.5) node {$1$};
  \draw (7.5,3.5) node {$\ldots$};
  
  \draw (1.5,2.5) node {$0$};
  \draw (2.5,2.5) node {$0$};
  \draw (3.5,2.5) node {$0$};
  \draw (4.5,2.5) node {$1$};
  \draw (5.5,2.5) node {$1$};
  \draw (6.5,2.5) node {$0$};
  \draw (7.5,2.5) node {$0$};

  \draw (1.5,1.5) node {$0$};
  \draw (2.5,1.5) node {$0$};
  \draw (3.5,1.5) node {$0$};
  \draw (4.5,1.5) node {$0$};
  \draw (5.5,1.5) node {$0$};
  \draw (6.5,1.5) node {$\ldots$};
  
   \draw (1.5,0.5) node {$1$};
  \draw (2.5,0.5) node {$1$};
  \draw (3.5,0.5) node {$0$};
  \draw (4.5,0.5) node {$1$};
  \draw (5.5,0.5) node {$1$};
  \draw (6.5,0.5) node {$\ldots$};
  
  \draw (1.5,-0.5) node {$\ldots$};
   \draw (8.5,3.5) node {$\ldots$};

  \end{tikzpicture}
  \end{center}
  
  
  \onslide<2>{
  \begin{center}
  \large \bl{|Progs| $=$ $|\mathbb{N}|$ $<$ |Probs|}
 \end{center}
  }


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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Halting Problem}

\large
Assume a program \bl{$H$} that decides for all programs \bl{$A$} and all 
input data \bl{$D$} whether\bigskip

\begin{itemize}
\item \bl{$H(A, D) \dn 1$} iff \bl{$A(D)$} terminates
\item \bl{$H(A, D) \dn 0$} otherwise
\end{itemize}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Halting Problem (2)}

\large
Given such a program \bl{$H$} define the following program \bl{$C$}:
for all programs \bl{$A$}\bigskip

\begin{itemize}
\item \bl{$C(A) \dn 0$} iff \bl{$H(A, A) = 0$} 
\item \bl{$C(A) \dn$ loops} otherwise
\end{itemize}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Contradiction}


\bl{$H(C, C)$} is either \bl{$0$} or \bl{$1$}.

\begin{itemize}
\item \bl{$H(C, C) = 1$} $\stackrel{\text{def}\,H}{\Rightarrow}$ \bl{$C(C)\downarrow$} $\stackrel{\text{def}\,C}{\Rightarrow}$ \bl{$H(C, C)=0$} 
\item \bl{$H(C, C) = 0$} $\stackrel{\text{def}\,H}{\Rightarrow}$ \bl{$C(C)$} loops $\stackrel{\text{def}\,C}{\Rightarrow}$\\ 
\hspace{7cm}\bl{$H(C, C)=1$} 
\end{itemize}

Contradiction in both cases. So \bl{$H$} cannot exist.

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \mode<presentation>{
  \begin{frame}[c]
  \frametitle{Take Home Points}
 \large
 
  \begin{itemize}
  \item there are sets that are more infinite than others\bigskip
  \item even  with the most powerful computer we can imagine, there 
  are problems that cannot be solved by any program\bigskip\bigskip
  
  \item in CS we actually hit quite often such problems (halting problem)
  \end{itemize}

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

\begin{frame}<1-20>[c]
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Big Thank You!}
\large

\only<1>{%
\begin{itemize}
\item<1> It is always fun to learn new things in CFL
\item<1> I want to add Higher-Order Functions and Algebraic Datatypes to Fun (typing is a distant dream unfortunately)
  
\end{itemize}}

\hfill\includegraphics[scale=0.12]{thanks.png} 
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Big Thank You!}
\large

\begin{itemize}
\item Thanks for ALL the EoY feedback:\medskip\bigskip
\end{itemize}


\only<2>{
\begin{minipage}{13cm}  
\begin{quote}\it
``If all modules were as good as this one I would start recommending KCL over basically every single university instead of suggesting people look somewhere else.''
\end{quote}
\end{minipage}}

\only<3>{
\begin{minipage}{13cm}  
\begin{quote}\it
``Overall, CFL was without a doubt the most interesting subject I have taken\ldots''
\end{quote}
\end{minipage}\medskip}

\only<3>{
\begin{minipage}{13cm}  
\begin{quote}\it
``I like the lecture videos on KEATS, I think they are very engaging and I like the lecturers sense of humour.''
\end{quote}
\end{minipage}}

\hfill\includegraphics[scale=0.12]{thanks.png} 

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


\end{document}

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

