[Python-3000] Generic functions

[Phillip J. Eby]

Nick Coghlan wrote:
>Unfortunately the rules for choosing *which* implementation to dispatch to,
>even if restricting things to concrete types only, are necessarily complex.
>
>As Walter pointed out, the deliberately simplistic sample code elsewhere in
>this thread dispatches to a different method depending on order of
>registration and hashing idiosyncrasies.

The simple code that I posted actually depends only on __mro__.

>To fix that, you either have to stop permitting subclasses of registered
>argument types,
Um, no.  :)  The single-dispatch case works quite nicely with __mro__ 
(or the moral equivalent thereof for classic classes).


>or else you have to define the idea of a "closest" signature
>match, at which point you've been forced to throw "simple" right out 
>the window.

It's no more complex than Python's __mro__ computation is, actually.


>Given this type hierarchy:
>      A
>   B     C
>D E    F
>
>and a call containing (D(), E(), F()), is the type signature (B, B, C) a
>closer match than the signature (A, E, F)?

Neither.  It's ambiguous if you're doing symmetric dispatch.  The 
correct algorithm for scanning a set of signatures like this is that 
you must check *all* signatures for applicability, and then choose 
the one that is "most specific" by throwing out dominated matches 
(ones that are a superset of some other match).  If you end up with 
more than one applicable signature, you have a conflict.

This is almost exactly the same as Python's metaclass determination 
algorithm, by the way: it goes through all the candidate metaclasses 
and throws away dominated metaclasses.  If at the end there is more 
than one candidate remaining, it's a metaclass conflict.

Now, I'm not saying that you'd actually want to implement this 
matching algorithm in such a naive way as a loop over all 
possibilities.  RuleDispatch creates a tree of tests that eliminates 
entire groups of signatures from consideration while testing 
conditions in parallel.  So in your example, the D() argument has its 
__mro__ scanned to eliminate any signatures that don't support a 'B' 
, 'A', or 'D' in the first position.  Then the E() is scanned, and 
finally the F().

In each case, the equivalent of a single isinstance() check is done, 
and the result used to choose a new sub-branch of the tree.  The 
final node after doing the three quasi-isinstance operations is a 
node representing the set of applicable signatures.  If there is more 
than one dominant signature, it's an ambiguity error.

I'm simplifying a bit here, because RuleDispatch actually allows you 
to create custom combiners to handle multiple applicable signatures 
entirely according to your taste.  So, you could actually define an 
alternative resolution that didn't complain about ambiguous 
methods.  For example, you could decide that you would use a 
left-to-right asymmetric resolution (ala Common Lisp) so that (B,B,C) 
would be more specific than (A,E,F) because B->A in the first 
position.  Or you could decide that you would break ties using the 
definition order, which is a popular approach if you're just using 
the generic function as a kind of "listener" hook, where you plan to 
call *all* the applicable signatures, even duplicates, because the 
function is intended as a broadcast hook.

(Notice, by the way, that this makes another class of "registration" 
or "registries" in the stdlib unnecessary; for example, you could 
ditch the atexit module by just having sys.exitfunc be a generic 
function that users register methods for!)


>In a certain sense, an adapting protocol is just a generic function that only
>permits dispatch of single argument functions based on type of that 
>argument -
>as such, adaptation is necessarily simpler than full generic function support.

Adaptation is equivalent to a single-dispatch generic function, 
yes.  And multiple dispatch is certainly more complex to 
implement.  However, multiple dispatch is a lot easier to implement 
if you have single-dispatch generic functions available.  A huge 
amount of RuleDispatch is built on single-dispatch generic functions 
and adaptation.

If I were going to do it over again, I wouldn't use the adaptation 
bit at all; I'd just start with single-dispatch generics.  Or maybe 
not even those.  I've considered that I could actually write the 
bootstrapping bits of RuleDispatch using a simple "naive" 
test-all-signatures algorithm, because by the time RuleDispatch was 
fully imported it would be able to replace those functions with its 
tree-building algorithms.

But that's mostly fantasy at the moment, because RuleDispatch was 
effectively a sabbatical project for me, and although I've gotten a 
few nibbles about possible consulting projects built around it, 
nothing has materialized.  So RuleDispatch is unlikely to get any 
serious development time from me in the near future.