GHC选择何种字典时，多于一个字典？ [英] Which dictionary does GHC choose when more than one is in scope?

问题描述

  import Data.Constraint 
 
 class Bar a where 
 bar :: a  - > a 
 
 foo ::（Bar a）=>字典（Bar a） - > a  - > a 
 foo Dict = bar 
  

GHC有两种选择让字典在选择在 foo 中的 Bar 实例：它可以使用 Bar中的字典a foo 的$ c>约束，或者它可以使用运行时 Dict 来获取字典。请参阅此问题，其中的词典对应于不同的实例。



GHC使用哪一种词典，为什么它是正确的选择？

/ GH> GHC只挑一个，这是正确的选择。任何两个相同约束的字典应该是相同的。

重叠物质和不相容物质在破坏力方面基本相同;他们都通过设计失去了实例一致性（您的程序中的任何两个相同的约束都被相同的字典所满足）。 OverlappingInstances为您提供了更多的能力来确定哪些实例将在个案基础上使用，但是当您将Dicts作为第一类值传递时，这没什么用处。我只考虑使用OverlappingInstances，当我考虑重叠的实例延伸等价的时候（例如，对于像Int这样的特定类型，更高效但平等的实现），但即使如此，如果我足够关心性能来编写专门的实现，它是一个性能错误，如果它没有被使用，它可能是什么？

总之，如果你使用OverlappingInstances，你放弃了提问的权利该字典将在这里被选中。

现在确实可以在没有OverlappingInstances的情况下打破实例一致性。事实上，你可以在没有孤儿的情况下做任何事情，除了FlexibleInstances以外没有任何扩展（可以说当问题是启用了FlexibleInstances时，孤儿的定义是错误的）。这是一个非常长久的GHC错误，这个错误并没有得到部分解决，因为（a）它实际上不会像任何人似乎知道的那样直接导致崩溃，并且（b）可能有很多程序实际上依赖于在程序的不同部分有相同约束的多个实例，这可能很难避免。

回到主题，原则上它是GHC可以选择任何可用于满足约束的字典，因为尽管它们应该是相同的，但GHC可能会拥有比其他字典更多的静态信息。你的例子有点过于简单，不足以说明，但想象一下你传递了一个参数给 bar ;一般来说，GHC并不知道通过 Dict 传入的字典，所以它必须将其视为对未知函数的调用，但是您称之为 foo 在特定类型 T 上，其范围内存在 Bar T 实例，那么GHC会知道 Bar a 约束字典中的 bar 是 T ' bar ，并且可以生成对已知函数的调用，并可能内联 T 的s bar ，并进行更多的优化。

实际上，GHC目前不是这么聪明，它只是使用最里面的字典可用。总是使用最外面的字典可能会更好。但是，如果有多个词典可用，这种情况并不常见，所以我们没有良好的基准测试。

Consider the following example:

import Data.Constraint

class Bar a where
  bar :: a -> a

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

GHC has two choices for the dictionary to use when selecting a Bar instance in foo: it could use the dictionary from the Bar a constraint on foo, or it could use the runtime Dict to get a dictionary. See this question for an example where the dictionaries correspond to different instances.

Which dictionary does GHC use, and why is it the "correct" choice?

解决方案

GHC just picks one, and this is the correct choice. Any two dictionaries for the same constraint are supposed to be equal.

OverlappingInstances and IncoherentInstances are basically equivalent in destructive power; they both lose instance coherence by design (any two equal constraints in your program being satisfied by the same dictionary). OverlappingInstances gives you a little more ability to work out which instances will be used on a case-by-case basis, but this isn't that useful when you get to the point of passing around Dicts as first class values and so on. I would only consider using OverlappingInstances when I consider the overlapping instances extensionally equivalent (e.g., a more efficient but otherwise equal implementation for a specific type like Int), but even then, if I care enough about performance to write that specialized implementation, isn't it a performance bug if it doesn't get used when it could be?

In short, if you use OverlappingInstances, you give up the right to ask the question of which dictionary will be selected here.

Now it's true that you can break instance coherence without OverlappingInstances. In fact you can do it without orphans and without any extensions other than FlexibleInstances (arguably the problem is that the definition of "orphan" is wrong when FlexibleInstances is enabled). This is a very long-standing GHC bug, which hasn't been fixed in part because (a) it actually can't cause crashes directly as far as anybody seems to know, and (b) there might be a lot of programs that actually rely on having multiple instances for the same constraint in separate parts of the program, and that might be hard to avoid.

Getting back to the main topic, in principle it's important that GHC can select any dictionary that it has available to satisfy a constraint, because even though they are supposed to be equal, GHC might have more static information about some of them than others. Your example is a little bit too simple to be illustrative but imagine that you passed an argument to bar; in general GHC doesn't know anything about the dictionary passed in via Dict so it has to treat this as a call to an unknown function, but you called foo at a specific type T for which there was a Bar T instance in scope, then GHC would know that the bar from the Bar a constraint dictionary was T's bar and could generate a call to a known function, and potentially inline T's bar and do more optimizations as a result.

In practice, GHC is currently not this smart and it just uses the innermost dictionary available. It would probably be already better to always use the outermost dictionary. But cases like this where there are multiple dictionaries available are not very common, so we don't have good benchmarks to test on.

这篇关于GHC选择何种字典时，多于一个字典？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！