GHC crashes while compiling

Question

module Main where

newtype Rec a b = Rec {deRec :: Rec a b -> a}

infixl 1 >|>
infixl 1 <|<
(>|>) = Rec
(<|<) (Rec x) = x

fix f = (\x -> f (x <|< x)) (Rec (\x -> f (x <|< x)))
factorial = fix (\f x -> if x<=1 then 1 else x*f(x-1))

main = do 
   x <- getLine
   putStrLn (show (factorial (read x)))

GHC response:

ghc: panic! (the 'impossible' happened)
  (GHC version 7.6.3 for x86_64-apple-darwin):
    Simplifier ticks exhausted
    When trying UnfoldingDone a_sMx{v} [lid]
    To increase the limit, use -fsimpl-tick-factor=N (default 100)
    If you need to do this, let GHC HQ know, and what factor you needed
    To see detailed counts use -ddump-simpl-stats
    Total ticks: 7121

Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug

What's wrong?

I can reproduce this with Ubuntu (GHC version 7.6.3 for x86_64-unknown-linux). I think you have no reason not to report it. I'd report it, but as it's your bug, I'll leave the credits up to you. However, this might be only a case of increasing -fsimpl-tick-factor — Uli Köhler
– Uli Köhler, Commented Mar 2, 2014 at 4:15
The bug still occurs if replacing everything inside main with print "foo" and removing factorial. — Uli Köhler
– Uli Köhler, Commented Mar 2, 2014 at 4:17
With -fsimpl-tick-factor=25000 (250 times the default value!) the error still occurs. More than that causes thrashing for me. Looks like infinite iterative unfolding of some of your constructs. Where did you get that code from (is it your own?) — Uli Köhler
– Uli Köhler, Commented Mar 2, 2014 at 4:24
This is indeed quite strange. To my knowledge, the relevant optimizer code is the same in GHC as it is in GHCi. — Uli Köhler
– Uli Köhler, Commented Mar 2, 2014 at 4:28

Gabriella Gonzalez · Accepted Answer · 2014-03-03 17:13:22Z

13

I think this is related to a known bug. See Section 14.2 of the ghc manual:

http://www.haskell.org/ghc/docs/7.6.2/html/users_guide/bugs.html

I'll reproduce the relevant section here:

GHC's inliner can be persuaded into non-termination using the standard way to encode recursion via a data type:

data U = MkU (U -> Bool)

russel :: U -> Bool
russel u@(MkU p) = not $ p u

x :: Bool
x = russel (MkU russel)

We have never found another class of programs, other than this contrived one, that makes GHC diverge, and fixing the problem would impose an extra overhead on every compilation. So the bug remains un-fixed. There is more background in Secrets of the GHC inliner.

In other words, this bug arises when you use recursion in the negative position (i.e. the argument of a function). From the manual, it appears that they have no intention of fixing this.

edited Mar 3, 2014 at 17:13

answered Mar 2, 2014 at 5:46

Gabriella Gonzalez

35.2k3 gold badges80 silver badges138 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Antal Spector-Zabusky Over a year ago

You linked to the 6.12 manual; that text is still there, unchanged, in the 7.6.2 user manual, although the section it's in is now numbered 14.2. (Also, here's the Secrets of the GHC inliner link.)

Artem Pelenitsyn · Accepted Answer · 2016-04-18 07:32:24Z

1

As it was mentioned earlier, the problem arises when GHC's inliner working with function with parameters of recursive types. This can be workarounded with NOINLINE pragma. In your case:

{-# NOINLINE (<|<) #-}

answered Apr 18, 2016 at 7:32

Artem Pelenitsyn

2,59822 silver badges38 bronze badges

Collectives™ on Stack Overflow

GHC crashes while compiling

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related