Re: tail recursion

[bartlett@wrl.dec.com]

[In reply to RPG@sail.stanford.edu sent 24 Apr 90  1832 PDT]

Based on my experience implementing Scheme, I support rpg's proposal
that tail call removal be considered optional and implementers be given
strong advice on what might be expected from the system. 

The Scheme-to-C system done at WRL, Scheme->C, grew out of a project
investigating the problems in implementing a LISP system on the WRL
built Titan. All compilers on the Titan are required to compile to an
intermediate language.  This language is then optimized and compiled
into machine code for a specific hardware implementation. 

Programs in the intermediate language are divided into procedures. 
Within a procedure, one can transfer control by goto's, but the only
way to transfer control between procedures is via a call.  The
intermediate language hides such things as general purpose registers
and the mechanics of procedure call and return.  As is the case with
the MIPS intermediate language system, the Titan does not support tail call. 

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.

jfb