Y组合子在Elisp中的应用

Question

我们可以通过Y组合子定义递归函数，以阶乘为例，如下所示：

;;; 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. 是否存在将 lambda 表达式转换成 (e)lisp 的翻译器？

- Student

---

如果你想探索Y，我建议不要使用elisp。使用Scheme或其他语言吧。 - user5920214

@tfb 很有趣！您能否详细解释一下为什么Scheme是更好的选择？ - Student

用两种语言都写下 Y... - user5920214

通常情况下，您应该避免在Emacs Lisp中使用#引用lambda表达式：https://emacs.stackexchange.com/questions/3595/when-to-sharp-quote-a-lambda-expression - Metropolis

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-calculus 世界中，你的定义和正常工作的代码是相同的。这导致了这样一个结论：你的代码之所以不起作用，是因为 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演算的工作原理，尝试使用动态绑定会显著增加复杂性，却没有任何好处。

- Joseph Sible-Reinstate Monica

---

1. 在我发布的工作代码中，还有 ..(funcall x x)..。为什么它没有被过早地求值？
2. 直接在 Haskell 中执行此操作会导致错误，因为有类型限制。这更加棘手，但可以通过一些方法解决，请参阅我的问题。

- Student

1. 因为它被包含在 lambda (y) 中，而 lambda 的主体直到调用时才会被评估。
2. 是的，也许 Haskell 不是最好的具体例子，因为它的类型系统。我想不出任何一种语言，既具有惰性又具有足够弱的类型系统来编写它。

- Joseph Sible-Reinstate Monica

很棒的答案！今天我学到了可以使用lambda表达式来制作(e)lisp。至于第二点...是啊，我想知道为什么没有一种语言能让我们自由选择是否要输入/不输入、延迟/不延迟... - Student

@JosephSible-ReinstateMonica：你可以在Racket中懒惰地写出明显的Y。 - user5920214

@tfb 谢谢。回答已经编辑，现在可以将其用作示例。 - Joseph Sible-Reinstate Monica