6

当我第一次阅读有关-XUndecidableInstances.

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

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

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

但很公平,因为我一直在脑海中保留“不可判定的实例可能会使编译器挂起”。

当我在 CodeGolf.SE 上阅读这个挑战时,它是从哪里获得的,要求提供可以无限挂起编译器的代码。好吧,这听起来像是在不确定的情况下工作,对吧?

事实证明我无法让他们这样做。以下内容立即编译,至少从 GHC-7.10 开始:

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

我什至可以使用类方法,它们只会在运行时导致循环:

{-# 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)

同样,在编译时没有问题。

那么,在解析不可判定的类型类实例时,实际上需要什么来挂起编译器呢?

4

3 回答 3

10

我想我从来没有真正挂过编译器。我可以通过修改您的第一个示例来使其堆栈溢出。似乎有一些缓存正在进行,所以我们需要一个无限序列的唯一约束,例如

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 工作的人的意见。

于 2017-02-21T00:05:57.170 回答
6

获得“减少堆栈溢出”的最简单方法是使用类型族:

type family Loop where
  Loop = Loop

foo :: Loop
foo = True

我不知道在当前 GHC 上进行实际循环编译的直接方法。我记得使用 GHC 7.11 循环了几次,但我只记得一个可重现的细节:

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

但此后此问题已得到解决。

于 2017-02-21T00:20:57.203 回答
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

编辑:这确实是一个错误,已经在当前的 GHC 开发版本中修复。

于 2017-10-30T02:19:58.283 回答