lisp - elisp 中的 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)) )

你可以 eta-expand x x 得到这个:

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

你应该看到这和工作的是一样的。因此，在纯数学 lambda 演算世界中，您的定义和工作定义是相同的。这导致你的结论不起作用，因为 Lisp 并不生活在纯数学 lambda 演算的世界中。确实是这样，具体区别在于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)

至于为什么您的代码使用词法绑定(bind)，简单的答案是这就是 lambda 演算的工作原理，并且试图让它与动态绑定(bind)一起工作会使一切都变得非常复杂而没有任何好处。