\documentclass{article}\usepackage{../style}\usepackage{../langs}\usepackage{../graphics}\begin{document}\section*{Homework 8}%%\HEADER\begin{enumerate}\item Write a program in the WHILE-language that calculates the factorial function.%\begin{lstlisting}%write "factorial: ";%read n;%minus1 := 1;%while n > 0 do {%minus1 := minus1 * n;%n := n - 1%};%write "Result: ";%write minus1 ;%write "\n"%\end{lstlisting}\item What optimisations could a compiler perform when compiling a WHILE-program? \solution{ \begin{itemize} \item peephole optimisations (more specific instructions) \item common sub-expression elimination %, for example%\begin{lstlisting}%x := 3 + a%y := 3 + a%\end{lstlisting} %can be optimised to %\begin{lstlisting}[numbers=none,language={}] % z := 3 + a % x := z % y := z %\end{lstlisting} \item constant folding / constant propagation (that is calculate the result of 3 + 4 already during compilation) \item tail-recursion optimisation cannot be applied to the WHILE language because there are no recursive functions \end{itemize} }\item What is the main difference between the Java assembler (as processed by Jasmin) and Java Byte Code? \solution{ The main difference is that the j-files have symbols for places where to jump, while class files have this resolved to concrete addresses (or relative jumps). That is what the assembler has to generate. }\item Remember symbolic labels in the Jasmin-assembler are meant to be used for jumps (like in loops or if-conditions). Assume you generated a Jasmin-file with some redundant labels, that is some labels are not used in your code for any jumps. For example \texttt{L\_begin} and \texttt{L\_end} are not used in the following code-snippet:\begin{lstlisting}[language=JVMIS,numbers=none]L_begin: ldc 1ldc 2ldc 3imulldc 4ldc 3isubiaddiaddL_end:\end{lstlisting} Do these redundant labels affect the size of the generated JVM-code? (Hint: What are the labels translated to by the Jasmin-assembler?). \solution{The answer is no. The reason is that assemblers calculate for labels either relative or explicit adresses, which are then used in the JVM-byte-code. Relative addresses are like ``jump 10 bytes forward'' or ``12 bytes backward''. So additional labels do not increase the size of the generated code.}\item Consider the following Scala snippet. Are the two functions\texttt{is\_even} and \texttt{is\_odd} tail-recursive? \begin{lstlisting}[numbers=none]def is_even(n: Int) : Boolean = { if (n == 0) true else is_odd(n - 1)}def is_odd(n: Int) : Boolean = { if (n == 0) false else if (n == 1) true else is_even(n - 1)}\end{lstlisting}Do they cause stack-overflows when compiled to the JVM (for example by Scala)?\solution{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).} \item Explain what is meant by the terms lazy evaluation and eager evaluation. \solution{ Lazy evaluation only evaluates expressions when they are needed and if they are needed twice, the results will be re-used. Eager evaluation immediately evaluates expressions, for example if they are arguments to function calls or allocated to variables.}\item \POSTSCRIPT \end{enumerate}\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: