MC28 Lab 1: Modifying Evaluators (Spring 1997)

Due: February 26, 1997


You will work on this lab as a member of a two-person (or if need be, three-person) team. Each team is to submit a single jointly-authored lab report. For the first part of this lab, you will work with section 10.3 of the text, which is an implementation of the ``Micro-Scheme'' programming language. You will extend the language with new features which make it less like Scheme. Then, in the second part of the lab, you will modify the ``Mini-Scheme'' implementation of section 10.4 in the ways shown in section 10.5 so as to make it generate explanatory output as it does its evaluation.


Before coming to lab, you should have read and thought about the all of sections 10.1 through 10.3, and this handout. If possible, identify a team-mate; otherwise, we will assign team-mates at the beginning of the first lab period.

In Lab

  1. You should open the file /Net/solen/u8/Faculty/em/max/MC28/micro-scheme.scm and use the ``Evaluate All'' command to evaluate all the definitions in that file. This file contains the Micro-Scheme implementation from section 10.3 of the text, along with some necessary definitions from section 10.2 and earlier chapters of the text.
  2. Next, evaluate (read-eval-print-loop) in Scheme and then try evaluating various Micro-Scheme expressions in the resulting Micro-Scheme read-eval-print loop. When you are done trying out Micro-Scheme and want to return to real Scheme, you can use the ``Abort to Top'' command in the ``Actions'' menu.
  3. Now that you are familiar with Micro-Scheme as it is provided, it is time to add your own extensions. First, add more pre-defined names by modifying look-up-value, as described in exercises 10.11 and 10.12 on page 340 of the textbook. You should use the ``Copy'' and ``Paste'' commands in SchematiX to copy the definition of look-up-value into your own file before you start modifying it. For 10.11, you could add cons, car, cdr, and null?, so that you can do list processing in Micro-Scheme. For 10.12, you can add anything you've wished Scheme had built in, perhaps square. Try out Micro-Scheme again, making sure that your new pre-defined names work.
  4. Next it is time to add a new kind of expression to Micro-Scheme. Do exercise 10.16 from pages 344-345 of the textbook, which calls for adding with expressions to Micro-Scheme. This will involve modifying the definition of micro-scheme-parsing-p/a-list, so you should copy and paste that definition into your file as well. You shouldn't need to modify any other existing definitions -- you should just modify your copy of micro-scheme-parsing-p/a-list and add any new definitions you need.

    Here are two somewhat tricky with expressions; think carefully about what the value of each of them should be, and make sure your implementation produces those values:

    (with x = (+ 2 3) compute (with y = (+ x 4) compute (* x y)))
    (with x = (+ 2 3) compute (with x = (+ x 4) compute (* x x)))
  5. Next you'll add explanatory output to Mini-Scheme as explained in section 10.5. You'll need to have read the remainder of chapter 10 before you continue. Open the file /Net/solen/u8/Faculty/em/max/MC28/mini-scheme.scm and use the Evaluate All command. This file contains the definitions from section 10.4, with the exception of those superseded in section 10.5, and it also contains relevant definitions from 10.2, 10.3, and earlier chapters. Finally, this file also contains the definitions from section 10.5 of unparse (p.354), evaluate-in-at and display-times (p. 355), make-application-ast (p. 356), and make-mini-scheme-version-of (p. 358). You will need to copy all the AST constructors and the read-eval-print-loop and make-procedure procedures out of this file into your own file in order to modify them in the subsequent exercises. (Note that the indentation of make-application-ast (p. 356) is a bit messed up; the on-line version is corrected.)
  6. Do exercise 10.22 on page 354 and test your procedure by unparsing the result of parsing each kind of expression. Be sure to test not only simple constant ASTs, like you would get from (parse 3), but also those that need to be expressed as quotations, such as you would get from (parse '(quote x)).
  7. Do exercises 10.24-10.26 on pages 356-357. Contrary to what exercise 10.26 says, you won't need to change make-mini-scheme-version-of, because the version we have provided from page 358 already incorporates the needed modifications. Test your read-eval-print loop as shown on page 358 and in other ways. (When comparing your output to that shown in the book, don't be concerned if the subexpressions of an expression are evaluated in a different order.)
  8. Do exercise 10.27 on page 359 and test. (Again, when comparing your output to that shown in the book, don't be concerned if the subexpressions of an expression are evaluated in a different order.)


As usual, write up a lab report that explains all of what you did to an audience generally knowledgeable about Scheme and computing, but ignorant of specifically what you did.

Course web site:
Instructor: Max Hailperin <>
Other lab instructor: Karl Knight <>