Modifying Evaluators

MCS-178: Introduction to Computer Science II
Max Hailperin, Fall 2001

Due: September 24th, at the beginning of class


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.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.


It's critical (especially in this lab) to test each change you make to the code as soon as possible: Write a few lines of code, test them, write a few more, test them, repeat. By coding this way, when you find a bug, you'll usually know exactly where the bug is, saving you time and frustration. For the first few challenging exercises below, there are guidelines for how to do this.


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

In Lab

  1. You should open the file ~mc28/labs/evaluators/micro-scheme.scm and use the "Save Definitions As..." command to save a private copy in your own directory, which you will modify in the first few exercises. Use the ``Execute'' button 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 ``Break'' button at the top of the window.
  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 299 of the textbook. You should use the ``Copy'' and ``Paste'' commands in Dr. Scheme 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 page 303 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)))

    Be sure to try to test every change to the code you make as soon as possible. This way, if there is a bug, you'll know exactly where to look. For this exercise, for example, you first may wish to make a temporary pattern/action for the with statement that allows you to test the pattern matching, before concerning yourself with how these expressions should actually be turned into ASTs. In particular, you can temporarily use the following action:

     (lambda (variable value-expression body)
       (display "with expression parsed with variable ")
       (write variable)
       (display ", value expression ")
       (write value-expression)
       (display ", and body ")
       (write body)
       (make-constant-ast 7))
    This will of course not behave at all as with expressions should: it will make all with expressions always evaluate to 7. However, this "testing stub" will allow you to see that with expressions are being correctly pattern matched. Once you have checked that, you can replace the action with a real one.
  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 ~mc28/labs/evaluators/mini-scheme.scm and use the "Save Definitions As..." command to save a private copy in your own directory, which you will modify in the subsequent exercises. 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.3 and earlier chapters. Finally, this file also contains the definitions from section 10.5 of unparse (p. 312), evaluate-in-at and display-times (p. 313), make-application-ast (p. 314), write-with-at and blank-line-at (p. 321), and evaluate-in-at and evaluate-additional-in-at (p. 322).

    Note that you won't be able to run mini-scheme until you have completed the following two portions of the lab.

  6. Do exercise 10.22 on pages 312-313 and test each AST constructor immediately after you've changed it by unparsing the result of parsing an appropriate expression. (If you find this confusing, be sure to ask!) As the exercise says, some constants need to be quoted and others not.
  7. Do exercises 10.24-10.26 on pages 314-315. Test your read-eval-print loop as shown on page 315 and in other ways.
  8. Do exercise 10.27-10.28 on page 322 and test. You'll need to use the new version of evaluate-in-at (page 322) which is commented out of the bottom of the file mini-scheme.scm.

    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.

  9. Optional: do exercises 10.29 and/or exercise 10.30.


As usual, write up a lab report that explains your final product to an audience generally knowledgeable about Scheme and computing, but ignorant of specifically what you did. Be sure to clearly describe how you tested each procedure as well as the final program. Follow the guidelines for lab reports.