CS 37
Clab 29: 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)
define and set! to our mini-evaluator. If you succeeded with
all of that and have tested your work, continue to use your
evaluator. If you are not certain that your evaluator works,
start with mine which is available at:
/home/cfk/pub/cs37/week10/clab28d.scm.
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.
Let's run the short test from the end of last clab:
<![CDATA[
> 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.
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 372 [3m].
Language: Pretty Big (includes MrEd and Advanced Student).
> (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[
> +
#<primitive:+>
> (eval + (interaction-environment))
#<primitive:+>
> (define a 10)
> (define b 5)
> (apply
(eval + (interaction-environment))
(list
(eval 'a (interaction-environment))
(eval 'b (interaction-environment))
))
15
> (apply
(eval + (interaction-environment))
(list 'a 'b))
. +: expects type <number> as 1st argument, given: a; other arguments were: b
>
> (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 be given 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)
((Williams Amherst Swarthmore Middlebury cat) 3 2 1 4 4)
((x cat p) 17 10 3))
> (list-of-values '(y Williams x cat) 3levenv)
(2 3 17 4)
>
]]>
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 of the Drscheme primitive on the list of operand
values evaluated in our environment.
So, let us set up the global environment in your
Definitions window 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 environment 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, press run
to effectively redefine mini-eval.
Note that the predicate application? just says #t if
its argument exp is a pair. So, you better put this AFTER any
clauses where a pair could be something else (like a define
of set!).
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 and
evaluates x and y in our environment. x and y are NOT defined
in drscheme's environment.
Evaluate: (require (lib "trace.ss"))
Here is a trace that is worth thinking about:
<![CDATA[
Welcome to DrScheme, version 372 [3m].
Language: Pretty Big (includes MrEd and Advanced Student).
> (require (lib "trace.ss"))
> (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.
Having stolen + and - from Drscheme, there is no reason to stop there.
If you like, you can think of these primitives as being supplied in
the machine language of the machine we are writing our mini-eval to run on.
Let's steal
some more primitive procedures. This means we want to grab a bunch of stuff to
form an initial environment. We will do this in a somewhat more organized way
so that adding and removing primitives will be relatively easy. For more
power, we want lots of primitives. If we want to look at environments in
detail, we may not want to clutter it up with primitives we do not need.
Think about and add the following to your definition window.
<![CDATA[
(define primitive-procedures
(list (list 'car car)
(list 'cdr cdr)
(list 'cons cons)
(list 'null? null?)
(list '+ +)
(list '- -)
;; more primitives
))
(define (primitive-procedure-names)
(map car
primitive-procedures))
(define (primitive-procedure-objects)
(map (lambda (proc) (list 'primitive (cadr proc)))
primitive-procedures))
(define (setup-environment)
(let ((initial-env
(extend-environment (primitive-procedure-names)
(primitive-procedure-objects)
the-empty-environment)))
;; (define-variable! '#t #t initial-env) decided to treat as
;; (define-variable! '#f #f initial-env) self-evaluating
initial-env))
(define the-global-environment (setup-environment))
]]>
Now try out our new environment:
<![CDATA[
> the-global-environment
(((car cdr cons null? + -)
(primitive #<primitive:car>)
(primitive #<primitive:cdr>)
(primitive #<primitive:cons>)
(primitive #<primitive:null?>)
(primitive #<primitive:+>)
(primitive #<primitive:->)))
> (driver-loop)
MC-EVAL==> (define x 25)
ok
MC-EVAL==> (define y 100)
ok
MC-EVAL==> (- y x)
75
MC-EVAL==> (define alis '(a b c))
ok
MC-EVAL==> (car alis)
a
MC-EVAL==> (cdr alis)
(b c)
MC-EVAL==> (null? alis)
#f
MC-EVAL==> (quit)
"exiting-mini-eval"
> the-global-environment
(((alis y x car cdr cons null? + -)
(a b c)
100
25
(primitive #<primitive:car>)
(primitive #<primitive:cdr>)
(primitive #<primitive:cons>)
(primitive #<primitive:null?>)
(primitive #<primitive:+>)
(primitive #<primitive:->)))
> alis
. reference to undefined identifier: alis
> y
. reference to undefined identifier: y
> x
. reference to undefined identifier: x
>
]]>
Now our interpreter can do quite a bit. Meditate on this.