SICP 3.3.1 Exercises

February 21, 2019 10:45

The majority of the exercises in this section are meant to be done manually, which is to say the results are to be worked out without using the interpreter. In most cases, then, checking the code with the interpreter is only useful verification of a correct result. The file will include the expressions for the manual exercises, as well as test expressions for the other exercises.

For the ones that do require the interpreter, it may be easily possible to check what value is being produced, yet that may not be the main point of the exercise. They should be worked out, or at least attempted to be worked out, before being executed/implemented, to gain a better understanding of how the program is actually working; we may not have a complete model of evaluation yet, but we’re growing pretty close to it.

A few of the exercises require diagrams, which will be both box-and-pointer for lists, and environment diagrams. Note that while Exercise 3-16 only requires the box-and-pointer diagrams, it will be necessary to write the solutions into the file, in order to test the correct version in the exercise that follows it. There is one that leads to an infinite loop, however. There’s no way to actually test that, other than by putting it in the file and noting that it won’t exit quickly. That should still be done, to make sure that it doesn’t actually exit when it’s not expected to.

There’s one more aspect of this section that’s important if you are using Dr Racket/Pretty Big as your version of Scheme. Racket-based langauges don’t allow the use of set-car! and set-cdr! with normally-created lists, in order to make list processing faster in general. It does allow for ‘mutable’ lists, but they can’t be mixed with ordinary lists, and the procedures that work on mutable lists are all preceded with an m (i.e. mcar, mcdr, and set-mcar!). One approach would be to use these mutable forms, but I avoid that, in order for the code to be portable to other implementations of Scheme.

For this set of exercises, if using Dr Racket, I switched the language to R5RS, also known as ‘Scheme version 5’. This implements Scheme according to the standard closer to what the text uses, and all lists are mutable by default. You will also need to ensure that the box for ‘Disallow redifinition of initial bindings’ is unchecked in Dr Racket, or else it won’t be possible to write two versions of the same procedure in Exercise 3-19. (Technically you can use set! with a lambda expression to redefine a procedure if this isn’t enabled. That’s better in practice where you normally would not ever want to overwrite a procedure without being very aware of what you are doing, but it’s a little cumbersome for our purposes at present.)

Exercises 3.3.1.