共享和非共享的不动点组合子

Question

这是Haskell中固定点组合子的通常定义：

fix :: (a -> a) -> a
fix f = let x = f x in x

在 https://wiki.haskell.org/Prime_numbers 上，他们定义了一个不同的不动点组合子：

_Y   :: (t -> t) -> t
_Y g = g (_Y g)                -- multistage, non-sharing,  g (g (g (g ...)))
    -- g (let x = g x in x)    -- two g stages, sharing

_Y是一个非共享的不动点组合子，在这里安排了一个递归的“伸缩”多阶段质数生产（一堆生产者的“塔”）。

这到底意味着什么？在这种情况下，“共享”与“非共享”是什么意思？_Y与fix有何不同？

- Joseph Sible-Reinstate Monica

---

这里讨论了两个定义之间的差异：为什么 GHC 使得 fix 函数如此令人困惑？。 - Will Ness

Answer 1

“Sharing” 表示 f x 会重复使用它创建的 x；但是对于 _Y g = g . g . g . g . ...，每个 g 都会重新计算其输出（参见这里和这里）。

在这种情况下，共享版本的内存使用率要差得多，会导致空间泄漏（参考）。¹ _Y 的定义反映了通常的 lambda 演算中 Y 组合子的效果，通过复制来模拟递归，而真正的递归则指相同（因此是“共享”的）实体。

在

    x      = f x
    (_Y g) = g (_Y g)

两个 x 引用了同一个实体，但是每个 (_Y g) 引用了等价但不同的实体。这就是初衷。

当然，由于引用透明性，在 Haskell 语言中并不能保证任何这样的情况。但是 GHC 编译器确实会像这样运行。

_Y g 是常见的子表达式，它 可能 通过给它一个名称并重复使用该命名实体来被编译器“消除”，从而破坏整个目的。这就是为什么 GHC 有 “no common sub-expressions elimination” -fno-cse 标志，用于明确防止此类情况。以前你必须使用这个标志才能实现这里想要的行为，但现在不需要了。GHC 不再像几年前那样过于依赖公共子表达式的消除法。

免责声明：我是你正在引用页面的那一部分的作者。我希望获得维基页面上通常会出现的互动，但是这种情况从未发生过，所以我的工作没有像那样接受审查。也许是没人关心，或者它没有严重错误。维基页面似乎已经被荒废了多年。

---

¹ 涉及的 g 函数，

(3:) . minus [5,7..] . foldr (\ (x:xs) ⟶ (x:) . union xs) [] 
                      . map (\ p ⟶ [p², p² + 2p..])

给定所有奇素数的递增流，它会产生一个递增的奇素数流。为了产生值为N的素数，它会消耗输入流，直到第一个大于sqrt(N)的素数为止。因此，这些生产点大致由重复平方给出，在这些素数生成器的链（或"塔"）中总共有~ log (log N)个这样的g函数，每个都可以立即进行垃圾回收，最低的一个仅使用已知的第一个奇素数3就能产生其素数。

使用两级_Y2 g = g x where { x = g x }，链中只有两个，但仅有顶部可以立即进行垃圾回收，如上面引用链接所述。

- Will Ness

Answer 2

_Y被翻译为以下STG：

_Y f = let x = _Y f in f x

fix的翻译与Haskell源代码完全相同：

fix f = let x = f x in x

因此，fix f设置了一个递归thunk x并返回它，而_Y是一个递归函数，并且重要的是它不是尾递归。强制执行_Y f会进入f，将一个新的调用传递给_Y f作为参数，因此每个递归调用都设置了一个新的thunk；强制执行由fix f返回的x会进入f，将x本身作为参数传递，因此每个递归调用都进入相同的thunk ——这就是“共享”的含义。

共享版本的内存使用通常更好，并且还可让GHC RTS检测某些类型的无限循环。当强制执行thunk之前，它会被替换为一个“黑洞”；如果在计算thunk期间从同一线程到达黑洞，则我们知道存在无限循环并可以抛出异常（您可能已经看到其显示为Exception: <<loop>>）。

- Jon Purdy

---

在这种情况下，共享版本更糟，会导致空间泄漏。 :) （更多讨论和链接在我的答案中）。另一个我们不想共享的情况是例如幂集计算。 - Will Ness

@WillNess：你说得对；我在“更好的内存使用”这一说法中加入了一个“通常”的限定词——这确实取决于你用它做什么。通常在提高共享和避免不必要的保留之间存在权衡。 - Jon Purdy

是的，我想这取决于输出中被重用部分的大小。以 Hamming 数为例，对于 O(n) 序列，保留的部分是 O(n^(2/3))，所以没问题。但是对于质数，保留的部分从 ~sqrt(n) 到 ~(n)，因此太大了。 - Will Ness

对于相反的例子，使用共享修复程序计算斐波那契数列要高效得多。 - Will Ness

Answer 3

我认为你已经从GHC/Haskell的角度得到了优秀的答案。我只是想补充一些历史/理论注释。

Hasegawa在他的博士论文中严格研究了展开和递归循环视图之间的对应关系：https://www.springer.com/us/book/9781447112211。

（这是一篇较短的论文，您可以在不支付Springer费用的情况下阅读：https://link.springer.com/content/pdf/10.1007%2F3-540-62688-3_37.pdf）。

Hasegawa假设一个被跟踪的单调范畴，这个要求比域论的通常PCPO假设要少得多，后者构成了我们通常思考Haskell的基础。Hasegawa所展示的是，在这样的设置中，可以定义这些“共享”不动点运算符，并且建立它们与Church的lambda演算中固定点的通常展开视图之间的对应关系。也就是说，没有办法通过使它们产生不同的答案来区分它们。

Hasegawa的对应关系适用于所谓的中央箭头，即没有涉及“效果”的情况。之后，Benton和Hyland扩展了这项工作，并表明在底层箭头可以执行“轻微”单调效果的某些情况下，该对应关系仍然成立：https://pdfs.semanticscholar.org/7b5c/8ed42a65dbd37355088df9dde122efc9653d.pdf。

不幸的是，Benton和Hyland只允许相当“温和”的效果：像状态和环境单子这样的效果符合条件，但不包括一般效果，如异常、列表或IO。（这些效果计算的固定点运算符在Haskell中被称为mfix，类型签名为(a -> m a) -> m a，它们构成递归-do表示法的基础。）

如何扩展此工作以涵盖任意的单调效果仍然是一个未解决的问题。虽然这似乎在今天并没有受到太多关注。（对于那些对lambda演算、单调效果和基于图形的计算之间的对应关系感兴趣的人来说，这将是一个很好的博士课题。）

- alias