stodghil@urd.cs.cornell.edu (Paul Stodghill) (12/07/90)
Yesterday I posed the question, What compile-time transformation can be made to remove the tail-recursiveness from Scheme? From mail that I have received, it is clear that I didn't pose the question that I meant to. I understand how a compiler can generate code when will exhibit iterative behavior at runtime: Don't use procedure calls, use goto. One small problem: I am thinking of using an intermediate representation which only allows calls and returns between procedures, not gotos. The intermediate language has a very definite notion of runtime stack which I can't monkey with. If possible, I want to avoid making runtime decisions. I want to schedule everything at compile time. So, I want to discover at compile time all of the "syntactic" loops in a Scheme program. I want to use a looping construct in the intermediate language for these loops, and let call/return handle all other procedure calls. Let me ask two questions. First, When the Revised Report says that Scheme handles tail-recursion iteratively, does this mean that any program which would execute tail-recursively, even if the compiler has no hope of discovering this, must run in constant space. If this is what is meant, why does the Report refer to "syntactically" recursive procedure? Second, If I only need to handle tail recursion which is _statically_ present in a program, exactly what is the criteria for a "syntactically" recursive procedure? I am aware of the Joel Bartlett's Scheme->C compiler. I intend to look closely at this to see what sort of decisions he made.
harlan@iuvax.cs.indiana.edu (Pete Harlan) (12/09/90)
stodghil@urd.cs.cornell.edu (Paul Stodghill) writes: >I want to use a looping >construct in the intermediate language for these loops, and let call/return >handle all other procedure calls. But tail-calls are used for more than just loops -- continuation- passing style programs, for example, rely on tail recursion. That's why it isn't just an implementation concern, it's a language-design issue. Pete Harlan harlan@iuvax.cs.indiana.edu