diff -r 7c7854feccb5 -r 7dac350b20a1 handouts/ho08.tex --- a/handouts/ho08.tex Fri Nov 22 13:03:13 2019 +0000 +++ b/handouts/ho08.tex Sun Nov 24 01:03:38 2019 +0000 @@ -67,8 +67,10 @@ The grammar of the Fun-language is slightly simpler than the While-language, because the main syntactic category are -expressions (we do not have statements). The grammar rules are -as follows: +expressions (we do not have statements in Fun). The grammar rules are +as follows:\footnote{We of course have a slightly different (non-left-recursive) +grammar for our parsing combinators. But for simplicity sake we leave +these details to the implementation.} \begin{plstx}[rhs style=,margin=1.5cm] @@ -100,11 +102,13 @@ starts the computation in the program. For example \begin{lstlisting}[numbers=none] -def fact(n) = if n == 0 then 1 else n * fact(n - 1); +def fact(n) = if n == 0 then 1 + else n * fact(n - 1); + write(fact(5)) \end{lstlisting} -\noindent would be a valid Fun-program. The parser of the +\noindent is a valid Fun-program. The parser of the Fun-language produces abstract syntax trees which in Scala can be represented as follows: @@ -210,7 +214,7 @@ .limit locals ?? .limit stack ?? ... - ireturn + ireturn .method end \end{lstlisting} @@ -398,12 +402,12 @@ \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 expensive recursive -functions call and replace it by a simple jump back to the beginning of the -function. To make this work we have to change how we communicate the arguments -to the next level of ``recursion'': we cannot use the stack, but have to load -the argument into the corresponding local variables. This gives the following -code +The idea of tail-call optimisation is to eliminate the expensive +recursive functions call and replace it by a simple jump back to the +beginning of the function. To make this work we have to change how we +communicate the arguments to the next level of the recursion/iteration: +we cannot use the stack, but have to load the arguments into the +corresponding local variables. This gives the following code \begin{lstlisting}[language=JVMIS, numbers=left, escapeinside={(*@}{@*)}] .method public static facT(II)I @@ -433,12 +437,11 @@ \noindent In Line 4 we introduce a label for indicating where the start of the function is. Important are Lines 17 and 18 where we store the values -from the stack into local variables. When we then jump back to the -beginning of the function (in Line 19) it will look like to the -function as if the function had been called the normal way via values -on the stack. But because of the jump, clearly, no memory on the -stack is needed. In effect we replaced a recursive call with a simple -loop. +from the stack into local variables. When we then jump back to the +beginning of the function (in Line 19) it will look to the function as +if it had been called the normal way via values on the stack. But +because of the jump, clearly, no memory on the stack is needed. In +effect 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 last