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

[Neil Toronto]

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