SICP 7b
Metacircular Evaluation II

Table of Contents

Metacircular interpreters are convenient for exploring language issues and excellent for exchanging ideas about language design.

1 Indefinite number of arguments

One potentially helpful feature to add to a language, is allowing procedures to take an indefinite number of arguments. 

(+ 3 5 7 5 3)

To add this feature, we require a syntactic specification to notate the additional arguments. 

(lambda (x . y)
  (map (lambda (u) (+ x u))
       y))

.: syntax for representing cons​es.

Note the syntactic difference between these three expressions. 

(lambda (x y z) ...)
(lambda (x . y) ...)
(lambda x x)

Note (lambda x x) is equivalent to list.

Now incorporate this feature into the interpreter. For this we need to change pair-up. 

(define pair-up
  (lambda (vars vals)
    (cond
     ((eq? vars '())
      (cond ((eq? vals '()) '())
            (else (error "too many arguments"))))
     ((symbol? vars)               ;new
      (cons (cons vars vals) '())) ;new
     ((eq? vals '()) (error "too few arguments"))
     (else
      (cons (cons (car vars)
                  (cdr vals))
            (pair-up (cdr vars)
                     (cdr vals)))))))

2 Dynamic binding of variables

Next, we will attempt a more substational variation: dynamic binding of variables. First, we'll observe why it may be useful to have. 

(define sum
  (lambda (term a next b)
    (cond ((> a b) 0)
          (else
           (+ (term a)
              (sum term
                   (next a)
                   next
                   b))))))
(define sum-powers
  (lambda (a b n)
    (sum (lambda (x) (expt x n))
         a
         1+
         b)))
(define product-powers
  (lambda (a b n)
   (product (lambda (x) (expt x n))
            a
            1+
            b)))

Notice that sum-powers and product-powers are essentially the same, which is a sure indicator something is awry. 

(define sum-powers
  (lambda (a b n)
    (sum nth-power a 1+ b)))
(define product-powers
  (lambda (a b n)
    (product nth-power a 1+ b)))
(define nth-power
  (lambda (x)
    (expt x n)))

Upon first glance, it appears this is preferable. However this is currently impossible, as n remains undefined.

Dynamic binding: a free variable in a procedure has its value defined in the chain of callers, rather than where the procedure is defined. 

(define eval
  (lambda (exp env)
    (cond ((number? exp) exp)
          ((symbol? exp) (lookup exp env))
          ((eq? (car exp) 'quote) (cadr exp))
          ((eq? (car exp) 'lambda) exp)   ;new
          ((eq? (car exp) 'cond)
           (evcond (cdr exp) env))
          (else (apply (eval (car exp) env)
                       (evlist (cdr exp) env)
                       env)))))           ;new

We no longer have to save the environment upon definition of the procedure so no closure is required. However, the environment is required upon the application of the procedure. 

(define apply
  (lambda (proc args env) ;new
    (cond
     ((primitive? proc)
      (apply-primop proc args))
     ((eq? (car proc) 'lambda)
      ;; proc = (LAMBDA bvis body)
      (eval (caddr proc) ;body
            (bind (cadr proc) ;bvis
                  args
                  env))) ;new
     (else error-unknown-procedure))))

The catch is that dynamic binding leads to a modularity crisis. For example, if next in sum were to be renamed n, then sum-powers would stop working. Dynamic binding removes the ability to have qualifiers.

So what would be the correct solution? How do we gain the power of dynamic binding within a lexical system? 

(define pgen
  (lambda (n)
    (lambda (x) (expt x n))))

(define sum-pairs
  (lambda (a b n)
    (sum (pgen n) a 1+ b)))
(define product-pairs
  (lambda (a b n)
    (product (pgen n) a 1+ b)))

3 Delayed parameters

Finally, we will add the ability to delay the calculation of parameters. 

(define (unless p c a)
  (cond ((not p) c)
        (else a)))

Without delayed parameters, the following code can't be run, as evaluating the arguments leads to an error. 

(unless (= 1 0) 2 (/ 1 0))

What we would like instead, is for the following procedure to be constructed. 

(cond ((not (= 1 0)) 2)
      (else (/ 1 0)))

To construct this, build a kluge. 

(define (unless p (name c) (name a))
  (cond ((not p) c)
        (else a)))

Adding support for delayed parameters requires a far more complicated modification of the interpreter compared to adding both of the previous features. 

(define eval
  (lambda (exp env)
    (cond ((number? exp) exp)
          ((symbol? exp) (lookup exp env))
          ((eq? (car exp) 'quote) (cadr exp))
          ((eq? (car exp) 'lambda)
           (list 'closure (cdr exp) env))
          ((eq? (car exp) 'cond)
           (evcond (cdr exp) env))
          (else
           (apply (undelay (eval (car exp) ;new
                                 env))
                  (cdr exp)
                  env)))))

(define apply
  (lambda (proc args env) ;new
    (cond
     ((primitive? proc)
      (apply-primop proc
                    (evlist ops env))) ;new
     ((eq? (car proc) 'closure)
      ;; proc = (CLOSURE (bvrs body) env
      (eval (cadadr proc)
            (bind (vnames (caadr proc)) ;new
                  (gevlist (caadr args) ;new
                           ops
                           env)
                  (caddr proc))))
     (else error-unknown-procedure))))

(define evlist
  (lambda (l env)
    (cond
     ((eq? l '()) '())
     (else
      (cons (undelay (eval (car l) env))
            (evlist (cdr l) env))))))

(define gevlist
  (lambda (vars exps env)
    (cond
     ((eq? exps '()) '())
     ((symbol? (car vars)) ;applicative
      (cons (eval (car exps) env)
            (gevlist (cdr vars)
                     (cdr exps)
                     env)))
     ((eq? (caar vars) 'name)
      (cons (make-delay (car exps) env)
            (gevlist (cdr vars)
                     (cdr exps)
                     env)))
     (else error-unknown-declaration))))

(define evcond
  (lambda (clauses env)
    (cond
     ((eq? clauses '()) '()) ;arbitrary
     ((eq? (caar clauses) 'else)
      (eval (cadar clauses) env))
     ((false? (undelay
               (eval (caar clauses)
                     env)))
      (vcond (cdr clauses) env))
     (else
      (eval (cadar clauses) env)))))

(define false?
  (lambda (x) (eq? x nil)))

(define make-delay
  (lambda (exp env)
    (cons 'thunk (cons exp env))))

(define (undelay v)
  (cond ((pair? v)
         (cond ((eq? (car v) 'thunk)
                (undelay
                 (eval (cadr v)
                       (cddr v))))
               (else v)))
        (else v)))

Thunk apparently is the sound of hitting a stack.

Christian Christiansen