Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

GHC crashes while compiling

Tags:

haskell

ghc

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?

like image 946
ThePiercingPrince Avatar asked Mar 02 '14 04:03

ThePiercingPrince


2 Answers

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.

like image 166
Gabriella Gonzalez Avatar answered Oct 20 '22 14:10

Gabriella Gonzalez


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 (<|<) #-}
like image 25
Artem Pelenitsyn Avatar answered Oct 20 '22 15:10

Artem Pelenitsyn