--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/cw04.tex Tue Sep 01 16:00:37 2020 +0100
@@ -0,0 +1,421 @@
+% !TEX program = xelatex
+\documentclass{article}
+\usepackage{../style}
+\usepackage{../langs}
+
+\begin{document}
+
+%https://github.com/Storyyeller/Krakatau
+%https://docs.oracle.com/javase/specs/jvms/se7/html/
+
+% Jasmin Tutorial
+%http://saksagan.ceng.metu.edu.tr/courses/ceng444/link/jvm-cpm.html
+
+\section*{Coursework 4}
+
+\noindent This coursework is worth 10\% and is due on \cwFOUR{}
+at 18:00. You are asked to implement a compiler for
+the WHILE language that targets the assembler language
+provided by Jasmin or Krakatau (both have very similar
+syntax). 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 a mark of 0\% will
+be awarded. You should use the lexer and parser from the
+previous courseworks. Please package \emph{everything}(!) in
+a zip-file that creates a directory with the name
+\texttt{YournameYourFamilyname} on my end.
+
+\subsection*{Disclaimer\alert}
+
+It should be understood that the work you submit represents
+your own effort. You have not copied from anyone else. An
+exception is the Scala code I showed during the lectures,
+which you can use. You can also use your own code from the
+CW~1, CW~2 and CW~3.
+
+
+\subsection*{Jasmin Assembler}
+
+The Jasmin 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 into 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. For example:
+
+\begin{center}
+\texttt{java -cp . loops/loops}
+\end{center}
+
+\noindent There are also other resources about Jasmin on the
+Internet, for example
+
+\begin{center}
+\small\url{http://www.ceng.metu.edu.tr/courses/ceng444/link/f3jasmintutorial.html}
+\end{center}
+
+\noindent and
+
+\begin{center}
+ \small\url{http://www.csc.villanova.edu/~tway/courses/csc4181/s2018/labs/lab4/JVM.pdf}
+\end{center}
+
+\subsection*{Krakatau Assembler}
+
+The Krakatau assembler is available from
+
+\begin{center}
+\url{https://github.com/Storyyeller/Krakatau}
+\end{center}
+
+\noindent This assembler requires Python and a package called
+\pcode{ply} available from
+
+\begin{center}
+\url{https://pypi.python.org/pypi/ply}
+\end{center}
+
+\noindent This assembler is largely compatible with the Jasmin
+syntax---that means for the files we are concerned with here,
+it understands the same input syntax (no changes to your
+compiler need to be made; ok maybe some small syntactic
+adjustments are needed). You can generate Java Byte Code by
+using
+
+\begin{center}
+\texttt{python Krakatau-master/assemble.py loops.j}
+\end{center}
+
+\noindent where you may have to adapt the directory where
+Krakatau is installed (I just downloaded the zip file from
+Github and \pcode{Krakatau-master} was the directory where it
+was installed). Again the resulting class-file you can run with
+\texttt{java}.
+
+
+%\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}
+
+You need to lex and parse WHILE programs, and then generate
+Java Byte Code instructions for the Jasmin assembler (or
+Krakatau assembler). As solution you need to submit the
+assembler instructions for the Fibonacci and Factorial
+programs. Both should be so modified that a user can input on
+the console which Fibonacci number and which Factorial should
+be calculated. The Fibonacci program is given in
+Figure~\ref{fibs}. You can write your own program for
+calculating factorials. Submit your assembler code as
+a file that can be run, not as PDF-text.
+
+\begin{figure}[t]
+\lstinputlisting[language=while]{../progs/while-tests/fib.while}
+\caption{The Fibonacci program in the WHILE language.\label{fibs}}
+\end{figure}
+
+\subsection*{Question 2}
+
+Extend the syntax of your language so that it contains also
+\texttt{for}-loops, like
+
+\begin{center}
+\lstset{language=While}
+\code{for} \;\textit{Id} \texttt{:=} \textit{AExp}\; \code{upto}
+\;\textit{AExp}\; \code{do} \textit{Block}
+\end{center}
+
+\noindent The intended meaning is to first assign the variable
+\textit{Id} the value of the first arithmetic expression, test
+whether this value is less or equal than the value of the
+second arithmetic expression. If yes, go through the loop, and
+at the end increase the value of the loop variable by 1 and
+start again with the test. If no, leave the loop. For example
+the following instance of a \code{for}-loop is supposed to
+print out the numbers \pcode{2}, \pcode{3}, \pcode{4}.
+
+
+\begin{center}
+\begin{minipage}{12cm}
+\begin{lstlisting}[language=While, 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 \code{for}-loops; the other is to
+translate the abstract syntax tree of \code{for}-loops into
+an abstract syntax tree using existing language constructs.
+For example the loop above could be translated to the
+following \code{while}-loop:
+
+\begin{center}
+\begin{minipage}{12cm}
+\begin{lstlisting}[language=While, numbers=none]
+i := 2;
+while (i <= 4) do {
+ write i;
+ i := i + 1;
+}
+\end{lstlisting}
+\end{minipage}
+\end{center}
+
+\subsection*{Question 3}
+
+\noindent In this question you are supposed to give the
+assembler instructions for the program
+
+\begin{center}
+\begin{minipage}{12cm}
+\begin{lstlisting}[language=While, numbers=none]
+for i := 1 upto 10 do {
+ for i := 1 upto 10 do {
+ write i
+ }
+}
+\end{lstlisting}
+\end{minipage}
+\end{center}
+
+\noindent
+Note that in this program the variable \pcode{i} is used
+twice. You need to make a decision how it should be compiled?
+Explain your decision and indicate what this program would
+print out.
+
+\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 or Krakatau---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}{12cm}
+\begin{lstlisting}[language=Java,numbers=none]
+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}
+\begin{minipage}{12cm}
+\begin{lstlisting}[language={},numbers=none]
+javap -v HelloWorld
+\end{lstlisting}
+\end{minipage}
+\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}{12cm}
+\begin{lstlisting}[language=Scala,numbers=none]
+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 need to write out
+an integer and 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}[language=JVMIS, numbers=none]
+.method public static write(I)V
+ .limit locals 1
+ .limit stack 2
+ getstatic java/lang/System/out Ljava/io/PrintStream;
+ iload 0
+ 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}{12cm}
+\begin{lstlisting}[language=JVMIS, 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}[language=JVMIS, numbers=none]
+.method public static writes(Ljava/lang/String;)V
+ .limit stack 2
+ .limit locals 1
+ 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 \code{write
+"some_string"} commands is
+
+\begin{center}
+\begin{minipage}{12cm}
+\begin{lstlisting}[language=JVMIS,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}{12cm}
+\begin{lstlisting}[language=JVMIS,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. If you
+use Windows you need to take into account that a ``return'' is not just a newline,
+\code{'\\10'}, but \code{'\\13\\10'}. This means you need to change line~12 in
+Figure~\ref{read} to \pcode{ldc 13}.
+
+
+\begin{figure}[t]\small
+\begin{lstlisting}[language=JVMIS,numbers=left]
+.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 for Unix (Windows 13)
+ 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: