Ex. 2.81

Adding the ‘self-coercion’ routines causes a problem. If a matching procedure is not found in the table, apply-generic will attempt to coerce the arguments. If a coercion exists, even if it coerces the type to its current type, then a new search for a procedure will commence with the ‘new’ types. That means that if coercion routines exist for all types, the search for a procedure will never exit.

The answer to part b, and a better explanation for the first part, can be found by looking at the relevant portion of apply-generic. This is where coercion potentially occurs:

...(let ((t1->t2 (get-coercion type1 type2))
	    (t2->t1 (get-coercion type2 type1))
	    )
	    (cond (t1->t2
	         (apply-generic op (t1->t2 a1) a2)
	         )
	         (t2->t1
	         (apply-generic op a1 (t2->t1 a2))
	         )
	         (else
	         (error "No method for these types"
	                (list op type-tags)
	                )
	         )
	        )

What can be seen here is that not only is self-coercion not necessary, since it will not improve the search for a matching procedure, but that in order to get the error result for no matching method, it is required that there are no coercion routines in the table for some types. The cond statement itself tests for the very existence of the coercion routines, and assumes that if they exist, then the recursive call to apply-generic will not be repeating the same values. It is only when the coercion routines do not exist (i.e. get-coercion returns false) that the “No method” error message can result and the procedure can exit if it has not found a match.

To explicitly avoid this problem in apply-generic, we can add a test for the types just ahead of the coercion lookup, which is the section just quoted. This is the solution I went for. An alternate approach, if you’d rather keep the error reporting in a single location, is to force the coercion routines (t1->t2 and t2->t1) to be false when the types match, something which could also be done in get-coercion itself.

Ex. 2.82

The approach I took followed the suggested plan of attempting to coerce the arguments, one at a time, to the type of each argument. My routine creates a list of coercion lists, where each “coercion list” is a list of procedures that, when applied to the arguments, will coerce them all to one type. Technically the coercion list, when it is applied, doesn’t really care what it’s coercing to — all it does is apply each procedure to each argument, and then use that for the next check. To avoid the problem of the infinite loops, the coercion list is created only once, and instead of coercing on apply-generic, an internal routine is used. Once a coercion list has been applied to the arguments, it will not be used again.

To create a coercion list, each argument type is used as a base to check the table for coercion routines. If no coercion routine is in the table, a placeholder of 'failed is placed in the list. Interestingly enough, this approach actually requires a ‘self-coercion’ routine, since apply-generic will now map every argument using the coercion list. We don’t rely on the table to provide such a routine, however, and simply check for a matching type and use the uncoerced procedure, which does not change the argument.

After all arguments have had a coercion list created for them, the ones which failed are removed. Note that this does mean that when two arguments of the same type occur in the argument list, there will be a duplicate coercion list created, but I consider this a minor peformance hit.

The last part of the exercise asks for cases where this approach may fail, even when appropriate coercion routines exist. One situation, suggested by the hint, is when there are mixed-type operations. Since this approach coerces all arguments to only a single type, it cannot match against procedures that accept arguments of different type. As an example, suppose an operation such as exponentiation is defined, but only if the exponent is of type real. In that case, coercing all the arguments to complex type would fail, since exponentiation of complex to complex is not allowed.

Another situation where this fails is when there is another valid type that the arguments could be coerced to, different from any of the arguments. If, for instance, the rectangular and polar numbers were not contained within the complex type, but instead could be coerced to it, operations that mixed the two types would fail, even though they could work if properly coerced.

Ex. 2.83

The raise operation for each type is not that difficult to implement. For each type, the constructor of the next higher type in the hierarchy is called, using the current value as its value. It’s merely a matter of math to properly construct the value required for the constructor: for Integer→Rational, the denominator is set to 1, for Rational→Real, the numerator is divided by the denominator, and for Real→Complex, the imaginary part is 0.

The generic raise operation is similar to the original apply-generic :

(define (raise x) 
  (let ((proc (get 'raise (type-tag x)))
        )
    (if proc
        (proc (contents x))
        x
        )
    )
  )

The table is checked to see if a raising procedure exists for that type. If so, the procedure is applied, which should return the raised value. If the procedure doesn’t exist, then the original value is returned.

The generic raise could also have been implemented in one line by simply calling apply-generic. However, since we’ve reached the point that apply-generic has been modified to be more suitable for procedures with multiple arguments, it made sense to keep raise simple, as it only ever needs one argument. This also lets us control what happens when the procedure is not found in the table.

There was no explicit indication of what to do when an unraisable value (such as a Complex number) is submitted. I choose to simply return it unchanged. This approach means that a value is always returned, but it is not necessarily a raised value. Alternate sensible approaches would be to signal an error, or return a special value (e.g. false) to show that the argument cannot be raised.

Ex. 2.84

My intention here was to keep apply-generic similar to its most recent form. This time, instead of applying a list of procedures to the arguments to get a coerced list, a new set of coerced arguments is generated. The function that generates the coerced arguments will return false if the arguments cannot be changed. Otherwise the altered set of arguments is returned, and apply-generic is called recursively.

One distinction between this version and the previous one is that only one coerced argument list is produced each time. To ensure that all possible cases are covered, we raise only the lowest argument in the list. The procedure raise-lowest accomplishes this. It steps through each argument, and produces a list with only this argument raised, and then only if the argument’s type precedence is at or below the lowest type seen. Once all the arguments have been examined, the new argument list will have at most one raised argument. If no arguments could be raised, the procedure returns false.

To indicate type precedence in a manner that will allow for future expansion, each type has an entry in the table which is a numeric value for its precedence. Types with higher precedence actually have a lower numeric value, and any value that is less than 0 is considered an ‘unraisable’ type (this is also the default for types that have no precedence entry in the table). This allows multiple type systems to be in place, and even allows two types to have the same precedence. Further adjustment might be needed for some kinds of precedence changes. Inserting a new type in place of an existing precedence level could be done by using fractional values, or by altering the table for all existing types.

Ex. 2.85

The generic project is rather similar to the generic raise; the big difference here is that false is returned when the value cannot be projected (there’s also an explict check for pairs, intended to find tagged types and avoid projecting ‘ordinary’ Scheme numbers). Each type then has its own project method stored in the table. We are also using ‘rationalizable’ Real values, so the types will raise and lower by the same steps.

That is only part of the simplification process. Generic drop has to check that the type can be projected, and that it is also equal to the original when raised back. Here’s drop:

(define (drop x)
  (let ((lowered-x (project x)))
    (cond
      ((not lowered-x) x)
      ((equ? x (raise lowered-x)) (drop lowered-x))
      (else x)
      )
    )
  )

Note the use of a cond statement. We take advantage of the fact that the cond will exit at the first matching clause to avoid attempting to raise invalid values. If (project x) returns false, we can simply return the value as-is. That way we don’t bother trying to raise something that can’t be projected.

In similar fashion to raise, my version of drop returns the value itself if it could not be changed. The other notable feature is that after a successful drop, the procedure recurses — this makes it continue to drop as far as possible. At that point the value is returned, and it’s the lowest it can possibly be.

Incorporating this into apply-generic is very easy thanks to that behavior. A simple call to drop needs to be added at the point when a valid procedure for the given types has been found. That one call will yield an answer that is dropped as far as possible, even in cases where no actual drop is performed.

Ex 2.86

The changes here, while extensive, are not quite as difficult to implement as it may appear. However, doing so may reveal hidden flaws in the system if it hasn’t been built up robustly. I ended up rewriting a lot of the earlier exercises thanks to bugs detected while completing this one.

In short, we need to change all internal procedures that use math in the complex system to ones that use generic operations. This change needs to be implemented at the level of the rectangular and polar system as well, since internally they perform differing calculations. Additionally, generic operations for several more advanced mathematic operations (such as sine or arctangent) must be implemented. Thanks to the raise operation, those only need to be defined for the Reals, since values of other types will just be raised as necessary. It is a long list of changes, but mostly involves just substitution of the procedure names.

The other big change is how to handle dropping a Complex value. In order to check the drop properly, the value must be forced to be of Real type. To handle that, I added a to-scheme-number that returns the ‘ordinary’ Scheme value for something of generic type. This is required since the constructors for the lower types still expect Scheme values as arguments. This change would no longer be required if the constructors were altered to accept generic arithmetic values as well, or by using coercion to force a Real result from other types.

Solutions 2.5.2