haskell - GHC 编译时崩溃

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 回应:

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

出了什么问题？

Answer 1

我认为这与一个已知的错误有关。请参阅 ghc 手册第 14.2 节:

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

我将在此处重现相关部分:

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.

换句话说，当您在负数位置(即函数的参数)使用递归时，就会出现此错误。从手册来看，他们似乎无意修复此问题。