Will recursive or mutually recursive bounds on TypeVar be supported?

[smallnamespace]

Reading through the discussion at python/typing#59, there was an example that had TypeVar bound that referenced itself. Is this intended to be eventually implemented? The actual PEP just has a bare Comparable.

A motivating example (from the Java world) is discussed here, in the context of their Enum. An example in Python:

from typing import Generic, Optional, Tuple, TypeVar  

# Would like to write bound='TypedCons[T, V]' here, where T is self-referential
T = TypeVar('T', bound='TypedCons')
V = TypeVar('V')  


class TypedCons(Generic[T, V]):  
    def __init__(self, value: V, cdr: Optional[T]=None) -> None:  
        self.value = value  
        self.cdr = cdr  

    def first_two(self) -> Tuple[T, T]:  
        # Fails without cast with "Incompatible return value type: expected Tuple[T`1, T`1], got Tuple[example.TypedCons[T`1, V`2], T`1]"  
        return self, self.cdr  

class IntCons(TypedCons['IntCons', int]):  
    pass

# Recursive bound would reject this
class BadCons(TypedCons['IntCons', str]):  
    pass  

If I try to write the recursive bound, I get:

example.py:3: error: Invalid type "example.T"

A similar example where this is needed is at https://github.com/smallnamespace/pymcts/blob/b5e1375e67983ef7b5baa2511c680074fd31b00c/pymcts/tree.py#L78 -- here we need to use the fact that N and Node are identical.

[smallnamespace]

@gvanrossum @JukkaL

Reading through python/typing#59 again, it seems like the recursive reference is the same thing as F-bounded polymorphism, which you want to hold off on.

Just curious, is that due to the difficulty in implementing the checker properly, or in using bounded quantification correctly?

[gvanrossum]

Honestly my head explodes each time I try to understand this idea. So maybe it's also hard to implement? OTOH if you can come up with a patch I'm not opposed.

…

--Guido (mobile)

[smallnamespace]

This paper suggests a straightforward implementation, but it'll take awhile for me to wrap my ahead around mypy's codebase. Would it make it into the PEP if mypy supported it?

Note that realistic f-bounded polymorphism implementations would have restrictions on what can be written, because the completely general case (with variance) is undecidable. The paper above makes type checking tractable by splitting types in 'shapes' and 'materials'.

[gvanrossum]

Probably.

On Mon, May 30, 2016 at 10:52 AM, smallnamespace notifications@github.com
wrote:

This paper
http://www.cs.cornell.edu/%7Eross/publications/shapes/shapes-pldi14-tr.pdf
suggests a straightforward implementation, but it'll take awhile for me to
wrap my ahead around mypy's codebase. Would it make it into the PEP if mypy
supported it?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#1561 (comment), or mute
the thread
https://github.com/notifications/unsubscribe/ACwrMpdEN-8eWRTa9bJPobwdkkrjQ4Uxks5qGyPDgaJpZM4Ijc1v
.

--Guido van Rossum (python.org/~guido)

[JukkaL]

When I looked into this it seemed like this wouldn't quite work for perhaps the most common potential use (Comparable[T]) because of the semantics of operator methods (reverse methods, etc.). Thus I wasn't aware of many interesting use cases where this would actually work, whereas there were a lot of other potential features missing or broken that had well-known use cases (and still are). However, if the implementation isn't complex we'd probably accept a PR.

[erictraut]

I think mypy is doing the right thing here. The above code sample clearly exhibits a type violation, for a couple of reasons:

1. The type of self is not necessarily T. The type of T could be a different subtype of TypedCons.
2. The type of the expression self.cdr is not T, it's T | None.

I recommend closing this issue.