We can easily improve the little interpreter in lots of ways. [ We should put the code in a file minieval.scm so people can experiment with it. Need to debug it first, of course. It's changed since the one I've used in class. ]
First, we can add a toplevel binding environment, so we can
have some variables. (Local variables will be discussed in
the next chapter.) To make them useful, we need some special
define and (while we're at it)
We can also add a few more data types; for now, we'll just add booleans.
Here's what our new main dispatch routine looks like:
(define (eval expr) (cond ;; variable reference ((symbol? expr) (eval-variable expr)) ;; combination OR special form ((pair? expr) (eval-list expr)) ;; any kind of self-evaluating object ((self-evaluating? expr) expr) (else (error "Illegal expression: " expr))))
Since we're adding variables to our interpreter, symbols can be
expressions by themselves now--references to top-level variable bindings.
We've added a branch to our
cond to handle that, and a helper
eval-variable. (We'll discuss how the variable lookup
is done shortly.)
We need to recognize two kinds of self-evaluating types now (and may
add more later), so we come up with a procedure
that covers both cases and can easily be extended.
(define (self-evaluating? expr) (or (number? expr) (boolean? expr)))
We also need to recognize two basic types of compound expressions:
combinations and special forms. These (and only these) are represented
as lists, so we can use
pair? as a test, and dispatch to
(What we're really doing here is checking to see whether we're evaluating a parenthesized expression. Since parenthesized expressions are read in as lists, we can just check to see whether the s-expression is a list.)
Here's the code for
eval-list, which just checks to see whether
a compound expression is a special form. It dispatches to
eval-special-form if it is, or to
eval-combo if it's not.
(define (eval-list expr) (if (and (symbol? (car expr)) (special-form-name? (car expr))) (eval-special-form expr) (eval-combo)))
We could use a
cond to check whether symbols are special form
names, but using
member on a literal list is clearer and easily
extensible--you can just add names to the list.
(define (special-form-name? expr) (member '(if define set!)))
eval-special-form just dispatches again, calling a routine
that handles whatever kind of special form it's faced with.
(Later, we'll see prettier ways of doing this kind of dispatching,
using first-class procedures.) From here, we've done most of the
analysis, and are dispatching to little procedures that actually
do the work.
[ need to come back to this after discussing backquote--this would make a good example ]
(define (eval-special-form expr) (let ((name (car expr))) (cond ((eq? name 'define) (eval-define expr)) ((eq? name 'set!) (eval-set! expr)) ((eq? name 'if) (eval-if expr)))))
Once the evaluator has recognized an
if expression, it calls
eval-if to do the work.
recursively, to evaluate the condition expression, and depending
on the result, calls it again to evaluate the "then" branch or
the "else" branch. (One slight complication is that we may
have a one-branch else, so
eval-if has to check to see if
the else branch is there. If not, it just returns
(define (eval-if expr) (let ((expr-length (length expr))) (if (eval (cadr expr)) (eval (caddr expr)) (if (= expr-length 4)) (eval (cadddr expr)) #f)))
[ note that what we're doing includes parsing... one-branch vs.
if. Should actually be doing more parsing,
checking syntax and signaling errors gracefully. E.g., should
check to see that
expr-length is a legal length. ]
[ Also note that we're snarfing booleans, and our
if behaves like
if... but we don't have to. We could put a different
if, e.g., only interpreting
#t as a
true value. ]
For a toplevel binding environment, we'll use an association list. (A more serious interpreter would probably use a hash table, but a association list will suffice to demonstrate the principles.)
We start by declaring a variable to hold our interpreter's environment, and initializing it with an empty list.
(define t-l-envt '())
To add bindings, we can define a routine to add an association to the association list.
(define (toplevel-bind! name value) (let ((bdg (assoc name t-l-envt))) ;; search for association of name ;; if binding already exists, put new value (in cadr) of association ;; else create a new association with given value (if bdg (set-car! (cdr bdg) value) (set! t-l-envt (cons (list name value) t-l-envt)))))
Recall that the elements of an association list are "associations," which are just lists whose first value is used as a key. We'll use the second element of the list as the actual storage for a variable.
For example, an environment containing just bindings of
bar with values
3 (respectively) would look
At the level of the little Scheme subset we're implementing, we'd draw this environment this way:
+-------+ [envt] t-l-envt | *---+------>+-------+ +-------+ foo | *---+---> 2 +-------+ bar | *---+---> 3 +-------+
This emphasizes the fact that these are variable bindings with values,
i.e., named storage locations. Notice that
t-l-envt is a variable
in the language we're using to implement our interpreter, but
bar are variables in the language the interpreter
If we want to show how it's implemented at the level of the Scheme we're writing our interpreter in, we can draw it more like this:
+-------+ t-l-envt | *---+---->+---+---+ +---+---+ +-------+ | * | *-+------------------>| * | * + +-|-+---+ +-+-+---+ | | +---+---+ +---+---+ +---+---+ +---+---+ | * | +-+-->| * | * | | * | *-+-->| * | * | +-|-+---+ +-|-+---+ +-|-+---+ +-+-+---+ | | | | foo 2 bar 3
Now we can add the four procedures we had in the math evaluator:
(toplevel-bind! '+ +) (toplevel-bind! '- -) (toplevel-bind! '* *) (toplevel-bind! '/ /)
Again, we're just snarfing procedures straight from the Scheme we're implementing our interpreter in. We put them in our binding environment under the same names.
Now we need accessor routines to get and set values of bindings
for variable lookups and
(define (toplevel-get name) (cadr (assoc name t-l-envt)))
(define (toplevel-set! name value) (set-car! (cdr (assoc name t-l-envt)) value))
[ of course, these really should have some error checking--give examples that signal unbound variable errors? ]
Given this machinery, we can now write
(Recall that when
eval encounters an expression that's
just a symbol, it interprets it as a reference to a variable
(define (eval-variable symbol) (toplevel-get symbol))
We can also define
eval-set!. All they do is
extract a variable name from the
and create binding for that name or update its value.
eval-set! are called
eval-special-form to interpret expressions of the
(define ...) or
(set! ...), respectively.)
(define (eval-define! expr) (toplevel-bind! (cadr expr) (eval (caddr expr))))
(define (eval-set! expr) (toplevel-set! (cadr expr) (eval (caddr expr))))
[ need some example uses ]