In Scheme, *lambda* expressions are evaluated, resulting in a **procedure**, known more widely in the Lisp world as a **closure**. The closure captures the environment that is in effect at *lambda* evaluation time. The environment is basically a table of variable bindings, and the first set of variables will be the ones represented by procedure argument names. The captured environment is used later to provide “lexical” scoping of variables.

The little evaluator is extended to pass along the current environment to all subexpressions, and a data structure for *lambda* procedures is created…

(set! proc-mark 'proc-mark)
(set! make-proc
(lambda (form env)
(cons proc-mark (cons env (cdr form)))
)
)
(set! ev
(lambda (x env)
(cond
( (eq? x #t) #t )
( (eq? x #f) #f )
( (eq? (first x) 'quote) (second x) )
( (eq? (first x) 'lambda) (make-proc x env) )
( (eq? (first x) 'car) (car (ev (second x) env)) )
( (eq? (first x) 'cdr) (cdr (ev (second x) env)) )
( (eq? (first x) 'cons) (cons (ev (second x) env) (ev (third x) env)) )
( (eq? (first x) 'eq?) (eq? (ev (second x) env) (ev (third x) env)) )
( (eq? (first x) 'exit) (exit) )
( #t '***undefined*** )
)
)
)
(set! eval
(lambda (x env)
(ev x env)
)
)

A procedure call is an elaborate affair: 1) the arguments must be evaluated, 2) the argument values must paired up with the “formal” arguments, 3) the pairings must be added somehow to the procedure environment, and 4) the body of the procedure must be evaluated.

We can, of course, use a recursive procedure to evaluate the procedure expression and the argument expressions. With *lambda* expressions evaluating to a procedure, this is a little cleaner than the original Lisp evaluator…

(set! evlist
(lambda (x env)
(cond
( (eq? x '()) '() )
( #t (cons (ev (car x) env) (evlist (cdr x) env)) )
)
)
)
(set! pcall
(lambda (x)
x
)
)
(set! ev
(lambda (x env)
(cond
( (eq? x #t) #t )
( (eq? x #f) #f )
( (eq? (first x) 'quote) (second x) )
( (eq? (first x) 'lambda) (make-proc x env) )
( (eq? (first x) 'car) (car (ev (second x) env)) )
( (eq? (first x) 'cdr) (cdr (ev (second x) env)) )
( (eq? (first x) 'cons) (cons (ev (second x) env) (ev (third x) env)) )
( (eq? (first x) 'eq?) (eq? (ev (second x) env) (ev (third x) env)) )
( (eq? (first x) 'exit) (exit) )
( #t (pcall (evlist x env)) )
)
)
)

We check to make sure we have a procedure object. If we have a procedure object, we can extract the list of formal arguments from it and pair them up with the argument values. Another recursive procedure to pair things up…

(set! pair
(lambda (x y)
(cond
( (eq? x '()) '() )
( #t (cons (cons (car x) (car y)) (pair (cdr x) (cdr y))) )
)
)
)
(set! pcall
(lambda (x)
(cond
( (eq? (first (car x)) proc-mark) (pair (third (car x)) (cdr x)) )
( #t '***undefined*** )
)
)
)

Next, the name-value pairs are used to create bindings in the procedure’s environment. For lexical scoping, the procedure’s captured environment is the procedure’s starting environment. For now, the environment is a singly linked list of *(name . value)* pairs. The list of name-value pairs are prepended to the environment. Yet another recursive procedure…

(set! append
(lambda (x y)
(cond
( (eq? x '()) y )
( #t (cons (car x) (append (cdr x) y)) )
)
)
)
(set! pcall
(lambda (x)
(cond
( (eq? (first (car x)) proc-mark) (append (pair (third (car x)) (cdr x)) (second (car x))) )
( #t '***undefined*** )
)
)
)

Arguments can be evaluated in any order. But to enforce the left-to-right evaluation of the procedure body’s expression sequence, we use the “eager” evaluation rule – the arguments must all be evaluated before the procedure body is evaluated. Scheme requires at least one expression in the body, so the no-expression case is treated as undefined…

(set! evseq
(lambda (x seq env)
(cond
( (eq? seq '()) x )
( #t (evseq (ev (car seq) env) (cdr seq) env) )
)
)
)
(set! pcall
(lambda (x)
(cond
(
(eq? (first (car x)) proc-mark)
(evseq
'***undefined***
(cdr(cdr(cdr (car x))))
(append (pair (third (car x)) (cdr x)) (second (car x)))
)
)
( #t '***undefined*** )
)
)
)

All that’s needed now is to look up the variable bindings. The linear search and the prepending of argument bindings provides hiding (or shadowing) of variables with the same name in an outer scope. Because *symbol?* was not defined in the base interpreter, an implementation detail of symbols is revealed. The *read* and *display* procedures were added for debugging…

(set! lookup
(lambda (v env)
(cond
( (eq? env '()) '***undefined*** )
( (eq? v (car (car env))) (cdr (car env)) )
( #t (lookup v (cdr env)) )
)
)
)
(set! symbol?
(lambda (x)
(eq? (car x) (car 'car))
)
)
(set! ev
(lambda (x env)
(cond
( (eq? x #t) #t )
( (eq? x #f) #f )
( (symbol? x) (lookup x env) )
( (eq? (first x) 'quote) (second x) )
( (eq? (first x) 'lambda) (make-proc x env) )
( (eq? (first x) 'car) (car (ev (second x) env)) )
( (eq? (first x) 'cdr) (cdr (ev (second x) env)) )
( (eq? (first x) 'cons) (cons (ev (second x) env) (ev (third x) env)) )
( (eq? (first x) 'eq?) (eq? (ev (second x) env) (ev (third x) env)) )
( (eq? (first x) 'read) (read) )
( (eq? (first x) 'display)(display (ev (second x) env)) )
( (eq? (first x) 'exit) (exit) )
( #t (pcall (evlist x env)) )
)
)
)

Next, conditional expressions.