\usepackage{xcolor}

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

  \LARGE Formal Languages (8)\\[3mm] 

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

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

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

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

\tikzset{edge from parent/.style={draw,very thick}}
\Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]]
\end{tikzpicture}}

\begin{column}{.3\textwidth}

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

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

\begin{tikzpicture}[remember picture,overlay]
  \draw[->,very thick] (A) edge [->,to path={-- ++(10mm,0mm) 

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

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

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

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

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