\section{Code generation}\label{sec:gen}
\subsection{Binary Representation}
\SPLC{} uses a simple stack layout in which all functions have their own stack
frame and all the arguments and local variables are present within this frame.
Arguments and local variables are either saved on the stack directly, or as a
pointer to the heap. This means that every allocated variable uses precisely
one stack address.

Simple values, i.e. \SI{Int}s, \SI{Bool}s and \SI{Char}s are stored directly on
the stack in their representative numeric value. Values on the stack in \SSM{}
are always numbers. For \SI{Int}s we use standard signed integers. For
characters \textsc{ASCII} values are used. A boolean true is
stored as a negative one and the boolean false is stored as a zero.

The heap simply grows with each added value, currently no garbage collection is
done. Functions, lists and tuples are currently stored in the heap. Lists are
represented simply as linked lists, by first storing the pointer to the next
list element and having the current list element in front of that pointer. The
empty list is represented as the null pointer. Tuples are stored by
storing the two values in succession on the heap and pointing to the first of
the two. Detailed description of function storage is explained in
Subsection~\ref{ssec:high}.

When calling a functions its arguments are placed on the stack, after which a
\tt{bsr} instruction calls the function. The function can then load its
arguments, if and when these are needed in an expression, by copying them from
below its stack frame. The \tt{bsr} instruction is an instruction that works
together with the \tt{ret} instruction. \tt{bsr} places the previous program
counter on the stack so that it can be restored with a \tt{ret}.

Note that the combination of this copying behaviour and passing complex values
as heap pointers means that in some cases \SPLC{} programs behave as
pass-by-value while in others it behave as pass-by-reference. Simple values
are trivially pass-by-value, whilst lists and tuples can behave as both,
depending on the usage. E.g. assigning a new list/tuple to an argument will
behave as pass-by-value, whilst changing the argument through a field selector
will behave as pass by reference, thus the pointer is passed by value.

Listing~\ref{lst:stackFunCall} shows the layout of the stack when executing the
two functions. the layout shown is the layout of the stack just before the
\tt{add} instruction to add x and y in plus. Note that, in compliance with
\SSM{}s calling model, the return address of a function is saved below the
stack frame of that function. When plus has returned, the two arguments are
popped of the stack and the value in \tt{RR} (for functions which do not return
\tt{Void}) is placed on the stack.

\begin{lstlisting}[
	label={lst:stackFunCall},
	caption={Stack layout during function calls},
	language=SPLCode]
plus(x, y}{ return x + y; }

main(){ var a = plus(3, 4); }

/*# | Stack
111 | 002   ;return address of main
;begin stack frame of main
112 | 110 	;Frame pointer for main; points to bottom of stack
113 | 003 	;arg1 for plus
114 | 004	;arg2 for plus
115 | 0fa 	;return address of plus
;begin stack frame of plus
116 | 112	;Frame pointer for plus; points to mains stack frame
117 | 003 	;x, loaded by ldl -3
118 | 004 	;y, loaded by ldl -2
*/
\end{lstlisting}

\subsection{Generation}
The code generation phase transforms a well typed \AST{} to either an error,
or a \tt{SSMProgram}. The latter is a list of labels and instructions. The
generation happens within a\\
\CI{WriterT SSMProgram (StateT (Addressbook, [Label]) (Either GenError)) a}\\
environment. Which we have implemented as a \tt{RWST} with \tt{()} for the
reading environment. In this \tt{Addressbook} is a simple map from
identifiers to \tt{Address}, which in turn is either a label to jump to or an
address where a variable can be found (relative to the current frame). The list
of labels is simply an infinite generator for fresh labels, used when
generating code for e.g. an if-statement.

Code generation is done by walking through the \AST{} depth first and
generating instructions for each encountered element. E.g. generation for an
\tt{Op2Expr} is simply recursively generating for each element of the
expression: \CI{g e1 >>| g e2 >>| g op}. For example the snippet in
Listing~\ref{lst:codegen} shows the code generation instance for the
implementation of the \SI{:} operator. First we generate the code for the left
part of the cons operator, the head, and afterwards the right side of the
operator, the tail. They are glued together by pushing the head and the tail
subsequently on the heap and what we are left with is the pointer to the tail.

\begin{lstlisting}[
	language=Clean,
	label={lst:codegen},
	caption={Code generation of the cons operator}]
instance g Expr where
	...
	g (Op2Expr _ e1 BiCons e2) = g e2 >>| g e1
		>>| tell [Instr "sth" [] ""]
		>>| tell [Instr "ajs" [Lit -1] ""]
		>>| tell [Instr "sth" [] ""]
	...
\end{lstlisting}

\subsection{Higher order functions}\label{ssec:high}
As extension this compiler can handle function types. Function types are
pointers to functions that may or may not have arguments already curried in. We
use the simple approach instead of the full fledged closure approach because of
time reasons. Adding the functionality in the lexer and parser was trivial
because of the modular nature. There was one small distinction that we had to
make which was the difference between a $0$-arity function call and a $0$-arity
function pointer. Currently \SI{read} is parsed as a function pointer and
\SI{read()} is parsed as a function call. Adding the functionality in the
semantic analysis was actually done from the start since the
\emph{Hindley-Milner} algorithm already supported it.

As all other data types, a function type object occupies one item on the stack
which contains a heap pointer. The heap pointer points to a position on the
heap that stores the function identification number, the number of arguments
already given and finally the argument values.  For example the snippet in
Listing~\ref{lst:highex} shows the representation of the incomplete function
\SI{plus} that already has two arguments.

\begin{lstlisting}[
	language=SPLCode,
	label={lst:highex},
	caption={Heap layout of curried functions}]
//SPLCode
plus(x, y, z){ return x + y + z; }

main(){
	var a = plus(4, 3);
}

/*# | Heap
001 | 008    //Function identification number
002 | 002    //Available arguments
003 | 004    //Argument 1
004 | 003    //Argument 2
*/
\end{lstlisting}

When an incomplete function is declared we save the remaining arity in our
state to be able to know when a function is complete and can be executed. When
a function is still not complete the function is copied in totality and the
available arguments position on the heap is increased accordingly and the
arguments are added on the heap. The reason we store the number of already
given arguments in the heap is because we need that information at run-time
since you can not know this at compile-time.

Normally we jump to functions using labels. But since we can not put labels on
the heap or stack we have introduced a function in the preamble that translate
integers to the corresponding label called \SI{1func}. When we want to
call a function that is identified by an address instead of a label we first
collect all the arguments from the heap and add the arguments given in the
function call. Calculating the number of arguments that have to be popped from
the heap is done at runtime using the \emph{Available Arguments} value stored
on the heap. Instead of jumping to a label we jump with a \texttt{bsr} to the
\SI{1func} function and make sure the identification is situated in register
R5. \SI{1func} then makes sure the correct function is branched to with a
\texttt{bra} and the caller can resume the normal execution path. In this way
the function can still use the \texttt{ret} instruction to leave the function.
