--- a/progs/fun.scala Mon Dec 02 23:21:22 2013 +0000
+++ b/progs/fun.scala Wed Dec 04 01:51:22 2013 +0000
@@ -23,7 +23,7 @@
def apply(s: String) : RANGE = RANGE(s.toList)
}
def NMTIMES(r: Rexp, n: Int, m: Int) = {
- if(m < n) throw new IllegalArgumentException("the number m cannot be smaller than n.")
+ if (m < n) throw new IllegalArgumentException("the number m cannot be smaller than n.")
else NUPTOM(r, n, m - n)
}
@@ -341,14 +341,6 @@
(Defn ~ T_SEMI ~ Prog) ==> { case ((x, y), z) => x :: z : List[Decl] } ||
(Exp ==> ((s) => List(Main(s)) : List[Decl]))
-// parser examples
-
-val p12_toks = tokenizer(fromFile("defs.rec"))
-val p12_ast = Prog.parse_all(p12_toks)
-//println(p12_toks.mkString(","))
-//println(p12_ast)
-
-
// compiler - built-in functions
// copied from http://www.ceng.metu.edu.tr/courses/ceng444/link/jvm-cpm.html
@@ -431,57 +423,6 @@
compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpgt " + jmp + "\n")
}
-
-def compile_expT(a: Exp, env : Mem, name: String) : Instrs = a match {
- case Num(i) => List("ldc " + i.toString + "\n")
- case Var(s) => List("iload " + env(s).toString + "\n")
- case Aop("+", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("iadd\n")
- case Aop("-", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("isub\n")
- case Aop("*", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("imul\n")
- case Aop("/", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("idiv\n")
- case Aop("%", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("irem\n")
- case If(b, a1, a2) => {
- val if_else = Fresh("If_else")
- val if_end = Fresh("If_end")
- compile_bexp(b, env, if_else) ++
- compile_expT(a1, env, name) ++
- List("goto " + if_end + "\n") ++
- List("\n" + if_else + ":\n\n") ++
- compile_expT(a2, env, name) ++
- List("\n" + if_end + ":\n\n")
- }
- 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")
- }
- case Sequ(a1, a2) => {
- compile_expT(a1, env, "") ++ List("pop\n") ++ compile_expT(a2, env, name)
- }
- case Write(a1) => {
- compile_expT(a1, env, "") ++
- List("dup\n",
- "invokestatic XXX/XXX/write(I)V\n")
- }
-}
-
-def compile_bexpT(b: BExp, env : Mem, jmp: String) : Instrs = b match {
- case Bop("==", a1, a2) =>
- compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("if_icmpne " + jmp + "\n")
- case Bop("!=", a1, a2) =>
- compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("if_icmpeq " + jmp + "\n")
- case Bop("<", a1, a2) =>
- compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("if_icmpge " + jmp + "\n")
- case Bop("<=", a1, a2) =>
- compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("if_icmpgt " + jmp + "\n")
-}
-
-
def compile_decl(d: Decl) : Instrs = d match {
case Def(name, args, a) => {
val env = args.zipWithIndex.toMap
@@ -490,21 +431,18 @@
".limit locals " + args.length.toString + "\n",
".limit stack " + (1 + max_stack_exp(a)).toString + "\n",
name + "_Start:\n") ++
- //compile_exp(a, env) ++
- compile_expT(a, env, name) ++
+ compile_exp(a, env) ++
List("ireturn\n",
".end method \n\n")
}
case Main(a) => {
- val main_begin =
- List(".method public static main([Ljava/lang/String;)V\n",
- ".limit locals 200\n",
- ".limit stack 200\n")
- val main_end =
- List("invokestatic XXX/XXX/write(I)V\n",
- "return\n",
- ".end method\n")
- main_begin ++ compile_exp(a, Map()) ++ main_end
+ List(".method public static main([Ljava/lang/String;)V\n",
+ ".limit locals 200\n",
+ ".limit stack 200\n") ++
+ compile_exp(a, Map()) ++
+ List("invokestatic XXX/XXX/write(I)V\n",
+ "return\n",
+ ".end method\n")
}
}
--- a/slides/slides10.tex Mon Dec 02 23:21:22 2013 +0000
+++ b/slides/slides10.tex Wed Dec 04 01:51:22 2013 +0000
@@ -18,63 +18,42 @@
\usetikzlibrary{plotmarks}
\usepackage{graphicx}
\usepackage{pgfplots}
+\usepackage{soul}
\usepackage{../langs}
\usepackage{../data}
+\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 10, King's College London, 4.~December 2013}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
-
-% The data files, written on the first run.
-\begin{filecontents}{compiled.data}
-%1 0.234146
-%5000 0.227539
-%10000 0.280748
-50000 1.087897
-100000 3.713165
-250000 21.6624545
-500000 85.872613
-750000 203.6408015
-1000000 345.736574
-\end{filecontents}
-
-\begin{filecontents}{interpreted.data}
-%1 0.00503
-200 1.005863
-400 7.8296765
-500 15.43106
-600 27.2321885
-800 65.249271
-1000 135.4493445
-1200 232.134097
-1400 382.527227
-\end{filecontents}
-
-\begin{filecontents}{interpreted2.data}
-%1 0.00503
-200 1.005863
-400 7.8296765
-600 27.2321885
-800 65.249271
-1000 135.4493445
-1200 232.134097
-1400 382.527227
-\end{filecontents}
-
-\begin{filecontents}{compiled2.data}
-200 0.222058
-400 0.215204
-600 0.202031
-800 0.21986
-1000 0.205934
-1200 0.1981615
-1400 0.207116
-\end{filecontents}
-
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -112,24 +91,533 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
-\begin{frame}[c]
-\frametitle{Revision: Proofs}
+\begin{frame}[t]
+\frametitle{Last Week}
+
+\begin{center}
+if \bl{$\varnothing$} does not occur in \bl{$r$} \;\;then\;\;\bl{$L(r) \not= \{\}$}
+\end{center}
+
+\noindent
+holds, or equivalently
\begin{center}
-%%\includegraphics[scale=0.4]{river-stones.jpg}
+\bl{$L(r) = \{\}$} \;\;implies\;\; \bl{$\varnothing$} occurs in \bl{$r$}.\pause
+\end{center}
+
+\begin{center}
+\bl{\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+$occurs(\varnothing)$ & $\dn$ & $true$\\
+$occurs(\epsilon)$ & $\dn$ & $f\!alse$\\
+$occurs (c)$ & $\dn$ & $f\!alse$\\
+$occurs (r_1 + r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\
+$occurs (r_1 \cdot r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\
+$occurs (r^*)$ & $\dn$ & $occurs(r)$ \\
+\end{tabular}}
\end{center}
\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Functional Programming}
+
+\footnotesize
+\begin{textblock}{13}(0.9,3)
+\lstset{emph={def,if,then,else},emphstyle=\color{javapurple}}
+\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<presentation>{
\begin{frame}[c]
-\frametitle{Subsets}
+
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\Large
-\bl{$A \subseteq B$}\bigskip\bigskip\\
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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{tikzpicture}\small
+\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
+{\begin{minipage}{5cm}
+\begin{lstlisting}[language=Lisp,basicstyle=\ttfamily, numbers=none]
+def suc(x) = x + 1;
+\end{lstlisting}
+\end{minipage}};
+\end{tikzpicture}
+\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{tikzpicture}\small
+\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
+{\begin{minipage}{7cm}
+\begin{lstlisting}[language=Lisp,basicstyle=\ttfamily, numbers=none]
+def add(x, y) =
+ if x == 0 then y
+ else suc(add(x - 1, y));
+\end{lstlisting}
+\end{minipage}};
+\end{tikzpicture}
+\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}
-\bl{$\forall e.\; e \in A \Rightarrow e \in B$}
+\begin{textblock}{7}(6,7)
+\begin{tikzpicture}\small
+\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
+{\begin{minipage}{7cm}
+\begin{lstlisting}[language=Lisp,basicstyle=\ttfamily, numbers=none]
+def facT(n, acc) =
+ if n == 0 then acc
+ else facT(n - 1, n * acc);
+\end{lstlisting}
+\end{minipage}};
+\end{tikzpicture}
+\end{textblock}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[fragile]
+%\frametitle{Factorial}
+
+\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{tikzpicture}\small
+\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
+{\begin{minipage}{7cm}
+\begin{lstlisting}[language=Lisp,basicstyle=\ttfamily, numbers=none]
+def facT(n, acc) =
+ if n == 0 then acc
+ else facT(n - 1, n * acc);
+\end{lstlisting}
+\end{minipage}};
+\end{tikzpicture}
+\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<presentation>{
+\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%