Sun Oct 10 18:49:53 CEST 2010

Tree walking vs byte code

Is ANF byte code just CDR-coded treewalking?  Looks like it.  Code
takes the form of a sequence of LET and BEGIN forms.  You only need
one bit to distinguish between both, so let's focus on LET only.

So byte code would look like this:

       PUSHK(ex1_r)     // start of let
       jump code_ex1    // compute value (this code jumps to k_return)
ex1_r: PUSH(e, v)       // continuation code pops value to env stack
       ...              // execute body of let

/* This code can also just be inlined. */
code_ex1:  ...
           v = some_data
           goto k_return

k_return:  c = POP(k)
           i = NPOP(c)  // address of ex1_r
           e = POP(c)   // restore env

The above is a bit informal but the idea is quite simple: 

Before jumping into a machine code procedure that computes a value v
to be added to the environment as a new binding, push a continuation
frame that saves the environment, and the code address to resume

The environment is caller-saved because the callee might be an
application of a closure which destroys the environment.

In the current vm.c the continuation needs 3 args instead: syntax (c)
+ interpreter (continuation bytecode such as k_let and k_begin).