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

Neil Toronto ntoronto at cs.byu.edu
Sat Dec 15 01:28:32 CET 2007

Arnaud Delobelle wrote:
> 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.  The set of choices is the set S of signatures of
> specialisations of the function (which is partially ordered), and the
> 'commitee' is made of one entity only: the function call's signature s.
> To choose the relevant specialisation, look at:
>
> { t \in S | s <= t and \forall u \in S (s < u <= t) \implies  u = t }
>
> If this set is a singleton { t } then the specialization with signature t
> is the best fit for s, otherwise there is no best fit.

Let's call this set T. In English, it's the set of t's (function
signatures) whose types aren't more specific than s's - but only the
most specific ones according to the partial general-to-specific
ordering. Most multiple dispatch algorithms agree that T has the right
function in it.

Some kind of conflict resolution seems necessary. The number of ways to
have "no best fit" is exponential in the number of function arguments,
so punting with a raised exception doesn't seem useful. It's in the
conflict resolution - when the set isn't a singleton - that multiple
dispatch algorithms are most different.

Conflict resolution puts us squarely into Arrow's wasteland. Whether
it's formulated as a social choice function or not, I think it's
equivalent to one.

In a social choice reformulation of multiple dispatch conflict
resolution, T are the candidate outcomes. (This much is obvious.) The
types are the agents: each prefers functions in which the type in its
position in the signature is most specific. Again, it's a reformulation,
but I believe it's equivalent.

The application implements a social choice function: it picks a winner
function based on types' "preferences". Arrow's Theorem doesn't care
exactly how it does this - whether it has types vote or sums distances
from whatever - it just says that however it does this, the result can't
always be "fair". And "fair" doesn't even mean one type can't have more
say than another by, for example, narrowing the subset first based on
its own preferences. It only means that things don't act
counterintuitively in general, that there's *some* means to every
outcome, and that one agent (type) doesn't control everything.

Maybe, as not-useful as it looks, punting with a raised exception is the
only way out.

Neil