CS 22
Clab 33: The Meta-circular evaluator VI: user defined procedures
We will continue to follow SICP's design (using abstraction
barriers, etc.) to build a small Scheme evaluator bottom-up.
Our interpreter now lets users do most things except define and
execute their own functions. Today we will finish building the basic
mini-evaluator by adding user-defined procedures.
Let us review what Scheme should do when it evaluates an expression like:
<![CDATA[
(lambda (x y ) body)
]]>
According to rule 4 (second bullet on page 240), "A procedure is
created by evaluating a lambda expression relative to a given
environment. The resulting procedure object is a pair consisting of
the text of the lambda expression and a pointer to the environment in
which the procedure was created." This is done so that the procedure
can be properly applied when invoked on arguments. In our
interpreter, instead of 'a pointer to the environment in which the
procedure was created', we will carry that whole environment with the
procedure. That is evaluation of a lambda expression in environment
env will consist of constructing a list consisting of the word
procedure, followed by the lambda expression followed by the whole
environment, env. This can be accomplished by:
<![CDATA[
;;; returns #t if exp begins with lambda. returns #f otherwise.
(define (lambda? exp) (tagged-list? exp 'lambda))
;;; given a user-defined lambda expression, exp,
;;; returns the list of parameters of exp
(define (lambda-parameters exp) (cadr exp))
;;; given a user-defined lambda expression, exp,
;;; returns the body of exp
(define (lambda-body exp) (cddr exp))
;;; given a list of parameters and body and
;;; environment, env, make-procedure returns a procedure object that
;;; is a list consisting of the word procedure, followed by the
;;; list of parameters followed by the body followed by the whole environment
(define (make-procedure parameters body env)
(list 'procedure parameters body env))
]]>
Using we get:
<![CDATA[
> (define f '(lambda (x y z)
(+ (* x z) y)))
> f
(lambda (x y z) (+ (* x z) y))
> (lambda-parameters f)
(x y z)
> (lambda-body f)
((+ (* x z) y))
> (make-procedure
(lambda-parameters f)
(lambda-body f)
3levenv)
(procedure
(x y z)
((+ (* x z) y))
(((k y) isover 2)
((buchanan nader cat bush gore) (name too long) lost 56 maybeb maybeg)
((x cat p) 17 10 3)))
>
]]>
We can handle evaluation of lambda in mini-eval by adding the clause:
<![CDATA[
((lambda? exp)
(make-procedure (lambda-parameters exp)
(lambda-body exp)
env))
]]>
before the application clause. Do that, save, execute, and then
try the following:
<![CDATA[
Welcome to DrScheme, version 103p1.
Language: Graphical Full Scheme (MrEd) Custom.
> the-global-environment
(((car cdr cons null? + - * / = < > newline display)
(primitive #<primitive:car>)
(primitive #<primitive:cdr>)
(primitive #<primitive:cons>)
(primitive #<primitive:null?>)
(primitive #<primitive:+>)
(primitive #<primitive:->)
(primitive #<primitive:*>)
(primitive #<primitive:/>)
(primitive #<primitive:=>)
(primitive #<primitive:<>)
(primitive #<primitive:>>)
(primitive #<primitive:newline>)
(primitive #<primitive:display>)))
> (driver-loop)
MC-EVAL==> (define f
(lambda (x y) (+ (* x x) (* y y))))
ok
MC-EVAL==> f
#0=(procedure (x y) ((+ (* x x) (* y y))) (((f car cdr cons null? + -
* / = < > newline display) #0# (primitive #<primitive:car>) (primitive
#<primitive:cdr>) (primitive #<primitive:cons>) (primitive
#<primitive:null?>) (primitive #<primitive:+>) (primitive
#<primitive:->) (primitive #<primitive:*>) (primitive #<primitive:/>)
(primitive #<primitive:=>) (primitive #<primitive:<>) (primitive
#<primitive:>>) (primitive #<primitive:newline>) (primitive
#<primitive:display>))))
MC-EVAL==> (quit)
"exiting-mini-eval"
> the-global-environment
#1=(((f car cdr cons null? + - * / = < > newline display)
(procedure (x y) ((+ (* x x) (* y y))) #1#)
(primitive #<primitive:car>)
(primitive #<primitive:cdr>)
(primitive #<primitive:cons>)
(primitive #<primitive:null?>)
(primitive #<primitive:+>)
(primitive #<primitive:->)
(primitive #<primitive:*>)
(primitive #<primitive:/>)
(primitive #<primitive:=>)
(primitive #<primitive:<>)
(primitive #<primitive:>>)
(primitive #<primitive:newline>)
(primitive #<primitive:display>)))
>
]]>
Notice that f is bound to the list:
<![CDATA[
(procedure (x y) ((+ (* x x) (* y y))) #1#)
]]>
where #1# is an abbreviation for the environment that the lambda was
evaluated in (later mutated by the define f ).
Of course, now that we have procedure objects that look like:
<![CDATA[
(procedure
(x y z)
((+ (* x z) y))
(((k y) isover 2)
((buchanan nader cat bush gore) (name too long) lost 56 maybeb maybeg)
((x cat p) 17 10 3)))
]]>
we need a predicate to recognize 'em and some selectors
to pull them apart so define:
<![CDATA[
;;; returns #t if p is a user-defined procedure object
;;; returns #f otherwise
(define (compound-procedure? p)
(tagged-list? p 'procedure))
;;; returns list of formal parameters from procedure object p
(define (procedure-parameters p) (cadr p))
;;; returns the body of procedure object p
(define (procedure-body p) (caddr p))
;;; returns environment bound with procedure object p
(define (procedure-environment p) (cadddr p))
]]>
If this is the way we create procedure objects, we will have to make
sure that we apply them according to rule 3 (first bullet on page
240): "A procedure object is applied to a set of arguments by
constructing a frame, binding the formal parameters of the procedure
to the actual values of the arguments of the call, and then evaluating
the body of the procedure in the context of the new environment
constructed. The new frame has as its enclosing environment the
environment part of the procedure object being applied."
We carry this rule out by redefining mini-apply. We use the predicate
and selectors defined above. In defining mini-apply, we take care of
"binding the formal parameters of the procedure to the actual values
of the arguments of the call ... The new frame has as its enclosing
environment the environment part of the procedure object being
applied." by
<![CDATA[
(extend-environment
(procedure-parameters procedure)
arguments
(procedure-environment procedure))))
]]>
where arguments was obtained by our old friend: list-of-values.
The body of the procedure object is: (procedure-body procedure).
We take care of "and then evaluating the body of the procedure in the
context of the new environment constructed" by
<![CDATA[
(eval-sequence
(procedure-body procedure)
(extend-environment
(procedure-parameters procedure)
arguments
(procedure-environment procedure))))
]]>
Except for the addition of the lambda clause, mini-eval can be left as
it was for handling primitive procedures. But we need to modify
mini-apply so that it looks like:
<![CDATA[
(define (mini-apply procedure arguments)
(cond ((primitive-procedure? procedure)
(apply-primitive-procedure procedure arguments))
((compound-procedure? procedure)
(eval-sequence
(procedure-body procedure)
(extend-environment
(procedure-parameters procedure)
arguments
(procedure-environment procedure))))
(else
(error
"Unknown procedure type -- APPLY" procedure))))
]]>
Try this out. Here are a couple of examples:
<![CDATA[
(driver-loop)
MC-EVAL==> (define f
(lambda (x) (* x x)))
ok
MC-EVAL==> (f 5)
25
MC-EVAL==> ((lambda (x y) (+ x (f y))) 3 20)
403
MC-EVAL==> q
> (driver-loop)
MC-EVAL==> (define fact
(lambda (n)
(cond
((< n 1) 1)
(else (* n (fact (- n 1)))))))
ok
MC-EVAL==> fact
#0=(procedure (n) ((cond ((< n 1) 1) (else (* n (fact (- n 1)))))) (((fact car cdr cons null? + - * / = < >) #0# (primitive #<primitive:car>) (primitive #<primitive:cdr>) (primitive #<primitive:cons>) (primitive #<primitive:null?>) (primitive #<primitive:+>) (primitive #<primitive:->) (primitive #<primitive:*>) (primitive #<primitive:/>) (primitive #<primitive:=>) (primitive #<primitive:<>) (primitive #<primitive:>>))))
MC-EVAL==> (fact 3)
6
MC-EVAL==> (fact 5)
120
]]>
Now I must shout:
You now have a small but complete evaluator. With appropriate
encoding and memory resources, this evaluator can do anything
that any computer can do using any language.
Kelemen seconds three MIT professors (Abelson, Sussman, Sussman)
when they say:
"An evaluator (or interpreter) for a programming language is
a procedure that, when applied to an expression of the language,
performs the actions required to evaluate that expression.
It is no exaggeration to regard this as the most fundamental
idea in programming:
The evaluator, which determines the meaning of expressions in a
programming language, is just another program.
To appreciate this point is to change our images of ourselves
as programmers. We come to see ourselves as designers of languages,
rather than only users of languages designed by others."
If you have not already done so, modify your interpreter so that
it can handle the sequencing construct:
begin and the (define (f ... form of define.
Try your new interpreter on the procedure make-withdraw of pp. 222.
I used cond because I didn't have if implemented. Make sure you have
* as a primitive procedure.
See if you can get:
<![CDATA[
> (driver-loop)
MC-EVAL==> (define (fact n)
(cond
((< n 1) 1)
(#t (* (fact (- n 1)) n))))
ok
MC-EVAL==> (fact 6)
720
MC-EVAL==> (define (make-withdraw balance)
(lambda (amount)
(cond
((> balance amount)
(set! balance (- balance amount))
balance)
(else "insuff funds"))))
ok
MC-EVAL==> (define w1 (make-withdraw 100))
ok
MC-EVAL==> (w1 20)
80
MC-EVAL==> (define w2 (make-withdraw 200))
ok
MC-EVAL==> (w2 20)
180
MC-EVAL==> q
Unbound variable q
>
]]>