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,