% !TEX program = xelatex
\documentclass{article}
\usepackage{../style}
\usepackage{../langs}
\usepackage{../grammar}
\usepackage{../graphics}


\begin{document}
\fnote{\copyright{} Christian Urban, King's College London, 2017, 2018, 2019}

\section*{Handout 7 (Compilation)}



The purpose of a compiler is to transform a program a human can read and
write into code the machine can run as fast as possible. The fastest
code would be machine code the CPU can run directly, but it is often
good enough for improving the speed of a program to target a
virtual machine. This produces not the fastest possible code, but code
that is often pretty fast. This way of producing code has the advantage that
the virtual machine takes care of things a compiler would normally need
to take care of (like explicit memory management). 

As a first example in this module we will implement a compiler for the
very simple While-language. It will generate code for the Java Virtual
Machine (JVM). Unfortunately the Java ecosystem does not come with an
assembler which would be handy for our  compiler-endeavour  (unlike
Microsoft's  Common Language Infrastructure for the .Net platform which
has an assembler out-of-the-box). As a substitute we use in this module
the 3rd-party programs Jasmin and Krakatau

\begin{itemize}
  \item \url{http://jasmin.sourceforge.net}
  \item \url{https://github.com/Storyyeller/Krakatau}
\end{itemize}

\noindent
The first is a Java program and the second a program written in Python.
Each of them allow us to generate \emph{assembly} files that are still
readable by humans, as opposed to class-files which are pretty much just
(horrible) zeros and ones. Jasmin (respectively Krakatau) will then take
an assembly file as input and generate the corresponding class file for
us. 

Good about the JVM is that it is a stack-based virtual machine, a fact
which will make it easy to generate code for arithmetic expressions. For
example when compiling the expression $1 + 2$ we need to generate the
following three instructions

\begin{lstlisting}[language=JVMIS,numbers=none]
ldc 1
ldc 2
iadd 
\end{lstlisting}

\noindent The first instruction loads the constant $1$ onto
the stack, the next one loads $2$, the third instruction adds both
numbers together replacing the top two elements of the stack
with the result $3$. For simplicity, we will throughout
consider only integer numbers. Therefore we can
use the JVM instructions \code{iadd}, \code{isub},
\code{imul}, \code{idiv} and so on. The \code{i} stands for
integer instructions in the JVM (alternatives are \code{d} for
doubles, \code{l} for longs and \code{f} for floats).

Recall our grammar for arithmetic expressions (\meta{E} is the
starting symbol):


\begin{plstx}[rhs style=, margin=3cm]
: \meta{E} ::= \meta{T} $+$ \meta{E}
         | \meta{T} $-$ \meta{E}
         | \meta{T}\\
: \meta{T} ::= \meta{F} $*$ \meta{T}
          | \meta{F} $\backslash$ \meta{T}
          | \meta{F}\\
: \meta{F} ::= ( \meta{E} )
          | \meta{Id}
          | \meta{Num}\\
\end{plstx}


\noindent where \meta{Id} stands for variables and \meta{Num}
for numbers. For the moment let us omit variables from arithmetic
expressions. Our parser will take this grammar and given an input
produce abstract syntax trees. For example we will obtain for the
expression $1 + ((2 * 3) + (4 - 3))$ the following tree.

\begin{center}
\begin{tikzpicture}
\Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]]
\end{tikzpicture}
\end{center}

\noindent To generate JVM code for this expression, we need to
traverse this tree in post-order fashion and emit code for
each node---this traversal in post-order fashion will produce
code for a stack-machine (what the JVM is). Doing so for the
tree above generates the instructions

\begin{lstlisting}[language=JVMIS,numbers=none]
ldc 1 
ldc 2 
ldc 3 
imul 
ldc 4 
ldc 3 
isub 
iadd 
iadd
\end{lstlisting}

\noindent If we ``run'' these instructions, the result $8$ will be on
top of the stack (I leave this to you to verify; the meaning of each
instruction should be clear). The result being on the top of the stack
will be an important convention we always observe in our compiler. Note,
that a different bracketing of the expression, for example $(1 + (2 *
3)) + (4 - 3)$, produces a different abstract syntax tree and thus also
a different list of instructions. Generating code in this
post-order-traversal fashion is rather easy to implement: it can be done
with the following recursive \textit{compile}-function, which takes the
abstract syntax tree as argument:

\begin{center}
\begin{tabular}{lcl}
$\textit{compile}(n)$ & $\dn$ & $\pcode{ldc}\; n$\\
$\textit{compile}(a_1 + a_2)$ & $\dn$ &
$\textit{compile}(a_1) \;@\;\textit{compile}(a_2)\;@\; \pcode{iadd}$\\
$\textit{compile}(a_1 - a_2)$ & $\dn$ & 
$\textit{compile}(a_1) \;@\; \textit{compile}(a_2)\;@\; \pcode{isub}$\\
$\textit{compile}(a_1 * a_2)$ & $\dn$ & 
$\textit{compile}(a_1) \;@\; \textit{compile}(a_2)\;@\; \pcode{imul}$\\
$\textit{compile}(a_1 \backslash a_2)$ & $\dn$ & 
$\textit{compile}(a_1) \;@\; \textit{compile}(a_2)\;@\; \pcode{idiv}$\\
\end{tabular}
\end{center}

However, our arithmetic expressions can also contain
variables. We will represent them as \emph{local variables} in
the JVM. Essentially, local variables are an array or pointers
to memory cells, containing in our case only integers. Looking
up a variable can be done with the instruction

\begin{lstlisting}[language=JVMIS,mathescape,numbers=none]
iload $index$
\end{lstlisting}

\noindent 
which places the content of the local variable $index$ onto 
the stack. Storing the top of the stack into a local variable 
can be done by the instruction

\begin{lstlisting}[language=JVMIS,mathescape,numbers=none]
istore $index$
\end{lstlisting}

\noindent Note that this also pops off the top of the stack.
One problem we have to overcome, however, is that local
variables are addressed, not by identifiers, but by numbers
(starting from $0$). Therefore our compiler needs to maintain
a kind of environment where variables are associated to
numbers. This association needs to be unique: if we muddle up
the numbers, then we essentially confuse variables and the
consequence will usually be an erroneous result. Our extended
\textit{compile}-function for arithmetic expressions will
therefore take two arguments: the abstract syntax tree and an
environment, $E$, that maps identifiers to index-numbers.

\begin{center}
\begin{tabular}{lcl}
$\textit{compile}(n, E)$ & $\dn$ & $\pcode{ldc}\;n$\\
$\textit{compile}(a_1 + a_2, E)$ & $\dn$ & 
$\textit{compile}(a_1, E) \;@\;\textit{compile}(a_2, E)\;@\; \pcode{iadd}$\\
$\textit{compile}(a_1 - a_2, E)$ & $\dn$ &
$\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{isub}$\\
$\textit{compile}(a_1 * a_2, E)$ & $\dn$ &
$\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{imul}$\\
$\textit{compile}(a_1 \backslash a_2, E)$ & $\dn$ & 
$\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{idiv}$\\
$\textit{compile}(x, E)$ & $\dn$ & $\pcode{iload}\;E(x)$\\
\end{tabular}
\end{center}

\noindent In the last line we generate the code for variables
where $E(x)$ stands for looking up the environment to which
index the variable $x$ maps to. This is similar to an interpreter,
which also needs an environment: the difference is that the 
interpreter maintains a mapping from variables to current values (what is the
currently the value of a variable), while compilers need a mapping
from variables to memory locations (where can I find the current 
value for the variable in memory).

There is a similar \textit{compile}-function for boolean
expressions, but it includes a ``trick'' to do with
\pcode{if}- and \pcode{while}-statements. To explain the issue
let us first describe the compilation of statements of the
While-language. The clause for \pcode{skip} is trivial, since
we do not have to generate any instruction

\begin{center}
\begin{tabular}{lcl}
$\textit{compile}(\pcode{skip}, E)$ & $\dn$ & $([], E)$\\
\end{tabular}
\end{center}

\noindent whereby $[]$ is the empty list of instructions. Note that
the \textit{compile}-function for statements returns a pair, a
list of instructions (in this case the empty list) and an
environment for variables. The reason for the environment is
that assignments in the While-language might change the
environment---clearly if a variable is used for the first
time, we need to allocate a new index and if it has been used
before, then we need to be able to retrieve the associated index.
This is reflected in the clause for compiling assignments, say
$\textit{x := a}$:

\begin{center}
\begin{tabular}{lcl}
$\textit{compile}(x := a, E)$ & $\dn$ & 
$(\textit{compile}(a, E) \;@\;\pcode{istore}\;index, E')$
\end{tabular}
\end{center}

\noindent We first generate code for the right-hand side of
the assignment and then add an \pcode{istore}-instruction at
the end. By convention the result of the arithmetic expression
$a$ will be on top of the stack. After the \pcode{istore}
instruction, the result will be stored in the index
corresponding to the variable $x$. If the variable $x$ has
been used before in the program, we just need to look up what
the index is and return the environment unchanged (that is in
this case $E' = E$). However, if this is the first encounter 
of the variable $x$ in the program, then we have to augment 
the environment and assign $x$ with the largest index in $E$
plus one (that is $E' = E(x \mapsto largest\_index + 1)$). 
To sum up, for the assignment $x := x + 1$ we generate the
following code

\begin{lstlisting}[language=JVMIS,mathescape,numbers=none]
iload $n_x$
ldc 1
iadd
istore $n_x$
\end{lstlisting}

\noindent 
where $n_x$ is the index (or pointer to the memory) for the variable
$x$. The code for looking-up the index for the variable is as follow:

\begin{center}
\begin{tabular}{lcl}
$index \;=\; E\textit{.getOrElse}(x, |E|)$
\end{tabular}
\end{center}

\noindent
In case the environment $E$ contains an index for $x$, we return it.
Otherwise we ``create'' a new index by returning the size $|E|$ of the
environment (that will be an index that is guaranteed to be not used
yet). In all this we take advantage of the JVM which provides us with 
a potentially limitless supply of places where we can store values
of variables.

A bit more complicated is the generation of code for
\pcode{if}-statements, say

\begin{lstlisting}[mathescape,language={},numbers=none]
if $b$ then $cs_1$ else $cs_2$
\end{lstlisting}

\noindent where $b$ is a boolean expression and where both $cs_{1/2}$
are the statements for each of the \pcode{if}-branches. Lets assume we
already generated code for $b$ and $cs_{1/2}$. Then in the true-case the
control-flow of the program needs to behave as 

\begin{center}
\begin{tikzpicture}[node distance=2mm and 4mm,
 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},
 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},
 skip loop/.style={black, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]
\node (A1) [point] {};
\node (b) [block, right=of A1] {code of $b$};
\node (A2) [point, right=of b] {};
\node (cs1) [block, right=of A2] {code of $cs_1$};
\node (A3) [point, right=of cs1] {};
\node (cs2) [block, right=of A3] {code of $cs_2$};
\node (A4) [point, right=of cs2] {};

\draw (A1) edge [->, black, line width=1mm] (b);
\draw (b) edge [->, black, line width=1mm] (cs1);
\draw (cs1) edge [->, black, line width=1mm] (A3);
\draw (A3) edge [->, black, skip loop] (A4);
\node [below=of cs2] {\raisebox{-5mm}{\small{}jump}};
\end{tikzpicture}
\end{center}

\noindent where we start with running the code for $b$; since
we are in the true case we continue with running the code for
$cs_1$. After this however, we must not run the code for
$cs_2$, but always jump after the last instruction of $cs_2$
(the code for the \pcode{else}-branch). Note that this jump is
unconditional, meaning we always have to jump to the end of
$cs_2$. The corresponding instruction of the JVM is
\pcode{goto}. In case $b$ turns out to be false we need the
control-flow

\begin{center}
\begin{tikzpicture}[node distance=2mm and 4mm,
 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},
 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},
 skip loop/.style={black, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]
\node (A1) [point] {};
\node (b) [block, right=of A1] {code of $b$};
\node (A2) [point, right=of b] {};
\node (cs1) [block, right=of A2] {code of $cs_1$};
\node (A3) [point, right=of cs1] {};
\node (cs2) [block, right=of A3] {code of $cs_2$};
\node (A4) [point, right=of cs2] {};

\draw (A1) edge [->, black, line width=1mm] (b);
\draw (b) edge [->, black, line width=1mm] (A2);
\draw (A2) edge [skip loop] (A3);
\draw (A3) edge [->, black, line width=1mm] (cs2);
\draw (cs2) edge [->,black, line width=1mm] (A4);
\node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};
\end{tikzpicture}
\end{center}

\noindent where we now need a conditional jump (if the
if-condition is false) from the end of the code for the 
boolean to the beginning of the instructions $cs_2$. Once we 
are finished with running $cs_2$ we can continue with whatever
code comes after the if-statement.

The \pcode{goto} and the conditional jumps need addresses to
where the jump should go. Since we are generating assembly
code for the JVM, we do not actually have to give (numeric)
addresses, but can just attach (symbolic) labels to our code.
These labels specify a target for a jump. Therefore the labels
need to be unique, as otherwise it would be ambiguous where a
jump should go to. A label, say \pcode{L}, is attached to code
like

\begin{lstlisting}[mathescape,numbers=none]
L:
  $instr_1$
  $instr_2$
    $\vdots$
\end{lstlisting}
 
\noindent where a label is indicated by a colon. The task of the
assmbler (in our case Jasmin or Krakatau) is to resolve the labels
to actual addresses, for example jump 10 instructions forward,
or 20 instructions backwards.
 
Recall the ``trick'' with compiling boolean expressions: the 
\textit{compile}-function for boolean expressions takes three
arguments: an abstract syntax tree, an environment for 
variable indices and also the label, $lab$, to where an conditional 
jump needs to go. The clause for the expression $a_1 = a_2$, 
for example, is as follows:

\begin{center}
\begin{tabular}{lcl}
$\textit{compile}(a_1 = a_2, E, lab)$ & $\dn$\\ 
\multicolumn{3}{l}{$\qquad\textit{compile}(a_1, E) \;@\;\textit{compile}(a_2, E)\;@\; \pcode{if_icmpne}\;lab$}
\end{tabular}
\end{center}

\noindent where we are first generating code for the
subexpressions $a_1$ and $a_2$. This will mean after running
the corresponding code there will be two integers on top of
the stack. If they are equal, we do not have to do anything
(except for popping them off from the stack) and just continue
with the next instructions (see control-flow of ifs above).
However if they are \emph{not} equal, then we need to
(conditionally) jump to the label $lab$. This can be done with
the instruction

\begin{lstlisting}[mathescape,numbers=none,language=JVMIS]
if_icmpne $lab$
\end{lstlisting}

\noindent Other jump instructions for boolean operators are

\begin{center}
\begin{tabular}{l@{\hspace{10mm}}c@{\hspace{10mm}}l}
$\not=$ & $\Rightarrow$ & \pcode{if_icmpeq}\\
$<$ & $\Rightarrow$ & \pcode{if_icmpge}\\
$\le$ & $\Rightarrow$ & \pcode{if_icmpgt}\\
\end{tabular}
\end{center}

\noindent and so on. I leave it to you to extend the
\textit{compile}-function for the other boolean expressions. Note that
we need to jump whenever the boolean is \emph{not} true, which means we
have to ``negate'' the jump condition---equals becomes not-equal, less
becomes greater-or-equal. If you do not like this design (it can be the
source of some nasty, hard-to-detect errors), you can also change the
layout of the code and first give the code for the else-branch and then
for the if-branch. However in the case of while-loops this
``upside-down-inside-out'' way of generating code still seems the most
convenient.

We are now ready to give the compile function for 
if-statements---remember this function returns for statements a 
pair consisting of the code and an environment:

\begin{center}
\begin{tabular}{lcl}
$\textit{compile}(\pcode{if}\;b\;\pcode{then}\; cs_1\;\pcode{else}\; cs_2, E)$ & $\dn$\\ 
\multicolumn{3}{l}{$\qquad L_\textit{ifelse}\;$ (fresh label)}\\
\multicolumn{3}{l}{$\qquad L_\textit{ifend}\;$ (fresh label)}\\
\multicolumn{3}{l}{$\qquad (is_1, E') = \textit{compile}(cs_1, E)$}\\
\multicolumn{3}{l}{$\qquad (is_2, E'') = \textit{compile}(cs_2, E')$}\\
\multicolumn{3}{l}{$\qquad(\textit{compile}(b, E, L_\textit{ifelse})$}\\
\multicolumn{3}{l}{$\qquad\phantom{(}@\;is_1$}\\
\multicolumn{3}{l}{$\qquad\phantom{(}@\; \pcode{goto}\;L_\textit{ifend}$}\\
\multicolumn{3}{l}{$\qquad\phantom{(}@\;L_\textit{ifelse}:$}\\
\multicolumn{3}{l}{$\qquad\phantom{(}@\;is_2$}\\
\multicolumn{3}{l}{$\qquad\phantom{(}@\;L_\textit{ifend}:, E'')$}\\
\end{tabular}
\end{center}

\noindent In the first two lines we generate two fresh labels
for the jump addresses (just before the else-branch and just
after). In the next two lines we generate the instructions for
the two branches, $is_1$ and $is_2$. The final code will
be first the code for $b$ (including the label 
just-before-the-else-branch), then the \pcode{goto} for after
the else-branch, the label $L_\textit{ifesle}$, followed by
the instructions for the else-branch, followed by the 
after-the-else-branch label. Consider for example the 
if-statement:

\begin{lstlisting}[mathescape,numbers=none,language=While]
if 1 = 1 then x := 2 else y := 3
\end{lstlisting}

\noindent 
The generated code is as follows:

\begin{lstlisting}[language=JVMIS,mathescape,numbers=left]
   ldc 1
   ldc 1
   if_icmpne L_ifelse $\quad\tikz[remember picture] \node (C) {\mbox{}};$
   ldc 2
   istore 0
   goto L_ifend $\quad\tikz[remember picture] \node (A) {\mbox{}};$
L_ifelse: $\quad\tikz[remember picture] \node[] (D) {\mbox{}};$
   ldc 3
   istore 1
L_ifend: $\quad\tikz[remember picture] \node[] (B) {\mbox{}};$
\end{lstlisting}

\begin{tikzpicture}[remember picture,overlay]
  \draw[->,very thick] (A) edge [->,to path={-- ++(10mm,0mm) 
           -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (B.east);
  \draw[->,very thick] (C) edge [->,to path={-- ++(10mm,0mm) 
           -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (D.east);
\end{tikzpicture}

\noindent The first three lines correspond to the the boolean
expression $1 = 1$. The jump for when this boolean expression
is false is in Line~3. Lines 4-6 corresponds to the if-branch;
the else-branch is in Lines 8 and 9. Note carefully how the
environment $E$ is threaded through the recursive calls of
\textit{compile}. The function receives an environment $E$,
but it might extend it when compiling the if-branch, yielding
$E'$. This happens for example in the if-statement above
whenever the variable \code{x} has not been used before.
Similarly with the environment $E''$ for the second call to
\textit{compile}. $E''$ is also the environment that needs to
be returned as part of the answer.

The compilation of the while-loops, say 
\pcode{while} $b$ \pcode{do} $cs$, is very similar. In case
the condition is true and we need to do another iteration, 
and the control-flow needs to be as follows

\begin{center}
\begin{tikzpicture}[node distance=2mm and 4mm,
 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},
 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},
 skip loop/.style={black, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]
\node (A0) [point, left=of A1] {};
\node (A1) [point] {};
\node (b) [block, right=of A1] {code of $b$};
\node (A2) [point, right=of b] {};
\node (cs1) [block, right=of A2] {code of $cs$};
\node (A3) [point, right=of cs1] {};
\node (A4) [point, right=of A3] {};

\draw (A0) edge [->, black, line width=1mm] (b);
\draw (b) edge [->, black, line width=1mm] (cs1);
\draw (cs1) edge [->, black, line width=1mm] (A3);
\draw (A3) edge [->,skip loop] (A1);
\end{tikzpicture}
\end{center}

\noindent Whereas if the condition is \emph{not} true, we
need to jump out of the loop, which gives the following
control flow.

\begin{center}
\begin{tikzpicture}[node distance=2mm and 4mm,
 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},
 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},
 skip loop/.style={black, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]
\node (A0) [point, left=of A1] {};
\node (A1) [point] {};
\node (b) [block, right=of A1] {code of $b$};
\node (A2) [point, right=of b] {};
\node (cs1) [block, right=of A2] {code of $cs$};
\node (A3) [point, right=of cs1] {};
\node (A4) [point, right=of A3] {};

\draw (A0) edge [->, black, line width=1mm] (b);
\draw (b) edge [->, black, line width=1mm] (A2);
\draw (A2) edge [skip loop] (A3);
\draw (A3) edge [->, black, line width=1mm] (A4);
\end{tikzpicture}
\end{center}

\noindent Again we can use the \textit{compile}-function for
boolean expressions to insert the appropriate jump to the
end of the loop (label $L_{wend}$ below).

\begin{center}
\begin{tabular}{lcl}
$\textit{compile}(\pcode{while}\; b\; \pcode{do} \;cs, E)$ & $\dn$\\ 
\multicolumn{3}{l}{$\qquad L_{wbegin}\;$ (fresh label)}\\
\multicolumn{3}{l}{$\qquad L_{wend}\;$ (fresh label)}\\
\multicolumn{3}{l}{$\qquad (is, E') = \textit{compile}(cs_1, E)$}\\
\multicolumn{3}{l}{$\qquad(L_{wbegin}:$}\\
\multicolumn{3}{l}{$\qquad\phantom{(}@\;\textit{compile}(b, E, L_{wend})$}\\
\multicolumn{3}{l}{$\qquad\phantom{(}@\;is$}\\
\multicolumn{3}{l}{$\qquad\phantom{(}@\; \text{goto}\;L_{wbegin}$}\\
\multicolumn{3}{l}{$\qquad\phantom{(}@\;L_{wend}:, E')$}\\
\end{tabular}
\end{center}

\noindent I let you go through how this clause works. As an example
you can consider the while-loop

\begin{lstlisting}[mathescape,numbers=none,language=While]
while x <= 10 do x := x + 1
\end{lstlisting}

\noindent yielding the following code

\begin{lstlisting}[language=JVMIS,mathescape,numbers=left]
L_wbegin: $\quad\tikz[remember picture] \node[] (LB) {\mbox{}};$
   iload 0
   ldc 10
   if_icmpgt L_wend $\quad\tikz[remember picture] \node (LC) {\mbox{}};$
   iload 0
   ldc 1
   iadd
   istore 0
   goto L_wbegin $\quad\tikz[remember picture] \node (LA) {\mbox{}};$
L_wend: $\quad\tikz[remember picture] \node[] (LD) {\mbox{}};$
\end{lstlisting}
 
\begin{tikzpicture}[remember picture,overlay]
  \draw[->,very thick] (LA) edge [->,to path={-- ++(10mm,0mm) 
           -- ++(0mm,17.3mm) |- (\tikztotarget)},line width=1mm] (LB.east);
  \draw[->,very thick] (LC) edge [->,to path={-- ++(10mm,0mm) 
           -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (LD.east);
\end{tikzpicture}

\noindent
I leave it to you to read the code and follow its controlflow.

Next we need to consider the statement \pcode{write x}, which
can be used to print out the content of a variable. For this
we need to use a Java library function. In order to avoid
having to generate a lot of code for each
\pcode{write}-command, we use a separate helper-method and
just call this method with an argument (which needs to be
placed onto the stack). The code of the helper-method is as
follows.


\begin{lstlisting}[language=JVMIS,numbers=left]
.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}

\noindent The first line marks the beginning of the method,
called \pcode{write}. It takes a single integer argument
indicated by the \pcode{(I)} and returns no result, indicated
by the \pcode{V}. Since the method has only one argument, we
only need a single local variable (Line~2) and a stack with
two cells will be sufficient (Line 3). Line 4 instructs the
JVM to get the value of the field \pcode{out} of the class
\pcode{java/lang/System}. It expects the value to be of type
\pcode{java/io/PrintStream}. A reference to this value will be
placed on the stack. Line~5 copies the integer we want to
print out onto the stack. In the next line we call the method
\pcode{println} (from the class \pcode{java/io/PrintStream}).
We want to print out an integer and do not expect anything
back (that is why the type annotation is \pcode{(I)V}). The
\pcode{return}-instruction in the next line changes the
control-flow back to the place from where \pcode{write} was
called. This method needs to be part of a header that is
included in any code we generate. The helper-method
\pcode{write} can be invoked with the two instructions

\begin{lstlisting}[mathescape,language=JVMIS]
iload $E(x)$ 
invokestatic XXX/XXX/write(I)V
\end{lstlisting}

\noindent where we first place the variable to be printed on
top of the stack and then call \pcode{write}. The \pcode{XXX}
need to be replaced by an appropriate class name (this will be
explained shortly).


\begin{figure}[t]
\begin{lstlisting}[mathescape,language=JVMIS,numbers=left]
.class public XXX.XXX
.super java/lang/Object

.method public <init>()V
    aload_0
    invokenonvirtual java/lang/Object/<init>()V
    return
.end method

.method public static main([Ljava/lang/String;)V
    .limit locals 200
    .limit stack 200

      $\textit{\ldots{}here comes the compiled code\ldots}$

    return
.end method
\end{lstlisting}
\caption{Boilerplate code needed for running generated code.\label{boiler}}
\end{figure}


By generating code for a While-program, we end up with a list
of (JVM assembly) instructions. Unfortunately, there is a bit
more boilerplate code needed before these instructions can be
run. The complete code is shown in Figure~\ref{boiler}. This
boilerplate code is very specific to the JVM. If we target any
other virtual machine or a machine language, then we would
need to change this code. Lines 4 to 8 in Figure~\ref{boiler}
contain a method for object creation in the JVM; this method
is called \emph{before} the \pcode{main}-method in Lines 10 to
17. Interesting are the Lines 11 and 12 where we hardwire that
the stack of our programs will never be larger than 200 and
that the maximum number of variables is also 200. This seem to
be conservative default values that allow is to run some
simple While-programs. In a real compiler, we would of course
need to work harder and find out appropriate values for the
stack and local variables.

To sum up, in Figure~\ref{test} is the complete code generated
for the slightly nonsensical program

\begin{lstlisting}[mathescape,language=While]
x := 1 + 2;
write x
\end{lstlisting}

\noindent I let you read the code and make sure the code behaves as
expected. Having this code at our disposal, we need the assembler to
translate the generated code into JVM bytecode (a class file). This
bytecode is then understood by the JVM and can be run by just invoking
the \pcode{java}-program.


\begin{figure}[p]
\lstinputlisting[language=JVMIS]{../progs/test-small.j}
\caption{Generated code for a test program. This code can be 
processed by an Java assembler producing a class-file, which
can be run by the {\tt{}java}-program.\label{test}}
\end{figure}

\subsection*{Arrays}

Maybe a useful addition to the While-language would be arrays. This
would let us generate more interesting While-programs by translating
BF*** programs into equivalent While-code. So in this section lets have
a look at how we can support the following three constructions

\begin{lstlisting}[mathescape,language=While]
new arr[15000]
x := 3 + arr[3 + y]
arr[42 * n] := ...
\end{lstlisting}

\noindent
The first construct is for creating new arrays, in this instance the
name of the array is \pcode{arr} and it can hold 15000 integers. The
second is for referencing an array cell inside an arithmetic
expression---we need to be able to look up the contents of an array at
an index determined by an arithmetic expression. Similarly in the line
below, we need to be able to update the content of an array at an
calculated index.  

For creating a new array we can generate the following three JVM
instructions:

\begin{lstlisting}[mathescape,language=JVMIS]
ldc number 
newarray int 
astore loc_var
\end{lstlisting}

\noindent
First we need to put the dimension of the array onto the stack. The next
instruction creates the array. With the last we can store the array as a
local variable (like the ``simple'' variables from the previous
section). The use of a local variable for each array allows us to have
multiple arrays in a While-program. For looking up an element in an
array we can use the following JVM code

\begin{lstlisting}[mathescape,language=JVMIS]
aload loc_var 
index_aexp 
iaload
\end{lstlisting}

\noindent
The first instruction loads the ``pointer'' to the array onto the stack.
Then we have some instructions corresponding to the index where we want
to look up the array. The idea is that these instructions will leave a
concrete number on the stack, which will be the index into the array we
need. Finally we need to tell the JVM to load the corresponding element
onto the stack. Updating an array at an index with a value is as
follows.

\begin{lstlisting}[mathescape,language=JVMIS]
aload loc_var 
index_aexp 
value_aexp 
iastore
\end{lstlisting}

\noindent
Again the first instruction loads the ``pointer'' to the array onto the
stack. Then we have some instructions corresponding to the index where
we want to update the array. After that come the instructions for with
what value we want to update the array. The last line contains the
instruction for updating the array.

Next we need to modify our grammar rules for our While-language: it
seems best to extend the rule for factors in arithmetic expressions with
a rule for looking up an array.

\begin{plstx}[rhs style=, margin=3cm]
: \meta{E} ::= \meta{T} $+$ \meta{E}
         | \meta{T} $-$ \meta{E}
         | \meta{T}\\
: \meta{T} ::= \meta{F} $*$ \meta{T}
          | \meta{F} $\backslash$ \meta{T}
          | \meta{F}\\
: \meta{F} ::= ( \meta{E} )
          | $\underbrace{\meta{Id}\,[\,\meta{E}\,]}_{new}$
          | \meta{Id}
          | \meta{Num}\\
\end{plstx}

\noindent
There is no problem with left-recursion as the \meta{E} is ``protected''
by an identifier and the brackets. There are two new rules for statements,
one for creating an array and one for array assignment:

\begin{plstx}[rhs style=, margin=2cm, one per line]
: \meta{Stmt} ::=  \ldots
              | \texttt{new}\; \meta{Id}\,[\,\meta{Num}\,] 
              | \meta{Id}\,[\,\meta{E}\,]\,:=\,\meta{E}\\
\end{plstx}

With this in place we can turn back to the idea of creating While
programs by translating BF programs. This is a relatively easy task
because BF only has eight instructions (we will actually only have seven
because we can omit the read-in instruction from BF). But also translating
BF-loops is going to be easy since they straightforwardly can be 
represented by While-loops. The Scala code for the translation is
as follows:

\begin{lstlisting}[language=Scala,numbers=left]
def instr(c: Char) : String = c match {
  case '>' => "ptr := ptr + 1;"
  case '<' => "ptr := ptr - 1;"
  case '+' => "field[ptr] := field[ptr] + 1;"
  case '-' => "field[ptr] := field[ptr] - 1;"
  case '.' => "x := field[ptr]; write x;"
  case '['  => "while (field[ptr] != 0) do {"
  case ']'  => "skip};"
  case _ => ""
}
\end{lstlisting}

\noindent 
The idea behind the translation is that BF-programs operate on an array,
called \texttt{field}. The BP-memory pointer into this array is
represented as the variable \texttt{ptr}. The BF-instructions \code{>}
and \code{<} increase, respectively decrease, \texttt{ptr}. The
instructions \code{+} and \code{-} update a cell in \texttt{field}. In
Line 6 we need to first assign a field-cell to an auxiliary variable
since we have not changed our write functions in order to cope with
writing out any array-content directly. Lines 7 and 8 are for
translating BF-loops. Line 8 is interesting in the sense that we need to
generate a \code{skip} instruction just before finishing with the 
closing \code{"\}"}. The reason is that we are rather pedantic about
semicolons in our While-grammar: the last command cannot have a
semicolon---adding a \code{skip} works around this snag. Putting
all this together is we can generate While-programs with more than
400 instructions and then run the compiled JVM code for such programs.


\end{document}

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