3

我们可以定义一个递归函数，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 表达式？
4

1 回答 1

1

你说你理解这个定义：

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

您可以对其中的 s 进行 eta-expandx x以获得以下信息：

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

您应该看到这与工作中的相同。因此，在纯粹的数学 lambda 演算世界中，您的定义和工作定义是相同的。这导致您的结论不起作用，因为 Lisp 并不生活在纯粹的数学 lambda 演算世界中。确实如此，具体的区别在于 Lisp 是严格的，这导致它x x过早地评估 s，因此无限递归而无处可去。将它们包装在数学上不必要的 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 演算就是这样工作的，并且试图让它与动态绑定一起工作会使一切变得非常复杂而没有任何好处。

于 2020-05-12T16:26:05.733 回答