[Python-3000] Sane transitive adaptation

[Tim Hochberg]

Nick Coghlan wrote:
> One issue with generic functions and adaptation as currently being discussed 
> (and something Tim mentioned a while back), it that it is very focused on 
> dispatching based solely on obj.__class__.__mro__.
> 
> That's all well and good, but (to use an example of Tim's), suppose we have a 
> couple of frameworks we're using, where those frameworks have each defined 
> their own version of a "wibbly-wobbly" object:
> 
>    frmwrk_A.IWibble
>    frmwrk_B.IWobble
> 
> The methods and signatures included in these protocols may be the same, 
> IWibble may be a subset of IWobble, or vice versa.
> 
> Both frameworks have defined their interfaces (input and output) in terms of 
> these protocols, rather than in terms of concrete types.
> 
> As Tim pointed out, pure type-based dispatch would require that every type be 
> registered with both protocols, even if the two protocols are identical. Doing 
> that manually would be a serious pain if the frameworks were non-trivial.
> 
> The first thought may be to allow adaptation between protocols - but the issue 
> with that is that at adaptation time, we only have the object to work with, 
> and won't know what protocols it claims to implement (this is where either 
> __conform__ or a global registry comes in with PEP 246).
> 
> Even if we did know, the cost of doing a search on all equivalent protocols on 
> each call would add up. We don't really want to be finding ways to make 
> functions calls even slower than usual ;)
> 
> There is, however, an alternative, which would be to include a mechanism for 
> telling a protocol about other equivalent protocols, and updating the 
> registration mechanism to distribute any registration updates to the 
> equivalent protocols.
> 
[Implementation snipped]

In the "Adaptation vs. Generic Functions" thread I proposed that the 
registry be implemented using a ChainedDict that searched it's parent 
for any keys that it didn't have itself. This allows extending existing 
protocols using:

     extended_protocol = Protocol(base_protocol)

[Note that the name parameter has gone away. I'll include the Protocol 
and ChainedDict implementation at the end of this post.]

It's a relatively short step from here to allowing the extending of 
multiple protocols. And a relatively short step from there to an 
alternative implementation of register_subprotocol.


> 
> Using such a mechanism, the interface mismatch above could be addressed in one 
> of the following ways:
> 
> Suppose framework A specifies fewer methods than framework B, but those 
> methods match. Then you can write:
> 
>    frmwrk_B.IWobble.register_subprotocol(frmwrk_A.IWibble)
>    # Now registration for framework B also registers you for the narrower
>    # interface in framework A

Given the above, if framework A is created with knowledge of framework 
B, we can use:

     # in frmwrk_A
     IWibble = Protocol(frmwrk_B.I_Wobble)

If instead we want to make IWibble a subprotocol of IWobble after the 
fact, we can instead do:

     frmwrk_B.IWobble.registry.parents.append(frmwrk_A.IWibble.registry)

This may need some sugar to make it more palatable. For instance, one 
could have still have register_subprotocol as a method, or perhaps a 
helper function, that implemented the above. I'll try add_parent and see 
how that looks:

     class Protocol:
         #...
         def add_parent(self, protocol):
             self.registry.parents.append(protocol.registr)

Then we can dynamically make IWibble a subprotocol of IWobble using:

     frmwrk_B.IWobble.add_parent(frmwrk_A.IWibble)

> 
> You can turn that around, if A is the one that is more prescriptive:
> 
>    frmwrk_A.IWibble.register_subprotocol(frmwrk_B.IWobble)
>    # Now it is registration for framework A that registers you for the narrower
>    # interface in framework B
> 
> And finally, if the two interfaces are identical:
> 
>    frmwrk_A.IWibble.register_subprotocol(frmwrk_B.IWobble)
>    frmwrk_B.IWobble.register_subprotocol(frmwrk_A.IWibble)
>    # Now registration for either framework registers you for both

ChainedDict is careful not to loop, so this case can be spelled as:

     frmwrk_A.IWibble.registry.parents.append(frmwrk_A.IWobble.registry)
     frmwrk_B.IWobble.registry.parents.append(frmwrk_B.IWibble.registry)

or perhaps more readably as:

     frmwrk_B.IWobble.add_parent(frmwrk_A.IWibble)
     frmwrk_A.IWibble.add_parent(frmwrk_B.IWobble)

> Now, suppose, however, that mapping from A to B required a slight tweak to A's 
> interface - one of the method signatures didn't line up right (e.g. one of A's 
> methods has the wrong name). This can be handled with an explicit protocol 
> adapter, which would provide a modified update method like so:
> 
>    class ProtocolAdapter(object):
>        def __init__(self, src, target):
>            self.target = target
>            src.register_subprotocol(self)
> 
>        def _update(self, updates, updated=None):
>            if self.target in updated:
>                return
>            wrapped_updates = {}
>            for signature, adapter in updates.iteritems():
>                def wrapped_adapter(*args, **kwds):
>                     return self.adapt(adapter(*args, **kwds))
>                wrapped_updates[signature] = wrapped_adapter
>            self.target._update(wrapped_updates, updated)
> 
>        def __call__(self, adapter):
>            self.adapt = adapter
> 
>    class AdaptWibbletoWobble(object):
>        def __init__(self, obj):
>            self.obj = obj
>        def __iter__(x, y, z):
>            return self.obj.method2(x, y, z)
> 
>    ProtocolAdapter(frmwork_A.IWibble, frmwrk_B.IWobble)(AdaptWibbleToWobble)


Clever. The naming makes that last statement pretty opaque until you 
squint at the code for a while though. I don't think this would be a 
problem to layer on top of chained dict if needed. I think something 
like the following would work:

     WrappedDict(object):
         def __init__(self, obj, wrapper):
             self._obj = obj
             self._wrapper = wrapper
         def get(self, key, default=None):
             try:
                 return self[key]
             except KeyError:
                 return default
         def __getitem___(self, key):
             return self._wrapper(self._obj[key])
         def __contains__(self, key):
             return key in self._obj

     class Protocol:
         #....
         def add_parent(self, protocol, wrapper=None):
             registry = protocol.registry
             if wrapper is not None:
                 registry = WrappedDict(registry)
             self.registry.parents.append(protocol.registry)


I'm not sure this stuff needs to be methods -- it might be better 
relegated to helper functions to keep the core Protocol object simple.


> The equivalent of the above for generic functions is the case where "generic 
> function A" does a very similar thing to "generic function B", and you want to 
> be able to do a wholesale delegation from A to B of everything that B handles 
> more specifically than A.
> 
> Aside from the fact that I think any such transitivity mechanism should be 
> observer based, and that the updates should happen at registration time rather 
> than lookup time, I'm not really wedded to any of the implementation details 
> above. But I figured it was something worth throwing out there :)

I can see why you would want to this for performance reasons. However, 
the implementation crosses the threshold into too complex in my mind. In 
a sense, I've just pushed the complexity off into ChainedDict, but it's 
easier for me to digest in smaller chunks. I can also see some caching 
strategies that would make ChainedDict as fast as the observer strategy 
as long as we don't need to worry too much about people removing keys 
from the registries.

Regards,

-tim


======================================================


_missing = object()

class ChainedDict(dict):
     """A dict like object that forwards item requests to its parent if 
neeeded."""
     def __init__(self, *parents):
         dict.__init__(self)
         self.parents = list(parents)
     def __contains__(self, key):
         return self.get(key, _missing) is not _missing
     def __getitem__(self, key):
         x = self.get(key, _missing)
         if x is _missing:
             raise KeyError('not found')
         return x
     def _get(self, key, visited):
         # Get a value from self or parents. Return _missing on failure
         # visited contains the ids of objects searched so far.
         myid = id(self)
         if myid in visited:
             return _missing
         visited.add(myid)
         x = dict.get(self, key, _missing)
         if x is not _missing:
             return x
         for p in self.parents:
             if isinstance(p, ChainedDict):
                 x = p._get(key, visited)
             else:
                 x = p.get(key, _missing)
             if x is not _missing:
                 return x
         return _missing
     def get(self, key, default=None):
         x = self._get(key, set())
         if x is _missing:
             return default
         return x


def null_adapter(*args):
      """Adapter used when adaptation isn't actually needed"""
      if len(args) > 1:
          return args
      else:
          return args[0]

class Protocol(object):
     """Declare a protocol object that subclasses parents if provided"""
     def __init__(self, *parents):
         self.registry = ChainedDict(*(x.registry for x in parents))

     def register(self, *args):
         """Function decorator to register as an adapter for given keys"""
         if len(args) == 1:
             args = args[0]
         def helper(adapter):
             if adapter is None:
                 adapter = null_adapter
             self.registry[args] = adapter
             return adapter
         return helper

     def signatures(self, *args):
         """Find signatures for given call arguments"""
         # Default behaviour dispatches on the type of the first argument
         if len(args) != 1:
             raise TypeError("%s expected 1 argument, got %s" %
                             (self, len(args)))
         return type(args[0]).__mro__

     def default_adapter(self, *args):
         """Call result when no adapter was found"""
         raise TypeError("Can't adapt <%s> to %s" %
                         (', '.join(x.__class__.__name__ for x in args),
                          self.__class__.__name__))

     def __call__(self, *args):
        """Adapt supplied arguments to this protocol"""
        for key in self.signatures(*args):
            adapter = self.registry.get(key, _missing)
            if adapter is not _missing:
                return adapter(*args)
        return self.default_adapter(*args)