Democratic multiple dispatch doomed to fail (probably)
(Sorry I can't in-reply-to I've lost the original message) 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. -- Arnaud
Arnaud Delobelle writes:
(Sorry I can't in-reply-to I've lost the original message)
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.
I don't think it applies but I think a detailed analysis sheds light on why perfect multiple dispatch is impossible. The second part is true, individual arguments are not expressing preferences in general (though they could, for example a generic concatenation function could take an optional return_type argument so that the appropriate type of sequence is constructed from scratch, rather than sometimes requiring a possibly expensive conversion). The type is not doing the choosing, though. The problem here is that what is really doing the choosing is the application calling the function. You could imagine a module dwim which contains exactly one API: dwim(), which of course does the computation needed by the application at that point. dwim's implementation would presumably dispatch to specializations. Now since all dwim has is the type signature (this includes any subtypes deducible from the value, such as "nonnegative integer", so it's actually quite a lot of information), dwim can't work. Eg, search("de","dent") and append("de","dent") have the same signature (and a lisper might even return the substring whose head matches the pattern, so the return type might not disambiguate). While this is an example requiring so much generality as to be bizarre, I think it's easy to imagine situations where applications will disagree about the exact semantics that some generic function should have. The generic concatenation function is one, and an individual application might even want to have the dispatch done differently in different parts of the program. In sum, the problem is the real "voters" (applications) are represented by rather limited information (argument signatures) to the dispatcher. So the real goal here seems to be to come up with rules that *programmers* can keep in their heads that (a) are flexible enough to cover lots of common situations and (b) simple enough so that any programmer good enough to be given dog food can remember both the covered situations and the exceptions. But that, in turn, requires the "situations" to be easy to factor the "correct" way. Saunders Mac Lane makes a comment about the analysis of certain spaces in mathematics, where the special case that provides all the intuition wasn't defined for decades after the general case. Had it been done the other way around, the important theorems would have been proved within a couple of years, and grad students could have worked out the details within the decade. So I don't think that this can be worked out by defining multiple dispatch for Python; you have to define Python for multiple dispatch. Maybe it's already pretty close?! This-is-a-job-for-the-time-machine-ly y'rs,
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
I wrote:
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.
Sorry to self-reply, but I was just reading this: http://dev.perl.org/perl6/rfc/256.html """ 1. 2. 3. <Exact matches> 4. Otherwise, the dispatch mechanism examines each viable target and computes its inheritance distance from the actual set of arguments. The inheritance distance from a single argument to the corresponding parameter is the number of inheritance steps between their respective classes (working up the tree from argument to parameter). If there's no inheritance path between them, the distance is infinite. The inheritance distance for a set of arguments is just the sum of their individual inheritance distances. 5. The dispatch mechanism then chooses the viable target with the smallest inheritance distance as the actual target. If more than one viable target has the same smallest distance, the call is ambiguous. In that case, the dispatch process fails and an exception is thrown (but see "Handling dispatch failure" below) If there's only a single actual target, its identity is cached (to accelerate subsequent dispatching), and then the actual target is invoked. """ This is almost precisely the Borda protocol: http://en.wikipedia.org/wiki/Borda_count Borda does not satisfy independence of irrelevant alternatives. HOWEVER, the proposed dispatch mechanism does. Why? The agents are voting a kind of utility, not a preference. With the addition or removal of a function, the sum of votes for any other function will not change. AFAIK, that's the only Arrow-ish problem with Borda, so this proposed dispatch mechanism doesn't have the problems I was expecting. Big stink for nothing, I guess. I imagine that making next-method calls behave is a nightmare, though. The more I read about multiple dispatch, the less I like it. Neil
ntoronto@cs.byu.edu writes:
This is almost precisely the Borda protocol:
No, it is not. The Borda rule requires a linear order, whereas this is a partial order, and complete indifference is possible.
Why? The agents are voting a kind of utility, not a preference. With the addition or removal of a function, the sum of votes for any other function will not change.
And this utilitarian rule has its own big problems. For one, you could argue that it violates the Arrow condition of non-dictatorship because *somebody* has to choose the weights. In particular, weighting the number of levels by one doesn't make a lot of sense: some developers prefer a shallow style with an abstract class and a lot of concrete derivatives, others prefer a hierarchy of abstract classes with several levels before arriving at the concrete implementations. I think it would be a bad thing if devotees of the latter style were discouraged because their users found the convenience of automatic dispatch more important than the (usually invisible) internal type hierarchy. Also, my intuition doesn't rule out the possibility that self *should* be a dictator if it "expresses a preference" -- the Arrow condition of non-dictatorship might not even be appropriate.
I imagine that making next-method calls behave is a nightmare, though. The more I read about multiple dispatch, the less I like it.
It's a hard problem.
Stephen J. Turnbull wrote:
ntoronto@cs.byu.edu writes:
Why? The agents are voting a kind of utility, not a preference. With the addition or removal of a function, the sum of votes for any other function will not change.
And this utilitarian rule has its own big problems.
For one, you could argue that it violates the Arrow condition of non-dictatorship because *somebody* has to choose the weights. In particular, weighting the number of levels by one doesn't make a lot of sense: some developers prefer a shallow style with an abstract class and a lot of concrete derivatives, others prefer a hierarchy of abstract classes with several levels before arriving at the concrete implementations. I think it would be a bad thing if devotees of the latter style were discouraged because their users found the convenience of automatic dispatch more important than the (usually invisible) internal type hierarchy.
Good point. Further, what if it's more important for one type to be treated as specifically as possible than for another? In a multi-agent setting, we'd call this the problem of combining utilities. In general, there's not a good way to do it - utilities (or these pseudo-utilities) are unique only up to a linear (or positive affine) transform. Assuming it's possible to pick a zero point you can normally shift and multiply them, but here the only obvious zero point (minimum distance over all matching functions) would net you a lot of ties. Here's another fun idea: a lesser-known theorem called Gibbard-Satterthwaite says you can't construct a fair voting system in which the best response for each agent is to always tell the truth. It's strange to think of types *lying* about their distances from each other, but I'm sure users will end up constructing whacked-out hierarchies in an attempt to game the system and swing the vote toward specific functions. At that point, dispatch may as well be completely manual. Maybe the voting reformulation wasn't such a bad idea after all. At the very least, I've decided I really don't like Perl's implementation. :D
Also, my intuition doesn't rule out the possibility that self *should* be a dictator if it "expresses a preference" -- the Arrow condition of non-dictatorship might not even be appropriate.
I'm not completely sure of this (the docs I've read have been pretty vague) but I think CLOS does that. One way to look at the problem is finding a total order in some D1xD2x...xDn space, where Di is a type's distance from matching function signature types. CLOS imposes a lexicographical order on this space, so self is a dictator. Type 2 gets to be a dictator if self is satisfied, and so on. Somehow they make it work with multiple inheritance. Of all the approaches I've seen I like this best, though it's still really complex. Python's __op__/__rop__ is a rather clever solution to the problem in binary form. Do you know if there's a generalization of this? CLOS is almost it, but Python lets the class containing __op__ or __rop__ own the operation after it finds one that implements it. Neil
Neil Toronto writes:
Python's __op__/__rop__ is a rather clever solution to the problem in binary form. Do you know if there's a generalization of this? CLOS is almost it, but Python lets the class containing __op__ or __rop__ own the operation after it finds one that implements it.
Sorry, no. I'm a professional economist (my early work was related to Gibbard-Satterthwaite, thus my interest here) and wannabe developer, who happens to have enjoyed the occasional guidance of Ken Arrow a couple decades ago. If you think there's something to the application of multiobjective optimization to this problem, I'd love to take a hack at it ... no classes to teach winter term, I've got some time to bone up on the multidispatch problem itself.
Stephen J. Turnbull wrote:
Neil Toronto writes:
Python's __op__/__rop__ is a rather clever solution to the problem in binary form. Do you know if there's a generalization of this? CLOS is almost it, but Python lets the class containing __op__ or __rop__ own the operation after it finds one that implements it.
Sorry, no. I'm a professional economist (my early work was related to Gibbard-Satterthwaite, thus my interest here) and wannabe developer, who happens to have enjoyed the occasional guidance of Ken Arrow a couple decades ago.
Excellent.
If you think there's something to the application of multiobjective optimization to this problem, I'd love to take a hack at it ... no classes to teach winter term, I've got some time to bone up on the multidispatch problem itself.
For finding the first matching function, you could say it's picking some "best fit" from the Pareto optimal front. AFAIK all ways of doing that suck somehow. :) After that, the problem is calling a next-method, which requires imposing a total order on the entire space of fitting functions. (This had better define the "best fit" as well.) The big hurdles to multiple dispatch I see are: 1. It has to "make sense" somehow - maybe by satisfying some set of intuitive axioms. 2. It seems unlikely a majority will agree on the axioms. (Yay! Another social choice problem!) 3. It has to be simple enough that it's easy to predict what a method or next-method call does. Because this seems nigh-impossible (particularly #3), I'm starting to look elsewhere for solutions to "the problem". Speaking of which, it's really easy to forget the two primary use-cases that motivate multiple dispatch in the first place: 1. Interop with other types. For instance, I define a BarNumber type, and I want fooing of BarNumber with anything else to return a new BarNumber. Or perhaps I need some class I currently would have no control over to treat my custom type specially or apply a transformation before doing what it usually does. CLOS (Common Lisp Object System) handles this. Python's __op__/__rop__ does for a finite set of binary operators. 2. True dynamic overloading so we don't have to do type checks at the heads of our functions. CLOS handles this. #1 can always be done with clever delegation. For example, numpy's arrays do it halfway by applying __array__ to a function argument before operating on it. If they also applied, say, a type's fromarray classmethod upon return it'd provide a full solution. But as with numpy's arrays, users don't have enough control to make it work exactly as they want if the only solution is delegation. The class creator has to anticipate how his class will be used and risk over-generalizing it. In the worst cases, you'd end up with a crazy proliferation of types like FooLoggable and FooAppendable and methods like __foo_loggable__ and __foo_appendable__... The most general way to do #2 is the way it's done now. Sure it's Turing-complete, but it'd be nice to be able to handle the common cases automatically. PJE has a lot of further reading here: http://mail.python.org/pipermail/python-3000/2006-November/004421.html Neil
participants (4)
-
Arnaud Delobelle -
Neil Toronto -
ntorontoļ¼ cs.byu.edu
-
Stephen J. Turnbull