Tail recursive Common Lisp interpreter?

[edsel!eb@su-navajo.arpa (Eric Benson)]

Recently, we added a new feature to our compiler: general tail-recursion
removal.  That is, when FOO returns the value of calling BAR, there is
no need to grow the stack; BAR can use the same stack frame as FOO and
return to its caller.  Scheme requires this behavior, so that iteration
can be defined in terms of recursion.  Scheme supporters tend to get
irate about Lisp implementations which do not have this behavior.  In
fact, they call this "properly tail-recursive," giving a moral tone to
the whole issue.

When I wrote our interpreter, I tried to be very careful so that if it
were compiled with a compiler which does tail recursion elimination, it
too would be properly tail recursive.  Finally, I had a chance to try it
out.  I compiled EVAL, loaded it in and typed

(DEFUN FOO (X)
  (IF (ZEROP X)
      (BREAK)
      (FOO (1- X))))

(FOO 10)

thus entering the debugger, expecting to find no frames on the stack.
To my dismay, I saw 10 BLOCK frames.  Then it dawned on me: every DEFUN
wraps a BLOCK around the body, so that I would have been able to say
(RETURN-FROM FOO ...) anywhere in my definition.  BLOCK is implemented
with a CATCH in the interpreter, and the last call of a CATCH is not
tail recursive; the CATCH frame must be removed from the stack before
returning.  Even FLET and LABELS aren't tail recursive, for the same
reason, due to our recent extension to them of the "implicit BLOCK"
feature.  Only raw LAMBDAs are truly tail recursive.

I would like to change this, but I don't want to do a lot of static
analysis in the interpreter. That tends to defeat the purpose of EVAL,
which I take to be fast turnaround time in testing code.  I can't see
any other way of implementing the implicit BLOCK except using CATCH or
some other mechanism which defeats tail recursion.  Does anyone have any
clever ideas for solving this problem?