% !TEX program = xelatex\documentclass{article}\usepackage{../style}\usepackage{../langs}\usepackage{../grammar}\usepackage{../graphics}\usepackage{amssymb}\usepackage{xcolor}\usepackage[most]{tcolorbox}\newtcbox{\hm}[1][]{% size=fbox, tcbox raise base, nobeforeafter, enhanced, colframe=gray, colback=gray!30, boxrule=1pt, fontupper=\ttfamily, #1}% modern compilers are different% https://channel9.msdn.com/Blogs/Seth-Juarez/Anders-Hejlsberg-on-Modern-Compiler-Construction%halting problem%https://dfilaretti.github.io/2017-04-30/halting-problem\begin{document}\lstset{morekeywords={def,if,then,else,write,read},keywordstyle=\color{codepurple}\bfseries}\section*{Handout 8 (A Functional Language)}The language we looked at in the previous lecture was ratherprimitive and the compiler rather crude---everything wasessentially compiled into a big monolithic chunk of codeinside the main function. In this handout we like to have alook at a slightly more comfortable language, which I callFun-language, and a tiny-teeny bit more realistic compiler.The Fun-language is a small functional programming language. A smallcollection of programs we want to be able to write and compileis as follows:\begin{lstlisting}[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}\noindent Compare the code of the fib-program with the same programwritten in the WHILE-language\ldots Fun is definitely more comfortable.We will still focus on programs involving integers only, that means forexample that every function in Fun is expected to return an integer. Thepoint of the Fun language is to compile each function to a separatemethod in JVM bytecode (not just a big monolithic code chunk). The meanswe need to adapt to some of the conventions of the JVM about methods.The grammar of the Fun-language is slightly simpler than theWHILE-language, because the main syntactic category areexpressions (we do not have statements in Fun). The grammar rules areas follows:\footnote{We of course have a slightly different (non-left-recursive)grammar for our parsing combinators. But for simplicity sake we leavethese details to the implementation.}\begin{plstx}[rhs style=,margin=1.5cm]: \meta{Exp} ::= \meta{Id} | \meta{Num} {\hspace{3.7cm}} | \meta{Exp} + \meta{Exp} | ... | (\meta{Exp}) {\hspace{3.7cm}} | \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_n$) = \meta{Exp}\\ \end{plstx}\noindent where, as usual, \meta{Id} stands for variables and\meta{Num} for numbers. We can call a function by applying thearguments to a function name (as shown in the last clause of\meta{Exp}). The arguments in such a function call can beagain expressions, including other function calls. Incontrast, when defining a function (see \meta{Def}-clause) thearguments need to be variables, say $x_1$ to $x_n$. We callthe expression on the right of = in a function definition asthe \emph{body of the function}. We have the restriction thatthe variables inside a function body can only be those thatare mentioned as arguments of the function. A Fun-program isthen a sequence of function definitions separated bysemicolons, and a final ``main'' call of a function thatstarts the computation in the program. For example\begin{lstlisting}[numbers=none]def fact(n) = if n == 0 then 1 else n * fact(n - 1);write(fact(5))\end{lstlisting}\noindent is a valid Fun-program. The parser of theFun-language produces abstract syntax trees which in Scalacan be represented as follows:{\small\begin{lstlisting}[numbers=none]abstract class Expabstract class BExp abstract class Declcase class Var(s: String) extends Expcase class Num(i: Int) extends Expcase class Aop(o: String, a1: Exp, a2: Exp) extends Expcase class If(a: BExp, e1: Exp, e2: Exp) extends Expcase class Write(e: Exp) extends Expcase class Sequ(e1: Exp, e2: Exp) extends Expcase class Call(name: String, args: List[Exp]) extends Expcase class Bop(o: String, a1: Exp, a2: Exp) extends BExpcase class Def(name: String, args: List[String], body: Exp) extends Declcase class Main(e: Exp) extends Decl\end{lstlisting}}The rest of the hand out is about compiling this language. Let us firstlook at some clauses for compiling expressions. The compilation ofarithmetic and boolean expressions is just like for the WHILE-languageand does not need any modification (recall that the\textit{compile}-function for boolean expressions takes a third argumentfor the label where the control-flow should jump when the booleanexpression is \emph{not} true---this is needed for compiling\pcode{if}s). One additional feature in the Fun-language are sequences.Their purpose is to do one calculation after another or printing out anintermediate result. The reason why we need to be careful however is theconvention that every expression can only produce a single result(including sequences). Since this result will be on the top of thestack, we need to generate a \pcode{pop}-instruction for sequences inorder to clean-up the stack. For example, for an expression of the form\pcode{exp1 ; exp2} we need to generate code where after the first codechunk a \pcode{pop}-instruction is needed. \begin{lstlisting}[language=JVMIS, numbers=none,mathescape]$\textrm{\textit{compile}}($exp1$)$pop$\textrm{\textit{compile}}($exp2$)$\end{lstlisting}\noindent In effect we ``forget'' about the result the firstexpression calculates. I leave you to think about why thissequence operator is still useful in the Fun-language, even if the first result is just ``discarded''. There is also one small modification we have to perform whencalling the write method. Remember in the Fun-language we havethe convention that every expression needs to return aninteger as a result (located on the top of the stack). Ourhelper function implementing write, however, ``consumes'' thetop element of the stack and violates this convention.Therefore before we call, say, \pcode{write(1+2)}, we need toduplicate the top element of the stack like so\begin{figure}[t]\begin{lstlisting}[language=JVMIS, xleftmargin=2mm, numbers=none].method public static write(I)V .limit locals 1 .limit stack 2 getstatic java/lang/System/out Ljava/io/PrintStream; iload 0 invokevirtual java/io/PrintStream/println(I)V return .end method\end{lstlisting}\caption{The helper function for printing out integers.\label{write}}\end{figure}\begin{lstlisting}[language=JVMIS, numbers=none,mathescape]$\textrm{\textit{compile}}($1+2$)$dupinvokestatic XXX/XXX/write(I)V\end{lstlisting}\noindent We also need to first generate code for theargument-expression of write, which in the WHILE-language wasonly allowed to be a single variable.Most of the new code in the compiler for the Fun-languagecomes from function definitions and function calls. For thishave a look again at the helper function inFigure~\ref{write}. Assuming we have a function definition\begin{lstlisting}[numbers=none,mathescape]def fname (x1, ... , xn) = ...\end{lstlisting}\noindent then we have to generate\begin{lstlisting}[numbers=none,mathescape,language=JVMIS].method public static fname (I...I)I .limit locals ?? .limit stack ?? ... ireturn.method end \end{lstlisting}\noindent where the number of \pcode{I}s corresponds to thenumber of arguments the function has, say \pcode{x1} to\pcode{xn}. The final \pcode{I} is needed in order to indicatethat the function returns an integer. Therefore we also haveto use \pcode{ireturn} instead of \pcode{return}. However,more interesting are the two \pcode{.limit} lines.\pcode{Locals} refers to the local variables of the method,which can be queried and overwritten using the JVMinstructions \pcode{iload} and \pcode{istore}, respectively.Before we call a function with, say, three arguments, we needto ensure that these three arguments are pushed onto the stack(we will come to the corresponding code shortly). Once we areinside the method, the arguments on the stack turn into localvariables. So in case we have three arguments on the stack, we will have inside the function three local variables that can be referenced by the indices $0..2$. Determining the limit forlocal variables is the easy bit. Harder is the stack limit.Calculating how much stack a program needs is equivalent to the Halting problem, and thus undecidable in general. Fortunately, we are only asked how much stack a \emph{single} call of the function requires. This can be relatively easilycompiled by recursively analysing which instructions we generate and how much stack they might require.\begin{center}\begin{tabular}{lcl}$\textit{estimate}(n)$ & $\dn$ & $1$\\$\textit{estimate}(x)$ & $\dn$ & $1$\\$\textit{estimate}(a_1\;aop\;a_2)$ & $\dn$ &$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\$\textit{estimate}(\pcode{if}\;b\;\pcode{then}\;e_1\;\pcode{else}\;e_2)$ & $\dn$ & $\textit{estimate}(b) +$\\ & & $\quad max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\$\textit{estimate}(\pcode{write}(e))$ & $\dn$ & $\textit{estimate}(e) + 1$\\$\textit{estimate}(e_1 ; e_2)$ & $\dn$ & $max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\$\textit{estimate}(f(e_1, ..., e_n))$ & $\dn$ & $\sum_{i = 1..n}\;estimate(e_i)$\medskip\\$\textit{estimate}(a_1\;bop\;a_2)$ & $\dn$ &$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\\end{tabular}\end{center} \noindent This function overestimates the stack size, forexample, in the case of \pcode{if}s. Since we cannot predictwhich branch will be run, we have to allocate the maximum of stack each branch might take. I leave you also to think about whether the estimate in case of function calls is the best possible estimate. Note also that in case of \pcode{write}we need to add one, because we duplicate the top-most elementin the stack.With this all in place, we can start generating code, forexample, for the two functions:\begin{lstlisting}[numbers=none]def suc(x) = x + 1;def add(x, y) = if x == 0 then y else suc(add(x - 1, y));\end{lstlisting}\noindent The successor function is a simple loading of theargument $x$ (index $0$) onto the stack, as well as the number$1$. Then we add both elements leaving the result of the addition on top of the stack. This value will be returned by the \pcode{suc}-function. See below:\begin{lstlisting}[language=JVMIS].method public static suc(I)I .limit locals 1.limit stack 2 iload 0 ldc 1 iadd ireturn.end method \end{lstlisting}\noindent The addition function is a bit more interestingsince in the last line we have to call the functionrecursively and ``wrap around'' a call to the successorfunction. The code is as follows:\begin{lstlisting}[language=JVMIS].method public static add(II)I .limit locals 2.limit stack 5 iload 0 ldc 0 if_icmpne If_else iload 1 goto If_endIf_else: iload 0 ldc 1 isub iload 1 invokestatic XXX/XXX/add(II)I invokestatic XXX/XXX/suc(I)IIf_end: ireturn.end method\end{lstlisting}\noindent The locals limit is 2 because add takes two arguments.The stack limit is a simple calculation using the estimatefunction. We first generate code for the boolean expression\pcode{x == 0}, that is loading the local variable 0 and thenumber 0 onto the stack (Lines 4 and 5). If the not-equalitytest fails, we continue with returning $y$, which is the localvariable 1 (followed by a jump to the return instruction). Ifthe not-equality test succeeds, then we jump to the label \pcode{If_else} (Line 9). After that label is the code for\pcode{suc(add(x - 1, y))}. We first have to evaluate theargument of the suc-function. But this means we first have toevaluate the two arguments of the add-function. This meansloading $x$ and $1$ onto the stack and subtracting them.Then loading $y$ onto the stack. We can then make a recursive call to add (its two arguments are on the stack). When thiscall returns we have the result of the addition on the top of the stack and just need to call suc. Finally, we can return the result on top of the stack as the result of the add-function.\subsection*{Tail-Call Optimisations}Let us now briefly touch again upon the vast topic of compileroptimisations. As an example, let's perform tail-call optimisations forour Fun-language. Consider the following version of the factorialfunction:\begin{lstlisting}def facT(n, acc) = if n == 0 then acc else facT(n - 1, n * acc);\end{lstlisting}\noindent The corresponding JVM code for this function is below:\begin{lstlisting}[language=JVMIS, numbers=left].method public static facT(II)I .limit locals 2.limit stack 6 iload 0 ldc 0 if_icmpne If_else_2 iload 1 goto If_end_3If_else_2: iload 0 ldc 1 isub iload 0 iload 1 imul invokestatic fact/fact/facT(II)IIf_end_3: ireturn.end method \end{lstlisting}\noindentThe interesting part is in Lines 10 to 16. Since the \code{facT}function is recursive, we have also a recursive call in Line 16 in theJVM code. The problem is that before we can make the recursive call, weneed to put the two arguments, namely \code{n - 1} and \code{n * acc},onto the stack. That is how we communicate arguments to a function. Tosee the the difficulty, imagine you call this function 1000 timesrecursively. Each call results in some hefty overhead on thestack---ultimately leading to a stack overflow. Well, it is possible toavoid this overhead completely in many circumstances. This is what\emph{tail-call optimisations} are about. Note that the call to \code{facT} in the program is the last instructionbefore the \code{ireturn} (the label in Line 17 does not count since itis not an instruction). Also remember, before we make the recursive callthe arguments of \code{facT} need to be put on the stack. Once we are``inside'' the function, the arguments on the stack turn into localvariables. Therefore \code{n} and \code{acc} are referenced inside the function with \pcode{iload 0}and \pcode{iload 1} respectively.The idea of tail-call optimisation is to eliminate the expensiverecursive functions call and replace it by a simple jump back to thebeginning of the function. To make this work we have to change how wecommunicate the arguments to the next level of the recursion/iteration:we cannot use the stack, but have to load the arguments into thecorresponding local variables. This gives the following code\begin{lstlisting}[language=JVMIS, numbers=left, escapeinside={(*@}{@*)}].method public static facT(II)I .limit locals 2.limit stack 6(*@\hm{facT\_Start:} @*) iload 0 ldc 0 if_icmpne If_else_2 iload 1 goto If_end_3If_else_2: iload 0 ldc 1 isub iload 0 iload 1 imul (*@\hm{istore 1} @*) (*@\hm{istore 0} @*) (*@\hm{goto facT\_Start} @*)If_end_3: ireturn.end method \end{lstlisting}\noindentIn Line 4 we introduce a label for indicating where the start of thefunction is. Important are Lines 17 and 18 where we store the valuesfrom the stack into local variables. When we then jump back to thebeginning of the function (in Line 19) it will look to the function asif it had been called the normal way via values on the stack. Butbecause of the jump, clearly, no memory on the stack is needed. Ineffect we replaced a recursive call with a simple loop.Can this optimisation always be applied? Unfortunately not. The recursive call needs to be in tail-call position, that is the lastoperation needs to be the recursive call. This is for examplenot the case with the usual formulation of the factorial function.Consider again the Fun-program\begin{lstlisting}[numbers=none]def fact(n) = if n == 0 then 1 else n * fact(n - 1)\end{lstlisting} \noindentIn this version of the factorial function the recursive call is\emph{not} the last operation (which can also been seen very clearlyin the generated JVM code). Because of this, the plumbing of local variables would not work and in effect the optimisation is not applicable. Very roughly speaking the tail-position of a function is in the two highlighted places\begin{itemize}\item \texttt{if Bexp then \hm{Exp} else \hm{Exp}}\item \texttt{Exp ; \hm{Exp}}\end{itemize}To sum up, the compiler needs to recognise when a recursive callis in tail-position. It then can apply the tail-call optimisationstechnique, which is well known and widely implemented in compilersfor functional programming languages.\end{document}%%% Local Variables: %%% mode: latex %%% TeX-master: t%%% End: