Re: requiring proper tail recursion

[Guillermo J. Rozas <gjr@martigny.ai.mit.edu>]

|   Date: Tue, 2 Sep 1997 17:22:45 -0400
|   From: Richard Kelsey <kelsey@research.nj.nec.com>
|   Subject: Re: requiring proper tail recursion
|   
|   
|      Date: Tue, 02 Sep 1997 10:13:25 -0500
|      From: William D Clinger <will@ccs.neu.edu>
|      References: <199708291400.KAA25450@kima.nj.nec.com> <ogtyb5jttwn.fsf@laozi.mitre.org>
|   
|      EVAL is probably a bit more controversial.  It appears to me that
|      requiring EVAL to evaluate its argument within a tail context might
|      rule out implementations that implement a fully reflective tower of
|      interpreters.  It might also rule out implementations that must
|      perform some kind of context switch when transferring between native
|      and interpreted Scheme code; several existing implementations do
|      this, and have good reasons for doing this.
|   
|   The tail-recursion requirement does make it harder to implement
|   a mixed native-code/interpreted system, but the problem isn't
|   with calls to EVAL itself.  Given an EVAL that does not evaluate
|   its argument in a tail context it is easy to write an EVAL that
|   does (modulo problems with LAMBDA having a nonstandard binding
|   in the specified environment):
|   
|      (define tr-eval
|        (lambda (exp env-spec)
|          ((eval `(lambda () ,exp)
|                  env-spec))))

Or "expressions" that are top-level definitions in implementations
that allow it.

I don't feel strongly either way in the case of explicit calls to
EVAL, but I do believe that proper tail recursion should be maintained
between interpreted and compiled-to-native code in implementations
that support it.

MIT Scheme goes through some contortions to make tail recursion work
from interpreted code to compiled code and viceversa.  The
contortions have nothing to do with EVAL per se, since the system can
boot and run (or used to be able to) without any native code at all.
They are a consequence of maintaining proper tail recursion across the
interpreter/native code boundary.  EVAL is free.

The contortions involve the following loose algorithm at cross-domain
calls:

Interpreter -> native code

  Examine top continuation/stack frame:
  - If continuation has special interpreter return code
    return-to-native, eliminate frame from stack and emulate
    native->native call.
  - If continuation has any other return code, push the special
    "native->interpreter" native return frame on stack
    and emulate native->native call.

Native code -> Interpreter
	
  Examine top continuation/stack frame:
  - If continuation has special "native->interpreter" return address,
    eliminate frame from stack and emulate interpreter->interpreter
    call.
  - If continuation has any other return address, push special
    "return-to-native" return code frame on stack and emulate
    interpreter->interpreter call.

Needless to say, all this stack/continuation examination is done by
the interpreter.  Native code calls code assuming that it is compiled
to native and lets the recovery "hooks" fix it up.