CS 37

Clab 30: The Meta-circular evaluator V: begin and cond

We will continue to follow SICP's design (using abstraction barriers, etc.) to build a small Scheme evaluator bottom-up. My interpreter from last clab is available at: /home/cfk/pub/cs37/week10/clab29c.scm.

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.

We ended up using drscheme primitives for: car, cdr,cons, null?, +, -.

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 372 [3m]. Language: Pretty Big (includes MrEd and Advanced Student). > 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 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. And I added my begin and cond to mini-eval. Here is a sample run:

Welcome to DrScheme, version 372 [3m]. Language: Pretty Big (includes MrEd and Advanced Student). > 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 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.