Substitution of ParamSpec in Concatenate

[serhiy-storchaka]

BPO	44791
Nosy	@gvanrossum, @serhiy-storchaka, @JelleZijlstra, @miss-islington, @sobolevn, @Fidget-Spinner, @AlexWaygood, @cdce8p
PRs	bpo-44791: Fix substitution of ParamSpec in Concatenate with differen… #27518 [3.10] bpo-44791: Fix substitution of ParamSpec in Concatenate with different parameter expressions (GH-27518) #30959 bpo-44791: Accept ellipsis as the last argument of Concatenate #30969

^{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:

assignee = None
closed_at = None
created_at = <Date 2021-07-31.10:25:13.991>
labels = ['library', '3.10', '3.11']
title = 'Substitution of ParamSpec in Concatenate'
updated_at = <Date 2022-02-20.09:11:54.505>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2022-02-20.09:11:54.505>
actor = 'med2277'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Library (Lib)']
creation = <Date 2021-07-31.10:25:13.991>
creator = 'serhiy.storchaka'
dependencies = []
files = []
hgrepos = []
issue_num = 44791
keywords = ['patch']
message_count = 9.0
messages = ['398632', '398645', '398661', '411862', '411863', '411926', '411933', '413534', '413573']
nosy_count = 9.0
nosy_names = ['gvanrossum', 'serhiy.storchaka', 'JelleZijlstra', 'miss-islington', 'sobolevn', 'kj', 'AlexWaygood', 'cdce8p', 'med2277']
pr_nums = ['27518', '30959', '30969']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = None
url = 'https://bugs.python.org/issue44791'
versions = ['Python 3.10', 'Python 3.11']

[serhiy-storchaka]

Substitution of ParamSpec in Concatenate produces weird results:

>>> import typing
>>> P = typing.ParamSpec('P')
>>> typing.Concatenate[str, P][int]
typing.Concatenate[str, int]
>>> typing.Concatenate[str, P][[int]]
typing.Concatenate[str, (<class 'int'>,)]
>>> typing.Concatenate[str, P][typing.Concatenate[int, P]]
typing.Concatenate[str, typing.Concatenate[int, ~P]]

But all these results are invalid:

>>> typing.Concatenate[str, int]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/serhiy/py/cpython/Lib/typing.py", line 309, in inner
    return func(*args, **kwds)
           ^^^^^^^^^^^^^^^^^^^
  File "/home/serhiy/py/cpython/Lib/typing.py", line 400, in __getitem__
    return self._getitem(self, parameters)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/serhiy/py/cpython/Lib/typing.py", line 595, in Concatenate
    raise TypeError("The last parameter to Concatenate should be a "
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
TypeError: The last parameter to Concatenate should be a ParamSpec variable.
>>> typing.Concatenate[str, (int,)]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/serhiy/py/cpython/Lib/typing.py", line 309, in inner
    return func(*args, **kwds)
           ^^^^^^^^^^^^^^^^^^^
  File "/home/serhiy/py/cpython/Lib/typing.py", line 400, in __getitem__
    return self._getitem(self, parameters)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/serhiy/py/cpython/Lib/typing.py", line 595, in Concatenate
    raise TypeError("The last parameter to Concatenate should be a "
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
TypeError: The last parameter to Concatenate should be a ParamSpec variable.
>>> typing.Concatenate[str, [int]]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/serhiy/py/cpython/Lib/typing.py", line 309, in inner
    return func(*args, **kwds)
           ^^^^^^^^^^^^^^^^^^^
  File "/home/serhiy/py/cpython/Lib/typing.py", line 400, in __getitem__
    return self._getitem(self, parameters)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/serhiy/py/cpython/Lib/typing.py", line 595, in Concatenate
    raise TypeError("The last parameter to Concatenate should be a "
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
TypeError: The last parameter to Concatenate should be a ParamSpec variable.
>>> typing.Concatenate[str, typing.Concatenate[int, P]]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/serhiy/py/cpython/Lib/typing.py", line 309, in inner
    return func(*args, **kwds)
           ^^^^^^^^^^^^^^^^^^^
  File "/home/serhiy/py/cpython/Lib/typing.py", line 400, in __getitem__
    return self._getitem(self, parameters)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/serhiy/py/cpython/Lib/typing.py", line 595, in Concatenate
    raise TypeError("The last parameter to Concatenate should be a "
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
TypeError: The last parameter to Concatenate should be a ParamSpec variable.

I expect that

1. The last parameter to Concatenate can be a Concatenate. Inner Concatenate should merge with the external one:

Concatenate[str, Concatenate[int, P]] -> Concatenate[str, int, P]
Concatenate[str, P][Concatenate[int, P]] -> Concatenate[str, int, P]

2. The last parameter to Concatenate can be a list of types. The result should be a list of types.

Concatenate[str, [int, dict]] -> [str, int, dict]
Concatenate[str, P][[int, dict]] -> [str, int, dict]

3. The last parameter to Concatenate can be an ellipsis.

Concatenate[str, ...]
Concatenate[str, P][...] -> Concatenate[str, ...]

[Fidget-Spinner]

Should Concatenate support substitution to begin with? PEP-612 doesn't say anything, and I am fairly certain it's a special typing form, not a generic. So I don't really understand what it means to substitute Concatenate.

Then again, Callable with a nested Concatenate can be substituted, and we currently implement that by using Concatenate's substitution behavior as proxy. But again, the meaning isn't clear to me.

I also noticed this strange part in PEP-612 about user-defined generic classes:

"Generic[P] makes a class generic on parameters_expressions (when P is a ParamSpec)":

...
class X(Generic[T, P]):
f: Callable[P, int]
x: T

def f(x: X[int, Concatenate[int, P_2]]) -> str: ...  # Accepted (KJ: What?)
...

The grammar for parameters_expression is:

parameters_expression ::=
| "..."
| "[" [ type_expression ("," type_expression)* ] "]"
| parameter_specification_variable
| concatenate "["
type_expression ("," type_expression)* ","
parameter_specification_variable
"]"

I'm very confused. Does this mean Concatenate is valid when substituting user generics? Maybe I should ask the PEP authors?

My general sense when I implemented the PEP was that it was intended primarily for static type checking only. IMO, runtime correctness wasn't its concern.

[serhiy-storchaka]

My understanding is that type expression is valid when substitute TypeVar and parameters expression is valid when substitute ParamSpec.

[serhiy-storchaka]

New changeset ecfacc3 by Serhiy Storchaka in branch 'main':
bpo-44791: Fix substitution of ParamSpec in Concatenate with different parameter expressions (GH-27518)
ecfacc3

[miss-islington]

New changeset 89db090 by Miss Islington (bot) in branch '3.10':
bpo-44791: Fix substitution of ParamSpec in Concatenate with different parameter expressions (GH-27518)
89db090

[serhiy-storchaka]

PR 27518 fixes a substitution of a ParamSpec variable with a Concatenate nad a list of types. It is not specified explicitly in PEP-612, but it does not contradict it.

PR 30969 makes an ellipsis be valid as the last argument of Concatenate to fix a substitution of a ParamSpec variable with an ellipsis. It contradicts with PEP-612 which allows only a ParamSpec variable there.

[gvanrossum]

Before you start supporting things that contradict PEP-612 this should be discussed on typing-sig (or in the python/typing tracker).

Honestly I'd feel more comfortable if there was agreement on typing-sig with your previous PRs in this issue as well; "it does not contradict it" is not a ringing endorsement. :-)

[JelleZijlstra]

I'm looking at #30969 and I'm not sure what the motivation for the change is. PEP-612 is quite precise here (https://www.python.org/dev/peps/pep-0612/#id1) and allows only a ParamSpec as the last argument to Concatenate.

What is the use case for using ... as the last argument? What should it mean to a static type checker?

[med2277]

Concatenate[int, ...] I would interpret as a function signature with first argument int, followed by arbitrary arguments afterwards. I haven't run into this case, but ... is allowed in other spots Paramspec is allowed currently.

P = Paramspec("P")

class Foo(Generic[P]):
  ...

Foo[...] # Allowed
Callable[..., None] # Allowed

Are there any other places a paramspec is allowed? Generic type argument, first argument to callable, last to concatenate, anything else?

I'm unaware of any type checking use case for Concatenate[int, ...]. You can practically get same thing by using a paramspec variable without using it elsewhere so that it captures, but then effectively discards that information.

def use_func1(f: Callable[Concatenate[int, P], None]) -> None:
  ...

def use_func2(f: Callable[Concatenate[int, ...], None]) -> None:
  ...

feels like those two signatures should encode same information.

[JelleZijlstra]

I still haven't seen a compelling reason to allow substituting ... in Concatenate, so I think we should leave things unchanged here and close #30969.

[JelleZijlstra]

I just talked to @pradeep90 and he is actually on board with allowing this; it seems like a reasonable generalization, and we can allow it at runtime already pending type checker support.

[gvanrossum]

Mind summarizing the use case here? Maybe give a simple example?

[JelleZijlstra]

Pradeep showed me an email thread from a few months ago (I think you were also on it) that showed a use case. I don't recall the exact code, but basically it would allow pyre to infer Callable[Concatenate[T1, ...], T2] instead of Callable[..., T2] in some cases.

[gvanrossum]

Sure. I wish we had allowed spelling that as Callable[[T1, ...], T2] -- the Concatenate seems to do nothing except make everything longer and less readable. :-(

[pradeep90]

Pradeep showed me an email thread from a few months ago (I think you were also on it) that showed a use case. I don't recall the exact code, but basically it would allow pyre to infer Callable[Concatenate[T1, ...], T2] instead of Callable[..., T2] in some cases.

@JelleZijlstra Reproducing the email thread (from August 2021)… for future reference:

Mark Mendoza said:

Guido is correct in that I've moved on from working on Python typing in my day-to-day work.
Overall, this plan sounds totally reasonable. Serhiy, your proposals for substitution rules line up with my intentions/intuitions, save for the Callable[Concatenate[int, P], str][...] substitution, which I think I originally implemented as resolving to Callable[..., str]. However, your proposal seems totally reasonable! In any case, I think augmenting the PEP with more precision as to the solution rules is a good idea.
As for the details of the generic alias question, and any other ongoing work in this area, I'd refer you to Pradeep, who is on the Pyre team today, and implemented our support for generic aliases.

My reply to Serhiy's question:

Concatenate and ... and other edge cases

As Mark mentioned, Pyre's current behavior is to convert Callable[Concatenate[int, P], str][...] to Callable[..., str].

If we want to allow Callable[Concatenate[int, ...], str], then we'd probably have to extend the grammar in PEP 612 to allow any parameters_expression as the second argument to Concatenate instead of just parameter_specification_variable. That will make the following cleanly interchangeable in the syntax: P, [int, str], ..., and Concatenate[int, P].

before:

callable ::= Callable "[" parameters_expression, type_expression "]"

parameters_expression ::=
  | "..."
  | "[" [ type_expression ("," type_expression)* ] "]"
  | parameter_specification_variable
  | concatenate "["
                   type_expression ("," type_expression)* ","
                   parameter_specification_variable
                "]"

after:

callable ::= Callable "[" parameters_expression, type_expression "]"

parameters_expression ::=
  | "..."
  | "[" [ type_expression ("," type_expression)* ] "]"
  | parameter_specification_variable
  | concatenate "["
                   type_expression ("," type_expression)* ","
                   parameters_expression                                          # <--- change
                "]"

This would allow things like

1. Concatenate[int, str, P]
2. Concatenate[int, str, ...]
3. Concatenate[int, str, [str, bool]]
4. Concatenate[int, str, Concatenate[str, bool, P]]

(3) should be equivalent to [int, str, str, bool] and (4) should be equivalent to Concatenate[int, str, str, bool, P].

This would be more flexible than the previous behavior. It would handle different edge cases equivalently regardless of whether they came from alias substitution or from direct user-written types. But it would also require more parsing work from typecheckers. Pyre's current behavior is simpler but less flexible. This might be worth checking on in typing-sig since people from other typecheckers may have opinions.

I'm ok with adding these items to the PEP since they're not explicitly stated. Happy to extend the reference implementation in Pyre if we reach a consensus on the ... case.

[serhiy-storchaka]

3. Concatenate[int, str, [str, bool]]
4. Concatenate[int, str, Concatenate[str, bool, P]]

I do not think we need this.

We need a way to express the result of parameter_specification_variable substitution with parameters_expression, that's all. It is not necessary that substitution gives the same type. For example, Union[T, int][int] is just int, not Union[int].

The only problem was with ellipsis. There is no valid syntax to express the result. The specification should be extended to allow either Concatenate[int, str, ...], or [int, str, ...], or some other syntax.

[AlexWaygood]

I believe that we eventually arrived on consensus here that the changes made were acceptable. (Apologies if this summary is inaccurate.) Is there anything left to do here from a CPython/runtime perspective, or can this now be closed?

Discussions about whether the PEP should be updated should probably continue over at python/typing, if there are still unresolved questions.

[AlexWaygood]

Closing for now. Feel free to reopen (or open a new issue at python/typing) if there's still more to discuss :)