# HG changeset patch # User Christian Urban # Date 1416787891 0 # Node ID d384fe01d0e888e6706cee4881ff59c6b907a496 # Parent 640e4a05cd9bf0ab9762c19f2438157823f64602 updated diff -r 640e4a05cd9b -r d384fe01d0e8 slides/slides09.pdf Binary file slides/slides09.pdf has changed diff -r 640e4a05cd9b -r d384fe01d0e8 slides/slides09.tex --- a/slides/slides09.tex Sun Nov 23 22:12:18 2014 +0000 +++ b/slides/slides09.tex Mon Nov 24 00:11:31 2014 +0000 @@ -3,12 +3,39 @@ \usepackage{../langs} \usepackage{../data} \usepackage{../graphics} +\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}{AFL 09, King's College London} \newcommand{\bl}[1]{\textcolor{blue}{#1}} + \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -33,6 +60,500 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c,fragile] +\frametitle{Functional Programming} + +\footnotesize +\begin{textblock}{13}(0.9,3) +\lstset{emph={def,if,then,else},emphstyle=\color{codepurple}} +\begin{lstlisting}[basicstyle=\ttfamily, 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} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] + +\begin{center} +\bl{\begin{tabular}{@{}lcl@{}} +\textit{Exp} & $\rightarrow$ & \textit{Var} $|$ \textit{Num}\\ + & $|$ & \textit{Exp} \texttt{+} \textit{Exp} $|$ ... $|$ ( \textit{Exp} )\\ + & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Exp} \;\texttt{else}\; \textit{Exp}\\ + & $|$ & \texttt{write}\;\textit{Exp}\\ + & $|$ & \textit{Exp}\;\texttt{;}\;\textit{Exp}\\ + & $|$ & \textit{FunName} \texttt{(}\textit{Exp},...,\textit{Exp}\texttt{)}\medskip\\ +\textit{BExp} & $\rightarrow$ & \ldots\medskip\\ +\textit{Decl} & $\rightarrow$ & \textit{Def} \;\texttt{;}\; \textit{Decl}\\ + & $|$ & \textit{Exp}\medskip\\ +\textit{Def} & +$\rightarrow$ & \texttt{def} \textit{FunName}\texttt{(}\textit{x}$_1$,..., \textit{x}$_n$\texttt{)} \texttt{=} \textit{Exp}\\ +\end{tabular}} +\end{center} + + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c, fragile] +\frametitle{Abstract Syntax Tree} + +\footnotesize +\begin{textblock}{13}(0.3,2) +\begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] +abstract class Exp +abstract class BExp +abstract class Decl + +case class + Def(name: String, args: List[String], body: Exp) + extends Decl +case class Main(e: Exp) extends Decl + +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 Sequ(e1: Exp, e2: Exp) extends Exp +case class Bop(o: String, a1: Exp, a2: Exp) extends BExp +\end{lstlisting} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c, fragile] +\frametitle{Mathematical Functions} + +Compilation of some mathematical functions: + +\begin{center} +\begin{tabular}{lcl} +\texttt{Aop("+", a1, a2)} & $\Rightarrow$ & \texttt{...iadd}\\ +\texttt{Aop("-", a1, a2)} & $\Rightarrow$ & \texttt{...isub}\\ +\texttt{Aop("*", a1, a2)} & $\Rightarrow$ & \texttt{...imul}\\ +\texttt{Aop("/", a1, a2)} & $\Rightarrow$ & \texttt{...idiv}\\ +\texttt{Aop("\%", a1, a2)} & $\Rightarrow$ & \texttt{...irem}\\ +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c, fragile] +\frametitle{Boolean Expressions} + +Compilation of boolean expressions: + +\begin{center} +\begin{tikzpicture}[node distance=2mm and 4mm, + block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, + point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, + skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] +\node (A1) [point] {}; +\node (b) [block, right=of A1] {code of \bl{$b$}}; +\node (A2) [point, right=of b] {}; +\node (cs1) [block, right=of A2] {code of \bl{$cs_1$}}; +\node (A3) [point, right=of cs1] {}; +\node (cs2) [block, right=of A3] {code of \bl{$cs_2$}}; +\node (A4) [point, right=of cs2] {}; + +\only<1>{ +\draw (A1) edge [->, red, line width=1mm] (b); +\draw (b) edge [->, red, line width=1mm] (A2); +\draw (A2) edge [skip loop] (A3); +\draw (A3) edge [->, red, line width=1mm] (cs2); +\draw (cs2) edge [->,red, line width=1mm] (A4); +\node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};} +\end{tikzpicture} +\end{center} + +\begin{center} +\begin{tabular}{lcl} +\texttt{Bop("==", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpne...}\\ +\texttt{Bop("!=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpeq...}\\ +\texttt{Bop("<", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpge...}\\ +\texttt{Bop("<=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpgt...}\\ +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t, fragile] +\frametitle{Sequences} + +Compiling \texttt{arg1 ; arg2}: + + +\begin{textblock}{7}(2,5)\footnotesize +\begin{minipage}{6cm} +\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] +...arg1... +pop +...arg1... +\end{lstlisting} +\end{minipage} +\end{textblock} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t, fragile] +\frametitle{Write} + +Compiling \texttt{write(arg)}: + + +\begin{textblock}{7}(2,4)\footnotesize +\begin{minipage}{6cm} +\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] +...arg... +dup +invokestatic XXX/XXX/write(I)V +\end{lstlisting} +\end{minipage} +\end{textblock} + + + +\begin{textblock}{7}(2,8)\footnotesize +\begin{minipage}{6cm} +\begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] +case Write(a1) => { + compile_exp(a1, env) ++ + List("dup\n", + "invokestatic XXX/XXX/write(I)V\n") + } +\end{lstlisting} +\end{minipage} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c, fragile] +\frametitle{Functions} + +\begin{textblock}{7}(1,2)\footnotesize +\begin{minipage}{6cm} +\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] +.method public static write(I)V + .limit locals 5 + .limit stack 5 + iload 0 + getstatic java/lang/System/out Ljava/io/PrintStream; + swap + invokevirtual java/io/PrintStream/println(I)V + return +.end method +\end{lstlisting} +\end{minipage} +\end{textblock} + + +\begin{textblock}{10}(1,9.8) +\small We will need for definitions\\[-8mm]\mbox{}\footnotesize +\begin{center} +\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] +.method public static f (I...I)I + .limit locals ?? + .limit stack ?? + ?? +.end method +\end{lstlisting} +\end{center} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c, fragile] +\frametitle{Stack Estimation} +\footnotesize +\begin{center} +\begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] +def max_stack_exp(e: Exp): Int = e match { + case Call(_, args) => args.map(max_stack_exp).sum + case If(a, e1, e2) => max_stack_bexp(a) + + (List(max_stack_exp(e1), max_stack_exp(e1)).max) + case Write(e) => max_stack_exp(e) + 1 + case Var(_) => 1 + case Num(_) => 1 + case Aop(_, a1, a2) => + max_stack_exp(a1) + max_stack_exp(a2) + case Sequ(e1, e2) => + List(max_stack_exp(e1), max_stack_exp(e2)).max +} + +def max_stack_bexp(e: BExp): Int = e match { + case Bop(_, a1, a2) => + max_stack_exp(a1) + max_stack_exp(a2) +} +\end{lstlisting} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[fragile] +\frametitle{Successor} + +\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 + 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] +def suc(x) = x + 1; +\end{lstlisting} +\end{bubble} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[fragile] +\frametitle{Addition} + +\begin{textblock}{7}(1,1.5)\footnotesize +\begin{minipage}{6cm} +\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] +.method public static add(II)I +.limit locals 2 +.limit stack 4 + iload 0 + ldc 0 + if_icmpne If_else_2 + iload 1 + goto If_end_3 +If_else_2: + iload 0 + ldc 1 + isub + iload 1 + invokestatic defs/defs/add(II)I + invokestatic defs/defs/suc(I)I +If_end_3: + ireturn +.end method +\end{lstlisting} +\end{minipage} +\end{textblock} + +\begin{textblock}{7}(6,6.2) +\begin{bubble}[7cm]\small +\begin{lstlisting}[language=Lisp, + basicstyle=\ttfamily, + numbers=none, + xleftmargin=1mm] +def add(x, y) = + if x == 0 then y + else suc(add(x - 1, y)); +\end{lstlisting} +\end{bubble} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[fragile] +\frametitle{Factorial} + +\begin{textblock}{7}(1,1.5)\footnotesize +\begin{minipage}{6cm} +\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] +.method public static facT(II)I +.limit locals 2 +.limit stack 4 + iload 0 + ldc 0 + if_icmpne If_else_2 + iload 1 + goto If_end_3 +If_else_2: + iload 0 + ldc 1 + isub + iload 0 + iload 1 + imul + invokestatic fact/fact/facT(II)I +If_end_3: + ireturn +.end method +\end{lstlisting} +\end{minipage} +\end{textblock} + +\begin{textblock}{7}(6,7) +\begin{bubble}[7cm]\small +\begin{lstlisting}[language=Lisp, + basicstyle=\ttfamily, + numbers=none, + xleftmargin=1mm] +def facT(n, acc) = + if n == 0 then acc + else facT(n - 1, n * acc); +\end{lstlisting} +\end{bubble} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[fragile] + +\begin{textblock}{7}(1,-0.2)\footnotesize +\begin{minipage}{6cm} +\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none, escapeinside={(*@}{@*)}] +.method public static facT(II)I +.limit locals 2 +.limit stack 4 +(*@\hl{facT\_Start:} @*) + iload 0 + ldc 0 + if_icmpne If_else_2 + iload 1 + goto If_end_3 +If_else_2: + iload 0 + ldc 1 + isub + iload 0 + iload 1 + imul + (*@\hl{istore 1} @*) + (*@\hl{istore 0} @*) + (*@\hl{goto facT\_Start} @*) +If_end_3: + ireturn +.end method +\end{lstlisting} +\end{minipage} +\end{textblock} + +\begin{textblock}{7}(6,7) +\begin{bubble}[7cm]\small +\begin{lstlisting}[language=Lisp, + basicstyle=\ttfamily, + numbers=none, + xleftmargin=1mm] +def facT(n, acc) = + if n == 0 then acc + else facT(n - 1, n * acc); +\end{lstlisting} +\end{bubble} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c, fragile] +\frametitle{Tail Recursion} + +A call to \texttt{f(args)} is usually compiled as\medskip + +{\small\begin{lstlisting}[basicstyle=\ttfamily, numbers=none] + args onto stack + invokestatic .../f +\end{lstlisting}}\pause + + +A call is in tail position provided:\medskip + +{\small\begin{itemize} +\item \texttt{if Bexp then \hl{Exp} else \hl{Exp}} +\item \texttt{Exp ; \hl{Exp}} +\item \texttt{Exp op Exp} +\end{itemize}}\medskip + +then a call \texttt{f(args)} can be compiled as\medskip\small + +\begin{lstlisting}[basicstyle=\ttfamily, numbers=none] + prepare environment + jump to start of function +\end{lstlisting} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c, fragile] +\frametitle{Tail Recursive Call} +\footnotesize + +\begin{textblock}{13}(-0.3,2) +\begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] +def compile_expT(a: Exp, env: Mem, name: String): Instrs = + ... + case Call(n, args) => if (name == n) + { + val stores = args.zipWithIndex.map + { case (x, y) => "istore " + y.toString + "\n" } + args.flatMap(a => compile_expT(a, env, "")) ++ + stores.reverse ++ + List ("goto " + n + "_Start\n") + } + else + { + val is = "I" * args.length + args.flatMap(a => compile_expT(a, env, "")) ++ + List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n") + } +\end{lstlisting} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] @@ -199,202 +720,6 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{Our Compiler} - - \begin{center} - \begin{tikzpicture}[scale=1] - - \node (0) at (-2.3,0) {}; - - \node (A) at (0,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=20mm] {}; - \node [below right] at (A.north west) {lexer}; - - \node (B) at (3,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=20mm] {}; - \node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser}; - - \node (C) at (6,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=20mm] {}; - \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen}; - - \node (1) at (8.4,0) {}; - - \draw [->,line width=4mm] (0) -- (A); - \draw [->,line width=4mm] (A) -- (B); - \draw [->,line width=4mm] (B) -- (C); - \draw [->,line width=4mm] (C) -- (1); - \end{tikzpicture} - \end{center} - -lexer input: string\medskip\\ -lexer output: sequence of tokens\\ -\mbox{}\hfill(white space and comments filtered out)\medskip\\ -parser output: abstract syntax tree\medskip\\ -code gen output: assembler byte code / \\ -\mbox{}\hfill assembler machine code -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}For-Loops\end{tabular}} - - -\begin{center}\Large -\texttt{for} \;\textit{Id} \texttt{:=} \textit{AExp}\; \texttt{upto} \;\textit{AExp}\; \texttt{do} \textit{Block} -\end{center}\bigskip - -\begin{center} -\begin{minipage}{8cm} -\begin{tabular}{l} -\texttt{for i := 2 upto 4 do \{}\\ -\hspace{5mm}\texttt{write i}\\ -\texttt{\}}\ -\end{tabular} -\end{minipage} -\end{center} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}While-Language\end{tabular}} - - -\begin{center} -\bl{\begin{tabular}{@{}lcl@{}} -$Stmt$ & $\rightarrow$ & $\text{skip}$\\ - & $|$ & $Id := AExp$\\ - & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\ - & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\\ - & $|$ & $\alert{\text{write}\; Id}$\\ - & $|$ & $\alert{\text{read}\; Id}$\medskip\\ -$Stmts$ & $\rightarrow$ & $Stmt \;\text{;}\; Stmts$\\ - & $|$ & $Stmt$\medskip\\ -$Block$ & $\rightarrow$ & $\{ Stmts \}$\\ - & $|$ & $Stmt$\medskip\\ -$AExp$ & $\rightarrow$ & \ldots\\ -$BExp$ & $\rightarrow$ & \ldots\\ -\end{tabular}} -\end{center} - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Interpreter\end{tabular}} - -\begin{center} -\bl{\begin{tabular}{@{}lcl@{}} -$\text{eval}(n, E)$ & $\dn$ & $n$\\ -$\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\ -$\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\ -$\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\ -$\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\ -$\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\ -$\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\ -$\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\ -\end{tabular}} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}} - -\begin{center} -\bl{\begin{tabular}{@{}lcl@{}} -$\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\ -$\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\ -\multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\ -\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\; -\text{eval}(cs_1,E)$}\\ -\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\ -\multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\ -\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\ -\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\; -\text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\ -\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\ -$\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\ -\end{tabular}} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling Writes\end{tabular}} - -{\Large\bl{write $x$}} - -\begin{center} -\small\bl{\begin{tabular}{l} -.method public static write(I)V\hspace{1cm}\textcolor{black}{(library function)}\\ -\;\; .limit locals 5 \\ -\;\; .limit stack 5 \\ -\;\; iload 0 \\ -\;\; getstatic java/lang/System/out Ljava/io/PrintStream;\\ -\;\; swap \\ -\;\; invokevirtual java/io/PrintStream/println(I)V \\ -\;\; return \\ -.end method\bigskip\bigskip\\ -% -\normalsize -iload $E(x)$\\ -invokestatic write(I)V\\ -\end{tabular}} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\begin{center} -\small\bl{\begin{tabular}{l} -.class public XXX.XXX\\ -.super java/lang/Object\\ -\\ -.method public ()V\\ -\;\; aload\_0\\ -\;\; invokenonvirtual java/lang/Object/()V\\ - \;\; return\\ -.end method\\ -\\ -.method public static main([Ljava/lang/String;)V\\ -\;\; .limit locals 200\\ -\;\; .limit stack 200\\ -\\ - \textcolor{black}{(here comes the compiled code)}\\ -\\ -\;\; return\\ -.end method\\ -\end{tabular}} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}