9 |
9 |
10 %%\HEADER |
10 %%\HEADER |
11 |
11 |
12 \begin{enumerate} |
12 \begin{enumerate} |
13 \item Write a program in the WHILE-language that calculates |
13 \item Write a program in the WHILE-language that calculates |
14 the factorial function. |
14 the factorial function. |
|
15 |
|
16 \begin{lstlisting} |
|
17 write "factorial: "; |
|
18 read n; |
|
19 minus1 := 1; |
|
20 while n > 0 do { |
|
21 minus1 := minus1 * n; |
|
22 n := n - 1 |
|
23 }; |
|
24 write "Result: "; |
|
25 write minus1 ; |
|
26 write "\n" |
|
27 \end{lstlisting} |
15 |
28 |
16 \item What optimisations could a compiler perform when |
29 \item What optimisations could a compiler perform when |
17 compiling a WHILE-program? |
30 compiling a WHILE-program? |
|
31 |
|
32 \solution{ |
|
33 \begin{itemize} |
|
34 \item peephole optimisations (more specific instructions) |
|
35 \item common sub-expression elimination %, for example |
|
36 |
|
37 %\begin{lstlisting} |
|
38 %x := 3 + a |
|
39 %y := 3 + a |
|
40 %\end{lstlisting} |
|
41 |
|
42 %can be optimised to |
|
43 |
|
44 %\begin{lstlisting}[numbers=none,language={}] |
|
45 % z := 3 + a |
|
46 % x := z |
|
47 % y := z |
|
48 %\end{lstlisting} |
|
49 |
|
50 \item constant folding / constant propagation (that is calculate the result of 3 + 4 already during |
|
51 compilation) |
|
52 \item tail-recursion optimisation cannot be applied to the WHILE language |
|
53 because there are no recursive functions |
|
54 \end{itemize} |
|
55 } |
18 |
56 |
19 \item What is the main difference between the Java assembler |
57 \item What is the main difference between the Java assembler |
20 (as processed by Jasmin) and Java Byte Code? |
58 (as processed by Jasmin) and Java Byte Code? |
21 |
59 |
|
60 \solution{ The main difference is that the j-files have symbols |
|
61 for places where to jump, while class files have this resolved |
|
62 to concrete addresses (or relative jumps). That is what the |
|
63 assembler has to generate. } |
|
64 |
22 \item Remember symbolic labels in the Jasmin-assembler are meant to |
65 \item Remember symbolic labels in the Jasmin-assembler are meant to |
23 be used for jumps (like in loops or if-conditions). Assume |
66 be used for jumps (like in loops or if-conditions). Assume |
24 you generated a Jasmin-file with some redundant |
67 you generated a Jasmin-file with some redundant |
25 labels, that is some labels are not used in your code for any jumps. For |
68 labels, that is some labels are not used in your code for any jumps. For |
26 example \texttt{L\_begin} and \texttt{L\_end} are not used |
69 example \texttt{L\_begin} and \texttt{L\_end} are not used |
27 in the fol,lowing code-snippet: |
70 in the following code-snippet: |
28 |
71 |
29 \begin{lstlisting}[language=JVMIS,numbers=none] |
72 \begin{lstlisting}[language=JVMIS,numbers=none] |
30 L_begin: |
73 L_begin: |
31 ldc 1 |
74 ldc 1 |
32 ldc 2 |
75 ldc 2 |
40 L_end: |
83 L_end: |
41 \end{lstlisting} |
84 \end{lstlisting} |
42 |
85 |
43 Do these redundant labels affect the size of the generated |
86 Do these redundant labels affect the size of the generated |
44 JVM-code? (Hint: What are the labels translated to by |
87 JVM-code? (Hint: What are the labels translated to by |
45 the Jasmin-assembler?). |
88 the Jasmin-assembler?). |
46 |
89 |
47 \solution{The answer is no. The reason is that assemblers |
90 \solution{The answer is no. The reason is that assemblers |
48 calculate for labels either relative or explicit adresses, |
91 calculate for labels either relative or explicit adresses, |
49 which are then used in the JVM-byte-code. Relative addresses |
92 which are then used in the JVM-byte-code. Relative addresses |
50 are like ``jump 10 bytes forward'' or ``12 bytes backward''. So |
93 are like ``jump 10 bytes forward'' or ``12 bytes backward''. So |
65 } |
108 } |
66 \end{lstlisting} |
109 \end{lstlisting} |
67 |
110 |
68 Do they cause stack-overflows when compiled to the JVM (for example by Scala)? |
111 Do they cause stack-overflows when compiled to the JVM (for example by Scala)? |
69 |
112 |
|
113 \solution{ |
|
114 Scala cannot generate jumps in between different methods (to which functions are compiled to). So cannot eliminate the tail-calls. Haskell for example can do this because it compiles the code in a big ``blob'' inside a main-method (similar to the WHILE language). |
|
115 } |
|
116 |
70 |
117 |
71 \item Explain what is meant by the terms lazy evaluation and eager |
118 \item Explain what is meant by the terms lazy evaluation and eager |
72 evaluation. |
119 evaluation. |
|
120 |
|
121 \solution{ Lazy evaluation only evaluates expressions when they are |
|
122 needed and if they are needed twice, the results will be |
|
123 re-used. Eager evaluation immediately evaluates expressions, for |
|
124 example if they are arguments to function calls or allocated to |
|
125 variables.} |
|
126 |
73 |
127 |
74 \item \POSTSCRIPT |
128 \item \POSTSCRIPT |
75 \end{enumerate} |
129 \end{enumerate} |
76 |
130 |
77 \end{document} |
131 \end{document} |