[Python-ideas] Democratic multiple dispatch doomed to fail (probably)
ntoronto at cs.byu.edu
Fri Dec 14 07:40:15 CET 2007
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
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
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.
More information about the Python-ideas