Haskell中如何同时存在惰性与并行性？

Question

人们认为 Haskell 由于具有不可变数据结构而在并发性方面具有优势。但是 Haskell 还是懒惰的。这意味着数据实际上可以从thunk到求值结果进行变更。

因此，看起来懒惰可能会损害不可变性的优势。我错了还是 Haskell 对此问题有对策？或者这是 Haskell 的独特功能？

- damhiya

---

“数据实际上可以从thunk转变为评估结果”，您能否更详细地解释一下您的意思，并说明为什么您认为这是正确的？这句话的意思是，数据可以通过计算（或者说评估）将其从thunk（即一个未求值的表达式）转化为已经被计算出来的结果。我相信这是正确的，因为在编程中，我们通常会使用thunk来延迟计算，直到需要时再进行计算，以提高程序的效率和性能。当我们需要使用某个变量的值时，我们可以对其进行评估，得到其计算出来的结果。 - Thomas M. DuBuisson

@Thomas 我没有关于Haskell实现的确切信息，但我认为这是实现惰性和thunk的最简单解决方案。 - damhiya

同时：https://en.m.wikibooks.org/wiki/Haskell/Laziness#Thunks_and_Weak_head_normal_form - damhiya

重点是，每个线程必须同步信息，无论thunk是否已经被评估。或者每个线程必须重新评估thunk。（我认为） - damhiya

@Dai，因此，每次执行共享值的评估时，线程都必须阻止其他任务。 - damhiya

Answer 1

是的，GHC的运行时系统使用thunks来实现非严格评估，并且它们在幕后使用突变，因此需要一些同步。然而，由于大多数堆对象是不可变的，而函数具有引用透明性，因此这被简化了。

在多线程程序中，一个thunk的评估按以下方式进行：

- 原子地将thunk替换为BLACKHOLE对象 - 如果相同的线程尝试在更新为BLACKHOLE之后强制执行thunk，则表示无限循环，RTS会抛出异常(<>) - 如果不同的线程在thunk仍然是BLACKHOLE的情况下尝试强制执行它，则会阻塞，直到原始线程完成对thunk的评估并用值更新它 - 当评估完成后，原始线程原子地用其结果替换thunk

例如，使用比较和交换(CAS)指令。因此，这里存在一种潜在的竞争情况：如果两个线程试图同时强制执行相同的thunk，则它们可能都开始评估它。在这种情况下，它们将进行一些冗余工作——但是，一个线程将成功用结果覆盖BLACKHOLE，而另一个线程将简单地丢弃其计算出的结果，因为其CAS操作将失败。

安全代码无法检测到这种情况，因为它无法获取对象的地址或确定thunk的状态。而实际上，由于以下几个原因，这种类型的冲突很少发生：

- 并发代码通常会根据特定问题的要求对负载进行划分，因此重叠的风险很低。 - 在达到弱头正常形式之前，thunk的评估通常是相当“浅层”的，因此“碰撞”的概率较低。

因此，在实现非严格评估时，thunk最终提供了良好的性能权衡，即使在并发环境中也是如此。

- Jon Purdy

---

首先的步骤并不完全正确，因为GHC使用延迟黑洞技术（与通常的“lazy”一词有所不同）。请参阅网页http://mainisusuallyafunction.blogspot.com/2011/10/thunks-and-lazy-blackholes-introduction.html?m=1中的“Black holes and revelations”部分。 - dfeuer

考虑在文中包含一条链接，其中包含所有细节的论文，Haskell on a Shared-Memory Multiprocessor。在实践中，花费了大量时间讨论与使结果最终快速相关的非常低级别的细节。 - Alexis King