Multiple polymorphism / multi-methods

[Dave Ungar]

	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.

Congrats, you have convinced us! (Actually, we were already)


	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.

maybe yes, maybe no. Certainly yes for no-argument sends

        It eliminates the need
	to do explicit type checking in most cases.

I hope so, but. . 
      
        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.


Exactly!

	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!


Yes, we had thought of the very same examples. But I think it will used differently than we can guess.

	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.

I basically agree.

	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.

yes

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

_Restart (i.e. go to the top and read :-)

	- Danny Epstein
	  dje at scs.carleton.ca


Dave