Opened 3 years ago

Last modified 3 years ago

#5400 new bug

GHC loops on compiling with optimizations

Reported by: noschinl Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.0.4
Keywords: Cc:
Operating System: Linux Architecture: x86_64 (amd64)
Type of failure: Compile-time crash Difficulty:
Test Case: Blocked By:
Blocking: Related Tickets:

Description

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.

Attachments (1)

ghc-v.log (2.7 KB) - added by noschinl 3 years ago.
ghc -v -dcore-lint -O test.hs

Download all attachments as: .zip

Change History (3)

Changed 3 years ago by noschinl

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

comment:1 Changed 3 years ago by simonpj

  • Milestone set to _|_

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

comment:2 Changed 3 years ago by simonpj

See also #5448

Note: See TracTickets for help on using tickets.