Multiple dispatch based on typing.overload

[oscarbenjamin]

@wesselb

@oscarbenjamin

The way to resolve this is that you have to guarantee that if both the types in question and the dispatching function have been imported into a module then all of the relevant dispatch rules will have also been imported.

The convention could be that, whenever you want to type check a function that uses multiple dispatch, you need to make sure that all methods that you’re using can be found with explicit imports of the form from module import f. The type checker could then dig into the imports and find all relevant methods.

The issue isn’t just about the typechecker but about what the runtime behaviour should be. Suppose we have:

# a.py

class A: pass

# b.py

@dispatch
def f(arg: int):
    ...

# c.py

from a import A

@dispatch
def f(arg: A):
    ...

# d.py

from a import A
from b import f

# Here c has not been imported (or it might have been from somewhere else)
f(A())

import c

# Here c has definitely been imported. Does this dispatch the same?
f(A())

Whether or not c was imported could change the runtime behaviour when calling f(A()) in module d.py and it might be that module c was imported before module d was or it might not.

[wesselb (Wessel)]

@oscarbenjamin

Whether or not c was imported could change the runtime behaviour when calling f(A()) in module d.py and it might be that module c was imported before module d was or it might not.

Under a “global function registry”, the first f(A()) would fail, whereas the second f(A()) would succeed. To be clear, the approach I’m attempting to describe is the following very simplistic approach:

# typing.py / multipledispatch.py

class Function:
    ...

def dispatch(f):
    methods[f.__name__].append(f)
    return Function(f.__name__, methods)

Slightly more sophisticated would be

# typing.py / multipledispatch.py

class Function:
    ...

class Dispatcher:
    def __init__(self):
        self.methods = defaultdict(list)

    def __call__(self, f):
        self.methods[f.__name__].append(f)
        return Function(f.__name__, self.methods)

dispatch = Dispatcher()

One can then either use a predefined dispatch, which would correspond to a “global namespace”, or one can define their own namespaces by creating more instances of Dispatcher. This approach seems to be, in my experience, most successful in practice.

[oscarbenjamin]

I think that the way that singledispatch does it is best. There is a single function somewhere and all other places need to import that function to define dispatch rules on it. Anyone who wants to call the function should import it from the original place where it was defined.

The global dispatch function namespace will obviously run into the problem of clashing names if it is widely used.

[wesselb (Wessel)]

The singledispatch approach is very reasonable, but it can become cumbersome to keep importing all functions that you need. In my opinion, from a runtime and user convenience point of view, there are pros and cons to all three approaches: f.dispatch, global namespaces, and user-defined namespaces.

Taking a step back, in an ideal world, it would be great if the runtime mechanism could be left up to the implementation. There currently are a host of multiple dispatch solutions that implement a variety of mechanisms, which includes the singledispach approach, global namespaces, and user-defined namespaces.

It would be really great if we could provide a way to make these implementations mypy-compliant. Based on the discussion so far, I see two ways forward:

1. Decide on the runtime mechanism once and for all, e.g. on the singledispatch approach, and build a typing solution around that. This sounds feasible, but obviously is very drastic. I would be happy with this on the short term, as it enables some form of type compliance, but a forcing solution like this doesn’t sound like a great long-term solution.

2. Let the runtime mechanism up to the implementation and come up with an innovative approach that makes typing possible for all implementations.

Regarding 2, what about something like the following. Whereas type checking currently proceeds by just running mypy, we could imagine a two-stage approach. In the first stage, it is the responsibility of the runtime implementation to produce some sort of output which collects all methods for all functions and writes this output in a way understood by mypy, e.g. in the form of type stubs. In the second stage, mypy performs type checking as usual. I suppose that a solution like this might already be possible?!

[NeilGirdhar]

@wesselb

which includes the singledispach approach, global namespaces, and user-defined namespaces.

How are these affected by threading? What are the pros and cons?

[oscarbenjamin]

@wesselb

The singledispatch approach is very reasonable, but it can become cumbersome to keep importing all functions that you need.

How do you propose to call a function if you don’t import it?

I must be misunderstanding something here…

[wesselb (Wessel)]

@NeilGirdhar

How are these affected by threading? What are the pros and cons?

That’s an interesting question. I’ve not thought about this much. Intuitively I would say that these are not much affected by threading, but I might be wrong.

@oscarbenjamin

How do you propose to call a function if you don’t import it?

You can’t use a function without importing it, but you can define functions without importing them.

[oscarbenjamin]

@wesselb

@oscarbenjamin

How do you propose to call a function if you don’t import it?

You can’t use a function without importing it, but you can define functions without importing them.

There are 3 different people/codebases involved here:

• project A defines an extensible dispatch function called f in module a.py.
• project B defines a new type B and adds a dispatch rule for f(B(...)) in b.py.
• project C wants to be able to call the function f and also wants to work with objects of type B.

The way I think that it should look is like:

# a.py

# f here will be the callable. The decorator extends it with
# dispatch rules but the object bound to `f` here is what any
# downstream code should import if it wants to call the
# function and have it dispatch to different types.
@dispatch
def f(arg: Any):
    raise NotImplementedError

@f.register
def _(arg: int):
    print("int")

Then B does:

# b.py

from a import f

class B:
    ...

@f.register
def _(arg: B):
    print("B")

Now project C can do

# c.py

from a import f
from b import B

f(B())

Which imports would you propose to remove here?

If you mean that b.py should not need to have from a import f then I disagree. It sounds like you are proposing that we could instead have

# b.py

class B:
    ...

# The dispatch decorator collects this into a global registry based
# on the function name f so it is added to the same dispatch rules
# with the function f from a.py even though that function is not
# imported here
@dispatch
def f(arg: B):
    print("B")

I don’t agree with using the function name globally like this. It is obvious that it will go wrong: two different projects could define a function with the same name and the dispatcher would mix them up. There has to be some way to associate the dispatch rule in b.py explicitly with the dispatch callable in a.py rather than just putting together all functions with the same name. I don’t see any way to do that without importing something somewhere.

It might be intentional that project B should be allowed to extend f by defining dispatch rules for the new type B that it provides. However we still need to ensure that importing f and B always loads all of the dispatch rules that are needed at runtime which means any that are defined in a.py as well as the extended rules defined in b.py. To make sure that this happens b.py needs to import something from a.py.

You could make a custom dispatcher but b.py would still have to import it:

# b.py

from a import f_dispatcher

class B:
    ...

@f_dispatcher
def _(arg: B):
    print("B")

This is not any better than just doing from a import f and using @f.register.

Another point is that for project C that actually wants to call the function f it should always be the case that they import it from its original defined location in module a. They should not do from b import f and then call f(...). While the dispatch rules might be added by many different modules there should still be a single place from which the actual callable is imported for use.

Note that everything I have said above already applies to the functools.singledispatch decorator and is exactly how it already works.

[wesselb (Wessel)]

@oscarbenjamin

If you mean that b.py should not need to have from a import f then I disagree. It sounds like you are proposing that we could instead have

This is indeed what I was suggesting. I agree that having a global registry will rarely be desirable, but dispatch = Dispatcher() to establish a namespace which is e.g. local to a package or module does sound reasonable to me:

# mypackage/__init__.py

_dispatch = Dispatcher()

# mypackage/diagonal_matrix.py

from . import _dispatch

@_dispatch
def diag(a: Diagonal):
    ... # Computation of the diagonal of a diagonal matrix

# mypackage/dense_matrix.py

from . import _dispatch

@_dispatch
def diag(a: Dense):
    ... # Computation of the diagonal of a dense matrix

Although the f.dispatch pattern would obviously work fine too here, I think a localised namespace approach like is still acceptable.

The overarching point is that there are a host of existing implementations which provide a variety of mechanisms. An approach to typing that would enable mypy-compliance for all would clearly be the best possible outcome. A perfect solution like that is likely not feasible, but I think it would be nice to come up with a solution that is as widely applicable as possible.

The underlying rule of the singledispatch pattern seems to be that, if a type checker is to find all methods for a function named f, it can do that by finding all references in the file at hand and backtracing the imports. This sounds very reasonable to me.

Now, if we decided that this would be a reasonable rule for type checkers to implement, then the next question would be how type checkers know that dispatch decoraters provided by third-party implementations should be treated as such. The essence of @gabrieldemarmiesse’s PEP sketch is to introduce a typing.multiple_dispatcher (name to be determined) that can be used to indicate that a certain decorator implements multiple dispatch and hence should be treated like typing.overload:

# multipledispatch.py

from typing import multiple_dispatcher

@multiple_dispatcher
def dispatch(f):
   ...

# a.py

from multipledispatch import dispatch

@dispatch  # The type checker now knows that this should be treated like `typing.overload`!
def f(x: int):
    ...

I think this idea is interesting and could work, though we’d likely need to carefully think about the details and specifics.

[oscarbenjamin]

@wesselb

to establish a namespace which is e.g. local to a package or module

Most of the potential benefit of dispatch is lost if it is only local to a single codebase. In that limited situation it is just syntactic sugar for what if/elif can already do. Having a callable function that downstream codebases can extend is a very different proposition.

@wesselb

An approach to typing that would enable mypy-compliance for all would clearly be the best possible outcome.

I still think that “mypy-compliance” is a red herring here. We need to focus on what is useful at runtime first. Mypy or other type checkers can be made to work with it later.

There are a lot of details to be considered for any runtime implementation that need to be explored carefully. I don’t want to see anyone propose rules for type checkers without spelling those out for consideration. There can be room left for ambiguity but we start by looking at how to make it work at runtime and then consider what typecheckers might do afterwards. Posing the problem the other way around would inevitably mean designing something that does not work properly (fast, well defined, free of bugs, etc) at runtime.

[wesselb (Wessel)]

@oscarbenjamin

I still think that “mypy-compliance” is a red herring here. We need to focus on what is useful at runtime first. Mypy or other type checkers can be made to work with it later.

Right! I’ve been operating under the assumption that we would like to make existing implementations typing compliant, but you seem to want to discuss runtime details in more detail. For this, I think its helpful to study existing implementations to see works and what people like. The following would probably be good to look at:

• github .com/mrocklin/multipledispatch
• github .com/coady/multimethod
• github .com/beartype/plum

Please remove the spaces in the links above. I’m not able to post multiple links, since I’m a new user. Disclaimer: I’m one of the authors of Plum.

@oscarbenjamin

There are a lot of details to be considered for any runtime implementation that need to be explored carefully.

That’s definitely true. The first PyPI release of multipledispatch was in 2014, the first release of multimethod was in 2013, and the first release of plum-dispatch was in 2019, so I think it’s fair to say that sufficient time has passed and effort has been spent for these implementations to have converged onto something that works well, at least in practice. Unless these implementations have any obvious shortcomings, I’m not sure that there is a need to develop another.

@oscarbenjamin

Most of the potential benefit of dispatch is lost if it is only local to a single codebase. In that limited situation it is just syntactic sugar for what if/elif can already do. Having a callable function that downstream codebases can extend is a very different proposition.

You need not restrict yourself to either local/global namespaces or f.dispatch. You can combine them. This, in fact, is what I tend find most convenient in practice. Within a package, use a local namespace created with dispatch = Dispatcher(). When extending functions defined by other packages, use from otherpackage import f in combination with @f.dispatch. But one is always free to use whichever pattern they find most clear.

The practical problem at hand is not that one cannot effectively use multiple dispatch at runtime, whether that be with @f.dispatch or with local/global spaces, since both are possible with the implementations listed above. The problem is that it’s hard to write such code which is typing compliant too.

[oscarbenjamin]

@wesselb

That’s definitely true. The first PyPI release of multipledispatch was in 2014, the first release of multimethod was in 2013, and the first release of plum-dispatch was in 2019, so I think it’s fair to say that sufficient time has passed and effort has been spent for these implementations to have converged onto something that works well, at least in practice. Unless these implementations have any obvious shortcomings, I’m not sure that there is a need to develop another.

Firstly there are shortcomings e.g. the multipledispatch issue that I linked above:

Ordering of classes depends on order of function statement execution

Secondly I expect that if someone was to look at it closely they would find that the different implementations are not consistent with one another.

If the idea is to design typing rules that should work with these existing implementations then we need to be clear about what exactly are the differences and commonalities between them and how that relates to any choice for typechecker rules. We should also bear in mind that there might be the possibility for a new implementation to be better than all of the existing implementations and we should not design any typechecking rules now that would prevent that in future.

Before even contemplating things like list[int] we should be clear about how basic types like class A, class B(A) etc are handled. I think that multipledispatch does a good job of handling multiple dispatch when there are potentially subclasses of different arguments in an inheritance hierarchy. I have not used the other implementations so I can’t comment on them.

What I mean by subclasses of different arguments is something like:

class A: pass

class B(A): pass

class C: pass

class D(C): pass

@dispatch
def f(arg1:A, arg2: D):
    print('AD')

@dispatch
def f(arg1: B, arg2: C):
    print('BC')

# Which implementation should this call?
f(B(), D())

This is the major complication of multiple dispatch over single dispatch. I haven’t immediately tested but I think that multipledispatch would give an AmbiguityWarning in this case.

The next hurdle is multiple inheritance. In this case multipledispatch fails because it does not consider the mro i.e. the order of __bases__ properly (see linked issue).

The next hurdle is how to ensure that all dispatch rules are loaded at runtime i.e. that all relevant modules are imported when needed (hence “type piracy” above). The suggestion above that dispatch rules with no import connections could be used would be unworkable in general at runtime and also impossible for typecheckers. I think that functools.singledispatch handles this case well but there are caveats involved in making it work properly without the side effect that import x would not break seemingly unrelated code in other modules.

All of this is before we even get to something like list[int] which I doubt that any implementation handles properly. I would be inclined to leave something like list[int] as undefined for now and focus on other things first. Probably list[T] can work in some cases but what those cases are needs to be made well defined because it is bad to standardise rules for things that could not really be made to work properly in general.

If the intention is to try to standardise typechecking rules for the existing implementations then the way to push this forwards is to do detailed investigation of what those existing implementations do and what are their similarities, differences, strengths, shortcomings and what potential improvements might be. Without these investigations being done and the results of the investigations reported I don’t see how anyone could agree any typechecker rules.

[wesselb (Wessel)]

@oscarbenjamin

We should also bear in mind that there might be the possibility for a new implementation to be better than all of the existing implementations and we should not design any typechecking rules now that would prevent that in future.

I agree that we should keep this in mind, although it would be even better to contribute to existing implementations to try to fix any possible minor or major flaws.

@oscarbenjamin

I have not used the other implementations so I can’t comment on them.

In Plum, we carefully consider (multiple) inheritance and the MRO. Plum also handles types like list[int] well, thanks to Beartype. Multimethod handles list[int] too.

@oscarbenjamin

If the intention is to try to standardise typechecking rules for the existing implementations then the way to push this forwards is to do detailed investigation of what those existing implementations do and what are their similarities, differences, strengths, shortcomings and what potential improvements might be. Without these investigations being done and the results of the investigations reported I don’t see how anyone could agree any typechecker rules.

I agree with the sentiment of this paragraph, but before engaging in a detailed comparison it would make sense to agree on what we would be working towards. In an ideal world, we would spell out in detail how mulitple dispatch in Python is supposed to work, setting rules for runtime implementations to conform to. Obviously, this would be a massive effort and require a likely very lengthy discussion. Another approach would be to see if a non-perfect, but simpler solution is possible, e.g. by relaxing the semantics of typing.overload.

[pf_moore (Paul Moore)]

@wesselb

In an ideal world, we would spell out in detail how mulitple dispatch in Python is supposed to work, setting rules for runtime implementations to conform to.

I’d put it the other way round. If the various implementations are still trying out different approaches, it’s too soon to be thinking of making any changes to the stdlib or typing in order to support them. Once a clear “best approach” has become obvious, then we can look to add standard support for it.

[ntessore (Nicolas Tessore)]

While I’m enjoying the discussion, I want to point out that my original question was very much with the idea in mind that bolting multiple dispatch onto overload sidesteps the issues mentioned in this thread: Instead of solving the general multiple dispatch problem, such a dispatcher inherits the much more constrained rules of overload, and is understandable to type checkers by definition.

[pf_moore (Paul Moore)]

I guess the answer to that is “because no-one has written one”? It doesn’t have to be in the stdlib, so if there’s nothing on PyPI then either this is an opportunity for someone to write one, or it’s because the people interested in writing multiple dispatch implementations prefer different approaches.

Why not simply refine your “toy” implementation and publish it on PyPI? I feel that sometimes good ideas get stalled by a desire to get them added to the stdlib, when actually it would be far better to just get something available. (Disclaimer: I have almost never found a need for multiple dispatch in code that I’ve written, so I can’t really comment on the trade-offs between your idea and the other multiple dispatch libraries that have been brought up here).

[oscarbenjamin]

@ntessore

my original question was very much with the idea in mind that bolting multiple dispatch onto overload sidesteps the issues mentioned in this thread: Instead of solving the general multiple dispatch problem, such a dispatcher inherits the much more constrained rules of overload, and is understandable to type checkers by definition.

What use is it to define type checker rules for multiple dispatch without making any progress on “solving the general multiple dispatch problem”?

It is clear that @overload was not defined with this usecase in mind and is also not suitable for this usecase. I don’t think that using @overload “sidesteps” the problem. Rather it would make it harder to arrive at any proper solution in future. If you think that the @overload semantics are good enough in any sense for multiple dispatch then you are aiming for a broken multiple dispatch that has no utility beyond syntactic sugar.

This is a very basic point which I already mentioned above: how can @overload be used to extend a function that was defined in another module?

It is a waste of time even to contemplate endorsing a version of multiple dispatch that cannot work across multiple modules. If all dispatch rules are in one module then multiple dispatch achieves nothing more than what basic constructs like if/elif can already do more efficiently. When multiple dispatch is used well the main benefit is that a function from one codebase can be extended to support new types defined in another codebase.

[NeilGirdhar]

@oscarbenjamin

If all dispatch rules are in one module then multiple dispatch achieves nothing more than what basic constructs like if/elif can already do more efficiently.

I agree with your main point that overload is probably too restricted to be used to denote multiple dispatch. However, in a single module, multiple dispatch is more succinct than switching since the switching code is essentially implemented by the multiple dispatch library. Whatever you denote the multiple dispatch with (say, @multiple_dispatch) is probably just as wordy as the switching code’s type annotation (whcih needs @overload).

But, yeah, I agree that @overload is too restricted for this use case since it probably can’t be made to work across modules. I really love the attention and excitement about multiple dispatch in this thread, and I hope we make progress towards a general solution.

[wesselb (Wessel)]

@pf_moore

I’d put it the other way round. If the various implementations are still trying out different approaches, it’s too soon to be thinking of making any changes to the stdlib or typing in order to support them. Once a clear “best approach” has become obvious, then we can look to add standard support for it.

That very fair, though I wouldn’t say that implementations are still trying out approaches. Multimethod and Plum are becoming fairly mature and perhaps could even be considered candidates for a “good enough” implementation. Obviously that would have to be determined carefully.

[ParadaCarleton (Carlos Parada)]

@pf_moore

Why not simply refine your “toy” implementation and publish it on PyPI? I feel that sometimes good ideas get stalled by a desire to get them added to the stdlib, when actually it would be far better to just get something available. (Disclaimer: I have almost never found a need for multiple dispatch in code that I’ve written, so I can’t really comment on the trade-offs between your idea and the other multiple dispatch libraries that have been brought up here).

This feels like a great illustration of why the power of multiple dispatch is so subtle and easy to miss. People don’t realize how helpful multiple dispatch is because you rarely need multiple dispatch in your own code. What I really need is for everyone else to have multiple dispatch in their code!

Although rarely phrased this way, multiple dispatch is kind of like inheritance, but for functions. The principle of inheritance is I can’t change your classes; that would be bad. But I don’t want to just rewrite all the code in that class. So what if I just take your class, but change it up a bit? I want a class that acts just like your class, except in a few cases.

But there’s something missing from this feature. If we really have first-class functions like we’re supposed to… how do I do the same thing with functions?! What if I want to extend your function? Multiple dispatch says “Sure, go ahead” – you can always create more methods for an existing function. My function behaves just like yours, unless I say otherwise (“subtype” it, by creating a submethod to handle a specific case).

This is why multiple dispatch never seems useful until you have it, and then once you do, you can’t live without it. To someone used to Julia (like me), missing multiple dispatch in Python feels just like–well, it feels just like I did when I learned Julia doesn’t let you do multiple inheritance!