3

在 (Common) Lisp 中是否可以跳转到另一个函数而不是调用另一个函数？我的意思是，当前函数被破坏并调用另一个函数，而无需跳回数千个函数，就好像我自己决定是否完成了尾调用优化，即使它不是尾部。我不确定“（return-from fn x）”是否可以，我想要什么。

例子：

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

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

4

3 回答 3

5

当你需要一个尾调用优化，比如语言中不（必须）提供它但确实提供闭包的结构时，你可以使用蹦床来实现恒定的堆栈空间（权衡闭包对象的堆空间，课程）。这与您所要求的并不完全相同，但您可能会发现它很有用。在 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 的闭包。例如，非可变映射车的实现可能如下所示：

(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

如果不是，我们会返回一个重击：

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))
于 2014-02-26T16:02:03.747 回答
4

你如何使用尾调用？

(defun fn (x)
  (if x
      (progn
        (princ x)
        (fn (cdr x)))
      (progn
        (rest))))

它在尾部位置调用 fn。如果实现提供尾调用优化，您将不会出现堆栈溢出。如果您不想依赖它，则需要以非递归方式处理问题。Common Lisp 中没有明确的“删除此函数堆栈帧，然后调用函数 X”运算符。

于 2014-02-26T13:20:18.543 回答
0

嗯，不是真的。我曾经做过实验

(defmacro recurr (name bindings &body body)
  (let* ((names (mapcar #'car bindings))
         (restart (gensym "RESTART-"))
         (temp1 (gensym))
         (temp2 (gensym))
         (shadows (mapcar (lambda (name) (declare (ignore name)) (gensym)) names)))
    `(block ,name
       (let ,bindings
         (macrolet ((,name ,shadows
                      (list 'progn
                            (cons 'psetq
                                  (loop
                                    :for ,temp1 :in ',names
                                    :for ,temp2 :in (list ,@shadows)
                                    :nconcing (list ,temp1 ,temp2)))
                            (list 'go ',restart))))
           (tagbody
              ,restart
              (progn ,@body)))))))

并像方案的命名-let一样使用，例如：

(recurr traverse ((list '(1 2 3 4)))
   (if (null list) 'end 
       (traverse (cdr list))))

但：

  1. 定义的对象（traverse在示例中）不是一个函数，即你不能funcall或者apply它
  2. 这种构造并不能真正处理递归结构（即，由于没有保留堆栈，因此您不能使用它来遍历任意树而不是序列）

另一种方法可能是

(defmacro label (name (&rest bindings) &body body)
  `(labels ((,name ,(mapcar #'first bindings) ,@body))
     (,name ,@(mapcar #'second bindings))))

它实际上解决了提到的问题，但失去了“look ma，no stack space consing”属性。

于 2014-02-26T13:21:08.770 回答