PS9

Home Assignments Lecture Blog Resources Project Discussion Group

The Metacircular Evaluator

Overview

In this problem set, you’ll learn how to implement Scheme in Scheme—a “meta-circular evalator.”

We'll extend starter code with new features.

Reading

This material is based on the discussion in the book, Chapter 4.1, The Metacircular Evaluator.

The Code

To run the metacircular evaluator, download mceval-with-let.ss. Note: you must run it with the R5RS language—select “Choose Language...” from the pop-up menu in the lower-left corner of a main Racket window.

After evaluating the code buffer, evaluate (driver-loop) in the REPL. This will run the interactions for your metacircular UML Scheme world. Remember that everything you type in (except for variables and numbers) should be prefixed by “uml:” – if you forget, the system will have an error.

You only need to turn in the portions of the code that you change.

Warm-up: Run the metacircular evaluator and evaluate some UML Scheme expressions. Nothing to turn in for this part.

Problem 1: Exercise 4.4 (“or” only) on p. 374. Remember to name your new “or” as “uml:or”.

Problem 2: Exercise 4.1 on p. 368.

Problem 3: Exercise 4.9 on p. 376. Pick one of the iteration constructs (do, for, while or until) to implement.

Submit

Your work will be manually graded by the TAs.

Submit three source files—one for each problem. The work associated with Problem 1 should be in a file named problem1.rkt, Problem 2 answers in problem2.rkt, and Problem 3 answers in problem3.rkt.

For all problems, make sure to all turn in evidence that your code works, and an explanation of what it does.

One-third of the credit will be for a correct implementation;
one-third for a discussion of the implementation; and
one-third for demonstrating that your code works.

Each file should contain:

  • any code that you changed or added. Please do NOT submit the entire starting code.
  • a brief narrative about how the code works.
  • examples of testing that demonstrates that your code works, including narration.

For example, if you were to submit work to implement the uml:and function, you might turn in something like this.

Implementation and discussion of UML:AND
This is the main code:

(define (eval-and exp env)
  (define (iter clauses)
    (if (null? clauses)
	#t
	(if (false? (mc-eval (car clauses) env))
	    #f
	    (iter (cdr clauses)))))
  (iter (and-clauses exp)))

(define (and? exp) (tagged-list? exp 'uml:and))

(define (and-clauses exp) (cdr exp))
This works by iterating down the list of clauses provided to the AND expression. It recursively uses mc-eval to evaluate each clause in the order it appears in the list. If a clause evaluates to false, then the whole expression is considered false (short-circuiting the evaluation of any subsequent expressions).
The only way the whole AND expression evaluates to true is if every single clause evaluates to true. Then, when there are no clauses left (“(if (null? clauses) ... )”), the entire AND expression returns #t.
Also, the following is added to MC-EVAL, after the test for the if? expression:
((and? exp) (eval-and exp env))
Evidence that it works
;;; MC-Eval input: (uml:and true)
;;; MC-Eval value: #t
; AND of a true input is true

;;; MC-Eval input: (uml:and false)
;;; MC-Eval value: #f
; AND of a false input is false

;;; MC-Eval input: (uml:and true true)
;;; MC-Eval value: #t
; AND of two true inputs is true

;;; MC-Eval input: (uml:and true false)
;;; MC-Eval value: #f
; AND of a true input and a false input is false

;;; MC-Eval input: (uml:define foo 1)
;;; MC-Eval value: ok
; we are going to define a variable to test short-circuiting

;;; MC-Eval input: (uml:and false (uml:begin (uml:set! foo 2) true))
;;; MC-Eval value: #f
; AND should have short-circuited, and not evaluated the BEGIN expression which would set FOO to 2

;;; MC-Eval input: foo
;;; MC-Eval value: 1
; FOO is still 1, because UML:AND short-circuited after evaluating the first input as FALSE !

;;; MC-Eval input: (uml:and true (uml:begin (uml:set! foo 2) true))
;;; MC-Eval value: #t
; no short-circuiting, so now FOO should be 2

;;; MC-Eval input: foo
;;; MC-Eval value: 2
; and it is!