# HG changeset patch # User Christian Urban # Date 1447787571 0 # Node ID fa2589ec0faef317f28ee68533fee65b09dba57b # Parent e8ac05fe26303c74d2857e19e523eb2bc4bd863d updated diff -r e8ac05fe2630 -r fa2589ec0fae handouts/ho08.pdf Binary file handouts/ho08.pdf has changed 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 diff -r e8ac05fe2630 -r fa2589ec0fae langs.sty --- 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},% diff -r e8ac05fe2630 -r fa2589ec0fae slides/slides09.pdf Binary file slides/slides09.pdf has changed diff -r e8ac05fe2630 -r fa2589ec0fae slides/slides09.tex --- 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{ \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}