Multiple polymorphism / multi-methods

[dje@scs.carleton.ca (Danny Jared Epstein)]

I read in the SELF 1.0 / 1.1 manual that you were considering adding
multi-methods to SELF:

> SELF might support multimethods, i.e. dispatching on the type of the
> receiver and one or more arguments (instead of dispatching just on
> the type of the receiver).

I have always considered multiple polymorphism (a.k.a. multi-methods)
a good idea.  I would like to try to convince you of this, as well as
see whether any of you in self-interest land have any thoughts on the
matter.

Multiple polymorphism is a generalization of message passing, so you
can still using message passing most of the time, keeping the
corresponding mental model that goes with it.  It eliminates the need
to do explicit type checking in most cases.  Double (and triple and
higher) dispatching eliminates the speed problems associated with
explicit type checking by turning around and sending a message to the
argument including the type of the receiver in its name.  For example,
integer's '+' method is implemented as 'arg addFromInteger: self',
where 'addFromInteger:' is implemented in both integer and float.  The
problem with double dispatching is that it is messy, particularly when
you have to dispatch on three or more arguments.

The most common use of multiple polymorphism would be for arithmetic
operators such as '+'.  There would be separate methods for 'integer +
integer' and 'integer + float', so no explicit type checking or double
dispatching would be needed.  Another example of where multiple
polymorphism would be useful is for the displayOn: method.  Let's say
there are four types of forms, regular ones (1 bit plane), opaque ones
(2 bit planes: one is a mask), color ones (many bit planes), and
opaque color ones (many bit planes: one is a mask).  We would like to
be able to display any kind of form on any other kind of form using
any of several rules/modes (copy, reverse, etc).  This could be
implemented nicely as a multi-method:

   form             displayOn: form            At: point Rule: copy
   opaqueForm                  opaqueForm                      reverse
   colorForm                   colorForm                       drawBlack
   opaqueColorForm             opaqueColorForm                 eraseWhite

There are 4 x 4 x 4 = 64 combinations, most of which would be valid
methods.  Can you imagine implementing this using triple dispatching?
Ugh!

Now that I've tried to convince you that multiple polymorphism is
useful, I'll discuss how it could be implemented in SELF.  Adding
multiple polymorphism to a class-based language can be done in the
following way.  The method dispatch is done by searching in a directed
acyclic graph (DAG) of methods for a particular message with the
following property:

   A method X is a descendant (non-strict) of another method Y in the
   DAG if the classes of X's arguments are (non-strict) subclasses of
   the corresponding classes of Y's arguments.

The search is done by logically inserting a node for the classes of
the actual arguments and then searching up from there.  If there are
several parents, then there is an ambiguity, much like the ambiguities
that occur in multiple inheritance.  In a prototype-based language
such as SELF, we would replace the 'subclass' relation with the
'inherit' relation:

   A method X is a descendant (non-strict) of another method Y in the
   DAG if X's arguments inherit from (non-strict) Y's arguments.

Of course, I haven't dealt with the issue of efficiency: how this
method lookup can be optimized.  Also, how does multiple polymorphism
interact with other language features such as multiple inheritance and
privacy.  I don't want to trivialize the problem - I know it is
difficult.

What are your thoughts and plans regarding multi-methods in SELF?

- Danny Epstein
  dje@scs.carleton.ca