Multiple dispatch based on typing.overload

Ideas
1

Looking at the original issues [1], [2], it sounds as if there was initially an idea to have @typing.overload enable actual multiple dispatch, before it became informational only. This idea seems to resurface occasionally [3].

So, why isn’t there something like @functools.multidispatch that uses @typing.overload to actually do multiple dispatch? Since libraries for multiple dispatch exist, the actual dispatching is presumably not an insurmountable problem. And with @typing.overload there is already a standard mechanism to describe the individual specialisations.

To illustrate that point, now that Python 3.11 has added the ability to return the overloads of a given function, the following is entirely possible with a bit of DIY:

from typing import Any, overload

@overload
def concat(a: list, b: list) -> list:
    return a + b

@overload
def concat(a: list, b: object) -> list:
    return a + [b]

@overload
def concat(a: object, b: list) -> list:
    return [a] + b

# decorator that does multiple dispatch with a stub function
@multipledispatch
def concat(a: Any, b: Any) -> Any:
    ...

print(concat([1], [2]))  # [1, 2]
print(concat([1], 2))    # [1, 2]
print(concat(1, [2]))    # [1, 2]
print(concat(1, 2))      # TypeError: No overload variant ...

As you can see, the idea is roughly that the overloads have all necessary type information for multiple dispatch anyway, so one only has to add the specific implementations. While this turns the usual pattern of only having stubs for @typing.overload exactly on its head, it does yield somewhat type-checked multiple dispatch right now at no extra cost.[1]

Toy implementation

Below is a very naive implementation of the dispatcher, just to run the example. It would probably be better to reuse the @singledispatch mechanism.

from functools import wraps
from inspect import signature
from typing import Any, Callable, TypeVar, cast, get_overloads, get_type_hints

F = TypeVar('F', bound=Callable[..., Any])

def _dispatch(classes, registry):
    match = next((types for types in registry.keys()
                  if all(issubclass(c, t) for c, t in zip(classes, types))),
                 None)
    return registry.get(match)

def multipledispatch(func: F) -> F:
    registry = {}
    sig = signature(func)
    par = list(sig.parameters)
    for overload in get_overloads(func):
        ann = get_type_hints(overload)
        types = tuple(map(ann.get, par))
        registry[types] = overload

    @wraps(func)
    def wrapper(*args, **kwargs):
        ba = sig.bind(*args, **kwargs)
        ba.apply_defaults()
        classes = tuple(ba.arguments[name].__class__ for name in par)
        overload = _dispatch(classes, registry)
        if not overload:
            given = '", "'.join(cls.__name__ for cls in classes)
            raise TypeError(f'No overload variant of "{func.__name__}" '
                            f'matches argument types "{given}"')
        return overload(*args, **kwargs)

    return cast(F, wrapper)

  1. Somewhat, because there is probably no good way to implement support for generic types. ↩︎

4 Likes
2

Hi @ntessore ! I was thinking about it for a while after I worked a bit on plum: GitHub - beartype/plum: Multiple dispatch in Python .
We also worked with @overload there:

In the end I made my own lib there because of a few issues I had with plum (notably keyword arguments).
My lib is entirely focused on @overload and matching the semantics of mypy.

So far, it’s fully working with pycharm, vscode, mypy and pyright!!! The only small issue I have is that pyright is warning me that the body of overload functions must be empty (it’s easy to ignore this error with a type: ignore). It’s a quite minor problem. But what I would like is to make sure type checkers don’t break my lib in the future. So a PEP might be necessary.

The PEP would say something like “a lib can implement multiple dispatch based on the overload semantics. The lib must declare itself as a multiple dispatch library in this way: …, by doing so, type checkers now check the body of functions that have the @overload instead of the last one. The last declaration of the function must be empty.” (possibly the shortest PEP ever???)

4 Likes
3

I had an hour to loose. Here is a very quick draft of the PEP: GitHub - gabrieldemarmiesse/PEP-draft-multiple-dispatcher: draft of the multiple dispatcher PEP

I’m open to suggestions and comments :slight_smile:

2 Likes
4

I’m invoking @ambv who has shown some interest in multiple dispatch with overload and might be able to tell me if my PEP idea makes sense or not.

5

@gabrieldemarmiesse, your draft PEP is very interesting. @ntessore and @gabrieldemarmiesse, perhaps it is worthwhile to make a list of problems with the current state of type checking and multiple dispatch, to find consensus on what a PEP could address.

Off the top of my head, in no particular order, some issues are the following:

  1. For overload-based multiple dispatch implementations, overload methods are not intended to have an implementation. It would be a simple change to allow overload methods to have an implementation, but I’m wondering if that is a change that people would be willing to accept. An alternative would be to add typing.dispatch, which would work like typing.overload but with the semantics that typing.dispatch methods should have an implementation.

  2. For overload-based multiple dispatch implementations, it is slightly troublesome that first all overloads need to come and then the function needs to be implemented. For example, you cannot add additional overloads after the “implementation”:

@overload
def f(x: int) -> int:
    return x


def f(x):
    ... # The implementation


@overload
def f(x: float) -> float:  # This is not allowed, but we might want to do this.
    return x

  1. Related to the above point, I’m not sure that there currently is a mypy-compliant way to import a function from another file and “extend it with additional overloads”. I think this is a very necessary capability, but also drastically increases the complexity, because now one needs to ensure that the type checker is aware of all relevant overloads defined in other files and perhaps even other packages.

  2. Perhaps the biggest problem is that, to make type checking work, the type checker will need to implement multiple dispatch. Here’s an example:

@overload
def add(x: int, y: Number) -> Number:
    return x + y


@overload
def add(x: Number, y: int) -> Number:
    return x + y


@overload
def add(x: int, y: int) -> int:
    return x + y



add(1, 2)

mypy will determine that all three overloads are possible. Ideally, we’d like mypy to know that the (int, int) -> int method is correct, but obviously this is the mechanism of multiple dispatch. The problem is that, by not being able to narrow down the list of possible methods using the principle of multiple dispatch, the return type will be the union of all possible return types, and that will likely be too broad to be useful. In the above example, the return type will hence be int | Number == Number, which is broader than necessary, because we’d like the return type to be int.

Reflecting on all these points, I come to two conclusions:

  1. Should we try to coerse overload into doing multiple dispatch? Could it be simpler to propose a new overload-like decorator, e.g. typing.dispatch, with relaxed semantics?

  2. For type checking to be truly functional and useful, mypy will need to do multiple dispatch. I unfortunately can’t see a way around this.

6

I don’t see why the typing module is involved at all here. This is a generalised improvement of functools.singledispatch so I would suggest to add functools.dispatch. Type checkers would need to be taught to understand what this decorator means but that does not mean that it needs to be any part of the typing module.

5 Likes
7

@oscarbenjamin It seems the conversation has a bit diverged. @ntessore is talking about adding a new function in the standard library + make it work with @typing.overload. The PEP we are talking about with @wesselb is about making multiple dispatch libs work with @typing.overload only (the second part of my previous sentence). Maybe we should open a new discussion for everything here related to typing? If it can help I’ll do it.

About the process/timeline

While I don’t exclude the existence of a multiple dispatch mechanism in the standard library with this PEP, we are focusing here on allowing it from a type-checking point of view. Once this is done, if there is a consensus, we can use this mechanism to implement a multiple dispatch function in functools, that will be supported by type-checkers.

Writing a multiple dispatch library/function is actually harder than it may seem at first glance, this is why we should let the third-party libraries explore this space first.

There is no rush, and once third-party libraries have matured (and they can do so especially if type-checkers and IDEs understand what is going on), we may choose an implementation to copy in the stdlib if we want.

About the comments of @wesselb on the PEP

1

This is what the whole PEP is about. While it’s not allowed from a type-checking point of view currently, it’s already allowed at runtime. We just want the type-checking system to follow this.

This is actually a very cool idea. I’m very open to it. I have no preference between the mechanism proposed in the PEP and this. Each have their own advantages and drawbacks. It may come down to what is the easiest to implement for type checkers. I could draft a second competing PEP with this. I’ll do it when I have the time.

2

While I can see why it may be annoying, the PEP 0 reccomend that PEPs are focused on one single thing, so I’m not planning to address this. This can be the subject of another PEP afterwards.

3

Same answer as above. I like the idea, but we’ll make progress faster by tackling one issue at a time. The proposed PEP doesn’t prevent this idea from being implemented.

4

Even if it’s called overload, for most cases, mypy actually does multiple dispatch instead of a true overloading. The example you gave isn’t actually correct. Here is your example slightly modified that shows how mypy does it:

from numbers import Number
from typing import overload, reveal_type


@overload
def check_return_type(x: int, y: Number) -> list[str]:
    ...


@overload
def check_return_type(x: Number, y: int) -> str:
    ...


@overload
def check_return_type(x: int, y: int) -> set[str]:
    ...


def check_return_type(x, y):
    ...


output = check_return_type(1, 2)

reveal_type(output)

$ mypy ./trying_stuff.py
trying_stuff.py:28: note: Revealed type is "builtins.set[builtins.str]"
Success: no issues found in 1 source file

The rules of mypy are actually much closer to a multiple dispatch than to an overload. Which makes sense since we’re working with a dynamic, uncompiled language, so there is only one correct answer, two branches can’t be taken at once. See More types - mypy 1.7.1 documentation for the exact rules.

Conclusion

Both ideas are good, I’ll make a second draft PEP for typing.dispatch.

We’re lucky since it already does it :slight_smile:

8

From my perspective I would really like multipledispatch to be something that is supported better in Python the language. It seems backwards to start from a typing decorator and then figure out the runtime part later though. If the runtime decorator was provided then we would not want to use both typing.overload and functools.dispatch: the type checker should just be expected to apply type rules that match what the runtime implementation does.

The PEP draft says:

This PEP proposes a new decorator, being no-op at runtime: @typing.multiple_dispatcher that informs type-checkers that we are working with a multiple dispatch library. The library must respect the signature resolution rules of typing.overload . Such rules can be found in the Mypy documentation:

There are actually significant limitations on how to make this work at runtime so advocating at the outset that the semantics follow mypy’s rules which do not have any runtime equivalent is backwards. First the runtime semantics need to be clear and then the type checker should respect those runtime semantics.

My experience of mypy in particular as a typechecker is that it is fragile and opinionated and often does not respect the actual runtime semantics of Python the language. I don’t want to see any PEP that explicitly says that Python the language should constrain its runtime behaviour to match mypy’s rules and actually I don’t think that any specific type checking tool should be referenced here as providing any definition of the rules.

This has already happened over many years. I think that the PEP should start by exploring or defining what those runtime semantics are that have already been implemented rather than advocating mypy’s overload rules from the outset.

There are significant differences between @overload and @dispatch. Firstly the concept of types in the two cases is different. You can use @overload with abstract types but @dispatch can only be used with concrete types. For example it is probably a mistake to allow @dispatch to be used with things like list[int] even though it sort of is a concrete type because what would happen at runtime in that case? Should the runtime implementation loop over the whole list checking isinstance(obj, int)?

Also the @overload rules say that the “order” of the decorators matters. That can be okay for @overload because all of the decorators for the same function will be in the same module. A real issue with multiple dispatch at runtime in Python is that the decorated dispatched functions might be in different modules. Then the runtime order of the decorators depends on the order of import statements. See e.g.:

1 Like
9

Surely the problem here is that, at runtime,

@overload
def fn(x: int) -> int:
    return x+2

@overload
def fn(x: str) -> int:
    return 42

is the same as

def fn(x):
    return 42

because the second definition replaces the first one - unless the @overload decorator implements multiple dispatch at runtime.

So I don’t think it’s reasonable to standardise this sort of mechanism for declaring multiple dispatch without the decorator also implementing it, as otherwise the runtime behaviour (in the absence of a 3rd party implementation) would be incredibly unexpected.

2 Likes
10

I do agree with you on this.

But in this case, how will type-checkers support third-party implementations of multiple dispatch? Will the one in functools be the only one supported?

This raises another question. Won’t it be confusing if we have both typing.overload and functools.dispatch and the rules differ slightly? Will type checkers be happy to implement two sets of rules that are slightly different? It’s going to be painful for type-checkers maintainers and Python beginners. Or maybe we could force the two to have the same rules by some kind of mechanism.

I do agree with this. I was quite sad that PEP 484 doesn’t specify any rules in case of ambiguity :sob: that would have been very helpful. I’m pretty sure type-checkers maintainers aren’t happy with it either.

Totally agree with this. I’m open to any alternative that supports type-checking with third-party libraries.

Agreed but many typing concept are very recents (protocols, generics) and third party libraries might want to support them.

This should be up to the library maintainer to decided. Many project allow today to check against generics like beartype’s is_bearable and pydantic’s TypeAdapter so type checking list[str] at runtime is feasable, just maybe not in the standard library.

Overall, I think we would like to go in the same direction, even if it takes a bit more time. The plan would be:

  1. Make a PEP that defines exactly the rules of @overload, at runtime and at “compile time”.
  2. Add a mechanism that will allow multiple-dispatch functions/libs to be understood by type-checkers. Those functions should follow the rules created at step 1.
  3. While third-party libraries can make crazy stuff with multiple dispatch, we can make an implementation of multiple dispatch that would go in functools and would have a reduced scope (it may be only isinstance(...) as you said).

Would you agree with this plan?

1 Like
11

or unless a decorator is used on the last declaration and uses typing.get_overloads(), which is the mechanism done by plum and overtake. So there is no issue with this code at runtime, it already works.

Type checkers are just annoying us with “the @overload-decorated function should have an empty body”. Pyright does it right now, see the desciption I made about this problem: GitHub - gabrieldemarmiesse/overtake: Have you ever dreamed of declaring the same function multiple times? .

I do agree, but supporting all types in the world might be very challenging and it’s a task third-party libraries may want to takle (I’m thinking about beartype and pydantic here). So the reference implementation may never be as complete as the rule. We’re in a pickle if we want to do present in a PEP both the rules and the runtime implementation of those rules.

1 Like
12

Yes, I think so but I also think that doing things in the wrong order will lead to the end result not working properly.

In my ideal future version of Python multiple dispatch is a core language feature and not something implemented by third-party libraries.

They should be required to implement different rules because I am almost certain that the existing overload rules will not work correctly for all cases. The multipledispatch library has to be very careful to make this work properly under multiple inheritance and the diamond problem etc. I guarantee that the existing implementation of this in mypy will not handle this because it has not been explicitly designed with runtime dispatch semantics in mind. Allowing the typecheckers to reuse their existing rules for this will fix in faulty semantics that then cannot be implemented properly at runtime.

This is the type checkers using the feature as intended. I know it might seem like an easy thing to just say “well we have @overload that is a bit like @dispatch so let’s just use that” but it is actually important that each feature be designed correctly with the intended use cases in mind. Currently @overload has not been designed deliberately for this use case and the implementations that handle it in type checkers will not correctly implement the rules that would actually be wanted at runtime.

1 Like
13

I think (but I know almost nothing about how type checkers work, so take this with a grain of salt) that the problem here is that type checkers have to recognise and process @overload specifically, so 3rd parties can’t implement a decorator that “works like the standard one”. That makes any sort of 3rd party experimentation tricky at best.

I admit I don’t know much here, though. What I’m basically meaning is, if I write a decorator:

def my_overload(fn):
    return typing.overload(fn)

then can I use that as

@my_overload
def f(x: int) -> int:
    ...

and have type checkers work that it’s an overload? If I can’t, then stdlib decorators have “special status”, and it’s not reasonable to expect that 3rd parties can experiment on an equal footing.

1 Like
14

Type checkers mostly* do not rely on implementation of function to determine the type of function. So your my_overload would not work. It is possible to make a my_overload that is type checked similar to standard library by doing,

from typing import TYPE_CHECKING, overload

if TYPE_CHECKING:
  my_overload = overload
else:
  def my_overload(…):
    …

That should work. If your my_overload needs different rules then exact ones normal overload does then you are stuck.

*: Mypy does not. Pyright does infer return types based on implementation but never infers overloaded type. It only infers concrete single type. Pyre/pytype unsure.

1 Like
15

If I understand correctly, what’s being proposed here is a decorator similar to PEP 681’s dataclass_transform - a meta-decorator which defines a multi-dispatch interface, that interface being decorator-based. (Currently, the draft says to repurpose typing.overload for the implementations but it doesn’t have to be that way.) I’m mentioning this only because a comparison with dataclass_transform could provide some insight into why having multi-dispatch in the stdlib might or might not be preferable.

1 Like
16

That’s what I thought. And that’s why I don’t see how it can be realistic to expect some sort of multiple dispatch decorator to be implemented in a 3rd party library, because type checkers won’t recognise it in exactly the way you describe.

Therefore, the conclusion I come to from this is that the only reasonable way of doing a typing-based multiple dispatch is by having some form of stdlib implementation, which type checkers then special-case in the same way that they special-case @overload. And given that multiple dispatch isn’t a type, it makes far more sense to me that it goes in functools and type checkers simply learn that this is where it’s imported from.

(I’m going to ignore, except for this comment, the fact that I think it’s incredibly limiting that type checkers require things like @overload to be built into the stdlib and defined by a PEP - I don’t like it, but it’s how things are so we need to work with the limitations it imposes).

1 Like
17

The draft PEP indicates that typing.multiple_dispatcher has no effect at runtime and is purely for the benefit of static type checking, but it doesn’t indicate how a type checker should change its behavior in the presence of typing.multiple_dispatcher. The remaining text seems to imply that the only behavioral change is to suppress any check for an implementation in the associated @overload functions. Is that correct?

If so, then I think the proposal is overkill for the problem it’s purporting to solve. I don’t think a new mechanism (or a PEP) is needed here. We simply need to agree that type checkers shouldn’t enforce that @overload function bodies must be empty. I think mypy already ignores this case, so no modification would be needed for mypy. A small change would need to be made in pyright. The only reason I added this check in pyright was to help educate people about the intended use of @overload. If we’re in agreement that @overload can be used for a broader set of use cases than those contemplated by PEP 484, then I could simply remove this check in pyright.

I don’t know if any change is needed in pyre or pytype. I suspect not, but someone should verify that.

I’ll note that the overload behavior for type checkers was never spec’ed fully. Mypy’s overload behavior is very complex, and its actual behavior doesn’t fully match its documented behavior, and I can point to inconsistencies in how it treats certain cases. I spent considerable time attempting to match mypy’s behavior in pyright, but small differences still exist. For a detailed documentation of pyright’s overload behavior, refer to this documentation. I think there could be value in standardizing overload matching behavior by formally spec’ing it, but that’s out of scope for this PEP.

I mention this to underscore the fact that multidispatch implementations will assuredly not match type checker behaviors exactly. It sounds like the behaviors implemented in existing multidispatch implementations are sufficiently close to the overload behaviors that it is useful to leverage this facility rather than creating some new parallel facility.

My recommendation is to abandon this PEP. I don’t think it’s needed.

If there is general agreement that the existing @overload mechanism is useful for multidispatch libraries, then I’ll remove pyright’s check for a non-empty @overload implementation, and that will allow further experimentation with this approach.

If there are objections to removing this check, another option is to simply recommend the use of # type: ignore to suppress this error for pyright users who want to experiment with the use of @overload for multidispatch.

5 Likes
18

I think that this is very important. It is very hard to get the semantics correct at runtime for multiple dispatch. Someone needs to explore how the current behaviour of type checkers compares with the (multiple) implementations of multiple dispatch that already exist. I am not even slightly convinced that existing type checkers handle the corner cases correctly. Just allowing type checkers to agree (or disagree!) on what they consider correct (without even a PEP) could completely hobble Python’s potential to ever have usable multiple dispatch. This is not just about typing because now in Python typing has the potential to dominate everything else so any typing proposal is a proposal that affects everything.

This proposal is one of many that puts the typing cart before the runtime horse. Turning it into an informal implementation that has no PEP or specification only makes that worse.

4 Likes
19

Indeed, you are right about that.

Yes, but also to warn the user if he/she implemented the wrong function. The main point of the PEP is to make sure type-checkers don’t get in the way of multiple dispatch libraries in the future. I can’t talk for all multiple dispatch library authors, but I think we could live without the warning I’m mentioning there.

I would be satisfied with this. @wesselb do you think that would be acceptable for plum? I thought a PEP might be needed for this agreement to take effect, but if there is a consensus about this, then let’s not jump through the full process. Removing this requirement will still allow multiple-dispatch libraries to grow and synergize with type-checkers and IDEs.

Very useful indeed, some codebases use multiple type checkers at once, they might run into trouble without a unified behavior.

I do agree. While not fully correct, just a for-loop on the signatures and taking the first corresponding one is enough for the vast majority of multiple-dispatch use cases. Library authors should be able to choose how far they go about matching the behavior of type-checkers.

Yes, I would very much like this option if that’s acceptable for everyone involved.

20

I’ll focus on runtime semantics and leave static type checking out of scope for this post.

On runtime semantics the first question is what kind of type annotations will be supported by this? I’d expect int/str/Foo (class Foo:) to all be clear to support. How about list[int], dict[str, int], Mapping[str, int], Sequence[int], Sequence[Mapping[str, str]]?

I consider types like list/dict pretty fundamental so they should have some support. Will multiple dispatch distinguish list[int] vs list[str]? How can it distinguish them?

I also consider types like Sequence/protocol/duck types pretty common and would want to avoid being stuck using concrete types and getting invariance issues. How would you at runtime check Sequence/Mapping/etc?

For protocols/ABC case isinstance can mostly work out fine. The generic case is more tricky to detect as at runtime [1,2,3] is just type list not list[int]. For generic standard library types you could special case them although runtime check may be expensive and wouldn’t handle user defined generic classes well. There’s a couple different options to support this case,

  1. Ignore generic type arguments. Support list, but do not distinguish between list[int] vs list[str].
  2. Allow specifying a checker function with dispatch for how to check it matches a type. This can handle any complexity generic and let the user decide what reasonable check is (for list[int] maybe check first element). Example would be,
@dispatch(checker=lambda ls: isinstance(ls, list) and len(ls) == 0 or isinstance(ls[0], int)
def my_func(ls: list[int):
  ...

@dispatch
def my_func(ls: int):
  ...

Only “complex” types would need to specify checker. Default checker would be simple isinstance check.

  1. Allow user to specify the expected type when calling the function. Have a reserved keyword argument called type. Simple enough types would not need to be specified and could be inferred with isinstance. Example,
@dispatch
def my_func(x: list[int]):
  ...

@dispatch
def my_func(x: int):
  ...

my_func(5) # Uses second dispatch
my_func(type=list[int], [1,2,3]) # Uses first dispatch
my_func([1,2,3]) # Error not supported. Complex types require explicit type
my_func(type=int, 3) # Uses second dispatch. type not required here, but allowed.

Of the 3, my preferred option is last. It can handle any type you want and is clear to reader which dispatch is being picked. For complex cases with multiple inheritance/overlapping types you can still specify type= as needed. It doesn’t have issues with generic/protocol types.