[Python-ideas] Democratic multiple dispatch doomed to fail (probably)
ntoronto at cs.byu.edu
Mon Dec 17 06:17:57 CET 2007
Stephen J. Turnbull wrote:
> ntoronto at 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.
More information about the Python-ideas