# 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.