scheme - 两层 "Y-style"组合子。这很常见吗？这个有正式名称吗？

Question

我一直在研究禁止 use-before-def 并且没有可变单元格(没有 set! 或 setq)的语言如何仍然可以提供递归.我当然遇到了(著名的？臭名昭著的？)Y 组合器和 friend ，例如:

• 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 应该定义并返回执行“真实”操作的“内部”功能。该内部函数接受argument 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 步”中)，尽管我找不到该命名的权威来源。

2013 年 4 月 28 日更新:

我意识到上面定义的 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 是完全可以的，我也这样做了(参见 fixed point combinator in lisp )。 U 用于缩短代码的用法是否有名称，我不这么认为。它只是 lambda 项的应用，是的，它也使 IMO 更清晰。

有一个名字，是 eta-conversion，在您的代码中用于延迟应用顺序下的评估，其中参数的值必须在功能应用之前已知。

通过不断应用 U 并对代码执行 eta 缩减 ( (λa.(f (s s)) a) ==> f (s s) )，它变成了熟悉的正常顺序 Y 组合子 - 即在正常顺序评估下工作，其中在功能应用程序之前不需要参数的值，毕竟最终可能不需要它们(或其中的一些):

Y = λf . (λs.f (s s)) (λs.f (s s))

顺便说一句，延迟可以以稍微不同的方式应用，

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 组合器仅模拟递归。真正的递归是真正的自引用；不是接收副本，通过 self 应用(无论多么聪明)。

TL;DR:虽然被定义的语言可能没有赋值和指针相等性等有趣的东西，但我们定义它的语言肯定会有这些东西，因为我们需要它们来提高效率。至少，它的实现会将它们隐藏起来。

另请参阅:fixed point combinator in lisp , 特别是In Scheme, how do you use lambda to create a recursive function? .