MASSACHVSETTS INSTITVTE OF TECHNOLOGY
Department of Electrical Engineering and Computer Science
6.001---Structure and Interpretation of Computer Programs
Spring Semester, 1999

Recitation -- Wednesday, March 10

1. Generic Operations

2. An Example

Let's walk through the evaluation of (mul x y) with the tree structures below. Notice the pattern:

1. Find the correct procedure based on type.
2. Strip off the tag to get to the data.
3. Call the procedure with the data arguments (maybe recursively calling ``smart procedures'').
4. Attach the tag to the result.

3. Comments on Generic Operations

1. Adding New Types and Operators

• How would we add a new type (say polynomials)?
  HiddenAnswer For the dispatch method, each operator must be changed to account for the new type. EndOfAnswer
  HiddenAnswer For the table method, we need another put for each operator. EndOfAnswer
• How would we add a new operator (say divide)?
  HiddenAnswer For the dispatch method, write a new operator that has the proper dispatch table EndOfAnswer
  HiddenAnswer For the table method, we need another put for each type. EndOfAnswer

4. Representing Sets

A set is a mathematical object defined as a collection of unique objects (i.e. an element appears at most once in a set). To model sets, we need to build an implementation that supports several operations. Build an implementation for sets of symbols, using unordered lists as the basic representation. Try to use map, filter, and accumulate where appropriate.

• About this document ...