Support Function With Multiple Generic Parameters Same Type

I would like to be able to type a function that has multiple parameters, with the same generic variable, that only checks if the later parameters are compatible with the first.

Proposal

I propose by adding a bind_first flag to TypeVar:

T = TypeVar('T', bind_first=True)

def eq(x: T, y: T) -> bool: ...

eq(10, 11) # passes
eq(10, "str") # fails

This would be equivalent typing-wise to capturing the first argument in a generic class and then using that in a method, like:

T = TypeVar('T')

class eq(Generic[T]):
     def __init__(self, x: T) -> None: ...

     def to(self, other: T) -> bool: ...

eq(10).to(11)
eq(10).to("str")

Motiviation

There are multiple existing discussions asking for this feature, including one in the Mypy issue tracker from 2019 as well as another from the python/typing discussion board from 2022

Personally, I maintain a Python library that supports optimizing domain-specific languages, called egglog.

In multiple places in the public API (eq, set, rewrite, ne, union, birewrite), I use the workaround of creating a generic class and using a method on it to support having a function with multiple arguments that need to be the same exact class.

I have received multiple times that eq(x).to(y) is less ergonomic and intuitive than eq(x, y), example. For this use case, you might suggest using operator overloading to use something like __eq__ instead. In my case, I want to preserve the ability of users to define their own classes with custom equality and not use this for the meta-level eq.

One option would be to support both forms eq(x).to(y) (type safe) and eq(x, y) (non type safe, but more ergonomic), but it would be unfortunate to have to force users to pick either safety or ergonomics.

Alternatives

In the issues links above, there are a few other suggestions for how to resolve this. One is very similar to this one, but suggests a same_value flag. With that flag however, there are still some open questions about unions and subtypes. It seems like by choosing the first value passed in and binding to that, the same as if we were to make a generic class, we can have a bit clearer semantics by relying on those existing ones for the class version.

There was also a workaround involving having each sub-class you want to distinguish inherit from a different parameterized class. This works, and I would be happy using this if the only sub-classes I needed were defined in my library itself. However, in my case users can define their own sub-classes and those need to be differentiated as well, and having each have this dummy instantiated class they inherit from seems too involved.

Feedback

I would love to hear any thoughts from folks who have thought about this more, to understand if adding this kind of flag would present some unforeseen issues or if there could be a workaround with the existing typing mechanisms.

1 Like

Isn’t that how generic functions are supposed to work already?

Have any of the type checkers implemented the new generics syntax yet?

No that is not how they work. They instead infer type that fits for all usages. If you have function and you pass one int and one str it is valid for type checker to infer that T is Union[int, str]. It is also valid for type checker to infer that T is object.

As of right now exact type T is inferred to be is undefined and different type checkers may choose different answers.

Even with current post idea of infer from first usage only that still leaves some ambiguous cases. If I call function with argument 3 is it int or Literal[3]?

Edit: For this topic the old vs new type syntax makes no difference.

2 Likes

Ah right I see. That’s a very helpful explanation - thankyou.

Thanks for the post. I want to make sure I understand the motivation, so I’ll attempt to reiterate the problem statement. You said that you want to support cases where multiple arguments need to evaluate to “the same exact class”. I presume you mean that these values need to be instances of the same class. Do instances of subclasses work as well? I presume so, since a subclass (by virtue of the Liskov Substitution Principle) should be substitutable for its parent class.

What you’re trying to do is impose an additional constraint on the constraint solver. That’s reasonable, but I see a number of issues with your formulation.

First, the notion of “first” is not well defined. Is it based on left-to-right argument order? Runtime evaluation order of arguments (which can differ in certain cases from left-to-right syntactic order)? Parameter order? What if keyword arguments and parameters are involved, in which case order is irrelevant? What if the parameter type references the type variable multiple times, as in def foo(x: dict[T, T]): ...? Or def foo(x: list[T] | set[T]): ...? What does “first” mean in this case? Unions are intended to be order-independent, so type checkers generally normalize the order of subtypes in a union. It’s therefore not clear what “first” means for list[T] | set[T].

Despite these challenges, we might be able to define “first” in unambiguous terms, but it’s not as straightforward as one might expect.

Second, it’s not clear to me what you mean by “equivalent typing-wise”. Do you really mean equivalent types? If so, do you consider the expressions 10 and 11 to have equivalent types? Pyright evaluates the types of these two expressions as Literal[10] and Literal[11], which are not equivalent. The rules for type evaluation of expressions are not spelled out in the typing spec, and different type checkers will evaluate expression types differently.

(I’ll also note here that constraint solving behaviors are not currently defined in the typing spec, and there are many cases where mypy and pyright differ in how they solve constraints.)

Type equivalency is a very high bar. For example, the type list[Any] is not equivalent to list[int]. Maybe you don’t really mean “equivalent types”. Perhaps you instead mean that the first argument should establish an implied upper bound constraint (which would be consistent with my point about the LSP and subtypes). All other values that bind to the type variable would then need to be assignable to the implied upper bound type. If the first argument is 3.0, would you want to accept 1 for the second argument? Or would you force the developer to specify the second argument as 1.0? If the first argument evaluates to list[Any], would you expect a type error if the second argument evaluated to list[int]? An “upper bound” formulation seems closer to what you probably want, but this would lead to a bunch of unexpected order-dependent behaviors in common circumstances. Consider the following:

eq(3.0, 1) # OK
eq(1, 3.0) # Error

eq(x=3.0, y=1) # OK
eq(y=1, x=3.0) # Error

Going back to the original problem statement, we can see that the proposed solution (even if it didn’t have the issues I’ve demonstrated above) fails to solve the problem as stated. The following code would type check without errors. There’s currently nothing in the type system that says that a type needs to be “a single class”. Unions are supported, as are structural types.

def func1(v: int | str):
    eq(v, "") # OK

func1(1) # OK

def func2(x: Hashable, y: Hashable):
    eq(x, y) # OK

func2(1, "") # OK

def func3(x: object, y: object):
    eq(x, y) # OK

func3(1, "") # OK

I’ll also note that you’re using an old (pre-PEP 695) technique for defining type variables in your sample code. It’s not clear how one would designate a “bind first” type parameter using the modern syntax. We could expand the syntax if this feature were sufficiently compelling, but it’s something that would need to be addressed.

I’m curious whether you know of any other programming languages that have a “bind first” construct like the one you’re proposing. I don’t know of any, and I’d be surprised if we could find such an example. It might be worth doing a survey of other programming languages to see if any of them have addressed this use case. If so, how?

Most programming languages provide a way to specify constraints through explicit specialization. Python already supports this for generic classes and generic type aliases, but it doesn’t support it for generic functions due to a limitation in the grammar. Draft PEP 718 proposes to add this functionality. This would allow you to use a type expression to add an explicit constraint for a generic function:

eq[int](0, 1) # Succeeds
eq[int](1, 2.0) # Fails
eq[int](2.0, 1) # Fails
eq[float](2.0, 1) # Succeeds

However, you may find this to be less ergonomic, so I can see why this might not feel like a great solution for your use case.

The solution you’ve adopted in your library — using a generic class and a method on it — strikes me as a good solution. The syntax may take a little getting used to, but it solves the problem nicely and guarantees type safety.

2 Likes

One variation that I think could be specified and implemented more precisely: Add a type qualifier that can wrap a TypeVar and means “do not use this usage of the TypeVar to add a constraint to the constraint solver”. Let’s call it NoConstraint.

It would behave like this:

def f[T](x: T, y: NoConstrain[T]): ...

def caller(i: int, o: object):
    x(i, 1)  # OK, T is solved to int, 1 is assignable to int
    x(i, o)  # error, T is solved to int, object is not assignable to int
    x(o, i)  # OK, T is solved to object

I think this would do what the OP wants and doesn’t rely on notions like the “first” usage.

I haven’t tried to actually implement it, though, and I don’t know if this is useful enough to add to the type system.

5 Likes

Another potentially more possible-to-implement alternative could be adding a different restriction option to TypeVar [1] namely, “has to be assigned a concrete runtime class”, i.e. something that can be returned by type(obj). This would mean:

  • Literal[...] types aren’t valid, they are never returned by type()
  • int | str is not a valid inference (meaning func1 given by @erictraut above isn’t valid)
  • func2 isn’t valid since it tries to pass Hashable to eq, which is just a protocol (although an exceptionally weird one.)
  • However, object would still be a valid interference. Maybe it would be possible to either tell type checkers to always reject object if this option is used, or to require that one of the two arguments has to have the exact type being inferred? The later one seems impossible to actually enforce.

So I don’t think this option is viable, but maybe it brings others to more helpful ideas.


  1. ignoring the issue new syntax for now ↩︎

Maybe it would help if you explain more concretely why you need the types to “match”. As people have said, it’s not clear what matching means. But it’s also not clear that it’s what you need?

It seems like you want the types to “match” because you want to ensure that x == y is defined. Perhaps, that’s the thing you want to assert somehow?

Thus, you want something like:

def eq[T: Any, U: SupportsEq[T]](x: T, y: U) -> bool:
  ...
  x == y
  ...

where SupportsEq somehow enforces the constraint that x == y is meaningful. But in Python that’s meaningful for nearly all types.

Typescript added exactly this feature fairly recently: NoInfer<T>

So there’s some prior art for that one, at least.

2 Likes

Unless I’m mistaken, this is the TypeScript equivalent of what OP is trying to do:

declare function eq<T, U extends T>(x: T, y: U): boolean;

f(10, 11);     // fine
f(10, 'str');  // error

In words: Use two type variables, the second extending the first.

The corresponding Python code would be:

def eq[T, U: T](x: T, y: U) -> bool:
    ...

…or:

T = TypeVar('T')
U = TypeVar('U', bound = T)

def eq(x: T, y: U) -> bool:
    ...

These are already valid at runtime, so “only” the typing specs would need to change to allow this. Better than adding new constructs/parameters, no?

That’s interesting, I wonder how that interacts with TypeScript’s NoInfer feature noted in the post above yours.

Intuitively, I would think that with your code, if a type checker sees a call to eq(10, "str"), it would be valid to solve both T and U to object. TypeScript doesn’t allow that (playground link: TS Playground - An online editor for exploring TypeScript and JavaScript), so it must have some extra type inference rules here. A proposal to add this feature to the Python type system would have to spell out what those rules are.

1 Like

Thank you all for your responses! I wanted to first refine a bit my particular use case and then go into the different ways to resolve it based on the suggestions here.

Motivation

Let me give an example from the docs on the sort of things I want it to check:

from egglog import *

class Num(Expr):
    def __init__(self, value: i64Like) -> None: ...

    @classmethod
    def var(cls, name: StringLike) -> Num:  ...

    def __add__(self, other: Num) -> Num: ...

    def __mul__(self, other: Num) -> Num: ...

egraph = EGraph()

@egraph.register
def _num_rule(a: Num, b: Num, c: Num, i: i64, j: i64):
    yield rewrite(a + b).to(b + a)
    yield rewrite(a * (b + c)).to((a * b) + (a * c))
    yield rewrite(Num(i) + Num(j)).to(Num(i + j))
    yield rewrite(Num(i) * Num(j)).to(Num(i * j))

Here, I am using the rewrite(...).to(...) syntax so that we can verify that the LHS and RHS are the of the “same type”. For example, a + b can be rewritten to b + a (because they are both of type Num), but Num(i) + Num(j) could not be rewritten to i + j, because the LHS is of type Num and the RHS is of type i64.

Yes, I mean that they are instances of the same class. In my case, sub-classing and unions won’t come up, so I would be fine with any way they are handled.

I agree that this is ambiguous with the current proposal. In my case, I would only need it to work called with positional arguments and as the top level parameter, not nested within a list.

Thank you for clarifying this. I do mean that subsequent arguments would be assignable to the inferred type of the first argument, not that they are equivalent. In my particular case equivalence would be fine, since sub-classing and literals don’t come up, if we think about it as all cases that work with the eq(10).to(11) syntax, then assignability is what I mean.

Basically, if it types checks in the current syntax of the generic class called once with one arg, then with a method with another arg, then it should type check with both args passed in. So any behavior that replicates that would be fine.

That’s fine if those all pass. I am not trying to statically guarantee that it’s called with a statically resolved single class. I just want it to raise an error if I pass in two different single classes.

Yes I can see that it solves the problem. I wouldn’t bring it up, it’s just that I have had multiple users complain and get confused about it. It’s unfortunate that to make the library work with those who do use static typing, I have to adopt a syntax that’s more verbose for everyone.

Yeah in this case I am not trying to catch type errors in the body of eq but in it’s downstream usage. I

Solutions

I didn’t realize that Typescript had implemented very similar with NoInfer!

I think that’s a better solution for the problem and has the advantage of already being implemented there so it feels a bit battle-tested. They already went through all the trouble of refining their behavior so maybe we can re-use some of that (see the implementing PR).

It mentions this solution in the Typescript blog post introducing NoInfer:

One way people currently deal with this is to add a separate type parameter that’s bounded by the existing type parameter.
[…]
This works, but is a little bit awkward because D probably won’t be used anywhere else in the signature for createStreetLight. While not bad in this case, using a type parameter only once in a signature is often a code smell.

That’s why TypeScript 5.4 introduces a new NoInfer<T> utility type. Surrounding a type in NoInfer<...> gives a signal to TypeScript not to dig in and match against the inner types to find candidates for type inference.

I would use this “awkward” solution if it was already supported, but I would hesitate to advocate for implementing that more general syntax for this small use case unless we were already set on allowing bound typesvars to depend on other typevars. I would worry that the complexity of implementing it would be a bit higher.

Do you mind showing an example of downstream usage that should be caught by type checkers? Because a == b is fine for most Python types due to the default implementation accepting object.

In the Matrix example, I have this rewrite for example which uses a number of eq functions:

    rewrite(kron(A, B) @ kron(C, D)).to(
        kron(A @ C, B @ D),
        # Only when the dimensions match
        eq(A.ncols()).to(C.nrows()),
        eq(B.ncols()).to(D.nrows()),
    ),

If instead I had made a mistake and tried to make the rewrite conditional on if the cols of A is equal to B, this should give a type error (one is of type Dim the other of type Matrix):

    rewrite(kron(A, B) @ kron(C, D)).to(
        kron(A @ C, B @ D),
        # Only when the dimensions match
        eq(A.ncols()).to(C.nrows()),
        eq(B.ncols()).to(D), # type error
    ),

As you note, if I had used the builtin __eq__ this is easy to type, but I don’t in this case because I want to preserve __eq__ for user defined code, i.e. as an operation which might return a custom Boolean type instead of being a metaprogramming eq.

Hey there! Checking in a few years later to see what the current state of thinking was on this problem.

I have some more motivating examples about why this would be useful, and I think it can be done without inducing a ton of order-dependent effects:

So for my case, i am working on an array typing lib that is capable of having Literal sizes for the dimensions when they are well-known in advance (e.g. video resolutions, training/testing data, etc.) where it’s important that the dimension sizes match across different array. We want to use TypeVars to match these literals (when possible/provided), but instead the widening behavior makes that impossible with no possible alternative that i can see.

So similar to the matmul example above:

from typing import Literal as L
from typing import TypeVar, reveal_type

import numpy as np

M = TypeVar("M", bound=int)
K = TypeVar("K", bound=int)
N = TypeVar("N", bound=int)

def matmul(
    a: np.ndarray[tuple[M, K]], b: np.ndarray[tuple[K, N]]
) -> np.ndarray[tuple[M, N]]:
    return a @ b

x: np.ndarray[tuple[L[2], L[3]]] = np.ones((2, 3))
y: np.ndarray[tuple[L[3], L[5]]] = np.ones((3, 5))
z: np.ndarray[tuple[L[4], L[5]]] = np.ones((4, 5))

ok = matmul(x, y) # fine - K matches
bad = matmul(x, z) # not fine! - invisible K mismatch becomes L[3, 4]
reveal_type(bad)
# ndarray[tuple[Literal[2], Literal[5]], dtype[Any]]

where K gets widened by pyright and mypy into Literal[3, 4] inappropriately.

Another common one is in machine learning workflows, where some dimensions in the input X data must match the target y data. this is currently just done with docstrings that are ubiquitous in array programming libs like e.g. sklearn, “this dimension must be equal to that one”, and with this limitation can’t be typed using the python typing system (even when literal sizes are available)

Samples = TypeVar("Samples", bound=int)
Features = TypeVar("Features", bound=int)


def fit_predict(
    X: np.ndarray[tuple[Samples, Features]],
    y: np.ndarray[tuple[Samples]],
) -> np.ndarray[tuple[Samples]]:
    # in reality you would actually do something here...
    return y

X: np.ndarray[tuple[L[100], L[4]]] = np.zeros((100, 4))
y_good: np.ndarray[tuple[L[100]]] = np.zeros((100,))
y_bad: np.ndarray[tuple[L[90]]] = np.zeros((90,))

reveal_type(fit_predict(X, y_good)) # fine!
# ndarray[tuple[Literal[100]], dtype[Any]]
reveal_type(fit_predict(X, y_bad)) # not fine! y is a different length!
# ndarray[tuple[Literal[100, 90]], dtype[Any]]

And finally, a non-array example that is nonetheless something that seems like it should be possible to express with the type system. Currently the builtin max can’t be correctly typed: max(1, "hey") typechecks just fine. Consider the natural way to type max with a protocol generic that doesn’t have its typevar set to Any:

from typing import Protocol, Self, reveal_type


class Comparable(Protocol):
    def __lt__(self, other: Self, /) -> bool: ...


def my_max[T: Comparable](a: T, b: T) -> T:
    return b if a < b else a


reveal_type(my_max(1, 2)) # fine
# Type of "my_max(1, 2)" is "int"
reveal_type(my_max(1, 2.5)) # fine
# Type of "my_max(1, 2.5)" is "float"
reveal_type(my_max(2.5, 1)) # fine
# Type of "my_max(2.5, 1)" is "float"
reveal_type(my_max(1, "a")) # not fine!!!
# Type of "my_max(1, "a")" is "int | str"

I think the desired behavior in all these cases is that the typevar should be able to be specified such that it is widened to the widest type among the types that are passed but not go “above” them and be wider than the widest type. So in the max example above and the previous discussion about ordering effects, both orders max(1, 1.5) / max(1.5, 1) are fine because the type can be widened to float, which is one of the types that is provided, but if either is not assignable to the widest type, then things like max(1, "a") would be invalid. Similarly, if a Literal[1] and int are passed for a TypeVar, it could be widened to int and pass, but if Literal[1] and Literal[2] were passed as annotations, it could not be widened to int.

That seems tractable to implement to me as an opt-in behavior like

T = TypeVar("T", bound=int, widen=False)

def something[T: NoWiden[int]](x: T): ...

(where the naming there will need some work…)

I think that addresses concerns in the discussion, but please let me know if i missed something/this is impossible for some other reason. It seems like a relatively large gap in the typing system that there is no way to specify a generic like “Any subtype of the bound, but all the instances of the generic have to be compatible either by being the same type or direct ancestry”

Keep in mind that NumPy only supports bare int tuples as shape-type. Literal integer axis types can lead to wrong types when the array is used in numpy functions. See TYP: Overloads for typing shapes in `transpose`-family functions? · Issue #33150 · numpy/numpy · GitHub for details.

1 Like

yes, that is me that raised the issue! Completely understand that numpy would not offer these types directly, I am talking about downstream, stricter typing that is useful in specific contexts, even if it doesn’t make sense for an infrastructure-level library like numpy to use them directly.

Aside from the numpy examples, I still think the general principle of needing to be able to have typevars that don’t become implicitly widened unions stands alone, e.g. e.g. the “builtins.max can’t be typed correctly” as a motivating example

Oh haha woops, sorry about that.

Completely understand that numpy would not offer these types directly, I am talking about downstream, stricter typing that is useful in specific contexts, even if it doesn’t make sense for an infrastructure-level library like numpy to use them directly.

Well, I think you misunderstood then, because NumPy also doesn’t support using Literal in shape-types in downstream libraries. Because in many cases (e.g. ndarray.T) it will give you incorrect results. You could still use it I guess, but that would then be at your own risk.

Anyway, I didn’t mean to derail this thread, so I’ll try to say something smart without mentioning Numpy now about the actual topic at hand in an attempt to get it back on track again:

Aside from the numpy examples, I still think the general principle of needing to be able to have typevars that don’t become implicitly widened unions stands alone, e.g. e.g. the “builtins.max can’t be typed correctly” as a motivating example

Yes I fully agree. I have wished for this to be possible myself many times, most of them while working on, erm, a certain numerical Python library (oof, close call).
Usually I was able to (kinda) work around it by either throwing some overloads at the problem, or by using a “TypeVar with constraints” (for the lack of a better term), e.g.

# IntegerT = TypeVar("IntegerT", bound=integer)  # won't work
EitherInt = TypeVar("EitherInt", uint32, uint64, int32, int64)  # subtypes of `integer`

# `mod(int32, uint64) -> float64`, so joining these as `int32 | uint64` would be wrong
def mod(a: EItherInt, b: EItherInt, /) -> EItherInt: ...

But clearly, that’s not ideal:

  • it’s usually not a general solution as it requires you to manually specify a finite set of types
  • subtypes of the constraints are upcast [1],
  • results in messy code [2],
  • the typing spec only partially defines how it should behave [3], and
  • several type-checkers (at least mypy and pyright) today have a bug where they eagerly select the first constraint when Any is passed [4].

Another workaround would be to use 4 overloads: one for each type. However, that will have many of the same problems, and when in reality you’re dealing with 8 integer dtypes + 4 floating dtypes + 3 complex dtypes + …, you’ll likely end up rage-quitting when heroically attempting to write out each overload and realize that there are two boolean parameters that affects the result type that you’ll have to overload too, which requires x4 the number of overloads…


Note how this would not be a problem if all variable inputs were in invariant positions, e.g.

IntegerT = TypeVar("IntegerT", bound=integer)

def mod_list(a: list[IntegerT], b: list[IntegerT]) -> list[IntegerT]: ...

Here, if you pass a: list[int32] and b: list[uint64], checkers will complain (as they should), because list[int32] and list[uint64] are not assignable to list[int32 | uint64], so there exists no joined type here that’s subject to bound=integer.

So what if there was an invariant type like list, say Just, so that for any T you can assign T to Just[T] and vice-versa? Then we could write the first mod as

def mod[T: integer](a: Just[T], b: Just[T], /) -> T: ...

and mod(int32(5), uint64(2)) will be rejected, as desired :).


  1. In my experience that’s usually not what you want, but in rare cases it can be handy. ↩︎

  2. especially when using PEP 695 syntax, have >2 constraints, and have to use this in several functions or overloads ↩︎

  3. What should happen when input is assignable to multiple constraints, e.g. when you pass Never? What if the input is a union of multiple constraints like int32 | int64? What about Any as a constraint (Constrained type vars with `Any` default)? ↩︎

  4. I call it a “bug” because not all materializations are considered, and this usually leads to unexpected and undesired outcomes, e.g. assigning Any to EitherInt will give you int8 (mumbles something about the gradual guarantee), But I guess you could also blame the typing spec here for not being clear on how to deal with this, technically speaking. ↩︎

Doesn’t that behaviour depend on the type checker inferring T to be sufficiently small? Like, with the list definition if you e.g. pass in literals and they get inferred as list[integer] it typechecks fine.

I think with Just[T] I would expect the mod call to type check since we can infer T as int32 | uint64, both arguments are assignable to int32 | uint64 and thus to Just[int32 | uint64]. So I think we need a special form that tells type checkers not to widen type variable by combining constraints from different occurrences.

Hmm yea that’s a good point; that would indeed be wrong in this case, because you could pass a: integer and b: integer. So just Just just isn’t enough in this particular case (although it would probably be a fine solution for other cases).