问题 GHC在多个范围内选择哪个词典?


请考虑以下示例:

import Data.Constraint

class Bar a where
  bar :: a -> a

foo :: (Bar a) => Dict (Bar a) -> a -> a
foo Dict = bar

GHC在选择a时使用字典有两种选择 Bar 例子 foo:它可以使用来自的字典 Bar a 约束 foo,或者它可以使用运行时 Dict 得到一本字典。看到 这个问题 例如字典对应的例子 不同 实例。

GHC使用哪种词典,为什么它是“正确的”选择?


11134
2018-04-08 01:00


起源



答案:


GHC选择一个,这是正确的选择。相同约束的任何两个字典应该是相等的。

重叠实体和非相干实体在破坏力方面基本相同;它们都会因设计而失去实例连贯性(程序中任何两个相同的约束都被同一个字典所满足)。 OverlappingInstances为您提供了更多的能力,可以根据具体情况确定哪些实例将被使用,但是当您将Dicts作为第一类值传递时,这并不是很有用。我只考虑使用OverlappingInstances,当我认为重叠实例在扩展上是等价的(例如,对于像Int这样的特定类型的更有效但是相同的实现),但即便如此,如果我足够关心性能来编写那个专门的实现,isn'如果它没有被使用,它是一个性能错误?

简而言之,如果您使用OverlappingInstances,则放弃向此处询问将选择哪个字典的权利。

现在,你可以在不使用OverlappingInstances的情况下破坏实例一致性。事实上,你可以在没有孤儿的情况下完成它,除了灵活实例之外没有任何扩展(可以说,当启用FlexibleInstances时,“孤儿”的定义是错误的)。这是一个非常长期存在的GHC错误,部分原因尚未解决,因为(a)它实际上不会直接导致任何人似乎知道的崩溃,并且(b)可能有很多程序实际上,它依赖于在程序的不同部分中为同一约束设置多个实例,这可能很难避免。

回到主题,原则上重要的是GHC可以选择它可用于满足约束的任何字典,因为即使它们应该是相等的,GHC可能比其他字段有更多关于它们的静态信息。你的例子有点太简单了,不能说明,但想象你传递了一个参数 bar;一般来说,GHC对通过的字典一无所知 Dict 因此它必须将此视为对未知函数的调用,但是您调用了 foo 在特定类型 T 有一个 Bar T 在范围内的实例,然后GHC会知道 bar 来自 Bar a 约束字典是 Tbar 并且可以生成对已知函数的调用,并可能内联 Tbar并因此进行更多优化。

在实践中,GHC目前并不聪明,它只使用最里面的字典。总是使用最外层的字典可能已经更好了。但是这样的情况下,有多个词典可供使用并不常见,所以我们没有很好的基准测试。


5
2018-04-08 16:27



然后人们可能会问为什么我们有两个扩展(不连贯/重叠)而不是一个。人们可能会觉得单独重叠仍然是“安全的”,只有不连贯的真正的麻烦才会开始。 - chi
“任何两个相同约束的词典应该是平等的。” - 应该是,但不是。请参阅我的回答,了解违反此声明的示例,而不使用不连贯或重叠的实例。 - Daniel Wagner
是的,这就是我失去实例连贯性的意思。 - Reid Barton


答案:


GHC选择一个,这是正确的选择。相同约束的任何两个字典应该是相等的。

重叠实体和非相干实体在破坏力方面基本相同;它们都会因设计而失去实例连贯性(程序中任何两个相同的约束都被同一个字典所满足)。 OverlappingInstances为您提供了更多的能力,可以根据具体情况确定哪些实例将被使用,但是当您将Dicts作为第一类值传递时,这并不是很有用。我只考虑使用OverlappingInstances,当我认为重叠实例在扩展上是等价的(例如,对于像Int这样的特定类型的更有效但是相同的实现),但即便如此,如果我足够关心性能来编写那个专门的实现,isn'如果它没有被使用,它是一个性能错误?

简而言之,如果您使用OverlappingInstances,则放弃向此处询问将选择哪个字典的权利。

现在,你可以在不使用OverlappingInstances的情况下破坏实例一致性。事实上,你可以在没有孤儿的情况下完成它,除了灵活实例之外没有任何扩展(可以说,当启用FlexibleInstances时,“孤儿”的定义是错误的)。这是一个非常长期存在的GHC错误,部分原因尚未解决,因为(a)它实际上不会直接导致任何人似乎知道的崩溃,并且(b)可能有很多程序实际上,它依赖于在程序的不同部分中为同一约束设置多个实例,这可能很难避免。

回到主题,原则上重要的是GHC可以选择它可用于满足约束的任何字典,因为即使它们应该是相等的,GHC可能比其他字段有更多关于它们的静态信息。你的例子有点太简单了,不能说明,但想象你传递了一个参数 bar;一般来说,GHC对通过的字典一无所知 Dict 因此它必须将此视为对未知函数的调用,但是您调用了 foo 在特定类型 T 有一个 Bar T 在范围内的实例,然后GHC会知道 bar 来自 Bar a 约束字典是 Tbar 并且可以生成对已知函数的调用,并可能内联 Tbar并因此进行更多优化。

在实践中,GHC目前并不聪明,它只使用最里面的字典。总是使用最外层的字典可能已经更好了。但是这样的情况下,有多个词典可供使用并不常见,所以我们没有很好的基准测试。


5
2018-04-08 16:27



然后人们可能会问为什么我们有两个扩展(不连贯/重叠)而不是一个。人们可能会觉得单独重叠仍然是“安全的”,只有不连贯的真正的麻烦才会开始。 - chi
“任何两个相同约束的词典应该是平等的。” - 应该是,但不是。请参阅我的回答,了解违反此声明的示例,而不使用不连贯或重叠的实例。 - Daniel Wagner
是的,这就是我失去实例连贯性的意思。 - Reid Barton


它只选了一个。这不是正确的选择;这是一个非常着名的疣。你可以用这种方式导致崩溃,所以这是一个非常糟糕的事态。这是一个简单的例子,只使用它 GADTs 这表明有可能有两个 不同 范围内的实例:

-- file Class.hs
{-# LANGUAGE GADTs #-}
module Class where

data Dict a where
  Dict :: C a => Dict a

class C a where
  test :: a -> Bool

-- file A.hs
module A where

import Class

instance C Int where
  test _ = True

v :: Dict Int
v = Dict

-- file B.hs
module B where

import Class

instance C Int where
  test _ = False

f :: Dict Int -> Bool
f Dict = test (0 :: Int)

-- file Main.hs
import TestA
import TestB

main = print (f v)

你会发现的 Main.hs 编译得很好,甚至运行。它打印 True 使用GHC 7.10.1在我的机器上,但这不是一个稳定的结果。把它变成一个崩溃留给读者。


6
2018-04-08 01:12



那张票有票吗? - crockeea
你能详细说明如何导致崩溃吗? - chi
@chi我给出了一个片段,展示了如何在范围内获得两个不同的实例。从那里开始并不难 - 只需在代码中做一些关于所有实例相等的假设,你就会遇到问题。 - Daniel Wagner
我不认为你可以导致崩溃,除非你计算一个模块中的不变量导致的崩溃,假设实例是连贯的,并使用这个假设来证明 unsafeCoerce 等等。 (但后来我会说崩溃是由于 unsafeCoerce。) - Reid Barton
特别是人们可能会认为,虽然令人困惑 True 和 False对于其他有效的Haskell程序是无害的,可以使用相关类型来获得更少的无害混淆 Int 和 Maybe Int。但实际上GHC似乎总是检查类型族实例是否有重叠。 - Reid Barton


这是一个测试:

{-# LANGUAGE FlexibleInstances, OverlappingInstances, IncoherentInstances #-}
import Data.Constraint

class    C a    where foo :: a -> String
instance C [a]  where foo _ = "[a]"
instance C [()] where foo _ = "[()]"

aDict :: Dict (C [a])
aDict = Dict

bDict :: Dict (C [()])
bDict = Dict

bar1 :: String
bar1 = case (bDict, aDict :: Dict (C [()])) of
         (Dict,Dict) -> foo [()]              -- output: "[a]"

bar2 :: String
bar2 = case (aDict :: Dict (C [()]), bDict) of
         (Dict,Dict) -> foo [()]              -- output: "[()]"

上面的GHC碰巧使用了被引入范围的“最后”字典。不过,我不会依赖于此。

如果你限制自己 重叠的实例,只有,那么你将无法为同一类型引入两个不同的词典(据我所知),一切都应该没问题,因为词典的选择变得无关紧要。

然而, 不连贯的实例 是另一个野兽,因为它们允许您提交一个通用实例,然后在具有更具体实例的类型中使用它。这使得很难理解将使用哪个实例。

简而言之,语无伦次的实例是邪恶的。


更新:我进行了一些进一步的测试。在单独的模块中仅使用重叠实例和孤立实例,您仍然可以获得相同类型的两个不同的字典。所以,我们需要更多的警告。 :-(


5
2018-04-08 05:19



我知道 IncoherentInstances 可以导致各种各样的肮脏,这就是为什么我的例子 不 使用它(但它确实使用 OverlappingInstances and an orphan instance in another module). I didn't realize OverlappingInstances`也可能导致未定义的行为......我认为这是“安全的”。 - crockeea
@Eric我也这么认为。也许它可以被视为一个错误,但我不是那方面的专家。 - chi
@Eric为了记录,我只使用重叠的实例 Dict 打包模块中的“最佳”实例:GHC即使没有“不连贯”的扩展也会提交它,因为有一个最好的选择。在另一个模块中,我导入它,并定义一个更好的实例(这应该是不允许的,恕我直言)。 - chi
你能更新你的例子吗?如果你有另一种方式 Overlapping 无 Incoherent 可能不安全,我会发布一个错误。 - crockeea
我相信即使没有也可以欺骗GHC OverlappingInstances,这是孤儿被认为是邪恶的一大原因。 - dfeuer