双层"Y型"组合器.这是常见的吗？这有官方名称吗？

Question

我一直在研究禁止使用def-before-def并且没有可变单元格(no set!或setq)的语言如何提供递归.我当然跑过(着名的？臭名昭着的？)Y组合者和朋友,例如:

• http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
• http://okmij.org/ftp/Computation/fixed-point-combinators.html
• http://www.angelfire.com/tx4/cus/combinator/birds.html
• http://en.wikipedia.org/wiki/Fixed-point_combinator

当我以这种方式实现"letrec"语义时(也就是说,允许定义一个局部变量使得它可以是一个递归函数,在封面下它不会引用它自己的名字),组合器我最后写的看起来像这样:

Y_letrec = ?f . (?x.x x) (?s . (?a . (f ((?x.x x) s)) a))

或者,将U组合子分解出来:

U = ?x.x x
Y_letrec = ?f . U (?s . (?a . (f (U s)) a))

读这个:Y_letrec是一个带有待递归函数的函数f. f必须是一个单参数函数,它接受s,可以调用实现自递归s的函数f.f期望定义并返回执行"实际"操作的"内部"函数.该内部函数接受参数a(或者在一般情况下接受参数列表,但不能用传统的表示法表示).调用Y_letrec的结果是调用的结果 f,并且它被假定为"内部"函数,准备被调用.

我这样设置的原因是我可以直接使用待递归函数的解析树形式,而无需修改,只是在处理letrec时转换期间在其周围包裹一个额外的函数层.例如,如果原始代码是:

(letrec ((foo (lambda (a) (foo (cdr a))))))

然后转换后的形式将是:

(define foo (Y_letrec (lambda (foo) (lambda (a) (foo (cdr a))))))

请注意,内部函数体在两者之间是相同的.

我的问题是:

• 我的Y_letrec功能常用吗？
• 它有一个完善的名字吗？

注意:上面的第一个链接指的是与"应用顺序Y组合子"类似的功能(在"步骤5"中),尽管我无法找到该命名的权威来源.

更新28-apr-2013:

我意识到上面定义的Y_letrec与维基百科中定义的Z组合器非常接近但不完全相同.根据维基百科,Z组合子和"按值调用的Y组合子"是相同的东西,看起来这确实是可能更常被称为"应用顺序Y组合子"的东西.

所以,我有什么上面是不一样的,通常编写的应用性阶Y组合,但几乎可以肯定在他们相关的感觉.这是我进行比较的方式:

从...开始:

Y_letrec = ?f . (?x.x x) (?s . (?a . (f ((?x.x x) s)) a))

应用内U:

Y_letrec = ?f . (?x.x x) (?s . (?a . (f (s s)) a))

应用外U:

Y_letrec = ?f . (?s . (?a . (f (s s)) a)) (?s . (?a . (f (s s)) a))

重命名以匹配维基百科对Z组合子的定义:

Y_letrec = ?f . (?x . (?v . (f (x x)) v)) (?x . (?v . (f (x x)) v))

将此与维基百科的Z组合器进行比较:

Z        = ?f . (?x . f (?v . ((x x) v))) (?x . f (?v . ((x x) v)))

显着差异f在于应用功能的地方.有关系吗？尽管有这些差异,这两个功能是否相同？

Answer 1

是的,它是一个应用顺序Y组合子.在里面使用U是完全可以的,我也是这样做的(参见lisp中的固定点组合器).使用U来缩短代码是否有名字,我不这么认为.它只是一个lambda术语的应用,是的,它使IMO更清晰.

有什么名称,即eta转换,在您的代码中用于延迟在应用顺序下的评估,其中在功能应用之前必须知道参数的值.

在你的代码((?a.(f (s s)) a)==> f (s s))上执行U通过和通过和eta减少,它成为熟悉的正常顺序Y组合子 - 即在正常顺序评估下工作,其中在功能之前不需要参数值应用程序,最终可能最终不需要它们(或其中一些):

Y = ?f . (?s.f (s s)) (?s.f (s s))

BTW延迟可以稍微不同的方式应用,

Y_ = ?f . (?x.x x) (?s.f (?a.(s s) a)) 

这也适用于申请订单评估规则.

有什么不同？让我们比较减少序列.你的版本,

Y_ = ?f . (?x . (?v . (f (x x)) v)) (?x . (?v . (f (x x)) v))

((Y_ f) a) = 
  = ((?x . (?v . (f (x x)) v)) (?x . (?v . (f (x x)) v))) a
  = (?v . (f (x x)) v) a    { x := (?x . (?v . (f (x x)) v)) }
  = (f (x x)) a
  = | ; here (f (x x)) application must be evaluated, so 
    | ; the value of (x x) is first determined
    | (x x) 
    | = ((?x . (?v . (f (x x)) v)) (?x . (?v . (f (x x)) v))) 
    | = (?v . (f (x x)) v)     { x := (?x . (?v . (f (x x)) v)) }

这里f输入了.所以在这里,表现良好的函数f接收它的第一个参数,并且它不应该对它做任何事情.所以也许两者完全等同.

但实际上,lambda表达式定义的细节在实际实现时并不重要,因为真正的实现语言将有指针,我们只是操纵它们以正确指向包含表达式主体,而不是它的副本.毕竟,使用铅笔和纸进行Lambda演算,作为文本复制和替换.lambda演算中的Y组合子仅模拟递归.真正的递归是真正的自我引用 ; 没有通过自我申请获得与自我相同的副本(无论多么聪明).

TL; DR:虽然定义的语言可能没有分配和指针相等等有趣的东西,但我们定义它的语言肯定会有这些,因为我们需要它们来提高效率.至少,它的实施将在引擎盖下进行.

另见:lisp中的定点组合子,尤其是 在Scheme中,如何使用lambda创建递归函数？.