CS 22

Clab 30: 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). Here is the code we had (also at: /home/cfk/pub/cs22/week10/clab29.scm).

;;; make-frame constructs an SICP style frame from a list of ;;; variables (the parameter variables) and a list of values ;;; (the parameter values) (define (make-frame variables values) (cons variables values)) ;;; given an SICP style frame (the parameter frame), ;;; frame-variables returns a list of the variable names ;;; in the frame (define (frame-variables frame) (car frame)) ;;; given an SICP style frame (the parameter frame), ;;; frame-values returns a list of the values ;;; in the frame (define (frame-values frame) (cdr frame)) ;;;returns the value of variable var in frame ;(define (lookup-variable-value var frame) ; (define (scan vars vals) ; (cond ((null? vars) ; (error "Unbound variable" var)) ; ((eq? var (car vars)) ; (car vals)) ; (else (scan (cdr vars) (cdr vals))))) ; (scan (frame-variables frame) ; (frame-values frame))) (define atom? (lambda (x) (not (pair? x)))) (define my-sicp-frame (make-frame '(x cat p) '(17 10 3))) ;;;returns #t if exp is a quote expression; returns #f otherwise (define (quoted? exp) (if (atom? exp) #f (eq? (car exp) 'quote))) ;;; if exp is a quoted expression, returns its value (define (text-of-quotation exp) (cadr exp)) ;;; returns #t if exp is a simple variable name; returns #f otherwise (define (variable? exp) (symbol? exp)) ;;; a really mini-mini eval. evaluates quoted expressions and ;;; simple variables only in one frame. The expression is ;;; parameter exp and the frame is parameter env. (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)))) ;;; The driver loop reads an expression, evaluates it in the global ;;; environment, and prints the result. Note that the driver ;;; uses a prompt of "MC-EVAL==> " to help you avoid confusing typing to the ;;; metacircular evaluator with typing to the underlying SCHEME interpreter. ;;; (Also, we have called our evaluator procedures MINI-EVAL and MINI-APPLY ;;; to help you avoid confusing them with Scheme's EVAL and APPLY.) ;;; When/If your interaction with the evaluator bombs out in an error, ;;; you should restart it by calling DRIVER-LOOP again. ;;; make the global environment our little frame for now (define the-global-environment my-sicp-frame) (define (driver-loop) (newline) (display "MC-EVAL==> ") (let ((input (read))) (if (equal? input '(quit)) "exiting-mini-eval" (begin (display (mini-eval input ;;;;change display to user-print later the-global-environment)) (driver-loop))))) (define funframe (make-frame '(buchanan nader cat bush gore) '((name too long) lost 56 maybeb maybeg))) (define 2levenv (list funframe my-sicp-frame)) (define (enclosing-environment env) (cdr env)) (define (first-frame env) (car env)) (define the-empty-environment '()) (define (extend-environment vars vals base-env) (if (= (length vars) (length vals)) (cons (make-frame vars vals) base-env) (if (< (length vars) (length vals)) (error "Too many arguments supplied" vars vals) (error "Too few arguments supplied" vars vals)))) (define (add-binding-to-frame! var val frame) (set-car! frame (cons var (car frame))) (set-cdr! frame (cons val (cdr frame)))) (define newframe (list '())) (add-binding-to-frame! 'y 2 newframe) (add-binding-to-frame! 'k 'isover newframe) (define 3levenv (extend-environment (frame-variables newframe) (frame-values newframe) 2levenv)) (define (lookup-variable-value var env) (define (env-loop env) (define (scan vars vals) (cond ((null? vars) (env-loop (enclosing-environment env))) ((eq? var (car vars)) (car vals)) (else (scan (cdr vars) (cdr vals))))) (if (eq? env the-empty-environment) (error "Unbound variable" var) (let ((frame (first-frame env))) (scan (frame-variables frame) (frame-values frame))))) (env-loop env)) 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) ((buchanan nader cat bush gore) (name too long) lost 56 maybeb maybeg) ((x cat p) 17 10 3)) > (driver-loop) MC-EVAL==> k isover MC-EVAL==> y 2 MC-EVAL==> nadar Unbound variable nadar > (driver-loop) MC-EVAL==> nader lost MC-EVAL==> cat 56 MC-EVAL==> x 17 MC-EVAL==> cat 56 MC-EVAL==> p 3 Note that the value of cat returned was that in the most recently added frame of the environment.

We will also want to be able to set! existing variables and define new variables, so look at set-variable-value! and define-variable! on pp. 379 and 380 and below.

(define (set-variable-value! var val env) (define (env-loop env) (define (scan vars vals) (cond ((null? vars) (env-loop (enclosing-environment env))) ((eq? var (car vars)) (set-car! vals val)) (else (scan (cdr vars) (cdr vals))))) (if (eq? env the-empty-environment) (error "Unbound variable -- SET!" var) (let ((frame (first-frame env))) (scan (frame-variables frame) (frame-values frame))))) (env-loop env)) (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) ((buchanan nader cat bush gore) (name too long) lost 56 maybeb maybeg) ((x cat p) 17 10 3)) > (set-variable-value! 'y 56 3levenv) > 3levenv (((k y) isover 56) ((buchanan nader cat bush gore) (name too long) lost 56 maybeb maybeg) ((x cat p) 17 10 3)) > (set-variable-value! 'nader '2percent 3levenv) > 3levenv (((k y) isover 56) ((buchanan nader cat bush gore) (name too long) 2percent 56 maybeb maybeg) ((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) ((buchanan nader cat bush gore) (name too long) 2percent 56 maybeb maybeg) ((x cat p) 17 10 3)) > (define-variable! 'cat 'meow 3levenv) > 3levenv (((cat z k y) meow 200 isover 56) ((buchanan nader cat bush gore) (name too long) 2percent 56 maybeb maybeg) ((x cat p) 17 10 3)) > (define-variable! 'k 9 3levenv) > 3levenv (((cat z k y) meow 200 9 56) ((buchanan nader cat bush gore) (name too long) 2percent 56 maybeb maybeg) ((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 until next week.

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) ((buchanan nader cat bush gore) (name too long) lost 56 maybeb maybeg) ((x cat p) 17 10 3)) > (eval-definition def2 3levenv) ok > 3levenv (((x k y) 56 isover 2) ((buchanan nader cat bush gore) (name too long) lost 56 maybeb maybeg) ((x cat p) 17 10 3)) Note that cat was correctly evaluated to 56 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 (((buchanan nader cat bush gore) (name too long) lost 56 maybeb maybeg) ((x cat p) 17 10 3)) > (driver-loop) MC-EVAL==> nader lost MC-EVAL==> cat 56 MC-EVAL==> x 17 MC-EVAL==> (define y cat) ok MC-EVAL==> y 56 MC-EVAL==> (define p (quote 40)) ok MC-EVAL==> p 40 MC-EVAL==> (quit) "exiting-mini-eval" > the-global-environment (((p y buchanan nader cat bush gore) 40 56 (name too long) lost 56 maybeb maybeg) ((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 (((buchanan nader cat bush gore) (name too long) lost 56 maybeb maybeg) ((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 getting started on your homework.

Exercise: Give 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.