call/cc and proper tail recursion

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

   Date: Sat, 14 Nov 92 21:09:18 -0500
   From: "Aubrey Jaffer" <jaffer@martigny.ai.mit.edu>

      Date: Sat, 14 Nov 92 18:00:27 -0500
      From: "Aubrey Jaffer" <jaffer@martigny.ai.mit.edu>

	 I think the report needs to clarify the tail recursive property of
	 call/cc.

      I think so also; It should be clarified to NOT require
      CALL-WITH-CURRENT-CONTINUATION be tail-recursive.

MIT Scheme does not currently satisfy this criterion, but I see no
compelling reason why it should not or why we should not require it.
The requirement makes certain tricks harder (they have to be
implemented at the lowest level, instead of layered), but it is not
terribly hard to do that.

   While we are on this topic, there are 2 places where the requirement
   for tail-recursiveness becomes unworkable.  DYNAMIC-WIND is one:

   (define (foo)
     (DYNAMIC-WIND (lambda () #f)
		   foo
		   (lambda () #t)))

DYNAMIC-WIND is not tail recursive because it needs to perform some
action when returning from each of the thunks.  To a first
approximation, DYNAMIC-WIND is

(define (dynamic-wind before during after)
  (before)
  (let ((result (during)))
    (after)
    result))

which no one would expect to reduce to any of the thunks.

   And the other is some form of EVAL (which will be part of R5RS).

   (define (foo) (EVAL '(foo)))

EVAL should not be a problem for tail recursion.  If EVAL is written
in Scheme in the natural way, it is naturally tail-recursive.

   There are only 3 other essential procedures for which
   tail-recursiveness can be a problem, CALL-WITH-CURRENT-CONTINUATION,
   APPLY, and FOR-EACH.  CALL-WITH-CURRENT-CONTINUATION has been
   discussed already.  I think that APPLY and FOR-EACH should be exempted
   from the tail-recursive requirment.

   If one calls APPLY and FOR-EACH using the native subroutine call
   conventions on most computers they will not be tail-recursive.  It
   seems a shame to deny conformance to implementations soley for the
   sake of these 3 procedures.

I assume that by making FOR-EACH tail-recursive you mean that it
reduces to its last call of its first argument.  I don't see why this
is a problem, although it is not currently a requirement.  In fact,
the report implies that you cannot assume this.  If FOR-EACH were to
be required to reduce to the last call, the value returned by
FOR-EACH would have to be the value returned by that call, but the
report states that the value returned by FOR-EACH is unspecified.

With respect to APPLY, I feel strongly that it should reduce into its
first argument.  It makes writing properly-tail-recursive layered
interpreters a lot easier, and there is no good way of obtain its
effect if it is not.

I don't find the argument about the native subroutine call convention
compelling since the native subroutine call convention never (to my
knowledge) accomodates tail recursion, and thus, even if you want to
use it, you have to tweak it.