4 ms·

See Steele's comments.

• jf 17y ago
  The article is worth reading for Guy's comments alone.
  • blasdel 17y ago
    It's not like Tim Bray had anything to add beyond "I don't get it" -- He's still stuck thinking this is all about fetishizing recursion. If only it was popularly called "Stack Frame Elimination", maybe people would get it. Guido's post calling it "Tail-Recursion Elimination" was particularly regressive -- the transformation doesn't make your code any less recursive! All it does is jump to the beginning of an existing stack frame, instead of setting up a new one, copying your state into it, and jumping to that.
    • JulianMorrison 17y ago
      When is eliminating a stack frame a sensible optimization? Only when you intend to go hundreds of calls deep. And there are only two types of code that do that: heavily factored "threaded" code in the Forth style, and recursion.
      • blasdel 17y ago
        As I commented on Bray's post, Enterprisey Java, loaded up with as many spaghetti abstractions as can be interposed, has lots of stack frames to spare. Aren't each of the extra dispatches and dependency interjections going to have tail calls to the next such abstraction?
        • JulianMorrison 17y ago
          ...so don't do that, said the doctor.
      • dkersten 17y ago
        When is eliminating a stack frame a sensible optimization? Off topic, since this isn't what you meant, but in the July issue of SIGPLAN notices, there was a paper entitled "Eliminating the call stack to save RAM" or something like that. It was an interesting little trick that exchanges code size for RAM usage.
      • eru 17y ago
        That's a sensible question to ask. (Though hundreds of calls deep could be done on the stack. Think more like thousands or millions or more.) Have you ever heard of parsing with combinators? This may be an example where you can see that tail call optimization really improves things.
      • gvb 17y ago
        Eliminating the stack frame is a pretty effective speed optimization for "traditional" languages. It costs a non-trivial amount of instructions (execution time) and cache space (potentially casting out more useful data - data fetch time) to build an unneeded stack frame, and then a couple more instructions to throw the frame away. Even for processors that have a "build a stack frame" instruction like the x86, the instruction is a pretty expensive one in terms of clocks required to execute. With a "traditional" language, stack frames can be eliminated in the leaf nodes of the calling trees. These routines tend to be the very small utility routines so building an unneeded stack frame to execute a three line (often only a handful of assy instructions) routine is measurably wasteful. Thus, I would add a third type of code that benefits from stack frame optimization: small leaf node functions, i.e. functions don't call anything other function.
      • mbrubeck 17y ago
        Think of it as a type of garbage collection. That stack frame is an unreachable resource. TCO guarantees that the language implementation will free the resource automatically. Without TCO, the programmer has to explicitly prevent unused resources from accumulating by trampolining, looping, etc.
    • asciilifeform 17y ago
      > "Stack Frame Elimination" We can do even better than that: http://www.loper-os.org/?p=46 http://www.loper-os.org/?p=46