Multimethods 101 (was Re: Multiple dispatch (Re: Q: Python 2.0 preliminary features?))

[Louis Madon]

[I'm cross-posting this to comp.lang.dylan as I think the Dylaners' may
be able to cast more light on this and/or correct any short-comings in
my thinking] 


In the beginning Greg Ewing wrote:

> Suppose AA is a subclass of A, and BB is a subclass of B,
> and there are methods defined for the combinations
> foo(A, B), foo(AA, B) and foo(A, BB).
> 
> Now, if you make a call with the combination foo(AA, BB),
> which method should get called?


Several people said its "ambiguous".


Then Amit Patel wrote:

> I don't know I'm calling foo(AA, BB).  All I know is that I have an "A
> like" object and a "B like" object (Python examples: file-like object
> and sequence).  I then call foo on these two arguments, and the system
> complains.
> 
> Therefore it can't be my fault when the foo(AA, BB) call fails.
> 
> My caller (1) doesn't know I'm calling foo (after all, why should he
> know the implementation details of my class?), and (2) only gave me
> one of the two arguments, and therefore is unaware of the combination
> that is about to take place.
> 
> Therefore it can't be my caller's fault when foo(AA, BB) fails.
> 
> When defining foo(AA, B), the author of AA may not know about foo(A,
> BB), so it can't be AA's fault if the call fails.
> 
> When defining foo(A, BB), the author of BB may not know about foo(AA,
> B), so it can't be BB's fault if the call fails.
> 
> Everyone wrote "correct" code but when it's put together it fails.


Ok, so the crux of your argument appears to be:

Combining pretested libraries can introduce new cases to a multimethod
for which there is no applicable/unambiguous handler

- therefore -

multiple dispatch is a bad idea.   




I think this can be visualised like so:

1st authors'   2nd authors'       combined 
    view           view             view

       B           B    BB          B    BB
    A  .        A  .    .        A  .    .
    AA .                         AA .


(Note: '.' indicates we have a method foo defined for that pair of
arguments)

So each author covered all possible cases from their point of view.  Yet
when we combine the libraries a hole appears in the resulting matrix for
foo(AA, BB).  Now until you combined those libraries there was no way a
foo(AA, BB) call could have arisen.  But after you do, and you start
using AA's and BB's together for the first time you suddenly find that
this method 'foo' throws an exception.  Perhaps your new code didn't
even call foo directly, perhaps it was called indirectly in some deeply
nested function within one of the *pretested* libraries.  You object and
ask how can this possibly be considered a good paradigm?  

The answer is that libraries of multimethods can export *abstract*
functionality.  A multimethod is not a concrete method, it is a higher
level abstraction that defines an operation conceptually. A multimethod
and its implementing method(s) are somewhat analogous to an abstract
interface and its concrete realization(s).

So a multimethod is a conceptual operation but the full generality of
that concept has not neccesarily been implemented.  The system however
(either at compile time or at run time) will always tell you when you
try to invoke unimplemented functionality.

So we could have a 'copy' operation that copies anything to anything, an
'add' operation that adds anything to anything and a 'find' operation
that finds anything in anything using anything as comparison criteria. 
Now we obviously can't implement such operations in totality, but we can
implement a few concrete cases to cover whats needed initially.  As
needs grow, implementation for more cases can be added, but the
interface stays the same.  This has a number of advantages :-

(a) The number of interfaces a programmer must learn is smaller since
procedures can be specified in terms of generalised operations. Say we
need to copy a over b, then use copy(a, b).  Once you know it then you
know the procedure for copying (cf. 'cp' command in unix - one command,
many types of objects). 

(b) Corollary to (a) - The number of interfaces a programmer must create
is smaller, since often the extra  functionality needed will naturally
belong within existing multimethods. Adding new methods to a multimethod
does not require invasive editing of some monolithic procedure nor even
modifying existing class definitions.  Therefore you should be able to
add the new method(s) even if the multimethod is partly implemented in a
library you don't control.   

(c) Its easier to create truly reusable code. By defining a process in
terms of multimethods you are describing the 'essence' of that process
since you don't have to bind it directly to concrete types or make
unneccesary assumptions about the types being operated upon. So for
example, { a = read(src) write(log, a) return a } is a generalised
procedure for reading some kind of data (from some sort of source
object), writing that data to some kind of log and then returning that
data (a logging read).  As more methods are added to the read and write
multimethods to handle more concrete types, this increased know-how
automatically flows on to all such procedures.  This also implies looser
coupling / greater adaptability.    



In a related post on a numeric library example, Amit Patel said:

> Taken separately, each module is great.  It defines the new type's
> interaction with the built in numeric types.
>
> But together, who defines what it means to do complex+rational?  There
> are gaps in the dispatch table.  If gaps lead to coercions, who
> decides if complex can be coerced to rational or if rational can be
> coerced to complex?
>
> With multiple dispatch it seems like you can't combine independently
> written modules without writing some "glue".  The person using the
> modules may not be qualified to make those decisions.  :-(

If their code required (directly or indirectly) the ability to add
complex with rational then it has to be provided.  Multimethods don't
call up functionality randomly, it gets called up because its needed. 
If they were not using multiple dispatch, they would still need to write
the "glue", but they wouldn't have a well defined slot to put the new
functionality into.
 

Louis.