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

出了什么问题？

- ThePiercingPrince

---

如果用 print "foo" 替换 main 函数内的所有内容并删除 factorial，该错误仍然会发生。 - Uli Köhler

@UliKöhler 这是我的代码，它在 GHCi 中运行良好。 - ThePiercingPrince

这确实很奇怪。据我所知，在 GHC 和 GHCi 中，相关的优化器代码是相同的。 - Uli Köhler

这是一个已知的问题。 GHC无法处理具有负递归使用的newtype。 - Philip JF

看起来像是简化器问题的变种，这个问题已经有文档记录了。 - augustss

Answer 1

我认为这与一个已知的漏洞相关。请参阅ghc手册的第14.2节：

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

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

GHC的内联器可以通过使用数据类型编码递归的标准方式来被说服进入非终止状态：

data U = MkU (U -> Bool)

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

x :: Bool
x = russel (MkU russel)

除了这个人为制造的程序，我们从未发现其他程序类别会导致 GHC 发散，而修复此问题将对每次编译施加额外的开销。因此这个bug仍然没有被解决。有更多背景信息请参见GHC内联器的秘密。

换句话说，当你在负位置（即函数的参数）使用递归时，就会出现这个bug。从手册上来看，他们似乎并没有打算修复这个问题。

- Gabriella Gonzalez

---

你链接到了6.12手册; 该文本仍然存在于7.6.2用户手册中，尽管它所在的部分现在编号为14.2。（此外，这是GHC内联器秘密链接。） - Antal Spector-Zabusky

Answer 2

正如之前所提到的，当GHC的内联器与具有递归类型参数的函数一起使用时会出现问题。这可以通过使用NOINLINE编译指示符进行解决。在您的情况下：

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

- Artem Pelenitsyn