Y组合器实施方案 [英] Y Combinator implementation Scheme

问题描述

我真的是计划函数编程的新手.最近，我在lambda演算中遇到了Y-combinator函数，就像这样的Y ≡ (λy.(λx.y(xx))(λx.y(xx))).我想在方案中实现它，我进行了大量搜索，但没有找到与上述给定结构完全匹配的实现.我发现其中一些如下:

I am really new to scheme functional programming. I recently came across Y-combinator function in lambda calculus, something like this Y ≡ (λy.(λx.y(xx))(λx.y(xx))). I wanted to implement it in scheme, i searched alot but i didn't find any implementation which exactly matches the above given structure. Some of them i found are given below:

(define Y
(lambda (X)
  ((lambda (procedure)
     (X (lambda (arg) ((procedure procedure) arg))))
   (lambda (procedure)
     (X (lambda (arg) ((procedure procedure) arg)))))))

和

(define Y
  (lambda (r)
    ((lambda (f) (f f))
     (lambda (y)
       (r (lambda (x) ((y y) x)))))))

如您所见，它们与此Y ≡ (λy.(λx.y(xx))(λx.y(xx)))组合器函数的结构不匹配.如何以完全相同的方式在方案中实现它?

As you can see, they dont match with the structure of this Y ≡ (λy.(λx.y(xx))(λx.y(xx))) combinator function. How can I implement it in scheme in exactly same way?

推荐答案

在诸如Lazy Racket之类的惰性语言中，您可以使用常规订单版本，但不能在任何适用的顺序编程语言(如Scheme)中使用.他们将陷入无限循环.

In a lazy language like Lazy Racket you can use the normal order version, but not in any of the applicative order programming languages like Scheme. They will just go into an infinite loop.

Y的适用版本通常称为Z组合器:

The applicative version of Y is often called a Z combinator:

(define Z
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (g)
       (f (lambda args (apply (g g) args)))))))

现在，应用此程序时发生的第一件事是(g g)，并且由于您始终可以用其主体的扩展替换整个应用程序，因此可以将函数的主体重写为:

Now the first thing that happens when this is applied is (g g) and since you can always substitute a whole application with the expansion of it's body the body of the function can get rewritten to:

(define Z
  (lambda (f)
    ((lambda (g)
       (f (lambda args (apply (g g) args))))
     (lambda (g)
       (f (lambda args (apply (g g) args)))))))

我还没有真正改变任何东西.只是做一些完全相同的代码而已.请注意，此版本使用apply来支持多个参数函数.想象一下Ackermann函数:

I haven't really changed anything. It's just a little more code that does exactly the same. Notice this version uses apply to support multiple argument functions. Imagine the Ackermann function:

(define ackermann
  (lambda (m n)
    (cond
      ((= m 0) (+ n 1))
      ((= n 0) (ackermann (- m 1) 1))
      (else (ackermann (- m 1) (ackermann m (- n 1)))))))

(ackermann 3 6) ; ==> 509

这可以通过Z来完成，例如:

This can be done with Z like this:

((Z (lambda (ackermann)
      (lambda (m n)
        (cond
        ((= m 0) (+ n 1))
        ((= n 0) (ackermann (- m 1) 1))
        (else (ackermann (- m 1) (ackermann m (- n 1))))))))
 3
 6) ; ==> 509

请注意，实现完全相同，不同之处在于如何处理对自身的引用.

Notice the implementations is exactly the same and the difference is how the reference to itself is handled.

编辑

所以您要问评估如何延迟.正常的订购版本如下所示:

So you are asking how the evaluation gets delayed. Well the normal order version looks like this:

(define Y
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (g) (f (g g))))))

如果查看如何将其与参数一起使用，您会注意到Y永远不会返回，因为在它可以在(f (g g))中应用f之前，它需要先评估(g g)，然后再评估(f (g g))为了挽救我们不立即应用(g g).我们知道(g g)成为一个函数，所以我们只给f一个函数，该函数在应用时将生成实际函数并应用它.如果您具有函数add1，则可以制作一个包装程序(lambda (x) (add1 x))，而可以使用它，它将起作用.以同样的方式(lambda args (apply (g g) args))与(g g)相同，您可以通过应用替换规则来看到这一点.这里的线索是，这将有效地停止每一步计算，直到将其实际使用为止.

If you look at how this would be applied with an argument you'll notice that Y never returns since before it can apply f in (f (g g)) it needs to evaluate (g g) which in turn evaluates (f (g g)) etc. To salvage that we don't apply (g g) right away. We know (g g) becomes a function so we just give f a function that when applied will generate the actual function and apply it. If you have a function add1 you can make a wrapper (lambda (x) (add1 x)) that you can use instead and it will work. In the same manner (lambda args (apply (g g) args)) is the same as (g g) and you can see that by just applying substitution rules. The clue here is that this effectively stops the computation at each step until it's actually put into use.

这篇关于Y组合器实施方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！