CS 22
Clab 29: The Meta-circular evaluator II
Last clab, we built a mini-micro Scheme interpreter using a
single-frame golbal environment with bindings implemented by
dotted pairs.
We chose to represent a binding as a dotted pair and a frame as a list
of bindings. This is attractive and we could proceed with this kind
of binding. SICP chooses to represent a frame as a pair of lists.
The car of the frame is a list of the variable names; the cdr of the
frame is a list of the corresponding values.
So the frame we were working with
<![CDATA[
((x . 17) (cat . 10) (p . 3))
]]>
would be represented by SICP as
<![CDATA[
((x cat p) . (17 10 3))
]]>
but it will be printed by drscheme as
<![CDATA[
((x cat p) 17 10 3)
]]>
This is an artifact of the standard scheme printing. If you draw box
and pointer diagrams you will see why.
Let's modify our stuff so that we have a mini-micro Scheme interpreter
for frames represented the sicp way.
Start a new file for the SICP style frames.
We need a lookup-variable-value function for the sicp way of representing
a frame. It will be useful to have some procedures with mnemonic
names here, so
before you define lookup-variable-value, define the following for the
SICP kind of frame.
<![CDATA[
;;; 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)
....
;;; given an SICP style frame (the parameter frame),
;;; frame-variables returns a list of the variable names
;;; in the frame
(define (frame-variables frame) ....
;;; given an SICP style frame (the parameter frame),
;;; frame-values returns a list of the values
;;; in the frame
(define (frame-values frame) ....
]]>
These should behave as follows:
<![CDATA[
> (define my-sicp-frame
(make-frame '(x cat p) '(17 10 3)))
> my-sicp-frame
((x cat p) 17 10 3)
> (frame-variables my-sicp-frame)
(x cat p)
> (frame-values my-sicp-frame)
(17 10 3)
]]>
Now define
<![CDATA[
;;;returns the value of variable var in frame
(define (lookup-variable-value var frame)
...
]]>
It should behave as follows:
<![CDATA[
> my-sicp-frame
((x cat p) 17 10 3)
> (lookup-variable-value 'x my-sicp-frame)
17
> (lookup-variable-value 'cat my-sicp-frame)
10
]]>
Here is our old mini-eval, driver-loop, and a couple of helping
procedures from last clab.
<![CDATA[
(define atom? (lambda (x)
(not (pair? x))))
;;;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)))))
]]>
Copy in our old mini-eval and driver-loop and ehlping functions.
Make the global environment my-sicp-frame and run driver-loop. You
should have the same sort of micro world we had before but now with
the SICP style frame.
Here is a sample run:
<![CDATA[
> my-sicp-frame
((x cat p) 17 10 3)
> (driver-loop)
MC-EVAL==> p
3
MC-EVAL==> (quote (my name is harry potter))
(my name is harry potter)
MC-EVAL==> x
17
MC-EVAL==> zoo
. Unbound variable zoo
]]>
In case you didn't complete this, here is possible code for managing
bindings the SICP way:
<![CDATA[
(define the-empty-environment '())
;;; 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))
;;;just a frame to test things with
(define my-sicp-frame
(make-frame '(x cat p) '(17 10 3)))
;;;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))))
;;;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)))))
]]>
Note how the scan helper function in lookup-variable-value
works. In particular, scan assumes that a frame is well-formed
(i.e. a dotted pair of two equal-length lists).
What we have here is a mini-micro Scheme interpreter. Once the user
types (driver-loop), he is in our world. Our interpreter evaluates
whatever expressions are typed by the user until the user quits (or
bombs out by typing something our interpreter cannot handle). We have
a lot of work to do to turn this into a reasonable interpreter, but
this is a start. Make sure you understand how this little interpreter
works and ask for help if you need it.
In order to have a really functional interpreter, we need to add a
lot. Users should be able to define their own variables and give them
values. We should provide some primitive operations that users can
use. Users should be able to define their own functions and invoke
them.
Here is the sicp eval function.
<![CDATA[
(define (eval exp env)
(cond ((self-evaluating? exp) exp)
((variable? exp) (lookup-variable-value exp env))
((quoted? exp) (text-of-quotation exp))
((assignment? exp) (eval-assignment exp env))
((definition? exp) (eval-definition exp env))
((if? exp) (eval-if exp env))
((lambda? exp)
(make-procedure (lambda-parameters exp)
(lambda-body exp)
env))
((begin? exp)
(eval-sequence (begin-actions exp) env))
((cond? exp) (eval (cond->if exp) env))
((application? exp)
(apply (eval (operator exp) env)
(list-of-values (operands exp) env)))
(else
(error "Unknown expression type -- EVAL" exp))))
]]>
I'll say a couple of words about this and then we will go on
in a bottom-up fashion, making small changes, running our code,
and getting lots of CS highs.
We will begin by working on the environment handling functions so that
users can define their own variables inside our interpreter. Since we
know that eventually we will want to work with environments that
consist of more than one frame, we will define environment functions
that allow for such complex environments.
We can represent an
environment as a list of frames.
Of course it is up to us to handle things correctly. If we have an
environment that looks like the list (frame1 frame2 frame3), we will
understand this to be an environemt that we would draw in an
environment diagram as frame1 in a box with an arrow from frame 1 to a
box with frame2 in it and an arrow from the frame 2 box to a box
frame3 in it. Usually we would draw frame3 on the top although it is
the direction of the arrows that is important.
Let's keep our good old my-sicp-frame and add another say:
<![CDATA[
(define funframe
(make-frame
'(buchanan nader cat bush gore)
'((name too long) lost 56 maybeb maybeg)))
]]>
which will look like:
<![CDATA[
((buchanan nader cat bush gore) (name too long) lost 56 maybeb maybeg)
]]>
We can define a simple two level environment that would be illustrated by an
arrow from funframe to my-sicp-frame by evaluating:
<![CDATA[
(define 2levenv (list funframe my-sicp-frame))
]]>
Now define the following environment procedures thinking about what they do
and testing them as you go along:
<![CDATA[
(define (enclosing-environment env) (cdr env))
(define (first-frame env) (car env))
(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))))
]]>
Let's use these to construct a new frame, newframe and
a 3 level environment that that extends 2levenv by newframe.
<![CDATA[
> (define newframe (list '()))
> newframe
(())
> (add-binding-to-frame! 'y 2 newframe)
> newframe
((y) 2)
> (add-binding-to-frame! 'k 'isover newframe)
> newframe
((k y) isover 2)
> (define 3levenv
(extend-environment
(frame-variables newframe)
(frame-values newframe)
2levenv))
> 3levenv
(((k y) isover 2)
((buchanan nader cat bush gore) (name too long) lost 56 maybeb maybeg)
((x cat p) 17 10 3))
]]>
For testing, move this construction to the definitions window so that
you can use my-sicp-frame, funframe, newframe, 2levenv, and
3levenv without having to retype.
Suppose we try to look up the value of variable k in 3levenv.
We get:
<![CDATA[
> (lookup-variable-value 'k (first-frame 3levenv))
isover
]]>
We got the right answer but there is a problem here.
Try:
<![CDATA[
> (lookup-variable-value 'k 3levenv)
cdr: expects argument of type <pair>; given ()
]]>
We got an error on because 3levenv is an environment,
not a frame and we wrote lookup-variable-value assuming the
second parameter was a frame. We can get around this by manually
picking frames from an environment as above. The problem is
that, once complicated recursions are allowed, we won't usually
know how many frames are in an environment. So we need to redefine
lookup-variable-value to work in a multi-frame environment. SICP
does this on page 379.
<![CDATA[
(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))
]]>
Study this definition for a few minutes,
making sure you understand how it works. Then replace your old
single-frame version with this one in your
definitions window and test it for variables in different levels
of 3levenv.
<![CDATA[
> 3levenv
(((k y) isover 2)
((buchanan nader cat bush gore) (name too long) lost 56 maybeb maybeg)
((x cat p) 17 10 3))
> (lookup-variable-value 'k 3levenv)
isover
> (lookup-variable-value 'gore 3levenv)
maybeg
> (lookup-variable-value 'p 3levenv)
3
]]>
A less direct but easier way to check it out is to use our
driver loop with 3levenv as the-global environment.
<![CDATA[
> (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. This is as it
should be.