4 ms·

Continuations I can live without, but is Scheme at all usable without tail calls?

neilv 4y ago
Not normal idiomatic Scheme, but I suppose some programs might have in-practice stack usage bounded not too high. A Wasm target of the Chez/Racket compiler might be an easier way to get fast and proper evaluation in Web browsers.
noduerme 4y ago
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
It is one of the few languages where tail calls are part of the language specification, so not really.
cultofmetatron 4y ago
its the only way to do loops without blowing your call stack in scheme. technically yes as long as you're not doing anything interesting
- vishesh 4y ago
  Currently, the compiler does a dumb conversion to JS for loop of self tail calls. So if you call `map` on list of 1000000 items, your stack wont blow up. But I understand it is not enough for many non-trivial codebases. We were interested in doing more general TCO, and had some ideas around using trampolines (or iirc detecting mutually recursions and then trying to generate potentially a bit faster code). Had limited time, and was maybe too hopeful that eventually TCO will actually be supported by browsers (as it is part of standard).

Not normal idiomatic Scheme, but I suppose some programs might have in-practice stack usage bounded not too high. A Wasm target of the Chez/Racket compiler might be an easier way to get fast and proper evaluation in Web browsers.

noduerme 4y ago

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

It is one of the few languages where tail calls are part of the language specification, so not really.

cultofmetatron 4y ago

its the only way to do loops without blowing your call stack in scheme. technically yes as long as you're not doing anything interesting

vishesh 4y ago
Currently, the compiler does a dumb conversion to JS for loop of self tail calls. So if you call `map` on list of 1000000 items, your stack wont blow up. But I understand it is not enough for many non-trivial codebases. We were interested in doing more general TCO, and had some ideas around using trampolines (or iirc detecting mutually recursions and then trying to generate potentially a bit faster code). Had limited time, and was maybe too hopeful that eventually TCO will actually be supported by browsers (as it is part of standard).