[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
call/cc and proper tail recursion
(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.
If one calls APPLY [...] 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.
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.
The requirements for tail-recursion in procedure calls and in
expressions other than procedure calls are very different. The SCM
interpreter has no difficulty in executing all non-procedure call
expressions tail-recursively; Eval only recurses with a C call to eval
if it is not tail-calling. The SCM compiler also generates tail calls
(jumps) within top level procedures from code analysis.
The situation for subrs is quite another matter. Tail-call is just
not a portable feature. However, there are only 3 procedures which
would need it: CALL-WITH-CURRENT-CONTINUATION, APPLY, and EVAL (thank
you for the corrections). If these 3 were primitive expressions types
then there would be no problem because their code could be in eval and
they could be tail-called like all other primitive and derived
It is a strange accident that these 3 control primitives are
procedures rather than primitive expression types. They could not be
expressed in terms of the primitive expression types without
constructing a meta-interpreter (or having arity functions in the case
of APPLY). In the case of APPLY, having it be a procedure is useful
because it offers a way for other languages to call Scheme procedures.
Note that single-argument EVAL cannot be used for this purpose; EVAL
takes Scheme code as an argument and there are many Scheme objects
which cannot be expressed as Scheme code.
I will probably solve the problem for SCM by creating hidden
expression types for CALL-WITH-CURRENT-CONTINUATION, EVAL, and APPLY
which are called by interpreted procedures. This is no problem for
the first 2, but handling APPLY will cause substantial duplication of
code since I need a subr APPLY as well.