在Scheme中，如何使用lambda创建递归函数？
我在一个Scheme 类中，我很好奇在不使用define 的情况下编写一个递归函数。当然，主要问题是如果函数没有名称，则无法在其内部调用该函数。
我确实找到了这个例子：它是一个仅使用 lambda 的阶乘生成器。
((lambda (x) (x x))
(lambda (fact-gen)
(lambda (n)
(if (zero? n)
1
(* n ((fact-gen fact-gen) (sub1 n)))))))
但我什至无法理解第一个调用， (lambda (x) (xx))：它到底有什么作用？您在哪里输入要获取阶乘的值？
这不是为了上课，这只是出于好奇。
I'm in a Scheme class and I was curious about writing a recursive function without using define. The main problem, of course, is that you cannot call a function within itself if it doesn't have a name.
I did find this example: It's a factorial generator using only lambda.
((lambda (x) (x x))
(lambda (fact-gen)
(lambda (n)
(if (zero? n)
1
(* n ((fact-gen fact-gen) (sub1 n)))))))
But I can't even make sense of the first call, (lambda (x) (x x)): What exactly does that do? And where do you input the value you want to get the factorial of?
This is not for the class, this is just out of curiosity.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
(lambda (x) (xx))是一个对自身调用参数 x 的函数。您发布的整个代码块都会生成一个参数的函数。您可以这样调用它：
使用 5 调用它，并返回 120。
从高层次考虑这个问题的最简单方法是第一个函数
(lambda (x) (xx))，给 x 一个对自身的引用，所以现在 x 可以引用自己，从而递归。(lambda (x) (x x))is a function that calls an argument, x, on itself.The whole block of code you posted results in a function of one argument. You could call it like this:
That calls it with 5, and returns 120.
The easiest way to think about this at a high level is that the first function,
(lambda (x) (x x)), is giving x a reference to itself so now x can refer to itself, and hence recurse.表达式
(lambda (x) (xx))创建一个函数，当使用一个参数（必须是函数）求值时，将该函数及其自身作为参数应用。您给定的表达式计算结果为一个函数，该函数接受一个数字参数并返回该参数的阶乘。尝试一下：
您的示例中有多个层，值得一步一步地完成并仔细检查每个层的作用。
The expression
(lambda (x) (x x))creates a function that, when evaluated with one argument (which must be a function), applies that function with itself as an argument.Your given expression evaluates to a function that takes one numeric argument and returns the factorial of that argument. To try it:
There are several layers in your example, it's worthwhile to work through step by step and carefully examine what each does.
基本上你所拥有的是类似于 Y 组合器的形式。如果您重构阶乘特定代码以便可以实现任何递归函数，那么剩余的代码将是 Y 组合器。
为了更好地理解，我自己完成了这些步骤。
https://gist.github.com/z5h/238891
如果你不喜欢我的内容已经写过，只需用谷歌搜索一下 Y Combinator （函数）即可。
Basically what you have is a form similar to the Y combinator. If you refactored out the factorial specific code so that any recursive function could be implemented, then the remaining code would be the Y combinator.
I have gone through these steps myself for better understanding.
https://gist.github.com/z5h/238891
If you don't like what I've written, just do some googleing for Y Combinator (the function).
(lambda (x) (xx))接受一个函数对象，然后使用一个参数（函数对象本身）调用该对象。然后用另一个函数调用它，该函数在参数名称
fact-gen下获取该函数对象。它返回一个采用实际参数n的 lambda。这就是((fact-gen fact-gen) (sub1 n))的工作原理。如果您愿意，您应该阅读小阴谋家中的示例章节（第 9 章）可以跟随它。它讨论了如何构建这种类型的函数，并最终将此模式提取到 Y 组合器 （一般可用于提供递归）。
(lambda (x) (x x))takes a function object, then invokes that object using one argument, the function object itself.This is then called with another function, which takes that function object under the parameter name
fact-gen. It returns a lambda that takes the actual argument,n. This is how the((fact-gen fact-gen) (sub1 n))works.You should read the sample chapter (Chapter 9) from The Little Schemer if you can follow it. It discusses how to build functions of this type, and ultimately extracting this pattern out into the Y combinator (which can be used to provide recursion in general).
我喜欢这个问题。 《方案编程语言》是一本好书。我的想法来自那本书的第二章。
首先，我们知道这一点：
使用
letrec我们可以递归地创建函数。我们看到，当我们调用(fact 5)时，fact已经绑定到一个函数。如果我们还有另一个函数，我们可以这样称呼它（另一个事实5），现在另一个被称为二元函数（我的英文是不好，抱歉）。我们可以这样定义another：为什么我们不这样定义
fact呢？如果
fact是一个二元函数，那么可以使用函数f和整数n来调用它，其中case 函数f恰好是fact本身。如果您掌握了以上所有内容，您现在就可以编写 Y 组合器，用
lambda替换let。I like this question. 'The scheme programming language' is a good book. My idea is from Chapter 2 of that book.
First, we know this:
With
letrecwe can make functions recursively. And we see when we call(fact 5),factis already bound to a function. If we have another function, we can call it this way(another fact 5), and nowanotheris called binary function (my English is not good, sorry). We can defineanotheras this:Why not we define
factthis way?If
factis a binary function, then it can be called with a functionfand integern, in which case functionfhappens to befactitself.If you got all the above, you could write Y combinator now, making a substitution of
letwithlambda.你可以这样定义它：
这就是
letrec真正的工作原理。请参阅 Christian Queinnec 的 LiSP。在您询问的示例中，自应用组合器称为 "U 组合器”，
这里的微妙之处在于，由于
let的作用域规则，lambda 表达式无法引用正在定义的名称。当调用
((U h) 5)时，它会在let创建的环境框架内简化为((hh) 5)应用程序代码> 形式。现在，将
h应用于h创建了新的环境框架，其中g指向其上方环境中的h：这里的
(lambda (n) ...)表达式是从该环境框架内部返回的，其中g指向其上方的h-作为闭包对象。即一个参数n的函数，它还记住g、h和U的绑定。因此，当调用此闭包时，
n被分配为5，并且输入if形式：(gg)应用程序被简化为(hh)应用程序，因为g指向在创建闭包对象的环境之上的环境框架中定义的h。也就是说，在上面的let表单中。但我们已经看到了(hh)调用的减少，它创建了闭包，即一个参数n的函数，用作我们的阶乘函数，在下一次迭代中将使用4调用该函数，然后使用3等调用。无论是新的闭包对象还是会重用相同的闭包对象，取决于编译器。这可能会对性能产生影响，但是不是关于递归的语义。
You define it like this:
which is how
letrecreally works. See LiSP by Christian Queinnec.In the example you're asking about, the self-application combinator is called "U combinator",
The subtlety here is that, because of
let's scoping rules, the lambda expressions can not refer to the names being defined.When
((U h) 5)is called, it is reduced to((h h) 5)application, inside the environment frame created by theletform.Now the application of
htohcreates new environment frame in whichgpoints tohin the environment above it:The
(lambda (n) ...)expression here is returned from inside that environment frame in whichgpoints tohabove it - as a closure object. I.e. a function of one argument,n, which also remembers the bindings forg,h, andU.So when this closure is called,
ngets assigned5, and theifform is entered:The
(g g)application gets reduced into(h h)application becausegpoints tohdefined in the environment frame above the environment in which the closure object was created. Which is to say, up there, in the topletform. But we've already seen the reduction of(h h)call, which created the closure i.e. the function of one argumentn, serving as ourfactorialfunction, which on the next iteration will be called with4, then3etc.Whether it will be a new closure object or same closure object will be reused, depends on a compiler. This can have an impact on performance, but not on semantics of the recursion.
对于单个 lambda 来说这是不可能的。但使用两个或多个 lambda 是可能的。由于所有其他解决方案都使用三个 lambda 或 let/letrec，因此我将使用两个 lambda 来解释该方法：
输出为 120。
这里，
(lambda (fx) (ffx))是一个带有两个参数的 lambda，第一个是 lambda（我们称之为f），第二个是参数（我们称之为x）。请注意，在其主体中，它以f和x作为参数调用提供的 lambdaf- 相同f。f（来自第 1 点）即self是我们想要用来递归的。看，当递归调用self时，我们还传递self作为第一个参数，将(- n 1)作为第二个参数。因此，调用
(self self ...)使用与(ff ...)启动的相同组合 - 这就是递归的含义，即从 self 调用 self：self绑定到第二个 lambda(lambda (self ...) ...)并作为其体内的值传递给self。这个传递的值在新调用中用作函数及其参数，克服了在 lambda 演算中无法为函数提供全局名称并且只能使用无名（“匿名”）lambda 的限制。
With a single lambda it's not possible. But using two or more lambda's it is possible. As, all other solutions are using three lambdas or let/letrec, I'm going to explain the method using two lambdas:
And the output is 120.
Here,
(lambda (f x) (f f x))is a lambda that takes two arguments, the first one is a lambda (let's call itf) and the second is the parameter (let's call itx). Notice, in its body it calls the provided lambdafwithfandxas arguments – the samef.f(from point 1) i.e.selfis what we want to use to recurse. See, when callingselfrecursively, we also passselfas the first argument and(- n 1)as the second argument.Thus calling
(self self ...)uses the same combination as initiated by(f f ...)– which is the meaning of recursion, i.e. calling self from self:selfbecomes bound to the second lambda(lambda (self ...) ...)and is passed toselfas a value inside its body.This passed value being used both as a function in the new call and its argument overcomes the limitation of not being able to give global names to functions, in the lambda calculus, and only using nameless ("anonymous") lambdas.
这里有点题外话，但是看到上面的陈述我只是想让你知道“不使用定义”并不意味着“没有名字”。可以给某些东西一个名字，并在没有定义的情况下在Scheme中递归地使用它。
如果你的问题具体说“匿名递归”，那就更清楚了。
A little off-topic here, but seeing the above statements I just wanted to let you know that "without using define" does not mean "doesn't have a name". It is possible to give something a name and use it recursively in Scheme without define.
It would be more clear if your question specifically says "anonymous recursion".
我发现这个问题是因为我需要在宏中使用递归辅助函数，而不能使用定义。
人们想要理解
(lambda (x) (xx))和 Y 组合器，但命名为 let 可以完成工作，而不会吓跑游客：人们也可以推迟理解
(lambda ( x) (xx))和 Y 组合器，如果这样的代码就足够了。与哈斯克尔和银河系一样，Scheme 的中心也有一个巨大的黑洞。许多以前富有成效的程序员被这些黑洞的数学之美所吸引，然后就再也没有出现过。I found this question because I needed a recursive helper function inside a macro, where one can't use define.
One wants to understand
(lambda (x) (x x))and the Y-combinator, but named let gets the job done without scaring off tourists:One can also put off understanding
(lambda (x) (x x))and the Y-combinator, if code like this suffices. Scheme, like Haskell and the Milky Way, harbors a massive black hole at its center. Many a formerly productive programmer gets entranced by the mathematical beauty of these black holes, and is never seen again.