The Metacircular Evaluator
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.
This material is based on the discussion in the book, Chapter 4.1, The Metacircular Evaluator.
To run the metacircular evaluator, download
mceval-with-let.ss. Note: you must run it with the R5RS languageselect 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 (
until) to implement.
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
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.
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))
clausesprovided to the AND expression. It recursively uses
mc-evalto 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).
(if (null? clauses) ... )”), the entire AND expression returns
MC-EVAL, after the test for the
((and? exp) (eval-and exp env))
;;; 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!