7

我一直在研究禁止 use-before-def 并且没有可变单元格（no set!or setq）的语言如何提供递归。我当然遇到了（著名的？臭名昭著的？）Y 组合器和朋友，例如：

当我以这种风格实现“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”中），尽管我在找到该命名的权威来源时遇到了麻烦。

2013 年 4 月 28 日更新：

我意识到上面定义的 Y_letrec非常接近但不等同于维基百科中定义的 Z 组合子。根据 Wikipedia，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))

重命名以匹配 Wikipedia 对 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的应用位置。有关系吗？尽管存在这种差异，这两个功能是否等效？

4

1 回答 1

6

是的，它是一个应用阶 Y 组合子。在里面使用 U 完全没问题，我也这样做了（参见lisp 中的定点组合器）。使用 U 来缩短代码是否有名称，我不这么认为。这只是 lambda 项的应用，是的，它也使 IMO 更清晰。

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

(λa.(f (s s)) a)在你的代码（ ==> ）上应用 U 并通过 eta 减少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 组合器仅模拟递归。真正的递归是真正的自引用；通过自我应用（无论多么聪明），没有收到等同于自我的副本。

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

另请参阅：lisp 中的定点组合器，尤其是。在 Scheme 中，如何使用 lambda 创建递归函数？.

于 2013-04-28T12:32:49.440 回答