You should begin working on the assignment once you receive it. It is to your advantage to get work done early, rather than waiting until the night before it is due. You should also read over and think through each part of the assignment for that week (as well as any project code) before you sit down at the computer. It is generally much more efficient to test, debug, and run a program that you have thought about beforehand, rather than doing the planning "online." Diving into program development without a clear idea of what you plan to do generally ensures that the assignments will take much longer than necessary.
The purpose of this project is to familiarize you with evaluators, of various flavors. There is a lot to read and understand; we recommend that you first skim through the project to familiarize yourself with the format, before tackling problems.
Word to the wise: This part of the project doesn't require a lot of actual programming. It does require understanding a body of code, however, and thus it will require careful preparation. You will be working with evaluators such as those described in chapter 4 of the textbook, and variations on those evaluators. If you don't have a good understanding of how the evaluator is structured, it is very easy to become confused between the programs that the evaluator is interpreting, and the procedures that implement the evaluator itself. For this project, therefore, we suggest that you do some careful preparation. Once you've done this, your work in the lab should be fairly straightforward.Load the code (meval.scm, then syntax.scm, finally environment.scm) for this part of the project. This file contains a version of the meta-circular evaluator described in lecture and in the textbook. Because this evaluator is built on top of the underlying Scheme evaluator, we have called the procedure that executes evaluation m-eval (with associated m-apply) to distinguish it from the normal eval.
You should look through this file to get a sense for how it implements a version of the evaluator discussed in lecture (especially the procedure m-eval).
You will be both adding code to the evaluator, and using the evaluator. Be careful, because it is easy to get confused. Here are things to keep in mind:
;;; M-Eval input: (+ 3 4) ;;; M-Eval value: 7shows an interaction with the m-eval evaluator. To evaluate an expression, you type the expression and press ctrl-x ctrl-e. Don't use M-z to evaluate the expression; the presence of the prompt confuses the M-z mechanism. Also notice that if you have started up the evaluator in a *scheme* buffer, you may go to any other buffer, write definitions or expressions and evaluate them from that buffer. This will cause the expressions to be evaluated in the new evaluator. On the other hand, if you have not started up the evaluator, evaluating expressions from a buffer will cause them to be evaluated in the normal Scheme evaluator.
Computer Exercise 1: Exploring Meval.
Load the code files into your Scheme environment. To begin using the Scheme interpreter defined by this file, evaluate (driver-loop). Notice how it now gives you a new prompt, in order to alert you to the fact that you are now "talking" to this new interpreter. Try evaluating some simple expressions in this interpreter. Note that this interpreter has no debugging mechanism -- that is, if you hit an error, you will be thrown into the debugger for the underlying Scheme. This can be valuable in helping you to debug your code for the new interpreter, but you will need to restart the interpreter.
You may quickly notice that some of the primitive procedures that Scheme normally knows about are missing in m-eval. These include some simple arithmetic procedures (such as *) and procedures such as cadr, cddr, newline. Extend your evaluator by adding these new primitive procedures (and any others that you think might be useful). Check through the code to figure out where this is done. In order to make these changes visible in the evaluator, you'll need to rebuild the global environment:
(refresh-global-environment)
Show your changes to the evaluator, and turn in a demonstration of your extended evaluator working correctly.
Computer Exercise 2: Changing style.
In MITScheme, if expressions are allowed to lack an alternative expression, as in the following:
(define x 5)
(if (= x 0)
(set! x 0.000001))
At present, what happens if you evaluate this expression in m-eval?
Modify the evaluator so that ifs may lack an alternative, but if they are lacking the alternative and the test evaluates to false, then the value of the if should be #f.
Show your changes to the evaluator, and turn in a demonstration of your extended evaluator working correctly.
Computer Exercise 3: Order of evaluation.
The order of evaluation of arguments in scheme is unspecified, which means each scheme interpreter is free to evaluate them as it sees fit. For the following expression, it is unspecified whether the 3 or the 4 is evaluated first:
(+ 3 4)For this expression, the order of evaluation of arguments doesn't matter, since both 3 and 4 are self-evaluating. However, the result of some expressions (hint: think mutation) could depend on the order of evaluation.
What is the order of evaluation of arguments in MITScheme? Give an expression (or sequence of expressions) that demonstrate the order of evaluation (that is, where the result is different if the evaluator evaluates left-to-right versus right-to-left).
What is the order of evaluation in the meta-circular evaluator? What procedure determines this order of evaluation?
Change the order of evaluation of the meta-circular evaluator to be opposite to that of the underlying MITScheme (e.g. if MITScheme's evaluation order is left-to-right, change your meval to be right-to-left). In order to do this, you will need to figure out how to force one expression to be evaluated before another.
Computer Exercise 4: Adding a special form.
We have seen that our evaluator treats any compound expression as an application of a procedure, unless that expression is a special form that has been explicitly defined to obey a different set of rules of evaluation (e.g., define, lambda, if). We are going to add some special forms to our evaluator in the next few exercises.
A very simple special form is a while loop. This might have the following syntax:
(while (> i 0) (newline) (display i) (newline) (display (factorial i)) (set! i (- i 1)))
This is not necessarily a style of programming that we like, since it relies on explicit mutation of variables. In the above example, the idea is that i would have initially be defined to some value, and then we evaluate the while loop. This loop tests the first subexpression to see if it is true. If it is, the loop then evaluates all of the other subexpressions in order (note the mutation of i to change its value) and repeats the process, doing so until the test expression evaluates to false.
Your task is to add this special form to m-eval, showing your changes to the code, and demonstrating that it works by providing some test cases.
To do this, you should include the following:
Be sure to turn in a listing of your additions and changes, as well as examples of your code working on test cases.
Computer Exercise 5: The let* special form.
Now let's try something a bit tougher. We have already seen the let special form. A variation on this is the let* special form. This form acts much like let, however, the clauses of the let* are evaluated in order (rather than all at the same time as in a let), and any reference in a later clause to the variable of an earlier clause should use the new value of that variable. For example
(define i 1)
(let ((i 3)
(j (fact i))
(list i j)))
would return the value (3 1) because the let variables i, j are bound in parallel, and thus the argument to fact is the value of i outside the expression, namely 1. On the other hand:
(define i 1)
(let* ((i 3)
(j (fact i))
(list i j)))
would return the value (3 6) since the variable i is first bound to 3, and then the variable j is bound, and in this case the input to fact is the new value 3.
Add let* to the evaluator as a special form. To do this, you will need to
Add this special form to your evaluator. Turn in a listing of your changes, and examples of your procedures working on test cases.
Computer Exercise 6:
As a final exercise in adding special forms directly to the evaluator, we would like to add a way for set!s to be undone. To do this, we will need a new special form, unset! which is used as follows:
(define x 4) x ; 4 (set! x 5) x ; 5 (set! x 6) x ; 6 (unset! x) x ; 5 (unset! x) x ; 4 (unset! x) x ; 4
You'll notice that any number of set!s can be undone, and that unset!ing a variable that hasn't been set does nothing.
Early in the semester, we introduced the idea of "syntactic sugar," that is, the notion that some of the special forms in our language can be expressed as simple syntactic transformations of other language elements. Examples are cond, which can be implemented in terms of if; and let, which can be implemented in terms of lambda. Such expressions are also call derived expressions. Your job in this part will be to design and implement a new derived expression for Scheme.
Section 4.1.2 of the textbook demonstrates how to implement cond as a derived expression: to evaluate a cond expression, we transform it to an equivalent if expression using the procedure cond->if; then we evaluate the transformed expression. Let can also be implemented as a derived expression, as explained in exercise 4.6 on page 375.
Computer Exercise 7: Transforming a while.
Implement a syntactic transformation to convert a while loop expression into an if expression. Then change your evaluator so that when the special form while is recognized, the evaluator converts this expression into an if expression and evaluates that.
Remember that in a syntactic transformation, you are converting one list structure into another (which will subsequently be evaluated). Thus, you should start with a simple while-loop example, and write down what the equivalent if expression would be.
For example,
(while (> i 0) (display i) (display (factorial i)) (set! i (- i 1)))
can be rewritten as
(if (> i 0)
(begin
(display i)
(display (factorial i))
(set! i (- i 1))
(while (> i 0)
(display i)
(display (factorial i))
(set! i (- i 1))))
'done)
Thus we need to generalize this transformation, and implement this transformation as a procedure, that takes the while expression and returns the transformed expression. This procedure can now be added to the syntax procedures of the evaluator, and an appropriate clause added to m-eval to handle the new type of expression.
The easiest way to start is to directly use list, append, cons and quote to create the list structure. You will see, however, that this is a bit cumbersome, because we have to do so much direct list manipulation. An alternative method is to use what is known as quasiquote. If you are feeling adventurous, you can read the appendix at the end of this project on quasiquote and use that if you prefer, to create this transformation.
Computer Exercise 8: Transforming boolean combinations.
Look up the official specification of the special form or and the special form and (they are very similar). As before, add a pair of clauses to m-eval that transform or and and expressions into expressions that m-eval can evaluate. Remember that the individual expressions in the body of or are supposed to be evaluated at most once:
(or (begin (display "once ") #f)
(begin (display "and ") #f)
(begin (display "only") 'done))
once and only
;Value: done
(One way to desugar or involves using let---which can itself be desugared later. In this case there can be "false capture" errors if the let variable already appears in the or expression being desugared. For this problem, it is okay to assume that any variables you use in desugaring do not already appear. Note that there is a better way to desugar an or expression that avoids this problem.)
Computer Exercise 9: Desugaring let*s.
Extend m-eval to handle let* expressions, by desugaring them into some other form, such as a let.
Computer Exercise 10: Recursive lets.
Try evaluating the following expression in MITScheme:
(let ((fact
(lambda (n)
(if (= n 0)
1
(* n (fact (- n 1)))))))
(fact 10))
What happens? You might try drawing an environment diagram to figure it out. Scheme has a different special form which works for this case called letrec:
(letrec ((fact
(lambda (n)
(if (= n 0)
1
(* n (fact (- n 1)))))))
(fact 10))
Your task for this question is to add the letrec special form to our evaluator by desugaring it. Do this by first dropping a new frame with the variables bound to some dummy value, then changing the bindings to their actual values. However, you'll have to figure out how to express this in terms of expressions already implemented by m-eval. Also note that you should do this without explicitly using a define.
After implementing letrec, test it with a variety of expressions. Does it work the same as let, except for allowing recursive bindings? Are there any cases where the implementation strategy above yields answers that don't seem right?
Computer Exercise 11: Named lets.
Another special form supported by MITScheme is the named let. Essentially, it allows the lambda produced in the desugaring to be named and referenced in the code. This allows for a nice looping construct; one that doesn't feel as forced (and non-functional-style) as the while loop you implemented earlier. Here is an example of named-let in operation:
(let loop
((i 5))
(if (= i 0) 'done
(begin
(display i)
(loop (- i 1)))))
54321
;Value: done
loop
;Error: unbound variable loop
The application of loop in the body of the named let causes the body of the let to be evaluated again, but with a new value for the variable i. In addition, the name is not added to the current environment as demonstrated by the error generated when it is referenced. Below is another useful example of named let:
(define (ireverse lst)
(let helper
((lst lst)
(result '()))
(if (null? lst)
result
(helper (cdr lst) (cons (car lst) result)))))
Come up with a desugaring for named let and add it to the evaluator. You will notice that the named let expression is very similar to a regular let, except it has an additional symbol at the beginning. Once again, you should do this without an explicit use of define. As usual, test it with a variety of expressions.
You'll find that if you add a complete enough set of primitive procedures, you can run Meval inside of Meval!. Furthermore, you can run Meval inside of Meval inside of Meval inside of Meval inside of Meval ... However, you will notice a certain performance degradation the more evaluators you run. Is there any way to tell how many layers of evaluators are running?
(Note: this may take a bit of work, as there are a number of changes that need to be made. Doing so is not required to complete the project.)
For each problem, include your code (with identification of the exercise number being solved), as well as comments and explanations of your code, and demonstrate your code's functionality against a set of test cases. Once you have completed this project, your file should be submitted electronically on the 6.001 on-line tutor, using the Submit Project Files button.
We encourage you to work with others on problem sets as long as you acknowledge it (see the 6.001 General Information handout) and so long as you observe the rules on collaboration and using "bibles". If you cooperated with other students, LA's, or others, please indicate your consultants' names and how they collaborated. Be sure that your actions are consistent with the posted course policy on collaboration.
Remember that this is Project 5; when you have completed all your work and saved it in a file, upload that file and submit it for Project 5.
Here is an example of using quasiquote to create a transformer. Suppose we have a special form called until, for example:
(define (countup n)
(let ((x 0))
(until (> x n)
(write-line x)
(set! x (+ x 1)))))
The idea is that until checks to see if the first subexpression is true. If it is, it evaluates and returns the next expression, otherwise it skips to the subsequent expression, evaluates it, and repeats the process.
This can be generalized to:
(until test
exp1
exp2
...
expn)
where test, exp1, ..., expn are expressions. The description is that until evaluates the test expression. If the result is true, the value returned by until is #t. If the result is false, until evaluates each of the expressions expi in sequence, then goes back to repeat the test, and keeps doing this over and over until the result of the test is true.
Thus, one way to implement an until is to rewrite it in terms of more primitive Scheme expressions. For instance, in the above example,
(until (> x n)
(write-line x)
(set! x (+ x 1)))))
can be rewritten as
(let ()
(define (loop)
(if (> x n)
#t
(begin (write-line x)
(set! x (+ x 1))
(loop))))
(loop))
and thus
(until test
exp1
exp2
...
expn)
can be rewritten as
(let ()
(define (loop)
(if test
#t
(begin exp1
exp2
...
expn
(loop))))
(loop))
where test, exp1, exp2, ..., expn can be arbitrary expressions.
Hence one way to implement the transformation is as a procedure, which takes the until expression and returns the transformed expression.
(define (until->transformed exp)
(let ((test (cadr exp))
(other-exps (cddr exp)))
(list
'let
'()
(list 'define
'(loop)
(list 'if
test
#t
(cons 'begin
(append other-exps (list '(loop))))))
'(loop))))
This is the direct way of creating the transform. You should check it through carefully to see how the use of list and quote will create an appropriate expression. This form is also a bit cumbersome, because we have to do so much direct list manipulation.
Here is an alternative method called quasiquote -- (note that this is much hairer -- don't feel you have to use this approach as the version above is perfectly fine!! However, you can check out the Scheme reference manual for more details on quasiquote.)
(define (until->transformed exp)
(let ((test (cadr exp))
(other-exps (cddr exp)))
`(let ()
(define (loop)
(if ,test
#t
(begin ,@other-exps
(loop))))
(loop))))
As this example illustrates, the special syntax characters backquote
(`), comma (,), and at-sign (@) are
extremely useful in writing syntactic transformations. Placing a
backquote before an expression is similar to placing an ordinary quote
before the expression, except that any subexpression preceded by a
comma is evaluated. If a subexpression is preceded by comma at-sign,
it is evaluated (and must produce a list) and the list is appended
into the result being formed. For example:
(define x '(1 2 3)) (define y '(4 5 6)) `(a b c ,x ,@y 7 8) ;Value: (a b c (1 2 3) 4 5 6 7 8)
Note that that the evaluated subexpressions of a backquote form can be actual expressions, not just symbols. Thus until->transformed can also be defined as
(define (until->transformed exp)
`(let ()
(define (loop)
(if ,(cadr exp)
#t
(begin ,@(cddr exp)
(loop))))
(loop)))