4 ms·

Yes, I agree, that is a caricature. More seriously, I think leaning on this language-specific feature in a book that's supposedly teaching "general programming

Yes, I agree, that is a caricature. More seriously, I think leaning on this language-specific feature in a book that's supposedly teaching "general programming 101," or whatever, is in bad taste. As it says: > One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose ``looping constructs'' such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar. This is an example of a point where an algorithms book is helpful + clarifying and SICP is really not. (fake quote: "Be conceptually sloppy and let Scheme take care of it, kid.") It has a few pages on orders of growth, but the coverage is not amazing.

chongli 6y ago
I wouldn’t really call tail-call elimination a feature, language-specific or otherwise. Instead, I would describe the lack of it as a bug. If you examine what’s actually going on in compilers that lack tail call elimination, what you witness is the saving of registers to the stack whose values are provably never going to be used.
- spekcular 6y ago
  You contend that all C compilers prior to their introduction of TCE were bugged?
ckcheng 6y ago
Tail-call elimination / optimization is not a Scheme language-specific feature though. Other popular languages have TCO to varying degrees, like C and C++ when using fairly standard compilers like MSVC, GCC, Clang, or ICC [1]. Destructors do get in the way though sometimes. Java/JVM doesn't support TCO, but Kotlin and Clojure make do with special syntax to support tail-recursion (i.e. tailrec, recur). Apparently JavaScriptCore supports TCO for JavaScript [2]. The book makes it sound like TCE is language-specific, but since that book was published, it's spread to many other mainstream languages too. [1]: https://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization/34129#34129 https://stackoverflow.com/questions/34125/which-if-any-c-com... [2]: https://dev.to/rohit/demystifying-tail-call-optimization-5bf3 https://dev.to/rohit/demystifying-tail-call-optimization-5bf...
afiori 6y ago
SICP point is that you can implement a for loop with tail recursion easily but not viceversa.
- Jtsummers 6y ago
  I don't think that's the point, as conversion in both directions is near trivial. It is a straightforward mechanical process, it may not always be easy or simple but it's more likely tedious than hard or complex. More importantly, in the listed languages (excepting a handful of compiler optimization options) the semantics of procedure calls are different than Scheme's semantics for procedure calls. So if you, in C, convert a for loop into a tail recursive procedure you have changed the behavior of the program, not just its appearance (and same in reverse). In Scheme or another language with tail call elimination, then this conversion ought not actually change the behavior of your program (done in either direction). This also has the effect of removing the loop constructs as a necessity of the language. You can describe an efficient iterative process in Scheme with tail recursion, but you cannot describe it (in a general sense, same caveat for some optimization options) with tail recursion in the listed procedural languages and must use a special syntax element (their loop constructs) to achieve the same program semantics.
  - afiori 6y ago
    Transforming a program with tail calls to one without require to move all mutually recursive tail function to a common trampoline or something similar. Rewriting a single or a few tail functions into a loop/switch is easy, but it "impossible" to do for library API without global transformations. (I could be wrong, I am not an expert in this, my basis are that an open set of function with a call in tail position can be used to describe arbitrary state machines (with the state being the arguments of the tail call and the rules the code of each function) that is open to new functions being added from anywhere. If you want to transform this in an iterative state machine all your functions need to be "registered" and "called" by the state machine.)

chongli 6y ago

I wouldn’t really call tail-call elimination a feature, language-specific or otherwise. Instead, I would describe the lack of it as a bug. If you examine what’s actually going on in compilers that lack tail call elimination, what you witness is the saving of registers to the stack whose values are provably never going to be used.

spekcular 6y ago
You contend that all C compilers prior to their introduction of TCE were bugged?

ckcheng 6y ago

Tail-call elimination / optimization is not a Scheme language-specific feature though. Other popular languages have TCO to varying degrees, like C and C++ when using fairly standard compilers like MSVC, GCC, Clang, or ICC [1]. Destructors do get in the way though sometimes. Java/JVM doesn't support TCO, but Kotlin and Clojure make do with special syntax to support tail-recursion (i.e. tailrec, recur). Apparently JavaScriptCore supports TCO for JavaScript [2]. The book makes it sound like TCE is language-specific, but since that book was published, it's spread to many other mainstream languages too. [1]: https://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization/34129#34129 https://stackoverflow.com/questions/34125/which-if-any-c-com... [2]: https://dev.to/rohit/demystifying-tail-call-optimization-5bf3 https://dev.to/rohit/demystifying-tail-call-optimization-5bf...

afiori 6y ago

SICP point is that you can implement a for loop with tail recursion easily but not viceversa.

Jtsummers 6y ago
I don't think that's the point, as conversion in both directions is near trivial. It is a straightforward mechanical process, it may not always be easy or simple but it's more likely tedious than hard or complex. More importantly, in the listed languages (excepting a handful of compiler optimization options) the semantics of procedure calls are different than Scheme's semantics for procedure calls. So if you, in C, convert a for loop into a tail recursive procedure you have changed the behavior of the program, not just its appearance (and same in reverse). In Scheme or another language with tail call elimination, then this conversion ought not actually change the behavior of your program (done in either direction). This also has the effect of removing the loop constructs as a necessity of the language. You can describe an efficient iterative process in Scheme with tail recursion, but you cannot describe it (in a general sense, same caveat for some optimization options) with tail recursion in the listed procedural languages and must use a special syntax element (their loop constructs) to achieve the same program semantics.
- afiori 6y ago
  Transforming a program with tail calls to one without require to move all mutually recursive tail function to a common trampoline or something similar. Rewriting a single or a few tail functions into a loop/switch is easy, but it "impossible" to do for library API without global transformations. (I could be wrong, I am not an expert in this, my basis are that an open set of function with a call in tail position can be used to describe arbitrary state machines (with the state being the arguments of the tail call and the rules the code of each function) that is open to new functions being added from anywhere. If you want to transform this in an iterative state machine all your functions need to be "registered" and "called" by the state machine.)