Q:

Recursive call on error

My goal is a function which can call itself again indefinitely upon
encountering an error.
I am describing different approaches I tried based on the Common Lisp HyperSpec and would appreciate if someone could reveal the secrets of why
they act as they do.
I'm using SBCL 1.3.8 with enabled tail call optimization and verified that it is working properly on a simple tail recursive function.
unwind-protect
With the first approach I tried, m0 gets called twice. Once as a result of the original call and once as part of the cleanup form in the unwind-protect.
After encountering the error in the second body, it does not execute the cleanup form properly.
I would have expected for the function to call itself over and over again, and to run into a stack overflow or for SBCL to be able to recognize the call as a tail call and to optimize it.
(defun m0 ()
  (unwind-protect
       (progn
         (write-line "body")
         (error "error"))
    (write-line "cleanup")
    (m0)))
(m0)

Intrigued by the result, I investigated whether it was an occurrence with nested unwind-protects in general, and it seems to be. The following program displays the same behavior:
(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"))))

Is this behavior related to the extent of the exit of the inner unwind-protect?
Is there a way to get it to work and especially a way which supports tail call elimination?
Why can the unwind-protects not be nested arbitrarily?
handler-case
The second approach I tried runs into a stack overflow. This is not as surprising as the result of the first approach, but without knowing the inner details of the condition system, I would have expected the function to be tail recursive and therefore I would have expected for SBCL to optimize the tail call.
(define-condition m-error () nil)

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

Is there a way in which the function could be slightly modified to ensure that tail call elimination will occur?
handler-bind
Throws an error due to reaching the maximum-error-depth defined for the runtime environment.
I would have expected this to perform roughly equal to the handler-case solution. The stack is not unwound before executing the cleanup forms in this case due to the different behavior of handler-case and handler-bind, but I still would have expected for the call to m to be recognized as a tail call and to be optimized in the grand scheme of things.
(defun m2 ()
  (handler-bind
      ((m-error #'(lambda (c)
                    (progn (write-line "cleanup")
                           (m2)))))
    (write-line "body")
    (error 'm-error)))
(m2)

The question related to m1 applies here, too.
I would like to know why these cases do not work as I expected them to work, based on the documentation. The people in #lisp on freenode were also puzzled by this behavior.
And if there is no way in which these examples can be fixed, then I would appreciate a pointer to some construct with which this behavior could be implemented, without returning control to a higher level.

A:

Firstly, there is no guarantee that this is possible at all: CL the language is not specified to be tail-recursive at all, and thus it is entirely up to implementations both as to whether they optimise tail calls and, when they do, what is in tail position with respect to what.
Secondly, your first, unwind-protect implementation probably does not do what you think it does, and neither does your third.  In the case of the third implementation your handler fails to handle the error which essentially means that there is no hope of the code being tail-recursive, since the handler must remain on the stack until it either returns normally or handles the error, neither of which it does.
The handler-bind implementation
As I think handler-bind is not widely understood, here is a version of your third implementation which might stand a chance of being tail-recursive: the handler does handle the error, and then the code it jumps to recurses.
(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))))

However, in neither of the implementations to which I have immediate access (LW and CCL) will this easily compile as a tail call to m4 (both implementations do optimise tail calls).
I also tried a more horrible but explicit version of this solution:
(defun m5 ()
  (tagbody
   (return-from m5
     (handler-bind ((m-error
                     #'(lambda (c)
                         (declare (ignorable c))
                         (go recurse))))
       (error 'm-error)))
   recurse
   (m5)))

And I can't get either implication to compile the recursive call to m5 as a tail call.  Probably to understand why they won't would require looking at the assembler.
The unwind-protect implementation
It's not clear to me that this can work.  In particular, remember that

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.

(From the  CLHS.)
So any code which looks like
(defun m6 ()
  (unwind-protect
      ...any form...
    (m6)))

is going to call itself recursively whatever happens.  In particular it will almost certainly do so when you exit the debugger after any error in ...any form..., will certainly do so if there is no error in ...any form..., so long as it terminates, and it may very well try to call itself when you exit the Lisp implementation itself.  Indeed this function may make it reasonably hard to regain control: it is not at all obvious that it terminates or that it is easily possible to force it to do so, even by interrupting evaluation.
Something like the following gives you more chance of escape:
(defun m7 ()
  (let ((errored nil))
    (unwind-protect
        (handler-case
            (error 'm-error)
          (m-error ()
            (setf errored t)))
      (when errored
        (m7)))))

A deeply horrid implementation
Real Programmers (who are correctly known as REAL PROGRAMMERS) would of course write the following version, which avoids having to worry about all this hipster 'tail recursion' nonsense:
(defun m8 ()
  (tagbody
   loop
   (return-from m8
     (handler-bind ((m-error
                     #'(lambda (c)
                         (declare (ignorable c))
                         (go loop))))
       (error 'm-error)))))

(except they would write it in UPPERCASE).

