603
|
1 |
% !TEX program = xelatex
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
2 |
\documentclass{article}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
3 |
\usepackage{../style}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
4 |
\usepackage{../langs}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
5 |
\usepackage{../grammar}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
\usepackage{../graphics}
|
381
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
7 |
\usepackage{amssymb}
|
693
|
8 |
\usepackage{xcolor}
|
|
9 |
|
|
10 |
\usepackage[most]{tcolorbox}
|
|
11 |
|
|
12 |
\newtcbox{\hm}[1][]{%
|
|
13 |
size=fbox,
|
|
14 |
tcbox raise base, nobeforeafter,
|
|
15 |
enhanced, colframe=gray,
|
|
16 |
colback=gray!30, boxrule=1pt,
|
|
17 |
fontupper=\ttfamily,
|
|
18 |
#1}
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
19 |
|
405
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
% modern compilers are different
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
% https://channel9.msdn.com/Blogs/Seth-Juarez/Anders-Hejlsberg-on-Modern-Compiler-Construction
|
379
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
|
492
|
23 |
%halting problem
|
|
24 |
%https://dfilaretti.github.io/2017-04-30/halting-problem
|
|
25 |
|
|
26 |
|
693
|
27 |
|
|
28 |
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
29 |
\begin{document}
|
379
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
30 |
\lstset{morekeywords={def,if,then,else,write,read},keywordstyle=\color{codepurple}\bfseries}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
32 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
\section*{Handout 8 (A Functional Language)}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
|
379
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
35 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
The language we looked at in the previous lecture was rather
|
603
|
37 |
primitive and the compiler rather crude---everything was
|
604
|
38 |
essentially compiled into a big monolithic chunk of code
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
39 |
inside the main function. In this handout we like to have a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
40 |
look at a slightly more comfortable language, which I call
|
603
|
41 |
Fun-language, and a tiny-teeny bit more realistic compiler.
|
693
|
42 |
The Fun-language is a small functional programming language. A small
|
604
|
43 |
collection of programs we want to be able to write and compile
|
379
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
44 |
is as follows:
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
45 |
|
381
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
\begin{lstlisting}[numbers=none]
|
379
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
def fib(n) = if n == 0 then 0
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
48 |
else if n == 1 then 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
49 |
else fib(n - 1) + fib(n - 2);
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
50 |
|
379
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
51 |
def fact(n) = if n == 0 then 1 else n * fact(n - 1);
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
52 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
def ack(m, n) = if m == 0 then n + 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
54 |
else if n == 0 then ack(m - 1, 1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
else ack(m - 1, ack(m, n - 1));
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
56 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
def gcd(a, b) = if b == 0 then a else gcd(b, a % b);
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
58 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
59 |
|
693
|
60 |
\noindent Compare the code of the fib-program with the same program
|
711
|
61 |
written in the WHILE-language\ldots Fun is definitely more comfortable.
|
693
|
62 |
We will still focus on programs involving integers only, that means for
|
|
63 |
example that every function in Fun is expected to return an integer. The
|
|
64 |
point of the Fun language is to compile each function to a separate
|
|
65 |
method in JVM bytecode (not just a big monolithic code chunk). The means
|
|
66 |
we need to adapt to some of the conventions of the JVM about methods.
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
The grammar of the Fun-language is slightly simpler than the
|
711
|
69 |
WHILE-language, because the main syntactic category are
|
699
|
70 |
expressions (we do not have statements in Fun). The grammar rules are
|
|
71 |
as follows:\footnote{We of course have a slightly different (non-left-recursive)
|
|
72 |
grammar for our parsing combinators. But for simplicity sake we leave
|
|
73 |
these details to the implementation.}
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
74 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
75 |
|
379
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
76 |
\begin{plstx}[rhs style=,margin=1.5cm]
|
600
|
77 |
: \meta{Exp} ::= \meta{Id} | \meta{Num} {\hspace{3.7cm}}
|
|
78 |
| \meta{Exp} + \meta{Exp} | ... | (\meta{Exp}) {\hspace{3.7cm}}
|
693
|
79 |
| \code{if} \; \meta{BExp} \; \code{then} \; \meta{Exp} \; \code{else} \; \meta{Exp}
|
379
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
80 |
| \code{write} \meta{Exp} {\hspace{5cm}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
81 |
| \meta{Exp} ; \meta{Exp} {\hspace{5cm}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
| \textit{FunName} (\meta{Exp}, ..., \meta{Exp})\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
: \meta{BExp} ::= ...\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
: \meta{Decl} ::= \meta{Def} ; \meta{Decl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
| \meta{Exp}\\
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
86 |
: \meta{Def} ::= \code{def} \textit{FunName} ($x_1$, ..., $x_n$) = \meta{Exp}\\
|
379
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
87 |
\end{plstx}
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
88 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
\noindent where, as usual, \meta{Id} stands for variables and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
\meta{Num} for numbers. We can call a function by applying the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
91 |
arguments to a function name (as shown in the last clause of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
\meta{Exp}). The arguments in such a function call can be
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
again expressions, including other function calls. In
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
contrast, when defining a function (see \meta{Def}-clause) the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
arguments need to be variables, say $x_1$ to $x_n$. We call
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
the expression on the right of = in a function definition as
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
the \emph{body of the function}. We have the restriction that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
98 |
the variables inside a function body can only be those that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
99 |
are mentioned as arguments of the function. A Fun-program is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
then a sequence of function definitions separated by
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
semicolons, and a final ``main'' call of a function that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
starts the computation in the program. For example
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
103 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
104 |
\begin{lstlisting}[numbers=none]
|
699
|
105 |
def fact(n) = if n == 0 then 1
|
|
106 |
else n * fact(n - 1);
|
|
107 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
108 |
write(fact(5))
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
109 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
110 |
|
699
|
111 |
\noindent is a valid Fun-program. The parser of the
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
112 |
Fun-language produces abstract syntax trees which in Scala
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
can be represented as follows:
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
114 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
115 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
116 |
{\small
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
117 |
\begin{lstlisting}[numbers=none]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
118 |
abstract class Exp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
119 |
abstract class BExp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
120 |
abstract class Decl
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
121 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
122 |
case class Var(s: String) extends Exp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
123 |
case class Num(i: Int) extends Exp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
124 |
case class Aop(o: String, a1: Exp, a2: Exp) extends Exp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
125 |
case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
126 |
case class Write(e: Exp) extends Exp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
127 |
case class Sequ(e1: Exp, e2: Exp) extends Exp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
128 |
case class Call(name: String, args: List[Exp]) extends Exp
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
129 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
130 |
case class Bop(o: String, a1: Exp, a2: Exp) extends BExp
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
131 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
132 |
case class Def(name: String,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
args: List[String],
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
134 |
body: Exp) extends Decl
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
135 |
case class Main(e: Exp) extends Decl
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
136 |
\end{lstlisting}}
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
137 |
|
711
|
138 |
The rest of the hand out is about compiling this language. Let us first
|
|
139 |
look at some clauses for compiling expressions. The compilation of
|
|
140 |
arithmetic and boolean expressions is just like for the WHILE-language
|
|
141 |
and does not need any modification (recall that the
|
693
|
142 |
\textit{compile}-function for boolean expressions takes a third argument
|
|
143 |
for the label where the control-flow should jump when the boolean
|
|
144 |
expression is \emph{not} true---this is needed for compiling
|
|
145 |
\pcode{if}s). One additional feature in the Fun-language are sequences.
|
|
146 |
Their purpose is to do one calculation after another or printing out an
|
|
147 |
intermediate result. The reason why we need to be careful however is the
|
711
|
148 |
convention that every expression can only produce a single result
|
693
|
149 |
(including sequences). Since this result will be on the top of the
|
|
150 |
stack, we need to generate a \pcode{pop}-instruction for sequences in
|
|
151 |
order to clean-up the stack. For example, for an expression of the form
|
|
152 |
\pcode{exp1 ; exp2} we need to generate code where after the first code
|
|
153 |
chunk a \pcode{pop}-instruction is needed.
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
154 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
155 |
\begin{lstlisting}[language=JVMIS, numbers=none,mathescape]
|
383
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
156 |
$\textrm{\textit{compile}}($exp1$)$
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
157 |
pop
|
383
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
158 |
$\textrm{\textit{compile}}($exp2$)$
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
159 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
160 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
161 |
\noindent In effect we ``forget'' about the result the first
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
162 |
expression calculates. I leave you to think about why this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
163 |
sequence operator is still useful in the Fun-language, even
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
164 |
if the first result is just ``discarded''.
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
165 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
166 |
There is also one small modification we have to perform when
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
167 |
calling the write method. Remember in the Fun-language we have
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
168 |
the convention that every expression needs to return an
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
169 |
integer as a result (located on the top of the stack). Our
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
170 |
helper function implementing write, however, ``consumes'' the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
171 |
top element of the stack and violates this convention.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
172 |
Therefore before we call, say, \pcode{write(1+2)}, we need to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
173 |
duplicate the top element of the stack like so
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
174 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
175 |
\begin{figure}[t]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
176 |
\begin{lstlisting}[language=JVMIS,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
177 |
xleftmargin=2mm,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
178 |
numbers=none]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
179 |
.method public static write(I)V
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
180 |
.limit locals 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
181 |
.limit stack 2
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
182 |
getstatic java/lang/System/out Ljava/io/PrintStream;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
183 |
iload 0
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
184 |
invokevirtual java/io/PrintStream/println(I)V
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
185 |
return
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
186 |
.end method
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
187 |
\end{lstlisting}
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
188 |
\caption{The helper function for printing out integers.\label{write}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
189 |
\end{figure}
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
190 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
191 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
192 |
\begin{lstlisting}[language=JVMIS, numbers=none,mathescape]
|
383
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
193 |
$\textrm{\textit{compile}}($1+2$)$
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
194 |
dup
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
195 |
invokestatic XXX/XXX/write(I)V
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
196 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
197 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
198 |
\noindent We also need to first generate code for the
|
711
|
199 |
argument-expression of write, which in the WHILE-language was
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
200 |
only allowed to be a single variable.
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
201 |
|
603
|
202 |
Most of the new code in the compiler for the Fun-language
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
203 |
comes from function definitions and function calls. For this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
204 |
have a look again at the helper function in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
205 |
Figure~\ref{write}. Assuming we have a function definition
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
206 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
207 |
\begin{lstlisting}[numbers=none,mathescape]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
208 |
def fname (x1, ... , xn) = ...
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
209 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
210 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
211 |
\noindent then we have to generate
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
212 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
213 |
\begin{lstlisting}[numbers=none,mathescape,language=JVMIS]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
214 |
.method public static fname (I...I)I
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
215 |
.limit locals ??
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
216 |
.limit stack ??
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
217 |
...
|
699
|
218 |
ireturn
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
219 |
.method end
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
220 |
\end{lstlisting}
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
221 |
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
222 |
\noindent where the number of \pcode{I}s corresponds to the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
223 |
number of arguments the function has, say \pcode{x1} to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
224 |
\pcode{xn}. The final \pcode{I} is needed in order to indicate
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
225 |
that the function returns an integer. Therefore we also have
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
226 |
to use \pcode{ireturn} instead of \pcode{return}. However,
|
381
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
227 |
more interesting are the two \pcode{.limit} lines.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
228 |
\pcode{Locals} refers to the local variables of the method,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
229 |
which can be queried and overwritten using the JVM
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
230 |
instructions \pcode{iload} and \pcode{istore}, respectively.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
231 |
Before we call a function with, say, three arguments, we need
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
232 |
to ensure that these three arguments are pushed onto the stack
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
233 |
(we will come to the corresponding code shortly). Once we are
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
234 |
inside the method, the arguments on the stack turn into local
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
235 |
variables. So in case we have three arguments on the stack, we
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
236 |
will have inside the function three local variables that can
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
237 |
be referenced by the indices $0..2$. Determining the limit for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
238 |
local variables is the easy bit. Harder is the stack limit.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
239 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
240 |
Calculating how much stack a program needs is equivalent to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
241 |
the Halting problem, and thus undecidable in general.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
242 |
Fortunately, we are only asked how much stack a \emph{single}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
243 |
call of the function requires. This can be relatively easily
|
604
|
244 |
compiled by recursively analysing which instructions we
|
381
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
245 |
generate and how much stack they might require.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
246 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
247 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
248 |
\begin{tabular}{lcl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
249 |
$\textit{estimate}(n)$ & $\dn$ & $1$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
250 |
$\textit{estimate}(x)$ & $\dn$ & $1$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
251 |
$\textit{estimate}(a_1\;aop\;a_2)$ & $\dn$ &
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
252 |
$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
253 |
$\textit{estimate}(\pcode{if}\;b\;\pcode{then}\;e_1\;\pcode{else}\;e_2)$ & $\dn$ &
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
254 |
$\textit{estimate}(b) +$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
255 |
& & $\quad max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
256 |
$\textit{estimate}(\pcode{write}(e))$ & $\dn$ &
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
257 |
$\textit{estimate}(e) + 1$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
258 |
$\textit{estimate}(e_1 ; e_2)$ & $\dn$ &
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
259 |
$max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
260 |
$\textit{estimate}(f(e_1, ..., e_n))$ & $\dn$ &
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
261 |
$\sum_{i = 1..n}\;estimate(e_i)$\medskip\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
262 |
$\textit{estimate}(a_1\;bop\;a_2)$ & $\dn$ &
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
263 |
$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
264 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
265 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
266 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
267 |
\noindent This function overestimates the stack size, for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
268 |
example, in the case of \pcode{if}s. Since we cannot predict
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
269 |
which branch will be run, we have to allocate the maximum
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
270 |
of stack each branch might take. I leave you also to think
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
271 |
about whether the estimate in case of function calls is the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
272 |
best possible estimate. Note also that in case of \pcode{write}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
273 |
we need to add one, because we duplicate the top-most element
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
274 |
in the stack.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
275 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
276 |
With this all in place, we can start generating code, for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
277 |
example, for the two functions:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
278 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
279 |
\begin{lstlisting}[numbers=none]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
280 |
def suc(x) = x + 1;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
281 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
282 |
def add(x, y) = if x == 0 then y
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
283 |
else suc(add(x - 1, y));
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
284 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
285 |
|
603
|
286 |
\noindent The successor function is a simple loading of the
|
381
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
287 |
argument $x$ (index $0$) onto the stack, as well as the number
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
288 |
$1$. Then we add both elements leaving the result of the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
289 |
addition on top of the stack. This value will be returned by
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
290 |
the \pcode{suc}-function. See below:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
291 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
292 |
\begin{lstlisting}[language=JVMIS]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
293 |
.method public static suc(I)I
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
294 |
.limit locals 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
295 |
.limit stack 2
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
296 |
iload 0
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
297 |
ldc 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
298 |
iadd
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
299 |
ireturn
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
300 |
.end method
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
301 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
302 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
303 |
\noindent The addition function is a bit more interesting
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
304 |
since in the last line we have to call the function
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
305 |
recursively and ``wrap around'' a call to the successor
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
306 |
function. The code is as follows:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
307 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
308 |
\begin{lstlisting}[language=JVMIS]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
309 |
.method public static add(II)I
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
310 |
.limit locals 2
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
311 |
.limit stack 5
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
312 |
iload 0
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
313 |
ldc 0
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
314 |
if_icmpne If_else
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
315 |
iload 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
316 |
goto If_end
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
317 |
If_else:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
318 |
iload 0
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
319 |
ldc 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
320 |
isub
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
321 |
iload 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
322 |
invokestatic XXX/XXX/add(II)I
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
323 |
invokestatic XXX/XXX/suc(I)I
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
324 |
If_end:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
325 |
ireturn
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
326 |
.end method
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
327 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
328 |
|
382
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
329 |
\noindent The locals limit is 2 because add takes two arguments.
|
381
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
330 |
The stack limit is a simple calculation using the estimate
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
331 |
function. We first generate code for the boolean expression
|
382
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
332 |
\pcode{x == 0}, that is loading the local variable 0 and the
|
381
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
333 |
number 0 onto the stack (Lines 4 and 5). If the not-equality
|
382
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
334 |
test fails, we continue with returning $y$, which is the local
|
381
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
335 |
variable 1 (followed by a jump to the return instruction). If
|
382
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
336 |
the not-equality test succeeds, then we jump to the label
|
381
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
337 |
\pcode{If_else} (Line 9). After that label is the code for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
338 |
\pcode{suc(add(x - 1, y))}. We first have to evaluate the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
339 |
argument of the suc-function. But this means we first have to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
340 |
evaluate the two arguments of the add-function. This means
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
341 |
loading $x$ and $1$ onto the stack and subtracting them.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
342 |
Then loading $y$ onto the stack. We can then make a recursive
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
343 |
call to add (its two arguments are on the stack). When this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
344 |
call returns we have the result of the addition on the top of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
345 |
the stack and just need to call suc. Finally, we can return
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
346 |
the result on top of the stack as the result of the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
347 |
add-function.
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
348 |
|
693
|
349 |
\subsection*{Tail-Call Optimisations}
|
|
350 |
|
711
|
351 |
Let us now briefly touch again upon the vast topic of compiler
|
|
352 |
optimisations. As an example, let's perform tail-call optimisations for
|
|
353 |
our Fun-language. Consider the following version of the factorial
|
|
354 |
function:
|
693
|
355 |
|
|
356 |
\begin{lstlisting}
|
|
357 |
def facT(n, acc) =
|
|
358 |
if n == 0 then acc
|
|
359 |
else facT(n - 1, n * acc);
|
|
360 |
\end{lstlisting}
|
|
361 |
|
|
362 |
\noindent
|
711
|
363 |
The corresponding JVM code for this function is below:
|
693
|
364 |
|
|
365 |
\begin{lstlisting}[language=JVMIS, numbers=left]
|
|
366 |
.method public static facT(II)I
|
|
367 |
.limit locals 2
|
|
368 |
.limit stack 6
|
|
369 |
iload 0
|
|
370 |
ldc 0
|
|
371 |
if_icmpne If_else_2
|
|
372 |
iload 1
|
|
373 |
goto If_end_3
|
|
374 |
If_else_2:
|
|
375 |
iload 0
|
|
376 |
ldc 1
|
|
377 |
isub
|
|
378 |
iload 0
|
|
379 |
iload 1
|
|
380 |
imul
|
|
381 |
invokestatic fact/fact/facT(II)I
|
|
382 |
If_end_3:
|
|
383 |
ireturn
|
|
384 |
.end method
|
|
385 |
\end{lstlisting}
|
|
386 |
|
|
387 |
\noindent
|
|
388 |
The interesting part is in Lines 10 to 16. Since the \code{facT}
|
|
389 |
function is recursive, we have also a recursive call in Line 16 in the
|
|
390 |
JVM code. The problem is that before we can make the recursive call, we
|
|
391 |
need to put the two arguments, namely \code{n - 1} and \code{n * acc},
|
|
392 |
onto the stack. That is how we communicate arguments to a function. To
|
|
393 |
see the the difficulty, imagine you call this function 1000 times
|
|
394 |
recursively. Each call results in some hefty overhead on the
|
|
395 |
stack---ultimately leading to a stack overflow. Well, it is possible to
|
|
396 |
avoid this overhead completely in many circumstances. This is what
|
711
|
397 |
\emph{tail-call optimisations} are about.
|
693
|
398 |
|
|
399 |
Note that the call to \code{facT} in the program is the last instruction
|
|
400 |
before the \code{ireturn} (the label in Line 17 does not count since it
|
|
401 |
is not an instruction). Also remember, before we make the recursive call
|
711
|
402 |
the arguments of \code{facT} need to be put on the stack. Once we are
|
|
403 |
``inside'' the function, the arguments on the stack turn into local
|
|
404 |
variables. Therefore
|
693
|
405 |
\code{n} and \code{acc} are referenced inside the function with \pcode{iload 0}
|
|
406 |
and \pcode{iload 1} respectively.
|
|
407 |
|
699
|
408 |
The idea of tail-call optimisation is to eliminate the expensive
|
|
409 |
recursive functions call and replace it by a simple jump back to the
|
|
410 |
beginning of the function. To make this work we have to change how we
|
|
411 |
communicate the arguments to the next level of the recursion/iteration:
|
|
412 |
we cannot use the stack, but have to load the arguments into the
|
|
413 |
corresponding local variables. This gives the following code
|
693
|
414 |
|
|
415 |
\begin{lstlisting}[language=JVMIS, numbers=left, escapeinside={(*@}{@*)}]
|
|
416 |
.method public static facT(II)I
|
|
417 |
.limit locals 2
|
|
418 |
.limit stack 6
|
|
419 |
(*@\hm{facT\_Start:} @*)
|
|
420 |
iload 0
|
|
421 |
ldc 0
|
|
422 |
if_icmpne If_else_2
|
|
423 |
iload 1
|
|
424 |
goto If_end_3
|
|
425 |
If_else_2:
|
|
426 |
iload 0
|
|
427 |
ldc 1
|
|
428 |
isub
|
|
429 |
iload 0
|
|
430 |
iload 1
|
|
431 |
imul
|
|
432 |
(*@\hm{istore 1} @*)
|
|
433 |
(*@\hm{istore 0} @*)
|
|
434 |
(*@\hm{goto facT\_Start} @*)
|
|
435 |
If_end_3:
|
|
436 |
ireturn
|
|
437 |
.end method
|
|
438 |
\end{lstlisting}
|
|
439 |
|
|
440 |
\noindent
|
|
441 |
In Line 4 we introduce a label for indicating where the start of the
|
|
442 |
function is. Important are Lines 17 and 18 where we store the values
|
699
|
443 |
from the stack into local variables. When we then jump back to the
|
|
444 |
beginning of the function (in Line 19) it will look to the function as
|
|
445 |
if it had been called the normal way via values on the stack. But
|
|
446 |
because of the jump, clearly, no memory on the stack is needed. In
|
|
447 |
effect we replaced a recursive call with a simple loop.
|
693
|
448 |
|
|
449 |
Can this optimisation always be applied? Unfortunately not. The
|
|
450 |
recursive call needs to be in tail-call position, that is the last
|
|
451 |
operation needs to be the recursive call. This is for example
|
|
452 |
not the case with the usual formulation of the factorial function.
|
|
453 |
Consider again the Fun-program
|
|
454 |
|
|
455 |
\begin{lstlisting}[numbers=none]
|
|
456 |
def fact(n) = if n == 0 then 1
|
|
457 |
else n * fact(n - 1)
|
|
458 |
\end{lstlisting}
|
|
459 |
|
|
460 |
\noindent
|
|
461 |
In this version of the factorial function the recursive call is
|
|
462 |
\emph{not} the last operation (which can also been seen very clearly
|
|
463 |
in the generated JVM code). Because of this, the plumbing of local
|
|
464 |
variables would not work and in effect the optimisation is not applicable.
|
|
465 |
Very roughly speaking the tail-position of a function is in the two
|
|
466 |
highlighted places
|
|
467 |
|
|
468 |
\begin{itemize}
|
|
469 |
\item \texttt{if Bexp then \hm{Exp} else \hm{Exp}}
|
|
470 |
\item \texttt{Exp ; \hm{Exp}}
|
|
471 |
\end{itemize}
|
|
472 |
|
|
473 |
To sum up, the compiler needs to recognise when a recursive call
|
|
474 |
is in tail-position. It then can apply the tail-call optimisations
|
|
475 |
technique, which is well known and widely implemented in compilers
|
|
476 |
for functional programming languages.
|
|
477 |
|
|
478 |
|
378
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
479 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
480 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
481 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
482 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
483 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
484 |
%%% End:
|