16 ms·

How Tail Call Optimization Works

220 points by g42gregory 6y ago

mmmkkaaayy 6y ago
One sentence summary: "(in the x86 ISA) Tail call optimization happens when the compiler transforms a call immediately followed by a ret into a single jmp"
- teknopaul 6y ago
  makes perfect sense, if you happen to have just read the article :)
- Someone 6y ago
  So, what do we call it when the compiler transforms a call immediately followed by a ret into a fall through into the to-be called function? And which compilers ever do that?
  - tln 6y ago
    Inlining?
  - MayeulC 6y ago
    That's called inlining, unless I misunderstood you :) Most compilers do that, for most compiled languages.
    - astrange 6y ago
      He means that if you have two functions 'a' and 'b' and a tail calls b, the call instruction could be eliminated because it's just going to the next instruction anyway. This is not just inlining, it's a function with multiple entry points, which is not popular.
      - Someone 6y ago
        I would call it two functions with multiple tails. And that was very popular when memory was scarce. The typical BASIC for the 6502 used it. See for example http://hackzapple.org/scripts_php/index.php?menu=14&mod=8517283d55e912b0b5ac842147e28904a4a751d3&page=4 http://hackzapple.org/scripts_php/index.php?menu=14&mod=8517... (search for “The CHARGET Subroutine”). Here, it is used for speed, too (otherwise, at least one of the functions would have to do an indirect load, which is cumbersome and slow on a 6502. The self-modifying code is a lot faster) It also often was used when one had, say, a function to output a character and another function that printed a specific character. Combined with a creative use of the BIT instruction, one could even have functions printing _any_ character, a space, a question mark, or a CR share their tails (https://retrocomputing.stackexchange.com/a/11132 https://retrocomputing.stackexchange.com/a/11132) But yes, nowadays I guess it is rare, although, with an ABI designed for it, it could be used to make a call with a default argument value fall through into the more generic code)
        astrange 6y ago
        One issue I can think of is that compilers/linkers assume they can reorder and delete unused symbols in a C program. You'd turn it off at the object file level if you're writing asm and doing tricks there (x264 asm has some fallthroughs like this), but there isn't a way to say only these two functions need to be in the same order.
        Someone 6y ago
        You wouldn’t have to say it. Linkers could figure it out on their own (but compilers dropping hints would make it easier) Some linkers already can merge functions that happen to compile to the same code, even though that corrupts stack frames (foo calls bar, but the linker makes it call baz instead. https://stackoverflow.com/a/61865960 https://stackoverflow.com/a/61865960) It’s ‘just’ a matter of learning the build system new tricks. I found a short discussion on this at https://gcc.gnu.org/legacy-ml/gcc/2000-02/msg00575.html https://gcc.gnu.org/legacy-ml/gcc/2000-02/msg00575.html that contains https://gcc.gnu.org/legacy-ml/gcc/2000-02/msg00599.html https://gcc.gnu.org/legacy-ml/gcc/2000-02/msg00599.html, which says “The P3 SSE stuff we've done generates multiple entry points, but it does that within the backend prologue expander. There's nothing to generate multiple regular prologues. Though it shouldn't be that hard to do. It's not impossible to believe that the bulk of the compiler would work with them, as long as flow knows how to properly create the CFG. LABEL_ALTERNATE_NAME was invented for this, though it appears that the code to properly deal with it is sitting on a branch waiting for accounting to say it has been paid for.“ That was in February 2000. I wouldn’t know whether that comment was close to the truth or what gcc currently supports. For llvm, the thread at https://lists.llvm.org/pipermail/llvm-dev/2018-October/127154.html https://lists.llvm.org/pipermail/llvm-dev/2018-October/12715... gives some cases where this could be used, but reading it, it doesn’t look it is solved in the way I gave (see for example https://lists.llvm.org/pipermail/llvm-dev/2018-October/127175.html https://lists.llvm.org/pipermail/llvm-dev/2018-October/12717.... https://lists.llvm.org/pipermail/llvm-dev/2018-October/127158.html https://lists.llvm.org/pipermail/llvm-dev/2018-October/12715... calls it “more like separate functions with a common tail.”, so I’m not alone in that. That thread also indicates that DWARF has support for helping debuggers figure out the correct name of such a function.
eyelidlessness 6y ago
This is actually (in the abstract) exactly how I’ve read and understood it in FP, with the necessary added note that when you TCO without recursion you lose history for eg stack traces and debuggers. It’s also astonishing to me that people in a position to explain even moderately complex computing ideas continue to treat recursion as somehow hard to reason about. It’s calling a function. A function that calls itself is still just a function calling another function. Two mutually recursive functions calling each other are just two functions calling two other functions. That’s so much easier to follow than state changing in a single function call.
- kevin_thibedeau 6y ago
  A better mind bender is an async promise calling itself.
  - eyelidlessness 6y ago
    Wait, I’m confused. Like one promise/future/whatever monadish-eventually-fulfilled value referencing its own value? Or a polymorphic promise/etc referencing the same construct that created it to map its resolution into a new value?
- bhawks 6y ago
  I've seen people hung up on the calling yourself while defining yourself concept. Talking through that often highlighted a mental model of functions where they were sort of almost cut'n'pasting the other function into their code. Basically their model was too low level and the understanding of defining and calling functions were unnecessarily conjoined.
  - eyelidlessness 6y ago
    I guess the way I’d try to help those people understand it is with the fiction I tell myself (which I alluded to upthread): I mentally model the “outer” function and the “inner” recursion as referencing different functions that have the same signature and the same body. The definition is concrete and self sufficient, it just dependency-injects a contract in its own image to delegate future work to. It’s even easy to literally implement that way in languages with first class functions, because you can just bind fn a to b and call b within a.
stevebmark 6y ago
Tail call optimization was added to the Javascript language specification in ES6 (ES2015). However most Javascript runtimes don't support it. This is a shame because recursive operations like Haskell's foldl/r would more straightforward to translate to Javascript. Minus the automatic currying and lazy evaluation of course. More info: https://2ality.com/2015/06/tail-call-optimization.html https://2ality.com/2015/06/tail-call-optimization.html Edit: Babel may have tried, but couldn't do it for all cases, so they stopped trying? https://github.com/babel/babel/issues/256 https://github.com/babel/babel/issues/256
- bjoli 6y ago
  It would simplify things a great deal for people compiling to JS. Forcing one looping facility into the behaviour of another can be hard. Implenting just about any looping facility as recursion is a matter of thinking for a while and then sitting down and doing it.
- ganafagol 6y ago
  Hm what does TCO have to do with a language spec? It impacts neither syntax nor semantics of a language, which is what a language spec should be about. It's a detail of the compiler. So I'm curious what this has to do with the languagr spec? Couldn't a smart compiler/interpreter do this before ES6 already?
  - KMag 6y ago
    "Optimization" is a misnomer with TCO. Optimization implies that only execution speed is affected without the optimization. Without TCO, potentially infinite mutually tail-recursive algorithms (or code transformed into continuation-passing style) can't be implemented without emulating tail recursion using a heap-allocated stack/linked list of states or manually transforming the mutually recursive functions into a trampoline variant of continuation passing style. function factorial(n, accumulator=1) { if (n <= 1) { if (n < 0) throw "Arument must not be negative"; return accumulator; } return factorial(n-1, n * accumulator); } TCO doesn't just affect the speed of this factorial implementation, it greatly affects the largest value that can be computed. It's not to tricky to manually convert tail recursion into a loop, but for mutually recursive functions, you'd probably be best off manually transforming your mutually recursive functions into a trampoline variant of continuation passing, where each function returns a tuple of function and arguments to a trampoline loop that just repeatedly invokes the returned function on the returned arguments. function trampoline(f, ... args) { while (true) { f, args = f(*args); if (args == null) { return f; } } } function fatorial_impl(n, accumulator) if (n <= 1) { if (n < 0) throw "Arument must not be negative"; return [accumulator, null]; } return [factorial_impl, [n-1, n * accumulator]]; } function factorial(n) { return trampoline(factorial_impl, n, 1); } It's all very mechanical, and you'd prefer that the compiler does it. The main argument against TCO is that it's easy for an unobservant programmer to accidentally make a change that prevents TCO. Ideally, the language would have a construct allowing a programmer to cause a given return site to be a syntactic error if it's not a TCO-able tail call.
millstone 6y ago
There's a funny interaction between TCO and memory management. If you have scoped destructors (C++, Rust) then you might accidentally defeat TCO by simply declaring a variable. GCs solve this problem by deferring collection to allocation points, but now TCO requires GC. What's the modern view here? I think it's bimodal: either TCO is a defining feature of the language, or a best-effort optimization that nobody should rely on.
- Andys 6y ago
  Yep. Matz disabled TCO in Ruby because it was incompatible with some alternative implementations like JRuby.
  - pmontra 6y ago
    Disabled by default but it can be enabled at runtime https://ruby-doc.org/core-3.0.0/RubyVM/InstructionSequence.html#method-c-compile_option-3D https://ruby-doc.org/core-3.0.0/RubyVM/InstructionSequence.h...
- haberman 6y ago
  > either TCO is a defining feature of the language, or a best-effort optimization that nobody should rely on. I think a third option is that tail calls are only guaranteed if you add a special attribute (eg. [[musttail]]) and that attribute fails to compile if your code is written in such a way that a true tail call cannot be guaranteed. The LLVM backend supports a "musttail" marker on function calls (https://llvm.org/docs/LangRef.html#call-instruction https://llvm.org/docs/LangRef.html#call-instruction), but it specifies a set of constraints that must be met for "musttail" to be valid. I have been experimenting with a Clang change that would plumb a C++ [[musttail]] attribute through the C++ frontend to LLVM, but it requires some care to make sure we satisfy LLVM's constraints.
  - im3w1l 6y ago
    I nominate the syntax goto function(parameter1, parameter2); Also, may I suggest that it runs destructors prior to the jump rather than throwing up it's hands and saying you can't TCO because you have destructors?
2mol 6y ago
For a high-level overview, I found this talk [0] at !!Con 2019 both entertaining and really informative. [0] Tail Call Optimization: The Musical: https://www.youtube.com/watch?v=-PX0BV9hGZY https://www.youtube.com/watch?v=-PX0BV9hGZY
- neillyons 6y ago
  ha, that video is amazing!
- krylon 6y ago
  There really should be more talks in musical form!
waynesonfire 6y ago
Joe Armstrong explaining the concept on the erlang mailing list in 2016, https://erlang.org/pipermail/erlang-questions/2016-October/090663.html https://erlang.org/pipermail/erlang-questions/2016-October/0...
- bmitc 6y ago
  I really like how Joe Armstrong speaks and writes so plainly. He always makes me feel good to learn from and not dumb.
- elexhobby 6y ago
  Wow. I wish everything was explained so clearly. I understood everything in that post except this paragraph. """ Languages like Erlang must implement tail call optimizations, since persisted data is stored as "loop variables" in infinite loops. This happens when we write code like this: loop(Data) -> .... ... loop(newData). When I see code like this I mentally "see" the last call as a "jump" to the start of the code, rather than a recursive call to loop. """ What is the loop(Data), loop(newData) doing? Would be great if someone could elaborate on this point.
moonchild 6y ago
> After executing the nop instruction the PC will be advanced by 1, because that's the size of nop and advancing it by 1 causes it to point to the next instruction Nit: the IP will be advanced by 1 before the nop is executed. IP always points to the instruction following the one which is currently being executed. Which is important for IP-relative addressing and, as mentioned later, calls.
jhanschoo 6y ago
One of the things that proceed naturally from TCO is transforming general recursive functions into mutually recursive functions that call functions only when they return; i.e. transforming them into continuation-passing style (CPS), so that even general recursion does not encounter stack overflow. Some FP compilers such as Guile compile to a CPS intermediate language, and the concept of CPS is known within people writing compilers and the FP community, but quite unheard of in the general programming community it seems.
CalChris 6y ago
I believe the article is describing sibling calls, which is a special case of tail calls. https://llvm.org/docs/CodeGenerator.html#sibling-call-optimization https://llvm.org/docs/CodeGenerator.html#sibling-call-optimi...
hyperman1 6y ago
Can someone clarify something for me in that second assembly dump: It does: xor %eax %eax (2 bytes) mov $0x0,%edi (5 bytes) Why does it decide to use 2 different ways to zero a register, the second one less efficient than the first? Or will the second one be patched while linking, i.e. the 0 is a placeholder for some other address?
- langarto 6y ago
  Exactly, the 0 is a placeholder for the address of the format string (first argument for printf).
- hyperman1 6y ago
  Update: Looking further, there seems to be a lot of space wasted in the disas factorial example: It is 32+1=33 bytes long, or even 48 if the next function will be aligned on a 16 bytes boundary. There are 2 nop's in there, consuming 6 and 4 bytes. So at least 10/33=about 30% of the memory is traded for aligning jumps on 8 (or 16?) byte boundaries. This seems a big waste of L1I cache. Is this a normal ratio? Does -Os much better?
  - saagarjha 6y ago
    Functions are usually longer than what you're seeing there.
    - hyperman1 6y ago
      True, but you would expect it is the ratio branches vs other code which is relevant here.
chalst 6y ago
It is misleading to suggest that an implementation of TCO follows directly from the instruction set architecture: it depends even more on what calling convention is followed [1]. gcc supports several calling conventions for x86 [2]. In the Scheme world, often a hybrid stack-heap calling convention called Cheney on the MTA is used in which all calls are tail calls [3]. [1]: https://en.m.wikipedia.org/wiki/Calling_convention https://en.m.wikipedia.org/wiki/Calling_convention [2]: http://redstack.net/blog/x86-calling-conventions.html http://redstack.net/blog/x86-calling-conventions.html [3]: https://news.ycombinator.com/item?id=12776198 https://news.ycombinator.com/item?id=12776198
- mcguire 6y ago
  Doesn't that part of Scheme implementation interact with continuations?
  - chalst 6y ago
    It is essentially continuation-passing style, which makes implementing first-class continuations very easy.
jabberwcky 6y ago
Perhaps we can soon get a post on how to write a post about tail call optimization? https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=%22tail%20call%22&sort=byPopularity&type=story https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... Not complaining.. but curious that this one feature gets so much visibility. Is it just because it is quite easy to understand?
beagle3 6y ago
TCO is an optimization. When it’s a semantic language feature like in Scheme, it should be called “Tail Call Elimination” because lack of it changes program semantics (thus not merely optimization)
- kazinator 6y ago
  In Scheme jargon, it has come to be that a "tail call" is in fact the name of the goto-like control transfer which replaces the regular subroutine call. Tail calls are not eliminated; rather it is ensured that a function call in tail position is a tail call. This is a useful view/terminology. Without the code transformation that implements tail calls, there is nothing special about a function call in tail position; it proceeds exactly like a call not in a tail position. Therefore, it is not a different kind of call. It becomes one after the code transformation: it becomes a tail call.
  - beagle3 6y ago
    I don’t like that it has no special mention. In a factorial function, fac(n-1) would be a tail call, but 0+fac(n-1) would not. It would be nice if one could annotate (and thus make the compiler verify) tail calls.
    - crististm 6y ago
      Exactly. The tail function in the second case is '+' not 'fac' so you can't replace the recursion with iteration
    - deleted 6y ago
      [deleted]
    - eru 6y ago
      > It would be nice if one could annotate (and thus make the compiler verify) tail calls. This always comes up, but honestly, I've never really run into the problem where I mistook a non-tail call for a tail call. (And I've programmed the majority of my career in languages like Haskell, OCaml and Erlang.) Of course, I'm always in favour of the compiler verifying more stuff. It just doesn't seem very pressing.
wnoise 6y ago
> However, the compiler still generated code for factorial_accumulate in my object file. This is because it is not declared static, and thus is visible outside that translation unit.
kazinator 6y ago
Inspired by my observation that tail calls can be seen as "goto with arguments"[1], in 2013 I wrote a Common Lisp macro called argtags which is like tags/prog, but with labels that have parameters. Giving them arguments causes the corresponding variables to be assigned as the transfer takes place. It compiles to tagbody. Then, I used argtags as the basis for tlet: a macro that looks like it is defining local functions using syntax similar to labels or flet, but actually compiles to argtags, so everything ends up as a tagbody. The calls are always tail calls, whether or not in tail position. You cannot accidentally blow the stack, but you can accidentally expect a call to return, which it won't! This is all found here: http://www.kylheku.com/cgit/lisp-snippets/tree/tail-recursion.lisp http://www.kylheku.com/cgit/lisp-snippets/tree/tail-recursio... There is a complementary cross-module tail calling system in here which provides a defun-like construct deftail for defining tail calling functions. That's based on a trampoline dispatch loop: tail calls unwind up to the loop, passing their arguments to it, along with the next function to be called. [1] Later I found out that Steele also offered the viewpoint back in the 1970's that tail calls can be seen as goto with arguments.
- mkw5053 6y ago
  That’s amazing!
- hrishi 6y ago
  I'd like to thank you for helping me understand what non-techies must feel listening to me talk sometimes, with that penultimate sentence. I understood none of it, but I know it has deep meaning and I respect it.
roperzh 6y ago
I'm doing the CS:APP3e course and out of curiosity searched about this exact same topic yesterday, crazy! I'm learning a great deal from the responses here, thank you. If you are in the same position I was (self-taught dev looking to improve your general understanding) I can't recommend this course/book highly enough: - Book: http://csapp.cs.cmu.edu/3e/home.html http://csapp.cs.cmu.edu/3e/home.html - Lectures: https://scs.hosted.panopto.com/Panopto/Pages/Sessions/List.aspx#folderID=%22b96d90ae-9871-4fae-91e2-b1627b43e25e%22&page=1 https://scs.hosted.panopto.com/Panopto/Pages/Sessions/List.a...
sriku 6y ago
I've seen the term "tail call elimination" applied to this general case and TCO applied to the recursion case. Is that still common? TCE is the more general one obviously .. and is what we almost always want.
teknopaul 6y ago
is gcc clever enough to optimize a() { b(); i++; } or should we code for tco?
ragnese 6y ago
I wish that Rust would follow the lead of some languages in allowing one to explicitly mark a function as recursive. (Not exactly the same as TCO, I understand, but related) I understand the argument against doing TCO in a low level language like Rust (debugging stack traces, etc). But as an opt-in? Yes, please! OCaml, which is like Rust's muse/parent, does it. Kotlin and Clojure do that as well, IIRC.
- eru 6y ago
  From my point of view TCO is exactly most useful when you are dealing with mutually recursive functions. Like eg a state machine where one state = one function. That's also the example in the corresponding Lambda the Ultimate paper. But yes, getting TCO for simple self-recursive function is better than nothing.
  - tomp 6y ago
    TCO is exactly as useful as async/await. Could you write an equivalent state machine manually? Yes. Do you want to? No.
    - eru 6y ago
      What do you mean by 'exactly as useful'? I can see how they are both useful, and there are even some problems were either approach works. But I don't see an exact correspondence?
- say_it_as_it_is 6y ago
  Since you understand the argument against TCO in Rust, would you mind explaining it to those who don't?
  - astrange 6y ago
    The function that performs the tail-call won't show up in stack traces. This is intentional (and needed) when it's done to eliminate an infinite number of recursive calls, but if it's just a utility function then it can be confusing. As an ObjC example, there's an objc_msgSend call between every two methods in a stack trace, but you never see it. In practice this has never been a problem for me.
karmakaze 6y ago
If you ever looked at different call conventions and how call stack frames are used with them, it would be immediately obvious that it's recursion via goto top making a loop using the same stack frame's local variable memory.

220 points by g42gregory 6y ago

One sentence summary: "(in the x86 ISA) Tail call optimization happens when the compiler transforms a call immediately followed by a ret into a single jmp"

teknopaul 6y ago
makes perfect sense, if you happen to have just read the article :)
Someone 6y ago
So, what do we call it when the compiler transforms a call immediately followed by a ret into a fall through into the to-be called function? And which compilers ever do that?
- tln 6y ago
  Inlining?
- MayeulC 6y ago
  That's called inlining, unless I misunderstood you :) Most compilers do that, for most compiled languages.
  - astrange 6y ago
    He means that if you have two functions 'a' and 'b' and a tail calls b, the call instruction could be eliminated because it's just going to the next instruction anyway. This is not just inlining, it's a function with multiple entry points, which is not popular.
    - Someone 6y ago
      I would call it two functions with multiple tails. And that was very popular when memory was scarce. The typical BASIC for the 6502 used it. See for example http://hackzapple.org/scripts_php/index.php?menu=14&mod=8517283d55e912b0b5ac842147e28904a4a751d3&page=4 http://hackzapple.org/scripts_php/index.php?menu=14&mod=8517... (search for “The CHARGET Subroutine”). Here, it is used for speed, too (otherwise, at least one of the functions would have to do an indirect load, which is cumbersome and slow on a 6502. The self-modifying code is a lot faster) It also often was used when one had, say, a function to output a character and another function that printed a specific character. Combined with a creative use of the BIT instruction, one could even have functions printing _any_ character, a space, a question mark, or a CR share their tails (https://retrocomputing.stackexchange.com/a/11132 https://retrocomputing.stackexchange.com/a/11132) But yes, nowadays I guess it is rare, although, with an ABI designed for it, it could be used to make a call with a default argument value fall through into the more generic code)
      - astrange 6y ago
        One issue I can think of is that compilers/linkers assume they can reorder and delete unused symbols in a C program. You'd turn it off at the object file level if you're writing asm and doing tricks there (x264 asm has some fallthroughs like this), but there isn't a way to say only these two functions need to be in the same order.
        Someone 6y ago
        You wouldn’t have to say it. Linkers could figure it out on their own (but compilers dropping hints would make it easier) Some linkers already can merge functions that happen to compile to the same code, even though that corrupts stack frames (foo calls bar, but the linker makes it call baz instead. https://stackoverflow.com/a/61865960 https://stackoverflow.com/a/61865960) It’s ‘just’ a matter of learning the build system new tricks. I found a short discussion on this at https://gcc.gnu.org/legacy-ml/gcc/2000-02/msg00575.html https://gcc.gnu.org/legacy-ml/gcc/2000-02/msg00575.html that contains https://gcc.gnu.org/legacy-ml/gcc/2000-02/msg00599.html https://gcc.gnu.org/legacy-ml/gcc/2000-02/msg00599.html, which says “The P3 SSE stuff we've done generates multiple entry points, but it does that within the backend prologue expander. There's nothing to generate multiple regular prologues. Though it shouldn't be that hard to do. It's not impossible to believe that the bulk of the compiler would work with them, as long as flow knows how to properly create the CFG. LABEL_ALTERNATE_NAME was invented for this, though it appears that the code to properly deal with it is sitting on a branch waiting for accounting to say it has been paid for.“ That was in February 2000. I wouldn’t know whether that comment was close to the truth or what gcc currently supports. For llvm, the thread at https://lists.llvm.org/pipermail/llvm-dev/2018-October/127154.html https://lists.llvm.org/pipermail/llvm-dev/2018-October/12715... gives some cases where this could be used, but reading it, it doesn’t look it is solved in the way I gave (see for example https://lists.llvm.org/pipermail/llvm-dev/2018-October/127175.html https://lists.llvm.org/pipermail/llvm-dev/2018-October/12717.... https://lists.llvm.org/pipermail/llvm-dev/2018-October/127158.html https://lists.llvm.org/pipermail/llvm-dev/2018-October/12715... calls it “more like separate functions with a common tail.”, so I’m not alone in that. That thread also indicates that DWARF has support for helping debuggers figure out the correct name of such a function.

eyelidlessness 6y ago

This is actually (in the abstract) exactly how I’ve read and understood it in FP, with the necessary added note that when you TCO without recursion you lose history for eg stack traces and debuggers. It’s also astonishing to me that people in a position to explain even moderately complex computing ideas continue to treat recursion as somehow hard to reason about. It’s calling a function. A function that calls itself is still just a function calling another function. Two mutually recursive functions calling each other are just two functions calling two other functions. That’s so much easier to follow than state changing in a single function call.

kevin_thibedeau 6y ago
A better mind bender is an async promise calling itself.
- eyelidlessness 6y ago
  Wait, I’m confused. Like one promise/future/whatever monadish-eventually-fulfilled value referencing its own value? Or a polymorphic promise/etc referencing the same construct that created it to map its resolution into a new value?
bhawks 6y ago
I've seen people hung up on the calling yourself while defining yourself concept. Talking through that often highlighted a mental model of functions where they were sort of almost cut'n'pasting the other function into their code. Basically their model was too low level and the understanding of defining and calling functions were unnecessarily conjoined.
- eyelidlessness 6y ago
  I guess the way I’d try to help those people understand it is with the fiction I tell myself (which I alluded to upthread): I mentally model the “outer” function and the “inner” recursion as referencing different functions that have the same signature and the same body. The definition is concrete and self sufficient, it just dependency-injects a contract in its own image to delegate future work to. It’s even easy to literally implement that way in languages with first class functions, because you can just bind fn a to b and call b within a.

stevebmark 6y ago

Tail call optimization was added to the Javascript language specification in ES6 (ES2015). However most Javascript runtimes don't support it. This is a shame because recursive operations like Haskell's foldl/r would more straightforward to translate to Javascript. Minus the automatic currying and lazy evaluation of course. More info: https://2ality.com/2015/06/tail-call-optimization.html https://2ality.com/2015/06/tail-call-optimization.html Edit: Babel may have tried, but couldn't do it for all cases, so they stopped trying? https://github.com/babel/babel/issues/256 https://github.com/babel/babel/issues/256

bjoli 6y ago
It would simplify things a great deal for people compiling to JS. Forcing one looping facility into the behaviour of another can be hard. Implenting just about any looping facility as recursion is a matter of thinking for a while and then sitting down and doing it.
ganafagol 6y ago
Hm what does TCO have to do with a language spec? It impacts neither syntax nor semantics of a language, which is what a language spec should be about. It's a detail of the compiler. So I'm curious what this has to do with the languagr spec? Couldn't a smart compiler/interpreter do this before ES6 already?
- KMag 6y ago
  "Optimization" is a misnomer with TCO. Optimization implies that only execution speed is affected without the optimization. Without TCO, potentially infinite mutually tail-recursive algorithms (or code transformed into continuation-passing style) can't be implemented without emulating tail recursion using a heap-allocated stack/linked list of states or manually transforming the mutually recursive functions into a trampoline variant of continuation passing style. function factorial(n, accumulator=1) { if (n <= 1) { if (n < 0) throw "Arument must not be negative"; return accumulator; } return factorial(n-1, n * accumulator); } TCO doesn't just affect the speed of this factorial implementation, it greatly affects the largest value that can be computed. It's not to tricky to manually convert tail recursion into a loop, but for mutually recursive functions, you'd probably be best off manually transforming your mutually recursive functions into a trampoline variant of continuation passing, where each function returns a tuple of function and arguments to a trampoline loop that just repeatedly invokes the returned function on the returned arguments. function trampoline(f, ... args) { while (true) { f, args = f(*args); if (args == null) { return f; } } } function fatorial_impl(n, accumulator) if (n <= 1) { if (n < 0) throw "Arument must not be negative"; return [accumulator, null]; } return [factorial_impl, [n-1, n * accumulator]]; } function factorial(n) { return trampoline(factorial_impl, n, 1); } It's all very mechanical, and you'd prefer that the compiler does it. The main argument against TCO is that it's easy for an unobservant programmer to accidentally make a change that prevents TCO. Ideally, the language would have a construct allowing a programmer to cause a given return site to be a syntactic error if it's not a TCO-able tail call.

millstone 6y ago

There's a funny interaction between TCO and memory management. If you have scoped destructors (C++, Rust) then you might accidentally defeat TCO by simply declaring a variable. GCs solve this problem by deferring collection to allocation points, but now TCO requires GC. What's the modern view here? I think it's bimodal: either TCO is a defining feature of the language, or a best-effort optimization that nobody should rely on.

Andys 6y ago
Yep. Matz disabled TCO in Ruby because it was incompatible with some alternative implementations like JRuby.
- pmontra 6y ago
  Disabled by default but it can be enabled at runtime https://ruby-doc.org/core-3.0.0/RubyVM/InstructionSequence.html#method-c-compile_option-3D https://ruby-doc.org/core-3.0.0/RubyVM/InstructionSequence.h...
haberman 6y ago
> either TCO is a defining feature of the language, or a best-effort optimization that nobody should rely on. I think a third option is that tail calls are only guaranteed if you add a special attribute (eg. [[musttail]]) and that attribute fails to compile if your code is written in such a way that a true tail call cannot be guaranteed. The LLVM backend supports a "musttail" marker on function calls (https://llvm.org/docs/LangRef.html#call-instruction https://llvm.org/docs/LangRef.html#call-instruction), but it specifies a set of constraints that must be met for "musttail" to be valid. I have been experimenting with a Clang change that would plumb a C++ [[musttail]] attribute through the C++ frontend to LLVM, but it requires some care to make sure we satisfy LLVM's constraints.
- im3w1l 6y ago
  I nominate the syntax goto function(parameter1, parameter2); Also, may I suggest that it runs destructors prior to the jump rather than throwing up it's hands and saying you can't TCO because you have destructors?

2mol 6y ago

For a high-level overview, I found this talk [0] at !!Con 2019 both entertaining and really informative. [0] Tail Call Optimization: The Musical: https://www.youtube.com/watch?v=-PX0BV9hGZY https://www.youtube.com/watch?v=-PX0BV9hGZY

neillyons 6y ago
ha, that video is amazing!
krylon 6y ago
There really should be more talks in musical form!

waynesonfire 6y ago

Joe Armstrong explaining the concept on the erlang mailing list in 2016, https://erlang.org/pipermail/erlang-questions/2016-October/090663.html https://erlang.org/pipermail/erlang-questions/2016-October/0...

bmitc 6y ago
I really like how Joe Armstrong speaks and writes so plainly. He always makes me feel good to learn from and not dumb.
elexhobby 6y ago
Wow. I wish everything was explained so clearly. I understood everything in that post except this paragraph. """ Languages like Erlang must implement tail call optimizations, since persisted data is stored as "loop variables" in infinite loops. This happens when we write code like this: loop(Data) -> .... ... loop(newData). When I see code like this I mentally "see" the last call as a "jump" to the start of the code, rather than a recursive call to loop. """ What is the loop(Data), loop(newData) doing? Would be great if someone could elaborate on this point.

moonchild 6y ago

> After executing the nop instruction the PC will be advanced by 1, because that's the size of nop and advancing it by 1 causes it to point to the next instruction Nit: the IP will be advanced by 1 before the nop is executed. IP always points to the instruction following the one which is currently being executed. Which is important for IP-relative addressing and, as mentioned later, calls.

jhanschoo 6y ago

One of the things that proceed naturally from TCO is transforming general recursive functions into mutually recursive functions that call functions only when they return; i.e. transforming them into continuation-passing style (CPS), so that even general recursion does not encounter stack overflow. Some FP compilers such as Guile compile to a CPS intermediate language, and the concept of CPS is known within people writing compilers and the FP community, but quite unheard of in the general programming community it seems.

CalChris 6y ago

I believe the article is describing sibling calls, which is a special case of tail calls. https://llvm.org/docs/CodeGenerator.html#sibling-call-optimization https://llvm.org/docs/CodeGenerator.html#sibling-call-optimi...

hyperman1 6y ago

Can someone clarify something for me in that second assembly dump: It does: xor %eax %eax (2 bytes) mov $0x0,%edi (5 bytes) Why does it decide to use 2 different ways to zero a register, the second one less efficient than the first? Or will the second one be patched while linking, i.e. the 0 is a placeholder for some other address?

langarto 6y ago
Exactly, the 0 is a placeholder for the address of the format string (first argument for printf).
hyperman1 6y ago
Update: Looking further, there seems to be a lot of space wasted in the disas factorial example: It is 32+1=33 bytes long, or even 48 if the next function will be aligned on a 16 bytes boundary. There are 2 nop's in there, consuming 6 and 4 bytes. So at least 10/33=about 30% of the memory is traded for aligning jumps on 8 (or 16?) byte boundaries. This seems a big waste of L1I cache. Is this a normal ratio? Does -Os much better?
- saagarjha 6y ago
  Functions are usually longer than what you're seeing there.
  - hyperman1 6y ago
    True, but you would expect it is the ratio branches vs other code which is relevant here.

chalst 6y ago

It is misleading to suggest that an implementation of TCO follows directly from the instruction set architecture: it depends even more on what calling convention is followed [1]. gcc supports several calling conventions for x86 [2]. In the Scheme world, often a hybrid stack-heap calling convention called Cheney on the MTA is used in which all calls are tail calls [3]. [1]: https://en.m.wikipedia.org/wiki/Calling_convention https://en.m.wikipedia.org/wiki/Calling_convention [2]: http://redstack.net/blog/x86-calling-conventions.html http://redstack.net/blog/x86-calling-conventions.html [3]: https://news.ycombinator.com/item?id=12776198 https://news.ycombinator.com/item?id=12776198

mcguire 6y ago
Doesn't that part of Scheme implementation interact with continuations?
- chalst 6y ago
  It is essentially continuation-passing style, which makes implementing first-class continuations very easy.

jabberwcky 6y ago

Perhaps we can soon get a post on how to write a post about tail call optimization? https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=%22tail%20call%22&sort=byPopularity&type=story https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... Not complaining.. but curious that this one feature gets so much visibility. Is it just because it is quite easy to understand?

beagle3 6y ago

TCO is an optimization. When it’s a semantic language feature like in Scheme, it should be called “Tail Call Elimination” because lack of it changes program semantics (thus not merely optimization)

kazinator 6y ago
In Scheme jargon, it has come to be that a "tail call" is in fact the name of the goto-like control transfer which replaces the regular subroutine call. Tail calls are not eliminated; rather it is ensured that a function call in tail position is a tail call. This is a useful view/terminology. Without the code transformation that implements tail calls, there is nothing special about a function call in tail position; it proceeds exactly like a call not in a tail position. Therefore, it is not a different kind of call. It becomes one after the code transformation: it becomes a tail call.
- beagle3 6y ago
  I don’t like that it has no special mention. In a factorial function, fac(n-1) would be a tail call, but 0+fac(n-1) would not. It would be nice if one could annotate (and thus make the compiler verify) tail calls.
  - crististm 6y ago
    Exactly. The tail function in the second case is '+' not 'fac' so you can't replace the recursion with iteration
  - deleted 6y ago
    [deleted]
  - eru 6y ago
    > It would be nice if one could annotate (and thus make the compiler verify) tail calls. This always comes up, but honestly, I've never really run into the problem where I mistook a non-tail call for a tail call. (And I've programmed the majority of my career in languages like Haskell, OCaml and Erlang.) Of course, I'm always in favour of the compiler verifying more stuff. It just doesn't seem very pressing.

wnoise 6y ago

> However, the compiler still generated code for factorial_accumulate in my object file. This is because it is not declared static, and thus is visible outside that translation unit.

kazinator 6y ago

Inspired by my observation that tail calls can be seen as "goto with arguments"[1], in 2013 I wrote a Common Lisp macro called argtags which is like tags/prog, but with labels that have parameters. Giving them arguments causes the corresponding variables to be assigned as the transfer takes place. It compiles to tagbody. Then, I used argtags as the basis for tlet: a macro that looks like it is defining local functions using syntax similar to labels or flet, but actually compiles to argtags, so everything ends up as a tagbody. The calls are always tail calls, whether or not in tail position. You cannot accidentally blow the stack, but you can accidentally expect a call to return, which it won't! This is all found here: http://www.kylheku.com/cgit/lisp-snippets/tree/tail-recursion.lisp http://www.kylheku.com/cgit/lisp-snippets/tree/tail-recursio... There is a complementary cross-module tail calling system in here which provides a defun-like construct deftail for defining tail calling functions. That's based on a trampoline dispatch loop: tail calls unwind up to the loop, passing their arguments to it, along with the next function to be called. [1] Later I found out that Steele also offered the viewpoint back in the 1970's that tail calls can be seen as goto with arguments.

mkw5053 6y ago
That’s amazing!
hrishi 6y ago
I'd like to thank you for helping me understand what non-techies must feel listening to me talk sometimes, with that penultimate sentence. I understood none of it, but I know it has deep meaning and I respect it.

roperzh 6y ago

I'm doing the CS:APP3e course and out of curiosity searched about this exact same topic yesterday, crazy! I'm learning a great deal from the responses here, thank you. If you are in the same position I was (self-taught dev looking to improve your general understanding) I can't recommend this course/book highly enough: - Book: http://csapp.cs.cmu.edu/3e/home.html http://csapp.cs.cmu.edu/3e/home.html - Lectures: https://scs.hosted.panopto.com/Panopto/Pages/Sessions/List.aspx#folderID=%22b96d90ae-9871-4fae-91e2-b1627b43e25e%22&page=1 https://scs.hosted.panopto.com/Panopto/Pages/Sessions/List.a...

sriku 6y ago

I've seen the term "tail call elimination" applied to this general case and TCO applied to the recursion case. Is that still common? TCE is the more general one obviously .. and is what we almost always want.

teknopaul 6y ago

is gcc clever enough to optimize a() { b(); i++; } or should we code for tco?

ragnese 6y ago

I wish that Rust would follow the lead of some languages in allowing one to explicitly mark a function as recursive. (Not exactly the same as TCO, I understand, but related) I understand the argument against doing TCO in a low level language like Rust (debugging stack traces, etc). But as an opt-in? Yes, please! OCaml, which is like Rust's muse/parent, does it. Kotlin and Clojure do that as well, IIRC.

eru 6y ago
From my point of view TCO is exactly most useful when you are dealing with mutually recursive functions. Like eg a state machine where one state = one function. That's also the example in the corresponding Lambda the Ultimate paper. But yes, getting TCO for simple self-recursive function is better than nothing.
- tomp 6y ago
  TCO is exactly as useful as async/await. Could you write an equivalent state machine manually? Yes. Do you want to? No.
  - eru 6y ago
    What do you mean by 'exactly as useful'? I can see how they are both useful, and there are even some problems were either approach works. But I don't see an exact correspondence?
say_it_as_it_is 6y ago
Since you understand the argument against TCO in Rust, would you mind explaining it to those who don't?
- astrange 6y ago
  The function that performs the tail-call won't show up in stack traces. This is intentional (and needed) when it's done to eliminate an infinite number of recursive calls, but if it's just a utility function then it can be confusing. As an ObjC example, there's an objc_msgSend call between every two methods in a stack trace, but you never see it. In practice this has never been a problem for me.

karmakaze 6y ago

If you ever looked at different call conventions and how call stack frames are used with them, it would be immediately obvious that it's recursion via goto top making a loop using the same stack frame's local variable memory.