SICP 3.3.3 Exercises

August 11, 2019 10:54

We’ve finally reached the point referred to by the text way back in Section 2.4.3, when data tables were first used. We can now find out how to make them. Something to note here is that the table used back then (for the generic arithmetic system) had ‘operation’ and ‘type’ as its arguments; the actual implementation of tables doesn’t really assign particular meaning to its arguments. It just labels them as ‘keys’. All that matters is that whatever is used as the storage key is the same thing used for lookup in the same table, and that there is some way to match them. In this table, the actual comparison is using equal?, since the table will use assoc to find matches. (As a technical note, the data table file used for 2.4.3 used the built-in Scheme version of assoc, which actually relies on eq? for comparison, but the idea of generic ‘keys’ that simply need to match somehow remains the same.)

This marks one of the moments when we’ve learned enough about how to do something that we’re capable of building a key element of the underlying ‘support’ procedures that we used to rely on. As the book goes on, we’ll see that ever more of those will be something we learn to implement ourselves, even to the heart of the interpreter itself. That is indeed very much what the ‘Structure’ of the text’s title is getting at.

Testing here relies once again on the testing functions file from the library. If it’s already configured for your interpreter, you shouldn’t need to change it. The tests themselves still require some observation, however. Initially the test sequence for Exercise 3.24 is run using a procedure that is expected to fail. A list of failure or error messages is the intended outcome. The test sequence is then run against a table that should pass all the tests. It’s not strictly necessary to run the ‘failing’ table first, but it’s a potentially useful comparison when trying to figure out that the tables are working as intended.

In Exercise 3.25, another test sequence is provided. These tests may need to be modified, depending on your own implementation of the arbitrary-key table. An additional insert-and-test procedure is included that does an insertion and immediately checks that the value is in the table. This is wrapped in a single procedure so that errors during insertion do not cause an exit, although bear in mind that any errors that occur during execution of the sequence likely render later results invalid.

The last two exercises do not strictly require any implementation, but a short example is provided in the file, and the procedures from the text are included. This gives an opportunity for experimentation.

Exercises 3.3.3.

Testing functions