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