Part Ia. SECD: a high-level description


Contents

  • SECD: about
  • Part I and Part Ia describe high-level, formal definition of a SECD machine;
  • Part II discusses low-level details of SECD C implementation;
  • Part III (TODO): how to compile a Scheme subset into SECD code.

Things are getting dirty: putting functional in the SECD

Now we’re starting the most interesting part, adding functions into the functional virtual machine. First of all, a function is usually tied to its environment: a pair of function definition (arguments and body) and the environment it has been created in is called closure. So don’t be afraid of this semantic rules for opcode LDF (the newly made closure is underlined):

  • (s, e, LDF.(args body).c, d) => (((args body).e).s, e, c, d)

I want to stress that the environment is paired with the function definition on the stack, producing a closure (args body).e, which may be saved, used as an argument to another function (thus bound to a symbol), and so on.

The closure on top of the stack may be called using opcode AP:

  • (((argnames body).e').argvals.s, e, AP.c, d)
    => ( (), new-frame(argnames, argvals).e', body, s.e.c.d)


This definition is getting quite complex, let’s parse it step by step. State of the machine before the call was: a closure (args body).e') on top of the stack, a list of argument values argvals below it, the rest of stack being s. AP makes a few profound changes:

  1. old stack s, old environment e and old control path c are all saved on the dump: the new dump is s.e.c.d, we’ll need those values on return from the function;
  2. e' is extracted from the closure and is now considered the new environment; but hold on, we have also to make a frame for function arguments and prepend it to e': new-frame(args, argvals).e' is the new environment;
  3. body becomes the new control path;

After that, we’re ready to execute the function body and to restore the previous state using RTN, putting the result of the function (v) on top of the previous stack:

  • (v.(), e', RTN.(), s.e.c.d) => (v.s, e, c, d)

Now, let’s get this together and make a simple example of a function f(x)=x2:

  ;; In order to apply this definition, 
  ;; a list of arguments values must be already on the stack:
  LDC (5)   ;; list (5) is on the stack now
  ;; now pushing a closure on the stack:
  LDF ((x)     ;;  argument list: `x` will be bound to 5 after AP
       (LD x  LD x  MUL  RTN))    ;; body to be jumped to after AP
  ;; apply!
  AP
  ;; now 52 = 25 must be on the stack.

Another example, let’s call our x2+y2:

  ;; preparing arguments
  LDC ()   LDC 4  CONS  LDC 3  CONS   ;; => (3 4)
  ;; loading closure
  LDF ((x y)  (LD x LD x MUL LD y LD y MUL ADD RTN))
  ;; let's go!
  AP ;; => 25

Now an example of higher-order functions. Let’s pass function x+1 to function f(g) = g(5):

  ;; preparing the argument list:
  LDC ()
  ;; put a closure for an increment on the arg list:
  LDF ((x) (LD x  LDC 1  ADD  RTN))
  CONS
  ;; now make closure for f:
  LDF ((g) (LDC (5)  LD g   AP  RTN))
  ;; go!
  AP  ;; => 6

Nice, isn’t it?

Brain explosion guaranteed: getting recursive

You’ve gotten pretty far if you’re still reading this. And if you’re sad that function definition/application is the hardest part and it’s overcome, I have to encourage you: recursion in SECD is a kind of even more complex mental puzzle. You’re warned.

What’s wrong with AP, why we cannot get recursive call with it? Yes, we can call a closure of a function from inside the function, but how to put this closure into the environment? Turns out that it is not possible without imperative modification of the environment, and it’s done by a couple of special opcodes: DUM and RAP. DUM creates a dummy environment frame Ω to be replaced with the recursive environment later by RAP. Generally DUM/RAP usage looks like this:

DUM    ;; frame Ω holding a dummy pointer is prepended to the environment 
  ;; make a list of recursive definitions:
  LDC ()
  LDF f1  CONS   ;; the first frame is still Ω, can't look up `f2`
  LDF f2  CONS
  ...
  LDF fn  CONS
  ;; the list of closures on the stack now

  LDF (letrec-names letrec-body)
;; RAP takes the list of recursive closures and makes a new frame 
;; using `letrec-names`, then modifies the frame Ω physically, replacing
;; dummy pointer there with the pointer to the initialized frame with 
;; bindings for fi to `letrec-names` and calls AP for `letrec-body`:
RAP

DUM and RAP semantics:

  • (s, e, DUM.c, d) => (s, Ω.e, c, d)
  • (((args body).(Ω.e')).closures.s, Ω.e, RAP.c, d)
    => ((), set-car!(Ω.e', new-frame(args, closures)).e', body, s.e.c.d)

Each from f1, f2,…,fn still holds a pointer to environment Ω.e'. Now RAP takes a list of closures, makes a new frame from it using letrec-names, and destructively replaces a dummy frame in Ω, thus making all fi visible to all of the closures. After RAP f2 can look up e.g. f4 by name assigned to it in letrec-names and vice versa.

Once you have understood this trick, let’s look at the auxiliary example of a recursive function, factorial implementation:

DUM
  LDC ()
  ;; factorial function:
  LDF ((n)
       (LDC 0  LD n  EQ  SEL    ;; n == 0?
         ;; then: load 1 and return
         (LDC 1  JOIN)
         ;; else: n * fact(n - 1)
         (;; prepare arguments for recursive call:
          LDC ()
          LDC 1  LD n  SUB  ;; n-1 on the stack
          CONS
          ;; call `factorial`:
          LD factorial   AP  ;; fact(n - 1) on the stack,
          LD n   MUL
          JOIN)  ;; end of `else` branch
        RTN))
  CONS
  ;; now list (<factorial-definition>) is on the stack
  ;; trigger:
  LDF ((factorial)
       (LDC (6)
        LD factorial AP
        RTN))
;; push the trigger!
RAP
;; bang, 720 on the stack
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s