CS 22

Clab 32: The Meta-circular evaluator V: adding cond

We will continue to follow SICP's design (using abstraction barriers, etc.) to build a small Scheme evaluator bottom-up.

Last clab we increased the power of our mini-evaluator by adding the ability to inherit primitive procedures from the underlying scheme environment. This involved supplying a mini-apply that just invoked Drscheme's apply on the Drscheme primitive and the list of operand values evaluated in our environment. It also involved binding a procedure name in our mini-eval environment to the drscheme primitive.

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.

(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: Welcome to DrScheme, version 103p1. Language: Graphical Full Scheme (MrEd) Custom. > 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:->))) > Now our interpreter can do quite a bit.

We increased the power of our mini-evaluator by adding the ability to inherit primitive procedures from the underlying scheme environment. This involved supplying a mini-apply that just invoked Drscheme's apply on the Drscheme primitive and the list of operand values evaluated in our environment. It also involved binding a procedure name in our mini-eval environment to the drscheme primitive.

One way to think about this is to consider the primitives inherited as being supplied in the machine language of the machine we are writing our mini-eval to run on. The truth is that what we did will work for any function defined in the underlying scheme environment. For example:

Welcome to DrScheme, version 103p1. Language: Graphical Full Scheme (MrEd) Custom. > square reference to undefined identifier: square > (define square (lambda (x) (* x x))) > (define primitive-procedures (list (list 'car car) (list 'cdr cdr) (list 'cons cons) (list 'null? null?) (list '+ +) (list '- -) (list 'swatsq square) )) > (define the-global-environment (setup-environment)) > the-global-environment (((car cdr cons null? + - swatsq) (primitive #<primitive:car>) (primitive #<primitive:cdr>) (primitive #<primitive:cons>) (primitive #<primitive:null?>) (primitive #<primitive:+>) (primitive #<primitive:->) (primitive #<procedure:square>))) > (driver-loop) MC-EVAL==> (define thanks (+ 22 1)) ok MC-EVAL==> thanks 23 MC-EVAL==> (swatsq thanks) 529 MC-EVAL==> (quit) "exiting-mini-eval" So, depending on what we want to study, we can inherit from drscheme or (soon) define almost anything in our own mini-eval environment.

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.

Your task for the rest of today is to add sequence (begin ...) and cond to our mini-evaluator.

Recall that cond works as follows:
(cond (p1 act1) (p2 act2) ... (pn actn)) where each p is a predicate and each act is one or more actions to be taken if the corresponding p is the first p that is not #f. The pairs (p act) are called clauses. Conditionals are special forms because, they do not evaluate all their arguments first. That is p1 is evaluated. If p1 is not #f, then act1 is evaluated (act1 may be a sequence of actions) and none of the rest of the conditional is evaluated. If p1 is #f, then act1 is not evaluated; p2 is evaluated. If p2 is not #f, then act 2 is evaluated and none of the rest of the conditional is evaluated. If p2 is #f then p3 ....

In their evaluator, SICP handles conditionals by doing if first and then converting conditionals to nested ifs. I want you to try to do conditionals directly in the style of the evaluator so far i.e. case-based analysis using appropriate abstraction barriers, etc. Possible names for these might be: conditional?, clauses, no-clauses?, first-clause, rest-clauses, predicate, actions, else-clause?, last-exp?, first-exp, rest-exps.

I added a few more primitives in addition to cond and begin. Here is a sample run:

Welcome to DrScheme, version 103p1. Language: Graphical Full Scheme (MrEd) Custom. > the-global-environment (((car cdr cons null? + - * / = < >) (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:>>))) > (driver-loop) MC-EVAL==> (define x 7) ok MC-EVAL==> (define y 100) ok MC-EVAL==> (cond ((< x 17) 'hi) (else 'ho)) hi MC-EVAL==> (cond ((< x 1) 'hi) (else 'ho)) ho MC-EVAL==> (cond ((< x (+ 3 1)) 1) ((= x 6) 16) ((= x 7) 17 (set! y 333) 18) (else 20)) 18 MC-EVAL==> y 333 MC-EVAL==> (quit) "exiting-mini-eval" > Good luck.