deliverables/report/gen.tex

   1 \section{Code generation}\label{sec:gen}
   2 \subsection{ABR}
   3 %Heap en stack layout
   4
   5 \subsection{Generation}
   6 %gewoon hoe het werkt
   7
   8 \subsection{Higher order functions}
   9 The nature of the type checking algorithm already included type checking and
  10 inferring the type of higher order functions. Since we allow constants there is
  11 a difference between \SI{read} and \SI{read()}. To make this difference we
  12 introduced a separate type of expression called a \SI{FuncType}, this type
  13 encodes a function with arity $0$.
  14
  15 As all other data types a function type object occupies one item on the stack
  16 which contains a heap pointer. The heap pointer points to a position on the
  17 heap that stores, in increasing addresses, the function identification number,
  18 the number of arguments already given and finally the argument values.
  19 For example the following snippet shows the representation of the incomplete
  20 function \SI{plus} that already has two arguments.
  21 \begin{SPLCode}
  22 //SPLCode
  23 plus(x, y, z){ return x + y + z; }
  24
  25 main(){
  26         var a = plus(4, 3);
  27 }
  28
  29 /*# | Stack
  30 001 | 001    //Pointer to the
  31 ... |
  32
  33   # | Heap
  34 001 | 008    //Function identification number
  35 002 | 002    //Available arguments
  36 003 | 004    //Argument 1
  37 004 | 003    //Argument 2
  38 */
  39 \end{SPLCode}
  40
  41 When an incomplete function is declared we save the remaining arity in our
  42 state to be able to know when a function is complete and can be executed. When
  43 a function is still not complete the function is copied in totality and the
  44 available arguments position on the heap is increased accordingly and the
  45 arguments are added on the heap.
  46
  47 Function numbers are integers that identify the function. Normally we address
  48 functions using labels but it is not possible to store labels on the heap or on
  49 the stack. Therefore we include a function in the preamble that is basically a
  50 dictionary from integers to labels. All functions have their unique number that
  51 identifies them via the function dictionary called \SI{1func}. When we want to
  52 call a function that is identified by an address instead of a label we first
  53 collect all the arguments from the heap and add the arguments given in the
  54 function call. Calculating the number of arguments that have to be popped from
  55 the heap is done at runtime using the \emph{Available Arguments} value stored
  56 on the heap. Instead of jumping to a label we jump to the \SI{1func} function
  57 and make sure the identification is situated in register R5. \SI{1func} then
  58 makes sure the correct function is branched to and the caller can resume the
  59 normal execution path.