Interpreter Project
Part 1: Environments

For the remainder of the semester, we will be working towards building an interpreter for a large subset of Scheme, covering most of the commands which we have used in class. The interpreter we will write is constructed in six components, each which builds upon the last. It will not be possible to start a component until you have completed the previous one. For this reason, it is very important that you complete each component before the next class meeting. At the beginning of each class, you will be asked to demonstrate your working code. The final version of the project, including all six components, will be due at noon on Monday, May 8th.

You are encouraged to work with a partner for the duration of this project. You may not switch partners or drop your partner part-way through the project. You and your partner will receive identical grades, and this project is worth 20% of your grade, so choose your partner wisely.

The textbook focuses on creating an interpreter in Section 4.1. While many of the concepts we discuss in our interpreter are similar to those discussed in the textbook, we will not design our interpreter in the same way. You should read the text for a more complete understanding of the interpreter you are building, but you will be able to complete the interpreter project based on previous material you have learned in this class and through the directed steps I will provide for you in the each of the parts of this project.

We will be building what is known as a "bottom-up" interpreter. This means that we will start at the "bottom", getting the lowest-level components working first before moving "up" to higher-level components. Extensive testing of each component is extremely important as small mistakes early on will make successful completion of this project much more difficult.

Below is an outline of the steps we will take in implementing our interpreter:

Part 1	Variables and Environments	binding, frame and environment abstractions
Part 2	Evaluation	i-eval global-env read-eval-loop quote, define, set!
Extension One	(extra credit)	quasiquote, unquote simple syntax checking
Part 3	Primitive Procedures	primitive procedure abstraction i-apply car, cdr, cons, null? +, -, *, /, <, >, =, equal?, eq? display, newline set-car!, set-cdr!
Part 4	Special Forms	if, begin, cond
Extension Two	(extra credit)	trace, untrace
Part 5	User-defined procedures	lambda, let
Part 6	Added special forms and meta-circularity: interpret your interpreter	new special forms meta-circularity (portions extra credit)
Extension Three	(extra credit)	define-macro functions with variable arity "shortcut notation" functions ...and more!

This interpreter will be a large program. To be sure you keep yourself organized, you can always refer to this summary page which details each of the major functions you will write, along with the order of their parameters.

Extensive testing of your interpreter will clutter the code you have written and make it difficult for both you and me to examine. To alleviate this, you will keep all the tests you write in a separate file. Your interpreter should be kept in a file called interpreter.ss and your tests should be kept in a file called i-tests.ss. In order for your testing program to read your interpreter code, place the following line at the top of your test file: (load "interpreter.ss")

In addition, I have provided you with a framework for testing your interpreter. Read through the file using-tester.ss (in your cs37/homework/i-1/ directory) to learn how to use the tester module.

You should familiarize yourself with the search function built into DrScheme: under the Edit menu, choose Find. Also, a feature you may find useful is the (define ...) button located in the top left (below the name of the file you are editing and under the menu bar item "File"). It displays every defined variable and procedure, and if you click on one, you will be taken directly to its definition in the file.

Throughout the project, we will emphasize the idea of data abstraction. This means that we will create abstraction barriers between the data manipulated by the interpreter and the actual way in which the data is represented. This will be similar to what you have done in past assignments. Be sure to use constructor, selector, and mutator procedures whenever you want to create, access, or update data. For ease of writing your interpreter, you should not use object-oriented techniques for this project.

Environments

The first component begins by developing environments. Environments will be used by the interpreter when evaluating Scheme expressions. Every expression in Scheme is evaluated within some environment. Often it is a special environment called the global-env (which you will define in Part 2).

To get the files you will need to start, run update37.

At the lowest level of an environment are variable bindings. A binding is the joining of a symbol to a value. We will use list notation to represent bindings. For example, the binding (x 3) indicates that the symbol x is bound to the value 3, and (sponge bob) indicates that the symbol sponge is bound to the value bob.

These are the functions that you will use to create, access and change variable bindings:
(make-binding var val)
(binding-variable binding)
(binding-value binding)
(set-binding-value! binding val)

I have included tests for each of these functions in the i-tests.ss file. You may also want to see the summary page for more details. Example:

> (define sample (make-binding 'today 'tuesday))
> sample
(today tuesday)
> (binding-variable sample)
today
> (binding-value sample)
tuesday
> (set-binding-value! sample 'wednesday)
> sample
(today wednesday)

> (define sample2 (make-binding 'a-pair (cons 1 2)))
> a-pair  
(a-pair (1 . 2))
> (binding-variable sample2)
a-pair
> (binding-value sample2)
(1 . 2)

> (define sample3 (make-binding 'a-list (cons 1 (cons 2 null))))
> a-list  
(a-list (1 2))
> (binding-variable sample3)
a-list
> (binding-value sample3)
(1 2)

The frame abstraction

Next we need to implement frames, which are lists of bindings. The procedure make-frame takes a list of variables and a list of values, both of which should be the same length, and creates a frame containing bindings of the variables to the values. If the variable and value lists are of different lengths, make-frame should generate an appropriate error message. For example:

> (make-frame '(a b c) '(6 7 8))
((a 6) (b 7) (c 8))

> (make-frame '(d e) '((1 . 2) (3 4)))
((d (1 . 2)) (e (3 4)))

> (make-frame '(x y z) '(#t #f))
ERROR make-frame::too many variables

> (make-frame '(today tomorrow) '(tue wed thu))
ERROR make-frame::too many values

After completing and testing make-frame, write and test the remaining frame functions. (See the summary page for more details.)

(make-frame vars vals) ; defined above
(first-binding frame)
(rest-of-bindings frame)
(empty-frame? frame)
(adjoin-binding binding frame)
(binding-in-frame var frame)

Note that the function adjoin-binding does not have a "!" in its name. Therefore it should not use set!, set-car!, or set-cdr!. It should simply cons a new binding onto an existing frame and return the new frame.

Also, be sure you use the run-tests method for all of your tests and retain all of your tests in the i-tests.ss file since you will be graded on your tests as well as your code.

Here are some examples of the above mentioned functions:

> (define frame (make-frame '(a b c) '(6 7 8)))
> (first-binding frame)
(a 6)
> (rest-of-bindings frame)
((b 7) (c 8))
> (empty-frame? frame)
#f
> (binding-in-frame 'a frame)
(a 6)
> (binding-in-frame 'c frame)
(c 8)
> (binding-in-frame 'x frame)
#f

The environment abstraction

Now that frames have been implemented, we can implement environments, which are represented as a list of frames. An empty environment is represented as the empty list. Test all of these environment functions thoroughly before going on. (See the summary page for more details.)

(empty-env? env)
(first-frame env)
(rest-of-frames env)
(set-first-frame! env new-frame)
(adjoin-frame frame env)
(extend-env vars vals base-env)
(binding-in-env var env)
(lookup-variable var env) ; outside of the 'environment' abstraction

A variable may appear in several different frames of an environment. For example:

(define empty-env '())

(define env1 (extend-env '(a b c) '(1 2 3) empty-env))

(define env2 (extend-env '(a c d e) '(red blue green yellow) env1))

(define env3 (extend-env '(a f) '(#t #f) env2))

Write the procedure binding-in-env that will take a variable name and search through the frames of an environment until it finds the first binding for that variable. In this example, the first binding for a would be (a #t), the first binding for c would be (c blue) and the first binding for b would be (b 2). It should return #f if no binding is found. Be sure to use any appropriate abstraction functions, such as empty-env? and binding-in-frame.

> (binding-in-env 'c env3)
(c blue)

Finally, use binding-in-env to write the procedure lookup-variable to find the value of a variable in a given environment. If no binding is found, an error message should be generated. For example:

> (lookup-variable 'c env3)
blue

> (lookup-variable 'g env3)
ERROR lookup-variable::unbound variable g

Looking to share files with your partner?

scp interpreter.ss username@allspice:cs37/homework/i-1/interpreter.ss