So far, we have seen the magic of building new languages:

• Escher picture language (by Peter Henderson),

• digital logic language,

• query language.

Even though these have been toy examples, they are kernels for very useful things. All of them are based on LISP.

A lot of people ask: what particular problems is LISP good for solving for? The answer is LISP is not good for any particular problems. Wht LISP is good for is constructing within it the right language to solve the problems you want to solve.

What is LISP based on? Whilst examining the meta-circular evaluator, we saw that LISP is based on LISP. We saw, through a concoction of magic with Y combinators and fixed points, that LISP is the fixed point equation for those things that are defined in terms of themselves. We will now peek behind the magician's curtain by implementing LISP in terms of the architecture of the register machine.

Organisation of Register Machine

stack <—> data paths <—> finite-state controller

If we implement LISP in terms of a register machine, then everything ought to become, at this point, completely concrete. All the magic should go away.

To implement LISP in a register machine, use the same technique as in the previous lecture: hand-translate the procedures for the meta-circular evaluator to the register machine.

This will be our final most explicit model of LISP, having already covered the substitution model, the environment model and the meta-circular evaluator.

The meta-circular evaluator left unanswered how recursive procedures take space that grows, whereas some procedures which look syntactically recursive, do not take up that space. We justified it with the substitution model, but did not explain how the machine managed to achieve it. This will become extremely explicit.

We will cover eval today. Primitive operators have very little to do with LISP; reader and printer are rather complicated, but we will ignore them; list structure memory will be covered in the next lecture.

Register usage in evaluator machine

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)))

There are a fixed and finite number of operations in the register machine.

Let's quickly recap what eval and apply are.

eval

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((quoted? exp)
         (text-of-quotation exp))
        << ... more special forms .. >>
        ((application? exp)
         (apply
          (eval (operator exp) env)
          (list-of-values (operands exp)
                          env)))
        (else
         (error "Unknown expression."))))

apply

(define (apply proc args)
  (cond ((primitive-proc? proc)
         (primitive-apply proc args))
        ((compound-proc? proc)
         (eval-sequence
          (proc-body proc)
          (extend-environment
           (parameters proc)
           args
           (proc-environment proc))))
        (else
         (error "Unknown proc type"))))

We will have to capture this cycle in the register machine, by creating eval-dispatch and apply-dispatch.

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-dipatch fulfills

• The argl register contains a list of arguments.

• The fun register 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.

In the video, the following expressions are covered step-by-step:

1. 1

2. x

3. (+ x y)

in the environment e₀ where x = 3, y = 4.

As text isn't able to convey the information anywhere near as well as the video, please watch the video to glean how the above expressions are evaluated. Below is the code necessary to evaluate the three expressions above.

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)
ev-self-eval
  (assign val (fetch exp))
  (goto (fetch continue))
ev-variable
  (assign
   val
   (lookup-variable-value (fetch exp)))
  (goto (fetch continue))
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)
eval-args
  (restore unev)
  (restore env)
  (assign fun (fetch val))
  (save fun)
  (assign argl '())
  (goto eval-arg-loop)
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)
  (resetore argl)
  (assign
   argl
   (cons (fetch val) (fetch argl)))
  (assign
   unev
   (rest-operands (fetch unev)))
  (goto eval-arg-loop)
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)
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))

The reason that you need recursion in the evaluator is because the evaluation process, itself, is recursive.

We haven't yet seen an eval/apply loop. The following example will rectify this.

(define (f a b)
  (+ a b))
(f x y)

In the environment e₀ where x = 3, y = 4 and f = proc in envirnoment e₀ with args: a b and body: (+ a b).

This example is essentially the same as the previous example, apart from that we no longer deal with a primitive procedure, so a new environment will need to be manufactured at some point: e₁ where a = 3 and b = 4.

The evaluator will also have to be expanded.

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

Et voilà! The expression will be completely reduced with nothing left on the stack.

Let's see how the evaluator deals with two different kinds of procedures.

fact-iter

(define (fact-iter n)
  (define (iter product counter)
    (if (> counter)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

fact-rec

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

The evaluator is able to take procedures which look syntactically like recursive procedures, and execute some iteratively and some recursively. It achieves this by only saving what it needs later.

The above evaluator is only able to read one expression at a time. The more complete version, capable of dealing with multiple expressions in a sequence, is described below.

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
  (restore env) (restore unev)
  (assign unev (rest-exps (fetch env)))
  (goto-eval-sequence)
last-exp
  (restore continue)
  (goto eval-dispatch)