Intersections with Callable, in particular Any & Callable

[randolf-scholz]

In this issue, we shall discuss intersections with Callable. There is an unresolved issue with respect to Any & Callable, that stems from the following 2 axioms:

1. Intersections with Callable are resolved by intersecting with an equivalent Callback-Protocol (see current draft)
2. (x & y).foo = x.foo & y.foo (see Eric's outline: Handling of Any within an Intersection #1 (comment))

Both of these together can lead to infinite regress.

Therefore, we cannot use ① when intersecting function-types with function-types. One can distinguish 3 cases:

1. Intersections of function-types with non-function-types: then we can apply rule ①
2. Intersections of two function-types: regular subtyping and the more complicated function signature subtyping rules apply.
3. Intersections of function-types with Any

---

EDIT: The suggestions below are outdated. The intersection with Any is irreducible. What needs to be discussed is what happens when the type is attempted to be evaluated with arguments args.

---

As I see it, there are 2 options of how to resolve ③:

Ⓐ For a strict interpretation of Any as an unknown type, Any could feasibly be Callable[..., R], which is a "consistent" subtype of Callable[[T1, T2, ..., Tn], R]. It follows that:

Any & Callable[[T1, T2, ..., Tn], R] = Callable[..., R]

The consequence is that (Any & T).foo(*args, **kwargs), is valid for any method foo of T, which as expressed in the Any intersection thread causes some pains, as it makes Any & T behave very similar to Any itself (only attribute types and function return types are preserved)

Ⓑ An alternative approach would hinge on a slight re-interpretation of Any in the context of intersections. One could demand that Any shall be interpreted as a disjoint type from whatever it is intersected with (= maximum compatibility). That is, in Any & T, we interpret Any as an unknown type that presumably shares no overlapping methods with T. This leads to

Any & Callable[[T1, T2, ..., Tn], R] = Callable[[T1, T2, ..., Tn], R]

I.e. we come back full circle to question if Any can be simplified away from intersections. Under this premise, we would have 3 simple rules, as I mentioned in #1 (comment)

1. Any & T is an irreducible form
2. (Any & T).foo ≅ T.foo if T implements foo
3. (Any & T).bar ≅ Any if T does not implement bar

---

So, does it make sense to have a general exemption to the rules #1 (comment) when intersecting Any with function-types?

[randolf-scholz]

EDIT: There is possibly also a sort of middle ground option:

Ⓒ Only subtyping rules of Callable apply, but not the "consistent" subtyping rules. (see draft document for the distinction). That is, Any & Callable can mess with the argument types, but not the signature.

Any & Callable[[T1, T2, ..., Tn], R] = Callable[[Any, Any, ..., Any], R]

Under this approach, (Any & T).foo would have the same function signature as T.foo, but any argument type would be allowed. However, I kind of doubt either camp would be happy with Ⓒ.

[DiscordLiz]

If all of these are accurate:

1. That type checkers are willing to provide an optional warning for Any as an intersection operand
2. That there are no shortcuts that allow skipping certain checks that are not able to be shown as formally equivalent.
3. That these are the distinct places in this example that the intersection is consulted and how

x: A & B = ... # Here, we have to still check that x is both A and B

def f(x: A & B): 
    x.foo()  # here, we have to check that this is consistent use with definitions for all existing defintions of foo in A & B

f(something)  # here we check that something is both A and B

No special case needed.

[randolf-scholz]

Wait a second, I think this actually means that this whole example from earlier should already work fine, we don't even need

1. That type checkers are willing to provide an optional warning for Any as an intersection operand

from where import UntypedLibraryType
from typing import Protocol

class Mine(Protocol):
    def foo(self, x: int, /) -> int: ...

def fn(x: UntypedLibraryType & Mine):
    x.foo(1)  # this is how I expect it to be used
    x.foo("blah")  # this works because UntypedLibraryType is Any, and I would intend this as an error

The type-checker will test whether the signature foo(__x: str) is compatible with Mine.foo and Any.foo, and will consequently fail. If this wasn't how it is working already, then it would apply in the same vein to

from typing import Protocol

class Mine(Protocol):
    def foo(self, x: int, /) -> int: ...

def fn(x: Mine):
    x.foo(1)
    x.foo("blah")

I think this really does mean that we can simplify Any & C = C for any function-type C.

[diabolo-dan]

The type-checker will test whether the signature foo(__x: str) is compatible with Mine.foo and Any.foo, and will consequently fail.

It need only be consistent with one of Mine.foo and Any.foo, and it is consistent with Any.foo.

[randolf-scholz]

@diabolo-dan why only with one of them?

[erictraut]

Here's how type checkers handle calls on unions today in Python:

When A | B is called with args:

• If either A or B is not callable with args, the operation is an error
• If A and B are both callable with args, the return result is the union of the return results from A and B
• Any is treated as Callable[..., Any]

By symmetry, I would think that the rule for intersections would be:

When A & B is called with args:

• If neither A or B are callable with args, the operation is an error
• If A is callable with args but B is not, the return result comes from A
• If B is callable with args but A is not, the return result comes from B
• If A and B are both callable with args, the return result is the intersection of the return results from A and B
• Any is treated as Callable[..., Any]

And yes, this means that if an Any appears in either a union or an intersection, the resulting return type will include an Any. That's the nature of Any, and we should be consistent here.

Interestingly, TypeScript deviates from the above slightly in the case of intersections. If A and B are both callable with args, TypeScript uses the return type from A only. It apparently sorts the types (using an undocumented sorting algorithm) to maintain determinism and order independence of intersections. You get the same answer for A & B and B & A, but if you swap the names of the two interfaces, the result changes. So the sorting algorithm probably takes into account the names of the types.

interface A {
    y: (val: string) => number;
    z: () => number;
}

interface B {
    y: (val: number) => string;
    z: () => string;
}

function f(c: A & B) {
    const x = c.x(); // Error
    const y1 = c.y(0); // string
    const y2 = c.y(''); // number
    const z = c.z(); // number (but becomes string if A and B interface names are swapped)
}

The behavior in TypeScript seems inconsistent to me, and the "undocumented sorting algorithm" means that it cannot be replicated from a spec unless that spec fully documents the way types should be sorted. I'd prefer to avoid that for Python.

[erictraut]

Edit: The following was a response to an earlier post that was deleted. I'll leave it here, but it's probably no longer valid.

---

@randolf-scholz, good point. That means my proposed rule above is flawed. "If A and B are both callable with args, the return result is the intersection of the return results from A and B" doesn't hold.

This would explain TypeScript's behavior. It is effectively creating an overload from the two callables. The challenge is that overloads depend on ordering, but intersections are order-independent. That means some deterministic order must be imposed, which explains the sorting behavior in TypeScript.

In TypeScript, overloads are simple. The first matching overload is always selected. In Python, thanks to mypy's implementation, overloads are extremely complex and involve a bunch of special casing for union expansion and handling of Any arguments. To avoid this complexity, we could avoid the mention of "overload" and instead define the rule as follows:

If A and B are both callable with args, the return result comes from the return type of Sort(A, B) where Sort is a sorting algorithm that deterministically chooses either A or B.

We would then need to define the sorting algorithm. (Yuck.)

I have a type sorting algorithm in pyright that I added in an attempt to make union-related operations more deterministic and order-independent, but I consider this algorithm to be an implementation detail. I presume that mypy has a similar sorting algorithm.

Maybe it's OK to leave the sorting algorithm out of the spec and say that it's up to each type checker to implement this? But this will lead to different behaviors across type checkers.

[randolf-scholz]

Hm, I think there is a problematic case though, which is incompatible signatures:

class A:
    def foo(self, *, key: str) -> T: ... # takes 1 mandatory keyword argument "key"
class B:
    def foo(self) -> S: ...

The issue here is that by the LSP, one is not allowed to have a subclass of B where foo has mandatory key arguments.
One is generally only allowed to add optional arguments, i.e. arguments with defaults, *args, and **kwargs.

I think one has to amend the rules as follows: When A & B is called with args:

• If neither A or B are callable with args, the operation is an error
• If A is callable with args, and signature(args) ≤ signature(B), the result comes from A.
• If A is callable with args, but signature(args) incompatible with signature(B), the operation is an error
• If B is callable with args, and signature(args) ≤ signature(A), the result comes from B.
• If B is callable with args, but signature(args) incompatible with signature(A), the operation is an error
• If A and B are both callable with args, the return result is the intersection of the return results from A and B
• Any is treated as Callable[..., Any]

Also, I wonder if "the operation is an error" can generally just be replaced by returning Never and type-checker raising whenever an instance of Never is created.

[randolf-scholz]

@erictraut I deleted the earlier comment, the argument was flawed. In the example

class A:
    def foo(self, x: int) -> int: ...
class B:
    def foo(self, x: str) -> str: ...
class C(A, B):
    @overload
    def foo(self, x: int) -> int: ...
    @overload
    def foo(self, x: str) -> str: ...

C is not a proper subclass of A & B since C.foo(int & str) would yield int, violating LSP for class B.

Actually, I am not the only one who fell for this, in the current specification draft for Protocol-merging the overloads are used as well.

[mikeshardmind]

I think most of this is ruled out by the original assignability check.

I don't think it should be picking one of A or B as typescript does. If the two are incompatible, the two are incompatible. If they aren't, compatible use should be acceptable, but the assignability concern says it needs to be compatible with both. We aren't stating that there is a direct subclass with a specific MRO with intersections, and even if we were, replacement says such a subclass would have to be compatible this way too.

@DiscordLiz linked an accepted (rust) RFC in #14 that has a section detailing detecting overlapping implementations that feels relevant here

[mikeshardmind]

There's also my comment here

quick relevant part:

As an exhaustive pattern for example
(A & B).foo
if A provides foo and B doesn't, A.foo
If B provides foo and A doesn't, B.foo
if both A and B provide foo, A.foo & B.foo
if neither A nor B provide foo, Never

Other than this not checking for compatibility between operands at the time of use (consistent subtyping, we should assume it from assignability), and only needing to check that use is compatible with each operand individually, this should align with how rust does this, and align with a general expectation of "I specified being compatible with each of these"

[DiscordLiz]

I don't think it should be picking one of A or B as typescript does. If the two are incompatible, the two are incompatible. If they aren't, compatible use should be acceptable

Yeah, but there's still a problem with that here:

class A:

    def foo(self) -> None:
        ...

class B:
    def foo(self, wait: bool = False) -> None:
        ...

def f(x: A & B):
    x.foo()  # fine
    x.foo(wait=True)  # not fine, not consistent with A.foo? But something consistent with A.foo and B.foo should allow this.

I think this shows that we have to check that overlapping attributes and methods have compatible overlap and determine what that compatible overlap is. We can't split assignment from use without first calculating a compatible overlap.

This means that #5 actually does need to be a type checking concern and mandated. This behavior needs to be part of the spec.

We also shouldn't arbitrarily pick a class, or try to determine what the mro would need to be, this is an intersection, not a direct subclass. someone could inherit from both and reconcile in a way that would be impossible without further additions than just these as base classes

class A:
    def foo(self) -> None:
        ...

    def bar(self, wait: bool = False) -> None:
        ...

class B:
    def foo(self, wait: bool = False) -> None:
        ...

    def bar(self) -> None:
        ...

This example shows that anything there are cases that would need additional reconciliation, even as just a subclass, let alone an intersection.

[DiscordLiz]

Going from that minimal overlap calculation, here would be some of my expectations

() -> None & (optional: bool=False) -> None = (optional: bool=False) -> None
(int) -> int & (int) -> str = Never

But in the above, we could modify it only slightly and also have a solvable case:

(int) -> int & (str) -> str = (T) -> T, for T: int | str

we also have to consider names as part of the api here when discussing something being compatible with both

(not_pos_only_name: int) -> int  & (different_not_pos_only_name: int) -> int = Never

[randolf-scholz]

@DiscordLiz When we take the literal definition of meet (=Intersection) and join (=Union) from partially ordered sets, then the meet/intersection is by definition the greatest lower bound

Definition: X is a greatest lower bound if and only if:

1. X ≤ A and X ≤ B ("X" is a lower bound to both A and B)
2. If Y≤A and Y≤B then Y≤X ("X" is greater than any other lower bound)

Lemma:

1. A greatest lower bound need not exist for given A and B (well, technically we can assign Never)
2. If it exists, it is unique, hence we call it the greatest lower bound and annotate it as A&B.

---

In the example you have given, therefore, A&B should be the most general subclass possible that is both compatible with A and B, so something like

class C(A,B):
    def foo(self, wait: bool = False) -> None: ...
    def bar(self, wait: bool = False) -> None: ...

which is a valid subclass of both A and B. Note that in the example I gave in #16 (comment), such a shared subclass is impossible due to LSP violation.

[DiscordLiz]

@randolf-scholz yes, that's exactly what I was getting at with that example, but also pointing out that Typescript's approach of just picking one side would never work for that case. I didn't feel I needed to spell that out how it was possible to resolve, especially in the presence of prior conversation and further examples.

[randolf-scholz]

Regarding overlap violation, I think this is really complex since it depends on function signature subtyping, which needs to take into account the 5 different argument kinds possible in python: POSITIONAL_ONLY, POSITIONAL_OR_KEYWORD, VAR_POSITIONAL KEYWORD_ONLY and VAR_KEYWORD.

[DiscordLiz]

Regarding overlap violation, I think this is really complex since it depends on function signature subtyping, which needs to take into account the 5 different argument kinds possible in python: POSITIONAL_ONLY, POSITIONAL_OR_KEYWORD, VAR_POSITIONAL KEYWORD_ONLY and VAR_KEYWORD.

I don't think this makes it more complex, at least not much.

We can say that

1. Nothing should move fromPOSITIONAL_ONLY to POSITIONAL_OR_KEYWORD, as this would defeat the purpose of POSITIONAL_ONLY's existence, to not expose a name as part of the api
2. For symmetry with 1, nothing should move from KEYWORD_ONLY to POSITIONAL_OR_KEYWORD *
3. Nothing can move from POSITIONAL_OR_KEYWORD to KEYWORD_ONLY or POSITIONAL_ONLY without breaking compatible use.
4. exposed parameter names must be unique across all groups in total
5. unexposed parameter names (POSITIONAL_ONLY) may be changed to allow compatibility with the prior point

* There is a way to make a signature that does this and is compatible as a method of a subtype.

I think we should just say that for the purposes of this, we handle each group individually, then check on handling points 4 & 5. While point 2 is stylistic in choice, rather than having a direct functional reason, I'd also rather not change library author's intent by intersecting their type with someone else's.

Additionally, if the same name shows up in different groups across callabled, it might be a stronger indication that they aren't used the same way and shouldn't be treated as compatible.

Not allowing movement between groups (1-3) allows a simple solution that does not need to consider these groups, but instead operate on each of them independently and check that the total signature is valid at the end.

[NeilGirdhar]

So, does it make sense to have a general exemption to the rules #1 (comment) when intersecting Any with function-types?

I don't think it's a good idea to have an exception to the rule. I think we should have a principle that changing any annotation from SomeClass to Any should not create type errors. If you had:

Any & Callable[[T1, T2, ..., Tn], R] = Callable[[T1, T2, ..., Tn], R]

then it could create errors even though substituting a type for Any would have no error.

It's the same for the middle ground option.

I think it must be that:

Any & Callable[[T1, T2, ..., Tn], R] = Callable[..., R]

I don't think it's a good idea to get into the weeds about "signature compatibility". The rule for calling A & B should be based only on the validity and return values of A and B and no examination of parameter specifications.

The key idea is that just because A is not callable with the arguments, it doesn't mean that A's subtype isn't callable with the arguments. But if neither A nor B are callable with the arguments, then the type checker should return an error for the same reason that it does when A alone is called with incorrect arguments (A alone doesn't "promise enough").

Therefore, let the result type of calling A with arguments (evaluating overloads, etc.) be RA. If A is not callable with the arguments let SA be the narrowest return type possible for calling A (e.g., if A has many overloads, it's the union of the return types of those overloads). Similarly define RB and SB. Then when A & B is called:

• If neither A nor B are callable with arguments, the operation is an error (since neither side "promises enough").
• If A is callable with the arguments, but B is not, the return result is RA & SB.
• If B is callable with the arguments, but A is not, the return result is RB & SA.
• If both of A and B are callable with the arguments, the return result is RA & SB | RB & SA.

Now, examine the various cases based on these rules:

• When B <: A, case 2 is satisfied as long as B is callable with the arguments. The result type is RB as long as LSP is obeyed.
• When neither is callable with the arguments, it's an error.
• When both are callable with the arguments, it's the intersection.
• When one is callable with the arguments:

class A:
    def f(self) -> RA:
        return 1

class B:
    def f(self, *, x: int = 1) -> RB:
        return 1
# (A & B).f() = RA & RB
# (A & B).f(x=1) = RA & RB

[randolf-scholz]

If both of A and B are callable with the arguments, the return result is RA & SB | RB & SA.

Can you explain this a bit? Why is it not RA & RB?

[DiscordLiz]

I don't think it's a good idea to get into the weeds about "signature compatibility". The rule for calling A & B should be based only on the validity and return values of A and B and no examination of parameter specifications.

This is part of the type. We have to have rules to resolve this. Ignoring the parameter specification does not work, examples of this above. We only know a minimum bound

[mniip]

@DiscordLiz In your example the issue of "compatible overlap" can actually be decoupled from the issue of working with paramspecs. We can restate the problem as follows:

class EmptyCall:
    def __call__(self): ...
class WaitCall(EmptyCall):
    def __call__(self, wait: bool = ...): ...
class A:
    foo: EmptyCall
    bar: WaitCall
class B:
    foo: WaitCall
    bar: EmptyCall

Here we used our domain knowledge of paramspecs to claim that all functions with a signature (wait: bool = ...) can be used where a () signature is expected, hence WaitCall is a subclass of EmptyCall. From this point on it doesn't really matter that these are about functions. The intersection A & B is indeed a type with {foo: WaitCall, bar: WaitCall}, meaning both of these are valid:

def foo(x: A & B):
  x.foo.__call__(wait=True)
    # we know x must be a B hence x.foo is known to be a WaitCall hence we can use its "method"
  x.bar.__call__(wait=True)
    # we know x must be an A hence x.bar is known to be a WaitCall hence we can use its "method"

[randolf-scholz]

@mniip If x is annotated as A&B then both x.foo and x.bar must be compatible with both WaitCall and EmptyCall.

[mniip]

@randolf-scholz if x.foo is compatible with WaitCall then it is also compatible with EmptyCall because of the subclass relationship.

[DiscordLiz]

@randolf-scholz your overloads there are incorrect, but it will still be complex and there is no way around this @erictraut brought concerns up with this in #5, and unfortunately we can now show this is necessary.

We can't fully express the true type here without a Not operator, but I'm still discussing with others on this, as Not presents a necessary behavior branch for Any

[DiscordLiz]

So, we need a Not as a prerequisite to this. Maybe we can leave this to the internals of typecheckers, but I think users should be able to express all types that the type system knows need exist.

The problem here comes from the following:

(A) -> A & (B) -> B

There is something which is consistent with both, that being

(T) -> T, for T: A XOR B

The equivalent overload set would be

(overload) (T) -> T, T: A & Not(B)
(overload) (T) -> T, T: B & Not(A)

If A&B is passed in place of T, there is no return value consistent with the intersection of callables. While the function might be a passthrough of type and result in A&B, we can't know this to be the case.

This matters for typechecking usage in functions receiving an intersection.

XOR cannot be expressed without negation of some form, the easiest way would be Not

Current type theory would suggest that Not is only valid for Static Types.

I would thus recommend the following behavior:

If a gradual type with disjoint paramters is encountered in an intersection of callables, we have to widen it to the widest callable and lose type information. We could reject it, but this goes against gradual typing.

For all disjoint static type paramter lists, we can create what is a restricted overload set that explicitly disallows anything which would create a problem with resolving a return type as ambiguous use.

Not[Any], Not[tuple[T, ...]], And any other unmentioned gradual types should be explicitly forbidden from Not. Any typechecking internals which might create it should branch charitably to gradual typing before this point in time.

[NeilGirdhar]

then I think the greatest lower bound is something like...

My point is that I think it should be possible to assess both the validity of the call and its return value (which is all you need) without synthesizing the entire interface.

In particular, note that if we ask: what are the possible return types of (X&Y).foo? Then the answer should be (A & C & D) | (B & C & D) | (A & B & C) | (A & B & D).

I'm not convinced of that. I think it's: ((A | B) & C) | ((A | B) & D) | (A & (C | D) | (B & (C | D)), which by distributivity just gives A&C | B&C | A&D | B&D | A&D | B&D.

I think you can check this by assuming that the intersections A&B and C&D are empty, and then passing P&R. According to the return value you gave, this would give never, but I think it should should give result type at least A&C.

[mikeshardmind]

My point is that I think it should be possible to assess both the validity of the call and its return value (which is all you need) without synthesizing the entire interface.

Unfortunately, this doesn't work. Rust's overlapping trait implementation resolution ran into a similar, yet different thing too, and they showed there were some cases where it was impossible to determine which implementation should be used correctly.

There are some parameters that we can't determine the correct return type for without more information than what the intersection provides, we can exclude those using the method @DiscordLiz explained above, either with bound type variables, or with overload sets.

Personally, I like the succinctness of the type variable method of consolidating them, but it may be less clear than the overload set for some people, and they are equivalent.

I think you can check this by assuming that the intersections A&B and C&D are empty

Where does this assumption come from? This is only possible to assume if there are class conflicts between intersection operands, and that these are concrete classes and not protocols.

[DiscordLiz]

I was typing something more than that, but instead, just a slight clarification to what @mikeshardmind just said above

There are some parameters that we can't determine the correct return type for without more information than what the intersection provides

it isn't just this.

(A&B) -> A is inconsistent with (A) -> A.
(A&B) ->B is inconsistent with (B) -> B.
(A&B) -> A&B can be consistent with each, but the intersection does not guarantee that it is from the minimum bound. An example where this would not be consistent:

class ParamA:
    ...

class ParamB:
    ...

class ParamAB(ParamA, ParamB):
    ...

class A:
    def foo(self, x: ParamA) -> ParamA:
        ...

class B:
    def foo(self, x: ParamB) -> ParamB:
        ...

class AB(A, B):
    @overload
    def foo(self, x: ParamA) -> ParamA:
        ...

    @overload
    def foo(self, x: ParamB) -> ParamB:
        ...

    def foo(self, x):
        if isinstance(x, ParamA):
            return ParamA()
        else:
            return ParamB()


def fn(x: A & B):
    x.foo(ParamAB())
    # if x is AB, this results in ParamA which is inconsistent with B.foo
    # even though AB.foo is consistent with A.foo and consistent with B.foo

[diabolo-dan]

@DiscordLiz

I find this unsatisfactory for the same reasons that NoReturn exists. Things that should always error are different from things that have the potential to error, but I think that if we add Not as user expressible, that I'm fine with it. I know that isn't quite consistent with the current type system, but we are also having a lot of discussions about changing some of the current definitions to be more expressive and formalized, and I think there is value in the difference between always an error and may be an error.

I'm not convinced it's worth giving up type consistency to pick up always exceptions, or that it's plausible in many cases.

That said, in this case, it could relatively early be picked up when you implement a subclass of A and B. If the type checker is working correctly, it'll require you to have your information that includes consistency with A&B -> A&B. You can type that as A&B - > Never and all you'd need is a type check or other linter can be set up to pick up -> Never.

[diabolo-dan]

The ordering of overloads actually matters

Sorry, I meant to say the order of overloaded intersections. Within each part of the intersection which has overloads, the order is of course important.

I thought the order of the intersection was what you were taking about from the context, but correct me if I may have misunderstood.

[DiscordLiz]

@diabolo-dan

I'm not convinced it's worth giving up type consistency to pick up always exceptions, or that it's plausible in many cases.

Normally I would agree, but I think this is a case where the two possible handlings are mutually exclusive, so we should have a way to express which one we intend.

@mikeshardmind

Beyond this, I believe there are other reasons it is needed that I would defer to those who came up with them to add in #17

There are, but I'm getting sick of this discussion if you attempt to summarize it, I'll revisit for any needed corrections later.

[mikeshardmind]

@diabolo-dan

The ordering of overloads actually matters

Sorry, I meant to say the order of overloaded intersections. Within each part of the intersection which has overloads, the order is of course important.

I thought the order of the intersection was what you were taking about from the context, but correct me if I may have misunderstood.

If we can't remove the order dependency, then we can't have consistent handling for an intersection between two things that both have overloads. How does the intersection determine which operand's overloads are "first"? Do we require intersections to be ordered?

Restricting what is "knowable", and implicitly handling the disjointedness removes the ordering concern and allows normal algebraic operations to function, something I would consider a non-negotiable feature. This doesn't need to be exposed to users as a type they can use, but I think I agree with @DiscordLiz that users should be able to express with Not to help with other ambiguous cases.

This lack of well-ordering and resolving what is safe with multiple definitions has prior art and requires that we can show that interfaces are either disjoint or specializations of each other.

[randolf-scholz]

@mikeshardmind

If we can't remove the order dependency, then we can't have consistent handling for an intersection between two things that both have overloads. How does the intersection determine which operand's overloads are "first"? Do we require intersections to be ordered?

There are precisely 2 3 questions to be answered:

1. When is C.foo a subtype of (A&B).foo?
   Answer: if and only if C.foo is a subtype of both A.foo and B.foo.
   Type-checkers should already know how to do this, even when A.foo, B.foo and C.foo are overloaded.

2. When is (A&B).foo a subtype of C.foo?
   Answer: if and only if A.foo is a subtype of C.foo or B.foo is a subtype of C.foo.

3. If (A&B).foo is called with arguments args, what is the return type?
   Answer: it's the type of A.foo(args) & B.foo(args). All the type checker needs to do is, in order, go through the list of overloads of A.foo until it finds a match for args and note the return type as RA, then do the same for B.foo to get RB. The end result is RA & RB.

What is not covered is how you would synthesize a compatible subclass of A&B automatically, but that should be outside the scope of the PEP, imo. The only reasonable exception I would consider is providing an auto-merge function for disjoint Protocol-classes. Later PEPs can extend this functionality if needed.

[mikeshardmind]

If (A & B).foo is called with arguments args, what is the return type?
Answer: it's the type of A.foo(args) & B.foo(args). All the type checker needs to do is, in order, go through the list of overloads of A.foo until it finds a match for args and note the return type as RA, then do the same for B.foo to get RB. The end result is RA & RB

This does not work, If you still do not understand why from my earlier comment about "well ordered overloads" necessitating an ordering on intersections, then please wait until more details explaining this are added to #17. A lot of work went into proving the necessity of this, and there is prior art also showing the necessity of this in a static typed environment. This is going to take some time to explain in proper detail with formal proof.

[diabolo-dan]

This lack of well-ordering and resolving what is safe with multiple definitions has prior art and requires that we can show that interfaces are either disjoint or specializations of each other.

Note that the linked rfc is about dispatch for multiple implementations, not about type compatibility. Dispatch needs to be unambiguously ordered because only a single implementation should get called. That doesn't apply for Type compatibility.

Wrt to your other points I'll wait for #17 to be fleshed out as requested.

[mikeshardmind]

@diabolo-dan

Note that the linked rfc is about dispatch for multiple implementations, not about type compatibility. Dispatch needs to be unambiguously ordered because only a single implementation should get called. That doesn't apply for Type compatibility.

Rust's method of dispatch on implementation is about unambiguously selecting an implementation based on type compatibility and specificity of the implementation. There's a subtle relation, and I acknowledge it is not 1:1, but it is a useful framework for correctly determining the most accurate/specific overload or intersected implementation for a given parameter list* We then have the return type (This is "to what end") of that overload or intersected implementation as our most specific known knowledge. (rather than dispatching to that, it still only goes to whatever is on the mro of the type)

[diabolo-dan]

but it is a useful framework for correctly determining the most accurate/specific overload or intersected implementation for a given parameter list

I don't believe that is necessary or useful. More precisely it may be useful as part of a type checking implementation, but it isn't necessary as part of the specification.

[mikeshardmind]

but it is a useful framework for correctly determining the most accurate/specific overload or intersected implementation for a given parameter list

I don't believe that is necessary or useful. More precisely it may be useful as part of a type checking implementation, but it isn't necessary as part of the specification.

If we don't specify this, it can diverge between type checkers, which is not an acceptable outcome with library use.

[mark-todd]

Something I found when implementing my simulator - I've been thinking that Callable & Callable would become an overload of __call__, similarly to:

class A:
    def __call__(self, x: int) -> int:
        ...
        
class B:
    def __call__(self, x: str) -> str:
        ...

(A & B).__call__

But I've now realised the call method isn't quite analogous to:

Callable[[int], int] & Callable[[str], str]

Because in the above the argument isn't named. It's kind of like __call__ but with wildcards for arg names.

My conclusion from this is maybe it's a different beast, that behaves similarly - so it still clashes like overloads would etc, but it's not in itself an overload.

[randolf-scholz]

@mark-todd You probably use Callback-Protocols in your simulator, instead of Callable[[int], int] & Callable[[str], str]

class Call_A(Protocol):
    def __call__(self, x: int) -> int:
        ...
        
class Call_B(Protocol):
    def __call__(self, x: str) -> str:
        ...

(A & B).__call__  # Call_A & Call_B

Simplifying Call_A & Call_B to the single callback protocol representing the __call__ of A&B will in general be very challenging, since compatible signatures need to be determined and overloads need to be taken into account.

Example

@overload
def f(arg: A) -> U: ...
@overload
def f(arg: B) -> V: ...

@overload
def g(arg: S) -> X: ...
@overload
def g(arg: T) -> Y: ...

Then f&g maps types according to the table

arg	return
A & S	U & X
A & (T\S)	U & Y
(B\A) & S	V & X
A \ (S | T)	U
S \ (A | B)	X
B \ (A | S | T)	V
T \ (S | A | B)	Y
(B\A) & (T\S)	V & Y

Which can be translated into the following equivalent set of 8 overloads (without using NOT / set differences)

(A & S) -> (U & X)
(A & T) -> (U & Y)
(B & S) -> (V & Y)
A -> U
S -> X
(B & T) -> (V & Y)
B -> V
T -> Y

You can verify this by drawing a 4-component Venn diagram:

It should be possible to give a tight upper bound for the number of needed overloads, I'll think about this over the holidays.

EDIT: It's actually quite straight forward. If f has $n$-many overloads and g has $m$-many overloads, then f&g requires up to $(n+m+n⋅m)$-many overloads.

[gvanrossum]

Because in the above the argument isn't named. It's kind of like __call__ but with wildcards for arg names.

Since Callable can only express positional argument types (except for Callable[..., X], which is special), the equivalent __call__ method would be something like this:

    def __call__(self, x: int, /)...

[mark-todd]

For now I've implemented something separate in the simulator for the Callable type, but it follows the same logic as __call__ would. The only part I haven't figured out yet is how to resolve something like the below:

class A:
    def __call__(self, x: int, /) -> int:
        pass
        
a = Intersection[A, Callable[[str], str]]

I suppose if the forward slash makes it positional only that's comparable, but if I'm to make one overloaded method, what's the arg name? I suppose it could take the name from the side that does have a name to produce:

Overload[(self, x: int, /) -> int, (self, x: str, /) -> str]

[gvanrossum]

Overload[(self, x: int, /) -> int, (self, x: str, /) -> str]

Where does that notation come from? Are you just making something up? I don't think it was in the callable signature PEP 677, though during its development we considered something like this.

I'm also confused by this, since in the example neither side has a name:

if I'm to make one overloaded method, what's the arg name? I suppose it could take the name from the side that does have a name to produce

[mark-todd]

Where does that notation come from? Are you just making something up? I don't think it was in the callable signature PEP 677, though during its development we considered something like this.

I could be wrong, but I believe this is how pyright shows method types when you inspect them - if the method is overloaded it uses the notation I used here.

I'm also confused by this, since in the example neither side has a name:

When I say name I mean x in the __call__ method - I only noticed the difference when I came to construct a function signature from a callable, and discovered I had to generate a new name. Callable defines the type of the argument but not the name.

[gvanrossum]

I could be wrong, but I believe this is how pyright shows method types when you inspect them - if the method is overloaded it uses the notation I used here.

Okay, that's hardly canonical. :-)

When I say name I mean x in the __call__ method - I only noticed the difference when I came to construct a function signature from a callable, and discovered I had to generate a new name. Callable defines the type of the argument but not the name.

But the name x in (self, x: str, /) -> str is not part of the type, it's just there for documentation -- you might as well use _. Or switch to the PEP 677 notation, which I suppose would be (Self, str) -> str (not sure what to do for self, actually -- why is it in the signature?)

[mark-todd]

But the name x in (self, x: str, /) -> str is not part of the type, it's just there for documentation -- you might as well use _. Or switch to the PEP 677 notation, which I suppose would be (Self, str) -> str (not sure what to do for self, actually -- why is it in the signature?)

Yeah that makes sense - I'm not sure if Self should be there really, as like you say in method form it's not really an input arg. So let's say we switch to: (str) -> str

Is there a canonical type for overloads? I've seen pyright use Overload but as you say that may not be following the PEPs. With the introduction of this function: https://docs.python.org/3/library/typing.html#typing.get_overloads
They even exist at runtime (I suppose the return type of this is list[Callable])

Radical thought perhaps but if there isn't such a notation do we need to introduce one? It could be:
Overload[(str) -> str, (int) -> int]. I would suggest we use intersection here but overloads have a defined order.

Edit: Follow up thought - do methods have a different type from Callable's generally? It's presented differently in pyright but I'm not sure this changes anything about the type as such.

[mark-todd]

On the below I get a type error:

from typing import Callable, overload
class A:
    @overload
    def foo(self, x: int) -> int:
        ...

    @overload
    def foo(self, x: str) -> str:
        ...

    def foo(self, x: int | str) -> int | str:
        return 1

x: Callable[[int | str], int | str] = A.foo

Expression of type "Overload[(self: A, x: int) -> int, (self: A, x: str) -> str]" cannot be assigned to declared type "(int | str) -> (int | str)"
  No overloaded function matches type "(int | str) -> (int | str)"Pyright[reportGeneralTypeIssues]

Edit: Perhaps stranger still, this also fails:

from typing import Callable, overload
@overload
def foo(x: int) -> int:
    ...

@overload
def foo(x: str) -> str:
    ...

def foo(x: int | str) -> int | str:
    return 1


x: Callable[[int | str], int | str] = foo

With error:

Expression of type "Overload[(x: int) -> int, (x: str) -> str, (x: int | str) -> (int | str)]" cannot be assigned to declared type "(int | str) -> (int | str)"
  No overloaded function matches type "(int | str) -> (int | str)"

[mark-todd]

On closer inspection, I think I've worked out what's going on here (at least in pyright). Interestingly enough, I have a feeling that the type of foo is already basically an intersection in it's current implementation:

from typing import Callable, overload
@overload
def foo(x: int) -> int:
    ...

@overload
def foo(x: str) -> str:
    ...

@overload
def foo(x: int | str) -> int | str:
    return 1

def foo(x: int | str) -> int | str:
    return 1


x: Callable[[str], str] = foo

The above returns no errors - and interestingly, if I make the final line:

x: Callable[[int], int] = foo

or

x: Callable[[int | str], int| str] = foo

These also return no errors. Since all of these are acceptable, I propose that the type of foo is effectively already: Callable[[str], str] & Callable[[int], int] & Callable[[int | str], int| str], and that's why assigning the type to be part of the intersection is valid.

[randolf-scholz]

@mark-todd overloads are order-dependent and thus generally not equivalent to intersections. In your example, this is somewhat masked by the fact that one cannot define a nominal subtype of the built-ins int and str in python.

@overload
def foo1(x: X) -> X: ...
@overload
def foo1(x: Y) -> Y: ...

@overload
def foo2(x: Y) -> Y: ...
@overload
def foo2(x: X) -> X: ...

foo3: Callable[[X],X] & Callable[[Y], Y]

All describe different behaviors. foo1(X&Y) gives X, foo2(X&Y) gives Y and foo3(X&Y) gives X&Y.

[mark-todd]

@mark-todd overloads are order-dependent and thus generally not equivalent to intersections. In your example, this is somewhat masked by the fact that one cannot define a nominal subtype of the built-ins int and str in python.

@randolf-scholz Ah yep apologies I remember previous discussions about ordering in Overloads now - in that case I think we're back to the Overload type so:

Overload[Callable[[int], int], Callable[[str], str], Callable[[int | str], int| str]]]

[gvanrossum]

I have to admit I don't know what you're trying to accomplish here (didn't look at the simulator PR) and I don't know your constraints, but that's not an accurate representation of that intersection type, right? In Callable[[int | str], int| str]] we might get str back for an int, which neither the overload nor the intersection does.

[mikeshardmind]

I mentioned this in discord earlier, but when trying to represent an intersection of callables with the simplest equivalent overloads, the ordered list for the simplest case

(T) -> T & (U) -> U

is

overload (T & U) -> T & U
overload (T) -> T
overload (U) -> U
implementation (T | U) -> T | U

The intersection form should be prefered rather than expanding it to this.

[mikeshardmind]

I'm tentatively closing this one. I believe the consistency based rule we are aiming for ends up solving this sufficiently, can be reopened if there are new relevant issues to this topic that would benefit from being continued here.