recursion - 错误时递归调用

Question

我的目标是一个可以无限期地再次调用自身的函数 遇到错误。 我正在描述我根据 Common Lisp HyperSpec 尝试过的不同方法，如果有人能揭示其中的 secret ，我将不胜感激 他们的行为就像他们所做的那样。 我使用启用了尾部调用优化的 SBCL 1.3.8，并验证它在简单的尾部递归函数上正常工作。

展开保护

使用我尝试的第一种方法，m0 被调用两次。一次作为原始调用的结果，一次作为展开保护中清理表单的一部分。 在第二个主体中遇到错误后，它无法正确执行清理表单。

我预计该函数会一遍又一遍地调用自身，并遇到堆栈溢出或 SBCL 能够将该调用识别为尾部调用并对其进行优化。

(defun m0 ()
  (unwind-protect
       (progn
         (write-line "body")
         (error "error"))
    (write-line "cleanup")
    (m0)))
(m0)

出于对结果的兴趣，我调查了这是否是一般嵌套展开保护的情况，看起来确实如此。以下程序显示相同的行为:

(unwind-protect
     (progn
       (write-line "body 0")
       (error "error 0"))
  (unwind-protect
       (progn
         (write-line "body 1")
         (error "error 1"))
    (write-line "body 2")
    (error "error 2"))))

此行为与内部 unwind-protect 的退出程度有关吗？ 有没有办法让它工作，特别是支持尾调用消除的方法？ 为什么unwind-protects不能任意嵌套？

处理程序案例

我尝试的第二种方法遇到了堆栈溢出。这并不像第一种方法的结果那么令人惊讶，但在不知道条件系统的内部细节的情况下，我预计该函数是尾递归的，因此我预计 SBCL 会优化尾部调用。

(define-condition m-error () nil)

(defun m1 ()
  (handler-case
      (progn (write-line "body")
             (error 'm-error))
    (m-error ()
      (progn (write-line "cleanup")
             (m1)))))
(m1)

是否有一种方法可以稍微修改该函数以确保发生尾调用消除？

处理程序绑定(bind)

由于达到为运行时环境定义的最大错误深度而引发错误。 我原本期望它的性能与处理程序案例解决方案大致相同。在这种情况下，由于 handler-case 和 handler-bind 的不同行为，在执行清理表单之前堆栈不会展开，但我仍然期望对 m 的调用被识别为尾部调用并在宏伟的计划。

(defun m2 ()
  (handler-bind
      ((m-error #'(lambda (c)
                    (progn (write-line "cleanup")
                           (m2)))))
    (write-line "body")
    (error 'm-error)))
(m2)

与 m1 相关的问题也适用于此。

我想知道为什么这些案例不能像我根据文档预期的那样工作。 freenode 上#lisp 中的人们也对这种行为感到困惑。

如果没有办法修复这些示例，那么我希望有一个指向可以实现此行为的构造的指针，而无需将控制权返回到更高级别。

Answer 1

首先，不能保证这是可能的:CL 语言根本没有被指定为尾递归，因此完全取决于实现是否优化尾调用以及何时优化尾调用do，什么相对于什么处于尾部位置。

其次，您的第一个 unwind-protect 实现可能不会按照您的想法执行，您的第三个也不会。在第三种实现的情况下，您的处理程序无法处理错误，这本质上意味着代码不可能是尾递归的，因为处理程序必须保留在堆栈上，直到它正常返回或处理错误为止，两者都不是确实如此。

handler-bind 实现

正如我认为handler-bind没有被广泛理解，这是你的第三个实现的一个版本，它可能有机会进行尾递归:处理程序确实处理错误，然后它跳转到的代码递归。

(define-condition m-error ()
  ())

(defun m4 ()
  (let* ((errored nil)
         (result
          (block escape
            (handler-bind ((m-error
                            #'(lambda (c)
                                (declare (ignorable c))
                                (setf errored t)
                                (return-from escape nil))))
              (error 'm-error)))))
    (if (not errored)
        result
      (m4))))

但是，在我可以立即访问的两种实现(LW 和 CCL)中，都不会轻松地将其编译为对 m4 的尾部调用(两种实现都会优化尾部调用)。

我还尝试了该解决方案的更可怕但更明确的版本:

(defun m5 ()
  (tagbody
   (return-from m5
     (handler-bind ((m-error
                     #'(lambda (c)
                         (declare (ignorable c))
                         (go recurse))))
       (error 'm-error)))
   recurse
   (m5)))

而且我无法将对 m5 的递归调用编译为尾调用。可能要理解为什么他们不需要查看汇编程序。

unwind-protect 实现

我不清楚这是否可行。特别要记住的是

unwind-protect evaluates protected-form and guarantees that cleanup-forms are executed before unwind-protect exits, whether it terminates normally or is aborted by a control transfer of some kind.

(来自 CLHS 。)

所以任何看起来像这样的代码

(defun m6 ()
  (unwind-protect
      ...any form...
    (m6)))

无论发生什么都会递归地调用自身。特别是，当您在...任何形式...出现任何错误后退出调试器时，它几乎肯定会这样做，如果没有错误，它肯定会这样做...任何形式...，只要它终止，并且当您退出 Lisp 实现本身时，它很可能会尝试调用自身。事实上，这个函数可能会使重新获得控制变得相当困难:它根本不明显地终止，或者很容易强制它这样做，即使通过中断评估也是如此。

像下面这样的东西会给你更多的逃脱机会:

(defun m7 ()
  (let ((errored nil))
    (unwind-protect
        (handler-case
            (error 'm-error)
          (m-error ()
            (setf errored t)))
      (when errored
        (m7)))))

一个非常可怕的实现

真正的程序员(正确地称为REAL PROGRAMMERS)当然会编写以下版本，这样就不必担心所有这些时髦的“尾递归”废话:

(defun m8 ()
  (tagbody
   loop
   (return-from m8
     (handler-bind ((m-error
                     #'(lambda (c)
                         (declare (ignorable c))
                         (go loop))))
       (error 'm-error)))))

(除非他们用大写书写)。