[GHC] #11203: Kind inference with SigTvs is wrong
#11203: Kind inference with SigTvs is wrong -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.2 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Consider {{{#!hs data SameKind :: k -> k -> * data Q (a :: k1) (b :: k2) c = MkQ (SameKind a b) }}} This code should be rejected. Yet it is accepted. The problem is that, when kind-checking a datatype declaration without a CUSK, GHC uses `SigTv`s for user-written kind variables. `SigTv`s are allowed to unify with other `SigTv`s, leading to incorrect behavior here. The motivating scenario is this: {{{#!hs data T (a :: k1) x = MkT (S a ()) data S (b :: k2) y = MkS (T b ()) }}} This program should be accepted. Neither type has a CUSK and therefore is not generalized before kind-checking the group. GHC must then unify `k1` and `k2`. If they were skolems, this unification would fail and this pair of definitions would be rejected. This ticket is identical in spirit to #9201, but that example has a CUSK and thus works. The bug can happen only when there is no CUSK. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11203> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11203: Kind inference with SigTvs is wrong -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): Use of `SigTv`s also sometimes gets in the way of `splitTelescopeTvs`, which depends on the kind variables in a tycon's kind having the same names as the `LHsQTyVars` in the tycon definitions. This is blocking `perf/compiler/T9872d` from compiling. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11203#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11203: Kind inference with SigTvs is wrong -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Richard Eisenberg <eir@…>): In [changeset:"6746549772c5cc0ac66c0fce562f297f4d4b80a2/ghc" 67465497/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="6746549772c5cc0ac66c0fce562f297f4d4b80a2" Add kind equalities to GHC. This implements the ideas originally put forward in "System FC with Explicit Kind Equality" (ICFP'13). There are several noteworthy changes with this patch: * We now have casts in types. These change the kind of a type. See new constructor `CastTy`. * All types and all constructors can be promoted. This includes GADT constructors. GADT pattern matches take place in type family equations. In Core, types can now be applied to coercions via the `CoercionTy` constructor. * Coercions can now be heterogeneous, relating types of different kinds. A coercion proving `t1 :: k1 ~ t2 :: k2` proves both that `t1` and `t2` are the same and also that `k1` and `k2` are the same. * The `Coercion` type has been significantly enhanced. The documentation in `docs/core-spec/core-spec.pdf` reflects the new reality. * The type of `*` is now `*`. No more `BOX`. * Users can write explicit kind variables in their code, anywhere they can write type variables. For backward compatibility, automatic inference of kind-variable binding is still permitted. * The new extension `TypeInType` turns on the new user-facing features. * Type families and synonyms are now promoted to kinds. This causes trouble with parsing `*`, leading to the somewhat awkward new `HsAppsTy` constructor for `HsType`. This is dispatched with in the renamer, where the kind `*` can be told apart from a type-level multiplication operator. Without `-XTypeInType` the old behavior persists. With `-XTypeInType`, you need to import `Data.Kind` to get `*`, also known as `Type`. * The kind-checking algorithms in TcHsType have been significantly rewritten to allow for enhanced kinds. * The new features are still quite experimental and may be in flux. * TODO: Several open tickets: #11195, #11196, #11197, #11198, #11203. * TODO: Update user manual. Tickets addressed: #9017, #9173, #7961, #10524, #8566, #11142. Updates Haddock submodule. }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11203#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11203: Kind inference with SigTvs is wrong -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): What is the situation on this ticket? Should it be on the list at [wiki:DependentTypes/Phase1]? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11203#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11203: Kind inference with SigTvs is wrong -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): Not quite. This problem existed before `TypeInType` and continues to exist. It's just that my (new) implementation of `tcTyClTyVars` gets thrown off the scent by the `SigTv`s. But I'm pretty sure I have a fix for that, totally orthogonal to any fix for this ticket. I'll get the (quite local) fix in soon. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11203#comment:4> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11203: Kind inference with SigTvs is wrong -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): Quite a bit of discussion has led to this general rule: * Two user-written type variables, both in scope at the same time, should always refer to distinct, unknown types. Note that this rule is, in fact, violated sometimes: {{{ f :: a -> a -> Int f (x :: b) (y :: c) = 3 }}} This definition is accepted, even though `b` and `c` share a scope and refer to the same type. Under the general rule, this should be rejected. Now that we have type wildcards, a user who really wanted to write something like `f` can use wildcards. Returning to the situation in the original ticket, the general rule would allow `S`/`T` and prevent `Q`, as desired. Now, how to implement: when creating a `SigTv`, we could record the set of variables in scope at the time. Then, whenever we unify a `SigTv` with another type, we just make sure that the other type can never unify with any of those variables. Specifically: let's write `SigTv{a,b}` to denote a `SigTv` type variable flavor (a `MetaInfo`) that cannot unify with `a` or `b`. A tyvar `b` with flavor `SigTv{vs}` may unify with a type `t` only when: 1. `t` is a type variable, `a`; AND 2. (`a` is a skolem; OR 3. `a` is a `SigTv{ws}` such that `ws` is a superset of `vs`) Note that `ws` and `vs` may contain other `SigTv`s that have unified; it might be necessary to zonk `ws` and `vs` before doing the superset check. I offer no justification for why my approach might work. But I think it would. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11203#comment:5> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11203: Kind inference with SigTvs is wrong -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Richard Eisenberg <eir@…>): In [changeset:"ae86eb9f72fa7220fe47ac54d6d21395691c1308/ghc" ae86eb9f/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="ae86eb9f72fa7220fe47ac54d6d21395691c1308" Fix tcTyClTyVars to handle SigTvs Previously, tcTyClTyVars required that the names of the LHsQTyVars matched up exactly with the names of the kind of the given TyCon. It now does a bit of matching up when necessary to relax this restriction. This commit enables a few tests that had previously been disabled. The shortcoming this addresses is discussed in #11203, but that ticket is not directly addressed here. Test case: polykinds/SigTvKinds, perf/compiler/T9872d }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11203#comment:6> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11203: Kind inference with SigTvs is wrong -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): The commit just pushed restores the (broken) behavior from before `TypeInType`, but does not address this ticket. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11203#comment:7> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11203: Kind inference with SigTvs is wrong -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): See #11453, which has several examples of weird behavior caused by this bug. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11203#comment:8> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11203: Kind inference with SigTvs is wrong -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * cc: RyanGlScott (added) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11203#comment:9> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11203: Kind inference with SigTvs is wrong -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 7.10.2 checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Simon Peyton Jones <simonpj@…>): In [changeset:"8361b2c5a9f7a00f0024f44a43b851998ae41e33/ghc" 8361b2c5/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="8361b2c5a9f7a00f0024f44a43b851998ae41e33" Fix SigTvs at the kind level This patch fixes two bugs in the treatment of SigTvs at the kind level: - We should always generalise them, never default them (Trac #14555, #14563) - We should check if they get unified with each other (Trac #11203) Both are described in TcHsType Note [Kind generalisation and SigTvs] }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11203#comment:11> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11203: Kind inference with SigTvs is wrong -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler (Type | Version: 7.10.2 checker) | Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: | polykinds/T11203 Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * status: new => closed * testcase: => polykinds/T11203 * resolution: => fixed Comment: Finally fixed! {{{ T11203.hs:7:24: error: • Couldn't match ‘k1’ with ‘k2’ • In the data declaration for ‘Q’ }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11203#comment:12> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11203: Kind inference with SigTvs is wrong -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler (Type | Version: 7.10.2 checker) | Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: | polykinds/T11203 Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Richard Eisenberg <rae@…>): In [changeset:"3910d3e2f8b3084f6f6de3d9aeb8d8ed20670245/ghc" 3910d3e2/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="3910d3e2f8b3084f6f6de3d9aeb8d8ed20670245" Add some commentary re: fix to #11203 The fix for #11203 prohibits duplicate SigTvs in non-CUSK kind signatures by checking for duplicates after type inference is done. This works well. GHC also checks for duplicate SigTvs after working with partial type signatures (another place where SigTvs arise). However, neither fix eliminates this whole class of problems (because doing so would be heavier than we would like). So, this comment adds a warning to users of newSigTyVar to be aware of problems with duplicates. }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11203#comment:13> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC