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". 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
fp' <-- fp
lv1
lv2
...
lvn
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 (from fp upward,
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 sp
SS[sp+k] = fp
// save old fp
fp = sp+k
// new frame
sp = fp
// move sp to new frame
x = eval(e)
// eval body
//
then do a return
sp = fp-v-1
// delete frame
fp = SS[fp]
// restore old fp
run-time supports
To actually run n-code, the simulator provides run-time supports. The
memory model is an important factor. The actual memory is provide
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 (sim.txt) arranges its memory?
The base simulator (nsim.c) loads the object of simulator-in-nut
(a.obj) first, then starts executing it. This causes sim-in-nut to read
the object code from stdin and evaluating it. sim-in-nut must
relocate its n-code to begin behind a.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[
a.obj | n-code | data | stack | ss ]
^
^
sim-in-nut
stack of nsim
Once the object code is loaded by sim-in-nut, it starts its execution
by allocating its stack segment and set sp, fp appropriately.
main
readinfile
load object
initialise sim-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]
...
27 June 2006