3 ms·

tail calls are a foreign concept to me, and I assume that's because I'm coming from JIT scripts where that's not a common way to think of optimization. Just rea

tail calls are a foreign concept to me, and I assume that's because I'm coming from JIT scripts where that's not a common way to think of optimization. Just reading a bit of what they are, it sounds like you're branching within a function to others that return something of the same type - common enough - but get a huge memory/ processing bonus when you branch as long as the sending function doesn't continue? Is that sort of it? I'm really intrigued as to how and where this plays a big role in day to day coding or whether it's just an optimization once you refactor everything at the end.

pjmlp 4y ago
Basically it is just another way of doing gotos, while keeeping the abstraction of function calls, without the space required for recursion stack data structures. Having this as guarantee allows all the control flow concepts to be reduced to recursion and function calls. A kind of purity when we reduce a programing language to the basic set of primitives that provide the building blocks to create any kind of programming paradigm, this is in a way the beauty of Scheme, moreso than Lisp.
- eru 4y ago
  Specifically, loops are a special case (with special syntax) of tail calls for language that don't support tail calls properly. However as great as tail calls are they can't practically implement all control flow concepts. Eg they aren't really all that great for modelling exceptions, I think.
  - pjmlp 4y ago
    Fair point, however exceptions have their roots on continuations.
  - throwaway17_17 4y ago
    I would agree with sibling, and expand his comment a bit. Tail calls are just the specialization of continuation passing (or of having reified continuations programmer accessible. Actually, all control flow is the application of a continuation. So while I agree that tail calls are not used as the basis for exceptions, the parent concept of continuation passing does.
ughitsaaron 4y ago
TCO is a runtime feature that enables code authors to write functions that call out to other functions in such a way that the stack size is not increased. If you’ve ever crossed the `RangeError: Maximum Call Stack Size Exceeded` error, it’s possible that the executed code could’ve benefitted from TCO. TCO is especially invaluable for writing recursive functions (without it, recursion is almost always a bad idea, IMHO). TCO is technically in the ECMAScript specification (since 2015) but hasn’t been implemented across browsers or runtimes (with a few exceptions). Dr. Axel has written a good explainer of TCO in the context of Javascript here https://2ality.com/2015/06/tail-call-optimization.html https://2ality.com/2015/06/tail-call-optimization.html
- zeckalpha 4y ago
  This can be worked around using trampolines.
  - ughitsaaron 4y ago
    This is the first time I've heard of "trampolines". How interesting. Do you use this strategy for implementing recursion? Are there consequences or trade offs? For others who are curious, see 1) https://stackoverflow.com/questions/25228871/how-to-understand-trampoline-in-javascript https://stackoverflow.com/questions/25228871/how-to-understa..., and 2) https://raganwald.com/2013/03/28/trampolines-in-javascript.html https://raganwald.com/2013/03/28/trampolines-in-javascript.h...
    - zeckalpha 4y ago
      You would do this inside a transpiler, rather than manually.
    - soegaard 4y ago
      Check "Using ParentheC to Transform Scheme Programs to C or How to Write Interesting Recursive Programs in a Spartan Host (Program Counter)" for more about trampolines. It's not the only strategy though. https://stackoverflow.com/q/6003037/23567 https://stackoverflow.com/q/6003037/23567

pjmlp 4y ago

Basically it is just another way of doing gotos, while keeeping the abstraction of function calls, without the space required for recursion stack data structures. Having this as guarantee allows all the control flow concepts to be reduced to recursion and function calls. A kind of purity when we reduce a programing language to the basic set of primitives that provide the building blocks to create any kind of programming paradigm, this is in a way the beauty of Scheme, moreso than Lisp.

eru 4y ago
Specifically, loops are a special case (with special syntax) of tail calls for language that don't support tail calls properly. However as great as tail calls are they can't practically implement all control flow concepts. Eg they aren't really all that great for modelling exceptions, I think.
- pjmlp 4y ago
  Fair point, however exceptions have their roots on continuations.
- throwaway17_17 4y ago
  I would agree with sibling, and expand his comment a bit. Tail calls are just the specialization of continuation passing (or of having reified continuations programmer accessible. Actually, all control flow is the application of a continuation. So while I agree that tail calls are not used as the basis for exceptions, the parent concept of continuation passing does.

ughitsaaron 4y ago

TCO is a runtime feature that enables code authors to write functions that call out to other functions in such a way that the stack size is not increased. If you’ve ever crossed the `RangeError: Maximum Call Stack Size Exceeded` error, it’s possible that the executed code could’ve benefitted from TCO. TCO is especially invaluable for writing recursive functions (without it, recursion is almost always a bad idea, IMHO). TCO is technically in the ECMAScript specification (since 2015) but hasn’t been implemented across browsers or runtimes (with a few exceptions). Dr. Axel has written a good explainer of TCO in the context of Javascript here https://2ality.com/2015/06/tail-call-optimization.html https://2ality.com/2015/06/tail-call-optimization.html

zeckalpha 4y ago
This can be worked around using trampolines.
- ughitsaaron 4y ago
  This is the first time I've heard of "trampolines". How interesting. Do you use this strategy for implementing recursion? Are there consequences or trade offs? For others who are curious, see 1) https://stackoverflow.com/questions/25228871/how-to-understand-trampoline-in-javascript https://stackoverflow.com/questions/25228871/how-to-understa..., and 2) https://raganwald.com/2013/03/28/trampolines-in-javascript.html https://raganwald.com/2013/03/28/trampolines-in-javascript.h...
  - zeckalpha 4y ago
    You would do this inside a transpiler, rather than manually.
  - soegaard 4y ago
    Check "Using ParentheC to Transform Scheme Programs to C or How to Write Interesting Recursive Programs in a Spartan Host (Program Counter)" for more about trampolines. It's not the only strategy though. https://stackoverflow.com/q/6003037/23567 https://stackoverflow.com/q/6003037/23567