Lisp中的定点组合器 [英] fixed point combinator in lisp
问题描述
;; compute the max of a list of integers
(define Y
(lambda (w)
((lambda (f)
(f f))
(lambda (f)
(w (lambda (x)
((f f) x)))))))
((Y
(lambda (max)
(lambda (l)
(cond ((null? l) -1)
((> (car l) (max (cdr l))) (car l))
(else (max (cdr l)))))))
'(1 2 3 4 5))
我希望了解这种结构.有人可以给这个代码一个简单明了的解释吗?
I wish to understand this construction. Can somebody give a clear and simple explanation for this code?
例如，假设我忘记了Y的公式.我如何记住它，并在使用它很长时间后对其进行复制?
For example, supposing that I forget the formula of Y. How can I remember it , and reproduce it long after I work with it ?
推荐答案
以下是一些相关的答案(对我来说):
Here's some related answers (by me):
- Y combinator discussion in "The Little Schemer"
- Unable to get implementation of Y combinator working
- In Scheme, how do you use lambda to create a recursive function?
基本上，将 Y 定义为λr.(λh.h h) (λg.r (λx.(g g) x))，应用程序Y r简化为
Basically, with Y defined as λr.(λh.h h) (λg.r (λx.(g g) x)), an application Y r reduces as
Y r
(λw.(λh.h h) (λg.w (λx.(g g) x))) r
(λh.h h) (λg.r (λx.(g g) x))
h h
;where
h = (λg.r (λx.(g g) x)) <----\
|
(λg.r (λx.(g g) x)) h |
r (λx.(g g) x) <-------------- | ----------\
;where | |
g = h -----/ |
;so that |
(g g) = (h h) = r (λx.(g g) x) ------/
因此r必须期望两个参数-第一个表示要调用的递归函数，第二个-实际参数:
So r must expect two arguments - first representing the recursive function to be called, and second - an actual argument:
r = λf (λx. ....x.....(f y)...... )
以使(Y r) x减少为
(r (λx.(g g) x)) x
(r f) x
;where
f = (λx.(g g) x)
f y = (λx.(g g) x) y = (g g) y = (r f) y ; f is "fixed point" of r
定义f = (λx.(g g) x)的意思是，当调用f y时，将调用(g g) y，在该点上 g将被自动应用，r从中拉出"在g内部，并使用y参数调用(r f)的结果. IE.由(r f)应用程序产生的lambda表达式主体中的任何调用(f y)都将转换回(r f) y，即使用新的参数y调用同一主体.
The definiton f = (λx.(g g) x) means, when f y is called, (g g) y will be called, at which point g will be self-applied, r "pulled" from inside g and the result of (r f) called with y argument. I.e. any call (f y) in the body of lambda expression resulting from (r f) application, is translated back to (r f) y i.e. invocation of same body with a new argument y.
重要的实现细节是它是 same 函数体还是其 copy ，但是语义是相同的-我们能够输入相同的函数体带有新的参数值.
The important implementational detail is whether it is the same function body, or its copy, but the semantics are the same - we are able to enter the same function body with a new argument value.
Y组合器的本质是通过引用和自我应用进行复制:我们通过相同的 name 引用相同的事物两次；因此我们安排 it 接收本身作为参数.
The essence of Y combinator is replication through reference and self-application: we refer to the same thing through same name, twice; and thus we arrange for it to receive itself as an argument.
在没有引用的情况下(例如在纯lambda演算中)，并且参数会接收参数的文本副本(即通过文本重写进行归约)，这仍然有效，因为相同副本会被复制并传递，被作为self的参数，因此如果需要，可以在下一次迭代中使用.
When there's no referencing, as in pure lambda calculus, and parameters receive textual copies of arguments - i.e. reduction is done by textual rewriting - this still works, because same copies get replicated and passed around, being fed as argument to self so it is available on the next iteration, if need be.
但是，当共享引用可用时，效率会更高(相同名称的所有用法都与相同事物相关).在评估的环境模型下，自指功能的创建很简单
But it is much more efficient when shared referencing is available (all uses of same name refer to same thing). Under environment model of evaluation creation of self-referential function is simple as
(let ((fact #f))
(set! fact
(lambda (n) (if (< 2 n) 1
(* n (fact (- n 1))))))
fact)
实际上，您答案中的定义是应用顺序Y组合器的定义.对于正态，可以应用eta约简而不引起无限循环，以得到Ynorm = (λw.(λh.h h) (λg.w (g g)))，其通常写为
In fact the definition in your answer is that of applicative-order Y combinator. With normal-order, eta-reduction can be applied without causing infinite looping, to get Ynorm = (λw.(λh.h h) (λg.w (g g))) which is canonically written as
Ynorm = (λf.(λx.f (x x)) (λx.f (x x)))
确实
Ynorm g
= (λx.g (x x)) (λx.g (x x))
= g ((λx.g (x x)) (λx.g (x x)))
这篇关于Lisp中的定点组合器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
