[Python-3000] Adaptation vs. Generic Functions

[Guido van Rossum]

On 4/6/06, Phillip J. Eby <pje at telecommunity.com> wrote:
> Guido wrote:
> >         mros = tuple(t.__mro__ for t in types)
> >         n = len(mros)
> >         candidates = [sig for sig in self.registry
> >                       if len(sig) == n and
> >                          all(t in mro for t, mro in zip(sig, mros))]
>
> I believe this can be simplified to:
>      n = len(types)
>      candidates = [sig for sig in self.registry
>                    if len(sig) == n and
>                       all(issubclass(s,t) for s,t in zip(sig, types))]
[but with issubclass(t,s) as Jim Jewett pointed out]

Aha. This would solve the problem that it currently only works with
"proper" types (that inherit from type and hence define __mro__).

> Similarly, I believe the dominates function can be moved out to a
> top-level function in similar fashion:
>
>      def dominates(dom, sub):
>          return all(d is not s and issubclass(d,s) for d,s in zip(dom, sub))
>
> Using issubclass() is more accurate in this case than using __mro__,
> because __mro__ considers the order of the __bases__ to be
> significant, which can lead to unexpected results due to false
> precision.  (i.e., because it'll be guessing about cases that are
> actually ambiguous)

Here I'm not so sure. Are you sure those results are unexpected? It
seems you are saying that if I have a class C deriving from A and B
(in that order) where both A and B implement a method foo(), and C
doesn't, the call C().foo() would be ambiguous. But in fact the whole
point of having a defined MRO is to foster the expectation that it
will call A's foo(), because that one comes first in the MRO.

So at least for the single-argument variant I would think that my
algorithm gives results consistent with the definition of inheritance
in new-style classes.

> Unfortunately, this entire approach is subject to similar scale
> issues as PyProtocols/RuleDispatch.

Even with the cache I put in? The hairy algorithm doesn't get invoked
more than once per actual signature (type tuple).

> It is much slower than a few
> hand-written if-then's for the common cases, and it's even slower and
> too inflexible for the "zillions of methods" cases like Zope's "view"
> registry (which dispatches based on some types and a string).

I don't recall the details of Zope view dispatch (and they changed
since I left) but isn't the string a red herring that can be solved by
having a separate dispatcher for each string?

> You
> could get better performance in the common cases by just creating a
> dominance hierarchy among all the methods, and then writing out
> Python code that executes a series of if-then tests with the dominant
> cases being tested first (and some extra branches to check for
> ambiguity).

I like the idea of analyzing the methods for dominance relationships
ahead of time. But I'm not sure why we should then resort to
generating code. Shouldn't it be just as easy to create a data
structure that can be walked by fixed code? (Just like a
recursive-descent parser can be written as a fixed "machine" that
interprets a data structure representing the parse information.)

> This code would then run at virtually the same speed as
> an identical hand-written function for the most common use cases
> (which tend towards having only a handful of overloads at most), and
> it would also not require any extra memory allocations for temporary
> lists and tuples on each invocation of the function (because all the
> state is effectively tracked in the program counter as it threads its
> way among the if-then tests).

If the cache is doing its work, the only allocation on each call is
the expression

    types = tuple(type(a) for a in args)

Tuple allocation is pretty fast so I'm surprised you're worried about
this. Have you ever measured this kind of thing?

> To make the same approach also work for the zillions-of-methods
> cases, all that would be needed is replacing some of the if-thens
> with dictionary lookups to allow N-way branches instead of just
> true/false tests, and some optimization to avoid re-testing
> conditions or recomputing values that have already been
> computed.

> Most of RuleDispatch's complexity stems from the fact that
> I effectively implemented a mini-interpreter for executing such N-way
> dispatch trees, instead of just generating bytecode.  I made that
> choice because there's unfortunately no "computed goto" equivalent in
> today's bytecode.  (Bytecode is also rather annoyingly low-level for
> this kind of work.)

I would not recommend anyone even looking into bytecode generation. If
you *have* to generate code, at least generate Python code, so Jython
and IronPython aren't left behind.

--
--Guido van Rossum (home page: http://www.python.org/~guido/)