CS 37

Clab 28: The Meta-circular evaluator III

We will continue to follow SICP's design (using abstraction barriers, etc.) to build a small Scheme evaluator bottom-up.

Last clab we considered multi-frame environments. We represented an environment as a list of frames and we modified lookup-variable-value to lookup the value of a variable in an environment (potentially multi-level) rather than in a simple frame. We also introduced abstract helping functions: enclosing-environment, first-frame, extend-environment, add-binding-to-frame!. We noted that since our driver-loop and mini-eval used abstraction barriers (like lookup-variable-value), we could test our multi-level version by making the-global-environment a multilevel one and running (driver-loop). We ended by defining set-variable-value! which will allow us to mutate a variable that is already defined in the environment. If you got this far and your code works, use it. Otherwise you can download my code from: /home/cfk/pub/cs37/week9/clab27c.scm and use it.

I moved the construction of my-sicp-frame, funframe, newframe, 2levenv, and 3levenv to the definitions window so that you can use them without having to retype.

Just to be sure we are all together, let's check this out using our driver loop with 3levenv as the-global environment.

> (define the-global-environment 3levenv) > the-global-environment (((k y) isover 2) ((Williams Amherst Swarthmore Middlebury cat) 3 2 1 4 4) ((x cat p) 17 10 3)) > (driver-loop) MC-EVAL==> k isover MC-EVAL==> y 2 MC-EVAL==> dog . in lookup-variable-value--Unbound variable dog > (driver-loop) MC-EVAL==> cat 4 MC-EVAL==> x 17 MC-EVAL==> cat 4 MC-EVAL==> p 3 MC-EVAL==> (quit) "exiting-mini-eval" Note that the value of cat returned was that in the most recently added frame of the environment.

In addition to set!, we will also want to be able to define new variables, so look at define-variable! from p. 380 and below.

(define (define-variable! var val env) (let ((frame (first-frame env))) (define (scan vars vals) (cond ((null? vars) (add-binding-to-frame! var val frame)) ((eq? var (car vars)) (set-car! vals val)) (else (scan (cdr vars) (cdr vals))))) (scan (frame-variables frame) (frame-values frame)))) Note that define-variable! looks very much like our old version of lookup-variable-value (works in one frame) while set-variable-value! looks more like our new version of lookup-variable-value (might look through several frames in an environment). Make sure you understand how they work, how they are different, and why they are different. Then test them out. For example: > 3levenv (((k y) isover 2) ((Williams Amherst Swarthmore Middlebury cat) 3 2 1 4 4) ((x cat p) 17 10 3)) > (set-variable-value! 'y 56 3levenv) > 3levenv (((k y) isover 56) ((Williams Amherst Swarthmore Middlebury cat) 3 2 1 4 4) ((x cat p) 17 10 3)) > (set-variable-value! 'Amherst 'behindSwat 3levenv) > 3levenv (((k y) isover 56) ((Williams Amherst Swarthmore Middlebury cat) 3 behindSwat 1 4 4) ((x cat p) 17 10 3)) > (set-variable-value! 'z 200 3levenv) . Unbound variable -- SET! z > (define-variable! 'z 200 3levenv) > 3levenv (((z k y) 200 isover 56) ((Williams Amherst Swarthmore Middlebury cat) 3 behindSwat 1 4 4) ((x cat p) 17 10 3)) > (define-variable! 'cat 'meow 3levenv) > 3levenv (((cat z k y) meow 200 isover 56) ((Williams Amherst Swarthmore Middlebury cat) 3 behindSwat 1 4 4) ((x cat p) 17 10 3)) > (define-variable! 'k 9 3levenv) > 3levenv (((cat z k y) meow 200 9 56) ((Williams Amherst Swarthmore Middlebury cat) 3 behindSwat 1 4 4) ((x cat p) 17 10 3)) Note that define-variable! only affects the first (most recent) frame in an environment, while set-variable-value! can go deeper. But set-variable-value! must find the variable already existing while define-variable! will define the variable if it is not already in the first frame.

Here is our mini-evaluator so far:

(define (mini-eval exp env) (cond ((quoted? exp) (text-of-quotation exp)) ((variable? exp) (lookup-variable-value exp env)) (else (error "unknown expression--mini-eval" exp)))) It can recognize a quoted expression and a simple variable name; nothing else.

We now have the tools to handle a user definition. To make our interpreter handle a user definition, it must recognize an expression that is a user definition and be able to get at its parts. For example, if a user types: (define x cat) , we must recognize

  1. that this is a definition,
  2. that the variable to be defined is x and
  3. that the value to assign to x is the value of cat in the current environment.
If this were the only kind of definition we had to deal with we could
  1. recognize that an expression exp is a definition if (car exp) is equal to 'define. We could
  2. get the variable to be defined by (cadr exp) and we could
  3. get the value by (mini-eval (caddr exp) env).
Although we will not deal with function definitions today, we will soon have to deal with definitions that look like
(define (f y) someBody). Here, 2, the identifier to be defined is (caadr exp). We will make our selectors general enough to handle either case although we will work only with the first case (variable definition) today.

Define, think about, and test: tagged-list?, definition?, definition-variable, and definition-value.

(define (tagged-list? exp tag) (if (pair? exp) (eq? (car exp) tag) #f)) (define (definition? exp) (tagged-list? exp 'define)) (define (definition-variable exp) (if (symbol? (cadr exp)) (cadr exp) (caadr exp))) (define (definition-value exp) (if (symbol? (cadr exp)) (caddr exp) ;;; (make-lambda (cdadr exp) worry about later ;;; (cddr exp)) )) (define def1 '(define x 43)) Let's check them out: > def1 (define x 43) > (definition? def1) #t > (definition? '(this is a test)) #f > (definition-variable def1) x > (definition-value def1) 43 > (define funct1 '(define (sqr x) (* x x ))) > funct1 (define (sqr x) (* x x)) > (definition? funct1) #t > (definition-variable funct1) sqr Note that definition-variable works for both (define x ... and (define (f ...
But we'll put off dealing with function definitions for a bit.

With these selectors and define-variable!, we can write a procedure that will carry out a definition of the first sort, given an expression that is such a definition. Define and think about:

;;;the parameter exp is assumed to be a valid scheme ;;;definition. the parameter env is a valid environment. ;;;eval-definition evaluates the definition value in ;;;env and effects the definition in the environment ;;;env. (define (eval-definition exp env) ... Your definition evaluator should work as follows: > (define def2 '(define x cat)) > def2 (define x cat) > 3levenv (((k y) isover 2) ((Williams Amherst Swarthmore Middlebury cat) 3 2 1 4 4) ((x cat p) 17 10 3)) > (eval-definition def2 3levenv) ok > 3levenv (((x k y) 4 isover 2) ((Williams Amherst Swarthmore Middlebury cat) 3 2 1 4 4) ((x cat p) 17 10 3)) > Note that cat was correctly evaluated to 4 in 3levenv and then the variable x was defined in the first frame of 3levenv.
We will now add user-definitions to our interpreter. To do this, we just need to modify our evaluator to test whether the input expression is a definition and if it is a definition to pass it to eval-definition.
This requires one additional line to our conditional (shown below). Redefine mini-eval by adding ((definition? exp) (eval-definition exp env)) to the conditional in mini-eval. Let's test our slightly more powerful interpreter: > (define the-global-environment 2levenv) > the-global-environment (((Williams Amherst Swarthmore Middlebury cat) 3 2 1 4 4) ((x cat p) 17 10 3)) > (driver-loop) MC-EVAL==> Amherst 2 MC-EVAL==> cat 4 MC-EVAL==> x 17 MC-EVAL==> (define p (quote 40)) ok MC-EVAL==> p 40 MC-EVAL==> (quit) "exiting-mini-eval" > the-global-environment (((p Williams Amherst Swarthmore Middlebury cat) 40 3 2 1 4 4) ((x cat p) 17 10 3)) > Back in drscheme, we can see that the global environment really changed.

Well, we are making progress. But the only thing that we can use as values are things which are already defined (in the-global-environment) or quoted expressions. We can't even use ordinary numbers. Now, we could add bindings like ((1 2 3). (1 2 3 )) etc. to the-global-environment but this gets rather tedious. Furthermore, later we want to use Drscheme's underlying numerical operators so we need Drscheme's numbers. So we'll just steal them. While we are at it, we'll steal strings also. We can think of these as primitive units being supplied by the underlying hardware. We will make our evaluator recognize numbers and strings as things to be passed through to Drscheme for evaluation instead of using our own mini-eval. We'll do this by defining a predicate self-evaluating? that returns #t if an expression should just be passed through to Drscheme for evaluation. Then we will add another case to the cond in mini-eval that will recognize self-evaluating expressions. If the action taken is just exp, then exp will be evaluated by Drscheme's eval. If we want our evaluator to evaluate an expression, we invoke one of our own evaluators like: mini-eval, lookup-variable-value , or eval-definition. So define self-evaluating? and re-define mini-eval as follows:

(define (self-evaluating? exp) (cond ((number? exp) #t) ((string? exp) #t) ((eq? exp #t) #t) ;; added to handle #truth ((eq? exp #f) #t) ;; as used in drscheme (else #f))) ;;; a really mini eval. evaluates quoted expressions, defines, ;;; simple variables, numbers, and strings. The expression is ;;; parameter exp and the frame is parameter env. (define (mini-eval exp env) (cond ((self-evaluating? exp) exp) ((quoted? exp) (text-of-quotation exp)) ((variable? exp) (lookup-variable-value exp env)) ((definition? exp) (eval-definition exp env)) (else (error "unknown expression--mini-eval" exp)))) Now we can do a quick test: > the-global-environment (((k y) isover 2) ((Williams Amherst Swarthmore Middlebury cat) 3 2 1 4 4) ((x cat p) 17 10 3)) > (driver-loop) MC-EVAL==> x 17 MC-EVAL==> (define y 3) ok MC-EVAL==> y 3 MC-EVAL==> (quit) "exiting-mini-eval" > A more interesting test is to start with an empty environment: > (define the-global-environment (list (list '()))) > the-global-environment ((())) > (driver-loop) MC-EVAL==> (define x 17) ok MC-EVAL==> (define cat 2000) ok MC-EVAL==> x 17 MC-EVAL==> cat 2000 MC-EVAL==> (define alis (quote (dog horse 4))) ok MC-EVAL==> alis (dog horse 4) MC-EVAL==> (quit) "exiting-mini-eval" > the-global-environment (((alis cat x) (dog horse 4) 2000 17)) So we can now start our interpreter with an environment that consists of one empty frame and the user can put stuff into it and get stuff out of it.

It is now time for you to test and exercise your understanding of all this by giving our interpreter the ability to handle set!.
This is similar to handling define but slightly different. (define x exp) will evaluate exp in the current environment to get some value (call it val). If x is defined in the first frame of the current environment then define will change the definition of x to val. If x is not defined in the first frame of the current environment then define will add a binding of x to val in the first frame. Contrast the above with the following: (set! x exp) will evaluate exp in the current environment to get some value (call it val). If x is defined in any frame of the current environment then set! will change the definition of x to val in the first frame where x is defined. If x is not defined in the current environment our set! will generate an error. You have actually done almost all the work for this.

You should be able to get results like:

> the-global-environment (((k y) isover 2) ((Williams Amherst Swarthmore Middlebury cat) 3 2 1 4 4) ((x cat p) 17 10 3)) > (driver-loop) MC-EVAL==> x 17 MC-EVAL==> (set! x 25) ok MC-EVAL==> x 25 MC-EVAL==> (define z '(a b c)) ok MC-EVAL==> z (a b c) MC-EVAL==> (set! cat '(not 4 anymore)) ok MC-EVAL==> (set! y 1776) ok MC-EVAL==> x 25 MC-EVAL==> cat (not 4 anymore) MC-EVAL==> y 1776 MC-EVAL==> (quit) "exiting-mini-eval" > the-global-environment (((z k y) (a b c) isover 1776) ((Williams Amherst Swarthmore Middlebury cat) 3 2 1 4 (not 4 anymore)) ((x cat p) 25 10 3)) Checking the values inside our driver-loop gives us some hope that set! is working. Checking the changes in the-global-environment outside of mini-eval gives us considerably more confidence. We can see that set! can correctly make changes at all three levels of this environment.