#9106 closed bug (fixed)

GHC Panic related to functional dependencies - kindFunResult

Reported by: yuriy Owned by:
Priority: normal Milestone: 7.8.3
Component: Compiler Version: 7.8.2
Keywords: Cc:
Operating System: Windows Architecture: x86
Type of failure: Compile-time crash Test Case: polykinds/T9106
Blocked By: Blocking:
Related Tickets: Differential Revisions:

Description

Minimal example:

{-# LANGUAGE 
  MultiParamTypeClasses, DataKinds, FunctionalDependencies, TypeOperators,
  KindSignatures, PolyKinds, FlexibleInstances, FlexibleContexts, UndecidableInstances #-}

import GHC.TypeLits 

data Proxy (a :: k) = Proxy 

class FunctorN n f a fa | n f a -> fa where 
  fmapn :: Proxy n -> Proxy f -> (a -> a) -> fa -> fa

instance FunctorN 0 f a a where 
  fmapn _ _ a = a 

instance (Functor f, FunctorN (n - 1) f a fa) => FunctorN n f a (f fa) where 
  fmapn _ pf f = fmap (fmapn (Proxy :: Proxy (n-1)) pf f)

Crashes with ghc and ghci:

>ghc test
[1 of 1] Compiling Main             ( test.hs, test.o )
ghc.exe: panic! (the 'impossible' happened)
  (GHC version 7.8.20140130 for x86_64-unknown-mingw32):
        kindFunResult k{tv azb} [sk]

>ghci test
GHCi, version 7.8.20140130: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( test.hs, interpreted )
ghc.exe: panic! (the 'impossible' happened)
  (GHC version 7.8.20140130 for x86_64-unknown-mingw32):
        kindFunResult k{tv aPm} [sk]

Removing the functional dependency makes the code compile.

Attachments (3)

test.hs (538 bytes) - added by yuriy 16 months ago.
File containing the source which causes the crash.
verbose_output.txt (2.5 KB) - added by yuriy 16 months ago.
Output of ghc compilation with -v3
nobug.hs (557 bytes) - added by yuriy 16 months ago.
Slight modification removes the bug

Download all attachments as: .zip

Change History (11)

Changed 16 months ago by yuriy

File containing the source which causes the crash.

Changed 16 months ago by yuriy

Output of ghc compilation with -v3

Changed 16 months ago by yuriy

Slight modification removes the bug

comment:1 Changed 16 months ago by yuriy

The same code without GHC.TypeLits works:

{-# LANGUAGE 
  MultiParamTypeClasses, DataKinds, FunctionalDependencies, TypeOperators,
  KindSignatures, PolyKinds, FlexibleInstances, FlexibleContexts, UndecidableInstances,
  ScopedTypeVariables #-}

data Proxy (a :: k) = Proxy 

data Nat = Z | P Nat 

class FunctorN n f a fa | n f a -> fa where 
  fmapn :: Proxy n -> Proxy f -> (a -> a) -> fa -> fa

instance FunctorN Z f a a where 
  fmapn _ _ a = a 

instance (Functor f, FunctorN n f a fa) => FunctorN (P n) f a (f fa) where 
  fmapn _ pf f = fmap (fmapn (Proxy :: Proxy n) pf f)

comment:2 Changed 16 months ago by darchon

Also annotating the Z instance with a monomorphic kind, (f :: *), makes the GHC.TypeLits version work:

{-# LANGUAGE
  MultiParamTypeClasses, DataKinds, FunctionalDependencies, TypeOperators,
  KindSignatures, PolyKinds, FlexibleInstances, FlexibleContexts, UndecidableInstances, ScopedTypeVariables #-}
module FunctorN where

import GHC.TypeLits

data Proxy (a :: k) = Proxy

class FunctorN n f a fa | n f a -> fa where
  fmapn :: Proxy n -> Proxy f -> (a -> a) -> fa -> fa

instance FunctorN 0 (f :: *) a a where
  fmapn _ _ a = a

instance (Functor f, FunctorN (n - 1) f a fa) => FunctorN n f a (f fa) where
  fmapn _ pf f = fmap (fmapn (Proxy :: Proxy (n-1)) pf f)

Without the annotation, f is poly-kinded in the first FunctorN instance (it is * -> * in the second instance), and the kindFunResult error seems to be related to this kind-variable. That is when I annotate the f in the first FunctorN instance as (f :: p) I get:

ghc: panic! (the 'impossible' happened)
  (GHC version 7.8.2 for x86_64-apple-darwin):
	kindFunResult p{tv a1FO} [sk]
Last edited 16 months ago by darchon (previous) (diff)

comment:3 Changed 16 months ago by darchon

The type family version also works:

{-# LANGUAGE DataKinds, FlexibleInstances, MultiParamTypeClasses, PolyKinds,
    ScopedTypeVariables, TypeFamilies, TypeOperators, UndecidableInstances #-}
module FunctorN where

import GHC.TypeLits

data Proxy (a :: k) = Proxy

type family F n f a
  where
    F 0 f a = a
    F n f a = f (F (n-1) f a)

class F n f a ~ fa => FunctorN n f a fa where
  fmapn :: Proxy n -> Proxy f -> (a -> a) -> fa -> fa

instance FunctorN 0 f a a where
  fmapn _ _ a  = a

instance ( Functor f, FunctorN (n-1) f a fa, F (n - 1) f a ~ fa
         , F n f a ~ f fa) => FunctorN n f a (f fa) where
  fmapn _ pf f = fmap (fmapn (Proxy :: Proxy (n-1)) pf f)

test :: Maybe (Maybe (Maybe Int))
test = fmapn (Proxy :: Proxy 3) (Proxy :: Proxy Maybe) (+1)
             (Just (Just (Just 3)))

comment:4 Changed 16 months ago by simonpj

I'm working on this... I know more or less what's happening. Thanks for the examples

comment:5 Changed 16 months ago by Simon Peyton Jones <simonpj@…>

In d8d97113c24e7216be36c9cdfc58e91f26528f06/ghc:

Make the unifier a fixpoint even for the free kind vars of a tyvar

The (pure) unifier tcUnifyTys returns an idempotent substitution.
But previously the kinds of type variables free in the range of
the subst could have un-substituted kind variables.

This patch fixes that, fixing Trac #9106.

See Note [Finding the substitution fixpoint] in Unify

comment:6 Changed 16 months ago by simonpj

  • Status changed from new to merge
  • Test Case set to polykinds/T9106

Thank you. I've fixed the crash. Now we get

T9106.hs:13:10:
    Illegal instance declaration for ‘FunctorN n f a (f fa)’
      The liberal coverage condition fails in class ‘FunctorN’
        for functional dependency: ‘n f a -> fa’
      Reason: lhs types ‘n’, ‘f’, ‘a’
        do not jointly determine rhs type ‘f fa’
    In the instance declaration for ‘FunctorN n f a (f fa)’

which looks right to me.

Simon

comment:7 Changed 15 months ago by thoughtpolice

  • Milestone set to 7.8.3

comment:8 Changed 15 months ago by thoughtpolice

  • Resolution set to fixed
  • Status changed from merge to closed
Note: See TracTickets for help on using tickets.