GHC loops on compiling with optimizations

[noschinl]

When compiling the snippet below with optimizations enabled (i.e. ghc -O test.hs), GHC does not seem to terminate. This happens with at least 7.0.3 and 7.0.4. Without optimizations, it builds fine.

data A = A Int

class C a where 
    fromHsk :: C a => a -> Int

instance C Int where 
    fromHsk = fromHsk

instance C A where 
    fromHsk (A s) = fromHsk s

main = undefined

When building this example with GHC 6.12.4, it fails with a complaint about the bogus type constraints in the declaration of fromHsk:

test.hs:3:0:
    All of the type variables in the constraint `C a'
    are already in scope (at least one must be universally quantified here)
        (Use -XFlexibleContexts to lift this restriction)
    When checking the class method: fromHsk :: (C a) => a -> Int
    In the class declaration for `C'

After removing these unneeded constraint (i.e. changing the declaration of fromHsk to fromHsk :: a -> Int, the snippet above builds even with GHC 7.0.4 and optimizations.

[noschinl]

ghc -v -dcore-lint -O test.hs

[simonpj]

Interesting example! This program should diverge, of course, but it should not do so at runtime. Yet it turns out to be a disguised case of GHC's well-known compile-time divergence bug (User manual 12.2.1, bullet 3).

Here is the desugaring of the program after dictionaries have become explicit:

data C a = MkC (C a -> Int)

fH :: C Int -> Int
fH x = case x of { MkC g -> g x }

fCInt :: C Int   -- The instance decl for (C Int) gives this
fCInt = MkC fH

Notice that

• None of these definitions is recursive
• But the data type C a has a (C a) on the left of an arrow.

Now consider evaluating

     fH fCInt

--> (inline fH)
    case fCInt of MkC g -> g fCInt

--> (inline fCInt and eliminate the case)
    fH fCInt

and so on forever...

It's a classic example of the Russell-paradox loop. The manual claims this "never happens in practice" and I guess this bug report is a counter-example! However, it's not easy to fix this particular loop; and as you found, it's not a program you want to write anyway.

See also #3872

[simonpj]

See also #5448