两层"Y-style"组合器.这很常见吗?这有官方名称吗? [英] Two-layer "Y-style" combinator. Is this common? Does this have an official name?

问题描述

我一直在研究禁止使用before-def且没有可变单元格(没有set!或setq)的语言如何提供递归.我当然遇到了(著名的?臭名昭著的)Y组合者和朋友，例如:

I've been looking into how languages that forbid use-before-def and don't have mutable cells (no set! or setq) can nonetheless provide recursion. I of course ran across the (famous? infamous?) Y combinator and friends, e.g.:

• 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/bird.html
• http://en.wikipedia.org/wiki/Fixed-point_combinator

• 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"语义时(也就是说，允许定义局部变量，使其可以成为递归函数，在此情况下，它永远都不会引用自己的名称) ，我最终编写的组合器如下所示:

When I went to implement "letrec" semantics in this style (that is, allow a local variable to be defined such that it can be a recursive function, where under the covers it doesn't ever refer to its own name), the combinator I ended up writing looks like this:

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，并且假定它是一个内部"函数，随时可以调用.

Read this as: Y_letrec is a function which takes a to-be-recursed function f. f must be a single-argument function which accepts s, where s is the function that f can call to achieve self-recursion. f is expected to define and return an "inner" function which does the "real" operation. That inner function accepts argument a (or in the general case an argument list, but that can't be expressed in the traditional notation). The result of calling Y_letrec is a result of calling f, and it is presumed to be an "inner" function, ready to be called.

我以这种方式进行设置的原因是，我可以使用的解析树形式 直接递归的函数，无需修改，仅包装一个额外的 处理letrec时在转换过程中围绕它的功能层.例如，如果 原始代码是:

The reason I set things up this way is so that I could use the parse tree form of the to-be-recursed function directly, without modification, merely wrapping an additional function layer around it during transformation when handling letrec. E.g., if the original code is:

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

然后转换后的形式将遵循:

then the transformed form would be along the lines of:

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

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

Note that the inner function body is identical between the two.

我的问题是:

• 我的Y_letrec函数是否常用?
• 它的名称是否成立?

注意:上面的第一个链接引用了与应用顺序Y组合器"相似的功能(在第5步"中)，尽管我很难找到该名称的权威来源.

Note: The first link above refers to a similar function (in "step 5") as the "applicative-order Y combinator", though I'm having trouble finding an authoritative source for that naming.

2013年4月28日更新:

UPDATE 28-apr-2013:

我意识到上面定义的Y_letrec非常接近，但与Wikipedia中定义的Z组合器并不相同.根据Wikipedia的说法，Z组合器和按值调用Y组合器"是同一件事，而且看起来确实确实是一种更普遍的应用顺序Y组合器".

I realized that Y_letrec as defined above is very close to but not identical to the Z combinator as defined in Wikipedia. Per Wikipedia, the Z combinator and "call-by-value Y combinator" are the same thing, and it looks like that is indeed the thing that may be more commonly called the "applicative-order Y combinator."

因此，我上面的内容与通常编写的应用顺序Y组合器不相同，但是几乎可以肯定它们之间存在某种联系.这是我进行比较的方式:

So, what I have above is not the same as the applicative-order Y combinator as usually written, but there is almost certainly a sense in which they're related. Here's how I did the comparison:

开始于:

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组合器的定义:

Rename to match Wikipedia's definition of the Z combinator:

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

将此与Wikipedia的Z组合器进行比较:

Compare this to Wikipedia's Z combinator:

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

显着差异是应用功能f的位置.有关系吗?尽管存在差异，但这两个函数是否等效?

The salient difference is where the function f is being applied. Does it matter? Are these two functions equivalent despite this difference?

推荐答案

是的，它是应用级Y组合器.在里面使用U完全可以，我也做到了(参见定点组合器一口气).是否使用U来缩短代码有名称，我不这么认为.这只是lambda项的应用，是的，它也使IMO更清晰.

Yes, it is an applicative-order Y combinator. Using U inside it is perfectly OK, I did it too (cf. fixed point combinator in lisp). Whether the usage of U to shorten code has a name or not, I don't think so. It's just an application of a lambda-term, and yes, it makes it clearer IMO too.

确实有个名字，就是eta转换，在您的代码中使用它来延迟应用顺序下的求值，在应用顺序之前，必须先知道参数的值.

What does have a name, is eta-conversion, used in your code to delay evaluation under applicative order, where arguments' values must be known before functional application.

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

With U applied through and through and eta-reduction performed on your code ( (λa.(f (s s)) a) ==> f (s s) ), it becomes the familiar normal-order Y combinator - i.e. such that works under normal-order evaluation, where arguments' values aren't demanded before functional application, which might end up not needing them (or some of them) after all:

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

顺便说一句，延迟的应用方式可能略有不同，

BTW the delaying can be applied in slightly different way,

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

这也适用于应用顺序评估规则.

which also works under applicative-order evaluation rules.

有什么区别?让我们比较一下还原顺序.您的版本，

What is the difference? let's compare the reduction sequences. Your version,

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会接收其第一个参数，并且应该对此不做任何事情.所以也许两者毕竟是完全相同的.

and here f is entered. So here too, the well-behaved function f receives its first argument and it's supposed not to do anything with it. So maybe the two are exactly equivalent after all.

但是，实际上，lambda表达式定义的细节并不重要，因为真正的实现语言将具有指针，我们将操纵它们以正确地指向包含表达式的主体，而不是指向它的副本. Lambda演算毕竟是用铅笔和纸完成的，是文本的复制和替换. Lambda演算中的Y组合器仅模拟递归.真正的递归是真正的 self-reference ；通过自我应用(无论多么聪明)不会接收等同于自身的副本.

But really, the minutia of lambda-expressions definitions do not matter when it comes to the real implementation, because real implementation language will have pointers and we'll just manipulate them to point properly to the containing expression body, and not to its copy. Lambda calculus is done with pencil and paper after all, as textual copying and replacement. Y combinator in lambda calculus only emulates recursion. True recursion is true self-reference; not receiving copies equal to self, through self-application (however smart that is).

TL; DR:尽管所定义的语言可能缺少诸如赋值和指针相等之类的有趣内容，但是我们定义它的语言肯定会包含这些内容，因为我们需要它们来提高效率.至少，它的实现会在后台显示它们.

TL;DR: though language being defined can be devoid of such fun stuff as assignment and pointer equality, the language in which we define it will most certainly have those, because we need them for efficiency. At the very least, its implementation will have them, under the hood.

另请参见: lisp中的定点组合器，尤其是. 在Scheme中，如何您使用lambda创建递归函数吗?.

see also: fixed point combinator in lisp , esp. In Scheme, how do you use lambda to create a recursive function?.

这篇关于两层"Y-style"组合器.这很常见吗?这有官方名称吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！