[Python-3000] Adaptation vs. Generic Functions

[Tim Hochberg]

Guido van Rossum wrote:
> #!/usr/bin/python2.4
> 
> """An example of generic functions vs. adaptation.
> 
> After some face-to-face discussions with Alex I'm presenting here two
> extremely simplified implementations of second-generation adaptation
> and generic functions, in order to contrast and compare.
> 
> As the running example, we use the iterator protocol.  Pretend that
> the iter() built-in function doesn't exist; how would we implement
> iteration using adaptation or generic functions?
> 
> """
> 
> 
> __metaclass__ = type # Use new-style classes everywhere
> 
> 
> # 0. The SequenceIter class is shared by all versions.
> 
> class SequenceIter:
>     def __init__(self, obj):
>         self.obj = obj
>         self.index = 0
>     def next(self):
>         i = self.index
>         self.index += 1
>         if i < len(self.obj):
>             return self.obj[i]
>         raise StopIteration
>     def __iter__(self):
>         # This exists so we can use this in a for loop
>         return self
> 
> 
> # 1. Do it manually.  This is ugly but effective... until you need to
> # iterate over a third party object type whose class you can't modify.
> 
> def ManualIter(obj):
>     if isinstance(obj, (list, str, unicode)):
>         return SequenceIter(obj)
>     if isinstance(obj, dict):
>         # We can't really do a better job without exposing PyDict_Next()
>         return SequenceIter(obj.keys())
>     if hasattr(obj, "__iter__"):
>         return obj.__iter__()
>     raise TypeError("Can't iterate over a %s object" % obj.__class__.__name__)
> 
> 
> # 2. Using adaptation.  First I show a simple implementation of
> # adaptation.  In a more realistic situation this would of course be
> # imported.  I call this "second generation adaptation" because the
> # adaptation from protocol P to type T is invoked as P.adapt(T), and
> # the registration of an adapter function A for type T is invoked as
> # P.register(T, A).  The only "smart" feature of this implementation
> # is its support for inheritance (in T, not in P): if T has registered
> # an adapter A for P, then A is also the default adapter for any
> # subclass S of T, unless a more specific adapter is registered for S
> # (or for some base of S that comes before T in S's MRO).
> 
> class Protocol:
>     def __init__(self, name):
>         self.registry = {}
>         self.name = name
>     def register(self, T, A):
>         self.registry[T] = A
>     def adapt(self, obj):
>         for T in obj.__class__.__mro__:
>             if T in self.registry:
>                 return self.registry[T](obj)
>         raise TypeError("Can't adapt %s to %s" %
>                         (obj.__class__.__name__, self.name))
>     def __call__(self, T):
>         # This is invoked when a Protocol instance is used as a decorator.
>         def helper(A):
>             self.register(T, A)
>             return A
>         return helper

[Guido in another thread where I had posted a Protocol class]
> I'd like to hear what you think of my version and how you'd refactor it.


The above ended up being almost identical to the Protocol class I came 
up with. It hopefully speaks well of the general concept that different 
people came up with essentially the same thing. There are two minor 
spelling differences, how to spell adapt (I spelled it __call__) and how 
to spell decorate (I spelled it 'when', here it's spelled __call__). So 
far, I like how code looks when adapt is spelled __call__, still using 
__call__ to spell decorate sidesteps the need to come up with a good 
name ('when' is right out).

There are two other differences. The first is that I allowed multiple 
type arguments (using *args) in three locations. The first two are in 
register and call (decorate); this is done to allow multiple types to be 
registered at once. This requires that the order of the A and T 
arguments be switched in register so that the signature becomes 
register(A, *types). The other location is in adapt. This is done to 
allow subclasses to support multiple arguments. Thus the signature to 
adapt is adapt(self,*args).

The second difference is that I factored out how to get keys for the 
registry. With this change adapt becomes:

      def adapt(self, *args):
          for T in self.keysof(obj):
              if T in self.registry:
                  return self.registry[T](obj)
          raise TypeError("Can't adapt %s to %s" %
                          (obj.__class__.__name__, self.name))
      def keysof(self, *args):
          if len(args) != 1: raise TypeError('expected 1 argument')
          return args[0].__mro__

(and no, no ones happy with the name keysof -- suggestions welcome).

At first this seems a step backwards; Things got longer and marginally 
more complicated. However, factoring out keysof gives you another level 
of flexibility. For example, you can now build a simple multiple 
dispatch mechanism on top of protocol by simple overriding keysof.

class MultipleDispatchProtocol(Protocol):
     def keysof(self, *args):
         return [tuple(type(x) for x in args)]

This only dispatches on types, it doesn't do any mro traversals or 
anything. Still, I found it pretty impressive that it was so simple.

It's possible that this factoring out of keysof was a mistake; adapt is 
so simple that perhaps overriding it completely is the right approach. 
On the other hand, if one were to try to implement full blown 
multimethods on top of this, I think all of the complexity would live in 
keysof, leaving adapt simple. On the third hand, perhaps only that class 
would need to factor out the keysof logic. I think I'll try unfactoring 
it and see how my examples end up looking.

So after all of that, I think my conclusion is that I wouldn't refactor 
this at all, at least not yet. I'd add support for multiple registration 
and possibly spell adapt as __call__, otherwise I'd leave it alone. My 
opinion may change after I try ripping out keysof and see how it looks.


Regards,

-tim


> 
> # Now I show how to define and register the various adapters.  In a
> # more realistic situation these don't all have to be in the same file
> # of course.
> 
> AdaptingIterProtocol = Protocol("AdaptingIterProtocol")
> 
> @AdaptingIterProtocol(list)
> def _AdaptingSequenceIter(obj):
>     return SequenceIter(obj)
> 
> AdaptingIterProtocol.register(str, _AdaptingSequenceIter)
> AdaptingIterProtocol.register(unicode, _AdaptingSequenceIter)
> 
> @AdaptingIterProtocol(dict)
> def _AdaptingDictIter(obj):
>     return SequenceIter(obj.keys())
> 
> @AdaptingIterProtocol(object)
> def _AdaptingObjectIter(obj):
>     if hasattr(obj, "__iter__"):
>         return obj.__iter__()
>     raise TypeError("Can't iterate over a %s object" % obj.__class__.__name__)
> 
> def AdaptingIter(obj):
>     return AdaptingIterProtocol.adapt(obj)
> 
> 
> # 3. Using generic functions.  First I show a simple implementation of
> # generic functions.  In a more realistic situation this would of
> # course be imported.
> 
> class GenericFunction:
>     def __init__(self, default_function):
>         self.default_function = default_function
>         self.registry = {}
>     def register(self, *args):
>         def helper(F):
>             self.registry[args] = F
>             return F
>         return helper
>     def __call__(self, *args):
>         types = tuple([obj.__class__ for obj in args])
>         function = self.registry.get(types, self.default_function)
>         return function(*args)
> 
> # Now I show how to define a generic function and how to register the
> # various type-specific implementations.  In a more realistic
> # situation these don't all have to be in the same file of course.
> 
> @GenericFunction
> def GenericIter(obj):
>     """This is the docstring for the generic function."""
>     # The body is the default implementation
>     if hasattr(obj, "__iter__"):
>         return obj.__iter__()
>     raise TypeError("Can't iterate over %s object" % obj.__class__.__name__)
> 
> @GenericIter.register(list)
> def _GenericSequenceIter(obj):
>     return SequenceIter(obj)
> 
> GenericIter.register(str)(_GenericSequenceIter)
> GenericIter.register(unicode)(_GenericSequenceIter)
> 
> @GenericIter.register(dict)
> def _GenericDictIter(obj):
>     return SequenceIter(obj.keys())
> 
> 
> # 4. Show that all of these work equivalently.
> 
> def main():
>     examples = [
>         [1, 2, 3, 4, 5],
>         "abcde",
>         u"ABCDE",
>         {"x": 1, "y": 2, "z": 3},
>         (6, 7, 8, 9, 10), # Not registered, but has __iter__ method
>         42, # Not registered and has no __iter__ method
>         ]
> 
>     functions = [ManualIter, AdaptingIter, GenericIter]
> 
>     for function in functions:
>         print
>         print "***", function, "***"
>         for example in examples:
>             print ":::", repr(example), ":::"
>             try:
>                 iterator = function(example)
>             except Exception, err:
>                 print "!!! %s: %s !!!" % (err.__class__.__name__, err)
>             else:
>                 for value in function(example):
>                     print repr(value),
>                 print
> 
> if __name__ == "__main__":
>     main()
> 
> # --
> # --Guido van Rossum (home page: http://www.python.org/~guido/)