我们可以定义一个递归函数,以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 表达式?
最佳答案
你说你理解这个定义:
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)一起工作会使一切都变得非常复杂而没有任何好处。
关于lisp - elisp 中的 Y 组合器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61751659/