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

[Neil Toronto]

I apologize if this is well-known, but it's new to me. It may be 
something to keep in mind when we occasionally dabble in generic 
functions or multimethods. Hopefully there's a way around it.

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.

Arrow's Theorem says that you can't (final, period, that's it) make a 
"social choice function" that's fair. A social choice function takes 
preferences as inputs and outputs a single preference ordering. (You 
could think of types as casting preference votes for functions, for 
example, by stating their "distance" from the exact type the function 
expects. It doesn't matter exactly how they vote, just that they do it.) 
"Fair" means the choice function meets these axioms:

1. The output preference has to be a total order. This is important for 
choosing a president or multiple dispatch, since without it you can't 
choose a "winner".

2. There has to be more than one agent (type, here) and more than two 
choices. (IOW, with two choices or one agent it's possible to be fair.)

3. If a new choice appears, it can't affect the final pairwise ordering 
of two already-existing choices. (Called "independence of irrelevant 
alternatives". It's one place most voting systems fail. Bush vs. Clinton 
vs. Perot is a classic example.)

4. An agent promoting a choice can't demote it in the final pairwise 
ordering. (Called "positive association". It's another place most voting 
systems fail.)

5. There has to be some way to get any particular pairwise ordering. 
(Called "citizen's sovereignty". Notice this doesn't say anything about 
a complete ordering.)

6. No single agent (or type) can control a final pairwise ordering 
independent of every other agent. (Called "non-dictatorship".)


Notice what it doesn't say, since some of these are very loose 
requirements. In particular, it says nothing about relative strengths of 
votes.

What does this mean for multiple dispatch?

It seems to explain why so many different kinds of dispatch algorithms 
have been invented: they can't be made "fair" by those axioms, which all 
seem to describe desirable dispatch behaviors. No matter how it's done, 
either the outcome is intransitive (violates #1), adding a seemingly 
unrelated function flips the top two in some cases (violates #3), using 
a more specific type can cause a strange demotion (violates #4), or 
there's no way to get some specific function as winner (violates #5). 
Single dispatch gets around this problem by violating #6 - that is, the 
first type is the dictator.

Am I missing something here? I want to be, since multiple dispatch 
sounds really nice.

Neil