
diff -r e8ac05fe2630 -r fa2589ec0fae handouts/ho08.tex
--- a/handouts/ho08.tex	Tue Nov 17 15:03:08 2015 +0000
+++ b/handouts/ho08.tex	Tue Nov 17 19:12:51 2015 +0000
@@ -5,58 +5,54 @@
 \usepackage{../graphics}
 
 
+
 \begin{document}
+\lstset{morekeywords={def,if,then,else,write,read},keywordstyle=\color{codepurple}\bfseries}
+
 
 \section*{Handout 8 (A Functional Language)}
 
-The purpose of a compiler is to transform a program, a human
-can read and write, into code the machine can run as fast as
-possible. The fastest code would be machine code the CPU can
-run directly, but it is often enough to improve the speed of a
-program by just targeting a virtual machine. This produces not
-the fastest possible code, but code that is fast enough and
-has the advantage that the virtual machine takes care of
-things a compiler would normally need to take care of (like
-explicit memory management).
+
+The language we looked at in the previous lecture was rather 
+primitive and the compiler rather crude. In this handout
+we like to have a look at a slightly more comfortable
+language and a tiny-teeny bit more realistic compiler. A small
+collection of programs we want to be able to write and compile
+is as follows:
 
-As a first example we will implement a compiler for the very
-simple While-language. It will generate code for the Java
-Virtual Machine (JVM). This is a stack-based virtual machine,
-a fact which will make it easy to generate code for arithmetic
-expressions. For example for generating code for the
-expression $1 + 2$ we need to generate the following three
-instructions
+\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);
 
-\begin{lstlisting}[numbers=none]
-ldc 1
-ldc 2
-iadd 
+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}
 
-\noindent The first instruction loads the constant $1$ onto
-the stack, the next one $2$, the third instruction adds both
-numbers together replacing the top two elements of the stack
-with the result $3$. For simplicity, we will throughout
-consider only integer numbers and results. Therefore we can
-use the JVM instructions \code{iadd}, \code{isub},
-\code{imul}, \code{idiv} and so on. The \code{i} stands for
-integer instructions in the JVM (alternatives are \code{d} for
-doubles, \code{l} for longs and \code{f} for floats).
-
-Recall our grammar for arithmetic expressions ($E$ is the
-starting symbol):
+\noindent We will still restrict us to just programs about
+integers, that means for example that every function needs to
+return an integer. The grammar of the Fun-language is slightly 
+simpler than the While-language, because almost everything is 
+an expression. The grammar rules are as follows:
 
 
-\begin{plstx}[rhs style=, margin=3cm]
: \meta{E} ::= \meta{T} $+$ \meta{E}
-         | \meta{T} $-$ \meta{E}
-         | \meta{T}\\
-: \meta{T} ::= \meta{F} $*$ \meta{T}
-          | \meta{F} $\backslash$ \meta{T}
-          | \meta{F}\\
-: \meta{F} ::= ( \meta{E} )
-          | \meta{Id}
-          | \meta{Num}\\
\end{plstx}
-
+\begin{plstx}[rhs style=,margin=1.5cm]
+: \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{5cm}}
+             |   \meta{Exp} ; \meta{Exp}  {\hspace{5cm}}
+             |   \textit{FunName} (\meta{Exp}, ..., \meta{Exp})\\
+: \meta{BExp} ::= ...\\
+: \meta{Decl} ::= \meta{Def} ; \meta{Decl}
+             | \meta{Exp}\\
+: \meta{Def} ::= \code{def} \textit{FunName} ($x_1$, ..., $x_2$)\\               
+\end{plstx}
 
 \noindent where \meta{Id} stands for variables and \meta{Num}
 for numbers. For the moment let us omit variables from




