省略号中的Y组合器

Question

我们可以通过factorial定义递归函数，例如YCombinator，如下所示

;;; elisp
;;; This code works. Thanks to
;;; https://www.diegoberrocal.com/blog/2015/10/12/y-combinator-in-emacs-lisp/ 

(setq lexical-binding t)  ;;; lexical == static ??

(defun YCombinator (f)
  (funcall #'(lambda (x) (funcall f
                            #'(lambda (y) (funcall (funcall x x) y))))

           #'(lambda (x) (funcall f
                            #'(lambda (y) (funcall (funcall x x) y))))
  )
)

(setq meta-factorial
      #'(lambda (f) #'(lambda (n) (if (eq n 0) 1 (* n (funcall f (1- n)))))))

(funcall (YCombinator meta-factorial) 4) ;; ===> 24

我了解了什么是Y组合器，并且知道如何以数学方式对其进行定义。

Y: f -> ( (x -> f(x x)) (x -> f(x x)) )

但是我发现很难实施。特别是，我对YCombinator的定义似乎更接近于数学定义，但没有定义factorial。

;; this code fails!

(defun YCombinator (f)
  (funcall #'(lambda (x) (funcall f
                            #'(funcall x x)))

           #'(lambda (x) (funcall f
                            #'(funcall x x)))
  )
)

问题

1. 为什么会这样？我错过了什么吗？
2. 为什么我们需要将lexical-binding设置为t？
3. 是否存在（e）lisp转换器的lambda表达式？

Answer 1

您说您了解此定义：

Y: f -> ( (x -> f(x x)) (x -> f(x x)) )

您可以对其中的x x进行eta展开以得到此信息：

Y: f -> ( (x -> f(y -> x x y)) (x -> f(y -> x x y)) )

并且您应该看到这与正常工作的相同。因此，在纯数学lambda演算世界中，您的定义和有效的定义是相同的。这导致您的结论不起作用，因为Lisp不在纯数学lambda-calculus世界中生活。确实是这种情况，并且特定的区别在于Lisp严格，这导致它过早评估x x，因此无限递归而无处可寻。将它们包装在数学上不必要的lambda周围，可以满足严格性要求。最后要说明的是，如果您尝试使用一种惰性语言来实现此目的，则不需要该解决方法。例如，这是您的代码到Lazy Racket的音译，没有它就可以正常工作：

#lang lazy
(define (YCombinator f) ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))
(define meta-factorial (lambda (f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1)))))))
((YCombinator meta-factorial) 4)

关于为什么您的代码使用词法绑定的原因很简单，那就是lambda演算是如何工作的，而试图使其与动态绑定一起使用将使所有事情变得毫无意义地复杂化。