MC28 Lab 1: Modifying Evaluators (Fall 1996)

Due: September 25, 1996


You will work on this lab as a member or 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.2 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.3 in the ways shown in section 10.4 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 introductory material at the beginning of chapter 10, all of sections 10.1 and 10.2, 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.2 of the text, along with some necessary definitions from section 10.1 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.9 and 10.10 on page 322 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.9, you could add cons, car, cdr, and null?, so that you can do list processing in Micro-Scheme. For 10.10, 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.13 from pages 326-327 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.4. 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.3, with the exception of those superseded in section 10.4, and it also contains relevant definitions from 10.2 and earlier chapters. Finally, this file also contains the definitions from section 10.4 of unparse (p.335), evaluate-in-at and display-times (p. 337), make-application-ast (p. 338), and make-mini-scheme-version-of (p. 340). 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.
  6. Do exercise 10.19 on page 336 and test your procedure by unparsing the result of parsing each kind of expression.
  7. Do exercises 10.21-10.23 on pages 338-339. Contrary to what exercise 10.23 says, you won't need to change make-mini-scheme-version-of, because the version we have provided from page 340 already incorporates the needed modifications. Test your read-eval-print loop as shown on page 340 and in other ways.
  8. Do exercise 10.24 on pages 340-341 and test. Since you are supposed to show the value among other things of procedure ASTs (i.e., lambda expressions), be sure that your test involves some lambda expressions, unlike the test shown in the book.


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 <>
Lab instructor: David Wolfe <>