equal
deleted
inserted
replaced
20 \section*{Handout 8 (A Functional Language)} |
20 \section*{Handout 8 (A Functional Language)} |
21 |
21 |
22 |
22 |
23 The language we looked at in the previous lecture was rather |
23 The language we looked at in the previous lecture was rather |
24 primitive and the compiler rather crude---everything was |
24 primitive and the compiler rather crude---everything was |
25 essentially estimated into a big monolithic chunk of code |
25 essentially compiled into a big monolithic chunk of code |
26 inside the main function. In this handout we like to have a |
26 inside the main function. In this handout we like to have a |
27 look at a slightly more comfortable language, which I call |
27 look at a slightly more comfortable language, which I call |
28 Fun-language, and a tiny-teeny bit more realistic compiler. |
28 Fun-language, and a tiny-teeny bit more realistic compiler. |
29 The Fun-language is a functional programming language. A small |
29 The Fun-language is a functional programming language. A small |
30 collection of programs we want to be able to write and estimate |
30 collection of programs we want to be able to write and compile |
31 is as follows: |
31 is as follows: |
32 |
32 |
33 \begin{lstlisting}[numbers=none] |
33 \begin{lstlisting}[numbers=none] |
34 def fib(n) = if n == 0 then 0 |
34 def fib(n) = if n == 0 then 0 |
35 else if n == 1 then 1 |
35 else if n == 1 then 1 |
47 \noindent Compare the code of the fib-program with the same |
47 \noindent Compare the code of the fib-program with the same |
48 program written in the While-language\ldots Fun is definitely |
48 program written in the While-language\ldots Fun is definitely |
49 more comfortable. We will still focus on programs involving |
49 more comfortable. We will still focus on programs involving |
50 integers only, that means for example that every function is |
50 integers only, that means for example that every function is |
51 expected to return an integer. The point of the Fun language |
51 expected to return an integer. The point of the Fun language |
52 is to estimate each function to a separate method in JVM |
52 is to compile each function to a separate method in JVM |
53 bytecode (not just a big monolithic code chunk). The means we |
53 bytecode (not just a big monolithic code chunk). The means we |
54 need to adapt to some of the conventions of the JVM about |
54 need to adapt to some of the conventions of the JVM about |
55 methods. |
55 methods. |
56 |
56 |
57 The grammar of the Fun-language is slightly simpler than the |
57 The grammar of the Fun-language is slightly simpler than the |
120 case class Main(e: Exp) extends Decl |
120 case class Main(e: Exp) extends Decl |
121 \end{lstlisting}} |
121 \end{lstlisting}} |
122 |
122 |
123 Let us first look at some clauses for compiling expressions. |
123 Let us first look at some clauses for compiling expressions. |
124 The compilation of arithmetic and boolean expressions is just |
124 The compilation of arithmetic and boolean expressions is just |
125 like for the While-language and do not need any modification. |
125 like for the While-language and do not need any modification |
126 (recall that the \textit{estimate}-function for boolean |
126 (recall that the \textit{compile}-function for boolean |
127 expression takes a third argument for the label where the |
127 expression takes a third argument for the label where the |
128 control-flow should jump when the boolean expression is |
128 control-flow should jump when the boolean expression is |
129 \emph{not} true---this is needed for compiling \pcode{if}s). |
129 \emph{not} true---this is needed for compiling \pcode{if}s). |
130 One additional feature in the Fun-language are sequences. |
130 One additional feature in the Fun-language are sequences. |
131 Their purpose is to do one calculation after another. The |
131 Their purpose is to do one calculation after another. The |
225 |
225 |
226 Calculating how much stack a program needs is equivalent to |
226 Calculating how much stack a program needs is equivalent to |
227 the Halting problem, and thus undecidable in general. |
227 the Halting problem, and thus undecidable in general. |
228 Fortunately, we are only asked how much stack a \emph{single} |
228 Fortunately, we are only asked how much stack a \emph{single} |
229 call of the function requires. This can be relatively easily |
229 call of the function requires. This can be relatively easily |
230 estimated by recursively analysing which instructions we |
230 compiled by recursively analysing which instructions we |
231 generate and how much stack they might require. |
231 generate and how much stack they might require. |
232 |
232 |
233 \begin{center} |
233 \begin{center} |
234 \begin{tabular}{lcl} |
234 \begin{tabular}{lcl} |
235 $\textit{estimate}(n)$ & $\dn$ & $1$\\ |
235 $\textit{estimate}(n)$ & $\dn$ & $1$\\ |