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.