不可判定的实例如何实际挂起编译器？

Question

当我第一次阅读严肃的 criticism on -XUndecidableInstances 时，我已经完全习惯了它，将其视为只是 删除 Haskell98 必须使编译器更易于实现的烦人限制.

事实上，我遇到过很多需要不可判定实例的应用程序，但 none 它们实际上导致了与不可判定性相关的任何问题。卢克的例子是有问题的，原因完全不同

class Group g where
  (%) :: g -> g -> g
  ...
instance Num g => Group g where
  ...

– 好吧，这显然会被任何适当的 Group 实例重叠，所以不确定性是我们最不担心的：这实际上是不确定性!

但公平地说，我一直把“不可判定的实例可能会挂起编译器”放在脑后。

当我阅读 this challenge on CodeGolf.SE 时获得它，要求获得会无限挂起编译器的代码。好吧，听起来像是针对不可判定实例的工作，对吧？

原来我无法让他们这样做。至少从 GHC-7.10 可以立即编译以下内容：

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
class C y
instance C y => C y
main = return ()

我什至可以使用 class 方法，它们只会在 运行时:

引起循环

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
class C y where y::y
instance C y => C y where y=z
z :: C y=>y; z=y
main = print (y :: Int)

但是运行时循环并不罕见，您可以在 Haskell98 中轻松编写这些代码。

我也尝试了不同的、不太直接的循环，例如

{-# LANGUAGE FlexibleContexts, UndecidableInstances #-}
data A x=A
data B x=B
class C y
instance C (A x) => C (B x)
instance C (B x) => C (A x)

同样，编译时没有问题。

那么，在解决不可判定类型 class 实例时，实际需要什么来挂起编译器？

Answer 1

我不认为我真的挂过编译器。我可以通过修改你的第一个例子让它堆栈溢出。似乎有一些缓存正在进行，所以我们需要一个无限序列的唯一约束，例如

data A x = A deriving (Show)
class C y where get :: y
instance (C (A (A a))) => C (A a) where
    get = A

main = print (get :: A ())

这给了我们

• Reduction stack overflow; size = 201
  When simplifying the following type:
    C (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A (A ())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
  Use -freduction-depth=0 to disable this check
  (any upper bound you could choose might fail unpredictably with
   minor updates to GHC, so disabling the check is recommended if
   you're sure that type checking should terminate)

它告诉你如果你真的想挂起来怎么才能挂起来。我的猜测是，如果你能在没有这个的情况下让它挂起，你就发现了一个错误。

我很想听听从事 GHC 工作的人的意见。

Answer 2

获得 "reduction stack overflow" 的最简单方法是使用类型族：

type family Loop where
  Loop = Loop

foo :: Loop
foo = True

我不知道在当前 GHC 上进行实际循环编译的直接方法。我记得在 GHC 7.11 中有过几次循环，但我只记得一个可重现的细节：

data T where
    T :: forall (t :: T). T

但这已经被修复了。

Answer 3

令我惊讶的是，UndecidableInstances 实际上可以挂起某些 GHC 版本。以下是为我完成的几行代码：

{-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TypeFamilies          #-}
{-# LANGUAGE UndecidableInstances  #-}
module Nested where

class Nested r ix where

type family Lower ix :: *

data LN

instance Nested LN (Lower ix) => Nested LN ix where

data L

instance Nested LN ix => Nested L ix where

当编译为库的一部分时（不是直接 ghc main.hs）此代码在 GHC 8.2.1 上无限期挂起

正如@luqui 所提到的，这看起来确实像是一个错误，因此已被报告为：https://ghc.haskell.org/trac/ghc/ticket/14402

编辑: 原来是个bug，目前开发版的GHC已经修复了

不可判定的实例如何实际挂起编译器？

How can undecidable instances actually hang the compiler?

haskell

halting-problem

typeclass

undecidable-instances