From 0dd77149ffbd3c3ca2e24671f1de648ea87f11f4 Mon Sep 17 00:00:00 2001 From: pimjager Date: Wed, 15 Jun 2016 15:23:01 +0200 Subject: [PATCH] report dingetejes --- deliverables/report/eval.tex | 43 ++++++++++++++++++++++ deliverables/report/gen.tex | 69 ++++++++++++++++++++++++++++++++++-- deliverables/report/sem.tex | 2 +- deliverables/report/todo.txt | 4 +-- 4 files changed, 112 insertions(+), 6 deletions(-) diff --git a/deliverables/report/eval.tex b/deliverables/report/eval.tex index cd3fc7f..ec111a6 100644 --- a/deliverables/report/eval.tex +++ b/deliverables/report/eval.tex @@ -1 +1,44 @@ \section{Evaluation} +All in all we are quite happy with \SPLC{}. Our added syntactic sugar and the +higher order functions make our implementation of \SPL{} quite comfortable to +program in. Due to the UNIX style interface it is quite easy to combine +usage of the compiler with \SSM{}. + +There are however of course a lot of things to can be improved. We discuss +a few of +the most interesting and most pressing issues. First of all error handling in +\SPLC{} can be greatly improved. Currently a lot of error happen at position +(0,0), most notably all type errors happen at this position. It would be a great +improvement in usability if errors would always be reported at the correct +position. A second issue is that in \SPLC{} it is not possible to spread a +program over multiple modules, when developing larger programs this would an +absolute requirement. Thirdly \SPLC{} currently does not allow for multiple +recursion, and all functions need to be declared before they are called. It +would be nice to have multiple recursion and to not be forced to structure your +program in the order in which functions are called. + +\subsection{Work division} +\begin{description} + \item [Lexing \& parsing] : \\ + \begin{description} + \item [Yard] Pim + \item [Lexing] Mart \& Pim + \item [Parsing] Mostly Mart, some Pim + \item [Sugar] literal string: Mart, literal lists: Pim, Variable + arguments printing: Mart, Let-expansion: Pim, Lambdas: Pim + \end{description} + \item [Semantical analysis] : \\ + \begin{description} + \item [Sanity checks] Mart + \item [Type inference] Mostly Pim, some Mart + \item [Lambda lifting] Pim + \end{description} + \item [Code generation] : \\ + \begin{description} + \item [RWST monad] Mart + \item [Basic Generation] Mart \& Pim + \item [Higher order functions] Mart + \end{description} +\end{description} +%thoughts about compiler +%division \ No newline at end of file diff --git a/deliverables/report/gen.tex b/deliverables/report/gen.tex index 0695174..ee377e6 100644 --- a/deliverables/report/gen.tex +++ b/deliverables/report/gen.tex @@ -1,9 +1,72 @@ \section{Code generation}\label{sec:gen} -\subsection{ABR} -%Heap en stack layout +\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. Simple values, i.e. Ints, Bools and Chars are stored +directly on the stack, while other values are stored on the heap. + +The heap simply grows with each added value, currently no garbage collection is +done. Lists are represented simply as linked lists, by first storing the pointer +to the next list element and then the current list element. Tuples are simply +stored by staring the two values in succession. + +When calling a functions its arguments are placed on the stack, after which +a \tt{bsr} instruction calls the function. The functions can then load its +arguments, if and when these are needed in an expression, by copying them +from below its stack frame. + +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. + +Listing~\ref{lst:stackFunCall} shows the layout of the stack executing the +two functions. the layout shown is the layout of the stack just before +the \tt{add} instruction to add x and y. 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{SPLCode} \label{lst:stackFunCall} +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{SPLCode} \subsection{Generation} -%gewoon hoe het werkt +The code generation phase transforms a well typed \AST{} to either an error, +or an \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}. \subsection{Higher order functions} The nature of the type checking algorithm already included type checking and diff --git a/deliverables/report/sem.tex b/deliverables/report/sem.tex index 9fc3dee..cddc19b 100644 --- a/deliverables/report/sem.tex +++ b/deliverables/report/sem.tex @@ -156,7 +156,7 @@ type then in itself can be a function. | CharType | VoidType | FuncType Type -- (-> t) - | (\->>) infixl 7 Type Type -- (t1 -> t2) + | (->>) infixl 7 Type Type -- (t1 -> t2) \end{lstlisting} \subsubsection{Environment} diff --git a/deliverables/report/todo.txt b/deliverables/report/todo.txt index 130480f..93baba5 100644 --- a/deliverables/report/todo.txt +++ b/deliverables/report/todo.txt @@ -1,5 +1,5 @@ VINK pim parse: Uitleggen over YARD VINK pim sem: sem opschonen appendix, die pagina landscape(package: lscape, \begin{lscape}) -pim gen: abi en generation +VINK pim gen: abi en generation mart gen: higher order functions -pim eval: doen +VINK pim eval: doen -- 2.20.1