[Python-ideas] Democratic multiple dispatch doomed to fail (probably)

[Stephen J. Turnbull]

Arnaud Delobelle writes:
 > (Sorry I can't in-reply-to I've lost the original message)
 > 
 > Neil Toronto ntoronto at cs.byu.edu:
 > 
 > > While kicking around ideas for multiple dispatch, I came across one of
 > > Perl's implementations, and it reminded me of something Larry Wall said
 > > recently in his State of the Onion address about how types get together
 > > and democratically select a function to dispatch to. I immediately
 > > thought of Arrow's Theorem.
 > 
 > Maybe I'm wrong, but I don't think this theorem applies in the case of
 > mulitple dispatch.  The type of the argument sequence as a whole chooses
 > the best specialisation, it's not the case that each argument expresses a
 > preference.

I don't think it applies but I think a detailed analysis sheds light
on why perfect multiple dispatch is impossible.

The second part is true, individual arguments are not expressing
preferences in general (though they could, for example a generic
concatenation function could take an optional return_type argument so
that the appropriate type of sequence is constructed from scratch,
rather than sometimes requiring a possibly expensive conversion).  The
type is not doing the choosing, though.

The problem here is that what is really doing the choosing is the
application calling the function.  You could imagine a module dwim
which contains exactly one API: dwim(), which of course does the
computation needed by the application at that point.  dwim's
implementation would presumably dispatch to specializations.

Now since all dwim has is the type signature (this includes any
subtypes deducible from the value, such as "nonnegative integer", so
it's actually quite a lot of information), dwim can't work.  Eg,
search("de","dent") and append("de","dent") have the same signature
(and a lisper might even return the substring whose head matches the
pattern, so the return type might not disambiguate).

While this is an example requiring so much generality as to be
bizarre, I think it's easy to imagine situations where applications
will disagree about the exact semantics that some generic function
should have.  The generic concatenation function is one, and an
individual application might even want to have the dispatch done
differently in different parts of the program.

In sum, the problem is the real "voters" (applications) are
represented by rather limited information (argument signatures) to the
dispatcher.

So the real goal here seems to be to come up with rules that
*programmers* can keep in their heads that (a) are flexible enough to
cover lots of common situations and (b) simple enough so that any
programmer good enough to be given dog food can remember both the
covered situations and the exceptions.

But that, in turn, requires the "situations" to be easy to factor the
"correct" way.  Saunders Mac Lane makes a comment about the analysis
of certain spaces in mathematics, where the special case that provides
all the intuition wasn't defined for decades after the general case.
Had it been done the other way around, the important theorems would
have been proved within a couple of years, and grad students could
have worked out the details within the decade.

So I don't think that this can be worked out by defining multiple
dispatch for Python; you have to define Python for multiple dispatch.
Maybe it's already pretty close?!

This-is-a-job-for-the-time-machine-ly y'rs,