4 ms·

> In a language with loops, however, TCO is not essential since you can always just use a loop. That's not correct. Loops are just one kind (the simplest) of i

by pflanze 11y ago

> In a language with loops, however, TCO is not essential since you can always just use a loop. That's not correct. Loops are just one kind (the simplest) of iteration. In a language with TCO, you can also implement state machines with function calls, or do continuation passing style (pass one or multiple functions to a function to be called with a result when done). There's a reason Guy Steele called the function the ultimate goto (assuming TCO): you can then build all control structures with them. Missing TCO, you need to fall back on handling state yourself (like you can still implement recursive algorithms in a language that doesn't offer recursion, like old Basics or whatever, you just need to build your own stack).

StefanKarpinski 11y ago
Right, that's a fair point. If you have goto, however, you don't need TCO, but then you're programming with gotos. This is not the argument most people make when arguing for TCO – they often talk about recursive algorithms for walking data structures – which usually are not actually eligible for TCO at all.
- pflanze 11y ago
  Hm, the question now becomes what kind of `goto` you're talking about. C's goto is definitively not enough either, since you can't use labels in other functions as target (and have other restrictions). Perl's goto qualifies, because it can jump to functions; also, Perl allows to set the @_ array variable which is used to pass arguments to functions; also, Perl has closures, which is also necessary in this case, to maintain the context. You can now simply argue that this is Perl's way to manually declare a subroutine call as tail optimized (i.e. Perl has manual TCO). Java has goto in the JVM, but AFAIK it does not qualify. Assembly language has various kinds of jump instructions, these do qualify, assuming that the rest of your code is able to deal with the jumps (i.e. you're also implementing closures manually). I'm pretty sure Guy Steele's paper title was tonge-in-cheek, as around a decade before the well-known letter "Go To Statement Considered Harmful" by Edsger Dijkstra was published. How would one want to propagate something as awful as goto? Well, the new goto allowed to pass arguments with it, and would reinstate the context. This would make it safe from a memory corruption stand point, and also be cleaner for it's now all calling of mathematical functions. So you could do all that goto could, but in a clean way. I don't know if Steele hat C in mind (which appeared just 5 years before the paper) or which other language(s). Also, perhaps "the ultimate goto" was a play on that it's even actually more powerful than goto in most languages? (I think I still haven't finished reading it, actually, and should, perhaps the answer is in the paper.) If you want to use goto in C to have the full power of TCO, then you need to write your C program as a single C function, with all actual "functions" of your program represented by labels, and allocate a stack and pass arguments on that stack or in globals yourself. And can forget about any type checking and programmer sanity. (A saner way to archieve TCO in C will be to use trampolines. Or use a code generator instead of writing goto'ified C manually; the Gambit-C system uses this approach to compile Scheme to C.)

by pflanze 11y ago

StefanKarpinski 11y ago

Right, that's a fair point. If you have goto, however, you don't need TCO, but then you're programming with gotos. This is not the argument most people make when arguing for TCO – they often talk about recursive algorithms for walking data structures – which usually are not actually eligible for TCO at all.

pflanze 11y ago
Hm, the question now becomes what kind of `goto` you're talking about. C's goto is definitively not enough either, since you can't use labels in other functions as target (and have other restrictions). Perl's goto qualifies, because it can jump to functions; also, Perl allows to set the @_ array variable which is used to pass arguments to functions; also, Perl has closures, which is also necessary in this case, to maintain the context. You can now simply argue that this is Perl's way to manually declare a subroutine call as tail optimized (i.e. Perl has manual TCO). Java has goto in the JVM, but AFAIK it does not qualify. Assembly language has various kinds of jump instructions, these do qualify, assuming that the rest of your code is able to deal with the jumps (i.e. you're also implementing closures manually). I'm pretty sure Guy Steele's paper title was tonge-in-cheek, as around a decade before the well-known letter "Go To Statement Considered Harmful" by Edsger Dijkstra was published. How would one want to propagate something as awful as goto? Well, the new goto allowed to pass arguments with it, and would reinstate the context. This would make it safe from a memory corruption stand point, and also be cleaner for it's now all calling of mathematical functions. So you could do all that goto could, but in a clean way. I don't know if Steele hat C in mind (which appeared just 5 years before the paper) or which other language(s). Also, perhaps "the ultimate goto" was a play on that it's even actually more powerful than goto in most languages? (I think I still haven't finished reading it, actually, and should, perhaps the answer is in the paper.) If you want to use goto in C to have the full power of TCO, then you need to write your C program as a single C function, with all actual "functions" of your program represented by labels, and allocate a stack and pass arguments on that stack or in globals yourself. And can forget about any type checking and programmer sanity. (A saner way to archieve TCO in C will be to use trampolines. Or use a code generator instead of writing goto'ified C manually; the Gambit-C system uses this approach to compile Scheme to C.)