Term-rewriting evaluator

Relevant sections in text: 1.1, 2.3

This is an extensive assignment, which develops an alternative view of evaluation to the one presented in chapters 3 and 4 of the text. This view extends the informal substitution model of section 1.1 to a full term-rewriting model for evaluating Scheme expressions. Working through this assignment provides experience with the formal view of language syntax and semantics, as well as considerable exercise with symbolic manipulation.

In order to do the assignment, students will need to read the supplementary handout (provided below), which describes term rewriting and the evaluation model.

We are grateful to Prof. Albert Meyer of MIT for developing this assignment and the underlying model.

Files for download:

ps4.tex TeX source for the assignment.
ps4.ps Postscript file for printing the assignment
trnotes.tex TeX source for the supplementary handout.
trnotes.ps Postscript file for printing the supplementary handout.
Scheme source code required for this assignment.

Copyright © 1985-1996 Massachusetts Institute of Technology.
The material in these problem sets may be duplicated, modified, and redistributed for any non-commercial use in conjunction with the book Structure and Interpretation of Computer Programs.

Return to sample assignment page

Return to SICP page

Last modified August 30, 1996