You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
NoReturn and Never are underspecified in the spec #1458
Never was added without a PEP as a way to directly indicate that something is uninhabited in 3.11
This brings up something from CarliJoy/intersection_examples#5 (comment) where we now have a way to express what appears to be an LSP violation that type checks (incorrectly) properly via structural subtyping by mishandling Never as a subtype of other types. Never is not a subtype of all other types. As the bottom type, it is uninhabited and does not follow subtyping rules.
I believe under LSP, B is no longer a safe drop-in replacement for A. It's important to note that ongoing work to formalize the type system, including Never does not treat Never as a subtype of all other types, see the ongoing work here: http://bit.ly/python-subtyping
(Sorry if this is a lot, I've split my comments by concern to not have a singular wall of text)
I don't know how breaking changing the definition of Never to be more in line with what proven theory says is correct for the bottom type would be, and I'm not in a great place to implement something to that effect right now to run against mypy_primer, but I think it is worth considering.
Notably, the only actual changes behaviorally is that Never can still arise from type narrowing removing all other possible types, but any code depending on an instance of Never can't be expected to be validly reached at runtime, and Never can't be used to replace other types without it being by removing the other types. With this change, the only function which should ever receive Never as an argument, is assert_never (or any other future function intended to handle how runtime realities may diverge from static analysis due to misuse or the uncertainties of the real-world code), and only at type checking time. It would still be valid to have as a return type (indicating the lack of return)
assert_never's signature should also probably be updated too
@overloaddefassert_never(obj: object) ->Never: ... # raises at runtime if called with any real object, purpose is `unreachable` code@overloaddefassert_never(obj: Never) ->None: ... # the point is ensuring the type has been exhausted of all possible typesdefassert_never(obj):
...
I know there's existing work on formalization going on elsewhere, but we're running into issues with the current less formal definitions now, and with ongoing work in trying to get the Intersections PEP ready.
One area of contention is whether the concept called a "bottom type" participates in subtype relationships. It makes logical sense to me that it would given that it satisfies all of the set-theoretic properties of subtyping, but it's possible I'm missing something here. If we're not able to agree on whether Never is a subtype of all other types, perhaps we can at least achieve agreement about whether Never is consistent with all other types. In a gradual type system, "is-consistent-with" is the relevant test. If we can agree on that, then I think the other point is largely moot, and we can avoid further debate.
I disagree that Never is consistent with other types, but it's probably useful to understand how it seems people got to a point where they have come to the conclusion that it is.
Lets start with something basic, If I specify in a function parameter annotation a singular static type, it isn't just that singular static type which is correct to give the function. Anything which can suitably stand in as a replacement for this singular type is also valid. So the parameter annotation doesn't represent one type (except in cases of invariant parameters) even though it is spelled as one type. This conceptual set of possible types which can be used in the hypothetical function exists at the same higher order @mikeshardmind referred to when describing how the top and bottom type don't exist at the same level as static and gradual types in the set-theoretic model.
In python, we have two ways that are supported by the type system for this. Inheritence (nominal typing) and Protocols (structural typing). Never can't suitably stand in for any type. It lacks the structure of every type, as it can't even exist, and it isn't a subclass of any other type either. It isn't a gradual type, it's the lack of a type all together.
So why is Never a suitable replacement in a return type? Well, it isn't. Because we aren't returning a type anymore, at least, not in a way that typing checks* and python does not have the same code path for returning values and raising exceptions, a function which unconditionally raises can have it's return value annotation used to mark the lack of return value without this being a replacement of the return type; Rather, it's specifying the lack of a type being returned.
I believe the original name of NoReturn was actually more correct for most places users could actually specify it, and some of the original insight of those who named it that may have fallen away to lack of recording anywhere important. The one case where Never is more correct as an annotation, is in the special purpose function assert_never, which the goal of is also to say that there is no longer a valid type. This is similar to unreachable in many compiled static languages. Actually reaching unreachable signals an error, as would passing an instance of something which shouldn't exist (the type system believes there are no remaining options, hence Never).**
I think it's how errors are handled in python and many other languages, and Never appearing to work as a replacement in one place (return values) that misleads people into believing it should work everywhere and be consistent with all types.
*Exceptions are really still just values with special control flow, but absent a proposal to add checked exceptions to python's type system, this distinction doesn't matter. I don't care about or want checked exceptions in python, but adding this to the type system would be an ordeal that if someone does want, they would find issues arise with Never as a replacement annotation without additional syntax.
** Never is still a good and useful name though. Never can still correctly arise in inference with elimination of possible types, and it would be weird to have NoReturn as the name in inference in that case.
So, why does your example seemingly break LSP? It doesn't actually, because you can't actually construct an instance of B!
I think it is debatable whether constructing an instance of B should be disallowed, or if it is enough that access to foo always raises an exception for B.foo to have type Never. However, this is moot. The same issue arises for methods returning Never and NoReturn:
mypy allows this, but this arguably violates LSP for the same reasons as the example in OP. It introduces unreachable code into methods using A. IMHO, creating instances of this B should be allowed, but this inheritance should generate an error.
Also note that
PEP 484 does not specify any subtyping relationships for NoReturn.
There are several issues for mypy where people ask to disallow using NoReturn and Never as values, because this hides bugs. [1][2][3]
mypy already disallows using functions that return None as values even if this is not a type error, because this is likely a bug. [4]
mypy allows this, but this arguably violates LSP for the same reasons as the example in OP. It introduces unreachable code into methods using A.
I think a type theorist would reply that yes, you are allowed to construct an instance of this B class but LSP still isn't violated because you cannot get the program into an inconsistent state with this; if you call B.foo through the interface of A, the program will just crash, but it is not the case that a variable that was declared as int now has a value of a different type. So, no type guarantee is violated.
But, python's static typing obviously doesn't have to follow type theory exactly, so I won't object to potential changes on this ground.
(I just object to OP's framing of this issue as mypy violating type theory. In type theory, the bottom type is definitely a subtype of all other types. You can advocate for deviating from this, but I don't think you can say that it's more theoretically grounded that way.)
if you call B.foo through the interface of A, the program will just crash, but it is not the case that a variable that was declared as int now has a value of a different type.
This is correct, but also not useful IMO. It is not different from passing in an object where foo is not defined at all, or has a different number of arguments. Both will result in an exception rather than a value of a different type. But preventing such exceptions is the primary reason to use a static type checker in python in the first place :-)
I agree that bottom type is by definition compatible with every other type. I think the OP's argument is that Never should be an "uninhabited type" rather than the bottom type, which are different in some theories, because making it bottom type introduces too much unsafety.
(I just object to OP's framing of this issue as mypy violating type theory. In type theory, the bottom type is definitely a subtype of all other types. You can advocate for deviating from this, but I don't think you can say that it's more theoretically grounded that way.)
In the set-theoretic model of typing which current formalization efforts are largely being built on top of, the bottom and top types don't participate in subtyping behavior. (At least in the way python type checkers are defining what a subtype is, see other posts that point out a reconciliation) Relations with these types are defined by other properties.
Now, I've linked a draft that still has a lot of imprecise wording and which there is still ongoing discussion about amending several sections to be more in line with theory and deviate from it less, but there are a lot of referenced research papers and published proofs linked within that, and you may find reading through some of the more recent research here and what more recent published proofs show to be correct may broaden your perspective.
In these models, the bottom type is uninhabitable and does not participate in subtyping behavior directly with static or gradual types, instead participating with a well-defined set of behaviors (that is not equivalent to subtyping for the top and bottom types) with the relation of type specifications, which are the sets of types that can be used where a static or gradual type is requested. This distinction is subtle but important. (Note that some papers have defined this as subtyping as well, but that these definitions do not match python's current behavior)
Outside of two things:
Any being subclassable. This one is reconcilable with the theories python is closest to currently by not treating any as the top type as a base class, but as a gradual type that shares the same name, but having a different symbolic meaning in this context.
Never participating in subtyping as current typecheckers are using the term. This one changes some fundamentals of those theories, and does not appear to be easy to reconcile.
Python's type system fully follows the set-theoretic model's definitions, specifically those built up in Abstracting Gradual Typing
If that doesn't change your perspective, I'd be interested to hear how you reconcile this, as well as the effects on LSP, as it could be illuminating for how we handle this going forward.
I think the OP's argument is that Never should be an "uninhabited type" rather than the bottom type, which are different in some theories, because making it bottom type introduces too much unsafety.
@eltoder See above, but no, the argument is that python actually follows the set-theoretic definitions for nearly everything else, and that it should for Never as well. (the set-theoretic ones have the bottom type as uninhabited, as you nodded to with "some theories")) Not doing so creates inconsistency, and creates a situation where established rules for safe-replacement do not work. (Note, This still is being discussed in the formalization happening in the background as well, there isn't good agreement on which definitions should be used yet anywhere, but there are issues we can show with treating Never as a type that participates in subtyping.)
As for the current behavior concretely violating LSP, @randolf-scholz raised this recently in the related conversation pertaining to intersections
One possible resolution: Behavioral LSP states that
(LSP-precondition): Preconditions cannot be strengthened in the subtype.
(LSP-postcondition): Postconditions cannot be weakened in the subtype.
For functions, the contra-variance of arguments and co-variance of return types can be equivalently described as a set of pre-conditions and post-conditions. In particular, the covariance of the return type of Callable[..., R] is equivalent to the post-condition isinstance(return_value, R).
However, when we try to substitute Never for R there is a problem: the equivalence to a post-condition is no longer true, since Never is supposed to be uninhabited (no instances of the type can exists). Therefore, the post-condition must fail. Indeed, the prior interpretation of Never as NoReturn means that the post-condition can actually never even be reached.
This suggests one could consider a modified subtyping rule for functions, which one may refer to:
(no-substitute-never) Callable[...., R] <: Callable[..., S] if and only if either R==S==Never or Never ≨ R <: S.
I.e. if S≠Never we assume subtyping includes the post-condition and if S=Never it doesn't. This is a weak version of (LSP-exception) that forbids to substitute a function with another function that unconditionally raises if the original didn't. It would make example ① void, and, consequently, the whole CarliJoy/intersection_examples#5 (comment). In particular, this would guarantee that B.getattribute("specific_key") is not allowed to raise unconditionally if the parent class didn't for "specific_key".
This makes an attempt to square the two, but notably, this creates a specific exception that reaches the same result as changing the general definition as argued here.
@mikeshardmind I think it is hard to argue "python actually follows the set-theoretic definitions for nearly everything". The typing PEPs are generally not precise enough, so mypy is used as a de facto interpretation of those PEPs. But mypy has over 2000 open issues and also includes behaviors that address style or practical concerns and are far from theory. I expect that if you examine the actual behavior of mypy in enough detail, you find a lot of places where it deviates from theory.
OTOH, the current definition of Never is used in a lot of programming languages[1], so it's fair to say at a minimum that there are arguments and research supporting this position.
I think it is hard to argue "python actually follows the set-theoretic definitions for nearly everything". The typing PEPs are generally not precise enough, so mypy is used as a de facto interpretation of those PEPs. But mypy has over 2000 open issues and also includes behaviors that address style or practical concerns and are far from theory. I expect that if you examine the actual behavior of mypy in enough detail, you find a lot of places where it deviates from theory.
OTOH, the current definition of Never is used in a lot of programming languages[1], so it's fair to say at a minimum that there are arguments and research supporting this position.
@eltoder This discussion in this thread is overflowing from over a month of exploring issues with a potential addition to the type system which is based on theory. I don't lightly bandy about that python mostly follows these definitions, this has been heavily discussed and led to a lot of discussion that ultimately needed to come here due to a poor interaction between how type checkers are currently interpreting Never and other assumptions people have about type safety.
I also think we would benefit from better definitions that don't lead to relying on "well, this is what type checkers are currently doing" to define what is correct, or the end result is "type checkers, including any errors in their implementation, are the source of truth, not the specified rules."
OTOH, the current definition of Never is used in a lot of programming languages[1], so it's fair to say at a minimum that there are arguments and research supporting this position.
Funnily enough, what you linked isn't quite making the argument you seem to think it is. For example, Haskell and Rust's definitions both match more closely to what is described in this issue than what type checkers are currently doing.
Haskell:
Attempting to evaluate such an expression causes the code to abort unrecoverable.
Rust:
In Rust, the bottom type is called the never type and is denoted by !. It is present in the type signature of functions guaranteed to never return, for example by calling panic!() or looping forever. It is also the type of certain control-flow keywords, such as break and return, which do not produce a value but are nonetheless usable as expressions
Rust and Haskell do not allow the bottom type where python type checkers currently do, only allowing it where there is no value, and correctly treating reaching code that has a type of Never to be an error.
@DiscordLiz gave a good explanation above for how easy it would be for someone without the type theory background to make the incorrect leap that many have made and why.
Additionally, When comparing TypeScript's use of Intersections, with what is being proposed for python, it was found that typescript has an arbitrary undocumented sorting algorithm that has an impact on the outcome of intersections. Should we conclude that intersections must have this feature because another language did this? Just because another language does something does not mean that that something has had the same considerations for use that would be appropriate for other use.
@mikeshardmind just a slight clarification for anyone confused, Haskell allows specifying such code but treats the use of it as and impossible to recover from error. This is strictly as a mathematical outcome that could arise due to composition of functions, and not as an intent to allow such code to exist or be used. You are still correct that this is not treating Never as a subtype but as the absence of a valid type.
I think it is hard to argue "python actually follows the set-theoretic definitions for nearly everything".
Hopefully mniip doesn't mind this being shared here to make the point that this is possible, but... It's possible to create a program to actually check this by encoding the rules of a specific model of working with types into a formal proof engine and comparing it to what is currently the "accepted consensus behavior" since you are arguing that the PEPs aren't precise. I similarly share the above opinion that the imprecision in PEPs meant to specify is a problem.
Coq formalization of "Gradual Typing with Union and Intersection Types" (https://www.irif.fr/~gc/papers/icfp17.pdf)
RequireImport Coq.Lists.List.
RequireImport Coq.Bool.Bool.
RequireImport Coq.Relations.Relations.
RequireImport Coq.Compat.AdmitAxiom.
Import ListNotations.
Infix "<$>" := map (at level 65, left associativity).
Notation "k >>= f" := (flat_map f k) (at level 66, left associativity).
Definition allb {A} (f : A -> bool) (xs : list A) : bool :=
fold_right andb true (map f xs).
Definition anyb {A} (f : A -> bool) (xs : list A) : bool :=
fold_right orb false (map f xs).
Definition apList {A B} (fs : list (A -> B)) (xs : list A) : list B :=
fs >>= fun f => f <$> xs.
Infix "<*>" := apList (at level 65, left associativity).
Definition null {A} (xs : list A) : bool :=
match xs with
| [] => true
| _ => false
end.
(* Subtyping decision procedure for base types. We parameterize over it here. *)Class SubtypeDecidable (BaseType : Type) : Type :=
{ bsubDecide : list BaseType -> list BaseType -> bool
(* `bsubDecide xs ys` is whether the intersection of xs lies within the union of ys *)
; BSub := fun t s => bsubDecide [t] [s] = true
; bsub_refl : reflexive _ BSub
; bsub_trans : transitive _ BSub
}.
SectionTypes.
Context {BaseType : Type} `{SubtypeDecidable BaseType}.
Inductive SType : Type :=
| SBottom : SType
| STop : SType
| SNot : SType -> SType
| SArrow : SType -> SType -> SType
| SBase : BaseType -> SType
| SAnd : SType -> SType -> SType
| SOr : SType -> SType -> SType.
Inductive GType : Type :=
| GBottom : GType
| GTop : GType
| GAny : GType
| GNot : SType -> GType
| GArrow : GType -> GType -> GType
| GBase : BaseType -> GType
| GAnd : GType -> GType -> GType
| GOr : GType -> GType -> GType.
DeclareScope stype_scope.
DelimitScope stype_scope with stype.
BindScope stype_scope with SType.
Notation "𝟘" := SBottom : stype_scope.
Notation "𝟙" := STop : stype_scope.
Notation "¬ t" := (SNot t) (at level 75) : stype_scope.
Infix "→" := SArrow (at level 99, right associativity) : stype_scope.
Infix "∧" := SAnd (at level 85, right associativity) : stype_scope.
Infix "∨" := SOr (at level 85, right associativity) : stype_scope.
Notation "⋀ xs" := (fold_right SAnd STop xs) (at level 85) : stype_scope.
Notation "⋁ xs" := (fold_right SOr SBottom xs) (at level 85) : stype_scope.
DeclareScope gtype_scope.
DelimitScope gtype_scope with gtype.
BindScope gtype_scope with GType.
Notation "𝟘" := GBottom : gtype_scope.
Notation "𝟙" := GTop : gtype_scope.
Notation "?" := GAny : gtype_scope.
Notation "¬ t" := (GNot t) (at level 75) : gtype_scope.
Infix "→" := GArrow (at level 99, right associativity) : gtype_scope.
Infix "∧" := GAnd (at level 85, right associativity) : gtype_scope.
Infix "∨" := GOr (at level 85, right associativity) : gtype_scope.
Notation "⋀ xs" := (fold_right GAnd GTop xs) (at level 85) : gtype_scope.
Notation "⋁ xs" := (fold_right GOr GBottom xs) (at level 85) : gtype_scope.
ReservedInfix "≤" (at level 70, no associativity).
Inductive Sub : SType -> SType -> Prop :=
| sub_base : forall b c, BSub b c -> SBase b ≤ SBase c
| sub_not_mono : forall t s, s ≤ t -> (¬t) ≤ (¬s)
| sub_arrow_mono : forall t1 t2 s1 s2, s1 ≤ t1 -> t2 ≤ s2 -> (t1 → t2) ≤ (s1 → s2)
| sub_bottom : forall t, 𝟘 ≤ t
| sub_top : forall t, t ≤ 𝟙
| sub_and_l : forall t1 t2, (t1 ∧ t2) ≤ t1
| sub_and_r : forall t1 t2, (t1 ∧ t2) ≤ t2
| sub_and : forall t s1 s2, t ≤ s1 -> t ≤ s2 -> t ≤ (s1 ∧ s2)
| sub_or_l : forall t1 t2, t1 ≤ (t1 ∨ t2)
| sub_or_r : forall t1 t2, t2 ≤ (t1 ∨ t2)
| sub_or : forall t1 t2 s, t1 ≤ s -> t2 ≤ s -> (t1 ∨ t2) ≤ s
| sub_trans : forall t s r, t ≤ s -> s ≤ r -> t ≤ r
where "t1 ≤ t2" := (Sub t1 t2).
Section SubDecide.
(* Either conjuncts or disjuncts depending on context, categorized by whetherit's a BaseType or an arrow, and by whether it's negated *)Record Junct := mkJunct
{ bases : list BaseType
; arrows : list (SType * SType)
; notBases : list BaseType
; notArrows : list (SType * SType)
}.
Definition unitJunct : Junct :=
{| bases := []
; arrows := []
; notBases := []
; notArrows := []
|}.
Definition mergeJuncts (j1 j2 : Junct) : Junct :=
{| bases := bases j1 ++ bases j2
; arrows := arrows j1 ++ arrows j2
; notBases := notBases j1 ++ notBases j2
; notArrows := notArrows j1 ++ notArrows j2
|}.
Definition invertJunct (j : Junct) : Junct :=
{| bases := notBases j
; arrows := notArrows j
; notBases := bases j
; notArrows := notArrows j
|}.
Fixpoint udnf (t : SType) : list Junct :=
match t with
| SBase b => [{| bases := [b]; arrows := []; notBases := []; notArrows := [] |}]
| t1 → t2 => [{| bases := []; arrows := [(t1, t2)]; notBases := []; notArrows := [] |}]
| 𝟘 => []
| 𝟙 => [unitJunct]
| ¬t => invertJunct <$> ucnf t
| t1 ∨ t2 => udnf t1 ++ udnf t2
| t1 ∧ t2 => mergeJuncts <$> udnf t1 <*> udnf t2
end%stype
with ucnf (t : SType) : list Junct :=
match t with
| SBase b => [{| bases := [b]; arrows := []; notBases := []; notArrows := [] |}]
| t1 → t2 => [{| bases := []; arrows := [(t1, t2)]; notBases := []; notArrows := [] |}]
| 𝟘 => [unitJunct]
| 𝟙 => []
| ¬t => invertJunct <$> udnf t
| t1 ∧ t2 => ucnf t1 ++ ucnf t2
| t1 ∨ t2 => mergeJuncts <$> ucnf t1 <*> ucnf t2
end%stype.
Definition junctDecide (jt js : Junct) : bool :=
match bases jt ++ notBases js, arrows jt ++ notArrows js with
| lbases, [] => bsubDecide lbases (bases js ++ notBases jt)
| [], _ => match proof_admitted with(* How to decide subtyping of a bunch of arrows? Not sure. *)end
| _, _ => match proof_admitted with(* How to decide whether base types intersect arrow types? This depends on the target language in some way. *)endend.
Definition subDecide (t s : SType) : bool :=
allb id (junctDecide <$> udnf t <*> ucnf s).
End SubDecide.
Infix "≤!" := subDecide (at level 70, no associativity).
Notation "t ∈ S" := (S t) (at level 70, only parsing).
Fixpoint γ (τ : GType) : SType -> Prop :=
match τ with
| ? => fun _ => True
| 𝟘 => eq 𝟘%stype
| 𝟙 => eq 𝟙%stype
| GBase b => eq (SBase b)
| ¬t => eq (¬t)%stype
| τ1 ∧ τ2 => fun t => match t with
| t1 ∧ t2 => t1 ∈ γ τ1 /\ t2 ∈ γ τ2
| _ => False
end%stype
| τ1 ∨ τ2 => fun t => match t with
| t1 ∨ t2 => t1 ∈ γ τ1 /\ t2 ∈ γ τ2
| _ => False
end%stype
| τ1 → τ2 => fun t => match t with
| t1 → t2 => t1 ∈ γ τ1 /\ t2 ∈ γ τ2
| _ => False
end%stype
end%gtype.
Definition lift2 (P : SType -> SType -> Prop) : GType -> GType -> Prop
:= fun τ1 τ2 => exists t1 t2, t1 ∈ γ τ1 /\ t2 ∈ γ τ2 /\ P t1 t2.
Fixpoint gradualMinimum (τ : GType) : SType :=
match τ with
| ? => 𝟘%stype
| 𝟘 => 𝟘%stype
| 𝟙 => 𝟙%stype
| GBase b => SBase b
| ¬t => (¬t)%stype
| τ1 ∧ τ2 => (gradualMinimum τ1 ∧ gradualMinimum τ2)%stype
| τ1 ∨ τ2 => (gradualMinimum τ1 ∨ gradualMinimum τ2)%stype
| τ1 → τ2 => (gradualMaximum τ1 → gradualMinimum τ2)%stype
end%gtype
with gradualMaximum (τ : GType) : SType :=
match τ with
| ? => 𝟙%stype
| 𝟘 => 𝟘%stype
| 𝟙 => 𝟙%stype
| GBase b => SBase b
| ¬t => (¬t)%stype
| τ1 ∧ τ2 => (gradualMaximum τ1 ∧ gradualMaximum τ2)%stype
| τ1 ∨ τ2 => (gradualMaximum τ1 ∨ gradualMaximum τ2)%stype
| τ1 → τ2 => (gradualMinimum τ1 → gradualMaximum τ2)%stype
end%gtype.
Notation "τ ⇓" := (gradualMinimum τ) (at level 65).
Notation "τ ⇑" := (gradualMaximum τ) (at level 65).
Infix "̃≤" := (lift2 Sub) (at level 70, no associativity).
Definition consSubDecide (σ τ : GType) : bool := σ⇓ ≤! τ⇑.
Infix "̃≤!" := consSubDecide (at level 70, no associativity).
Infix "̃≰" := (lift2 (fun s t => ~(s ≤ t))) (at level 70, no associativity).
Definition consNotSubDecide (σ τ : GType) : bool := negb (σ⇑ ≤! τ⇓).
Infix "̃≰!" := consNotSubDecide (at level 70, no associativity).
(* ??? The paper completely glances over that it treats SType as a subset ofGType in the definition of γA. γA+ restricted to SType is γApos' here. *)Fixpoint stype2gtype (t : SType) : GType :=
match t with
| 𝟘 => 𝟘%gtype
| 𝟙 => 𝟙%gtype
| ¬t => (¬t)%gtype
| t1 → t2 => (stype2gtype t1 → stype2gtype t2)%gtype
| SBase b => GBase b
| t1 ∧ t2 => (stype2gtype t1 ∧ stype2gtype t2)%gtype
| t1 ∨ t2 => (stype2gtype t1 ∨ stype2gtype t2)%gtype
end%stype.
Fixpoint γAneg (t : SType) : list (list (GType * GType)) :=
match t with
| t1 ∨ t2 => (fun T1 T2 => T1 ++ T2) <$> γAneg t1 <*> γAneg t2
| t1 ∧ t2 => γAneg t1 ++ γAneg t2
| _ → _ => [[]]
| ¬t => γApos' t
| 𝟘 => [[]]
| 𝟙 => []
| SBase _ => [[]]
end%stype
with γApos' (t : SType) : list (list (GType * GType)) :=
match t with
| t1 ∨ t2 => γApos' t1 ++ γApos' t2
| t1 ∧ t2 => (fun T1 T2 => T1 ++ T2) <$> γApos' t1 <*> γApos' t2
| t1 → t2 => [[(stype2gtype t1, stype2gtype t2)]]
| ¬t => γAneg t
| 𝟘 => []
| 𝟙 => [[]]
| SBase _ => [[]]
end%stype.
Fixpoint γApos (τ : GType) : list (list (GType * GType)) :=
match τ with
| τ1 ∨ τ2 => γApos τ1 ++ γApos τ2
| τ1 ∧ τ2 => (fun T1 T2 => T1 ++ T2) <$> γApos τ1 <*> γApos τ2
| τ1 → τ2 => [[(τ1, τ2)]]
| ¬t => γAneg t
| 𝟘 => []
| 𝟙 => [[]]
| GBase _ => [[]]
| ? => [[(?, ?)]]
end%gtype.
Definition dom (τ : GType) : SType :=
⋀ (fun S => ⋁ (fun '(ρ, _) => ρ⇑) <$> S)%stype <$> γApos τ.
Fixpoint assignments {X : Type} (xs : list X) : list (list (X * bool)) :=
match xs with
| [] => [[]]
| (x :: xs) => cons <$> [(x, false); (x, true)] <*> assignments xs
end.
Definition partitions {X : Type} (xs : list X) : list (list X * list X) :=
(fun ys => (fst <$> filter snd ys, fst <$> filter (fun p => negb (snd p)) ys))
<$> assignments xs.
Definition appResult (τ σ : GType) : GType := ⋁ (fun S =>
⋁ (fun '(Q, Qbar) => ⋀ snd <$> Qbar) <$> filter
(fun '(Q, Qbar) => negb (null Qbar) && (σ ̃≰! ⋁ fst <$> Q)
&& negb ((σ⇑ ∧ ⋁ (fun '(ρ, _) => ρ⇑) <$> Qbar) ≤! 𝟘))
(partitions S)
)%gtype <$> γApos τ.
Infix "∘" := appResult (at level 90, no associativity).
Section SomeTheorems.
LocalTheorem sub_and_mono t1 t2 s1 s2 : t1 ≤ s1 -> t2 ≤ s2 -> (t1 ∧ t2) ≤ (s1 ∧ s2).
Proof.
intros p q.
apply sub_and.
- refine (sub_trans _ _ _ _ p).
apply sub_and_l.
- refine (sub_trans _ _ _ _ q).
apply sub_and_r.
Qed.
LocalTheorem sub_or_mono t1 t2 s1 s2 : t1 ≤ s1 -> t2 ≤ s2 -> (t1 ∨ t2) ≤ (s1 ∨ s2).
Proof.
intros p q.
apply sub_or.
- refine (sub_trans _ _ _ p _).
apply sub_or_l.
- refine (sub_trans _ _ _ q _).
apply sub_or_r.
Qed.
LocalTheorem sub_refl t : t ≤ t.
Proof.
pose proof sub_and_mono.
pose proof sub_or_mono.
pose proof bsub_refl.
induction t; auto; now constructor.
Qed.
LocalTheorem gradual_extrema_in_concretization τ : τ⇓ ∈ γ τ /\ τ⇑ ∈ γ τ.
Proof.
induction τ as [ | | | | ? [] ? [] | | ? [] ? [] | ? [] ? [] ]; simpl; auto.
Qed.
LocalTheorem gradual_extrema_bounds τ : forall t, t ∈ γ τ -> τ⇓ ≤ t /\ t ≤ τ⇑.
Proof.
induction τ as [ | | | | ? IHl ? IHr | | ? IHl ? IHr | ? IHl ? IHr ]; simpl.
- intros _ <-. repeat constructor.
- intros _ <-. repeat constructor.
- repeat constructor.
- intros _ <-. repeat constructor.
+ apply sub_refl.
+ apply sub_refl.
- intros [ | | | t1 t2 | | | ]; try contradiction.
intros [].
destruct (IHl t1); auto.
destruct (IHr t2); auto.
repeat constructor; auto.
- intros _ <-. repeat constructor.
+ apply bsub_refl.
+ apply bsub_refl.
- intros [ | | | | | t1 t2 | ]; try contradiction.
intros [].
destruct (IHl t1); auto.
destruct (IHr t2); auto.
split.
+ apply sub_and_mono; auto.
+ apply sub_and_mono; auto.
- intros [ | | | | | | t1 t2 ]; try contradiction.
intros [].
destruct (IHl t1); auto.
destruct (IHr t2); auto.
split.
+ apply sub_or_mono; auto.
+ apply sub_or_mono; auto.
Qed.
LocalTheorem cons_sub_reduction σ τ : σ ̃≤ τ <-> σ⇓ ≤ τ⇑.
Proof.
unfold lift2. split.
- intros [s [t [? []]]].
apply (sub_trans _ s _).
+ now apply gradual_extrema_bounds.
+ apply (sub_trans _ t _).
* assumption.
* now apply gradual_extrema_bounds.
- intros ?.
exists (σ⇓), (τ⇑).
split; try split.
+ apply gradual_extrema_in_concretization.
+ apply gradual_extrema_in_concretization.
+ assumption.
Qed.
Theorem sub_decide_agrees t s : t ≤ s <-> t ≤! s = true.
(* Depends on the contents of junctDecide *)Admitted.
Theorem cons_sub_decide_agrees σ τ : σ ̃≤ τ <-> σ ̃≤! τ = true.
Proof.
transitivity (σ⇓ ≤ τ⇑).
- apply cons_sub_reduction.
- unfold consSubDecide.
apply sub_decide_agrees.
Qed.
Theorem cons_not_sub_reduction σ τ : σ ̃≰ τ <-> ~(σ⇑ ≤ τ⇓).
Proof.
unfold lift2. split.
- intros [s [t [? [? p]]]] n.
apply p.
apply (sub_trans _ (σ⇑) _).
+ now apply gradual_extrema_bounds.
+ apply (sub_trans _ (τ⇓) _).
* assumption.
* now apply gradual_extrema_bounds.
- intros n.
exists (σ⇑), (τ⇓).
split; try split.
+ apply gradual_extrema_in_concretization.
+ apply gradual_extrema_in_concretization.
+ assumption.
Qed.
Theorem cons_not_sub_decide_agrees σ τ : σ ̃≰ τ <-> σ ̃≰! τ = true.
Proof.
transitivity (~(σ⇑ ≤ τ⇓)).
- apply cons_not_sub_reduction.
- unfold consNotSubDecide.
transitivity (σ⇑ ≤! τ⇓ <> true).
+ apply not_iff_compat.
apply sub_decide_agrees.
+ transitivity (σ⇑ ≤! τ⇓ = false).
* apply not_true_iff_false.
* symmetry. apply negb_true_iff.
Qed.
End SomeTheorems.
Section SomeContradictions.
Inductive PartialEvalResult : Type :=
| EvBottom
| EvUnknown
| EvTop.
LocalFixpoint partialEval (t : SType) : PartialEvalResult :=
match t with
| 𝟘 => EvBottom
| 𝟙 => EvTop
| SBase _ => EvUnknown
| _ → _ => EvUnknown
| ¬t => match partialEval t with
| EvBottom => EvTop
| EvUnknown => EvUnknown
| EvTop => EvBottom
end
| t1 ∧ t2 => match partialEval t1, partialEval t2 with
| EvBottom, _ => EvBottom
| _, EvBottom => EvBottom
| EvUnknown, _ => EvUnknown
| _, EvUnknown => EvUnknown
| _, _ => EvTop
end
| t1 ∨ t2 => match partialEval t1, partialEval t2 with
| EvTop, _ => EvTop
| _, EvTop => EvTop
| EvUnknown, _ => EvUnknown
| _, EvUnknown => EvUnknown
| _, _ => EvBottom
endend%stype.
LocalTheorem partial_eval_mono t s :
t ≤ s -> match partialEval t, partialEval s with
| EvBottom, _ => True
| _, EvTop => True
| EvUnknown, EvBottom => False
| EvUnknown, _ => True
| EvTop, _ => False
end.
Proof.
intros p.
induction p.
all: repeat first [ progress (simpl; auto) | destruct (partialEval _) ].
Qed.
LocalTheorem top_nle_bottom : ~(𝟙 ≤ 𝟘).
Proof.
intros n. apply (partial_eval_mono _ _ n).
Qed.
Theorem cons_sub_nontrans : ~(forall g h k, g ̃≤ h -> h ̃≤ k -> g ̃≤ k).
Proof.
intros n.
enough (p : 𝟙 ̃≤ 𝟘).
- apply top_nle_bottom.
unfold lift2 in p. simpl in p.
now destruct p as [? [? [-> [->]]]].
- apply (n _ ?%gtype _).
+ unfold lift2. simpl.
exists 𝟙%stype, 𝟙%stype.
split; auto. split; auto.
constructor.
+ unfold lift2. simpl.
exists 𝟘%stype, 𝟘%stype.
split; auto. split; auto.
constructor.
Qed.
End SomeContradictions.
EndTypes.
(* Have to redeclare all notations now that the section is closed *)DeclareScope stype_scope.
DelimitScope stype_scope with stype.
BindScope stype_scope with SType.
Notation "𝟘" := SBottom : stype_scope.
Notation "𝟙" := STop : stype_scope.
Notation "¬ t" := (SNot t) (at level 75) : stype_scope.
Infix "→" := SArrow (at level 99, right associativity) : stype_scope.
Infix "∧" := SAnd (at level 85, right associativity) : stype_scope.
Infix "∨" := SOr (at level 85, right associativity) : stype_scope.
Notation "⋀ xs" := (fold_right SAnd STop xs) (at level 85) : stype_scope.
Notation "⋁ xs" := (fold_right SOr SBottom xs) (at level 85) : stype_scope.
DeclareScope gtype_scope.
DelimitScope gtype_scope with gtype.
BindScope gtype_scope with GType.
Notation "𝟘" := GBottom : gtype_scope.
Notation "𝟙" := GTop : gtype_scope.
Notation "?" := GAny : gtype_scope.
Notation "¬ t" := (GNot t) (at level 75) : gtype_scope.
Infix "→" := GArrow (at level 99, right associativity) : gtype_scope.
Infix "∧" := GAnd (at level 85, right associativity) : gtype_scope.
Infix "∨" := GOr (at level 85, right associativity) : gtype_scope.
Notation "⋀ xs" := (fold_right GAnd GTop xs) (at level 85) : gtype_scope.
Notation "⋁ xs" := (fold_right GOr GBottom xs) (at level 85) : gtype_scope.
Infix "≤" := Sub (at level 70, no associativity).
Infix "≤!" := subDecide (at level 70, no associativity).
Notation "τ ⇓" := (gradualMinimum τ) (at level 65).
Notation "τ ⇑" := (gradualMaximum τ) (at level 65).
Infix "̃≤" := (lift2 Sub) (at level 70, no associativity).
Infix "̃≤!" := consSubDecide (at level 70, no associativity).
Infix "̃≰" := (lift2 (fun s t => ~(s ≤ t))) (at level 70, no associativity).
Infix "̃≰!" := consNotSubDecide (at level 70, no associativity).
Infix "∘" := appResult (at level 90, no associativity).
SectionExample.
Inductive BaseType :=
| object
| int
| str
| bytes
| float.
SchemeEqualityfor BaseType.
Definition SBase' := @SBase BaseType.
Coercion SBase' : BaseType >-> SType.
Definition GBase' := @GBase BaseType.
Coercion GBase' : BaseType >-> GType.
Definition decideSubclass (b c : BaseType) : bool :=
BaseType_beq b c || match b, c with
| _, object => true
| _, _ => false
end.
ProgramInstance subtype_decidable_basetype : SubtypeDecidable BaseType :=
{| bsubDecide := fun conjs disjs =>
anyb id (decideSubclass <$> conjs <*> disjs)
|| anyb (fun c => match c with object => true | _ => false end) disjs
|| (anyb (fun c => match c with int => true | _ => false end) conjs
&& anyb (fun c => match c with str => true | _ => false end) conjs)
|}.
NextObligation.
unfold reflexive.
intros []; simpl; auto.
Qed.
NextObligation.
unfold transitive, anyb.
intros b c d.
destruct b, d; simpl; auto; destruct c; simpl; auto.
Qed.
Eval cbn in (int → float) ∧ (str → bytes) ∘ int.
(* = (((float ∧ bytes ∧ 𝟙) ∨ (float ∧ 𝟙) ∨ 𝟘) ∨ 𝟘)%gtype : GType*)EndExample.
Note: This doesn't contradict what was said about the set-theoretic view not allowing this despite the subtyping relation, The rules proposed in this paper and encoded in the coq program there treat the bottom type not as participating in subtyping as most people are aware of the term, but redefine subtyping more generally in such a way that it does apply.
The very first line of that page: states: "You can put it anywhere and it will compile. When evaluated, it throws an exception "undefined". But thanks to laziness you can put it anywhere you've not written yet:" This is not the same as type checkers allowing this and claiming it to be safe, in fact, this is haskell specifically telling you that use of it isn't safe.
A similar example works in Rust:
use std::process;fntest(x:u32) -> u32{
x
}fnmain(){#[allow(unreachable_code)]test(process::exit(1));}
You have to allow unreachable code, but this is not a type error.
This isn't an example of it being a value, Please read again about the difference between a value and a lack of a value, it matters. On top of this, Rust correctly detects unreachable code and you are opting out of the safety it provides visibly here.
This example works in Scala, Kotlin, TypeScript and probably others (with respective syntax changes):
@mikeshardmind nudged me to put this comment separately rather than in a collapsible section over in discord, but what definition of "subtyping" is used matters here too. The set-theoretic model can be (see the proof above) reconciled with a general type connective which the paper it was proved in defines as their version of subtyping, but this use isn't consistent with what current type checkers are allowing. (And indeed the paper takes the time to lay out how prior definitions of subtyping are lacking)
We have a very complex issue here where there is lots of good well proven theory, and no good definitions that are commonly accepted in python to actually communicate the issue due to lack of specification in PEPs.
Never indicates a complete lack of a value, and is a type can't exist at runtime.
The example below is clearly broken. Mypy allows it full-stop, pyright actually complains about overriding foo this way.
fromtypingimportNever, reveal_typeclassA:
@propertydeffoo(self) ->int:
return1classB:
@propertydeffoo(self) ->str:
return"okay"classAB(A, B):
foo: Never# mypy allows thisdeftakes_a(x: A) ->bytes:
returnx.foo.to_bytes(8)
deftakes_b(x: B) ->bytes:
returnx.foo.encode()
if__name__=="__main__":
obj=AB()
reveal_type(AB().foo) # Revealed type is "<nothing>" (pyright "Never", both wrong) print(obj.foo)
print(takes_a(obj)) # This one works because A is first in MRO, but we can't even just isinstance check, it's an instance of A and Bprint(takes_b(obj)) # This one fails for the same reason
As described above, and clearly demonstrated with the toy example here, Never isn't consistent with other types for the purposes of safe replacement, and treating it as such not only allows nonsensical subclasses, but also breaks expectations of checked code in terms of what may be passed to it. While there are definitions of subtyping that would apply between Never and other types, they exclude this broken behavior.
Any code relying on this behavior is fundamentally broken, and I don't think this requires a "Breaking change" or transitionary period to fix as
All uses which would be "Broken" by fixing this already are broken and this would only highlight those issues.
This wasn't officially specified anywhere. This was a decision type checkers made without a corresponding specification.
Pyright's errors via pylance in VSC with strict:
Mypy's output with --strict (Showing the lack of error isn't just a settings issue) via mypy playground on latest:
main.py:28: note: Revealed type is "<nothing>"
Success: no issues found in 1 source file
A more dangerous example would involve the return types both working for takes_a and takes_b purely by implementation accident, but returning different types than expected polluting where the type issues even came from.
Now if anyone can argue that it should be allowed and keep in mind the effects on library code taking in user-provided classes with this information and impact demonstrated, I'd love to hear the argument, because as it stands it sounds like the only argument against it is "Well that's not what we've been doing it and changing it might be hard" (Appeal to tradition or status quo) or "other language does this" (Appeal to authority) even though clearly there is a detectable issue here.
My preferred resolution on this involves clearly stating that Never isn't consistent with other types (officially somewhere) and that Never remains fine for things that truly don't return a value of any type, but you can't specify a function, class, or other annotation having a dependence on Never without it specifically indicating erroneous or unreachable code of some sort.
You state that with conviction, but that isn't how Never has been understood in the past by the Python typing community. There may or may not be good reasons to change its meaning in the Python type system. None of the reasons you've presented so far seem very compelling to me, but I'm trying to remain open-minded. Such a redefinition will likely have backward-compatibility implications, so it would need to be well motivated. Citing an academic paper on type theory will probably be insufficient to sway people. I personally enjoy geeking out about type theory, but pragmatism tends to trump theory in the Python community. There are other programming languages where "purity of theory" is valued much more highly (Haskell comes to mind), but Python tends to be further on the "pragmatism" side of that spectrum.
If you want to argue in favor of a change to the Python type system, a more effective approach is to demonstrate that such a change would solve some real problem that Python developers are facing today. What is the problem you're trying to solve? How prevalent is the problem? Do we have evidence to back this up (e.g. bug reports or feature requests in the mypy issue tracker or StackOverflow posts)?
pyright actually complains about overriding foo this way
Pyright is not complaining about the Never type. It's complaining about the fact that you're overriding a property with a variable. It will emit this regardless of which type you use in the override. Mypy is more lax in this case and allows properties to be overridden by variables. So this has nothing to do with Never.
And the actual output [shows a runtime crash]
The crash is because the variable foo was never assigned a value in class AB. This can happen with any class-scoped variable regardless of its type. This is not specific to Never.
Consider the following modified example. This also type checks without error in both mypy and pyright but crashes at runtime. There is no Never involved in this example, but it is otherwise completely analogous to your code above.
I think your example demonstrates that there are bugs that can go uncaught by static type checking. That's something that no one would dispute. It doesn't demonstrate why Never should be treated differently from other types.
@erictraut Replacing a non-Never annotated object with a Never annotated object violates certain aspects of LSP, specifically (LSP-exception)
(LSP-exception) New exceptions cannot be thrown by the methods in the subtype, except if they are subtypes of exceptions thrown by the methods of the supertype.
Imo, the main issue here is uncertainty. Since it is not explicitly codified, it is unclear what contract a type annotation like
classFoo:
bar: int
really promises. Most people would probably say that it guarantees that instances of Foo are guaranteed to have an attribute bar which is an instance of int.
But clearly, if a subclass SubFoo is allowed to substitute bar with Never, then (LSP-exception) is violated, since looking up said attribute never terminates or raises an exception. Therefore, SubFoo cannot safely be used as a substitute for Foo without wrapping everything in try-except blocks.
The Python community should decide whether they want the typing system to support (LSP-exception), or a weaker version of it, like the one I proposed in CarliJoy/intersection_examples#5 (comment), and clearly communicate this decision.
The crash is because the variable foo was never assigned a value in class AB. This can happen with any class-scoped variable regardless of its type. This is not specific to Never.
No, this misunderstands the example here. Simply annotating Never without replacing the inherited methods/properties is accepted, making the annotation of Never incorrect. The crash isn't because the attribute doesn't exist, and you can see in the traceback exactly what happened.
Did you look at my modified example? Try running it. My version produces exactly the same stack trace and error message but doesn't involve Never. I don't see how the two are any different, yet my version doesn't involve Never.
@erictraut Your modified example also involves annotating something incorrectly. This is detectable and isn't being detected.
The situation with Never matters here even if this issue of detection is resolved. You've also fundamentally sidestepped the underpinning question by turning that into a protocol. If there are two incompatible types, it shouldn't be possible to subclass both by simply placing a Never there.
It doesn't demonstrate why Never should be treated differently from other types.
Because it isn't a type in the same sense that int is. @DiscordLizalready explained how neither Any nor Never are singular types up above pretending Never is a singular type rather than the bottom type, (ie. the empty set of types or any other reasonable interpretation of what a bottom type is in a type system) is how we got here.
Because any code relying on the existence of an object with a type of Never at runtime is already broken. Fixing this can't break anything, only inform people they are already broken.
The feature added at the same time, as Never, assert_never, seems to be written correctly understanding that if you reach a point where you have an expectation of a type only being Never, you have unreachable code.
If you want to argue in favor of a change to the Python type system, a more effective approach is to demonstrate that such a change would solve some real problem that Python developers are facing today. What is the problem you're trying to solve? How prevalent is the problem? Do we have evidence to back this up (e.g. bug reports or feature requests in the mypy issue tracker or StackOverflow posts)?
But more to the point, where is it specified that Never is a subtype of and a suitable replacement for all other types? As far as I can ascertain, this is just a decision that type checkers made without it ever being specified and with a lack of understanding of what is correct from the point of view of theory. While it is very understandable how such a lack of understanding or misconception could occur, that's part of why these things should be specified and that the specification should happen in the open* not "oh, we implemented it this way, and we don't have a specification for it, guess you're stuck with it".
The issue it solves to have a correct specification is that future additions to the specification are building on a solid foundation not needing mountains of exceptions to rules because of an accumulation of errors.
Intersections, Not, and Stricter TypeGuards (Which use both intersections and Not in describing their resulting equivalence) are impossible to have a coherent set of rules and behaviors if Never is treated as a type, rather than an (empty) set of types. That's how this discussion came here, realizing that type checkers are allowing something that fundamentally breaks what is being worked on.
* And for the record, the typing-sig mailing list is the least visible place such a discussion could occur. Even the issue trackers of individual type checkers see more users regularly, and those do not have the barrier to entry of waiting for the mailing list administrator to manually review posts from new users which delays feedback if its even seen to begin with. Mailing lists are atrocious for modern-day collaborative discussion by comparison to other tools at the disposal of the community. (They still have a very clear place for announcements)
Your modified example also involves annotating something incorrectly.
Can you elaborate? What is annotated incorrectly in my example?
I agree that there's a bug in my example, but I don't think it involves an incorrect annotation. The bug is that AB.foo is not assigned a value that conforms with its annotation, so the underlying value of A.foo is leaking through at runtime. Would it be possible for a static type checker to detect this condition? Perhaps, but such a check would also produce many false positives for correctly-written Python code. That's why Python type checkers do not currently check for this case. It would simply be too noisy and wouldn't catch many real-world bugs.
Let's assume that a type checker could reasonably enforce that a declared class variable must be assigned a value within the class' implementation. Your original example and my example would both trigger that error. In my example, I could fix that error by assigning a value to AB.foo that conforms to the _SupportsEncodeAndToBytes protocol. In your example, any attempt to address that error by assigning a value would result in a different type error because it's impossible to assign a value that conforms to Never or a value that subclasses from both int and str.
So I assert once again that your example does not demonstrate why Never should be treated differently from other types. You may be able to produce other examples that support your position, but this example does not, at least as I see it.
Intersections, Not, and Stricter TypeGuards ... are impossible to have a coherent set of rules and behaviors if Never is treated as a type.
I'll once again note that TypeScript is an example of a popular programming language that supports gradual typing, intersections, and strict type guards, and it treats Never the same way that Python does today. (TypeScript doesn't support negated types, but I'm not aware of any popular programming language that does.) You've said that you perceive TypeScript to be "incorrect" from a type theory perspective. I personally know the developers responsible for TypeScript, and they are both very knowledgable about type theory and very pragmatic when it comes to prioritizing usability over purity. I admit that I'm not familiar with your background or credentials, but I think I'm safe in assuming that you have less experience than Anders Hejlsberg in developing programming languages and type systems 😀. I'm not saying that your viewpoint is wrong, but I would caution you against dismissing TypeScript as an unworthy exemplar.
TypeScript isn't alone in treating Never as the subtype of (and therefore assignable to) all other types. Wikipedia and many other sources define "bottom type" as the subtype of all other types in a type system. You and @DiscordLiz have asserted that wikipedia is wrong or that it's relying a different definition of subtype. You've pointed to an academic paper on gradual typing (published several years after the Python type system was created) that indicates that the "bottom type" should be treated as though it's outside normal subtyping rules in a type system. That doesn't appear to be a universally-held opinion, yet you keep asserting it as though it's an indisputable fact.
I appreciate the perspective you bring to this discussion, but I don't think you've made a clear and convincing case that we should make a change to the type system that results in a breaking change.
I agree with you that there is value in formalizing the Python type specification. As you point out, this is an important foundation upon which any major new typing features should be built. Ideally, this specification should be developed in an open and collaborative manner so it has buy-in from the broader typing community, and it should employ terminology that is clearly defined and used consistently throughout the spec. (In the discussions about intersections, I've noted that new terms are being injected into the conversation with the assumption that everyone has a common understanding of terms like uninhabited type, static type, gradual type, etc., and this is leading to confusion.) I also think it's important for this formalization to be done holistically, not piecemeal. If it's done piecemeal, it likely won't hold together, and inconsistencies will creep in.
As @DiscordLiz mentioned at the top of this thread, Kevin Millikin started an effort to produce a formalization. That effort appears to have stalled. You've stated that there are some aspects of this earlier document that you disagree with, and there are other aspects that require refinement, clarification, additional review, and input from others. Perhaps you'd like to pick up the mantle and drive that effort to completion?
Here's some new empirical data that may help inform this discussion. I did an experiment earlier today where I changed pyright to treat Never in the manner you're suggesting. It's an easy change — just a couple of lines of code. I then ran pyright on 28 sizable typed source bases, some of them private and some of them public. Of those, the type checking results for 11 of the 28 (about 40%) were unaffected. For the remaining 17 code bases (a little over 60%), new type errors were generated, an average of about ten per code base. That's not a huge number, but if you multiply that by the total number of typed code bases, it represents a level of churn that is not insignificant.
I looked at the errors to get a sense for their causes. I didn't see any cases that represented actual bugs (unintended runtime behaviors). About a third were attributable to incorrect type annotations that would be good to fix regardless of whether the definition of Never is changed. The remainder represent uses of Never that are legitimate based on its current definition. Most of these cases would be straightforward to change, but doing so would be "busy work" for the maintainers.
Based on this information, I propose that we do not change the definition of Never at this time. Doing so would be disruptive and solve few if any problems in the short term. This doesn't preclude us from making a change later as part of a holistic effort to formalize the type system. If you or @DiscordLiz are interested in spearheading such an effort (either using Kevin Millikin's document as a starting point or starting from scratch), I'd be happy to participate. I recommend doing this before proceeding with the effort to add intersection types to the type system, since those concepts will necessarily build upon the formalized definitions.
Can you elaborate? What is annotated incorrectly in my example?
I agree that there's a bug in my example, but I don't think it involves an incorrect annotation. The bug is that AB.foo is not assigned a value that conforms with its annotation, so the underlying value of A.foo is leaking through at runtime.
This is the incorrect annotation. The MRO isn't an ignorable detail, A.foo is part of the definition of AB. If you annotate AB.foo, it needs to be correct for AB.foo, which is defined in A. If you use the types I had in my example rather than the protocols you swapped them for, the issue persists and shows up with Never for LSP as you have types that should be considered irreconcilable types that are being reconciled with Never. (See next section for the additional issues of nominal subtyping vs typescript's use)
I'll once again note that TypeScript is an example of a popular programming language that supports gradual typing, intersections, and strict type guards, and it treats Never the same way that Python does today. [...] You've said that you perceive TypeScript to be "incorrect" from a type theory perspective.
Typescript over-elevated pragmatism in a few ways which has led to it having a few subtle ways it disagrees with type theory. These aren't major issues for Typescript, and while I disagree with them, I accept their pragmatism for typescript; Applying them to Python has more issues. Typescript isn't a good exemplar for Python less because of this and more because Typescript only has structural subtyping, not nominal. Typescript therefore doesn't have the same concepts for the safe substitution of subclasses, and we have to reevaluate the decisions Typescript has made to see if they hold up for Python before just accepting them for working in a similar language. I believe there to be major issues that arise adopting the less rigorous use of the bottom type due to this in Python.
(TypeScript doesn't support negated types, but I'm not aware of any popular programming language that does.)
Most statically typed languages do so implicitly not explicitly. I've been an advocate for explicit negation in python to reduce the number of necessary runtime checks that occur via negative inference that many actually statically typed languages don't need to do at runtime that instead happens at compile time with type dispatch.
Based on this information, I propose that we do not change the definition of Never at this time. Doing so would be disruptive and solve few if any problems in the short term.
The primary motivation for this discussion being brought here was the impact on future work (Intersections) and the need for a definitive answer on this. I believe that building Intersections on the current (Type checker adopted) behavior of Never to be perilous due to the number of edge cases which simply will be self-resolving with the general rules instead should we adjust this.
I also think it's important for this formalization to be done holistically, not piecemeal. If it's done piecemeal, it likely won't hold together, and inconsistencies will creep in.
As DiscordLiz mentioned at the top of this thread, Kevin Millikin started an effort to produce a formalization. That effort appears to have stalled. You've stated that there are some aspects of this earlier document that you disagree with, and there are other aspects that require refinement, clarification, additional review, and input from others. Perhaps you'd like to pick up the mantle and drive that effort to completion?
Without full community buy-in that puts a pause on ongoing additions to the type system until this is done, I don't think such a holistic effort is pragmatically possible at this time. (edit: possible, but difficult. I'm seeing if I can expend the time necessary to expedite this in a fashion that would reduce the churn involved in reconciling with other new things)
Whoever took it up would be constantly reconciling anything new with it and having to make hard decisions on larger breakages all at once, and then all of those breakages whatever they may be, need to be accepted as a package deal, thereby causing potentially much larger churn all at once. The benefit is more clear in that case, but I don't know how pragmatic the larger churn all at once would be even with the benefit being more clear. (Edit: but as @DiscordLiz mentions below, there aren't many things in total that would change for most users of typing, so even as a package deal, maybe this isn't insurmountably large an ask)
There have also been a few recent changes that have very ambiguous meanings, such as intentionally subclassing from Any, and the difference between directly subclassing the top type vs having an Unknown base. (instead of implementing support for __getattr__ despite that PEP 484 suggests a very similar method for modules with the need to inform type checkers of not typed members existing that should not be assumed an error)
I don't fully agree that it is necessary to do this holistically rather than piecemeal, but I think that very few people would be able to meaningfully participate if it wasn't done holistically because it would require unquestionably correct definitions done in order of most fundamental parts of the type system and building upon them in order. I think this is extremely hard to ask of most people, especially given the interactions with gradual typing.
You've pointed to an academic paper on gradual typing (published several years after the Python type system was created) that indicates that the "bottom type" should be treated as though it's outside normal subtyping rules in a type system. That doesn't appear to be a universally-held opinion, yet you keep asserting it as though it's an indisputable fact.
The paper linked includes proof that treating it the other way is insufficient, and there's a translation of the paper's proofs to a formal proof engine with some basic examples included in it for how the paper prescribes interactions with python's types up above as well. so yes, I'm treating it as an indisputable fact because there is proof that it is not merely an opinion, but a provable fact of the interactions between these.
Many of the original decisions in pythons type system have had issues of specification. (Here's one for unions having slightly incorrect specifications: CarliJoy/intersection_examples#22 which formally shows something that has led to minor divergence between type checker behavior, which was brought up at the typing summit in 2022.)
Python was pushing forward with gradual typing well before many of the stronger proofs of what is correct had been proven, and that should be applauded, but I would hope that we can look at things that are actually proven to improve the type system going forward and have fewer special cases needed by making small adjustments that fix the few places where formal theory is in disagreement. This gives us a stronger foundation, still allows gradual typing and allows future features to build more fearlessly as they can defer either entirely to what is proven already for the correct interpretation in many cases or use what is provable already to check for consistency.
Those who did the initial work on Python's type system were exceptionally close to being entirely correct with regard to now proven theory, and that is no small feat.
I think I'm safe in assuming that you have less experience than Anders Hejlsberg in developing programming languages and type systems
Not everyone lives such that their knowledge and experience is a matter of public record. I would caution from such appeals to credentials when we can discuss a matter plainly on the facts. (though doing this is undeniably difficult, as we have to distinguish from what is specified, what is conventionally accepted even if not specified, and what definitions of terms we are using where there isn't a singular definition adopted by the type system already)
I don't think it was your intention to use this in a discrediting manner and I personally have not taken it this way, but there have been multiple expressions in both public and less public places that contributing to Python's type system has barriers to entry that are artificial, or that certain things are only discussed with people already in "the club". While this may not be strictly true, even the appearance of such impacts some people's willingness to even try to participate. While this does not seem to have been your intent, I would advise that such statements could contribute to the existing sentiment that it is hard to meaningfully contribute to this without already being involved. I've been a bit loud on this more process-issue bit in particular because I've seen an impact of it on someone I consider a friend not wanting to even bother on this despite finding it to be something important.
Based on this information, I propose that we do not change the definition of Never at this time. Doing so would be disruptive and solve few if any problems in the short term. This doesn't preclude us from making a change later as part of a holistic effort to formalize the type system. If you or @DiscordLiz are interested in spearheading such an effort (either using Kevin Millikin's document as a starting point or starting from scratch), I'd be happy to participate. I recommend doing this before proceeding with the effort to add intersection types to the type system, since those concepts will necessarily build upon the formalized definitions.
@erictraut I would not be willing to spearhead that effort. I am willing to work with anyone (cough@mikeshardmind you are pretty invested in this) doing so if and only if there is a clear intent from the community that
The formalization is to be based on what is provable while remaining pragmatic.
Whatever the conclusions of it are should be kept up to date in a living specification document.
Implementations should follow the specification.
Implementations should not check things which are type issues that do not have specified behavior without it being clearly marked as outside of specification.
Any such checks outside of specification should lead to exploring if the specification should be expanded, and should be removed or adjusted if they become conflicting with the living specification.
Static analysis tools may continue to check for non-type based issues without specification, but should be encouraged to collaborate on specification of what may be correctly detected here as well. I believe there should be a section in the living specification of the type system for non-type issues which are correctly detectable in the presence of type information. Two existing examples of this are exhaustive type matching at runtime and unreachable code detection.
numbers 2, 4, 5, and 6 are of particular importance to me as they result in a source of truth that is not subject to bugs in implementation becoming the behavior without consideration, while allowing type checkers some freedom to check more than just what is fully agreed upon already, allowing room for heuristic checks which may not be proven or accepted yet, but still valuable to developers.
Being based on what is provable does not preclude any existing use case for gradual typing, but my observations lead me to think that code that directly uses Never or Any would be the code most likely to need more than only minor changes. It appears to me that outside of the top and bottom type, people are already either at the theory-correct conclusions for how types should behave or are correct by special case that applies to their use. I think there are two changes to the top type that would happen here as well if we go with theory-correct definitions, but that most users would not experience any meaningful difference on these changes as they are subtle.
I do think that the changes formalization based on theory would lead to would actually improve the usability for gradual typing users as well, not just current users of strict modes of type checkers. Having well defined specification here could allow implicit Any on untyped code as opt-in behavior be more safe than it currently is, though I'd prefer not to get too far into that hypothetical at this point in time.
I've been a bit loud on this more process-issue bit in particular because I've seen an impact of it on someone I consider a friend not wanting to even bother on this despite finding it to be something important.
@mikeshardmind I've made my displeasure in certain interactions with this known, but I hope you aren't doing this only because of that and I hope you're aware that you are also coming across a bit more confrontational as a result of taking that on.
I'll see if I can get some time approved to work on this as part of my actual day job. If so, I'm willing to attempt to not just pick up formalization efforts where they have stalled, but spearhead it. If not, I need to think about this a bit more to see if I'm willing to put in the time required.
I have a feeling that numbers 2 and 3 on your list of conditions @DiscordLiz would be a requirement for my employer to even consider me spending work hours on this. However, we heavily make use of static analysis and have fully typed code, so there is a case for my employer to be invested in such an outcome and I do think I can present this in a way that they may truly consider it. To be clear though, my employer's involvement in allowing me time to work on this would (on my end) be predicated on them not interfering in the process. My decisions on this would need to remain independent of their goals (though I believe the general case being correct aligns with my employer's use of static analysis anyhow) and something that I can evaluate only on the merits that are generally applicable or I'd not work on it on company time.
I'm also not being loud strictly because of what you've said. I've always held that good ideas can come from anywhere and that we should evaluate ideas and arguments on their own merits. I hadn't noticed that I was being that much more argumentative, so my apologies if anyone else has perceived me as being hostile as a result, the intent has been to reduce the barriers to entry on this and get the focus to be on the facts.
classA:
a: intclassB(A):
a: booldeffoo(a: A) ->None:
a.a=2B().a=2# not okfoo(B()) # ok
Something from the Python Discord's typing channel that shows that even though Never is in question in the issue here, there are ways to demonstrate other issues with what type checkers currently allow in the same place that don't require protocols or Never.
Fixing this may implicitly solve most of the perceived issues with Never, though I believe the issues with Never are fundamental enough to still require their own attention and more concrete specification.
The following scenario demonstrates the problem. Consider the following program fragment: let q : [x : Int] = [x = 5, y = true] in 〈body〉
According to standard subtype-based reasoning, the body cannot access the y field of the record.
Such modular reasoning is a hallmark of static typing, and programmers who mix static and dy-
namic typing want to reason about their code using static types where available [Tunnell Wilson et al.
2018]. Unfortunately, the following completed GTFL. program compiles and runs successfully: let q : [x : Int] = [x = 5, y = true] in (q :: ? :: [x : Int, y : Bool]).y
In essence, casting q to the unknown type and then back to a record type exposes the extra field
This is listed as one of the two motivating example (the other is about runtime performance for tail recursion), but the behaviour seems correct to me: assuming ? as Any, then "upcasting" to Any and then "upcasting" to a different type seems perfectly reasonable. (if ? is object, then the example would require an explicit cast, which could skip the ? part entirely).
You may disagree, but to present the paper to make the strong claim:
I'm treating it as an indisputable fact because there is proof that it is not merely an opinion, but a provable fact of the interactions between these
Without any acknowledgement that the assumptions of the proof may not be universally accepted in the python typing community (or referencing what the assumptions are directly), seems a bit misleading.
This is listed as one of the two motivating example (the other is about runtime performance for tail recursion), but the behaviour seems correct to me: assuming ? as Any, then "upcasting" to Any and then "upcasting" to a different type seems perfectly reasonable. (if ? is object, then the example would require an explicit cast, which could skip the ? part entirely).
Casting incorrectly doesn't make a type system's being incorrect correct it makes a programmer who does this without concern for the underlying behavior incorrect. The paper is calling out the issue with the existing definition here, the extra field that materializes and that the program works does not mean that this behavior is well defined by type systems.
Without any acknowledgement that the assumptions of the proof may not be universally accepted in the python typing community (or referencing what the assumptions are directly), seems a bit misleading
The assumptions of that paper are pretty bland, but it's safe to say that if someone is linking a paper to justify something, they are expecting that people read it and evaluate it for themselves. If I or anyone else was going to argue from base principles without leaning on existing research, the assumptions need to be included. If someone links a paper to claim something, it's safe to assume they are claiming the assumptions hold and if you have a problem with that, challenge those assumptions rather than just try and win a gotcha for them not writing word for word how the paper translates to this context.
seems a bit misleading
speaking of misleading, you didn't link the referenced paper where you wrote "From the referenced paper https://arxiv.org/pdf/2010.14094.pdf for some context.", this is a different paper that happens to agree with what was referenced above.
I'm treating it as an indisputable fact because there is proof that it is not merely an opinion, but a provable fact of the interactions between these
I was quite clear that I believe the assumptions are sound. If you don't believe that they are or think that rather general assumptions that hold across multiple type systems should not be used for python for some reason, please do explain yourself.
There are also direct examples in this thread that show an issue with current type checker behavior in this context both with and without the presence of Never, so it might do to defer to theory instead of to implementations that have clear and demonstrable errors.
Casting incorrectly doesn't make a type system's being incorrect correct it makes a programmer who does this without concern for the underlying behavior incorrect.
That's my point.
the extra field that materializes and that the program works does not mean that this behavior is well defined by type systems.
The behaviour can be well defined. I.e. you've gone through Any, so the behaviour is defined as not protected by the type system.
In this case the code works, but that's incidental from the type perspective, the logic would be the same as for:
let q : [x : Int] = [x = 5] in (q :: ? :: [x : Int, y : Bool]).y
which obviously crashes, but I wouldn't expect to raise a type error.
The paper is calling out the issue with the existing definition here,
I disagree that it's a problem with the definition, it's a problem with the programmer.
I guess you missed the earlier part of the post you're quoting:
This is listed as one of the two motivating example (the other is about runtime performance for tail recursion), but the behaviour seems correct to me: assuming ? as Any, then "upcasting" to Any and then "upcasting" to a different type seems perfectly reasonable. (if ? is object, then the example would require an explicit cast, which could skip the ? part entirely).
Technically, this is not an assumption of the proof, but it's presumably an outcome of the proof, so it proves by counterexample that there is an assumption I don't agree with.
speaking of misleading, you didn't link the referenced paper where you wrote "From the referenced paper https://arxiv.org/pdf/2010.14094.pdf for some context.", this is a different paper that happens to agree with what was referenced above.
My apologies, there was a paper referenced above, I couldn't find a link for it, so searched, and that paper came up. I see it was later linked, but didn't find that when I was trying to find the paper that was referenced.
I guess you missed the earlier part of the post you're quoting:
I didn't miss it, but it wasn't sensical for me to address it as it wasn't one of the assumptions of the proof.
Technically, this is not an assumption of the proof, but it's presumably an outcome of the proof, so it proves by counterexample that there is an assumption I don't agree with.
If you can't disagree with the assumptions but you disagree with the outcome, you need to show that the proof is incorrect or it is your model of thought which is wrong about the outcome.
My apologies, there was a paper referenced above, I couldn't find a link for it
The other is Titled "Abstracting General Typing" and is a 2016 paper attributable to Garcia. I don't have a link to it on hand, and I'm on mobile right now.
The other is Titled "Abstracting General Typing" and is a 2016 paper attributable to Garcia. I don't have a link to it on hand, and I'm on mobile right now.
@diabolo-dan yes, though the one linked in thread previously is the one which specific claims where made based on, that paper is referenced and built upon in the other.
All of that said, I think the part about "but this is proven correct" is only tangentially important right now. That can all be addressed in any formalization effort, The real issue here most relevant to what started all of this, is that mutable instance variables are not treated as invariant. This has a relevant open issue since 2017 linked above.
We can't compare directly to the decisions of other languages that don't have nominal subtyping (typescript) or that don't have the same concerns on mutability (Haskell) without addressing how things those languages don't have to consider interact.
I think there are some things not quite right here. (I only found out about this issue this morning).
A bottom type does participate in subtyping, by definition of what "bottom" means. It is a bottom type with respect to subtyping. What I intended to write in the draft spec was that Never was just such a static type.
An uninhabited type is one that, when intepreted as a set of values, is empty. In semantic subtyping where subtyping is subset inclusion, then an uninhabited type is a subtype of every type. (Trivially, every element of the empty set is an element of every other set.). Python's Never is an uninhabited static type (there are no values of type Never).
AGT ("abstracting gradual typing") represents ("concretizes") gradual types (possibly involving Any) as sets of static types. Any is the set of all static types. A static type (not involving Any) is concretized as the singleton set consisting of just that static type. So crucially, the bottom type Never is concretized as a singleton set containing the static type Never and this is definitely completely distinct from a gradual type that was concretized as an empty set (if such a thing existed).
This is definition 2 on page 9 in the paper (https://www.irif.fr/~gc/papers/icfp17.pdf). Notice that concretization here can not produce an empty set of static types. To my knowledge, nobody has worried about what would be the gradual type that would be concretized as an empty set of static types (the original AGT paper just says that abstracting such a set is undefined).
What I intended to write in the spec was that Never was most certainly a static type. If there were a hypothetical "fully statically typed" Python language, it would have Never as a static type (unlike Any). I was wishy washy about whether Never was a static subtype of Any, as an open question. (I think it could be, and I'm not aware of any problem with that.)
And mutable fields are definitely invariant. One way to think of a mutable field with type A is that it has both a getter with signature () -> A and a setter with signature (A) -> None. So the type A occurs both covariantly and contravariantly.
Under the definitions of that paper, and the definition of subtyping therin, Never participates in subtyping. The confusion here is that python type checkers aren't checking certain things (such as the variance of mutable fields of sub-classes) so with the way type checkers are treating subtyping by their behavior, Never shouldn't be considered to participate in subtyping.
One of the two needs to change here for this problem to go away.
What I intended to write in the spec was that Never was most certainly a static type. If there were a hypothetical "fully statically typed" Python language, it would have Never as a static type (unlike Any). I was wishy washy about whether Never was a static subtype of Any, as an open question. (I think it could be, and I'm not aware of any problem with that.)
Considering that we probably want it to remain the case that Never is uninhabited, I think the set-theoretic definition of Never is more useful for any formalization. This would have Never participate in subtyping behavior as a subset of all type specifications (sets of types) but not as a subtype of individual static types (see what you pointed out about the undefinable nature of concretization for this case.) The distinction here may not matter if other things that type checkers aren't checking get checked, but I think having that distinction makes definitions of other things simpler, such as those of Union, Intersection (not yet added), Not (not yet added) as the behavior of Never becomes a natural dual to the behavior of object (though not of Any)
The set-theoretic interpretation of static types is that static types loosely denote sets of values. A static type T ought to be a subtype of a static type S if the set of values denoted by T is a subset of the set of values denoted by S.
Never is a static type which denotes the empty set of values. Consequently, Never ought to be a subtype of every static type. This is what I (intended to) wrote in the draft spec. Note that this (what I've written above) is exactly dual to object.
It's really kind of an open question of Never is a subtype of Any. On the one hand, it seems it should be. If we informally think of Any as an unknown static type, then Never is certainly a subtype of whatever that type is. On the other hand, all the gradual typing literature either treats Any as only a subtype of itself (to ensure subtyping is reflexive, though to be fair I don't know if any of these systems have top and bottom types) or else treats it as not even in the domain of subtyping (the AGT approach).
What I wrote in the draft spec was that Never was not a subtype of Any, though there was some pushback in the comments. I chose this because I wanted the consequence that the union Any | Never was not equivalent to the type Any.
I'm not sure what you mean by "type specifications", I think we need to define the term.
And AGT-style concretization is simple for Never: concretization of Never is {Never} (the singleton set containing Never). What I meant to write is that abstraction (mapping a set of static types to a gradual type) of the empty set of static types is undefined in AGT. The reason is probably just because they didn't consider it. It just doesn't arise, even with unions, intersections, and negations (negations of static types only).
I think the clear solution for a Python typing spec is that class signatures are checked for invalid overrides and that the types of mutable fields are invariant. This is sort of recognized already for special cases, like TypedDict. I would rather write this than to try to patch a symptom of the problem with a weird interpretation of Never.
Checkers are of course free to implement whatever they want.
What I wrote in the draft spec was that Never was not a subtype of Any, though there was some pushback in the comments. I chose this because I wanted the consequence that the union Any | Never was not equivalent to the type Any.
In the intersection discussions we came to the conclusion that Any & T should be an irreducible form (e.g. simply by stating that the simplification rules for unions only apply to regular types with regular types, and gradual types with gradual types, but not for mixed cases), the same could simply be specified for Any | T. If I remember correctly, Eric said that internally, typecheckers already behaves this way. Although it seems that pyright special cases Never:
fromtyping_extensionsimportAny, Neverdeffoo(x: Any|int, y: Any|Never, z: int|Never):
reveal_type(x) # mypy: Any | int pyright: Any | intreveal_type(y) # mypy: Any | <nothing> pyright: Neverreveal_type(z) # mypy: int | <nothing> pyright: intpass
To come back to the issue. The point is that LSP aka behavioral subtyping is much stronger than mere structural subtyping. In particular the rules
(LSP-exception) New exceptions cannot be thrown by the methods in the subtype, except if they are subtypes of exceptions thrown by the methods of the supertype.
(LSP-postcondition) Postconditions cannot be weakened in the subtype.
are blatantly violated when a subclass annotates a return value as Never when the parent didn't. The new formalization of the typing spec should go into detail what precisely the contract is when annotations are made.
What is promised when one writes:
classFoo:
defbar(self) ->str: ...
instances of Foo have a method bar which returns instances of str in finite time.
instances of Foo have a method bar which returns instances of str or raises an exception or loops forever.
instances of Foo are such that if the attribute bar is accessed, either it loops forever, raises an exception, or returns a method which either returns an instance of str, raises an exception, or loops forever.
The current way things are checked corresponds to ③, because subclasses can override the return type with Never or can override the whole method with Never. But I think most people most of the time want ①.
Implementing full (LSP-exception) would require typed exceptions, which are possibly not wanted. But a simple solution would be an augmented rule:
Despite Never being a structual subtype of any type, it is not a behavioral subtype any type. Therefore, typecheckers should only allow substituting Never with Never, but raise an error if another type is substituted by Never.
I actually would not try to define any reductions on types. We can simply say that float | int and float are subtypes of each other as a consequence of the definition of subtyping without requiring that a typechecker rewrite one to the other.
The subtyping rule for unions that I wrote in the spec uses (plain) subtyping, so for a type such as int, int is a subtype of Any | int but Any | int is not a subtype of Any or int. I claim that this is what we want.
I don't really know what you mean by "simplification rules for unions only apply to ... gradual types with gradual types". This is a union of two gradual types: Any | dict[str, Any]. And we have that both Any is a consistent subtype of dict[str, Any] and vice versa. So is it even well-defined how you would "simplify" that? And why do we care?
(And it seems warty that we wouldn't do the same thing, whatever it is, to Any | int. int is both a static type and a gradual type, because every static type is a gradual type. So you'd need a notion of a non-static gradual type.)
Special cases add up and I don't see much value in terms of what the type system can do.
Oh, I thought in the new document, gradual types refer to Any and types that "contain" Any (list[Any], dict[str, Any], etc.):
We will refer to types that do not contain Any as a sub-part as fully static types. The dynamic type Any is the fully dynamic type. Any type other than Any that does contain Any as a sub-part will be referred to as a gradual type.
so int would not be a gradual type according to this definition.
I actually would not try to define any reductions on types
But the draft does define a reduction rule:
Subtypes can be removed from a union's components. That is, the type T is the same type as the type T | S when S <: T. We have T <: T | S from the first rule, and from T <: T (reflexivity of subtyping) and S <: T we have T | S <: T from the second rule. Note that we don't say that subtypes must be removed from a union's components. Some checkers keep them for their documentary value, they just don't contribute anything to the meaning of the type.
In the example Any | dict[str, Any] we have, using the language from the draft: Any ~< dict[str, Any] and Any ~< Any and Any <: Any, but notAny <: dict[str, Any]. Ergo, if the reduction rule requires <: and not just ~<, then Any | dict[str, Any] is irreducible. That's all I am saying. Well, possibly if someone defines a nominal subclass of Any (which is possible since 3.11), then unions between such subclasses of Any and Any could be simplified as well.
Python types don't say anything about exceptions or postconditions, so we really can't talk about them meaningfully here. I wouldn't call either of those "blatantly" violated by changing a return type to Never. We simply don't know if they're violated or not.
I don't think that really makes sense. The typing of C.foo is a perfectly good override of A.foo. (It's better than the typing of B .foo, because if we have an instance of C we can know statically that it's not intended to return.)
Obviously I have to be even more careful with my writing. The draft spec does not intend to define such a reduction rule.
I give two rules for subtyping of unions. Then I argues in non-normative text that these are enough to subsume the more complicated properties defined in the PEPs, because all of those properties are consequences of the simple definition. "Note that we don't say that subtypes must be removed...."
The typing of C.foo is a perfectly good override of A.foo. (It's better than the typing of B .foo, because if we have an instance of C we can know statically that it's not intended to return.)
Is it perfectly good, though? You can't use B or C meaningfully as substitutes for A without wrapping everything into try-except blocks. Putting instances of B or C into a function that expects A probably won't work. The typing of B is also arguably better due to the semantic meaning of NotImplementedError. What I propose would boil down to
Notice how the error should be raised in both cases, but at different lines. So the proposed rule is actually allowing neither B nor C. From a pragmatic point of view, it should only flag B if Never is returned unconditionally. Playing devil's advocate, what about this one:
Well, that's what I was arguing in #1458 (comment), that most developers, most of the time, likely want an annotation to mean that there is no violation. It feels weird that you argue that the status quo states X (=③) when the argument is it should state Y (=①) instead. I was expecting arguments in favor of *why* ③ is a good idea.
We're just talking in circles. Take a step back and consider: the things that we can statically decide about Python programs are limited (your #1 isn't even decidable). The type system we have is unsound, and by design. We can complicate the type system arbitrarily much, but there is a point of vanishing returns. We really want an "ergonomic" design that is easy to explain, easy to understand, and easy to implement correctly.
I am advocating to keep the type system simple and understandable for both programmers and implementers. Avoid special cases. (Example: we can't in general decide if a function raises different exceptions than another, so we shouldn't conclude as a special case that a function with Never as a return type definitely does raise different exceptions than any other function.)
Reacted by Jelle Zijlstra, Eric Traut, Sergei Lebedev, Martin DeMello, David Salvisberg and Daniel Grunwald
Take a step back and consider: the things that we can statically decide about Python programs are limited (your #1 isn't even decidable).
It's about what promise is made by a type annotation. The promise made by ③ is pretty useless in practice, I don't know anyone who uses this as their mental model to reason about code. The decidability is irrelevant here, a type-checker has no business attempting to infer whether code terminates and actually returns a value. This is done by the human brain who wrote the type-annotation. The argument is that an annotation like int is a promise that this code, under regular circumstances, returns an instance of int. A subclass that unconditionally raises an exception instead is not a proper substitute and will make your code fail.
You are essentially arguing that the static type shouldn't warn me even if it can detect a program failure ahead of time.
@kmillikin The problem comes in at mutable attributes. Subclasses should not be able to be more or less specific in the typing for mutable fields. As far as I can tell, all current type checkers allow this, and mypy has an open issue stating this should not be allowed going back to 2017.
Annotations are sometimes a two-way street. It isn't always just what is provided, but what can be assigned.
breaks any reliance BNotFine would have on the subclass. So the definition of that subclass itself is unsound as a drop in replacement for the base class, and people should not be allowed to do this, but instead use a generic for this pattern:
And this would only be safe for use in functions expecting an invariant match on the generic.
This example extends to Never (Swap in Never for each IntSubclassFromNumericLibrary) without any special casing of Never, but I wanted to present it without Never due to the lack of specification of Never's specific subtyping behavior.
@kmillikin so what's the path forward here for people working on anything more advanced that needs to interact with this if the whole ecosystem is wrong about something so basic and there isn't a specification to work from, only informal documents, various people's perspectives on which models of type systems python is best modeled by?
I'd like to see intersections added to python, but having good examples of how they should behave and even having good rules without special cases is hard when there is no specification, and the implementations are all wrong about more basic things.
@DiscordLiz We get the ecosystem fixed on the basics (I've just now opened an issue for pyright, there's an open issue already for mypy, and I'll look into triple-checking that pytype and pyre also have this issue), and we work on the underlying specification first
@DiscordLiz that was the subject of my talk at the Pycon US Typing Summit this year. We are in a bad position where we have multiple implementations and no specifications. This is not good for users, it's not good for implementers, and it's not good for designers of new typing features.
Unfortunately, I don't think we were able to get recordings of the Typing Summit talks.
My suggestion still is: we finish the simple subtyping specification, get a sponsor, make it a PEP, get it approved. Then (actually in parallel) we do the same thing for Part II: signature checking. This includes signature subtyping, override checking, and specification of how generic functions are implicitly specialized. We do this with input and buy-in from the implementations.
Reacted by Eric Traut, Michael H, Sergei Lebedev, Randolf Scholz and Carl Meyer
@kmillikin Well, I'm still somewhat willing to help with an effort on that, but I raised a few points earlier about that. I think most importantly, the type system needs a living reference doc that is kept up to date and which is strict in it's wording. Not just a collection of peps, but that each pep that adds to or modifies the behavior of the type system should also update the living specification. This gives a clear single source of truth without ambiguity of how various peps should resolve each other. If something new is added to the document, it is up to those adding it to ensure it isn't in conflict. This doesn't lead to people looking to potentially flawed implementations for the correct behavior.
quoting myself from earlier rather than just reference it: (This was a set of "I'm interested in helping with formalization, but conditional on these things")
The formalization is to be based on what is provable while remaining pragmatic.
Whatever the conclusions of it are should be kept up to date in a living specification document.
Implementations should follow the specification.
Implementations should not check things which are type issues that do not have specified behavior without it being clearly marked as outside of specification.
Any such checks outside of specification should lead to exploring if the specification should be expanded, and should be removed or adjusted if they become conflicting with the living specification.
Static analysis tools may continue to check for non-type based issues without specification, but should be encouraged to collaborate on specification of what may be correctly detected here as well. I believe there should be a section in the living specification of the type system for non-type issues which are correctly detectable in the presence of type information. Two existing examples of this are exhaustive type matching at runtime and unreachable code detection.
@erictraut also indicated that formalization of the existing parts of the type system should be done holistically, not in parts earlier in this thread, so I'm not sure how that interacts with your idea of splitting it into the subtyping behavior and then everything else. I think it is more natural to do everything at once to ensure consistency of definitions.
Days later edit...
After seeing how some of these issues have played out, I'm not actually interested in working on anything involving python typing anymore. It's amazing how trying to make typing "for everyone" really makes it feel bad for everyone, instead of just making it a good experience for the people who want it.
The ability to Remove capabilities from a class breaks the idea that subclasses are safe as a drop-in replacement for the base.
That's a very narrow view, in my opinion. Subclasses are used for many things, drop-in replacement being only one of them.
Then again, arguably LSP doesn't quite mesh perfectly with dynamic, duck-typed languages. It's a tool to think about a program, but it's not the only tool?
Necrobump + lolbro.typing.Never!? I Never heard of this nonsense wonderful type hint that will surely radically transform the face of... oh. Wait. It's just a typing.NoReturn alias, huh? Much better name to be sure. Still super-lame, though.
It's even lamer that "Never was added without a PEP". That's some grade-A QA BS right there. When you're adding new typing semantics without a PEP, you just know you've committed a grave sin and are about to embark on an even worse journey into the bowels of non-standard QA slop. You are now thinking:
"Uhh. What new typing semantics!? typing.Never and typing.NoReturn are just trivial aliases that still mostly do nothing and are globally impermissible, aren't they?"
Not quite. From a casual reading of the literally five billion heated comments where reputable Pythonistas start mudslinging vitriolic hate polite disagreement at one another above, we can infer that nobody knows what they're talking about when they talk about either typing.Never or typing.NoReturn, because (...waitforit) nothing was standardized. No PEP was authored. No peer review was performed. No community consensus was achieved. Nonetheless, for spurious reasons that fail to pass scrutiny, pure static type-checkers started making up seemingly pseudo-random ad-hoc semantics extending the behaviour of both typing.Never and typing.NoReturn without anyone's consent or buy-in.
According to PEP 484, typing.NoReturn and thus typing.Never is only valid as the return type hint of a callable. According to this thread, that's no longer true. In particular...
fromtypingimportNever, NoReturnclassFoo:
x: Nevery: NoReturn# <-- lolbrof=Foo() # No type errorf.x=""# Type violationf.y=""# Type violation, just 'causefoo: Never# No type errorfoo=""# Type violationbar: NoReturn# No type error but very much a "lolbro"bar=""# Type violation, just 'cause
As the above example demonstrates, "arbitrary attributes" now apparently means:
Global and local variables. Apparently, global and local variables can now be annotated by typing.Never. I'm unclear whether they have any demonstrable purpose. Maybe they do? They can be declared (and thus documented by a subsequent docstring), but they cannot be defined. So maybe that's the practical real-world utility? Documentation-only attributes? No idea. The fact they're so weird (as well as non-standard) probably explains why no @beartype user has ever complained about typing.Never before.
Class fields. Apparently, class fields can also now be annotated by typing.Never. Apparently, this includes both PEP 557-compliant @dataclass-decorated dataclass fields and standard class variables. I'm still unclear whether they have any demonstrable purpose. They... probably don't. typing do be like that.
fromtypingimportNever, Union# Semantically, these equalities apparently now hold for *ANY* valid type hint "S" and "T":Optional[Never] ==NoneUnion[Never, T] ==TNever|T==TUnion[Never, S, T] ==Union[S, T]
Never|S|T==S|T
Again, this is all pretty lame. What's the real-world use case for any of this? No idea. No one else has any idea either. @beartype's LLM-centric audience only cares about practical QA that yields tangible benefits. I share that obsession. I thus chortle spittle all over my keyboard as this thread descends into ever-increasing bouts of bike-shedding.
Anything Else? Probably. But Does Anyone Care?
I'm now wondering if you can subscript literally any subscriptable hint by typing.Never. What happens?
After all, you can subscript literally any subscriptable hint by typing.Any. PEP 484 standardized that meaning in a sensible way. For any type hint factory F, F[Any] == F is semantically true. That is, any type hint factory subscripted by typing.Any semantically reduces to just that factory unsubscripted. Thus:
fromtypingimportAny# Semantically, these equalities hold:list[Any] ==listset[Any] ==set
Above, we claimed without evidence that "typing.Never effectively implies the empty set ∅." That (possibly) being the case, it should thus be permissible to subscript any PEP 484- or 585-compliant container hint by typing.Never. Since Never == ∅, the semantic meaning would then be "An empty instance of that container." That is:
fromtypingimportNever# Semantically, these equalities should hold:tuple[()] ==tuple[Never, ...]
# Likewise, these PEP 526-compliant annotated variable assignments should be valid:empty_list: list[Never] = [] # <-- *FINE*empty_set: set[Never] =set() # <-- *FINE*# Lastly, these subsequent statements should be invalid:empty_list.append('ohboythisisawful') # <-- should be *NOT FINE*empty_set.add('and... this is trash') # <-- should be *NOT FINE*
Honestly, those are the only practical real-world use cases for typing.Never I can think of. They're probably also the only use cases for typing.Never not actually supported by pure static type-checkers. Being able to enforce container emptiness has pragmatic merit, though. It's always been a bit silly that you can type-check only empty tuples. Why not empty everything else, too? Orthogonality demands it! Actually, orthogonality doesn't care. And neither does anyone else. Why am I even typing all of this out... Why!?
typing.NoReturn: It No Longer Makes Sense
typing.Never is such an obviously more suitable, readable, and intelligible name than typing.NoReturn that... typing.NoReturn should be officially deprecated. Right? What's even the point of typing.NoReturn if it's now imposing all of these other tangentially unrelated constraints that have absolutely nothing to do with function returns anymore?
None. That's the obvious answer. typing.NoReturn no longer has a reason to live. Let's officially bring typing.NoReturn out back behind the woodshed. Its days are numbered. It's not a big number, either.
Emptiness is a place in my heart. But Hell is a place on python/typing. 😄 -> 😭
@leycec There's a slight detail that seems to have been lost along the way. If you were correct about what typing.Never indicates, the rest of the post would be spot on about the nonsensical nature.
Since Never == ∅, the semantic meaning would then be "An empty instance of that container." That is:
You're operating at the wrong level here, thankfully set-theoretic typing doesn't work this way, but I'll be one of the first to admit that our current terminology is not accessible to those not already deep in the weeds.
Never as a type annotation indicates the empty set of types, not that the value is an empty set.
Functions that never return a value (can only raise) can (and should) be typed as such, because there is no type at all for a value that doesn't exist.
Activity
mikeshardmind commentedon Aug 30, 2023
(Sorry if this is a lot, I've split my comments by concern to not have a singular wall of text)
I don't know how breaking changing the definition of Never to be more in line with what proven theory says is correct for the bottom type would be, and I'm not in a great place to implement something to that effect right now to run against mypy_primer, but I think it is worth considering.
Notably, the only actual changes behaviorally is that Never can still arise from type narrowing removing all other possible types, but any code depending on an instance of Never can't be expected to be validly reached at runtime, and Never can't be used to replace other types without it being by removing the other types. With this change, the only function which should ever receive Never as an argument, is assert_never (or any other future function intended to handle how runtime realities may diverge from static analysis due to misuse or the uncertainties of the real-world code), and only at type checking time. It would still be valid to have as a return type (indicating the lack of return)
assert_never's signature should also probably be updated too
I know there's existing work on formalization going on elsewhere, but we're running into issues with the current less formal definitions now, and with ongoing work in trying to get the Intersections PEP ready.
DiscordLiz commentedon Aug 31, 2023
I disagree that Never is consistent with other types, but it's probably useful to understand how it seems people got to a point where they have come to the conclusion that it is.
Lets start with something basic, If I specify in a function parameter annotation a singular static type, it isn't just that singular static type which is correct to give the function. Anything which can suitably stand in as a replacement for this singular type is also valid. So the parameter annotation doesn't represent one type (except in cases of invariant parameters) even though it is spelled as one type. This conceptual set of possible types which can be used in the hypothetical function exists at the same higher order @mikeshardmind referred to when describing how the top and bottom type don't exist at the same level as static and gradual types in the set-theoretic model.
In python, we have two ways that are supported by the type system for this. Inheritence (nominal typing) and Protocols (structural typing). Never can't suitably stand in for any type. It lacks the structure of every type, as it can't even exist, and it isn't a subclass of any other type either. It isn't a gradual type, it's the lack of a type all together.
So why is Never a suitable replacement in a return type? Well, it isn't. Because we aren't returning a type anymore, at least, not in a way that typing checks* and python does not have the same code path for returning values and raising exceptions, a function which unconditionally raises can have it's return value annotation used to mark the lack of return value without this being a replacement of the return type; Rather, it's specifying the lack of a type being returned.
I believe the original name of NoReturn was actually more correct for most places users could actually specify it, and some of the original insight of those who named it that may have fallen away to lack of recording anywhere important. The one case where Never is more correct as an annotation, is in the special purpose function assert_never, which the goal of is also to say that there is no longer a valid type. This is similar to
unreachablein many compiled static languages. Actually reaching unreachable signals an error, as would passing an instance of something which shouldn't exist (the type system believes there are no remaining options, hence Never).**I think it's how errors are handled in python and many other languages, and Never appearing to work as a replacement in one place (return values) that misleads people into believing it should work everywhere and be consistent with all types.
*Exceptions are really still just values with special control flow, but absent a proposal to add checked exceptions to python's type system, this distinction doesn't matter. I don't care about or want checked exceptions in python, but adding this to the type system would be an ordeal that if someone does want, they would find issues arise with Never as a replacement annotation without additional syntax.
** Never is still a good and useful name though. Never can still correctly arise in inference with elimination of possible types, and it would be weird to have NoReturn as the name in inference in that case.
eltoder commentedon Aug 31, 2023
@tmke8
I think it is debatable whether constructing an instance of
Bshould be disallowed, or if it is enough that access tofooalways raises an exception forB.footo have typeNever. However, this is moot. The same issue arises for methods returningNeverandNoReturn:mypy allows this, but this arguably violates LSP for the same reasons as the example in OP. It introduces unreachable code into methods using
A. IMHO, creating instances of thisBshould be allowed, but this inheritance should generate an error.Also note that
NoReturn.NoReturnandNeveras values, because this hides bugs. [1][2][3]Noneas values even if this is not a type error, because this is likely a bug. [4][1] python/mypy#4116
[2] python/mypy#13592
[3] python/mypy#15821
[4] https://mypy-play.net/?mypy=latest&python=3.11&gist=e757839d654dd3dbc395128ec3015912
tmke8 commentedon Aug 31, 2023
I think a type theorist would reply that yes, you are allowed to construct an instance of this
Bclass but LSP still isn't violated because you cannot get the program into an inconsistent state with this; if you callB.foothrough the interface ofA, the program will just crash, but it is not the case that a variable that was declared asintnow has a value of a different type. So, no type guarantee is violated.But, python's static typing obviously doesn't have to follow type theory exactly, so I won't object to potential changes on this ground.
(I just object to OP's framing of this issue as mypy violating type theory. In type theory, the bottom type is definitely a subtype of all other types. You can advocate for deviating from this, but I don't think you can say that it's more theoretically grounded that way.)
eltoder commentedon Aug 31, 2023
@tmke8
This is correct, but also not useful IMO. It is not different from passing in an object where
foois not defined at all, or has a different number of arguments. Both will result in an exception rather than a value of a different type. But preventing such exceptions is the primary reason to use a static type checker in python in the first place :-)I agree that bottom type is by definition compatible with every other type. I think the OP's argument is that
Nevershould be an "uninhabited type" rather than the bottom type, which are different in some theories, because making it bottom type introduces too much unsafety.mikeshardmind commentedon Aug 31, 2023
@tmke8
In the set-theoretic model of typing which current formalization efforts are largely being built on top of, the bottom and top types don't participate in subtyping behavior. (At least in the way python type checkers are defining what a subtype is, see other posts that point out a reconciliation) Relations with these types are defined by other properties.
Now, I've linked a draft that still has a lot of imprecise wording and which there is still ongoing discussion about amending several sections to be more in line with theory and deviate from it less, but there are a lot of referenced research papers and published proofs linked within that, and you may find reading through some of the more recent research here and what more recent published proofs show to be correct may broaden your perspective.
In these models, the bottom type is uninhabitable and does not participate in subtyping behavior directly with static or gradual types, instead participating with a well-defined set of behaviors (that is not equivalent to subtyping for the top and bottom types) with the relation of type specifications, which are the sets of types that can be used where a static or gradual type is requested. This distinction is subtle but important. (Note that some papers have defined this as subtyping as well, but that these definitions do not match python's current behavior)
Outside of two things:
Python's type system fully follows the set-theoretic model's definitions, specifically those built up in
Abstracting Gradual TypingIf that doesn't change your perspective, I'd be interested to hear how you reconcile this, as well as the effects on LSP, as it could be illuminating for how we handle this going forward.
@eltoder See above, but no, the argument is that python actually follows the set-theoretic definitions for nearly everything else, and that it should for Never as well. (the set-theoretic ones have the bottom type as uninhabited, as you nodded to with "some theories")) Not doing so creates inconsistency, and creates a situation where established rules for safe-replacement do not work. (Note, This still is being discussed in the formalization happening in the background as well, there isn't good agreement on which definitions should be used yet anywhere, but there are issues we can show with treating Never as a type that participates in subtyping.)
mikeshardmind commentedon Aug 31, 2023
As for the current behavior concretely violating LSP, @randolf-scholz raised this recently in the related conversation pertaining to intersections
This makes an attempt to square the two, but notably, this creates a specific exception that reaches the same result as changing the general definition as argued here.
eltoder commentedon Aug 31, 2023
@mikeshardmind I think it is hard to argue "python actually follows the set-theoretic definitions for nearly everything". The typing PEPs are generally not precise enough, so mypy is used as a de facto interpretation of those PEPs. But mypy has over 2000 open issues and also includes behaviors that address style or practical concerns and are far from theory. I expect that if you examine the actual behavior of mypy in enough detail, you find a lot of places where it deviates from theory.
OTOH, the current definition of
Neveris used in a lot of programming languages[1], so it's fair to say at a minimum that there are arguments and research supporting this position.[1] https://en.wikipedia.org/wiki/Bottom_type#In_programming_languages
mikeshardmind commentedon Aug 31, 2023
@eltoder This discussion in this thread is overflowing from over a month of exploring issues with a potential addition to the type system which is based on theory. I don't lightly bandy about that python mostly follows these definitions, this has been heavily discussed and led to a lot of discussion that ultimately needed to come here due to a poor interaction between how type checkers are currently interpreting Never and other assumptions people have about type safety.
I also think we would benefit from better definitions that don't lead to relying on "well, this is what type checkers are currently doing" to define what is correct, or the end result is "type checkers, including any errors in their implementation, are the source of truth, not the specified rules."
Funnily enough, what you linked isn't quite making the argument you seem to think it is. For example, Haskell and Rust's definitions both match more closely to what is described in this issue than what type checkers are currently doing.
Haskell:
Rust:
Rust and Haskell do not allow the bottom type where python type checkers currently do, only allowing it where there is no value, and correctly treating reaching code that has a type of Never to be an error.
@DiscordLiz gave a good explanation above for how easy it would be for someone without the type theory background to make the incorrect leap that many have made and why.
Additionally, When comparing TypeScript's use of Intersections, with what is being proposed for python, it was found that typescript has an arbitrary undocumented sorting algorithm that has an impact on the outcome of intersections. Should we conclude that intersections must have this feature because another language did this? Just because another language does something does not mean that that something has had the same considerations for use that would be appropriate for other use.
DiscordLiz commentedon Aug 31, 2023
@mikeshardmind just a slight clarification for anyone confused, Haskell allows specifying such code but treats the use of it as and impossible to recover from error. This is strictly as a mathematical outcome that could arise due to composition of functions, and not as an intent to allow such code to exist or be used. You are still correct that this is not treating Never as a subtype but as the absence of a valid type.
DiscordLiz commentedon Aug 31, 2023
@eltoder
Hopefully mniip doesn't mind this being shared here to make the point that this is possible, but... It's possible to create a program to actually check this by encoding the rules of a specific model of working with types into a formal proof engine and comparing it to what is currently the "accepted consensus behavior" since you are arguing that the PEPs aren't precise. I similarly share the above opinion that the imprecision in PEPs meant to specify is a problem.
Coq formalization of "Gradual Typing with Union and Intersection Types" (https://www.irif.fr/~gc/papers/icfp17.pdf)
Starting from: https://gist.github.com/mniip/0bfb52f35da3ad6c96878082e6af37e6, but modified further.
Note: This doesn't contradict what was said about the set-theoretic view not allowing this despite the subtyping relation, The rules proposed in this paper and encoded in the coq program there treat the bottom type not as participating in subtyping as most people are aware of the term, but redefine subtyping more generally in such a way that it does apply.
eltoder commentedon Aug 31, 2023
@mikeshardmind
Not really. Haskell allows
undefinedto be used in place of an expression of any type. For example, this type checks and runs:It is considered a feature: https://wiki.haskell.org/Undefined
A similar example works in Rust:
You have to allow unreachable code, but this is not a type error.
This example works in Scala, Kotlin, TypeScript and probably others (with respective syntax changes):
mikeshardmind commentedon Aug 31, 2023
The very first line of that page: states: "You can put it anywhere and it will compile. When evaluated, it throws an exception "undefined". But thanks to laziness you can put it anywhere you've not written yet:" This is not the same as type checkers allowing this and claiming it to be safe, in fact, this is haskell specifically telling you that use of it isn't safe.
This isn't an example of it being a value, Please read again about the difference between a value and a lack of a value, it matters. On top of this, Rust correctly detects unreachable code and you are opting out of the safety it provides visibly here.
This is also an example of something throwing an exception and not returning a value at all, not of something having a value of the bottom type.
DiscordLiz commentedon Sep 1, 2023
@mikeshardmind nudged me to put this comment separately rather than in a collapsible section over in discord, but what definition of "subtyping" is used matters here too. The set-theoretic model can be (see the proof above) reconciled with a general type connective which the paper it was proved in defines as their version of subtyping, but this use isn't consistent with what current type checkers are allowing. (And indeed the paper takes the time to lay out how prior definitions of subtyping are lacking)
We have a very complex issue here where there is lots of good well proven theory, and no good definitions that are commonly accepted in python to actually communicate the issue due to lack of specification in PEPs.
mikeshardmind commentedon Sep 7, 2023
I'm gonna start with a few things here.
And the actual output:
As described above, and clearly demonstrated with the toy example here, Never isn't consistent with other types for the purposes of safe replacement, and treating it as such not only allows nonsensical subclasses, but also breaks expectations of checked code in terms of what may be passed to it. While there are definitions of subtyping that would apply between Never and other types, they exclude this broken behavior.
Any code relying on this behavior is fundamentally broken, and I don't think this requires a "Breaking change" or transitionary period to fix as
Pyright's errors via pylance in VSC with strict:
Mypy's output with
--strict(Showing the lack of error isn't just a settings issue) via mypy playground on latest:A more dangerous example would involve the return types both working for
takes_aandtakes_bpurely by implementation accident, but returning different types than expected polluting where the type issues even came from.Now if anyone can argue that it should be allowed and keep in mind the effects on library code taking in user-provided classes with this information and impact demonstrated, I'd love to hear the argument, because as it stands it sounds like the only argument against it is "Well that's not what we've been doing it and changing it might be hard" (Appeal to tradition or status quo) or "other language does this" (Appeal to authority) even though clearly there is a detectable issue here.
My preferred resolution on this involves clearly stating that Never isn't consistent with other types (officially somewhere) and that Never remains fine for things that truly don't return a value of any type, but you can't specify a function, class, or other annotation having a dependence on Never without it specifically indicating erroneous or unreachable code of some sort.
erictraut commentedon Sep 7, 2023
You state that with conviction, but that isn't how
Neverhas been understood in the past by the Python typing community. There may or may not be good reasons to change its meaning in the Python type system. None of the reasons you've presented so far seem very compelling to me, but I'm trying to remain open-minded. Such a redefinition will likely have backward-compatibility implications, so it would need to be well motivated. Citing an academic paper on type theory will probably be insufficient to sway people. I personally enjoy geeking out about type theory, but pragmatism tends to trump theory in the Python community. There are other programming languages where "purity of theory" is valued much more highly (Haskell comes to mind), but Python tends to be further on the "pragmatism" side of that spectrum.If you want to argue in favor of a change to the Python type system, a more effective approach is to demonstrate that such a change would solve some real problem that Python developers are facing today. What is the problem you're trying to solve? How prevalent is the problem? Do we have evidence to back this up (e.g. bug reports or feature requests in the mypy issue tracker or StackOverflow posts)?
Pyright is not complaining about the
Nevertype. It's complaining about the fact that you're overriding a property with a variable. It will emit this regardless of which type you use in the override. Mypy is more lax in this case and allows properties to be overridden by variables. So this has nothing to do withNever.The crash is because the variable
foowas never assigned a value in classAB. This can happen with any class-scoped variable regardless of its type. This is not specific toNever.Consider the following modified example. This also type checks without error in both mypy and pyright but crashes at runtime. There is no
Neverinvolved in this example, but it is otherwise completely analogous to your code above.I think your example demonstrates that there are bugs that can go uncaught by static type checking. That's something that no one would dispute. It doesn't demonstrate why
Nevershould be treated differently from other types.Do you have other examples?
randolf-scholz commentedon Sep 7, 2023
@erictraut Replacing a non-
Neverannotated object with aNeverannotated object violates certain aspects of LSP, specifically (LSP-exception)Also, pre- and post-conditions are in some sense violated this way (CarliJoy/intersection_examples#5 (comment)).
Imo, the main issue here is uncertainty. Since it is not explicitly codified, it is unclear what contract a type annotation like
really promises. Most people would probably say that it guarantees that instances of
Fooare guaranteed to have an attributebarwhich is an instance ofint.But clearly, if a subclass
SubFoois allowed to substitutebarwithNever, then (LSP-exception) is violated, since looking up said attribute never terminates or raises an exception. Therefore,SubFoocannot safely be used as a substitute forFoowithout wrapping everything intry-exceptblocks.The Python community should decide whether they want the typing system to support (LSP-exception), or a weaker version of it, like the one I proposed in CarliJoy/intersection_examples#5 (comment), and clearly communicate this decision.
mikeshardmind commentedon Sep 7, 2023
@erictraut
No, this misunderstands the example here. Simply annotating Never without replacing the inherited methods/properties is accepted, making the annotation of Never incorrect. The crash isn't because the attribute doesn't exist, and you can see in the traceback exactly what happened.
erictraut commentedon Sep 7, 2023
Did you look at my modified example? Try running it. My version produces exactly the same stack trace and error message but doesn't involve
Never. I don't see how the two are any different, yet my version doesn't involveNever.mikeshardmind commentedon Sep 7, 2023
@erictraut Your modified example also involves annotating something incorrectly. This is detectable and isn't being detected.
The situation with Never matters here even if this issue of detection is resolved. You've also fundamentally sidestepped the underpinning question by turning that into a protocol. If there are two incompatible types, it shouldn't be possible to subclass both by simply placing a Never there.
mikeshardmind commentedon Sep 7, 2023
intis.@DiscordLiz already explained how neither Any nor Never are singular types up above pretending Never is a singular type rather than the bottom type, (ie. the empty set of types or any other reasonable interpretation of what a bottom type is in a type system) is how we got here.
Never,assert_never, seems to be written correctly understanding that if you reach a point where you have an expectation of a type only being Never, you have unreachable code.First of all, @eltoder already showed some relevant mypy bugs
But more to the point, where is it specified that Never is a subtype of and a suitable replacement for all other types? As far as I can ascertain, this is just a decision that type checkers made without it ever being specified and with a lack of understanding of what is correct from the point of view of theory. While it is very understandable how such a lack of understanding or misconception could occur, that's part of why these things should be specified and that the specification should happen in the open* not "oh, we implemented it this way, and we don't have a specification for it, guess you're stuck with it".
The issue it solves to have a correct specification is that future additions to the specification are building on a solid foundation not needing mountains of exceptions to rules because of an accumulation of errors.
Intersections, Not, and Stricter TypeGuards (Which use both intersections and Not in describing their resulting equivalence) are impossible to have a coherent set of rules and behaviors if Never is treated as a type, rather than an (empty) set of types. That's how this discussion came here, realizing that type checkers are allowing something that fundamentally breaks what is being worked on.
* And for the record, the typing-sig mailing list is the least visible place such a discussion could occur. Even the issue trackers of individual type checkers see more users regularly, and those do not have the barrier to entry of waiting for the mailing list administrator to manually review posts from new users which delays feedback if its even seen to begin with. Mailing lists are atrocious for modern-day collaborative discussion by comparison to other tools at the disposal of the community. (They still have a very clear place for announcements)
erictraut commentedon Sep 8, 2023
Can you elaborate? What is annotated incorrectly in my example?
I agree that there's a bug in my example, but I don't think it involves an incorrect annotation. The bug is that
AB.foois not assigned a value that conforms with its annotation, so the underlying value ofA.foois leaking through at runtime. Would it be possible for a static type checker to detect this condition? Perhaps, but such a check would also produce many false positives for correctly-written Python code. That's why Python type checkers do not currently check for this case. It would simply be too noisy and wouldn't catch many real-world bugs.Let's assume that a type checker could reasonably enforce that a declared class variable must be assigned a value within the class' implementation. Your original example and my example would both trigger that error. In my example, I could fix that error by assigning a value to
AB.foothat conforms to the_SupportsEncodeAndToBytesprotocol. In your example, any attempt to address that error by assigning a value would result in a different type error because it's impossible to assign a value that conforms toNeveror a value that subclasses from bothintandstr.So I assert once again that your example does not demonstrate why
Nevershould be treated differently from other types. You may be able to produce other examples that support your position, but this example does not, at least as I see it.I'll once again note that TypeScript is an example of a popular programming language that supports gradual typing, intersections, and strict type guards, and it treats
Neverthe same way that Python does today. (TypeScript doesn't support negated types, but I'm not aware of any popular programming language that does.) You've said that you perceive TypeScript to be "incorrect" from a type theory perspective. I personally know the developers responsible for TypeScript, and they are both very knowledgable about type theory and very pragmatic when it comes to prioritizing usability over purity. I admit that I'm not familiar with your background or credentials, but I think I'm safe in assuming that you have less experience than Anders Hejlsberg in developing programming languages and type systems 😀. I'm not saying that your viewpoint is wrong, but I would caution you against dismissing TypeScript as an unworthy exemplar.TypeScript isn't alone in treating
Neveras the subtype of (and therefore assignable to) all other types. Wikipedia and many other sources define "bottom type" as the subtype of all other types in a type system. You and @DiscordLiz have asserted that wikipedia is wrong or that it's relying a different definition of subtype. You've pointed to an academic paper on gradual typing (published several years after the Python type system was created) that indicates that the "bottom type" should be treated as though it's outside normal subtyping rules in a type system. That doesn't appear to be a universally-held opinion, yet you keep asserting it as though it's an indisputable fact.I appreciate the perspective you bring to this discussion, but I don't think you've made a clear and convincing case that we should make a change to the type system that results in a breaking change.
I agree with you that there is value in formalizing the Python type specification. As you point out, this is an important foundation upon which any major new typing features should be built. Ideally, this specification should be developed in an open and collaborative manner so it has buy-in from the broader typing community, and it should employ terminology that is clearly defined and used consistently throughout the spec. (In the discussions about intersections, I've noted that new terms are being injected into the conversation with the assumption that everyone has a common understanding of terms like uninhabited type, static type, gradual type, etc., and this is leading to confusion.) I also think it's important for this formalization to be done holistically, not piecemeal. If it's done piecemeal, it likely won't hold together, and inconsistencies will creep in.
As @DiscordLiz mentioned at the top of this thread, Kevin Millikin started an effort to produce a formalization. That effort appears to have stalled. You've stated that there are some aspects of this earlier document that you disagree with, and there are other aspects that require refinement, clarification, additional review, and input from others. Perhaps you'd like to pick up the mantle and drive that effort to completion?
Here's some new empirical data that may help inform this discussion. I did an experiment earlier today where I changed pyright to treat
Neverin the manner you're suggesting. It's an easy change — just a couple of lines of code. I then ran pyright on 28 sizable typed source bases, some of them private and some of them public. Of those, the type checking results for 11 of the 28 (about 40%) were unaffected. For the remaining 17 code bases (a little over 60%), new type errors were generated, an average of about ten per code base. That's not a huge number, but if you multiply that by the total number of typed code bases, it represents a level of churn that is not insignificant.I looked at the errors to get a sense for their causes. I didn't see any cases that represented actual bugs (unintended runtime behaviors). About a third were attributable to incorrect type annotations that would be good to fix regardless of whether the definition of
Neveris changed. The remainder represent uses ofNeverthat are legitimate based on its current definition. Most of these cases would be straightforward to change, but doing so would be "busy work" for the maintainers.Based on this information, I propose that we do not change the definition of
Neverat this time. Doing so would be disruptive and solve few if any problems in the short term. This doesn't preclude us from making a change later as part of a holistic effort to formalize the type system. If you or @DiscordLiz are interested in spearheading such an effort (either using Kevin Millikin's document as a starting point or starting from scratch), I'd be happy to participate. I recommend doing this before proceeding with the effort to add intersection types to the type system, since those concepts will necessarily build upon the formalized definitions.mikeshardmind commentedon Sep 8, 2023
@erictraut
This is the incorrect annotation. The MRO isn't an ignorable detail, A.foo is part of the definition of AB. If you annotate AB.foo, it needs to be correct for AB.foo, which is defined in A. If you use the types I had in my example rather than the protocols you swapped them for, the issue persists and shows up with Never for LSP as you have types that should be considered irreconcilable types that are being reconciled with Never. (See next section for the additional issues of nominal subtyping vs typescript's use)
Typescript over-elevated pragmatism in a few ways which has led to it having a few subtle ways it disagrees with type theory. These aren't major issues for Typescript, and while I disagree with them, I accept their pragmatism for typescript; Applying them to Python has more issues. Typescript isn't a good exemplar for Python less because of this and more because Typescript only has structural subtyping, not nominal. Typescript therefore doesn't have the same concepts for the safe substitution of subclasses, and we have to reevaluate the decisions Typescript has made to see if they hold up for Python before just accepting them for working in a similar language. I believe there to be major issues that arise adopting the less rigorous use of the bottom type due to this in Python.
Most statically typed languages do so implicitly not explicitly. I've been an advocate for explicit negation in python to reduce the number of necessary runtime checks that occur via negative inference that many actually statically typed languages don't need to do at runtime that instead happens at compile time with type dispatch.
The primary motivation for this discussion being brought here was the impact on future work (Intersections) and the need for a definitive answer on this. I believe that building Intersections on the current (Type checker adopted) behavior of Never to be perilous due to the number of edge cases which simply will be self-resolving with the general rules instead should we adjust this.
Without full community buy-in that puts a pause on ongoing additions to the type system until this is done,
I don't think such a holistic effort is pragmatically possible at this time.(edit: possible, but difficult. I'm seeing if I can expend the time necessary to expedite this in a fashion that would reduce the churn involved in reconciling with other new things)Whoever took it up would be constantly reconciling anything new with it and having to make hard decisions on larger breakages all at once, and then all of those breakages whatever they may be, need to be accepted as a package deal, thereby causing potentially much larger churn all at once. The benefit is more clear in that case, but I don't know how pragmatic the larger churn all at once would be even with the benefit being more clear. (Edit: but as @DiscordLiz mentions below, there aren't many things in total that would change for most users of typing, so even as a package deal, maybe this isn't insurmountably large an ask)
There have also been a few recent changes that have very ambiguous meanings, such as intentionally subclassing from Any, and the difference between directly subclassing the top type vs having an Unknown base. (instead of implementing support for
__getattr__despite that PEP 484 suggests a very similar method for modules with the need to inform type checkers of not typed members existing that should not be assumed an error)I don't fully agree that it is necessary to do this holistically rather than piecemeal, but I think that very few people would be able to meaningfully participate if it wasn't done holistically because it would require unquestionably correct definitions done in order of most fundamental parts of the type system and building upon them in order. I think this is extremely hard to ask of most people, especially given the interactions with gradual typing.
The paper linked includes proof that treating it the other way is insufficient, and there's a translation of the paper's proofs to a formal proof engine with some basic examples included in it for how the paper prescribes interactions with python's types up above as well. so yes, I'm treating it as an indisputable fact because there is proof that it is not merely an opinion, but a provable fact of the interactions between these.
Many of the original decisions in pythons type system have had issues of specification. (Here's one for unions having slightly incorrect specifications: CarliJoy/intersection_examples#22 which formally shows something that has led to minor divergence between type checker behavior, which was brought up at the typing summit in 2022.)
Python was pushing forward with gradual typing well before many of the stronger proofs of what is correct had been proven, and that should be applauded, but I would hope that we can look at things that are actually proven to improve the type system going forward and have fewer special cases needed by making small adjustments that fix the few places where formal theory is in disagreement. This gives us a stronger foundation, still allows gradual typing and allows future features to build more fearlessly as they can defer either entirely to what is proven already for the correct interpretation in many cases or use what is provable already to check for consistency.
Those who did the initial work on Python's type system were exceptionally close to being entirely correct with regard to now proven theory, and that is no small feat.
Not everyone lives such that their knowledge and experience is a matter of public record. I would caution from such appeals to credentials when we can discuss a matter plainly on the facts. (though doing this is undeniably difficult, as we have to distinguish from what is specified, what is conventionally accepted even if not specified, and what definitions of terms we are using where there isn't a singular definition adopted by the type system already)
I don't think it was your intention to use this in a discrediting manner and I personally have not taken it this way, but there have been multiple expressions in both public and less public places that contributing to Python's type system has barriers to entry that are artificial, or that certain things are only discussed with people already in "the club". While this may not be strictly true, even the appearance of such impacts some people's willingness to even try to participate. While this does not seem to have been your intent, I would advise that such statements could contribute to the existing sentiment that it is hard to meaningfully contribute to this without already being involved. I've been a bit loud on this more process-issue bit in particular because I've seen an impact of it on someone I consider a friend not wanting to even bother on this despite finding it to be something important.
DiscordLiz commentedon Sep 8, 2023
@erictraut I would not be willing to spearhead that effort. I am willing to work with anyone (cough @mikeshardmind you are pretty invested in this) doing so if and only if there is a clear intent from the community that
numbers 2, 4, 5, and 6 are of particular importance to me as they result in a source of truth that is not subject to bugs in implementation becoming the behavior without consideration, while allowing type checkers some freedom to check more than just what is fully agreed upon already, allowing room for heuristic checks which may not be proven or accepted yet, but still valuable to developers.
Being based on what is provable does not preclude any existing use case for gradual typing, but my observations lead me to think that code that directly uses
NeverorAnywould be the code most likely to need more than only minor changes. It appears to me that outside of the top and bottom type, people are already either at the theory-correct conclusions for how types should behave or are correct by special case that applies to their use. I think there are two changes to the top type that would happen here as well if we go with theory-correct definitions, but that most users would not experience any meaningful difference on these changes as they are subtle.I do think that the changes formalization based on theory would lead to would actually improve the usability for gradual typing users as well, not just current users of strict modes of type checkers. Having well defined specification here could allow implicit Any on untyped code as opt-in behavior be more safe than it currently is, though I'd prefer not to get too far into that hypothetical at this point in time.
@mikeshardmind I've made my displeasure in certain interactions with this known, but I hope you aren't doing this only because of that and I hope you're aware that you are also coming across a bit more confrontational as a result of taking that on.
mikeshardmind commentedon Sep 8, 2023
I'll see if I can get some time approved to work on this as part of my actual day job. If so, I'm willing to attempt to not just pick up formalization efforts where they have stalled, but spearhead it. If not, I need to think about this a bit more to see if I'm willing to put in the time required.
I have a feeling that numbers 2 and 3 on your list of conditions @DiscordLiz would be a requirement for my employer to even consider me spending work hours on this. However, we heavily make use of static analysis and have fully typed code, so there is a case for my employer to be invested in such an outcome and I do think I can present this in a way that they may truly consider it. To be clear though, my employer's involvement in allowing me time to work on this would (on my end) be predicated on them not interfering in the process. My decisions on this would need to remain independent of their goals (though I believe the general case being correct aligns with my employer's use of static analysis anyhow) and something that I can evaluate only on the merits that are generally applicable or I'd not work on it on company time.
I'm also not being loud strictly because of what you've said. I've always held that good ideas can come from anywhere and that we should evaluate ideas and arguments on their own merits. I hadn't noticed that I was being that much more argumentative, so my apologies if anyone else has perceived me as being hostile as a result, the intent has been to reduce the barriers to entry on this and get the focus to be on the facts.
mikeshardmind commentedon Sep 8, 2023
Something from the Python Discord's typing channel that shows that even though Never is in question in the issue here, there are ways to demonstrate other issues with what type checkers currently allow in the same place that don't require protocols or Never.
The problem here is still the LSP violation described above. Something that can be both used and assigned to is only being checked for variance as if it is only being used, not as if it also needs to be suitable to assign to in replacement. There's an open mypy issue going back to 2017 for this one.
Fixing this may implicitly solve most of the perceived issues with Never, though I believe the issues with Never are fundamental enough to still require their own attention and more concrete specification.
diabolo-dan commentedon Sep 8, 2023
From the referenced paper https://arxiv.org/pdf/2010.14094.pdf for some context.
This is listed as one of the two motivating example (the other is about runtime performance for tail recursion), but the behaviour seems correct to me: assuming
?asAny, then "upcasting" toAnyand then "upcasting" to a different type seems perfectly reasonable. (if?isobject, then the example would require an explicitcast, which could skip the?part entirely).You may disagree, but to present the paper to make the strong claim:
Without any acknowledgement that the assumptions of the proof may not be universally accepted in the python typing community (or referencing what the assumptions are directly), seems a bit misleading.
DiscordLiz commentedon Sep 8, 2023
Casting incorrectly doesn't make a type system's being incorrect correct it makes a programmer who does this without concern for the underlying behavior incorrect. The paper is calling out the issue with the existing definition here, the extra field that materializes and that the program works does not mean that this behavior is well defined by type systems.
The assumptions of that paper are pretty bland, but it's safe to say that if someone is linking a paper to justify something, they are expecting that people read it and evaluate it for themselves. If I or anyone else was going to argue from base principles without leaning on existing research, the assumptions need to be included. If someone links a paper to claim something, it's safe to assume they are claiming the assumptions hold and if you have a problem with that, challenge those assumptions rather than just try and win a gotcha for them not writing word for word how the paper translates to this context.
speaking of misleading, you didn't link the referenced paper where you wrote "From the referenced paper https://arxiv.org/pdf/2010.14094.pdf for some context.", this is a different paper that happens to agree with what was referenced above.
mikeshardmind commentedon Sep 8, 2023
When I said
I was quite clear that I believe the assumptions are sound. If you don't believe that they are or think that rather general assumptions that hold across multiple type systems should not be used for python for some reason, please do explain yourself.
There are also direct examples in this thread that show an issue with current type checker behavior in this context both with and without the presence of Never, so it might do to defer to theory instead of to implementations that have clear and demonstrable errors.
diabolo-dan commentedon Sep 8, 2023
That's my point.
The behaviour can be well defined. I.e. you've gone through
Any, so the behaviour is defined as not protected by the type system.In this case the code works, but that's incidental from the type perspective, the logic would be the same as for:
let q : [x : Int] = [x = 5] in (q :: ? :: [x : Int, y : Bool]).ywhich obviously crashes, but I wouldn't expect to raise a type error.
I disagree that it's a problem with the definition, it's a problem with the programmer.
diabolo-dan commentedon Sep 8, 2023
I guess you missed the earlier part of the post you're quoting:
Technically, this is not an assumption of the proof, but it's presumably an outcome of the proof, so it proves by counterexample that there is an assumption I don't agree with.
diabolo-dan commentedon Sep 8, 2023
My apologies, there was a paper referenced above, I couldn't find a link for it, so searched, and that paper came up. I see it was later linked, but didn't find that when I was trying to find the paper that was referenced.
I'll take a look. So I don't make the same mistake again, can you confirm that it's this one: https://www.irif.fr/~gc/papers/icfp17.pdf
mikeshardmind commentedon Sep 8, 2023
I didn't miss it, but it wasn't sensical for me to address it as it wasn't one of the assumptions of the proof.
If you can't disagree with the assumptions but you disagree with the outcome, you need to show that the proof is incorrect or it is your model of thought which is wrong about the outcome.
This is one of the two papers referenced specifically, and the one that has a link in thread, as well as a machine-proof version of it that shows how these definitions interact with Python's types Paper: https://www.irif.fr/~gc/papers/icfp17.pdf
The other is Titled "Abstracting General Typing" and is a 2016 paper attributable to Garcia. I don't have a link to it on hand, and I'm on mobile right now.
diabolo-dan commentedon Sep 8, 2023
this one:
https://www.cs.ubc.ca/~rxg/agt.pdf
?
mikeshardmind commentedon Sep 8, 2023
@diabolo-dan yes, though the one linked in thread previously is the one which specific claims where made based on, that paper is referenced and built upon in the other.
All of that said, I think the part about "but this is proven correct" is only tangentially important right now. That can all be addressed in any formalization effort, The real issue here most relevant to what started all of this, is that mutable instance variables are not treated as invariant. This has a relevant open issue since 2017 linked above.
We can't compare directly to the decisions of other languages that don't have nominal subtyping (typescript) or that don't have the same concerns on mutability (Haskell) without addressing how things those languages don't have to consider interact.
kmillikin commentedon Sep 11, 2023
I think there are some things not quite right here. (I only found out about this issue this morning).
A bottom type does participate in subtyping, by definition of what "bottom" means. It is a bottom type with respect to subtyping. What I intended to write in the draft spec was that Never was just such a static type.
An uninhabited type is one that, when intepreted as a set of values, is empty. In semantic subtyping where subtyping is subset inclusion, then an uninhabited type is a subtype of every type. (Trivially, every element of the empty set is an element of every other set.). Python's Never is an uninhabited static type (there are no values of type Never).
AGT ("abstracting gradual typing") represents ("concretizes") gradual types (possibly involving Any) as sets of static types. Any is the set of all static types. A static type (not involving Any) is concretized as the singleton set consisting of just that static type. So crucially, the bottom type Never is concretized as a singleton set containing the static type Never and this is definitely completely distinct from a gradual type that was concretized as an empty set (if such a thing existed).
This is definition 2 on page 9 in the paper (https://www.irif.fr/~gc/papers/icfp17.pdf). Notice that concretization here can not produce an empty set of static types. To my knowledge, nobody has worried about what would be the gradual type that would be concretized as an empty set of static types (the original AGT paper just says that abstracting such a set is undefined).
What I intended to write in the spec was that Never was most certainly a static type. If there were a hypothetical "fully statically typed" Python language, it would have Never as a static type (unlike Any). I was wishy washy about whether Never was a static subtype of Any, as an open question. (I think it could be, and I'm not aware of any problem with that.)
kmillikin commentedon Sep 11, 2023
And mutable fields are definitely invariant. One way to think of a mutable field with type
Ais that it has both a getter with signature() -> Aand a setter with signature(A) -> None. So the typeAoccurs both covariantly and contravariantly.DiscordLiz commentedon Sep 12, 2023
Under the definitions of that paper, and the definition of subtyping therin, Never participates in subtyping. The confusion here is that python type checkers aren't checking certain things (such as the variance of mutable fields of sub-classes) so with the way type checkers are treating subtyping by their behavior, Never shouldn't be considered to participate in subtyping.
One of the two needs to change here for this problem to go away.
mikeshardmind commentedon Sep 12, 2023
Considering that we probably want it to remain the case that Never is uninhabited, I think the set-theoretic definition of Never is more useful for any formalization. This would have Never participate in subtyping behavior as a subset of all type specifications (sets of types) but not as a subtype of individual static types (see what you pointed out about the undefinable nature of concretization for this case.) The distinction here may not matter if other things that type checkers aren't checking get checked, but I think having that distinction makes definitions of other things simpler, such as those of Union, Intersection (not yet added), Not (not yet added) as the behavior of Never becomes a natural dual to the behavior of
object(though not of Any)kmillikin commentedon Sep 12, 2023
I think there is still a misunderstanding.
The set-theoretic interpretation of static types is that static types loosely denote sets of values. A static type
Tought to be a subtype of a static typeSif the set of values denoted byTis a subset of the set of values denoted byS.Neveris a static type which denotes the empty set of values. Consequently,Neverought to be a subtype of every static type. This is what I (intended to) wrote in the draft spec. Note that this (what I've written above) is exactly dual toobject.It's really kind of an open question of
Neveris a subtype ofAny. On the one hand, it seems it should be. If we informally think ofAnyas an unknown static type, thenNeveris certainly a subtype of whatever that type is. On the other hand, all the gradual typing literature either treatsAnyas only a subtype of itself (to ensure subtyping is reflexive, though to be fair I don't know if any of these systems have top and bottom types) or else treats it as not even in the domain of subtyping (the AGT approach).What I wrote in the draft spec was that
Neverwas not a subtype ofAny, though there was some pushback in the comments. I chose this because I wanted the consequence that the unionAny | Neverwas not equivalent to the typeAny.I'm not sure what you mean by "type specifications", I think we need to define the term.
And AGT-style concretization is simple for
Never: concretization ofNeveris {Never} (the singleton set containingNever). What I meant to write is that abstraction (mapping a set of static types to a gradual type) of the empty set of static types is undefined in AGT. The reason is probably just because they didn't consider it. It just doesn't arise, even with unions, intersections, and negations (negations of static types only).kmillikin commentedon Sep 12, 2023
I think the clear solution for a Python typing spec is that class signatures are checked for invalid overrides and that the types of mutable fields are invariant. This is sort of recognized already for special cases, like
TypedDict. I would rather write this than to try to patch a symptom of the problem with a weird interpretation ofNever.Checkers are of course free to implement whatever they want.
randolf-scholz commentedon Sep 12, 2023
In the intersection discussions we came to the conclusion that
Any & Tshould be an irreducible form (e.g. simply by stating that the simplification rules for unions only apply to regular types with regular types, and gradual types with gradual types, but not for mixed cases), the same could simply be specified forAny | T. If I remember correctly, Eric said that internally, typecheckers already behaves this way. Although it seems thatpyrightspecial casesNever:randolf-scholz commentedon Sep 12, 2023
To come back to the issue. The point is that LSP aka behavioral subtyping is much stronger than mere structural subtyping. In particular the rules
are blatantly violated when a subclass annotates a return value as
Neverwhen the parent didn't. The new formalization of the typing spec should go into detail what precisely the contract is when annotations are made.What is promised when one writes:
Foohave a methodbarwhich returns instances ofstrin finite time.Foohave a methodbarwhich returns instances ofstror raises an exception or loops forever.Fooare such that if the attributebaris accessed, either it loops forever, raises an exception, or returns a method which either returns an instance ofstr, raises an exception, or loops forever.The current way things are checked corresponds to ③, because subclasses can override the return type with
Neveror can override the whole method withNever. But I think most people most of the time want ①.Implementing full (LSP-exception) would require typed exceptions, which are possibly not wanted. But a simple solution would be an augmented rule:
Despite
Neverbeing a structual subtype of any type, it is not a behavioral subtype any type. Therefore, typecheckers should only allow substitutingNeverwithNever, but raise an error if another type is substituted byNever.kmillikin commentedon Sep 12, 2023
I actually would not try to define any reductions on types. We can simply say that
float | intandfloatare subtypes of each other as a consequence of the definition of subtyping without requiring that a typechecker rewrite one to the other.The subtyping rule for unions that I wrote in the spec uses (plain) subtyping, so for a type such as
int,intis a subtype ofAny | intbutAny | intis not a subtype ofAnyorint. I claim that this is what we want.I don't really know what you mean by "simplification rules for unions only apply to ... gradual types with gradual types". This is a union of two gradual types:
Any | dict[str, Any]. And we have that bothAnyis a consistent subtype ofdict[str, Any]and vice versa. So is it even well-defined how you would "simplify" that? And why do we care?(And it seems warty that we wouldn't do the same thing, whatever it is, to
Any | int.intis both a static type and a gradual type, because every static type is a gradual type. So you'd need a notion of a non-static gradual type.)Special cases add up and I don't see much value in terms of what the type system can do.
randolf-scholz commentedon Sep 12, 2023
Oh, I thought in the new document, gradual types refer to
Anyand types that "contain"Any(list[Any],dict[str, Any], etc.):so
intwould not be a gradual type according to this definition.But the draft does define a reduction rule:
In the example
Any | dict[str, Any]we have, using the language from the draft:Any ~< dict[str, Any]andAny ~< AnyandAny <: Any, but notAny <: dict[str, Any]. Ergo, if the reduction rule requires<:and not just~<, thenAny | dict[str, Any]is irreducible. That's all I am saying. Well, possibly if someone defines a nominal subclass ofAny(which is possible since 3.11), then unions between such subclasses ofAnyandAnycould be simplified as well.kmillikin commentedon Sep 12, 2023
Python types don't say anything about exceptions or postconditions, so we really can't talk about them meaningfully here. I wouldn't call either of those "blatantly" violated by changing a return type to
Never. We simply don't know if they're violated or not.Are you proposing to allow:
but forbid:
I don't think that really makes sense. The typing of
C.foois a perfectly good override ofA.foo. (It's better than the typing ofB .foo, because if we have an instance ofCwe can know statically that it's not intended to return.)kmillikin commentedon Sep 12, 2023
Obviously I have to be even more careful with my writing. The draft spec does not intend to define such a reduction rule.
I give two rules for subtyping of unions. Then I argues in non-normative text that these are enough to subsume the more complicated properties defined in the PEPs, because all of those properties are consequences of the simple definition. "Note that we don't say that subtypes must be removed...."
randolf-scholz commentedon Sep 12, 2023
Is it perfectly good, though? You can't use
BorCmeaningfully as substitutes forAwithout wrapping everything intotry-exceptblocks. Putting instances ofBorCinto a function that expectsAprobably won't work. The typing ofBis also arguably better due to the semantic meaning ofNotImplementedError. What I propose would boil down toNotice how the error should be raised in both cases, but at different lines. So the proposed rule is actually allowing neither
BnorC. From a pragmatic point of view, it should only flagBifNeveris returned unconditionally. Playing devil's advocate, what about this one:Is this also a perfectly good override?
randolf-scholz commentedon Sep 12, 2023
Well, that's what I was arguing in #1458 (comment), that most developers, most of the time, likely want an annotation to mean that there is no violation. It feels weird that you argue that the status quo states X (=③) when the argument is it should state Y (=①) instead. I was expecting arguments in favor of *why* ③ is a good idea.
kmillikin commentedon Sep 12, 2023
We're just talking in circles. Take a step back and consider: the things that we can statically decide about Python programs are limited (your #1 isn't even decidable). The type system we have is unsound, and by design. We can complicate the type system arbitrarily much, but there is a point of vanishing returns. We really want an "ergonomic" design that is easy to explain, easy to understand, and easy to implement correctly.
I am advocating to keep the type system simple and understandable for both programmers and implementers. Avoid special cases. (Example: we can't in general decide if a function raises different exceptions than another, so we shouldn't conclude as a special case that a function with
Neveras a return type definitely does raise different exceptions than any other function.)randolf-scholz commentedon Sep 12, 2023
It's about what promise is made by a type annotation. The promise made by ③ is pretty useless in practice, I don't know anyone who uses this as their mental model to reason about code. The decidability is irrelevant here, a type-checker has no business attempting to infer whether code terminates and actually returns a value. This is done by the human brain who wrote the type-annotation. The argument is that an annotation like
intis a promise that this code, under regular circumstances, returns an instance ofint. A subclass that unconditionally raises an exception instead is not a proper substitute and will make your code fail.You are essentially arguing that the static type shouldn't warn me even if it can detect a program failure ahead of time.
mikeshardmind commentedon Sep 12, 2023
@kmillikin The problem comes in at mutable attributes. Subclasses should not be able to be more or less specific in the typing for mutable fields. As far as I can tell, all current type checkers allow this, and mypy has an open issue stating this should not be allowed going back to 2017.
Annotations are sometimes a two-way street. It isn't always just what is provided, but what can be assigned.
This should be fine, this breaks no expectations:
But
is not, because
breaks any reliance BNotFine would have on the subclass. So the definition of that subclass itself is unsound as a drop in replacement for the base class, and people should not be allowed to do this, but instead use a generic for this pattern:
And this would only be safe for use in functions expecting an invariant match on the generic.
This example extends to Never (Swap in
Neverfor eachIntSubclassFromNumericLibrary) without any special casing of Never, but I wanted to present it without Never due to the lack of specification of Never's specific subtyping behavior.The problem of Never's (lack of) specification may be a red herring here. The larger issue that has been left known broken by mypy since 2017, and that other type checkers have replicated clouded how people were interpreting subtyping behavior absent a specification.
kmillikin commentedon Sep 12, 2023
I do understand that. As I wrote above,
BNotFineshould be an invalid override ofANotFineand that should be a static type error.You will not fix this problem by tweaking the semantics of
Never.DiscordLiz commentedon Sep 12, 2023
@kmillikin so what's the path forward here for people working on anything more advanced that needs to interact with this if the whole ecosystem is wrong about something so basic and there isn't a specification to work from, only informal documents, various people's perspectives on which models of type systems python is best modeled by?
I'd like to see intersections added to python, but having good examples of how they should behave and even having good rules without special cases is hard when there is no specification, and the implementations are all wrong about more basic things.
mikeshardmind commentedon Sep 12, 2023
@DiscordLiz We get the ecosystem fixed on the basics (I've just now opened an issue for pyright, there's an open issue already for mypy, and I'll look into triple-checking that pytype and pyre also have this issue), and we work on the underlying specification first
We have to spend time on the foundations first.
kmillikin commentedon Sep 12, 2023
@DiscordLiz that was the subject of my talk at the Pycon US Typing Summit this year. We are in a bad position where we have multiple implementations and no specifications. This is not good for users, it's not good for implementers, and it's not good for designers of new typing features.
Unfortunately, I don't think we were able to get recordings of the Typing Summit talks.
My suggestion still is: we finish the simple subtyping specification, get a sponsor, make it a PEP, get it approved. Then (actually in parallel) we do the same thing for Part II: signature checking. This includes signature subtyping, override checking, and specification of how generic functions are implicitly specialized. We do this with input and buy-in from the implementations.
DiscordLiz commentedon Sep 12, 2023
@kmillikin Well, I'm still somewhat willing to help with an effort on that, but I raised a few points earlier about that. I think most importantly, the type system needs a living reference doc that is kept up to date and which is strict in it's wording. Not just a collection of peps, but that each pep that adds to or modifies the behavior of the type system should also update the living specification. This gives a clear single source of truth without ambiguity of how various peps should resolve each other. If something new is added to the document, it is up to those adding it to ensure it isn't in conflict. This doesn't lead to people looking to potentially flawed implementations for the correct behavior.
quoting myself from earlier rather than just reference it: (This was a set of "I'm interested in helping with formalization, but conditional on these things")
@erictraut also indicated that formalization of the existing parts of the type system should be done holistically, not in parts earlier in this thread, so I'm not sure how that interacts with your idea of splitting it into the subtyping behavior and then everything else. I think it is more natural to do everything at once to ensure consistency of definitions.
Days later edit...
After seeing how some of these issues have played out, I'm not actually interested in working on anything involving python typing anymore. It's amazing how trying to make typing "for everyone" really makes it feel bad for everyone, instead of just making it a good experience for the people who want it.
dimaqq commentedon Sep 26, 2023
That's a very narrow view, in my opinion. Subclasses are used for many things, drop-in replacement being only one of them.
Then again, arguably LSP doesn't quite mesh perfectly with dynamic, duck-typed languages. It's a tool to think about a program, but it's not the only tool?
leycec commentedon Jan 22, 2026
Necrobump + lolbro.
typing.Never!? INeverheard of thisnonsensewonderful type hint that will surely radically transform the face of... oh. Wait. It's just atyping.NoReturnalias, huh? Much better name to be sure. Still super-lame, though.It's even lamer that "
Neverwas added without a PEP". That's some grade-A QA BS right there. When you're adding newtypingsemantics without a PEP, you just know you've committed a grave sin and are about to embark on an even worse journey into the bowels of non-standard QA slop. You are now thinking:Not quite. From a casual reading of the literally five billion heated comments where reputable Pythonistas start mudslinging
vitriolic hatepolite disagreement at one another above, we can infer that nobody knows what they're talking about when they talk about eithertyping.Neverortyping.NoReturn, because (...waitforit) nothing was standardized. No PEP was authored. No peer review was performed. No community consensus was achieved. Nonetheless, for spurious reasons that fail to pass scrutiny, pure static type-checkers started making up seemingly pseudo-random ad-hoc semantics extending the behaviour of bothtyping.Neverandtyping.NoReturnwithout anyone's consent or buy-in.According to PEP 484,
typing.NoReturnand thustyping.Neveris only valid as the return type hint of a callable. According to this thread, that's no longer true. In particular...Attributes +
typing.Never= Can't Touch ThisApparently, you can also now annotate arbitrary attributes by
typing.Neverand thustyping.NoReturn. Of course, annotating an attribute bytyping.NoReturn... makes absolutely no sense. Apparently, static type-checkers have quietly supported this since Python 3.11 without telling anyone. Of course, this is awful. Apparently, this is now fine:As the above example demonstrates, "arbitrary attributes" now apparently means:
typing.Never. I'm unclear whether they have any demonstrable purpose. Maybe they do? They can be declared (and thus documented by a subsequent docstring), but they cannot be defined. So maybe that's the practical real-world utility? Documentation-only attributes? No idea. The fact they're so weird (as well as non-standard) probably explains why no @beartype user has ever complained abouttyping.Neverbefore.typing.Never. Apparently, this includes both PEP 557-compliant@dataclass-decorated dataclass fields and standard class variables. I'm still unclear whether they have any demonstrable purpose. They... probably don't.typingdo be like that.Unions +
typing.Never= u wot m8tApparently, both PEP 484- and 604-compliant unions can also be subscripted by
typing.Never. Apparently, in this context,typing.Nevereffectively implies the empty set ∅ and is thus conditionally ignorable. That is:Again, this is all pretty lame. What's the real-world use case for any of this? No idea. No one else has any idea either. @beartype's LLM-centric audience only cares about practical QA that yields tangible benefits. I share that obsession. I thus chortle spittle all over my keyboard as this thread descends into ever-increasing bouts of bike-shedding.
Anything Else? Probably. But Does Anyone Care?
I'm now wondering if you can subscript literally any subscriptable hint by
typing.Never. What happens?After all, you can subscript literally any subscriptable hint by
typing.Any. PEP 484 standardized that meaning in a sensible way. For any type hint factoryF,F[Any] == Fis semantically true. That is, any type hint factory subscripted bytyping.Anysemantically reduces to just that factory unsubscripted. Thus:Above, we claimed without evidence that "
typing.Nevereffectively implies the empty set ∅." That (possibly) being the case, it should thus be permissible to subscript any PEP 484- or 585-compliant container hint bytyping.Never. SinceNever == ∅, the semantic meaning would then be "An empty instance of that container." That is:Honestly, those are the only practical real-world use cases for
typing.NeverI can think of. They're probably also the only use cases fortyping.Nevernot actually supported by pure static type-checkers. Being able to enforce container emptiness has pragmatic merit, though. It's always been a bit silly that you can type-check only empty tuples. Why not empty everything else, too? Orthogonality demands it! Actually, orthogonality doesn't care. And neither does anyone else. Why am I even typing all of this out... Why!?typing.NoReturn: It No Longer Makes Sensetyping.Neveris such an obviously more suitable, readable, and intelligible name thantyping.NoReturnthat...typing.NoReturnshould be officially deprecated. Right? What's even the point oftyping.NoReturnif it's now imposing all of these other tangentially unrelated constraints that have absolutely nothing to do with function returns anymore?None. That's the obvious answer.
typing.NoReturnno longer has a reason to live. Let's officially bringtyping.NoReturnout back behind the woodshed. Its days are numbered. It's not a big number, either.Emptiness is a place in my heart. But Hell is a place on python/typing. 😄 -> 😭
[-]Issue with Never vs LSP[/-][+]NoReturn and Never are underspecified in the spec[/+]mikeshardmind commentedon Jan 23, 2026
@leycec There's a slight detail that seems to have been lost along the way. If you were correct about what typing.Never indicates, the rest of the post would be spot on about the nonsensical nature.
You're operating at the wrong level here, thankfully set-theoretic typing doesn't work this way, but I'll be one of the first to admit that our current terminology is not accessible to those not already deep in the weeds.
Never as a type annotation indicates the empty set of types, not that the value is an empty set.
Functions that never return a value (can only raise) can (and should) be typed as such, because there is no type at all for a value that doesn't exist.