[Python-3000] Adaptation vs. Generic Functions

[Guido van Rossum]

#!/usr/bin/env python2.5

# overloading.py

"""Here's another executable email.

This is an implementation of (dynamically, or run-time) overloaded
functions, formerly known as generic functions or multi-methods.

I actually blogged on Artima about multi-methods about a year ago; but
at the time I hadn't figured out the trick of explicitly declaring the
MM before registering the implementations (Phillip helpfully pointed
that out in a comment); also, I was using a global registry then.

This version is an improvement over my earlier attempts (both last
year and at the start of this thread) because it supports subclasses
in call signatures.  If an implementation is registered for a
signature (T1, T2), then a call with a signature (S1, S2) is
acceptable, assuming that S1 is a subclass of T1, S2 a subclass of T2,
and there is no ambiguity in the match (see below).

I came up with an algorithm for doing this that may or may not
resemble the one in PEAK's RuleDispatch.  I kind of doubt that it's
all that similar because RuleDispatch supports arbitrary predicates.
In contrast, I'm just using the argument types for dispatch, similar
to (compile-time) overloaded functions in C++ and methods in Java.  I
do use a concept that I overheard Phillip mention: if there are
multiple matches and one of those doesn't *dominate* the others, the
match is deemed ambiguous and an exception is raised.  I added one
refinement of my own: if, after removing the dominated matches, there
are still multiple matches left, but they all map to the same
function, then the match is not deemed ambiguous and that function is
used.  Read the method find_func() below for details.

The example is a bit lame; it's not a very good pretty-printer and it
only dispatches on a single argument; but it does exercise the weeding
out of dominant matches.  I'll try to post a complete unit test suite
later.

Python 2.5 is required due to the use of predicates any() and all().

"""

# Make the environment more like Python 3.0
__metaclass__ = type
from itertools import izip as zip


class overloaded:
    # An implementation of overloaded functions.

    def __init__(self, default_func):
        # Decorator to declare new overloaded function.
        self.registry = {}
        self.cache = {}
        self.default_func = default_func

    def register(self, *types):
        # Decorator to register an implementation for a specific set of types.
        # .register(t1, t2)(f) is equivalent to .register_func((t1, t2), f).
        def helper(func):
            self.register_func(types, func)
            return func
        return helper

    def register_func(self, types, func):
        # Helper to register an implementation.
        self.registry[tuple(types)] = func
        self.cache = {} # Clear the cache (later we can optimize this).

    def __call__(self, *args):
        # Call the overloaded function.
        func = self.find_func(args)
        return func(*args)

    def find_func(self, args):
        # Find the appropriate overloaded function; don't call it.
        # NB. This won't work for old-style classes or classes without __mro__.
        types = tuple(type(a) for a in args)
        if types in self.cache:
            # First easy case -- direct hit in cache.
            return self.cache[types]
        if types in self.registry:
            # Second easy case -- direct hit in registry, update cache.
            self.cache[types] = func = self.registry[types]
            return func
        # I can't help myself -- this is going to be intense functional code.
        # Find all possible candidate signatures.
        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))]
        if not candidates:
            # No match at all -- use the default function.
            self.cache[types] = func = self.default_func
            return func
        if len(candidates) == 1:
            # Unique match -- that's an easy case.
            self.cache[types] = func = self.registry[candidates[0]]
            return func
        # More than one match -- weed out the subordinate ones.
        def dominates(dom, sub,
                      orders=tuple(dict((t, i) for i, t in enumerate(mro))
                                   for mro in mros)):
            # Predicate to decide whether dom strictly dominates sub.
            # Strict domination is defined as domination without equality.
            # The arguments dom and sub are type tuples of equal length.
            # The orders argument is a precomputed auxiliary data structure
            # giving dicts of ordering information corresponding to the
            # positions in the type tuples.
            # A type d dominates a type s iff order[d] <= order[s].
            # A type tuple (d1, d2, ...) dominates a type tuple of equal length
            # (s1, s2, ...) iff d1 dominates s1, d2 dominates s2, etc.
            if dom is sub:
                return False
            return all(order[d] <= order[s]
                       for d, s, order in zip(dom, sub, orders))
        # I suppose I could inline dominates() but it wouldn't get any clearer.
        candidates = [cand
                      for cand in candidates
                      if not any(dominates(dom, cand) for dom in candidates)]
        if len(candidates) == 1:
            # There's exactly one candidate left.
            self.cache[types] = func = self.registry[candidates[0]]
            return func
        # Perhaps these multiple candidates all have the same implementation?
        funcs = set(self.registry[cand] for cand in candidates)
        if len(funcs) == 1:
            self.cache[types] = func = funcs.pop()
            return func
        # No, the situation is irreducibly ambiguous.
        raise TypeError("ambigous call; types=%r; candidates=%r" %
                        (types, candidates))


# Example showing how to create an overloaded function.

class List(list):
    pass

class SubList(List):
    pass

@overloaded
def pprint(obj):
    return repr(obj)

@pprint.register(List)
@pprint.register(list)
def pprint_list(obj):
    if not obj:
        return "[]"
    s = "["
    for item in obj:
        s += pprint(item).replace("\n", "\n ") + ",\n "
    return s[:-3] + "]"

@pprint.register(tuple)
def pprint_tuple(obj):
    if not obj:
        return "()"
    s = "("
    for item in obj:
        s += pprint(item).replace("\n", "\n ") + ",\n "
    if len(obj) == 1:
        return s[:-2] + ")"
    return s[:-3] + ")"

@pprint.register(dict)
def pprint_dict(obj):
    if not obj:
        return "{}"
    s = "{"
    for key, value in obj.iteritems():
        s += (pprint(key).replace("\n", "\n ") + ": " +
              pprint(value).replace("\n", "\n ") + ",\n ")
    return s[:-3] + "}"

@pprint.register(set)
def pprint_set(obj):
    if not obj:
        return "{/}"
    s = "{"
    for item in obj:
        s += pprint(item).replace("\n", "\n ") + ",\n "
    return s[:-3] + "}"


# Example showing how to use the above overloaded function.

data = (
    "this is a string", [1, 2, 3, 4], ("more tuples",
    1.0, 2.3, 4.5), "this is yet another string", (99,)
    )

print pprint(data)

print pprint(List(data))

print pprint(SubList(data))

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