Multiple dispatch decorator in Python

You have a docstring and some doctests, which is great! The docstring needs some work, though, as described below.

The docstring needs to mention that the returned function has an add method, and explain what this method does.

The docstring needs to explain how the multiple dispatch works: that is, by exact match on the types of the arguments against the types of the annotations of the function instances. You ought to make it clear that arguments without annotations are ignored by the dispatcher.

The docstring says, "The returned function doesn't allow keyword arguments" but you might want to elaborate on exactly what this means.

The example code in the docstring is not very motivating. Why would I want to want to write a function foo like this? It would be very helpful to the reader if you could come up with an example that more closely resembles a real use case.

A group of multi-dispatch functions is a persistent data structure with two methods (add and __call__) and so would be clearer, I think, if it were implemented as a class.

The introspection code would be much clearer if you used inspect.signature. (This was introduced in 3.3, but since you're using function annotations, you probably don't mind this.)

The function that is decorated with @multi_dispatch is only used for its name, module, and docstring (the items that are copied by functools.update_wrapper). The function body is ignored. This seems like a waste: why not add this function to the registry too?

If you wrote return decorated instead of return func at the end of adder, then you wouldn't have to respell the names of the method instances.

Update: What I mean by this is that you have to spell your method instances _foo rather than foo, to avoid overwriting the multi-method in the variable foo. With my suggestion, you wouldn't have to do this.

Dispatching on the exact types of the arguments limits the usefulness of multiple dispatch. In languages like Common Lisp that have multiple dispatch, dispatching can be performed on subclass matches (not just on exact matches). This makes for more natural fallback code, for example:

@find.add
def find(needle: str, haystack: str):
    # When both arguments are strings, Python has a built-in efficient
    # search operation.
    return haystack.find(needle)

@find.add
def find(needle: Sequence, haystack: Sequence):
    # Otherwise, for generic sequences, use Boyer–Moore–Horspool.
    h = len(haystack)
    n = len(needle)
    skip = {needle[i]: n - i - 1 for i in range(n - 1)}
    i = n - 1
    while i < h:
        for j in range(n):
            if haystack[i - j] != needle[-j - 1]:
                i += skip.get(haystack[i], n)
                break
        else:
            return i - n + 1
    return -1

With your implementation one would have to provide separate method instances for (list, list), (tuple, tuple), (list, tuple) and other combinations of sequence types.

Update: In comments you express concern about the speed of doing the subclass lookups. But you can deal with that by maintaining a cache of the actual argument types and the method instance that was found corresponding to those types. The revised dispatch logic would be something like this:

arg_types = tuple(type(i) for i in args)
try:
    method = cache[arg_types]
except KeyError:
    method = ... # slow subclass dispatch logic here
    cache[arg_types] = method
return method(*args)

(When adding a new method instance, this might invalidate some of the cached lookups, so you'd need to clear the cache in the add method.)

You probably want to look at Guido van Rossum's multimethod implementation for other ideas (like "stacking" of multimethod decorators).