CS 22
Clab 31: The Meta-circular evaluator IV
We will continue to follow SICP's design (using abstraction
barriers, etc.) to build a small Scheme evaluator bottom-up.
Last clab we added self-evaluating expressions (numbers and strings)
and define to our mini-evaluator. We also looked at set-variable-value!
which does the work of a set!
As homework you have added
assignment (set!) to your minievaluator. Here is my mini-evaluator
and its helping functions so far (also available at:
/home/cfk/pub/cs22/week11/sclab31.scm):
<![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))
(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 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)
((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))
(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 an sicp environment
(define the-global-environment the-empty-environment)
(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 (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))))
(define newframe (list '()))
(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))
(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))))
(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))
;;;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. It returns "ok"
(define (eval-definition exp env)
(define-variable! (definition-variable exp)
(mini-eval (definition-value exp) env)
env)
'ok)
(define (assignment? exp)
(tagged-list? exp 'set!))
(define (assignment-variable exp) (cadr exp))
(define (assignment-value exp) (caddr exp))
(define (eval-assignment exp env)
(set-variable-value! (assignment-variable exp)
(mini-eval (assignment-value exp) env)
env)
'ok)
;;;
;;; some frames and environments for testing purposes
;;;
(define my-sicp-frame
(make-frame '(x cat p) '(17 10 3)))
(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)))
(define funframe
(make-frame
'(buchanan nader cat bush gore)
'((name too long) lost 56 maybeb maybeg)))
(define 2levenv (list funframe my-sicp-frame))
(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 the-global-environment (list (list '())))
]]>
The heart of it is:
<![CDATA[
(define (mini-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))
(else (error "unknown expression--mini-eval" exp))))
]]>
Given an expression, exp, and an environment, env, mini-eval
sets up a case based analysis of exp. Once it recognizes what
kind of expression exp is, mini-eval farms out the work to an
appropriate function to carry out the task in environment env.
Here is a short test run starting with an empty environment:
<![CDATA[
> the-global-environment
((()))
> (driver-loop)
MC-EVAL==> (define x 17)
ok
MC-EVAL==> (define y '(a b c ))
ok
MC-EVAL==> x
17
MC-EVAL==> y
(a b c)
MC-EVAL==> (set! y 45)
ok
MC-EVAL==> y
45
MC-EVAL==> (quit)
"exiting-mini-eval"
]]>
Define and set! seem to be working. More tests starting with an
empty environment are appropriate but we will not take clab time
for them. While define should only affect the first frame in
an environment, set! should be able to find bindings in deeper
frames and change them. In order to test this, let's start with
the 3 level environment we played with last class and do some
set!s.:
<![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==> (set! cat '(not 56 anymore))
ok
MC-EVAL==> (set! x 2001)
ok
MC-EVAL==> (set! y 1776)
ok
MC-EVAL==> cat
(not 56 anymore)
MC-EVAL==> x
2001
MC-EVAL==> y
1776
MC-EVAL==> (quit)
"exiting-mini-eval"
> the-global-environment
(((k y) isover 1776)
((buchanan nader cat bush gore)
(name too long)
lost
(not 56 anymore)
maybeb
maybeg)
((x cat p) 2001 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.
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.
Our interpreter now lets users define their own variables and give
them values. Users can also assign values (mutate) to existing
variables. We will now add some primitive functions and the ability to
apply them.
Let us review what Scheme should do when it sees an expression like (
f x y ). It recognizes this expression as a function application
because it is a
pair ( i.e. f is consed with the list ( x y ) ) and it is not a special
form (like a define). To evaluate ( f x y), f is evaluated to
get a procedure object ( call it #[proc f] ) .
Then x and y are evaluated to get a list of values and then #[proc f]
is applied to the list of values.
Drscheme does not handle its functions exactly like this but what
Drscheme does is semantically equivalent to this. Recall that
standard scheme uses applicative order evaluation. That is arguments
are evaluated before the function is applied.
Observe the following:
<![CDATA[
Welcome to DrScheme, version 103p1.
Language: Graphical Full Scheme (MrEd) Custom.
> (define fun
(lambda (p q)
(list
(cons p p)
(cons q q))))
> (define x 'harry)
> (define y 'hermoine)
> fun
#<procedure:fun>
> x
harry
> y
hermoine
> (fun x y)
((harry . harry) (hermoine . hermoine))
>
]]>
Remember drscheme is running a read-eval-print loop. We
can do the eval and apply explicitly. Continue:
<![CDATA[
> (eval 'x (interaction-environment))
harry
> (eval 'y (interaction-environment))
hermoine
> (eval 'fun (interaction-environment))
#<procedure:fun>
> (apply
(eval 'fun (interaction-environment))
(list
(eval 'x (interaction-environment))
(eval 'y (interaction-environment))
))
((harry . harry) (hermoine . hermoine))
> (apply
(eval 'fun (interaction-environment))
(list
'x
'y
))
((x . x) (y . y))
>
]]>
Note that apply will NOT evaluate arguments for you. apply
expects to get the VALUE of arguments.
We will build some tools to take apart a function application
expression like (f x y) into its constituent pieces .
Define: application?, operator, operands, no-operands?, first-operand,
rest-operands.
<![CDATA[
(define (application? exp) (pair? exp))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))
(define (no-operands? ops) (null? ops))
(define (first-operand ops) (car ops))
(define (rest-operands ops) (cdr ops))
]]>
We can test these by executing the following sequence:
<![CDATA[
> (define myappl '(f x y))
> myappl
(f x y)
> (application? myappl)
#t
> (operator myappl)
f
> (operands myappl)
(x y)
> (first-operand (operands myappl))
x
> (rest-operands (operands myappl))
(y)
]]>
Apply applies the function it is given to a list of values. That
is, apply assumes the subsequent list is a list of evaluated
operands.
We will need to be able to evaluate the list of operands to get a list of
values to pass
to mini-apply. Define: list-of-values.
<![CDATA[
(define (list-of-values exps env)
(if (no-operands? exps)
'()
(cons (mini-eval (first-operand exps) env)
(list-of-values (rest-operands exps) env))))
]]>
Note we are using our mini-eval to evaluate an expression in env. We
can test it out by passing it a list of arguments and an environment
as follows:
<![CDATA[
> 3levenv
(((k y) isover 2)
((buchanan nader cat bush gore) (name too long) lost 56 maybeb maybeg)
((x cat p) 17 10 3))
> (list-of-values '(y buchanan x cat) 3levenv)
(2 (name too long) 17 56)
]]>
Looks like the right values. We even got the value of cat from
the most local frame that had cat defined.
Ok. We can recognize and pick apart a function application. We can
evaluate the
list of arguments.
Now we need to get some primitive procedures. Having designed a 3-bit
adder from logic gates, we could write our basic primitive procedures
from scratch. But it will be easier to steal them from Drscheme, just
like we stole numbers from Drscheme. We can get Drscheme's primitives
by using eval, for example:
<![CDATA[
> (eval '+ (interaction-environment))
#<primitive:+>
]]>
In fact, in drscheme, if you don't explicitly name the environment
in eval, it defaults to (interaction-environment).
<![CDATA[
> (eval '+)
#<primitive:+>
>
]]>
So, we want to bind
+ to Drscheme's #primitive:+, - to Drscheme's #primitive:- , etc.
in our global environment. Then we can make our mini-apply just invoke
Drscheme's apply on the Drscheme primitive and the list of operand
values evaluated in our environment.
So, let us set up the global environment as follows:
<![CDATA[
(define the-global-environment
(extend-environment
(list '+ '- )
(list
(list 'primitive (eval '+))
(list 'primitive (eval '-)))
the-empty-environment))
]]>
and observe:
<![CDATA[
> the-global-environment
(((+ -) (primitive #<primitive:+>) (primitive #<primitive:->)))
]]>
We will set up the environment in a more sophisticated way soon. For
now, I want to emphasize that + is bound to a list whose car is the
atom 'primitive and whose cadr is the Drscheme procedure object that
will carry out plus for us.
Now, suppose we have primitive procedures in the global environment as above,
how should we modify mini-eval and define mini-apply to handle this?
We will modify mini-eval to recognize and apply a function by adding the
clause:
<![CDATA[
((application? exp)
(mini-apply (mini-eval (operator exp) env)
(list-of-values (operands exp) env)))
]]>
to the cond in mini-eval. Essentially if exp is an application, this will
do the
following:
- call mini-eval to evaluate the operator in environement env
(and get a
procedure);
- call list-of-values to evaluate the operands in env; and
then
- call
mini-apply with the procedure object and list of operand values.
We must define mini-apply. mini-apply will assume that the first
parameter is a procedure object and the the second parameter is a list
of argument values. To define mini-apply, we will introduce a few
more predicates and selectors. Define and think about:
primitive-procedure?, primitive-implementation, apply-primitive-procedure.
<![CDATA[
(define (primitive-procedure? proc)
(tagged-list? proc 'primitive))
(define (primitive-implementation proc) (cadr proc))
(define (apply-primitive-procedure proc args)
(apply ;;in underlying implementation
(primitive-implementation proc) args))
]]>
With these we can define a mini-apply that will will work with primitive
procedures:
<![CDATA[
(define (mini-apply procedure arguments)
(cond ((primitive-procedure? procedure)
(apply-primitive-procedure procedure arguments))
(else
(error
"Unknown procedure type -- APPLY" procedure))))
]]>
Now add the application clause to mini-eval and redefine mini-eval. Define the
global environment as above and try:
<![CDATA[
> (driver-loop)
MC-EVAL==> (+ 4 6)
10
MC-EVAL==> (define x 17)
ok
MC-EVAL==> (define y (+ x 10))
ok
MC-EVAL==> y
27
MC-EVAL==> x
17
MC-EVAL==> (- x y)
-10
MC-EVAL==> (+ 100 (- y (+ x 3)))
107
MC-EVAL==> (quit)
]]>
This is really great. Our interpreter is beginning to be able to do
something. Notice that it even handles compound expressions.
Evaluate: (require-library "trace.ss")
Here is a trace that is worth thinking about:
<![CDATA[
Welcome to DrScheme, version 100.
Language: MrEd Debug.
> (trace mini-eval mini-apply list-of-values)
(mini-eval mini-apply list-of-values)
> the-global-environment
(((+ -) (primitive #<primitive:+>) (primitive #<primitive:->)))
> (driver-loop)
MC-EVAL==> (define x 17)
|(mini-eval
(define x 17)
(((+ -) (primitive #<primitive:+>) (primitive #<primitive:->))))
| (mini-eval
17
(((+ -) (primitive #<primitive:+>) (primitive #<primitive:->))))
| 17
|ok
ok
MC-EVAL==> x
|(mini-eval
x
(((x + -) 17 (primitive #<primitive:+>) (primitive #<primitive:->))))
|17
17
MC-EVAL==> (define cat 30)
|(mini-eval
(define cat 30)
(((x + -) 17 (primitive #<primitive:+>) (primitive #<primitive:->))))
| (mini-eval
30
(((x + -) 17 (primitive #<primitive:+>) (primitive #<primitive:->))))
| 30
|ok
ok
MC-EVAL==> cat
|(mini-eval
cat
(((cat x + -) 30 17 (primitive #<primitive:+>) (primitive #<primitive:->))))
|30
30
MC-EVAL==> (+ x cat)
|(mini-eval
(+ x cat)
(((cat x + -) 30 17 (primitive #<primitive:+>) (primitive #<primitive:->))))
| (mini-eval
+
(((cat x + -)
30
17
(primitive #<primitive:+>)
(primitive #<primitive:->))))
| (primitive #<primitive:+>)
| (list-of-values
(x cat)
(((cat x + -)
30
17
(primitive #<primitive:+>)
(primitive #<primitive:->))))
| |(mini-eval
x
(((cat x + -)
30
17
(primitive #<primitive:+>)
(primitive #<primitive:->))))
| |17
| |(list-of-values
(cat)
(((cat x + -)
30
17
(primitive #<primitive:+>)
(primitive #<primitive:->))))
| | (mini-eval
cat
(((cat x + -)
30
17
(primitive #<primitive:+>)
(primitive #<primitive:->))))
| | 30
| | (list-of-values
()
(((cat x + -)
30
17
(primitive #<primitive:+>)
(primitive #<primitive:->))))
| | ()
| |(30)
| (17 30)
| (mini-apply (primitive #<primitive:+>) (17 30))
| 47
|47
47
MC-EVAL==> (quit)
"exiting-mini-eval"
>
]]>
I'll say a few words about what you are looking at.
Make sure you understand the above trace. If you like, try a couple of
computations
with trace still on. Then get out of your interpreter and take the traces
off. At home, review everything and play around with your interpreter.