如何跳出Lisp中的函数？

Question

在(Common)Lisp中是否可以跳转到另一个函数而不是调用另一个函数？我的意思是,当前函数被打破而另一个被调用,没有跳过数千个函数,就好像我决定自己是否完成尾调用优化,即使它不是尾部.我不确定"(从fn x返回)"是否,我想要什么.

例:

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

'jump'应该像调用下面的函数而不保存这个函数的位置,而是返回原来的funcall所在的位置,这样就不会有堆栈溢出.只有x为零才能执行'rest'.

Answer 1

当你需要一种尾部调用优化,比如结构中的语言没有(必然)提供它,但确实提供了闭包,你可以使用trampoline来实现持续的堆栈空间(对于闭包对象,堆空间的权衡,课程).这与您要求的不完全相同,但您可能会发现它很有用.在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,以及所返回的形实转换值提供了"下一个"计算的蹦床将调用你.

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