SECD Machine

The CONS, CDR, CAR instructions behave as we would hope and expect:

CONS

(a b . s) e (CONS . c) d becomes ((a . b) . s) e c d

CAR

((a . b) . s) e (CAR . c) d becomes (a . s) e c d

CDR

((a . b) . s) e (CDR . c) d becomes (b . s) e c d

The ATOM predicate tests if the top item in s is an atomic datum or not.

ATOM

(a . s) e (ATOM . c) d becomes (t . s) e c d where t=T if a is in fact an atom, t=F if a is a list.

The arithmetic operations applied to the top 2 items of the stack, but do not modify the other registers:

• ADD takes (a b . s) and produces (b + a . s)
• SUB takes (a b . s) and produces (b - a . s)
• MUL takes (a b . s) and produces (b * a . s)
• DIV takes (a b . s) and produces (b / a . s)
• REM takes (a b . s) and produces (b % a . s)
• LEQ takes (a b . s) and produces (b <= a . s)
• EQ takes (a b . s) and produces (b = a . s)

LD

s e (LD i . c) d becomes (x . s) e c d where x = locate(i, e) is the current value for the index i, and locate() is a function in the meta-language

LDC

s e (LDC n . c) d becomes (n . s) e c d

LDF

s e (LDF c' . c) d becomes ((c' . e) . s) e c d where the closure is (c' . e).

The pseudocode for the locate() function requires first introducing a function which returns the nth member of a list (zero-indexed):

index :: Int -> List -> a
index 0 s = car(s)
index n s = if n < 0 then error "Must have non-negative index number"
            else index (n - 1) cdr(s)

We use this to define a function which determines, for an index pair i = (b . n) the corresponding value in the environment:

locate :: (Int, Int) -> Env -> a
locate (b, n) e = index n (index b e)

There are two instructions for conditional forms, namely SEL selects a sublist of the control based on the value at the top of the stack, and JOIN rejoins the main control. We could then expect the control to look like

(... SEL c_TRUE c_FALSE c)

where both c_TRUE and c_FALSE look like a list whose last element is JOIN, i.e., c_T = (... JOIN).

SEL

(x . s) e (SEL c_T c_F . c) d becomes s e c_X (c . d) where c_X is c_T if x = T, and c_X is c_F if x = F

JOIN

s e (JOIN) (c . d) evaluates to s e c d

So SEL is a jump instruction, JOIN jumps back to the function caller.

We need to bear in mind how we encode closures, because they govern how we implement AP, RTN, etc. A closure is just (c . e) a pair of instructions plus an environment for it.

AP

((c' . e') v . s) e (AP .c) d evaluates to NIL (v . e') c' (s e c . d) a state with:

1. a fresh NIL stack,
2. a new environment (v . e'),
3. the instructions to execute c' given by the function body, and
4. the saved state at the time of function call (s e c . d)

RTN

(x) e' (RTN) (s e c . d) becomes (x . s) e c d, it restores the previous state of the e, c, d registers, and pushes x to the top of the previous s register-state.

DUM

creating a new environment with PENDING as the first sublist, transforms s e (DUM . c) d into s (PENDING . e) c d.

RAP

recursively apply, ((c' . e') v . s) (PENDING . e) (RAP . c) d becomes NIL rplaca(e', v) c' (s e c . d) where rplaca is a function in the metalanguage (compare to AP which instead had (v . e') directly)

The recursive aspect of RAP is due to rplaca which amounts to be a (setf (car e') v) (thus replacing the PENDING dummy metasymbol introduced by DUM). The mnemonic really is rplaca(x,y) "replace car of x by y and return pointer to x".

Remember when we noted e is basically a stack of lists, and data stored in the e environment is given a unique identifier (x, y) ? In a typical function call with AP, a new list is pushed onto e. Any local variables now look like (len(e), y). This len(e) is problematic for recursive functions, because the stack grows with each recursive function call.

That's why RAP, instead of pushing a new list onto the environment stack, simply replaces whatever is at the head of e with a new environment list.