共享与非共享定点组合

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？

Answer 1

"共享"意味着f x重新使用x它创建的; 但是_Y g = g . g . g . g . ...,每个都g重新计算它的输出(参见this和this).

在这种情况下,共享版本的内存使用量会更糟,导致空间泄漏.¹

_Y镜像的定义是通常的lambda演算定义对Y组合子的影响,它通过复制模拟递归,而真正的递归则指向相同(因此,共享)的实体.

在

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

两者都x指的是同一个实体,但每个都(_Y g)指的是等同的,但是是分开的实体.无论如何,这是它的意图.

当然,由于参考透明度,Haskell无法保证任何此类语言.但GHC编译器确实以这种方式运行.

_Y g是一种常见的子表达式,它可以给它一个名称,并重新使用命名实体,颠覆它的整个目的是"消除"由编译器.这就是GHC具有"没有共同的子表达式消除" -fno-cse标志的原因,该标志明确地阻止了这一点.过去,您必须使用此标志才能在此处实现所需的行为,但现在不再需要.GHC将不再像常见的子表达式消除那样具有攻击性,最近的版本(阅读:几年)版本.

免责声明:我是您所指的页面部分的作者.希望wiki页面上常见的来回,但它从未出现过,所以我的工作没有得到那样的评论.要么没有人打扰,或者是差强人意(缺乏重大失误).维基似乎在很大程度上已被放弃多年.

¹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 }中,链中只有两个,但只有最上面的一个会立即被垃圾收集,如上面引用的链接所讨论的那样.