Skip to content

Impredicativity checking is fooled by a type synonym

Consider the following functions, which all instantiate undefined impredicatively:

{-# LANGUAGE RankNTypes #-}
module Bug where

a :: (forall a. a) -> ()
a = undefined

b :: (Show a => a) -> ()
b = undefined

type C = forall a. a
c :: C -> ()
c = undefined

type D a = Show a => a
d :: D a -> ()
d = undefined

a, b, and c will each fail to typecheck:

[1 of 1] Compiling Bug              ( Bug.hs, interpreted )

Bug.hs:5:5: error:
    • Cannot instantiate unification variable ‘a1’
      with a type involving polytypes: (forall a. a) -> ()
        GHC doesn't yet support impredicative polymorphism
    • In the expression: undefined
      In an equation for ‘a’: a = undefined
  |
5 | a = undefined
  |     ^^^^^^^^^

Bug.hs:8:5: error:
    • Cannot instantiate unification variable ‘a2’
      with a type involving polytypes: (Show a => a) -> ()
        GHC doesn't yet support impredicative polymorphism
    • In the expression: undefined
      In an equation for ‘b’: b = undefined
    • Relevant bindings include
        b :: (Show a => a) -> () (bound at Bug.hs:8:1)
  |
8 | b = undefined
  |     ^^^^^^^^^

Bug.hs:12:5: error:
    • Cannot instantiate unification variable ‘a0’
      with a type involving polytypes: C -> ()
        GHC doesn't yet support impredicative polymorphism
    • In the expression: undefined
      In an equation for ‘c’: c = undefined
   |
12 | c = undefined
   |     ^^^^^^^^^

Curiously, there is no error message for d. In fact, if you comment out a, b, and c, then d will typecheck! This is concerning, as d is just a variant of b with an extra type synonym thrown into the mix.

Why is it that c, which also uses a type synonym, is rejected, but d is accepted? It's ultimately because of GHC.Tc.Utils.Unify.preCheck, which powers GHC's impredicative instantiation checks. This part of preCheck is suspicious:

preCheck dflags ty_fam_ok tv ty
  = fast_check ty
  where
    ...

    fast_check :: TcType -> MetaTyVarUpdateResult ()
    ...
    fast_check (TyConApp tc tys)
      | bad_tc tc              = MTVU_Bad
      | otherwise              = mapM fast_check tys >> ok
    ...

    bad_tc :: TyCon -> Bool
    bad_tc tc
      | not (impredicative_ok || isTauTyCon tc)     = True
      | not (ty_fam_ok        || isFamFreeTyCon tc) = True
      | otherwise                                   = False

If bad_tc returns True, then that results in a TyConApp being flagged as impredicative. bad_tc first checks if impredicative_ok is True (i.e., if ImpredicativeTypes is enabled), and since that isn't the case in the program above, it checks isTauTyCon tc. For type synonyms like C and D, this checks if the RHS of the type synonym is a tau type, as defined by the isTauTy function:

-- @isTauTy@ tests if a type has no foralls
isTauTy :: Type -> Bool
isTauTy ty | Just ty' <- coreView ty = isTauTy ty'
isTauTy (TyVarTy _)           = True
isTauTy (LitTy {})            = True
isTauTy (TyConApp tc tys)     = all isTauTy tys && isTauTyCon tc
isTauTy (AppTy a b)           = isTauTy a && isTauTy b
isTauTy (FunTy _ a b)         = isTauTy a && isTauTy b
isTauTy (ForAllTy {})         = False
isTauTy (CastTy ty _)         = isTauTy ty
isTauTy (CoercionTy _)        = False  -- Not sure about this

However, isTauTy only checks if a type contains foralls, not contexts! As a result, C is flagged as impredicative, but D a is not.

I wonder if the definition of isTauTy should be expanded to detect higher-rank contexts in addition to higher-rank foralls? In other words, should the following change be applied?

diff --git a/compiler/GHC/Core/Type.hs b/compiler/GHC/Core/Type.hs
index 1e7af2d8cf..3cf4231480 100644
--- a/compiler/GHC/Core/Type.hs
+++ b/compiler/GHC/Core/Type.hs
@@ -1864,6 +1864,7 @@ isTauTy (TyVarTy _)           = True
 isTauTy (LitTy {})            = True
 isTauTy (TyConApp tc tys)     = all isTauTy tys && isTauTyCon tc
 isTauTy (AppTy a b)           = isTauTy a && isTauTy b
+isTauTy (FunTy InvisArg _ _)  = False
 isTauTy (FunTy _ a b)         = isTauTy a && isTauTy b
 isTauTy (ForAllTy {})         = False
 isTauTy (CastTy ty _)         = isTauTy ty

This change suffices to make d be flagged as impredicative, and it passes GHC's test suite to boot. But then again, I'm unclear on the origins of the term "tau type"—perhaps it's permissible for tau types to have higher-rank contexts? If so, this suggests that we'd need to implement a variant of isTauTy that checked for both contexts and foralls.

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information