3 ms·
There are three distinct concepts that are often conflated: 1) The syntactic construct of a tail call. 2) Abstract space efficiency properties that guarantee
by cwzwarich 8y ago
There are three distinct concepts that are often conflated:
1) The syntactic construct of a tail call.
2) Abstract space efficiency properties that guarantee asymptotic space usage of programs using tail calls.
3) The implementation techniques used to guarantee 2).
Even though the implementation techniques of 3) apply to all calls, the space efficiency properties in 2) are asymptotic and thus are only meaningful when applied to programs with unbounded recursive function invocations. Applying the techniques of 3) only to function calls that might potentially be involved in a recursive chain would still satisfy any of the standard definitions of 2).
See Will Clinger's paper Proper Tail Recursion and Space Efficiency (https://dl.acm.org/citation.cfm?id=277719 https://dl.acm.org/citation.cfm?id=277719) for details regarding the standard definition of "proper tail recursion" used in the Scheme spec and elsewhere.
- iuoershg 8y agoIf so, can a purely functional language require no more than one stack frame?
- nailuj 8y agoIt depends on what you mean by purely functional, the lambda calculus certainly doesn't require stack frames. Even better, you can implement any programming language without a stack. Stack frames are only a convenience feature for programmers after all (well, and many architectures probably do some hardware optimizations when using the stack related registers for stack things).