\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 1

ldc 2

ldc 3

imul

ldc 4

ldc 3

isub

iadd

iadd

L_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 The JVM method given below is code for the following recursive function

\begin{lstlisting}[numbers=none]

def add(x, y) = if x == 0 then y else add(x - 1, y + 1)

\end{lstlisting}

Rewrite the JVM code such that the recursive call at the end is removed.

\begin{lstlisting}[language=JVMIS,numbers=none]

.method public static add(II)I

.limit locals 2

.limit stack 7

  iload 0

  ldc 0

  if_icmpne If_else_4

  iload 1

  goto If_end_5

If_else_4:

  iload 0

  ldc 1

  isub

  iload 1

  ldc 1

  iadd

  invokestatic defs/defs/add(II)I  ;; recursive call

If_end_5:

  ireturn

.end method

\end{lstlisting}

\solution{

\begin{lstlisting}[language=JVMIS,numbers=none]

.method public static add(II)I

.limit locals 2

.limit stack 7

add2_Start:

  iload 0

  ldc 0

  if_icmpne If_else_4

  iload 1

  goto If_end_5

If_else_4:

  iload 0

  ldc 1

  isub

  iload 1

  ldc 1

  iadd 

  istore 1

  istore 0

  goto add2_Start

If_end_5:

  ireturn

.end method

\end{lstlisting}

}

\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: