Runtime system and the evaluator


How eval works?

The evaluator (function eval) is the machine that executes the internal forms (N-code).  The global data is allocated from the data segment when the variable is defined. The local data is dynamic and is allocated from the stack segment.  The local data is created when passing the actual parameters to a function and is destroyed when exit from the function.  Because the function call has the behaviour of last-in-first-out (LIFO) as the earliest call will exit the last, a stack structure is suitable for allocating the local data for function calls.

Using a stack gains a huge benefit of automatic reclamation of the memory when the local data is not longer in used.  (You may think this is obvious but this is the beauty of it.  Think about other alternative way of storing local data such as linked-list.  The local data once ceased to exist will have to be reclaim by some method).

             stack
   rho -->  |       |
            |-------|
 local1 --> |       |
            |-------|
 local2 --> |       |
            | . . . |

The global and local data can be handled in the same way except that the global data is in the data segment and the local data is in the stack segment.

The evaluation (execution) of a program employs a stack data structure.  All variables are accessed through the structure called "activation record" (or "stack frame").  When a function is evaluated, its has its local environment (local variables and stack area).  The activation record is maintained through two global pointers: fp (frame pointer), and sp (stack pointer).

hi mem

     ...   <-- sp
     lvn
     ...
     lv2
     lv1
           <-- fp
lo mem

The argument of value-instruction is the index relative to the frame pointer.  For example, to get a value of a local variable 3, the instruction "get.3", the access is SS[fp+3] where SS[.] is the memory.  Usually this part of memory is called "stack segment".

Most instructions take their argument from the evaluation stack.  The result (if any) is pushed back to the stack.  In this sense, N-code is said to be stack-based instructions.  The evaluation stack is local to the current activation record (pointed to by sp).
 

Function call instruction

(fun.a.v e)

create a new activation record, passing arguments from the evaluation stack to this environment, eval(e) the body of function, and delete the activation record.  Two parameters are required to handle creation and deletion of activation record: arity and the size of frame.  The encoding is "fun.a.v" where a is arity, v is the size of frame, used in the deletion of AR, k is v-arity+1, used in the creation of AR.

The action of "fun.a.v" is:   
SS[.] denotes stack segment

k = v-a+1        // offset from current sp
k = fp           // save current fp
fp = sp-a        // new fp
sp = fp+v        // move sp to new frame
x = eval(e)      // eval body
                    // then do a return
sp = fp             // delete frame
fp = k              // restore old fp

Where to store the old fp (k) depends on the implementation. 

run-time supports

To actually run n-code, the virtual machine provides run-time supports. The memory model is an important consideration. The actual memory is provided through the implementation language (C in our case).  In general, three parts of memory exist:

code segment -- storing n-code
data segment -- storing static/dynamic data
stack segment -- the run-time stack storing activation record and evaluation stack

M[]  size MEMEND

M[ cs  | ds  | ss ]
             ^
           MEMMAX

The loader loads the object into the memory. The n-code starts at the address 2.  The data starts at the address 0 and must be relocated to be next to the code segment.  In relocating the data, the instructions that involve global variables: ld, st, ldy, sty, str, must have their arguments offsetted.

How the simulator-in-nut (eval.nut) arranges its memory?

The base virtual machine (nvm.c) loads the object of eval-in-nut (eval.obj) first, then starts executing it. This causes eval-in-nut to read the object code from stdin and evaluating it.  eval-in-nut must relocate its n-code to begin behind eval.obj and also its data behind its n-code. To relocate the code, the argument to call instruction must be offsetted. To relocate the data, the argument to the instruction accessing globals must be offsetted.

M[ eval.obj | n-code | data | stack | ss ]
    ^                              ^
   eval-in-nut                  stack of eval

Once the object code is loaded by eval-in-nut, it starts its execution by allocating its stack segment and set sp, fp appropriately.

main
  readinfile
  load object
  initialise eval-in-nut
  eval start

eval
  get the operator and its arg-list, e1
  decode op arg
  swith op
    ADD
      (eval head e1) + (eval arg2 e1)
    IF
      if (eval head e1) != 0
        eval arg2 e1
      else
        eval arg3 e1
    CALL
      eval all arg and push them to eval stack
      eval the function
    LIT
      push arg
    GET
      push SS[fp+arg]
    ...

How to use eval.nut

First, compile eval.nut and rename a.obj to eval.obj

> nutc eval.nut
> copy a.obj eval.obj

The test file is: ("test-eval.nut")

(def add1 x () (+ x 1))
(def main () ()
  (sys 1 (add1 3)))

Compile it and keep its object file.

> nutc test-eval.nut
> copy a.obj test-eval.obj

Try to run test-eval.obj using the known good virtual machine (nvm)

> nvm test-eval.obj
4

Now try to use eval.obj to "evaluate" (execute) the test object.

> nvm eval.obj < test-eval.obj

1892 (fun.1.1 (+ get.1 lit.1 ))
1904 (fun.0.0 (sys.1 (call.1892 lit.3 )))
4


last update  5 Nov 2009