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