65 method in JVM bytecode (not just a big monolithic code chunk). The means |
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. |
66 we need to adapt to some of the conventions of the JVM about methods. |
67 |
67 |
68 The grammar of the Fun-language is slightly simpler than the |
68 The grammar of the Fun-language is slightly simpler than the |
69 While-language, because the main syntactic category are |
69 While-language, because the main syntactic category are |
70 expressions (we do not have statements). The grammar rules are |
70 expressions (we do not have statements in Fun). The grammar rules are |
71 as follows: |
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.} |
72 |
74 |
73 |
75 |
74 \begin{plstx}[rhs style=,margin=1.5cm] |
76 \begin{plstx}[rhs style=,margin=1.5cm] |
75 : \meta{Exp} ::= \meta{Id} | \meta{Num} {\hspace{3.7cm}} |
77 : \meta{Exp} ::= \meta{Id} | \meta{Num} {\hspace{3.7cm}} |
76 | \meta{Exp} + \meta{Exp} | ... | (\meta{Exp}) {\hspace{3.7cm}} |
78 | \meta{Exp} + \meta{Exp} | ... | (\meta{Exp}) {\hspace{3.7cm}} |
98 then a sequence of function definitions separated by |
100 then a sequence of function definitions separated by |
99 semicolons, and a final ``main'' call of a function that |
101 semicolons, and a final ``main'' call of a function that |
100 starts the computation in the program. For example |
102 starts the computation in the program. For example |
101 |
103 |
102 \begin{lstlisting}[numbers=none] |
104 \begin{lstlisting}[numbers=none] |
103 def fact(n) = if n == 0 then 1 else n * fact(n - 1); |
105 def fact(n) = if n == 0 then 1 |
|
106 else n * fact(n - 1); |
|
107 |
104 write(fact(5)) |
108 write(fact(5)) |
105 \end{lstlisting} |
109 \end{lstlisting} |
106 |
110 |
107 \noindent would be a valid Fun-program. The parser of the |
111 \noindent is a valid Fun-program. The parser of the |
108 Fun-language produces abstract syntax trees which in Scala |
112 Fun-language produces abstract syntax trees which in Scala |
109 can be represented as follows: |
113 can be represented as follows: |
110 |
114 |
111 |
115 |
112 {\small |
116 {\small |
208 \begin{lstlisting}[numbers=none,mathescape,language=JVMIS] |
212 \begin{lstlisting}[numbers=none,mathescape,language=JVMIS] |
209 .method public static fname (I...I)I |
213 .method public static fname (I...I)I |
210 .limit locals ?? |
214 .limit locals ?? |
211 .limit stack ?? |
215 .limit stack ?? |
212 ... |
216 ... |
213 ireturn |
217 ireturn |
214 .method end |
218 .method end |
215 \end{lstlisting} |
219 \end{lstlisting} |
216 |
220 |
217 \noindent where the number of \pcode{I}s corresponds to the |
221 \noindent where the number of \pcode{I}s corresponds to the |
218 number of arguments the function has, say \pcode{x1} to |
222 number of arguments the function has, say \pcode{x1} to |
396 the arguments of \code{facT} need to put on the stack. Once we are |
400 the arguments of \code{facT} need to put on the stack. Once we are |
397 ``inside'' the arguments on the stack turn into local variables. Therefore |
401 ``inside'' the arguments on the stack turn into local variables. Therefore |
398 \code{n} and \code{acc} are referenced inside the function with \pcode{iload 0} |
402 \code{n} and \code{acc} are referenced inside the function with \pcode{iload 0} |
399 and \pcode{iload 1} respectively. |
403 and \pcode{iload 1} respectively. |
400 |
404 |
401 The idea of tail-call optimisation is to eliminate the expensive recursive |
405 The idea of tail-call optimisation is to eliminate the expensive |
402 functions call and replace it by a simple jump back to the beginning of the |
406 recursive functions call and replace it by a simple jump back to the |
403 function. To make this work we have to change how we communicate the arguments |
407 beginning of the function. To make this work we have to change how we |
404 to the next level of ``recursion'': we cannot use the stack, but have to load |
408 communicate the arguments to the next level of the recursion/iteration: |
405 the argument into the corresponding local variables. This gives the following |
409 we cannot use the stack, but have to load the arguments into the |
406 code |
410 corresponding local variables. This gives the following code |
407 |
411 |
408 \begin{lstlisting}[language=JVMIS, numbers=left, escapeinside={(*@}{@*)}] |
412 \begin{lstlisting}[language=JVMIS, numbers=left, escapeinside={(*@}{@*)}] |
409 .method public static facT(II)I |
413 .method public static facT(II)I |
410 .limit locals 2 |
414 .limit locals 2 |
411 .limit stack 6 |
415 .limit stack 6 |
431 \end{lstlisting} |
435 \end{lstlisting} |
432 |
436 |
433 \noindent |
437 \noindent |
434 In Line 4 we introduce a label for indicating where the start of the |
438 In Line 4 we introduce a label for indicating where the start of the |
435 function is. Important are Lines 17 and 18 where we store the values |
439 function is. Important are Lines 17 and 18 where we store the values |
436 from the stack into local variables. When we then jump back to the |
440 from the stack into local variables. When we then jump back to the |
437 beginning of the function (in Line 19) it will look like to the |
441 beginning of the function (in Line 19) it will look to the function as |
438 function as if the function had been called the normal way via values |
442 if it had been called the normal way via values on the stack. But |
439 on the stack. But because of the jump, clearly, no memory on the |
443 because of the jump, clearly, no memory on the stack is needed. In |
440 stack is needed. In effect we replaced a recursive call with a simple |
444 effect we replaced a recursive call with a simple loop. |
441 loop. |
|
442 |
445 |
443 Can this optimisation always be applied? Unfortunately not. The |
446 Can this optimisation always be applied? Unfortunately not. The |
444 recursive call needs to be in tail-call position, that is the last |
447 recursive call needs to be in tail-call position, that is the last |
445 operation needs to be the recursive call. This is for example |
448 operation needs to be the recursive call. This is for example |
446 not the case with the usual formulation of the factorial function. |
449 not the case with the usual formulation of the factorial function. |