From: Marcin 'Qrczak' Kowalczyk <qrczak@...>
Date: 2002-11-02T02:42:54+09:00
Subject: Re: Multimethods (was Re: Larry Wall's comments on Ruby)

Wed, 11 Sep 2002 23:56:39 +0900, Dan Sugalski <dan@sidhe.org> pisze:

> For example, if you have:
> 
>     a = b + c
> 
> b and c are both integers, you want to return an integer. If one is 
> an integer and the other a float, you want to return a float but do 
> integer math (as its faster to add an int and a float than it is to 
> add two floats),
[...]

I've never used CLOS but I'm experimenting with a CLOS-like dispatch
mechanism, simpler than CLOS yet I believe powerful enough. It's not
in Ruby (but can be implemented in Ruby), sorry for off-topic...

Each generic function contains branches (specific definitions)
identified by finite sequences of types (for initial arguments).
The length is usually 1 (single dispatch), 2 (double dispatch)
or 0 (default version).

A type has a sequence of indirect supertypes (computed from direct
supertypes, i.e. multiply inherited). The dispatch goes like this:

Consider the maximal sequence length present in the given generic
function for which there are enough arguments. Consider the type of
the first argument. Find sequences which start with it. Consider
the next argument type. Narrow the search to matching sequences,
etc. If at some point there are no more sequences, look for the next
supertype instead. If you run out of supertypes, backtrack and look
at the next supertype in the previous step.

When the whole sequence length is matched, you found the branch.
Otherwise try again with the shorter length.

It's easy to implement. For efficiency, after you found a match
by using some supertypes it's inserted into the generic function
so the next time it will be found immediately.

Now, how I'm using it for mixed type arithmetic. The inheritance
graph looks like this:

   Integer <-- Rational <-- Real <-- Complex
      |           |           |         |
      v           v           v         v
     Int        Ratio       Float   ComplexFloat

The lower row lists specific types, e.g. Float implies a concrete
representation. The upper row lists abstract types, e.g. Real means
that the object represents a real number (it might be implemented as
Int if it happens to be an integer).

Now for example the * operator is implemented for (Int,Int),
(Integer,Integer), (Ratio,Ratio) etc. Branches from the lower row
perform the multiplication in the obvious way: both arguments have
a concrete representation.

Then the (Real,Real) branch for example converts both arguments to the
"canonical" Real type, Float (using a singly-dispatched conversion
function called float), and performs the multiplication in Floats.

You can add specific variants like Float*Int if needed for efficiency.
For some types operations don't need to be symmtetric, e.g.
Sequence*Int for replication (where Sequence is an abstract type
covering String and List among others), String+Int (working for
single-character strings only, "p"+2 == "r", so you can write x+1
instead of x.succ), Date+TimeInterval, TimeInterval*Rational etc.
They can be added incrementally in any order.

-- 
  __("<      Marcin Kowalczyk
  \__/     qrczak@knm.org.pl
   ^^    http://qrnik.knm.org.pl/~qrczak/