PEP 646: Decide on substitution behavior

[JelleZijlstra]

BPO	47006
Nosy	@gvanrossum, @serhiy-storchaka, @JelleZijlstra, @Fidget-Spinner, @mrahtz, @mrahtz, @AlexWaygood
PRs	python/cpython#32341

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields: ```python assignee = 'https://github.com/JelleZijlstra' closed_at = None created_at = labels = ['type-bug', 'release-blocker', '3.11'] title = 'PEP 646: Decide on substitution behavior' updated_at = user = 'https://github.com/JelleZijlstra' ``` bugs.python.org fields: ```python activity = actor = 'gvanrossum' assignee = 'JelleZijlstra' closed = False closed_date = None closer = None components = [] creation = creator = 'JelleZijlstra' dependencies = [] files = [] hgrepos = [] issue_num = 47006 keywords = ['patch'] message_count = 17.0 messages = ['415100', '415107', '415108', '415109', '415557', '415623', '415637', '415694', '415710', '415712', '415734', '415752', '415753', '416707', '416795', '416813', '416913'] nosy_count = 7.0 nosy_names = ['gvanrossum', 'serhiy.storchaka', 'JelleZijlstra', 'kj', 'matthew.rahtz', 'mrahtz', 'AlexWaygood'] pr_nums = ['32341'] priority = 'release blocker' resolution = None stage = 'patch review' status = 'open' superseder = None type = 'behavior' url = 'https://bugs.python.org/issue47006' versions = ['Python 3.11'] ```

[JelleZijlstra]

We've had some disagreement about the behavior of TypeVarTuple substitution related to PEP-646, and the discussion has now spilled around multiple PRs. I'd like to use this issue to come to an agreement so we don't have to chase through so many different places.

Links:

• python/cpython#75204 (merged) implements PEP-646 in typing.py. Matthew initially implemented full TypeVar substitution support, but took it out after I suggested an alternative solution in https://github.com/python/cpython/pull/31021#pullrequestreview-890627941.
• python/cpython#75981 (merged without review) implements TypeVarTuple substitution in Python.
• python/cpython#76009 implements TypeVarTuple substitution in C.
• python/cpython#76025 and python/cpython#76027 add additional test cases.
• python/cpython#75985 (closed) implements my proposed solution.

I'd like to ask that until we come to an agreement we hold off on making any more changes, so we don't have to go back and forth and we ensure that the eventual solution covers all edge cases.

The disagreement is about what to do with TypeVarTuple substitution: the behavior when a generic type is subscripted, like tuple[*Ts][int, str].

There are two possible extreme approaches:

• Implement full substitution support, just as we have it for existing TypeVars. This is complicated because TypeVarTuple makes it much harder to match up the types correctly. However, it is consistent with the behavior for other TypeVar-like objects. My example would turn into GenericAlias(tuple, (int, str)).
• Give up on substitution and just return a new GenericAlias object: GenericAlias(GenericAlias(tuple, Unpack[Ts]), (int, str). This avoids implementing any complex runtime behavior, but it inconsistent with existing behavior and less pretty when you print out the type. I prefer this approach because there's less risk that future enhancements to typing will break it. I also want to explore extending this approach to ParamSpec substitution.

[fd1152b9-82e1-43e9-8503-4a522c774a26]

Thanks for starting this, Jelle - I was a bit unsure about how to proceed here.

Given that https://github.com/python/cpython/pull/31800 is already merged, I'd also propose something halfway between the two extremes: return a sensible substitution when the logic to compute that isn't too onerous, and a new GenericAlias object when it is. The upsides are that we'd probably be able to return reasonable substitutions for the vast majority of cases, and that we wouldn't have to remove what's already been merged. The downsides would be lack of consistency, and the potential for changing rules about what does and doesn't return a full substitution as time goes on and new features are added.

[fd1152b9-82e1-43e9-8503-4a522c774a26]

(Having said that, to be clear: my preferred solution currently would still be the solution where we just return a new GenericAlias for anything involving a TypeVarTuple. The crux is what Serhiy is happy with.)

[JelleZijlstra]

Thanks Matthew! Merged PRs can still be reverted, and we have some time before the feature freeze. I'd like to hear what Guido and Ken think too.

If we go with the GenericAlias substitution, we need to make sure that such aliases still work as base class. That would need some C work to make types.GenericAlias.__mro_entries__ recurse if the alias's origin is itself a GenericAlias. There's a few other subtleties to think about; I can work on that but don't have a ton of time today.

[serhiy-storchaka]

I am for consistent behavior. If return GenericAlias(GenericAlias(tuple, Unpack[Ts]), (int, str)) for tuple[*Ts][int, str], we should also return GenericAlias(GenericAlias(list, T), int) for list[T][int], etc. And it will cause multiple problems:

• A repr can be less readable.
• It will break equality comparison and hashing. Good bye caching.
• What about __origin, __parameters, __args__? How will they be calculated?
• It can break code which uses annotations for something. For example it can break dataclasses.

It may be that will need to use it as a fallback for cases like tuple[T, *Ts][*Ts2] (currently it is error). But I am not sure that such cases should be supported.

[gvanrossum]

I think I'm with Serhiy, I don't understand the hesitance to transform tuple[*Ts][int, str] into tuple[int, str].

What would be an example of a substitution that's too complex to do?

[JelleZijlstra]

It's simple if you only look at simple examples.

Here are some examples current main (with Serhiy's patch for the Python version of typing) gets wrong:

>>> from typing import *
>>> Ts = TypeVarTuple("Ts")
>>> T1 = TypeVar("T1")
>>> T2 = TypeVar("T2")
>>> Tuple[T1, Unpack[Ts], T2][int, Unpack[tuple[int]]]  # expect error
typing.Tuple[int, *tuple[int]]
>>> Tuple[T1, Unpack[Ts], str, T2][int, Unpack[Ts]]  # expect error (T2 missing)
typing.Tuple[int, str, *Ts]  # it put *Ts in the wrong place
>>> Tuple[T1, Unpack[Ts], str, T2][int, Unpack[Ts], Unpack[Ts]]  # expect error (*Ts can't substitute T2)
typing.Tuple[int, *Ts, str, *Ts]
>>> class G(Generic[T1, Unpack[Ts], T2]): pass
... 
>>> G[int]  # expect error
__main__.G[int]

We can probably fix that, but I'm not looking forward to implementing the fixed logic in both Python and C. Also, I'm worried that it won't work with future extensions to the type system (e.g., the rumored Map operator) that may go into 3.12 or later versions.

[serhiy-storchaka]

The first case will be practically fixed by GH 32030 after chenging the grammar to allow unpacking in index tuple: A[*B].

Two other cases will be fixed by GH 32031. It does not require any C code.

In the last case no error is raised because some error checks are skipped if any of Generic arguments is a TypeVarTuple. We just need to add such checks. This is Python-only code too.

Note that the alternative proposition is even more lenient to errors.

[fd1152b9-82e1-43e9-8503-4a522c774a26]

[Guido]

What would be an example of a substitution that's too complex to do?

We also need to remember the dreaded arbitrary-length tuple. For example, I think it should be the case that:

T = TypeVar('T')
Ts = TypeVarTuple('Ts')
class C(Generic[*Ts]): pass
Alias = C[T, *Ts]
Alias2 = Alias[*tuple[int, ...]]
# Alias2 should be C[int, *tuple[int, ...]]

Ok, this is a bit of a silly example, but if we're committing to evaluating substitutions correctly, we should probably make even this kind of example behave correctly so that users who accidentally do something silly can debug what's gone wrong.

[Serhiy]

A repr can be less readable.

Definitely true.

It will break equality comparison and hashing. Good bye caching.

Huh, I didn't know about this one. Fair enough, this is totally a downside.

What about __origin, __parameters, __args__? How will they be calculated?

This could admittedly be thorny. We'd have to think it through carefully. Admittedly also a downside.

It can break code which uses annotations for something. For example it can break dataclasses.

Oh, also interesting - I didn't know about this one either. Could you give an example?

The first case will be practically fixed by GH 32030 after chenging the grammar to allow unpacking in index tuple: A[*B].

We actually deliberately chose not to unpack concrete tuple types - see the description of https://github.com/python/cpython/pull/30398, under the heading 'Starred tuple types'. (If you see another way around it, though, let me know.)

Two other cases will be fixed by GH 32031. It does not require any C code.

I'm also not sure about this one; disallowing unpacked TypeVarTuples in argument lists to generic aliases completely (if I've understood right?) seems like too restrictive a solution. I can imagine there might be completely legitimate cases where the ability to do this would be important. For example:

DType = TypeVar('DType')
Shape = TypeVarTuple('Shape')
class Tensor(Generic[DType, *Shape]): ...
Uint8Tensor = Tensor[uint8, *Shape]
Unit8BatchTensor = Uint8Tensor[Batch, *Shape]

Note that the alternative proposition is even more lenient to errors.

True, but at least it's predictably lenient to errors - I think the repr makes it very clear that "Woah, you're doing something advanced here. You're on your own!" I think it better fits the principle of least astonishment to have something that consistently lets through all errors of a certain class than something that sometimes catches errors and sometimes doesn't.

[fd1152b9-82e1-43e9-8503-4a522c774a26]

P.s. To be clear, (I think?) these are all substitutions that are computable. We *could* implement the logic to make all these evaluate correctly if we wanted to. It's just a matter of how much complexity we want to allow in typing.py (or in the runtime in general, if we say farmed some of this logic out to a separate module).

[gvanrossum]

I'd like to look at this as a case of simplifying something to its simplest canonical form, but no simpler. This is what the existing fixed-typevar expansion does: e.g. tuple[str, T, T][int] becomes tuple[str, int, int].

I propose that we try to agree on a set of rules for what can be simplified further and what cannot, when we have B = C[...]; A = B[...], (IOW A = C[...][...]), for various shapes of the subscripts to C and B. Note that what's relevant for the second subscript is C[...].__parameters__, so I'll call that "left" below.

1. Some edge case seems to be that if *tuple[...] is involved on either side we will never simplify. Or perhaps a better rule is that *tuple[...] is never simplified away (but fixed items before and after it may be).

2. Another edge case is that if neither side has any starred items we will always simplify (since this is the existing behavior in 3.10). This may raise an error if the number of subscripts on the right does not match the number of parameters on the left.

3. If there's a single *Ts on the left but not on the right, we should be able to simplify, which again may raise an error if there are not enough values on the right, but if there are more than enough, the excess will be consumed by *Ts (in fact that's the only way *Ts is fed).

4. If there's a *Ts on the right but not on the left, we should _not_ simplify, since whatever we have on the left serves as a constraint for *Ts. (E.g. tuple[int, int][Ts] constrains \Ts to being (int, int).)

5. If there's exactly one *Ts on the left and one on the right, we _might be able to simplify if the prefix and suffix of the __parameters match the prefix and suffix of the subscript on the right. E.g. C[int, T, *Ts, float][str, *Ts] can be simplified to C[int, str, *Ts, float]. OTOH C[int, T, *Ts, float][Ts] cannot be simplified -- but we cannot flag it as an error either. Note that __parameters in this example is (T, Ts); we have to assume that typevartuples in __parameters are always used as \Ts (since the PEP recognizes no valid unstarred uses of Ts).

TBH case 5 is the most complex and I may have overlooked something. I'm more sure of cases 1-4.

[serhiy-storchaka]

Alias = C[T, *Ts] Alias2 = Alias[*tuple[int, ...]]

Alias2 should be C[int, *tuple[int, ...]]

tuple[int, ...] includes also an empty tuple, and in this case there is no value for T.

Oh, also interesting - I didn't know about this one either. Could you give an example?

If __origin, __parameters, __args__ are a mess, it will definitely break a code which use them.

We actually deliberately chose not to unpack concrete tuple types - see the description of https://github.com/python/cpython/pull/30398, under the heading 'Starred tuple types'. (If you see another way around it, though, let me know.)

You assumed that *tuple[str, bool] in def foo(args: \tuple[str, bool]) should give foo.__annotations__['args'] = tuple[str, bool], but it should rather give (str, bool). No confusion with tuple[str, bool].

And one of PEP-646 options is to implement star-syntax only in subscription, not in var-parameter type annotations.

I'm also not sure about this one; disallowing unpacked TypeVarTuples in argument lists to generic aliases completely (if I've understood right?)

No, it will only be disallowed in substitution of a VarType. Tuple[T][Ts] -- error. Tuple[Ts][*Ts2] -- ok.

I propose to implement simple and strict rules, and later add support of new cases where it makes sense.

[serhiy-storchaka]

1. Some edge case seems to be that if *tuple[...] is involved on either side we will never simplify. Or perhaps a better rule is that *tuple[...] is never simplified away (but fixed items before and after it may be).

I do not understand this. Do you forbid simplifying of tuple[Ts, float][str, *tuple[int, ...]] to tuple[str, \tuple[int, ...], float]?

I think that the rule should be that *tuple[X, ...] cannot split between different variables. Or that it cannot substitute a TypeVar. A more strong variant of rule 4.

5. ... but we cannot flag it as an error either.

I think that it will better to flag it as an error now. Later, after all code be merged and all edge cases be handled we can return here and reconsider this.

There are workarounds for this.

• You should not use Generic[Ts] if you require at least one item, but Generic[Ts, T].
• Instead of def foo(*args: *Ts) use def foo(*args: *tuple[*Ts, T]).

These tricks are common in functional programming.

The rest of the rules match my implementations more or less.

[fd1152b9-82e1-43e9-8503-4a522c774a26]

Apologies for the slow reply - coming back to this now that the docs and pickling issues are mostly sorted.

[Serhiy]

> Alias = C[T, *Ts] > Alias2 = Alias[tuple[int, ...]] > # Alias2 should be C[int, \tuple[int, ...]]

tuple[int, ...] includes also an empty tuple, and in this case there is no value for T.

This was my initial intuition too, but Pradeep pointed out to me in https://github.com/python/cpython/pull/31021#discussion_r815853784 that for tuple[int, ...], Python has chosen the opposite mindset: instead of assuming the worst-case scenario, we assume the best-case scenario. Thus, the following type-checks correctly with mypy (https://mypy-play.net/?mypy=latest&python=3.10&gist=b9ca66fb7d172f939951a741388836a6):

def return_first(tup: tuple[int, ...]) -> int:
    return tup[0]
tup: tuple[()] = ()
return_first(tup)

> We actually deliberately chose not to unpack concrete tuple types - see the description of https://github.com/python/cpython/pull/30398, under the heading 'Starred tuple types'. (If you see another way around it, though, let me know.)

You assumed that *tuple[str, bool] in def foo(args: \tuple[str, bool]) should give foo.__annotations__['args'] = tuple[str, bool], but it should rather give (str, bool). No confusion with tuple[str, bool].

Fair point, we could technically distinguish between tuple[str, bool] and (str, bool). But if I was a naive user and I saw foo.__annotations__['args'] == (str, bool), I don't think it'd be immediately obvious to me that the type of args was *tuple[str, bool].

Also though, there's a second reason mentioned in https://github.com/python/cpython/pull/30398 why (str, bool) wouldn't be the best choice. We decided that the runtime behaviour of *args: *something should be that we essentially do (*something,)[0]. If we made tuple[int, str] unpack to (int, str), then we'd end up with __annotations__['args'] == (int,).

And one of PEP-646 options is to implement star-syntax only in subscription, not in var-parameter type annotations.

As in, we would allow Generic[*Ts], but not *args: *Ts? That'd be a major change to the PEP - not an option I'm willing to consider at this stage in the process.

> I'm also not sure about this one; disallowing unpacked TypeVarTuples in argument lists to generic aliases completely (if I've understood right?)

No, it will only be disallowed in substitution of a VarType. Tuple[T][Ts] -- error. Tuple[Ts][*Ts2] -- ok.

Ah, gotcha. My mistake.

[Guido]

I ran out of time this evening :) Will reply properly soon.

[fd1152b9-82e1-43e9-8503-4a522c774a26]

[Guido]

1. Some edge case seems to be that if *tuple[...] is involved on either side we will never simplify.

Alright, let me think this through with some examples to get my head round it.

It would prohibit the following difficult case:

class C(Generic[*Ts]): ...
Alias = C[T, *Ts]
Alias[*tuple[int, ...]]  # Does not simplify; stays C[T, *Ts][*tuple[int, ...]]

That seems pretty reasonable. It would also prohibit these other relatively simple cases, but I guess that's fine:

Alias = C[*Ts]
Alias[*tuple[int, ...]]  # Does not simplify; stays C[*Ts][*tuple[int, ...]]

Alias = C[T, *tuple[int, ...]]
Alias[str]  # Does not simplify; stays C[T, *tuple[int, ...]][str]

Or perhaps a better rule is that *tuple[...] is never simplified away (but fixed items before and after it may be).

Is this to say that we effectively prohibit binding *tuple[...] to anything? If we can simplify without binding *tuple[...] to anything, then we do simplify, but otherwise, we don't simplify? So under this rule, the following WOULD work?

Alias = C[T, *tuple[int, ...]]
Alias[str]  # Simplifies to C[str, *tuple[int, ...]], because we didn't have to bind *tuple[int, ...] to do it

2. Another edge case is that if neither side has any starred items we will always simplify (since this is the existing behavior in 3.10). This may raise an error if the number of subscripts on the right does not match the number of parameters on the left.

Alright, so this is business as usual.

3. If there's a single *Ts on the left but not on the right, we should be able to simplify, which again may raise an error if there are not enough values on the right, but if there are more than enough, the excess will be consumed by *Ts (in fact that's the only way *Ts is fed).

So then:

class C(Generic[*Ts]): ...
Alias = C[T, *Ts]
Alias[()]              # Raises error
Alias[int]             # Simplifies to C[int, *Ts]
Alias[int, str]        # Simplifies to C[int, str]
Alias[int, str, bool]  # Simplifies to C[int, str, bool]

Yup, seems straightforward.

4. If there's a *Ts on the right but not on the left, we should _not_ simplify, since whatever we have on the left serves as a constraint for *Ts.

Ok, so this is about the following situations:

class C(Generic[*Ts]): ...
Alias = C[T1, T2]
Alias[*Ts]  # Does not simplify; stays C[T1, T2][*Ts]

Yikes - in fact, this is actually super hairy; I hadn't thought about this edge case at all in the PEP.

Agreed that it seems reasonable not to simplify here.

E.g. tuple[int, int][Ts] constrains \Ts to being (int, int).

Was that a typo? Surely tuple[int, int][*Ts] isn't valid - since tuple[int, int] doesn't have any free parameters?

5. If there's exactly one *Ts on the left and one on the right, we _might be able to simplify if the prefix and suffix of the __parameters match the prefix and suffix of the subscript on the right. E.g. C[int, T, *Ts, float][str, *Ts] can be simplified to C[int, str, *Ts, float]. OTOH C[int, T, *Ts, float][Ts] cannot be simplified -- but we cannot flag it as an error either. Note that __parameters in this example is (T, Ts); we have to assume that typevartuples in __parameters are always used as \Ts (since the PEP recognizes no valid unstarred uses of Ts).

Ok, this also makes sense.

---

Still, though, doesn't the point that Serhiy brought up about __origin, __parameters and __args__ still apply? In cases where we *don't* simplify, there'd still be the issue of what we'd set these things to be.

This evening I'll also revisit the PRs adding tests for substitution to try and make them a comprehensive reference as to what's currently possible.

[fd1152b9-82e1-43e9-8503-4a522c774a26]

Ok, https://github.com/python/cpython/pull/32341/files is a reference of how the current implementation behaves. Fwiw, it *is* mostly correct - with a few minor tweaks it might be alright for at least the 3.11 release.

In particular, instead of dealing with the thorny issue of what to do about splitting unpacked arbitrary-length tuples over multiple type variables - e.g. C[T, *Ts][*tuple[int, ...]] - instead either deciding to try and evaluate it properly and living with the complexity, or leaving it unsimplified and living with the __args, __parameters and __origin__ problem - for now, we could just raise an exception for any substitutions which involve an unpacked arbitrary-length tuple, since I'd guess it's going to be an extremely rare use-case.

[gvanrossum]

We need to move on this, because the outcome of this discussion is a release blocker for 3.11b1 -- the next release!

[mrahtz]

Copying in correspondence by email while issues were being migrated:

@mrahtz:

(Temporarily moving this discussion to email, since my understanding is that the issue tracker will be down for ~24 hours while it's being migrated to GitHub, and it sounds like this might be getting urgent-ish.)

[Guido]

We need to move on this, because the outcome of this discussion is a release blocker for 3.11b1 -- the next release!

Oh yikes, I didn't realise. To be clear, what's the timeframe? I see the release schedule for 3.11 says that 3.11b1 is scheduled for 2022-05-06. Is the point that we need to have this discussion resolved and all the implementation finished by? Or is the very fact that this discussion is still underway blocking other folks right now?

(And for my general education: is the point of the remaining beta releases that they're supposed to be bugfix-only?)

@JelleZijlstra:

Oh yikes, I didn't realise. To be clear, what's the timeframe? I see the release schedule for 3.11 says that 3.11b1 is scheduled for 2022-05-06. Is the point that we need to have this discussion resolved and all the implementation finished by? Or is the very fact that this discussion is still underway blocking other folks right now?

Yes, we should not be changing any features after the feature freeze in early May.

(And for my general education: is the point of the remaining beta releases that they're supposed to be bugfix-only?)

That's right. This should enable people to test without having to worry about new features.

@mrahtz:

Alright, by the power invested in me as lead author of the PEP, I say let's go with implementing full substitution support (or as close to full as we can reasonably get it).

The reasoning is that a) I think we're closer to a working, consistent implementation with full substitution support compared to the "partially-evaluated substitution" approach; and b) Serhiy's point about what to do about args etc has got me worried; a "partially-evaluated substitution" would be a new kind of thing in the typing system, and I think it could easily have further implications we won't have time to discover/work through before 3.11b1. It's true that the logic will be a bit complicated, and that as Jelle says it could complicate implementation of future typing features, but I think the latter is partly an inevitable consequence of the fact that variadic generics simply are complicated, and overall I still think the tradeoff is worth it.

So unless anyone has a reason to veto this, let's proceed as follows:

1. Merge Serhiy's C code for substitution in https://github.com/python/cpython/pull/31828
2. Discuss https://github.com/python/cpython/pull/32341 until we're happy with what we think the behaviour should be (there are still a few in there I'm not entirely sure about myself), and use that as a basis for fixing the remaining issues
3. Reserve the right to raise NotImplementedError for the trickiest cases (e.g. splitting of *tuple[int, ...] across multiple type variables). Ideally it'd be nice to raise a message saying something like "If you think you need this, please leave a comment with your use case at " - is there any precedent for something like this being possible?

@serhiy-storchaka:

2. Discuss https://github.com/python/cpython/pull/32341 until we're happy with what we think the behaviour should be (there are still a few in there I'm not entirely sure about myself), and use that as a basis for fixing the remaining issues

There were many changes in the code related to ParamSpec and Concatenate during the beta stage of 3.10 and even after the release. The current implementation of ParamSpec substitution is based on "analogies" and "reading between lines" rather of a concrete specification.

3. Reserve the right to raise NotImplementedError for the trickiest cases (e.g. splitting of *tuple[int, ...] across multiple type variables). Ideally it'd be nice to raise a message saying something like "If you think you need this, please leave a comment with your use case at " - is there any precedent for something like this being possible?

Callable[Concatenate[int, P], str][...] raises a type error because the result cannot be expressed in a form which would not contradict existing PEPs.

[gvanrossum]

I feel I need to add this same remark here:

@mrahtz @JelleZijlstra @serhiy-storchaka Is it okay if I unsubscribe from these conversations and let you all come up with a compromise? I feel that while we ought to have a policy formulated and mostly implemented by beta 1 (May 6), tweaks of both the policy and the implementation during the beta period until RC 1 (Aug/Sept?) should be allowable.

[mrahtz]

Ok, thinking about things more in https://github.com/python/cpython/pull/32341, I would propose the following spec:

• In general, we aim to accurately evaluate type variable substitution, supporting as many valid aliases as we can.
• Exception: if an unpacked arbitrary-length tuple (e.g. *tuple[int, ...]) is used in a generic alias type args list, then:
  • It must be the only type argument
  • Alias[str, *tuple[int, ...]] would not be valid
  • Alias[*tuple[int, ...], *tuple[str, ...]] would not be valid
  • Only Alias[*tuple[int, ...]] would be valid
  • The alias's sole type parameter must be an unpacked TypeVarTuple
  • Alias = tuple[T, *Ts]; Alias[*tuple[int, ...]] would not be valid
  • Alias = tuple[T1, T2]; Alias[*tuple[int, ...]] would not be valid
  • Only Alias = tuple[*Ts]; Alias[*tuple[int, ...]] would be valid

[serhiy-storchaka]

Why Alias = tuple[T, *Ts]; Alias[str, *tuple[int, ...]] would not be valid?

[mrahtz]

Why Alias = tuple[T, Ts]; Alias[str, tuple[int, ...]] would not be valid?

Only because it might slightly complicate the rules about what's allowed and what isn't. If you're (@serhiy-storchaka and @JelleZijlstra) both fine with it, though - and also based on discussion so far with @pradeep90's in https://github.com/python/cpython/pull/32341 - a more lenient version of the spec could be:

• In general, we aim to accurately evaluate type variable substitution, supporting as many valid aliases as we can.
  • Edit: we also support some aliases which are technically invalid according to PEP 646. In particular, we support multiple unpackings per argument list - e.g. tuple[*Ts][*tuple[int, ...], *tuple[str, ...]].
• Exception: if an unpacked arbitrary-length tuple (e.g. *tuple[int, ...]) is used in a generic alias type args list, then it must 'match' exactly with a *Ts in the parameter list, such that the *tuple[int, ...] is completely consumed by the *Ts, and *Ts contains only the *tuple[int, ...]
  • Valid:
  • tuple[*Ts][*tuple[int, ...]]
  • tuple[T, *Ts][str, *tuple[int, ...]]
  • tuple[*Ts, T][*tuple[int, ...], str]
  • tuple[T1, *Ts, T2][int, *tuple[int, ...], str
  • Not valid (at runtime - even though they're otherwise valid constructions):
  • tuple[T, *Ts][*tuple[int, ...]] - because the *tuple[int, ...] would be split between T and *Ts)
  • tuple[*Ts][str, *tuple[int, ...]] - because the *Ts would consume both str and *tuple[int, ...]

Tentatively, as @pradeep90 mentions in https://github.com/python/cpython/pull/32341, we might also want to add:

• Unpacked arguments (e.g. Alias[*Ts], Alias[*tuple[int]], Alias[*tuple[int, ...]] can only be consumed by an unpacked TypeVarTuple in the parameters list of Alias
  • Valid:
  • tuple[*Ts][*Ts]
  • tuple[*Ts][*tuple[int]]
  • tuple[*Ts][*tuple[int, ...]]
  • tuple[T, *Ts][int, *tuple[str]]
  • Not valid:
  • tuple[T][*tuple[int]]
  • list[*tuple[int]]

I've updated the comments on the expected results in https://github.com/python/cpython/pull/32341 based on this tentative spec (minus the last point, for now).

[pradeep90]

Exception: if an unpacked arbitrary-length tuple (e.g. tuple[int, ...]) is used in a generic alias type args list, then it must 'match' exactly with a Ts in the parameter list, such that the tuple[int, ...] is completely consumed by the Ts, and Ts contains only the tuple[int, ...] Not valid (at runtime - even though they're otherwise valid constructions): tuple[T, Ts][tuple[int, ...]] - because the tuple[int, ...] would be split between T and Ts) tuple[Ts][str, tuple[int, ...]] - because the Ts would consume both str and tuple[int, ...]

Examples of why people will run into these cases:

1. The former is important for migrating code to shape types. Suppose someone has an alias Foo = Array[T, *Ts] and the migrating code doesn't want to specify the exact variadic dimensions. They could write Foo[*tuple[int, ...]] (as we mention in the PEP). We'd be forbidding that case.

2. The latter is important for partially unpacking shape types. For example, someone could have an alias IntTensor = Tensor[int, *Ts] and write:

class Tensor(Generic[DType, *Ts]): ...

IntTensor = Tensor[int, *Ts]

# elsewhere
def first_dimension(
    input: IntTensor[N1, *tuple[int, ...]],
) -> N1: ...

Here, we are essentially applying Tensor[int, *Ts][N1, *tuple[int, ...]]. IIUC, your above specification would forbid this.

---

Could you elaborate on why these are invalid? (As you mention, these are valid constructions as per the PEP.) I'm guessing it's because the implementation becomes complex. Just to clarify:

1. How hard would it be to extract the unbounded element in *tuple[int, ...] and substitute it for any TypeVars? e.g., Array[T, *Ts][*tuple[int, ...]] should have T=int.
2. Not clear what was the issue with Tensor[int, *Ts][N1, *tuple[int, ...]]. How hard would it be to wrap N1, *tuple[int, ...] and get Ts = *tuple[N1, *tuple[int, ...]]?

Totally understandable if these are genuinely hard to encode.

If we're avoiding these as a temporary measure to land this before the 3.11 beta release, that sounds reasonable. But if we're settling on this as a permanent restriction, that seems less than ideal.

[mrahtz]

Examples of why people will run into these cases: ...

Ah, ok, yeah, good points. This is a big update for me on the importance of supporting more than the current tentative spec.

Could you elaborate on why these are invalid? I'm guessing it's because the implementation becomes complex.

Yeah. At least, my guess is that it would be complex. I don't think it would be hard to encode.

I'll try writing an implementation of the logic that would support this in the next few days. So we can see how bad it would be.

If we're avoiding these as a temporary measure to land this before the 3.11 beta release, that sounds reasonable. But if we're settling on this as a permanent restriction, that seems less than ideal.

Yeah, this is more in the spirit of the former.

[mrahtz]

Ok, it looks like supporting correct substitution of unpacked arbitrary-length tuples wouldn't be too hard after all!

This thread is getting kinda long, so to recap: we're talking about the fact that this

Alias = tuple[T, *Ts]
Alias[*tuple[int, ...]]

should evaluate to tuple[int, *tuple[int, ...].

I've written a draft implementation (at least, of the typing.py version - though I guess the C version will be similar) in https://github.com/python/cpython/pull/91766. The difficult part is self-contained within this method: https://github.com/python/cpython/blob/2751e769994470cd76da87fd2b82dfaa0efb4bf7/Lib/typing.py#L1349 And apart from the refactoring necessary to move variadic stuff into its own method (and docstrings, and comments, and tests), is only about 10 lines more than the current implementation.

[mrahtz]

Ok, so assuming we are ok with tuple[T, *Ts][*tuple[int, ...]], the final informal spec would be as follows:

• In general, we aim to be complete in our support variable substitution at runtime, supporting as many valid aliases as we can.
• For simplicity, we also support some aliases which are technically invalid according to PEP 646. In particular, we support multiple unpackings per argument list - e.g. tuple[*Ts][*tuple[int, ...], *tuple[str, ...]].
• Exception 1: Unpacked types (e.g. *tuple[int], *tuple[int, ...]) cannot be used as arguments to generics (or generic aliases) which expect a fixed number of type arguments. In practice, this means you can only use unpacked types as arguments to a generic (or generic alias) that has a TypeVarTuple in its parameter list.
  • Not valid:
  • list[*Ts]
  • list[*tuple[int]]
  • list[*tuple[int, ...]]
  • tuple[T][*tuple[int]]
  • tuple[T][*tuple[int, ...]]
  • tuple[T1, T2][*tuple[int, ...]]
  • tuple[T][str, *tuple[int, ...]]
  • Valid:
  • tuple[*Ts][*tuple[int, ...]]
  • tuple[*Ts][str, *tuple[int, ...]]
  • tuple[T, *Ts][*tuple[int, ...]]
  • tuple[T, *Ts][str, *tuple[int, ...]]
  • tuple[*Ts, T][str, *tuple[int, ...]]
  • tuple[T1, T2, *Ts][*tuple[int, ...]]
• Exception 2: Unpacked TypeVarTuples can only be used as arguments to generics (or generic aliases) whose sole parameter is also an unpacked TypeVarTuple - to avoid splitting the TypeVarTuple over multiple variables
  • Not valid:
  • tuple[T][*Ts]
  • tuple[T1, T2][*Ts]
  • tuple[T, *Ts][*Ts]
  • Valid:
  • tuple[*Ts][*Ts]
  • tuple[int, *Ts][*Ts]
• We do simplify unpacked 'concrete' tuples like *tuple[int]. For unpacked arbitrary-length tuples like *tuple[int, ...], we mostly leave them unsimplified, but do pull out their component types for regular TypeVars. For example:
  • tuple[*Ts][*tuple[int]] evaluates to tuple[int]
  • tuple[*Ts][*tuple[int], *tuple[str]] evaluates to tuple[int, str]
  • tuple[*Ts][*tuple[int, ...]] evaluates to tuple[*tuple[int, ...]]
  • tuple[T, *Ts][*tuple[int, ...] evaluates to tuple[int, *tuple[int, ...]]

Links to relevant PRs (since Jelle's links at the top broke after the GitHub migration, lol):

• https://github.com/python/cpython/pull/31828
• https://github.com/python/cpython/pull/32341
• https://github.com/python/cpython/pull/91766

[JelleZijlstra]

Two things I noticed on current main, we should make sure to address them:

• tuple[*Ts][*tuple[int, ...], *tuple[str, ...]] doesn't work on current main

On current main:

>>> tuple[*Ts, T][str, *tuple[int, ...]]
tuple[(<class 'str'>,), *tuple[int, ...]]

Should be tuple[str, *tuple[int, ...]]

[AlexWaygood]

I was talking with @JelleZijlstra just now and we thought that this can probably now be marked as "deferred blocker" rather than "release blocker" (i.e., still a priority, but doesn't need to block the beta release next week). I've gone ahead and changed the labels accordingly.

[gvanrossum]

(Don't read the email. Read the updated comment.)

[gvanrossum]

I'm sorry if I am going over old stuff, but I would naively expect that some examples marked Valid should be invalid:

• tuple[T, *Ts][*tuple[int, ...]]

Invalid because the substitution may be tuple[()].

• tuple[T, *Ts][str, *tuple[int, ...]]

Valid (T becomes str, etc.).

• tuple[*Ts, T][str, *tuple[int, ...]]

Invalid because it's too complicated to compute what T is (but I don't care too much).

• tuple[T1, T2, *Ts][*tuple[int, ...]]

Invalid for the same reason as the first one.

[pradeep90]

[Guido]

I'm sorry if I am going over old stuff, but I would naively expect that some examples marked Valid should be invalid: tuple[T, Ts][tuple[int, ...]] Invalid because the substitution may be tuple[()]. tuple[T1, T2, Ts][tuple[int, ...]] Invalid for the same reason as the first one.

You and I had discussed this in an earlier comment: https://github.com/python/peps/pull/2162#discussion_r762324527

tuple[T, Ts][str, tuple[int, ...]] Valid (T becomes str, etc.).

Yes, this is already part of the "Valid" list in Matthew's comment.

tuple[Ts, T][str, tuple[int, ...]] Invalid because it's too complicated to compute what T is (but I don't care too much).

If Matthew thinks it's not too complicated to implement, it sounds fine. The solution is Ts = tuple[str, *tuple[int, ...]], T = int.

[Matthew]

tuple[Ts][tuple[int, ...]] evaluates to tuple[*tuple[int, ...]]

Would be ideal if it evaluated to tuple[int, ...], but if that's hard to do, no worries.

[gvanrossum]

Thanks!

[serhiy-storchaka]

In the case

A = tuple[tuple[*Ts1], tuple[*Ts2]]
B = A[int, str, float]

where an error should be raised? In the first line, when an alias with multiple TypeVarTuples in parameters is created, or in the second line, when a generic with multiple TypeVarTuples is subscribed?

[serhiy-storchaka]

Currently I am implementing the second option. __parameters__ is lazily evaluated in the C code, with the first option we would lose laziness.

[pablogsal]

Nobody expects the Spanish inquisition!

Is there any user-visible change left to do in this issue? Notice any semantic change, grammar change, API change or data structure change must be done before beta 1 is released and only bugfixes are allowed after that.

As deferred blockers are raised to release blockers in beta 1 I have added the label and beta 1 is blocked on this until we decide how to proceed.

[serhiy-storchaka]

I think that all following changes can be classified as bugfixes or as minor internal refactoring. It should not block beta 1.

[JelleZijlstra]

Agree with Serhiy, this doesn't need to block the beta. Any edge cases we fix can be treated as bugfixes.

[gvanrossum]

Agreed. So should we just remove the blocker label(s)?

[pablogsal]

Ok, I am removing the release blocker tag then

[mrahtz]

[Pablo]

Nobody expects the Spanish inquisition!

This is possibly the best thing ever in the history of the universe

[Everyone]

As a quick update on the current status: Serhiy's done some great work in https://github.com/python/cpython/pull/92335 which fixes the majority of the type substitution test cases we've come up with.

The main thing left to do after that PR is merged is deal with the tricky cases of:

• generic[T, *Ts][*tuple[int, ...]] - should evaluate to generic[int, *tuple[int, ...]].. We have a proof-of-concept implementation of this in https://github.com/python/cpython/pull/91766.
• generic[T, *Ts][*tuple[int, ...], str] - should evaluate to generic[int, *tuple[int, ...], str]. I haven't started thinking about how to implement this yet.

@serhiy-storchaka How do you want to split the remaining work here? I'm happy to take on these two remaining cases, but given how much you've been doing recently I wondered whether you might prefer to take them on yourself :)

[serhiy-storchaka]

I still have doubts about splitting a variable-length tuple. I propose to wait some time until we get feedback from users of PEP 646. It may be later at the betas stage, or even in 3.12.

I am going to spent some time on refactoring, cleanup and optimization of the existing code.

[mrahtz]

I am going to spent some time on refactoring, cleanup and optimization of the existing code.

Ok, cool.

I continue to think it's pretty important that we support at least generic[T, *Ts][*tuple[int, ...]] sooner rather than later for the reasons mentioned in https://github.com/python/cpython/issues/91162#issuecomment-1100953692, so I'll work on getting this merged.

I think I will just leave generic[T, *Ts][*tuple[int, ...], str] unfixed for now, and indeed come back to it if we get feedback from users that it's important.

[serhiy-storchaka]

I do not understand reasons in https://github.com/python/cpython/issues/91162#issuecomment-1100953692, but if people need this, I think it is possible to implement it.

We should support also cases like A[*Ts, T][*tuple[int, ...]] -> A[*tuple[int, ...], int].

[serhiy-storchaka]

I will try to do this on the next weekends. @mrahtz, if you want, you can take it yourself.

[mrahtz]

Actually, reading through https://github.com/python/cpython/issues/91162#issuecomment-1100953692 again, I realised I myself might have not understood it completely either.

@pradeep90 When we say:

The former is important for migrating code to shape types. Suppose someone has an alias Foo = Array[T, Ts] and the migrating code doesn't want to specify the exact variadic dimensions. They could write Foo[tuple[int, ...]] (as we mention in the PEP). We'd be forbidding that case.

If I understand right, we're talking about a situation where a library has switched to using shape types:

DType = TypeVar('DType')
Shape = TypeVarTuple('Shape')
class Array(Generic[DType, *Shape]): ...

# Elsewhere in the code
MultiDeviceArray = Array[DType, *Shape]

def get_array_for_one_device(array: MultiDeviceArray, device_num: int) -> Array: ... 

And there's some user code which doesn't want to have to specify the shapes:

def get_important_array() -> MultiDeviceArray: ...

x = get_important_array()
get_array_for_one_device(x, device_num=0)  # Should work fine

In a case like this, isn't it enough for them to just to leave the alias MultiDeviceArray unparameterised? Or if they wanted to be explicit, wouldn't it be enough to just do MultiDeviceArray[Any, *tuple[int, ...]]? What am I missing?

[mrahtz]

@pradeep90 Friendly poke :)

[pradeep90]

Sorry for the delay! I kept putting it off :|

[Pradeep]: The former is important for migrating code to shape types. Suppose someone has an alias Foo = Array[T, Ts] and the migrating code doesn't want to specify the exact variadic dimensions. They could write Foo[tuple[int, ...]] (as we mention in the PEP). We'd be forbidding that case.

[Matthew]: In a case like this, isn't it enough for them to just to leave the alias MultiDeviceArray unparameterised?

The PEP defines the behavior for (a) MultiDeviceArray by saying that it behaves the same as (b) MultiDeviceArray[*tuple[Any, ...]]. But, under the proposed runtime specification, (b) would be illegal at runtime. That means there's no way for people to see the behavior for (b), in order to understand how (a) works.

In other words, what is the runtime value of a parameterless MultiDeviceArray? The value for (b) should be the same as that for (a). If (a) is defined, then (b) can be defined analogously. If (a) is not defined, we have other problems :)

(A minor consideration is that leaving parameters unspecified will lead to type checker errors in strict mode (in Pyre, Pyright, etc.). Using MultiDeviceArray[*tuple[int, ...]] avoids the type checker errors.)

---

Again, I'm fine with deferring the features if they are hard to implement.

[mrahtz]

[Pradeep]

Sorry for the slow reply too. Busy week :(

The PEP defines the behavior for (a) MultiDeviceArray by saying that it behaves the same as (b) MultiDeviceArray[*tuple[Any, ...]]

I've just realised - is this actually what we said in the PEP? https://peps.python.org/pep-0646/#behaviour-when-type-parameters-are-not-specified says: (emphasis mine)

When a generic class parameterised by a type variable tuple is used without any type parameters, it behaves as if the type variable tuple was substituted with Tuple[Any, ...].

The section on aliases, https://peps.python.org/pep-0646/#aliases, says similarly:

If the type parameter list is omitted entirely, the unspecified type variable tuples are treated as Tuple[Any, ...]

That is, only the TypeVarTuple is substituted with Tuple[Any, ...]. Iiuc, this is different from saying that the whole argument list is set to *Tuple[Any, ...].

Admittedly we maybe could have been clearer on this in the PEP. I don't think we ever say explicitly what type is assigned to the other type parameters in a case like this.

But I think it's natural to assume that TypeVars in the parameter list should be assigned to individual Anys. So in this case:

DType = TypeVar('DType')
Shape = TypeVarTuple('Shape')
class Array(Generic[DType, *Shape]): ...

MultiDeviceArray = Array[DType, *Shape]

I think that MultiDeviceArray should actually behave like Array[Any, *tuple[Any, ...]], rather than Array[*tuple[Any, ...]].

Is this analysis correct?

[gvanrossum]

Looks like the only interpretation that makes sense. If you write dict without parameters it has two Any parameters by default. It does not become dict[*Any].

[pradeep90]

[Matthew]

Is this analysis correct?

Yes, that is indeed how Pyre handles aliases with missing type arguments. T is replaced with Any and Ts is replaced with tuple[Any, ...]. I misspoke about the analogy between MultiDeviceArray and MultiDeviceArray[*tuple[Any, ...]], even though they both produce the same result.

---

[Matthew]

Admittedly we maybe could have been clearer on this in the PEP. I don't think we ever say explicitly what type is assigned to the other type parameters in a case like this.

That's not true. We explicitly mention the behavior for Foo[*tuple[Any, ...]] in the following paragraph and code snippet from the PEP:

Array[*Tuple[Any, ...]] stands for an array with an arbitrary number of dimensions of type Any. This means that, in the call to expect_variadic_array, Batch is bound to Any and Shape is bound to Tuple[Any, ...]

class Array(Generic[*Shape]): ...  # I'm including the definition of Array for completeness.

y: Array[*Tuple[Any, ...]] = read_from_file()

def expect_variadic_array(
    x: Array[Batch, *Shape]
) -> None: ...

expect_variadic_array(y)  # OK

1. In this case, the user sees that passing an Array[*tuple[Any, ...]] to an expected Array[Batch, *Shape] leads to Batch=Any, Shape=tuple[Any, ...]. So, the concept of splitting an unbounded tuple across Batch, *Shape is specified in the PEP.

   The exact same thing goes for passing an Array or an Array[*tuple[int, ...], str] to an expected Array[Batch, *Shape]. These too require splitting an unbounded tuple across a mix of TypeVars and TypeVarTuples.

2. However, if the user defined a perfectly-valid alias, MultiDeviceArray = Array[Batch, *Shape], and tried to use MultiDeviceArray[*tuple[Any, ...]], then it would fail at runtime (as per your proposal).

   This would be really surprising. There is no justification why (1) is able to split *tuple[Any, ...] across Batch, *Shape, but (2) fails at runtime.

In other words, the splitting behavior of unbounded tuples over a mix of TypeVar and TypeVarTuple is important and specified in general, not just for the niche case of runtime alias application. Restricting the splitting for aliases at runtime, while allowing it everywhere else would be a bad, inconsistent user experience.

Lmk if that makes sense. I'm happy to hop on a VC call this week, if this is something you'd like to discuss further. Might be faster than waiting for each other's replies :)

Road ahead

We're back to the original question of what to do about Array[T, *Ts][*tuple[int, ...], str]. I see two choices ahead:

1. Defer its implementation because it's too much work now - this seems reasonable.

   If you're curious about how Pyre (and TypeScript) handle cases like Array[T, *Ts, T2][*tuple[int, ...], bool, str], we bind the TypeVars from either side till we reach an unpacked element. So, we would bind T = int and T2 = str. Then we align the remaining middle portion - Ts = tuple[*tuple[int, ...], bool]. Happy to discuss in more detail if needed.

   (I hope we agree that this is doable at runtime but involved.)

2. Forbid it in the PEP because the runtime computation would be involved - this seems less than ideal. We seem to be going in the opposite direction from the runtime being more lenient than the type checker.

   If we really are going that way, we should probably discuss what it implies for future PEPs. Will they also have to restrict things because the runtime is trying to compute exact values (for generic aliases, etc.)?

I favor option (1). Curious to hear your thoughts, since it's not clear which way you are leaning.

Footnote

If the question is why would anyone specify MultiDeviceArray[*tuple[int, ...]] explicitly, we address that in the PEP:

This allows users to handle dynamic code gracefully while still explicitly marking the code as unsafe (by using y: Array[*Tuple[Any, ...]]). Otherwise, users would face noisy errors from the type checker every time they tried to use the variable y, which would hinder them when migrating a legacy code base to use TypeVarTuple.