\documentclass{article}
\usepackage{charter}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{listings}
\usepackage{xcolor}


\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%
\begin{document}

\definecolor{javared}{rgb}{0.6,0,0} % for strings
\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc
  
\lstdefinelanguage{scala}{
  morekeywords={abstract,case,catch,class,def,%
    do,else,extends,false,final,finally,%
    for,if,implicit,import,match,mixin,%
    new,null,object,override,package,%
    private,protected,requires,return,sealed,%
    super,this,throw,trait,true,try,
    type,val,var,while,with,yield},
  otherkeywords={=>,<-,<\%,<:,>:,\#,@},
  sensitive=true,
  morecomment=[l]{//},
  morecomment=[n]{/*}{*/},
  morestring=[b]",
  morestring=[b]',
  morestring=[b]"""
}

\lstdefinelanguage{while}{
  morekeywords={while, if, then. else, read, write, for, upto, do},
  otherkeywords={=>,<-,<\%,<:,>:,\#,@},
  sensitive=true,
  morecomment=[l]{//},
  morecomment=[n]{/*}{*/},
  morestring=[b]",
  morestring=[b]',
  morestring=[b]"""
}


\lstset{language=Scala,
	basicstyle=\ttfamily,
	keywordstyle=\color{javapurple}\bfseries,
	stringstyle=\color{javagreen},
	commentstyle=\color{javagreen},
	morecomment=[s][\color{javadocblue}]{/**}{*/},
	numbers=left,
	numberstyle=\tiny\color{black},
	stepnumber=1,
	numbersep=10pt,
	tabsize=2,
	showspaces=false,
	showstringspaces=false}



\section*{Coursework 3}

\noindent
This coursework is worth 4\% and is due on 13 December at 16:00. You are asked to 
implement a compiler for the WHILE language that targets the
assembler language provided by Jasmin. This assembler 
is available from

\begin{center}
\url{http://jasmin.sourceforge.net}
\end{center}

\noindent
There is a user guide for Jasmin

\begin{center}
\url{http://jasmin.sourceforge.net/guide.html}
\end{center}

\noindent
and also a description of some of the instructions that the JVM understands

\begin{center}
\url{http://jasmin.sourceforge.net/instructions.html}
\end{center}

\noindent
If you generated a correct assembler file for Jasmin, for example
\texttt{loops.j}, you can use

\begin{center}
\texttt{java -jar jasmin-2.4/jasmin.jar loops.j}
\end{center}

\noindent
in order to translate it to Java byte code. The resulting class file can be
run with

\begin{center}
\texttt{java loops}
\end{center}

\noindent
where you might need to give the correct path to the class file.\bigskip

\noindent
You need to submit a document containing the answers for the two questions 
below. You can do the implementation in any programming language you like, but you need 
to submit the source code with which you answered the questions. Otherwise
the submission will not be counted.  However, the coursework 
will \emph{only} be judged according to the answers. You can submit your answers
in a txt-file or as pdf.\bigskip


\subsection*{Question 1 (marked with 2\%)}

You need to lex and parse WHILE programs and submit the assembler 
instructions for the Fibonacci program and for the program you submitted
in Coursework 2 in Question 3. The latter should be so modified that 
a user can input the upper bound on the console (in the original question
it was fixed to 100).

\subsection*{Question 2 (marked with 2\%)}

Extend the syntax of you language so that it contains also \texttt{for}-loops, like

\begin{center}
\texttt{for} \;\textit{Id} \texttt{:=} \textit{AExp}\; \texttt{upto} \;\textit{AExp}\; \texttt{do} \textit{Block} 
\end{center}

\noindent
The intended meaning is to first assign the variable \textit{Id} the value of the first arithmetic 
expression, then go through the loop, at the end increase the value of the variable by 1, 
and finally test wether the value is not less or equal to the value of the second
arithmetic expression. For example the following instance of a \texttt{for}-loop 
is supposed to print out the numbers \texttt{2}, \texttt{3}, \texttt{4}.


\begin{center}
\begin{minipage}{6cm}
\begin{lstlisting}[language=While,basicstyle=\ttfamily, numbers=none]
for i := 2 upto 4 do {
    write i	
}
\end{lstlisting}
\end{minipage}
\end{center}

\noindent
There are two ways how this can be implemented: one is to adapt the code generation 
part of the compiler and generate specific code for \texttt{for}-loops; the other is to
translate the abstract syntax tree of \texttt{for}-loops into an abstract syntax tree using
existing language constructs. For example the loop above could be translated
to the following \texttt{while}-loop:

\begin{center}
\begin{minipage}{6cm}
\begin{lstlisting}[language=While,basicstyle=\ttfamily, numbers=none]
i := 2;
while (i <= 4) do {
    write i;
    i := i + 1;
}
\end{lstlisting}
\end{minipage}
\end{center}

\noindent
In this question you are supposed to give the assembler instructions for the
program

\begin{center}
\begin{minipage}{6cm}
\begin{lstlisting}[language=While,basicstyle=\ttfamily, numbers=none]
for i := 1 upto 10000 do {
  for i := 1 upto 10000 do {
  skip
  }
} 
\end{lstlisting}
\end{minipage}
\end{center}



\subsection*{Further Information}

The Java infrastructure unfortunately does not contain an assembler out-of-the-box
(therefore
you need to download the additional package Jasmin---see above). But it does contain a 
disassembler, called \texttt{javap}. A dissembler does the ``opposite'' of an assembler: it
generates readable assembler code from Java byte code. Have a look at the
following example: Compile using the usual Java compiler the simple Hello World 
program below:

\begin{center}
\begin{minipage}{10cm}
\begin{lstlisting}[language=Java,basicstyle=\ttfamily]
class HelloWorld {
    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}
\end{lstlisting}
\end{minipage}
\end{center}

\noindent
You can use the command

\begin{center}
\texttt{javap -v HelloWorld}
\end{center}

\noindent
to see the assembler instructions of the Java byte code that has been generated for this
program. You can compare this with the code generated for the Scala
version of Hello World.

\begin{center}
\begin{minipage}{10cm}
\begin{lstlisting}[language=Scala,basicstyle=\ttfamily]
object HelloWorld {
   def main(args: Array[String]) {
      println("Hello World!")
  }
}
\end{lstlisting}
\end{minipage}
\end{center}

\subsection*{Library Functions}

You need to generate code for the commands \texttt{write} and \texttt{read}. This
will require the addition of some ``library'' functions to your generated code. The first
command even needs two versions, because you might want to write out an
integer or a string. The Java byte code will need two separate functions for this.
For writing out an integer, you can use the assembler code

\begin{center}
\begin{minipage}{12cm}
\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
.method public static write(I)V 
    .limit locals 5 
    .limit stack 5 
    iload 0 
    getstatic java/lang/System/out Ljava/io/PrintStream; 
    swap 
    invokevirtual java/io/PrintStream/println(I)V 
    return 
.end method
\end{lstlisting}
\end{minipage}
\end{center}

\noindent 
This function will invoke Java's \texttt{println} function for integers. Then if you need
to generate code for \texttt{write x} where \texttt{x} is an integer variable, you can generate

\begin{center}
\begin{minipage}{8cm}
\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
iload n 
invokestatic XXX/XXX/write(I)V
\end{lstlisting}
\end{minipage}
\end{center}

\noindent
where \texttt{n} is the index where the value of the variable \texttt{x} is
stored. The \texttt{XXX/XXX} needs to be replaced with the class name 
which you use to generate the code (for example \texttt{fib/fib} in case
of the Fibonacci numbers).

Writing out a string is similar. The corresponding library function uses strings 
instead of integers:

\begin{center}
\begin{minipage}{12cm}
\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
.method public static writes(Ljava/lang/String;)V
   .limit stack 2
   .limit locals 2
   getstatic java/lang/System/out Ljava/io/PrintStream;
   aload 0
   invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
   return
.end method
\end{lstlisting}
\end{minipage}
\end{center}

\noindent
The code that needs to be generated for \texttt{write "some\_string"} commands 
is

\begin{center}
\begin{minipage}{8cm}
\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
ldc "some_string"
invokestatic XXX/XXX/writes(Ljava/lang/String;)V
\end{lstlisting}
\end{minipage}
\end{center}

\noindent
Again you need to adjust the \texttt{XXX/XXX} part in each call.

The code for \texttt{read} is more complicated. The reason is that inputting a string
will need to be transformed into an integer. The code in Figure~\ref{read} does this.
It can be called with

\begin{center}
\begin{minipage}{8cm}
\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
invokestatic XXX/XXX/read()I 
istore n
\end{lstlisting}
\end{minipage}
\end{center}

\noindent 
where \texttt{n} is the index of the variable that requires an input.


\begin{figure}[p]\small
\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
.method public static read()I 
      .limit locals 10 
      .limit stack 10

      ldc 0 
      istore 1  ; this will hold our final integer 
Label1: 
      getstatic java/lang/System/in Ljava/io/InputStream; 
      invokevirtual java/io/InputStream/read()I 
      istore 2 
      iload 2 
      ldc 10   ; the newline delimiter 
      isub 
      ifeq Label2 
      iload 2 
      ldc 32   ; the space delimiter 
      isub 
      ifeq Label2

      iload 2 
      ldc 48   ; we have our digit in ASCII, have to subtract it from 48 
      isub 
      ldc 10 
      iload 1 
      imul 
      iadd 
      istore 1 
      goto Label1 
Label2: 
      ;when we come here we have our integer computed in Local Variable 1 
      iload 1 
      ireturn 
.end method
\end{lstlisting}\normalsize
\caption{Assembler code for reading an integer from the console.\label{read}}
\end{figure}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: