CS 37

Clab 31: 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.

Before we proceed, I would like you to read the following obituary from yesterday's NY Times.: Amir Pnueli, Pioneer of Temporal Logic, Dies at 68 or pnueli local

Time is one of the things that makes some aspects of computer science more difficult than ordinary mathematics. Without explicitly mentioning time, it was an issue when we considered the difference between recursive processes and iterative processes. Even though they may both be described by a recursive procedure, the processes those procedures engender may play out differently in time. We treated time more explicitly once we introduced mutation (set!, order is important), threads, and streams (future promises). In addition, to the mentions of time in the main text, the following footnotes involve time one way or another:
ch1: 54
ch3:12,30,34,35,36,39,47,48,49,50,51,52,58,59,73,75.
Treating time formally is not part of an ordinary undergraduate curriculum in CS nor even most areas of graduate study. However, progress in this area has already made significant contirbutions to processor design and will hopefully continue to improve correctness of software.

Last clab, we added begin and cond to our interpreter. If you did not finish, work on it some more at the end of this clab and at home. Until we get to the final examples, most of what follows will not need cond.

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:

(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, it will look like we are carrying the whole environment along with a procedure. That, however, is due to our printing. The identifier env at the end of our procedure objects is in fact 'a pointer to the environment in which the procedure was created'. So, 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, env. This can be accomplished by: ;;; 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)) Put those in your definitions window, hit run and test in your interactions window. You should get: > (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) ((Williams Amherst Swarthmore Middlebury cat) 3 2 1 4 4) ((x cat p) 17 10 3))) > We can handle evaluation of lambda in mini-eval by adding the clause: ((lambda? exp) (make-procedure (lambda-parameters exp) (lambda-body exp) env)) before the application clause. Do that, save, run, and then try the following: > 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: (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: (procedure (x y z) ((+ (* x z) y)) (((k y) isover 2) ((Williams Amherst Swarthmore Middlebury cat) 3 2 1 4 4) ((x cat p) 17 10 3))) we need a predicate to recognize 'em and some selectors to pull them apart so define: ;;; 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

(extend-environment (procedure-parameters procedure) arguments (procedure-environment procedure)))) where arguments was obtained by our old friend: list-of-values, in the call to mini-apply from mini-eval.

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

(eval-sequence (procedure-body procedure) (extend-environment (procedure-parameters procedure) arguments (procedure-environment procedure)))) Except for the addition of the lambda clause which we already did, mini-eval can be left as it was for handling primitive procedures. But we need to modify mini-apply so that it looks like: (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: (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)))))) #1=(((fact f car cdr cons null? + - * / = < > newline display) #0# (procedure (x) ((* x x)) #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>)))) MC-EVAL==> (fact 3) 6 MC-EVAL==> (fact 5) 120 Note that f was a free variable in the (lambda (x y) .. ) definition. f was found properly even though f was NOT in the frame binding x and y to apply the lambda to 3 20.

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:

> (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==> (w1 20) 60 MC-EVAL==> (define w2 (make-withdraw 200)) ok MC-EVAL==> (w2 20) 180 MC-EVAL==> (w1 50) 10 MC-EVAL==> (w2 50) 130 MC-EVAL==> (w1 50) insuff funds MC-EVAL==> (w2 50) 80 MC-EVAL==> (quit) "exiting-mini-eval" > If you do not successfully finish this in clab today, work on it at home. Feel free to ask questions.