SICP Section 2.5

So, four months after I started and more than 90 solved exercises, I can say Alhamdulillaah, chapter 2 is done! Section 2.5 was among the most challenging; the exercises revolved around building large, easily extensible software systems. And here are the thoughts again :)

1. Coercion

The section revealed the importance of coercion in software development by creating a math system for various numeric types (e.g., integers, rational, real, and complex numbers). Since Scheme is not an OOP language, procedures were used to encapsulate each numeric type’s functionality and ‘install’ them into the system. A generic apply function multiplexes routing calls to the matching number type interface.

The challenge was handling mixed operations (e.g. adding an integer to a complex number or vice versa). Since numeric types are progressively subsets of one another (i.e. an integer is also a complex number but not vice versa), it is possible to build the following hierarchy of types.

integer -> rational -> real ->complex

By leveraging this hierarchy, it becomes possible to perform arithmetic operations on a wide variety of number types. The system just needs to ‘raise’ all the numbers to the topmost type in the hierarchy and then invoke the arithmetic operation.

Let’s take it further; if ‘raise’ is possible, then surely ‘demote’ can be done too! A good application of this is ensuring that the results of ‘raised’ operations are in their simplest terms. For example, the result of adding these mixed numbers types: 1, 1 – i, 2.0, -1 + i is 3 + 0i. The result can be progressively reduced to the integer 3, as shown below:

3 + 0i -> 3.0 -> 3 / 1 -> 3

And the icing on the cake? There is no need to write a demote function! The earlier raise procedure should demote number types if its hierarchy of types is reversed.

This assumes the system already supports two-way converters for each boundary of the hierarchy (e.g., integer->rational and rational->integer). There is no need for an integer->real converter since integers can be promoted to rational numbers and then to real numbers.

Neat huh?

2. Extending a system

Assume the system above has to support polynomial arithmetic. It turns out it is quite simple – why not view polynomials as another layer in the hierarchy of types? This new hierarchy is shown below:

integer -> rational -> real ->complex->polynomial

It’s an interesting abstraction, isn’t it? It works, too, once all the interfaces are implemented. Designing software is indeed an art.

One extra learning point was the representation of polynomials: the sparse and dense approaches had pros and cons. A better fix was to enable the system to support both representation formats (simple trick: convert one form to the other, and everything should be all good :) ).

Another interesting trick was polynomial subtraction; there is really no need to implement subtract if you already have addition implemented. All you have to do is add ‘negated’ versions of each polynomial term. Simple but powerful.

On to chapter 3 insha Allaah!