Binary file handouts/ho08.pdf has changed
--- 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
--- a/langs.sty Tue Nov 17 15:03:08 2015 +0000
+++ b/langs.sty Tue Nov 17 19:12:51 2015 +0000
@@ -19,7 +19,7 @@
new,null,object,override,package,%
private,protected,requires,return,sealed,%
super,this,throw,trait,true,try,%
- type,val,var,while,with,yield},%
+ type,val,var,while,with,yield,write,read},%
otherkeywords={=>,<-,<\%,<:,>:,\#},%
sensitive=true,%
%directives={Int,Char,Rexp,String,Boolean,BigInt,Unit,List,Set},%
Binary file slides/slides09.pdf has changed
--- a/slides/slides09.tex Tue Nov 17 15:03:08 2015 +0000
+++ b/slides/slides09.tex Tue Nov 17 19:12:51 2015 +0000
@@ -3,6 +3,7 @@
\usepackage{../langs}
\usepackage{../data}
\usepackage{../graphics}
+\usepackage{../grammar}
\usepackage{soul}
\tikzset{onslide/.code args={<#1>#2}{%
@@ -17,7 +18,7 @@
\newcommand<>\btHL[1][]{%
\only#2{\begin{btHighlight}[#1]\bgroup\aftergroup\bt@HL@endenv}%
}
-\def\bt@HL@endenv{%
+\def\bt@HL@endenv{%b jm
\end{btHighlight}%
\egroup
}
@@ -30,6 +31,7 @@
}
\makeatother
+\lstset{morekeywords={def,if,then,else,write,read},keywordstyle=\color{codepurple}\bfseries}
% beamer stuff
\renewcommand{\slidecaption}{AFL 09, King's College London}
@@ -65,7 +67,6 @@
\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
@@ -85,30 +86,29 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\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}
+\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{Decl} ::= \meta{Def} ; \meta{Decl}
+ | \meta{Exp}\\
+: \meta{Def} ::= \code{def} \textit{FunName} ($\hspace{0.4mm}x_1$, ..., $x_2$)\\
+\end{plstx}}
-\end{frame}}
+
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c, fragile]
\frametitle{Abstract Syntax Tree}