This is a quote from SICP about coercion. This section talks about the arithmetic package with ordinary numbers, rational numbers and complex numbers and doing cross type operations on them (E.G. adding a complex number to an ordinary number.)
This coercion scheme has many advantages over the method of defining explicit cross-type operations, as outlined above. Although we still need to write coercion procedures to relate the types (possibly N^2 procedures for a system with N types), we need to write only one procedure for each pair of types rather than a different procedure for each collection of types and each generic operation.
I'm confused on this line:
"possibly N^2 procedures for a system with N types"
Let's take the arithmetic package example. The operations that deel with two ordinary numbers (scheme-number scheme-number), two rational numbers (rational rational) and two complex numbers (complex complex) are the same types, so they are not included in the coercion procedures.
We have three types, these are the coercion procedures I can think of with just two arguments.
(scheme-number rational) (scheme-number complex) (rational scheme-number) (rational complex) (complex scheme-number) (complex rational)
These are not n^2 coercion procedures. There are only six coercion procedures here, not 9. I think I'm not really understanding this part of the text at all. Can someone explain what I missed?
Finally, here's a footnote regarding this part of the text.
If we are clever, we can usually get by with fewer than N^2 coercion procedures. For instance, if we know how to convert from type 1 to type 2 and from type 2 to type 3, then we can use this knowledge to convert from type 1 to type 3. This can greatly decrease the number of coercion procedures we need to supply explicitly when we add a new type to the system.'
From what I understand if we can convert an ordinary number to a rational number, then convert that rational number into a complex number, we wouldn't need a procedure that converts an ordinary into a complex. Is that right?
Can anyone explain this more clearly?
The first part I understood as O(N^2): if there are 10 types, we'll need circa 100 operations (in reality, 90). As for the second part, you are right: we can build up a composable coercion. However, as far as I could think of its implementation, this will require building up a directed graph with nodes = types and edges = coercions. And then finding a right coercions will involve walking through the graph to find the path from one node to another (not cheap!).
PS. To make things even more complicated: both complex and rationals can act as containers for other types, e.g. complex of rationals, complex of integers, rational of integers (simplest version), rational of polynomials, etc. Then the question of coercion becomes even worse: consider adding 1+2i, 2/3 and 3.0 - first everything needs to be converted into their respective complex representations (1+2i, 2/3+0/1i, 3.0+0.0i) and only then coerce it all to floats inside complex... TL;DR: numbers coercion is a nightmare, I'm glad I don't have to do it myself!