71–72 of 72 posts
Earlier quoted context omitted.
You can turn it off, you just can't process large data sets, as you'd run out of stack space. But who wants to debug with large data sets?
People who are debugging behaviour with large data sets perhaps? :P
Earlier quoted context omitted.
Despite the name "tail call optimization", the proper implementation of tail calls is not "just" an optimization. Preserving a stack frame for a function which has nothing left to do is incorrect behavior on the part of the compiler which negatively impacts both the time and space complexity of the resulting object code. The code, as written, does not require a stack frame. If the compiled object code crashes it is n…
> nothing left to do is incorrect behavior on the part of the compiler But it's not though. By this token failing to optimize anything could be considered incorrect behavior. Obviously not turning on optimizations makes your program take longer and use more memory. When a function call is made its variables are pushed onto the stack and popped when the function returns. Doing something different when the compiler det…
Yes, but it shouldn't take an algorithm which only requires constant space as written and turn it into object code which requires linear space.
Update: Elaborating on this point somewhat—Consider the case of a simple loop with a local variable. The variable is specific to the body of the loop; each iteration, in effect, has its own copy of the variable. What if a compiler implementer decided, for the sake of simplicity, to allocate block-local variables with alloca(), so that new memory is reserved from the stack for each loop iteration, and only freed when the enclosing function returns? Perhaps an optional optimization is provided -floop-variable-space-optimization which "lifts" the variable out of the loop, allowing the memory to be reused and restoring constant space complexity. Would you still consider this an acceptable implementation on the grounds that "obviously not turning on optimizations makes your program ... use more memory"? I think not.
> When a function call is made its variables are pushed onto the stack and popped when the function returns.
That is nothing more than an unfortunate, naïve implementation choice common among compilers which do not implement tail calls properly. Nothing in the definition of a function or a function call requires the use of a stack. What is required is only a continuation—a reference to the code to be executed when the function is finished. When there is a chain of calls F -> G -> H, and the G -> H call is in tail position, the natural continuation for that call is the same continuation which was provided to G. A compiler which does not implement tail calls properly, however, interposes an extra, unnecessary continuation for the call to H, turning a (potentially) constant-space function into a linear one.
> A more correct design, I think, would be having a 'replace' keyword for function calls instead of return that causes it to replace the stack of the caller.
Most modern languages make it simple to determine when a function call is in tail position, and in such cases I feel that a special calling syntax would be an unnecessary distraction. In Scheme, for example, the cases where a tail call is required are obvious from the structure of the code and are, moreover, spelled out in the language standard. However, I will grant that languages like C and C++ which occasionally depend on the compiler adding hidden code at the end of some functions to run destructors or implicitly transform the result type might benefit from such a keyword. It would, at any rate, be an improvement over the current situation where proper tail calls are deemed an optional optimization.