SICP 2.5.3 Exercises

August 7, 2016 11:34

In this section the generic arithmetic system gets stretched even further, by adding the ability to work with polynomials. It’s not that hard to treat polynomials as ‘numbers’ in this manner, as long as we keep to the restrictions in the book. The generic nature of the system allows us to define the operations pretty much however we’d like, as there are no required properties of the implementation. In theory, the ‘add’ operation doesn’t even have to be the inverse of ‘subtracting’ at all. However, such a system likely wouldn’t be of any practical use.

The generic arithmetic system is in its final form as another library file, based on my own solutions. I would heavily recommend, however, that you replace it with your own system from 2.5.2, unless you did not complete those exercises. It’s an important part of the process to see how the choices you made in prior sections affect how the system works as more types are added. It is also an exercise in making sure all necessary elements of your system are in place when re-using code. To make sure it works initially, your system should pass the tests provided from the last section, which have not changed.

Of course in the ideal case, our system would be designed well enough that we don’t have to go back and change it due to a new addition, but occasionally a flaw is revealed that requires an update. We also want to ensure that no new change made ends up causing previously working parts to break. For this reason, I’d recommend that you continue running all tests after any changes to the generic arithmetic file, just to make sure all is working as intended.

For testing polynomials, I’ve continued with the approach of checking if the calculations are consistent with some expected arithmetic properties. The testing approach has been slightly altered, however, with the ability to selectively pick the properties that are valid for that operation. This avoids the problem with tests that always fail when the property doesn’t apply (as happened previously with integers). The new polynomial-specific tests are located in ‘poly-tests.scm’. This is another file that should go in the library directory.

Because the operation tests require the equ? operator to be defined for polynomials, we need a definition of polynomial equality. I’ve added definitions for this to the file, but they will not automatically work. They must to be inserted into an ‘install’ block for the polynomials, as they depend on specifically defined ‘local’ operations to get to the terms. In the later exercises, only a template is provided for equality, as the definition may vary depending on your approach.

Exercise 2.91 requires a portion of the procedure to be implemented, and then an implementation of div-poly itself. The tests are run only via the div-poly operation. These tests make use of poly-quotient and poly-remainder accessor procedures, which should get the proper result value from whatever result div-poly produces. You may need to alter those accessors so that the testing works properly with your implementation of div-poly.

The solutions post for this section will only deal with the exercises up to 2.92. The final ‘extended exercise’ section will be dealt with in a separate post.

Exercises 2.5.3

Generic Arithmetic system definitions

Polynomial Tests