# SICP Solutions

### Section - 2.5 - Systems with Generic Operations

#### Exercise 2.92

It took quite some time to get it working. At first glance it looked simple but :) This exercise felt boring as it was just a tedious task without any new underlying concepts. Perhaps I should not have done it but when I realised this I found myself in the middle of the solution so went ahead.

The outline of my approach:

There are two parts (i) Convert polynomial cannonical (ii) Changing operations add and mul to work with cannonical types.

Note: To decide priority - alphabetic ordering of the variable names is used.

(i) Convert to cannonial form:

This is easy. Lets assume we have add and mul that supports canonical form. Since our polynomial are represented as a sum of product form - we take every product, lets call it term, we just need to convert each of these terms(product) into canonical forms and add them! Now think of each term - it is a product of cofficient and power/order of the variable. Just convert the coefficient into cannonical and mul the converted coefficient with our variable raised to appropriate power/order.

The next problem is how to integrate this conversion in our existing system - Just convert to canonical form in the public api to make-polynomial. This should not be in the internal api to make polynomial because then it will go into loop.

Thats it! Here is the code:

(ii) Changing operations add and mul to work with canonical forms.

This is also easy:

We assume that all polynomicals passed to add or mul are canonical forms.

For add: if two polynomials are in different variables we just need to add the polynomial with lower priority variable as a constant in polynomial with higher priority variable. This can be done easily just be converting or raising the lower type polynomial into higher one. For eg: To add $\, (5 x^2 + 10 x + 100 x^0)$ and $(y^3 + 2 y^2 + 11 y^0) \,$. Here we first convert the lower priority polynomial(with variable $y$) into $(y^3 + 2 y^2 + 11 y^0) x^0$. Now we can just add them using our old procedure because now both polynomials are of same variable. The rest of the things will be taken cared by recursion :) Except for the case when we add/mul a polynomial and a number - This operation is not supported with our older add method.

• One way to do this is to raise number into polynomial. I did not feel correct to raise numbers as it raises the question of which type of variable should the number be raised into.
• Since we are using add which is internally calls apply-generic - it is difficult to do without raising the number to polynomial. (Note that in a way it appears a limitation of apply-generic. It would have been better if we have an apply-generic where we should be able to add polynomial and any type of number. Thus a way to identify types of number. Also another problem to notice is that suppose even if we allowed to raise a number to polynomial and we wrote a raise to raise complex to polynomial then all our numbers will be raised to complex types and in few situation they will not be dropped to basic type(when there is no arithmetic operation is performed)).
• Now, To avoid raising types I need to identify the places in polynomial package where a number and polynomial are added or multiplied. This is easy to spot - Its only the places where we are adding coefficients by calling generic add.
• Now instead of using generic add we use our new hybrid-add that checks if both arguments are number or polynomial then it calls generic add else if we add/mul polynomial by a constant it creates a new polynomial with this constant and then performs the actual operation(add-poly/mul-poly). Note that another approach can be to still use apply-generic by installing/putting appropriate procedures in the hash table. The problem is apply-generic strips off type-tag before calling the installed procedure. This is a probelm - consider for eg when we add the number to the polynomial - we are not adding directly - we are adding this number by adding this as a term with 0 order to the polynomial. Thus the actual number addition may not even happen if the polynomial does not have any constant term before. Now suppose later on this polynomial is added to another polynomial(both having constant terms) then addition of the last term/constant term will happen again by add. But at this point this add will not work because - we stripped the type-tag from the number in the last step!
• The above point brings an interesting question - How to handle such situation where all we need to an operation that can take any type of number and do not strips the type-tags because we are not actually doing any number arithmetic in there? Hope this gets answered in later part of the book. Perhaps one solution can be that apply-generic does not do any untagging/tagging - its just left to the individual packages. -As of now I just went ahead with mixed-add which does some work that should actually be done by apply-generic.

For mul: this is similar to add - just convert lower variable polynomial into higher and multiply!

Both steps look really simple but it took me sometime to arrive at these steps as well as some time also spent in problems with tagging. Internal procedures in general do not need to tag the types but we can not avoid them completely even in the internal procedures and need to pay attention to every operation whether we need to remove type-tag before proceeding or not. This made me realise that how easy it is in languages where late-binding is supported.

Another problem arises while adding if some coefficient becomes zero or while multiplying by a constant - these details are taken cared in procedure make-poly-with-term.

Note: I dont support operation for adding a number and a polynomial directly from outside - Outer api only supports addition/multiplication of polynomials but if situation happens when carrying out the operation - number and polynomial are added/multiplied then it works as mentioned in the above approach.

So here goes the complete code(Examples are at the bottom):

Examples/Output