4 ms·

Here's a related Zig proposal: https://github.com/ziglang/zig/issues/8220 https://github.com/ziglang/zig/issues/8220 Relevant section pasted here: > Other Pos

Here's a related Zig proposal: https://github.com/ziglang/zig/issues/8220 https://github.com/ziglang/zig/issues/8220 Relevant section pasted here: > Other Possible Solution: Tail Calls > Tail calls solve this problem. Each switch prong would return foo() (tail call) and foo() at the end of its business would inline call a function which would do the switch and then tail call the next prong. > This is reasonable in the sense that it is doable right now; however there are some problems: * As far as I understand, tail calls don't work on some architectures. * (what are these? does anybody know?) * I'm also concerned about trying to debug when doing dispatch with tail calls. * It forces you to organize your logic into functions. That's another jump that maybe you did not want in your hot path. See also https://dino-lang.github.io/learn/dino.pdf https://dino-lang.github.io/learn/dino.pdf, section 3.1 "Byte Code Dispatch".

haberman 6y ago
It sounds like the main question in the proposal is: how can we reliably get the compiler to generate threaded/replicated dispatch? While that is important, it is only one small part of what we were trying to achieve with tail calls. Ultimately we found that our tail call design significantly improved the register allocation and overall code generation compared with computed goto, see: https://gcc.gnu.org/pipermail/gcc/2021-April/235891.html https://gcc.gnu.org/pipermail/gcc/2021-April/235891.html
- seg_lol 6y ago
  I really want a timeline where we have tail calls everywhere and this drama can go away. The non-tail call folks feel like folks arguing for not using spaces in text. https://en.wikipedia.org/wiki/Scriptio_continua https://en.wikipedia.org/wiki/Scriptio_continua
  - haberman 6y ago
    I have to admit I had little interest in tail calls myself until I saw what they could achieve performance-wise. Now that I have seen that, I am sold. :)
    - seg_lol 6y ago
      Performance is only one small aspect, the things you can express in tail recursive functions are beautiful and compact. If feels like being in an inductive proof playground.
  - slaymaker1907 6y ago
    I do think tail call optimization can make debugging/stack traces confusing if you do general TCO. In the plain single function case, TCO probably makes it easier to debug, but it can get confusing if function A calls B and then B calls C in tail position so the stack trace is just C|A. It's probably not too bad if it is just one function getting elided, but this get very difficult if multiple important calls are being removed from the stack. This could also be a case of insufficient tooling for languages with TCO. Better support for reverse debugging would make detailed stacks less necessary. Most of the stack trace isn't that useful anyway when printing out exceptions compared to good application logging.
    - spockz 6y ago
      Don’t we have debug symbols or something like it to be able to translate the optimised version into the thing you saw in code? If you need to dive into the assembly you are in for a hell of a ride anyway due to all kinds of optimisations happening.
      - seg_lol 6y ago
        And tail recursive functions encode their state in the args and the body. There isn't any information in the stack anyway, by definition. If one does need to debug mutually tail recursive functions, step through them, this isn't a problem. The point is that they don't consume stack space. If you do want a stack of invocations, then don't write tail recursive code? This style of argumentation that the GP showed should have a name. BTW my original comment is at -1, hate but only in the tail position.
        KMag 6y ago
        > There isn't any information in the stack anyway, by definition. This is untrue. There are 3 possibilities: 1. Constant stack space (perhaps zero) across calls with caller-cleanup 2. Callee-cleanup 3. Caller-cleanup where an argument indicates how much stack space to clean/where to set the stack pointer

haberman 6y ago

It sounds like the main question in the proposal is: how can we reliably get the compiler to generate threaded/replicated dispatch? While that is important, it is only one small part of what we were trying to achieve with tail calls. Ultimately we found that our tail call design significantly improved the register allocation and overall code generation compared with computed goto, see: https://gcc.gnu.org/pipermail/gcc/2021-April/235891.html https://gcc.gnu.org/pipermail/gcc/2021-April/235891.html

seg_lol 6y ago
I really want a timeline where we have tail calls everywhere and this drama can go away. The non-tail call folks feel like folks arguing for not using spaces in text. https://en.wikipedia.org/wiki/Scriptio_continua https://en.wikipedia.org/wiki/Scriptio_continua
- haberman 6y ago
  I have to admit I had little interest in tail calls myself until I saw what they could achieve performance-wise. Now that I have seen that, I am sold. :)
  - seg_lol 6y ago
    Performance is only one small aspect, the things you can express in tail recursive functions are beautiful and compact. If feels like being in an inductive proof playground.
- slaymaker1907 6y ago
  I do think tail call optimization can make debugging/stack traces confusing if you do general TCO. In the plain single function case, TCO probably makes it easier to debug, but it can get confusing if function A calls B and then B calls C in tail position so the stack trace is just C|A. It's probably not too bad if it is just one function getting elided, but this get very difficult if multiple important calls are being removed from the stack. This could also be a case of insufficient tooling for languages with TCO. Better support for reverse debugging would make detailed stacks less necessary. Most of the stack trace isn't that useful anyway when printing out exceptions compared to good application logging.
  - spockz 6y ago
    Don’t we have debug symbols or something like it to be able to translate the optimised version into the thing you saw in code? If you need to dive into the assembly you are in for a hell of a ride anyway due to all kinds of optimisations happening.
    - seg_lol 6y ago
      And tail recursive functions encode their state in the args and the body. There isn't any information in the stack anyway, by definition. If one does need to debug mutually tail recursive functions, step through them, this isn't a problem. The point is that they don't consume stack space. If you do want a stack of invocations, then don't write tail recursive code? This style of argumentation that the GP showed should have a name. BTW my original comment is at -1, hate but only in the tail position.
      - KMag 6y ago
        > There isn't any information in the stack anyway, by definition. This is untrue. There are 3 possibilities: 1. Constant stack space (perhaps zero) across calls with caller-cleanup 2. Callee-cleanup 3. Caller-cleanup where an argument indicates how much stack space to clean/where to set the stack pointer