www.delorie.com/gnu/docs/kawa/kawa-tour_6.html

search

	Buy GNU books!

Kawa: Compiling Scheme to Java

1.5 Mixed-type arithmetic

Many operations are overloaded to have different definitions depending on the argument types. The classic examples are the functions of arithmetic such as `+', which needs to use different algorithms depending on the argument types. If there is a fixed and reasonably small set of number types (as is the case with standard Scheme), then we can just enumerate each possibility. However, the Kawa system is meant to be more extensible and support adding new number types.

The solution is straight-forward in the case of a one-operand function such as "negate", since we can use method overriding and virtual method calls to dynamically select the correct method. However, it is more difficult in the case of a binary method like `+', since classic object-oriented languages (including Java) only support dynamic method selection using the type of the first argument ("this"). Common Lisp and some Scheme dialects support dynamic method selection using all the arguments, and in fact the problem of binary arithmetic operations is probably the most obvious example where "multi-dispatch" is useful.

Since Java does not have multi-dispatch, we have to solve the problem in other ways. Smalltalk has the same problems, and solved it using "coercive generality": Each number class has a generality number, and operands of lower generality are converted to the class with the higher generality. This is inefficient because of all the conversions and temporary objects (see T. A. Budd: Gneralized arithmetic in C++. Journal of Object-Oriented Programming, 3(6):11--22, Feb. 1991, and it is limited to what extent you can add new kinds of number types.

In "double dispatch" D. Ingalls: A simple technique for handling multiple polymorphism. ACM SIGPLAN Notices, 21(11):347--349, Nov. 1986., the expression x-y is implemented as x.sub(y). Assuming the (run-time) class of x is Tx and that of y is Ty, this causes the sub method defined in Tx to be invoked, which just does y.subTx(x). That invokes the subTx method defined in Ty which can without further testing do the subtraction for types Tx and Ty.

The problem with this approach is that it is difficult to add a new Tz class, since you have to also add subTz methods in all the existing number classes, not to mention addTz and all the other operations.

In Kawa, x-y is also implemented by x.sub(y). The sub method of Tx checks if Ty is one of the types it knows how to handle. If so, it does the subtraction and returns the result itself. Otherwise, Tx.sub does y.sub_reversed(x). This invokes Ty.sub_reversed (or sub_reversed as defined in a super-class of Ty). Now Ty (or one of its super-classes) gets a chance to see if it knows how to subtract itself from a Tx object.

The advantage of this scheme is flexibility. The knowledge of how to handle a binary operation for types Tx and Ty can be in either of Tx or Ty or either of their super-classes. This makes is easier to add new classes without having to modify existing ones.