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. |
smeval.scm
smfresh.scm
smscope.scm
smstep.scm
smsyntax.scm
temp.scm
tests.scm
| 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
Last modified August 30, 1996