\documentclass[dvipsnames,14pt,t]{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 (8)\\[3mm] 

  \end{tabular}}

  \normalsize

  \begin{center}

  \begin{tabular}{ll}

  Email:  & christian.urban at kcl.ac.uk\\

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

  Slides: & KEATS (also home work is there)\\

  \end{tabular}

  \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{3cm}}

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

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

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

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

Compile \texttt{exp} 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 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}

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

.method public static suc(I)I 

.limit locals 1

.limit stack 2

  iload 0

  ldc 1

  iadd

  ireturn

.end method 

\end{lstlisting}

\end{minipage}

\end{textblock}

\begin{textblock}{7}(6,8)

\begin{bubble}[5cm]\small

\begin{lstlisting}[language=Lisp,

                   basicstyle=\ttfamily, 

                   numbers=none,

                   xleftmargin=1mm,linebackgroundcolor=\color{cream}]

def suc(x) = x + 1;

\end{lstlisting}

\end{bubble}

\end{textblock}

\end{frame}