Decide meaning of alias with one generic and one concrete parameter

[gvanrossum]

See python/mypy#606. We allow the following, and they are well-defined:

from typing import TypeVar, Dict
T = TypeVar('T')
U = TypeVar('U')
X = Dict[int, str]
Y = Dict[T, U]

But what does this mean?

Z = Dict[T, int]

In typing.py this currently defines Z as something with two parameters, the second constrained to int or subclasses thereof. But another reasonable interpretation would be that Z has one parameter, corresponding to T only.

The second interpretation is actually more reasonable. (As long as we require that all parameters are either concrete or a simple type variable, not another type expression or alias containing a type variable.)

If we agree, we should define this in the PEP and implement it in typing.py.

[gvanrossum]

On second thoungt I don't think we need language for aliases (they just mean whatever the expression on the RHS would mean in the context where the alias is used) but I added language clarifying that defining a class that inherits from Mapping[str, T] creates a class with one parameter, T.

This is not fixed in typing.py, so keeping the "bug" label.

[JukkaL]

Here are some examples to make sure I understand the feature right. Consider these definitions:

from typing import TypeVar, Dict

T = TypeVar('T')
S = TypeVar('S')

D1 = Dict[T, S]
D2 = Dict[T, int]

Now these two signatures would be equivalent:

def f(x: Dict[T, S]) -> Tuple[T, S]: ...
def g(x: D1) -> Tuple[T, S]: ...

Also, these two would be equivalent:

def f(x: Dict[int, T]) -> T: ...
def g(x: D2) -> T: ...

These would be errors:

def err1(x: D1[int, str]) -> None: ...
def err2(x: D2[str]) -> None: ...

[gvanrossum]

Here are some examples to make sure I understand the feature right.
Consider these definitions:

from typing import TypeVar, Dict

T = TypeVar('T')
S = TypeVar('S')

D1 = Dict[T, S]
D2 = Dict[T, int]

Now these two signatures would be equivalent:

def f(x: Dict[T, S]) -> Tuple[T, S]: ...
def g(x: D1) -> Tuple[T, S]: ...

Correct.

Also, these two would be equivalent:

def f(x: Dict[int, T]) -> T: ...
def g(x: D2) -> T: ...

No, for f, T is the dict's value type, while for g, T is the dict's key type. Maybe you meant this?

def f(x: Dict[T, int]) -> T: ...
def g(x: D2) -> T: ...

Those are indeed equivalent.

These would be errors:

def err1(x: D1[int, str]) -> None: ...

Why would that be an error? It just means (to me) that x is a dict with
int keys and str values.

def err2(x: D2[str]) -> None: ...

This example is the crux of the issue. The current implementation in
types.py disallows that -- it only accepts D2 with two parameters, and the
second parameter must be int (or a subclass). But I think this is wrong,
and I think it would be nice if we had some kind of rule that the following
are equivalent (in any context, and including situations where some part is
an alias expansion):

Dict[int, str]
Dict[int][str]

If you agree, can you update the PEP and then reassign to me so I can fix
typing.py? This will probably not be done by Friday.

[ilevkivskyi]

I must say that the idea to have both:

Dict[int, str] 
Dict[int][str]

means that generics have a very intuitive semantics, this is the same as for normal functions, normal variables, and partial application. With this generics feel like real first class members of the language. It would be cool to have this.

[gvanrossum]

Unfortunately I think I misspoke. I think allowing Dict[int] is too confusing and asking for trouble (it would be like calling a function with too few parameters return a partial function -- that's fine in Haskell, but not Python). However this should work:

T = TypeVar('T')
DS = Dict[str, T]
D = DS[int]
# Now D is the same type as Dict[str, int]

And this should work too:

T = TypeVar('T')
DI = Dict[T, int]
D = DI[str]
# Again, D is the same type as Dict[str, int]

[ilevkivskyi]

I agree, if one has two parameters, one must specify which parameter to fix, first or second.
Moreover, imagine that one has MyGenClass[A, B, C], it is absolutely not clear what would M = MyGenClass[int, str] mean. However, one can write M = MyGenClass[T, int, str] or M = MyGenClass[int, T, str], etc, and then for example M[bool]. Although, it is slightly verbose, it is really unambiguous and very flexible.

[spkersten]

I'm also in favor of the latest proposal. Allowing for currying would be another concept on top of something that might already be confusing.

On 21 mei 2015, at 23:12, ilevkivskyi [email protected] wrote:

I agree, if one has two parameters, one must specify which parameter to fix, first or second.
Moreover, imagine that one has MyGenClass[A, B, C], it is absolutely not clear what would M = MyGenClass[int, str] mean. However, one can write M = MyGenClass[T, int, str] or M = MyGenClass[int, T, str], etc, and then for example M[bool]. Although, it is slightly verbose, it is really unambiguous and flexible.

—
Reply to this email directly or view it on GitHub.

[gvanrossum]

Jukka, if you have time for this, it would be good to write this up in the PEP (if you think we've arrived at a workable and unambiguous proposal).

[JukkaL]

I won't be able to do it today, sorry, at least until the evening.  

—
Sent from Mailbox

On Fri, May 22, 2015 at 7:34 AM, Guido van Rossum
[email protected] wrote:

Jukka, if you have time for this, it would be good to write this up in the PEP (if you think we've arrived at a workable and unambiguous proposal).

Reply to this email directly or view it on GitHub:
#115 (comment)

[gvanrossum]

So let me summarize where this is. The PEP says that this should work:

class M(Mapping[T, str]): ...

and that now M has one parameter, T. This is not supported by typing.py yet (it sees M as having two parameters).

The PEP does not specify whether the following is allowed (it isn't supported by typing.py):

M = Mapping[T, str]  # OK
MM = M[str]  # TypeError

I propose that both should work. (But I still have some misgivings about the latter; see below.)

I also propose that this should not work:

M = Mapping[str]

The only ways to start with a generic type of N parameters and end up with a generic type of fewer but not zero parameters is to either subclass or create an alias from it, using concrete types for some parameter slots and type variables for other slots.

Also, while the following is allowed:

A = Mapping[Union[T, str], int]

the alias A must still be used with two parameters (each bounded by the corresponding parameter to Dict) and A cannot be used as a base class for a generic class. (This makes M = Mapping[T, str] above a bit of a special case, and I'm not 100% sure I like it.)

[ilevkivskyi]

I don't think the example with Union could be really useful. Probably in most cases one can use TypeVar('T', int, float, str) instead of Union[TypeVar('T', int, float), str].
On the other hand I think something like:

T = TypeVar('T')
S = TypeVar('S')

class MyMap(Mapping[Tuple[T, S], str]): ...

could be useful. In general: making a type more specific does not always mean reducing the number of type parameters. The above example currently fails with

TypeError: Cannot inherit from a generic class parameterized with non-type-variable typing.Tuple[~T, ~S]

Maybe typing should support this?

[gvanrossum]

I've just added some words (examples, really) to the PEP that imply Jukka's simpler set of rules from #85, in rev eeb7393. Please review.

[ilevkivskyi]

@gvanrossum I noticed that your example added to PEP contains Iterable[Tuple[K, V]], but this is still not supported by typing.py, I still get exception Cannot inherit from a generic class parameterized with non-type-variable... mentioned above. I just wanted to add that this problem also blocks #177.

[gvanrossum]

I know! I'm looking into it but it's a somewhat tricky change. I'm going on vacation until April 4th and I don't expect I'll get to it before then. It will be done before Python 3.5.2 is released.

[gvanrossum]

I expect I'll have to redesign and rewrite a large swath of typing.py. Here are some early thoughts on the design:

How this SHOULD work

• class C(Generic[T1, T2, ..., Tn]): ... creates a generic class
  C with parameters (T1, T2, ..., Tn).

• class D(C): ... creates a NON-generic class subclassed from
  C[Any, Any, ..., Any].

• class D(C[S1, S2, ...Sn]): ... creates a generic class with
  parameters (S1, S2, ...Sn) where there must be the same number
  of parameters as C. (Though maybe we shouldn't even enforce
  that?)

• class D(C[Tuple[S1, S2], S3, ..., Sn]): ... creates a generic
  class with parameters (S1, S2, S3, ..., Sn) where the parameters
  are taken from the list of bases in textual order, skipping
  duplicates (for a duplicate the leftmost occurrence is kept).

• Ditto for multiple inheritance from different generic classes.

• If you explicitly inherit from Generic[S1, S2, ..., Sn] then
  only those type variables should occur, and their order is
  always (S1, S2, ..., Sn) even if their textual occurrencs is
  different.

• Can you inherit from the same generic class twice with different
  parameters (e.g. C[S1, S2], C[S3, S4])? Probably not.

• For a generic class C with parameters (T1, T2, ..., Tn) you can
  index it with exactly n type expressions, C[E1, E2, ..., En].
  Each type expression may either be a concrete type (note that
  Any is concrete) or a parameterized type using as many type
  variables as you want. If all type expressions (Ei) are
  concrete types (contain no type variables, e.g. C[int, int])
  then the result is a concrete type. Otherwise the result is an
  "indexed generic class" (e.g. C[int, Tuple[T, T]]). An indexed
  generic class can be used in the following places:

  (0) In a type alias, i.e. an assignment of a type to a variable,
  e.g.

    A = C[int, Tuple[T, T]]
  
  Type aliases (when recognized by mypy) add no semantics and
  their use is just to avoid repetition, e.g.
  
    def foo(a1: A, a2: A, a3: Iterable[A]) -> List[A]:
        ...
  

  (a) As a type annotation in a function signature; the function
  will be generic, e.g.

    def foo(a: C[int, Tuple[T, T]]) -> None:
        ...
  

  (b) As a base class in a class definition; the class will be
  generic, e.g.

    class D(C[int, Tuple[T, T]]) -> None:
        ...
  

  (c) As an index to another generic class; the resulting
  expression will be another indexed generic class, e.g.

    E[C[int, Tuple[T, T]]]
  

  (d) As an argument to a special form like Union[] or TypeVar(),
  e.g.

    U = Union[str, C[int, Tuple[T, T]]]
    S = TypeVar('S', C[int, Tuple[T, T]])
  
  (I'm not actually sure what the latter would mean.)
  

  (e1) An indexed generic class can be indexed further. E.g. the
  following is valid, and means C[int, Tuple[str, str]]
  (i.e. a concrete type):

    C[int, Tuple[T, T]][str]
  
  (But mypy currently doesn't support it.)
  
  And e.g. the following produces another indexed generic class
  
    C[int, Tuple[T, T]][Tuple[S, S]]
  
  This would be equivalent to
  
    C[int, Tuple[Tuple[S, S], Tuple[S, S]]]
  
  (But again mypy doesn't supportt it yet.)
  

  (e2) Alternatively, maybe we should forbid further indexing an
  indexed generic type.

Possible algorithm

• Define a function that takes a list of type objects and extracts
  a (possibly empty) list of type variables from it. Call it
  type_vars(a: List[Type]) -> List[TypeVar]. Note that Type can also
  be a string representing a forward reference.
• In getitem(), call type_vars() on the list of subscripts,
  and construct a new generic type from those -- setting
  parameters to None if there are no type variables. Also set
  arguments to the raw list of subscripts.
• In the class constructor, look over the bases.
  • Classes that aren't generic are left alone.
  • Any of them that look like un-indexed generic types
    (e.g. plain 'Iterable') are given a list of Any parameters
    (except if it's 'Generic' -- that's an error).
  • Now find an explicit Generic[...] base, if any. Those are
    special, and the subscripts must be distinct type variables.
  • Call type_vars() over the rest.
  • If there was an explicit Generic base, type_vars() must be a
    subset of the parameters to Generic, and the latter are our
    parameters; otherwise imply a Generic base with exactly the
    type_vars() list, and those are the parameters.
  • If there are any parameters, construct a new (un-indexed)
    generic class with those parameters; if there are no
    parameters, construct a concrete class (if we can -- maybe
    it's just a generic class with __parameters__ set to None or
    an empty list/tuple).

[gvanrossum]

Not to tease too much, but I think I've got this implemented. However JetBlue's free wifi apparently blocks git (though web traffic goes through). Once I'm on the ground I'll push a branch so you can kick the tires.

[ilevkivskyi]

Everything looks logical. At first reading I didn't find any problems or inconsistencies. Concerning your bullet number 3: I think it is better to require the same total number of parameters plus concrete types (including Any). So that one can disregard some parameters by explicitly placing Any

class C(Generic[T1,T2]): ...
class D(C[Any, S]): ...

Concerning the choice between (e1) and (e2) I vote for (e1). I could imagine a situation when some library provides a generic class that is in fact indexed, so that if we prohibit further indexing users will have quite limited options and get unexpected errors. Also from the point of view of your algorithm I do not see a difference between "normal" generic and an "indexed" one, at the last step in the class constructor you create an un-indexed generic (and I think this is a good simple choice).

Looks like there is a big piece of work ahead. It would be great if you implement all the logic that you described.

[ilevkivskyi]

Wow! That is fast.

[gvanrossum]

Pushed. Review away!

[JukkaL]

Finally got around to reading the proposal -- it looks good, though the language feels a little vague at places. Making the definitions very rigorous would likely make them harder to read, so you may prefer to leave them as they are. I haven't looked at the implementation update yet.

[gvanrossum]

Which language is vague? The long comment I wrote in this issue? That was really just me trying to understand the intention of the PEP and figuring out how to implement it. Or the language in the PEP? That could use some tightening up so others won't fall in the same trap I fell into when I wrote the earlier implementation. But I'm blind for its vagueness now, so someone will have to propose specific edits.

[JukkaL]

It was about the long comment above. If it's only for this discussion then
please ignore my comment.
On Sat, Mar 26, 2016 at 19:50 Guido van Rossum [email protected]
wrote:

Which language is vague? The long comment I wrote in this issue? That was
really just me trying to understand the intention of the PEP and figuring
out how to implement it. Or the language in the PEP? That could use some
tightening up so others won't fall in the same trap I fell into when I
wrote the earlier implementation. But I'm blind for its vagueness now, so
someone will have to propose specific edits.

—
You are receiving this because you were assigned.
Reply to this email directly or view it on GitHub
#115 (comment)

[gvanrossum]

OK. FWIW the implementation goes with (e1), but that elicited the only feedback so far: #195 (comment) (my tentative response is right below it).