% !TEX program = xelatex

\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}

%%\usepackage{xcolor}

\usepackage{../slides}

\usepackage{../langs}

\usepackage{../data}

\usepackage{../graphics}

\usepackage{../grammar}

\usepackage[most]{tcolorbox}

\newtcbox{\hl}[1][]{%

     size=fbox,

    tcbox raise base, nobeforeafter, 

    enhanced, colframe=gray,

    colback=gray!30, boxrule=1pt,

    fontupper=\ttfamily,

    #1}

\lstset{morekeywords={def,if,then,else,write,read},keywordstyle=\color{codepurple}\bfseries}

% beamer stuff

\renewcommand{\slidecaption}{CFL 09, 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\\

    %Office Hours: & Thursdays 12 -- 14\\

    %Location: & N7.07 (North Wing, Bush House)\\

    Slides \& Progs: & KEATS (also homework is there)\\  

  \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      & \cellcolor{blue!50} 8 Compiling Functional Languages \\

          4 Lexing, Tokenising               & 9 Optimisations \\

          5 Grammars, Parsing                & 10 LLVM \\ \hline

        \end{tabular}%

      };

    \end{tikzpicture}

  \end{center}

\end{frame}

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

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

% \begin{frame}[c]

% \begin{center}

% \bl{\begin{tabular}{@{}lcl@{}}

% \meta{Stmt} & $::=$ &  $\texttt{skip}$\\

%               & $|$ & \textit{Id}\;\texttt{:=}\;\meta{AExp}\\

%               & $|$ & \texttt{if}\; \meta{BExp} \;\texttt{then}\; \meta{Block} \;\texttt{else}\; \meta{Block}\\

%               & $|$ & \texttt{while}\; \meta{BExp} \;\texttt{do}\; \meta{Block}\\

%               & $|$ & \texttt{read}\;\textit{Id}\\

%               & $|$ & \texttt{write}\;\textit{Id}\\

%               & $|$ & \texttt{write}\;\textit{String}\medskip\\

% \meta{Stmts} & $::=$ &  \meta{Stmt} \;\texttt{;}\; \meta{Stmts}\\

%               & $|$ & \meta{Stmt}\medskip\\

% \meta{Block} & $::=$ &  \texttt{\{}\,\meta{Stmts}\,\texttt{\}}\\

%                 & $|$ & \meta{Stmt}\medskip\\

% \meta{AExp} & $::=$ & \ldots\\

% \meta{BExp} & $::=$ & \ldots\\

% \end{tabular}}

% \end{center}

% \end{frame}

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

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

% \begin{frame}[t,fragile]

% \frametitle{Compiling AExps}

% For example \bl{$1 + ((2 * 3) + (4 - 3))$}:\medskip

% \begin{columns}[T]

% \begin{column}{.3\textwidth}

% \begin{center}

% \bl{\begin{tikzpicture}

% \tikzset{level distance=12mm,sibling distance=4mm}

% \tikzset{edge from parent/.style={draw,very thick}}

% \Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]]

% \end{tikzpicture}}

% \end{center}

% \end{column}

% \begin{column}{.3\textwidth}

% \begin{lstlisting}[language=JVMIS,numbers=none]

% ldc 1 

% ldc 2 

% ldc 3 

% imul 

% ldc 4 

% ldc 3 

% isub 

% iadd 

% iadd

% \end{lstlisting}

% \end{column}

% \end{columns}\bigskip

% \small

% Traverse tree in post-order \bl{$\Rightarrow$} code for 

% stack-machine

% \end{frame}

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

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

% \begin{frame}[c,fragile]

% \frametitle{Compiling AExps}

% \bl{

% \begin{center}

% \begin{tabular}{lcl}

% $\textit{compile}(n, E)$ & $\dn$ & $\pcode{ldc}\;n$\smallskip\\

% $\textit{compile}(a_1 + a_2, E)$ & $\dn$ \\

% \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\;\textit{compile}(a_2, E)\;@\; \pcode{iadd}$}\smallskip\\

% $\textit{compile}(a_1 - a_2, E)$ & $\dn$ \\

% \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{isub}$}\smallskip\\

% $\textit{compile}(a_1 * a_2, E)$ & $\dn$ \\

% \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{imul}$}\smallskip\\

% $\textit{compile}(a_1 \backslash a_2, E)$ & $\dn$\\ 

% \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{idiv}$}\smallskip\\

% $\textit{compile}(x, E)$ & $\dn$ & $\pcode{iload}\;E(x)$\\

% \end{tabular}

% \end{center}}

% \end{frame}

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

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

% \begin{frame}[c,fragile]

% \frametitle{Compiling Ifs}

% For example

% \begin{lstlisting}[mathescape,numbers=none,language=While]

% if 1 = 1 then x := 2 else y := 3

% \end{lstlisting}

% \begin{center}

% \begin{lstlisting}[mathescape,language=JVMIS,numbers=none]

%    ldc 1

%    ldc 1

%    if_icmpne L_ifelse $\quad\tikz[remember picture] \node (C) {\mbox{}};$

%    ldc 2

%    istore 0

%    goto L_ifend $\quad\tikz[remember picture] \node (A) {\mbox{}};$

% L_ifelse: $\quad\tikz[remember picture] \node[] (D) {\mbox{}};$

%    ldc 3

%    istore 1

% L_ifend: $\quad\tikz[remember picture] \node[] (B) {\mbox{}};$

% \end{lstlisting}

% \end{center}

% \begin{tikzpicture}[remember picture,overlay]

%   \draw[->,very thick] (A) edge [->,to path={-- ++(10mm,0mm) 

%            -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (B.east);

%   \draw[->,very thick] (C) edge [->,to path={-- ++(10mm,0mm) 

%            -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (D.east);

% \end{tikzpicture}

% \end{frame}

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

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

% \begin{frame}[c,fragile]

% \frametitle{Compiling Whiles}

% For example

% \begin{lstlisting}[mathescape,numbers=none,language=While]

% while x <= 10 do x := x + 1

% \end{lstlisting}

% \begin{center}

% \begin{lstlisting}[mathescape,language=JVMIS,numbers=none]

% L_wbegin: $\quad\tikz[remember picture] \node[] (LB) {\mbox{}};$

%    iload 0

%    ldc 10

%    if_icmpgt L_wend $\quad\tikz[remember picture] \node (LC) {\mbox{}};$

%    iload 0

%    ldc 1

%    iadd

%    istore 0

%    goto L_wbegin $\quad\tikz[remember picture] \node (LA) {\mbox{}};$

% L_wend: $\quad\tikz[remember picture] \node[] (LD) {\mbox{}};$

% \end{lstlisting}

% \end{center}

% \begin{tikzpicture}[remember picture,overlay]

%   \draw[->,very thick] (LA) edge [->,to path={-- ++(12mm,0mm) 

%            -- ++(0mm,17.3mm) |- (\tikztotarget)},line width=1mm] (LB.east);

%   \draw[->,very thick] (LC) edge [->,to path={-- ++(12mm,0mm) 

%            -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (LD.east);

% \end{tikzpicture}

% \end{frame}

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

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

% \begin{frame}[c,fragile]

% \frametitle{Compiling Writes}

% \small

% \begin{lstlisting}[language=JVMIS,mathescape,

%                    numbers=none,xleftmargin=-6mm]

% .method public static write(I)V 

%   .limit locals 1 

%   .limit stack 2 

%   getstatic java/lang/System/out 

%                             Ljava/io/PrintStream; 

%   iload 0

%   invokevirtual java/io/PrintStream/println(I)V 

%   return 

% .end method

% iload $E(x)$ 

% invokestatic XXX/XXX/write(I)V

% \end{lstlisting}

% \end{frame}

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

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

% \begin{frame}[c,fragile]

% \frametitle{Compiling Main}

% \footnotesize

% \begin{lstlisting}[language=JVMIS,mathescape,

%                    numbers=none,xleftmargin=-6mm]

% .class public XXX.XXX

% .super java/lang/Object

% .method public <init>()V

%     aload_0

%     invokenonvirtual java/lang/Object/<init>()V

%     return

% .end method

% .method public static main([Ljava/lang/String;)V

%     .limit locals 200

%     .limit stack 200

%       $\textit{\ldots{}here comes the compiled code\ldots}$

%     return

% .end method

% \end{lstlisting}

% \end{frame}

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

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

\begin{frame}[c,fragile]

\frametitle{Functional Programming}

\footnotesize

\begin{textblock}{13}(0.9,3)

\begin{lstlisting}[]numbers=none]

def fib(n) = if n == 0 then 0 

             else if n == 1 then 1 

             else fib(n - 1) + fib(n - 2);

def fact(n) = if n == 0 then 1 else n * fact(n - 1);

def ack(m, n) = if m == 0 then n + 1

                else if n == 0 then ack(m - 1, 1)

                else ack(m - 1, ack(m, n - 1));

def gcd(a, b) = if b == 0 then a else gcd(b, a % b);                

\end{lstlisting}

\end{textblock}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Fun-Grammar}

\bl{

\begin{plstx}[rhs style=]

: \meta{Exp} ::= \meta{Var} | \meta{Num}{\hspace{4cm}}

             |   \meta{Exp} + \meta{Exp} | ... | (\meta{Exp})

             |   \code{if} \meta{BExp} \code{then} \meta{Exp} \code{else} \meta{Exp}

             |   \code{write} \meta{Exp} {\hspace{5cm}}

             |   \meta{Exp} ; \meta{Exp}

             |   \textit{FunName} (\meta{Exp}, ... , \meta{Exp})\\

: \meta{BExp} ::= ...\\

: \meta{Def} ::= \code{def} \textit{FunName} ($\hspace{0.4mm}x_1$, ... , $x_n$) = \meta{Exp}\\               

: \meta{Prog} ::= \meta{Def} ; \meta{Prog}

               | \meta{Exp} ; \meta{Prog}

               | \meta{Exp}\\

\end{plstx}}

% Almost what is implemented - Exp ; Exp is left-recursive

%

\end{frame}

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

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

\begin{frame}[c, fragile]

\frametitle{Abstract Syntax Trees}

\footnotesize

\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]

abstract class Exp

abstract class BExp 

abstract class Decl

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 If(a: BExp, e1: Exp, e2: Exp) extends Exp

case class Write(e: Exp) extends Exp

case class Sequ(e1: Exp, e2: Exp) extends Exp

case class Call(name: String, args: List[Exp]) extends Exp

case class Bop(o: String, a1: Exp, a2: Exp) extends BExp

case class Def(name: String, 

               args: List[String], 

               body: Exp) extends Decl

case class Main(e: Exp) extends Decl

\end{lstlisting}

\end{frame}

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

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

\begin{frame}[c, fragile]

\frametitle{Ideas}

Use separate JVM methods for each Fun-function.\bigskip

Compile \bl{\texttt{exp}}s such that the result of the expression

is on top of the stack.\bigskip

\begin{itemize}

\item \texttt{\color{codepurple}{write}}\texttt{(1 + 2)}

\item \texttt{1 + 2; 3 + 4} 

\end{itemize}

\end{frame}

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

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

\begin{frame}[c, fragile]

\frametitle{Sequences}

Compiling \texttt{exp1 ; exp2}:\bigskip

\begin{lstlisting}[mathescape,language=JVMIS, numbers=none]

$\textit{compile}$(exp1)

pop

$\textit{compile}$(exp2)

\end{lstlisting}

\end{frame}

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

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

\begin{frame}[t, fragile]

\frametitle{Write}

Compiling call to \texttt{write(1+2)}:\bigskip

\begin{lstlisting}[mathescape,language=JVMIS, numbers=none]

$\textit{compile}$(1+2)

dup

invokestatic XXX/XXX/write(I)V

\end{lstlisting}\bigskip

\small

needs the helper method

\footnotesize

\begin{lstlisting}[language=JVMIS, 

                   xleftmargin=2mm, 

                   numbers=none]

.method public static write(I)V 

   .limit locals 1

   .limit stack 2

   getstatic java/lang/System/out Ljava/io/PrintStream; 

   iload 0 

   invokevirtual java/io/PrintStream/println(I)V 

   return 

.end method

\end{lstlisting}

\end{frame}

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

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

\begin{frame}[t, fragile]

\frametitle{Function Definitions}

\footnotesize

\begin{lstlisting}[language=JVMIS, 

                   xleftmargin=2mm, 

                   numbers=none]

.method public static write(I)V 

   .limit locals 1

   .limit stack 2

   getstatic java/lang/System/out Ljava/io/PrintStream; 

   iload 0 

   invokevirtual java/io/PrintStream/println(I)V 

   return 

.end method

\end{lstlisting}\bigskip

\small We will need methods for definitions like\footnotesize\medskip

\begin{lstlisting}[language=JVMIS, 

                   xleftmargin=2mm, 

                   numbers=none]

def fname (x1, ... , xn) = ...                   

.method public static fname (I...I)I

  .limit locals ??

  .limit stack ?? 

  ??

.end method

\end{lstlisting}

\end{frame}

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

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

\begin{frame}[c, fragile]

\frametitle{Stack Estimation}

\small

\mbox{}\\[-15mm]

\bl{\begin{center}

\begin{tabular}{@{\hspace{-4mm}}l@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}

$\textit{estimate}(n)$ & $\dn$ & $1$\\

$\textit{estimate}(x)$ & $\dn$ & $1$\\

$\textit{estimate}(a_1\;aop\;a_2)$ & $\dn$ &

$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\

$\textit{estimate}(\pcode{if}\;b\;\pcode{then}\;e_1\;\pcode{else}\;e_2)$ & $\dn$ & 

$\textit{estimate}(b) +$\\ 

& & $\quad max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\

$\textit{estimate}(\pcode{write}(e))$ & $\dn$ & 

$\textit{estimate}(e) + 1$\\

$\textit{estimate}(e_1 ; e_2)$ & $\dn$ & 

$max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\

$\textit{estimate}(f(e_1, ..., e_n))$ & $\dn$ & 

$\sum_{i = 1..n}\;estimate(e_i)$\medskip\\

$\textit{estimate}(a_1\;bop\;a_2)$ & $\dn$ &

$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\

\end{tabular}

\end{center}}

\end{frame}

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

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

\begin{frame}[fragile]

\frametitle{Successor Function}

\begin{textblock}{7}(1,2.5)\footnotesize

\begin{minipage}{6cm}