Opened 2 years ago

Closed 6 hours ago

#11203 closed bug (fixed)

Kind inference with SigTvs is wrong

Reported by: goldfire Owned by:
Priority: normal Milestone:
Component: Compiler (Type checker) Version: 7.10.2
Keywords: Cc: RyanGlScott
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:

Description

Consider

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 SigTvs for user-written kind variables. SigTvs are allowed to unify with other SigTvs, leading to incorrect behavior here.

The motivating scenario is this:

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.

Change History (12)

comment:1 Changed 2 years ago by goldfire

Use of SigTvs 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.

comment:2 Changed 2 years ago by Richard Eisenberg <eir@…>

In 67465497/ghc:

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.

comment:3 Changed 2 years ago by simonpj

What is the situation on this ticket? Should it be on the list at DependentHaskell/Phase1?

Last edited 2 years ago by simonpj (previous) (diff)

comment:4 Changed 2 years ago 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 SigTvs. 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.

comment:5 Changed 2 years ago 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 SigTvs 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.

comment:6 Changed 2 years ago by Richard Eisenberg <eir@…>

In ae86eb9f/ghc:

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

comment:7 Changed 2 years ago by goldfire

The commit just pushed restores the (broken) behavior from before TypeInType, but does not address this ticket.

comment:8 Changed 2 years ago by goldfire

See #11453, which has several examples of weird behavior caused by this bug.

comment:9 Changed 2 years ago by RyanGlScott

Cc: RyanGlScott added

comment:10 Changed 23 months ago by thomie

Component: CompilerCompiler (Type checker)

comment:11 Changed 22 hours ago by Simon Peyton Jones <simonpj@…>

In 8361b2c5/ghc:

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]

comment:12 Changed 6 hours ago by simonpj

Resolution: fixed
Status: newclosed
Test Case: polykinds/T11203

Finally fixed!

T11203.hs:7:24: error:
    • Couldn't match ‘k1’ with ‘k2’
    • In the data declaration for ‘Q’
Note: See TracTickets for help on using tickets.