run-time data structure

Memory model

There are two chunk of memory for run-time data structure of Nut: heap and stack segment.  Heap contains the code segment and the data segment.  Code segment is initialised by the loader.  The loader reads an object file and puts the n-code into code segment.  Data segment is used to stored variables, the global data.  The global data is allocated by "new" instruction.  

Stack segment contains activation records, the data occurs at run-time when a function is called.  The activation record contains all local variables and state of computation such as fp (frame pointer) and sp (stack pointer).  When a variable is accessed, for example

    (vec a (+ i 10))

    => (ldx.a (+ get.i lit.10))

the "get.i" instruction accesses the local variable "i" through the frame pointer from the stack segment by,  SS[fp-i] where SS is the stack segment.  The "ldx.a" accesses global data in data segment using the base address "a" (gets it from SS) and index (+ i 10) that is available from the stack (pointed to by sp).  The effective address for acessing data segment is ea = SS[fp-a] + SS[sp], then the value of (vec a (+ i 10)) is  heap[ea].

The part of memory SS[sp] can be called "evaluation stack".  It stores the intermediate values during computation of an expression. Our scheme combines the activation record with the evaluation stack within a single stack segment.  

To make it clear one can imagine 4 chunks of memory: code segment, data segment, stack segment, and evaluation stack. Code segment stores n-code, executable machine codes.  The data in the code segment is dot-pair and atoms.  Data segment stores global data, allocated by "new" instruction.  Stack segment stores activation records pointed to by fp.  Evaluation stack stores intermediate computation results, pointed to by sp.  Our heap combines code segment and data segment.  The SS combines stack segment and evaluation stack.  The figure below shows SS.

SS[.]

hi memory

..    <-- sp  // evaluation stack

fp'   <-- fp  // current activation record
lv1
..            // local variables
lvn

lo memory

Parameter passing

Actual parameters are evaluated and reside in the evaluation stack.  They are passed to a function when a function is called.  When a function is called, it creates a new activation record by overlapping its stack frame with the evaluation stack.  No parameters need to be copy to the new activation record.  For example,

(def sum3 (a b c) () (+ a (+ b c)))

(def main () () (sum3 4 5 6))

When "main" starts the arguments of "sum3" is evaluated one-by-one and the results are resided on the evaluation stack (pointed to by sp).

SS

hi mem

6  <-- sp
5
4

lo mem

then "sum3" is called.  "sum3" creates its own activation record on top of the evaluation stack.  The new evaluation stack starts at the top of the current activation record (sp = fp).

SS

hi mem

fp'  <-- fp <--sp
6    // lv.c
5    // lv.b
4    // lv.a

lo mem


The local variable "a" can be accessed by an offset from fp, SS[fp-a].  This overlapping also reordered the position of local
variables looking from the reference point of fp.  The number of a local variables is renamed from 1..n to n..1.  This is done by the compiler.

8 December 2004
P. Chongstitvatana