[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

tail recursion

    In order to fit Scheme into this environment, the rules were broken. 
    While many tail calls are converted into goto's, those that had to
    cross procedure boundaries in the intermediate language are implemented
    as conventional calls.

    To date, this approach has worked.  The users of this system seem to
    feel that the advantages of an easily ported system with a compiler
    that emits code that is compatible with other languages on the system
    outweigh the fact that it doesn't do every tail call correctly.

The question is whether the compromise was necessary.  There are ways,
although perhaps expensive, to achieve both goals.  You decided that
further investment into maintaining tail recursion was unnecessary,
and I may even agree with your decision in the context of Scheme->C,
but it in no way convinces me that the requirement should be dropped.
I'd be much happier if your compiler had an option that allowed me to
obtain full tail recursion even at a potential expense.

Note that full tail-recursion could be implemented even in your
context in the following horrible but straight forward way.  I'm sure
that there are better ways:

There is a large global array used as a temporary to pass arguments to
top-level procedures.  There is also an an associated convention to handle
parameter lists longer than the array size.

Top level procedures (including the initial one, corresponding to main
in C) are always called through an interface routine.

This interface routine takes the parameters from the global area and
passes them wherever C procedures expect them (the stack).  It should
be no harder to write this than to write the low level primitive for
cwcc that your system has, or whatever you do for closures.

This interface routine also does the equivalent of a C setjmp (I'm
sure your back end supports this C library procedure), and chains
together the longjmp buffers that result from nested calls.  The
current buffer is pointed at by a global variable.

When a top-level procedure wants to do a tail-call, it only needs to
place the procedure pointer, argument count, and parameters, in the
global area, and longjmp to the current buffer.

If any of the procedures invoked by the interface routine ever
returns, the interface routine unwinds the longjmp chain once, and
returns to it's caller with the result of the called routine.