return - 如何跳出 Lisp 中的函数？

Question

在(通用)Lisp 中是否可以跳转到另一个函数而不是调用另一个函数？ 我的意思是，当前函数被破坏并调用了另一个函数，没有通过数千个函数跳回，就好像我自己决定是否完成尾部调用优化，即使它不是尾部. 我不确定“(return-from fn x)”是否符合我的要求。

例子:

(defun fn (x)
  (when x
    (princ x)
    (jump 'fn (cdr x)))
  (rest))

'jump'应该是像调用后面的函数一样，不保存这个函数的位置，而是返回到原来funcall所在的地方，这样就不会出现stack overflow。 'rest' 只应在 x 为 nil 时执行。

Answer 1

当你需要尾调用优化，比如在一种语言中(不一定)提供它但提供闭包的结构时，你可以使用蹦床来实现恒定的堆栈空间(为闭包堆空间进行权衡)当然是对象)。这与您要求的不完全相同，但您可能会发现它很有用。在 Common Lisp 中很容易实现:

(defstruct thunk closure)

(defmacro thunk (&body body)
  `(make-thunk :closure (lambda () ,@body)))

(defun trampoline (thunk)
  (do ((thunk thunk (funcall (thunk-closure thunk))))
      ((not (thunk-p thunk)) thunk)))

要使用蹦床，您只需使用执行第一部分计算的 thunk 来调用它。该闭包可以返回另一个 thunk 或结果。如果它返回一个 thunk，那么因为它返回 初始栈帧被回收，然后调用返回的 thunk 的闭包。例如，非可变 mapcar 的实现可能如下所示:

(defun t-mapcar1 (function list)
  (labels ((m (list acc)
             (if (endp list)
                 (nreverse acc)
                 (thunk 
                   (m (rest list)
                      (list* (funcall function (first list)) acc))))))
    (m list '())))

当列表为空时，我们立即得到一个空列表:

CL-USER> (t-mapcar1 '1+ '())
NIL

如果不是，我们会返回一个 thunk:

CL-USER> (t-mapcar1 '1+ '(1 2))
#S(THUNK :CLOSURE #<CLOSURE (LAMBDA #) {10033C7B39}>)

这意味着我们应该用 trampoline 包装一个调用(这对于基本情况也很好，因为 trampoline 传递非 thunk 值):

CL-USER> (trampoline (t-mapcar1 '1+ '()))
NIL
CL-USER> (trampoline (t-mapcar1 '1+ '(1 2)))
(2 3)
CL-USER> (trampoline (t-mapcar1 '1+ '(1 2 3 4)))
(2 3 4 5)

您的示例代码不足以作为说明性示例，但是

(defun fn (x)
  (when x
    (princ x)
    (jump 'fn (cdr x)))
  (rest))

会变成下面这样。 return 提供了 fn 的提前终止，返回的 thunk 值提供了蹦床将为您调用的“下一个”计算。

(defun fn (x)
  (when x
    (princ x)
    (return (thunk (fn (cdr x)))))
  (rest))