SICP - Explicit-control Evaluator

This lecture looks at implementing the LISP meta-circular evaluator as a register machine.  Very interesting to see the process actually play itself out and how this looks to the hardware.




Note Dump:

Explicit-control evaluator

OMG Abelson is wearing a wizard hat lol!

So we are talking about building languages:

Escher Pictures
Digital Logic
Query language

Even though these were toy examples, they are the core of really interesting things.

Escher language extended to designing circuit boards
Digital logic extended into electronic circuit simulator
Query language is basically the language of ProLog

LISP is not good at solving problems, it is good at creating languages that solve problems.

LISP is based on the metacircular evaluator

So now we are going to make the magic all go away... looking at the register machine again.
Finite state controler
Data Paths
Register

When we implement LISP in hardware, everything becomes concrete.

To make LISP work, we just take the procedures that define the evaluator and translate them into a register machine.

The evaluator leaves some things undefined, like how information is stored for recursive procedures.

Parts of a LISP system:

USER: talks to the READER
READER: takes characters from the user and turns them into a list structure memory (pairs, pointers, etc). Characters are tranlated into memory pointers, which are seen by the evaluator.
EVAL: reads list structure. Has at it's dispossal a number of primitive operators. Answers sent to the PRINTER.
PRINTER: Translates list structure into characters and sends back to USER.

Register usage in evaluator machine
//registers hold a pointer to list structure memory
EXP - expression to be evaluated    \_ EVAL
ENV - evaluation environment        /
FUN - procedure to be applied       \_ APPLY
ARGL - list of evaluated arguments  /
CONTINUE - place to go to next
VAL - result of evaluation
UNEV - temporary register for expressions

Sample evaluator-machine operations
(assign val (fetch exp))

(branch
(conditional? (fetch exp))
ev-cond))

(assign exp (first-clause (fetch exp)))

(assign val
(lookup-variable-value (fetch exp)
                      (fetch env)))

Fixed and finite number of evaluations in the evaluator register machine.

The two big peices of the register machine corresponde to the EVAL and APPLY procedures in the meta-circular evaluator: EVAL-DISPATCH and APPLY-DISPATCH

These peices of the evaluator have contracts with the outside world:

Contract that eval-dispatch fulfills:
- The EXP register holds an expression to be evaluated
- The ENV register holds the environment in which the expression is to be evaluated
- The CONTINUE register holds a place to go to next
- The result will be left in the VAL register. Contents of all other registers may be destroyed

Contract that apply-dispatch fulfills:
- The ARGL register contains a list of the arguments
- The FUN resister contains a procedure to be applied
- The top of the STACK holds a place to go to next
- The result will be left in the VAL register. The STACK will be popped. Contents of all other registers may be destroyed

We're going to walk through an example, evaluating the expression 1 (literally just the number 1):

eval-dispatch
(branch (self-evaluating? (fetch exp))
       ev-self-eval)
(branch (variable? (fetch exp))
       ev-variable)

<... more special forms ...>

(branch (application? (fetch exp))
       ev-application)
(goto unknown-expression-error)

1 is self evaluating, so we go to ev-self-eval

ev-self-eval
(assign val (fetch exp))
(goto (fetch continue))

That was easy so we're going to do something harder. The ENV register holds a pointer to an environment E0, which contains the environment variables x=3 and y=4:

This time we branch to ev-variable:

ev-variable
(assign
val
(lookup-variable-value (fetch exp)))
(goto (fetch continue))

lookup-variable-value looks up a variable using the pointer found in ENV.

Now we're going to look at the expression (+ x y)

This is an appilcation, so we go to ev-application:

ev-application
(assign unev (operands (fetch exp)))
(assign exp (operator (fetch exp)))
(save continue)
(save env)
(save unev)
(assign continue eval-args)
(goto eval-dispatch)

The environment with the variables will be linked to the primatives environment (global environment)

We save the stuff we need to the stack, then recursively evaluate everything in the expression.

eval-args
(restore unev)
(restore env)
(assign fun (fetch val))
(save fun)
(assign argl '())
(goto eval-arg-loop)

eval-arg-loop moves expressions from unevaluated in UNEV to evaluated in the argument list.

eval-arg-loop
(save argl)
(assign
exp
(first-operand (fetch unev)))
(branch (last-operand? (fetch unev))
       eval-last-arg)
(save env)
(save unev)
(assign continue accumulate-arg)
(goto eval-dispatch)

accumulate-arg
(restore unev)
(restore env)
(restore argl)
(assign
argl
(cons (fetch val) (fetch argl)))
(assign
unev
(rest-operands (fetch unev)))
(goto eval-arg-loop)

Once we have evaluated X and placed it in the argument list ARGL, we evaluate Y which is the last argument. Because it is last we don't need to save the environment.

eval-last-arg
(assign continue accumulate-last-arg)
(goto eval-dispatch)

accumulate-last-arg
(restore argl)
(assign
argl
(cons (fetch val) (fetch argl)))
(restore fun)
(goto apply-dispatch)

Now we have a procedure (primitive plus <pp+>) and a list of arguments (4 3). Now we go to apply-dispatch:

apply-dispatch
(branch (primitive-proc? (fetch fun))
       primitive-apply)
(branch (compound-proc? (fetch fun))
       compound-apply)
(goto unknown-proc-type-error)

primitive-apply
(assign
val
(apply-primitive-proc (fetch fun)
                     (fetch argl)))
(restore continue)
(goto (fetch continue))

Sussman "I don't know how to add, I'm just an execution unit" lol. Abelson says he can't add either cause he's just the evaluator, so the female primative operator in the audience tells them the sum is 7 haha.

The reason we need recursion in the evaluator has nothing to do with the type of expressions being evaluated, but instead is because the evaluation process itself is recursive.

The evaluator has "reduced" the expression (+ x y) to the value 7 and there is nothing left on the stack.

Looks like Mullet got a haircut.

Now we're going to look at an eval-apply loop (compound procedure):

(DEFINE (F A B)
(+ A B))

Now we'll evaluate (F X Y)

We'll end up with a binding in our environment where F is a procedure with arguments (A B) and a body of (+ A B). When we hit apply-dispatch, instead of going to primative-apply we go to compound-apply:

compound-apply
(assign
exp
(procedure-body (fetch fun)))
(assign
env
(make-bindings (fetch fun)
              (fetch argl)))
(restore continue)
(goto eval-dispatch)

We reduce down the expression to basically the same primative expression we just looked at.

Looking at iterative factorial, each iteration is a reduction, i.e. there is nothing on the stack at the end of each iteration.

Now that we've looked at an iterative process we're going to look at a true recursive procedure.

(define (fact-rec n)
(if (= n 0)
1
(* n (fact-rec (- n 1)))))

Look at the substitution model for (FACT-REC 5)
(FACT-REC 5)
(* 5 (FACT-REC 4))
(* 5 (* 4 (FACT-REC 3)))
(* 5 (* 4 (* 3)..... and so on))

The procedure is reduced by eval down to (* n (fact-rec (- n 1))) where we are calling apply-dispatch with the following registers:

EXP: *
ENV: E1
CONTINUE: eval-args

STACK: (n (fact-rec (- n 1))) <UNEV>
       E1 <ENV>
       done <CONTINUE>

Each call to FACT-REC results in a new environment...
The arguments and operators are accumulated on the stack.

The evaluator earlier was oversimplified, there is actually a slightly different version that handles a sequense of expressions:

compound-apply
(assign
unev
(procedure-body (fetch fun)))
(assign
env
(make-bindings (fetch fun)
              (fetch argl)))
(goto eval-sequence)

eval-sequence
(assign exp (first-exp (fetch unev)))
(branch (last-exp? (fetch unev))
       last-exp)
(save unev)
(save env)
(assign continue eval-sequence-cont)
(goto eval-dispatch)

eval-sequence-cont
(restore env)
(restore unev)
(assign unev (rest-exps (fetch unev)))
(goto eval-sequence)

last-exp
(restore continue)
(goto eval-dispatch)

Show and tell with an on-chip LISP interpretter. 89,000 transistors

Tail recursion does not change time complexity, it just manages the stack better.