8

这是 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

4

3 回答 3

5

“共享”是指f x重复使用x它创建的内容；但是对于_Y g = g . g . g . g . ...，每个都g重新计算其输出（参见this和this）。

在这种情况下，共享版本的内存使用率要低得多，导致空间泄漏。1

Y组合子的定义_Y反映了通常的 lambda 演算定义的效果，它通过复制模拟递归，而真正的递归指的是相同的（因此，共享的）实体。

在

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

两个xs 指代同一个实体，但每个(_Y g)s 指代等价但独立的实体。无论如何，这就是它的意图。

当然，由于引用透明性，Haskell 语言不能保证任何这些。但是GHC 编译器确实以这种方式运行。

_Y g是一个常见的子表达式，编译器可以通过给它一个名称并重用该命名实体来“消除”它，从而破坏它的整个目的。这就是为什么 GHC 有“没有共同的子表达式消除” -fno-cse标志来明确防止这种情况发生。过去，您必须使用此标志才能在此处实现所需的行为，但现在不再如此。GHC 将不再那么积极地消除常见的子表达式，使用更新的（阅读：现在几年）版本。

免责声明：我是您所指页面的那部分的作者。希望在 wiki 页面上经常出现这种来回，但它从来没有出现过，所以我的工作没有得到这样的审查。要么没人打扰，要么可以通过（没有重大错误）。Wiki 似乎已被废弃多年。

1g所涉及的功能，

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

给定所有奇数素数的增加流，产生所有奇数素数的增加流. 为了产生一个质数，它至少N消耗它的输入流直到上面的第一个质数。sqrt(N)因此，生产点大致通过重复平方给出，并且在这些素数生产者的链（或“塔”~ log (log N) ）中总共有这样的功能，每个生产者都可以立即进行垃圾收集，最低的生产者只给出第一个奇数素数, , 先验已知。g3

并且对于两阶段_Y2 g = g x where { x = g x }，链中只有两个，但只有最上面的一个会立即被垃圾收集，如上面引用的链接中所讨论的。

于 2018-12-11T08:00:19.417 回答
4

_Y被翻译成以下STG：

_Y f = let x = _Y f in f x

fix与 Haskell 源代码翻译相同：

fix f = let x = f x in x

所以fix f设置一个递归 thunkx并返回它，while_Y是一个递归函数，重要的是它不是尾递归的。强制_Y f进入f，将新调用_Y f作为参数传递，因此每个递归调用都会设置一个新的thunk；强制x由 enter 返回，将自身作为参数传递，因此每个递归调用都fix f进入同一个 thunk ——这就是“共享”的意思。fx

共享版本通常具有更好的内存使用率，并且还可以让 GHC RTS 检测某些类型的无限循环。当一个 thunk 被强制执行时，在评估开始之前，它被一个“黑洞”取代；如果在评估 thunk 期间的任何时候从同一个线程到达黑洞，那么我们知道我们有一个无限循环并且可以抛出异常（您可能已经看到显示为Exception: <<loop>>）。

于 2018-12-11T07:47:38.150 回答
2

从 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 assumes a traced monoidal category, a requirement that is much less stringent than the usual PCPO assumption of domain theory, which forms the basis of how we think about Haskell in general. What Hasegawa showed was that one can define these "sharing" fixed point operators in such a setting, and established that they correspond to the usual unfolding view of fixed points from Church's lambda-calculus. That is, there is no way to tell them apart by making them produce different answers.

Hasegawa's correspondence holds for what's known as central arrows; i.e., when there are no "effects" involved. Later on, Benton and Hyland extended this work and showed that the correspondence holds for certain cases when the underlying arrow can perform "mild" monadic effects as well: https://pdfs.semanticscholar.org/7b5c/8ed42a65dbd37355088df9dde122efc9653d.pdf

Unfortunately, Benton and Hyland only allow effects that are quite "mild": Effects like the state and environment monads fit the bill, but not general effects like exceptions, lists, or IO. (The fixed point operators for these effectful computations are known as mfix in Haskell, with the type signature (a -> m a) -> m a, and they form the basis of the recursive-do notation.)

It's still an open question how to extend this work to cover arbitrary monadic effects. Though it doesn't seem to be receiving much attention these days. (Would make a great PhD topic for those interested in the correspondence between lambda-calculus, monadic effects, and graph-based computations.)

于 2018-12-11T18:34:39.633 回答