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)))
  )
)

问题

为什么会这样？我错过了什么吗？
为什么我们需要将 lexical-binding 设置为 t？
是否有 (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 演算的世界中。确实是这样，具体区别在于 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 演算就是这样工作的，并且试图让它与动态绑定一起工作会使一切都变得非常复杂而没有任何好处。

elisp 中的 Y 组合器

Y combinator in elisp

lisp

elisp

lambda-calculus

combinators

y-combinator

问题