5 ms·

In general, tail recursion destroys stacktrace information, e.g. if f calls g which tail calls h, and h crashes, you won't see g in the stacktrace, and this is

In general, tail recursion destroys stacktrace information, e.g. if f calls g which tail calls h, and h crashes, you won't see g in the stacktrace, and this is bad for debuggability. In lower level languages there are also a bunch of other issues: - RAII can easily make functions that appear in a tail position not actually tail calls, due to destructors implicitly running after the call; - there can be issues when reusing the stack frame of the caller, especially with caller-cleanup calling conventions; - the compiler needs to prove that no pointers to the stack frame of the function being optimized have escaped, otherwise it would be reusing the memory of live variables which is illegal.

hyperbrainer 2y ago
AFAIK Zig is the only somewhat-big and known low-level language with TCO. Obviously, Haskell/Ocaml and the like support and it are decently fast too, but system programming languages they are not.
- vlovich123 2y ago
  For guarantee: https://crates.io/crates/tiny_tco https://crates.io/crates/tiny_tco https://crates.io/crates/tco https://crates.io/crates/tco As an optimization my understanding is that GCC and LLVM implement it so Rust, C, and C++ also have it implicitly as optimizations that may or may not apply to your code. But yes, zig does have a formal language syntax for guaranteeing tail calls to happen at the language level (which I agree with as the right way to expose this optimization).
- SkiFire13 2y ago
  Zig's tco support is not much different than Clang's `[[clang::musttail]]` in C++. Both have the big restriction that the two functions involved are required to have the same signature.
  - hyperbrainer 2y ago
    > Both have the big restriction that the two functions involved are required to have the same signature. I did not know that! But I am a bit confused, since I don't really program in either language. Where exactly in the documentation could I read more about this? Or see more examples? The language reference for @call[0] was quite unhelpful for my untrained eye. [0] https://ziglang.org/documentation/master/#call https://ziglang.org/documentation/master/#call
    - SkiFire13 2y ago
      Generally I also find Zig's documentation pretty lacking, instead I try looking for the relevant issues/prs. In this case I found comments on this issues [1] which seem to still hold true. That same issue also links to the relevant LLVM/Clang issue [2], and the same restriction is also being proposed for Rust [3]. This is were I first learned about it and prompted me to investigate whether Zig also suffers from the same issue. [1]: https://github.com/ziglang/zig/issues/694#issuecomment-1567447672 https://github.com/ziglang/zig/issues/694#issuecomment-15674... [2]: https://github.com/llvm/llvm-project/issues/54964 https://github.com/llvm/llvm-project/issues/54964 [3]: https://github.com/rust-lang/rfcs/pull/3407 https://github.com/rust-lang/rfcs/pull/3407
    - ufo 2y ago
      This limitation is to ensure that the two functions use the exact same calling convention (input & output registers, and values passed via stack). It can depend on the particular architecture.
- Thorrez 2y ago
  C++: > All current mainstream compilers perform tail call optimisation fairly well (and have done for more than a decade) https://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization https://stackoverflow.com/questions/34125/which-if-any-c-com... (2008)
  - hyperbrainer 2y ago
    I couldn't actually figure out whether this TCO being done "fairly well" was a guarantee or simply like Rust (I am referring to the native support of the language, not what crates allow)
    - Thorrez 2y ago
      When that SO answer was written, it was not a guarantee. You can now get a guarantee by using non-standard compiler attributes: https://clang.llvm.org/docs/AttributeReference.html#musttail https://clang.llvm.org/docs/AttributeReference.html#musttail https://gcc.gnu.org/onlinedocs/gcc/Statement-Attributes.html#index-musttail-statement-attribute https://gcc.gnu.org/onlinedocs/gcc/Statement-Attributes.html...
- johnisgood 2y ago
  Depends on what you mean by "systems programming", you can definitely do that in OCaml.
- pjmlp 2y ago
  "Unix system programming in OCaml" https://ocaml.github.io/ocamlunix/ocamlunix.html https://ocaml.github.io/ocamlunix/ocamlunix.html MirageOS https://mirage.io/ https://mirage.io/ House OS, https://programatica.cs.pdx.edu/House/ https://programatica.cs.pdx.edu/House/ Just saying.
  - hyperbrainer 2y ago
    I know of these. Almost added a disclaimer too -- that was not my point, as I am sure, you understand. Also Ocaml has a GC, unsuitable for many applications common to systems programming.
chowells 2y ago
I'll believe destroying stacktrace information is a valid complaint when people start complaining that for loops destroy the entire history of previous values the loop variables have had. Tail recursion is equivalent to looping. People should stop complaining when it gives them the same information as looping.
- ameliaquining 2y ago
  I mean, if I were doing an ordinary non-recursive function call that just happened to be in tail position, and it got eliminated, and this caused me to not be able to get the full stack trace while debugging, I might be annoyed. In a couple languages I've seen proposals to solve this problem with a syntactic opt-in for tail call elimination, though I'm not sure whether any mainstream language has actually implemented this.
  - chowells 2y ago
    Language designers could keep taking ideas from Haskell, and allow functions to opt in to appearing in stack traces. Give the programmer control, and all.
  - SamLL 2y ago
    Kotlin has a syntactic opt-in for tail call elimination (the "tailrec" modifier).
  - michaelmrose 2y ago
    https://clojuredocs.org/clojure.core/recur https://clojuredocs.org/clojure.core/recur
- roenxi 2y ago
  > I'll believe destroying stacktrace information is a valid complaint when people start complaining that for loops destroy the entire history of previous values the loop variables have had. That is a common criticism. You're referring to the functional programmers. They would typically argue that building up state based on transient loop variables is a mistake. The body of a loop ideally should be (at the time any stack trace gets thrown) a pure function of constant values and a range that is being iterated over while being preserved. That makes debugging easier.
vbezhenar 2y ago
Some of the issues partially alleviated by using limited part of tail recursion optimization. You mark some function with tailrec keyword, and compiler verifies that this function calls itself as the last statement. You also wouldn't expect complete stack trace from that function. At the same time it probably helps with 90% of recursive algorithms which would benefit from the tail recursion.
- LeFantome 2y ago
  That is what Clojure does I believe.

hyperbrainer 2y ago

AFAIK Zig is the only somewhat-big and known low-level language with TCO. Obviously, Haskell/Ocaml and the like support and it are decently fast too, but system programming languages they are not.

vlovich123 2y ago
For guarantee: https://crates.io/crates/tiny_tco https://crates.io/crates/tiny_tco https://crates.io/crates/tco https://crates.io/crates/tco As an optimization my understanding is that GCC and LLVM implement it so Rust, C, and C++ also have it implicitly as optimizations that may or may not apply to your code. But yes, zig does have a formal language syntax for guaranteeing tail calls to happen at the language level (which I agree with as the right way to expose this optimization).
SkiFire13 2y ago
Zig's tco support is not much different than Clang's `[[clang::musttail]]` in C++. Both have the big restriction that the two functions involved are required to have the same signature.
- hyperbrainer 2y ago
  > Both have the big restriction that the two functions involved are required to have the same signature. I did not know that! But I am a bit confused, since I don't really program in either language. Where exactly in the documentation could I read more about this? Or see more examples? The language reference for @call[0] was quite unhelpful for my untrained eye. [0] https://ziglang.org/documentation/master/#call https://ziglang.org/documentation/master/#call
  - SkiFire13 2y ago
    Generally I also find Zig's documentation pretty lacking, instead I try looking for the relevant issues/prs. In this case I found comments on this issues [1] which seem to still hold true. That same issue also links to the relevant LLVM/Clang issue [2], and the same restriction is also being proposed for Rust [3]. This is were I first learned about it and prompted me to investigate whether Zig also suffers from the same issue. [1]: https://github.com/ziglang/zig/issues/694#issuecomment-1567447672 https://github.com/ziglang/zig/issues/694#issuecomment-15674... [2]: https://github.com/llvm/llvm-project/issues/54964 https://github.com/llvm/llvm-project/issues/54964 [3]: https://github.com/rust-lang/rfcs/pull/3407 https://github.com/rust-lang/rfcs/pull/3407
  - ufo 2y ago
    This limitation is to ensure that the two functions use the exact same calling convention (input & output registers, and values passed via stack). It can depend on the particular architecture.
Thorrez 2y ago
C++: > All current mainstream compilers perform tail call optimisation fairly well (and have done for more than a decade) https://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization https://stackoverflow.com/questions/34125/which-if-any-c-com... (2008)
- hyperbrainer 2y ago
  I couldn't actually figure out whether this TCO being done "fairly well" was a guarantee or simply like Rust (I am referring to the native support of the language, not what crates allow)
  - Thorrez 2y ago
    When that SO answer was written, it was not a guarantee. You can now get a guarantee by using non-standard compiler attributes: https://clang.llvm.org/docs/AttributeReference.html#musttail https://clang.llvm.org/docs/AttributeReference.html#musttail https://gcc.gnu.org/onlinedocs/gcc/Statement-Attributes.html#index-musttail-statement-attribute https://gcc.gnu.org/onlinedocs/gcc/Statement-Attributes.html...
johnisgood 2y ago
Depends on what you mean by "systems programming", you can definitely do that in OCaml.
pjmlp 2y ago
"Unix system programming in OCaml" https://ocaml.github.io/ocamlunix/ocamlunix.html https://ocaml.github.io/ocamlunix/ocamlunix.html MirageOS https://mirage.io/ https://mirage.io/ House OS, https://programatica.cs.pdx.edu/House/ https://programatica.cs.pdx.edu/House/ Just saying.
- hyperbrainer 2y ago
  I know of these. Almost added a disclaimer too -- that was not my point, as I am sure, you understand. Also Ocaml has a GC, unsuitable for many applications common to systems programming.

chowells 2y ago

I'll believe destroying stacktrace information is a valid complaint when people start complaining that for loops destroy the entire history of previous values the loop variables have had. Tail recursion is equivalent to looping. People should stop complaining when it gives them the same information as looping.

ameliaquining 2y ago
I mean, if I were doing an ordinary non-recursive function call that just happened to be in tail position, and it got eliminated, and this caused me to not be able to get the full stack trace while debugging, I might be annoyed. In a couple languages I've seen proposals to solve this problem with a syntactic opt-in for tail call elimination, though I'm not sure whether any mainstream language has actually implemented this.
- chowells 2y ago
  Language designers could keep taking ideas from Haskell, and allow functions to opt in to appearing in stack traces. Give the programmer control, and all.
- SamLL 2y ago
  Kotlin has a syntactic opt-in for tail call elimination (the "tailrec" modifier).
- michaelmrose 2y ago
  https://clojuredocs.org/clojure.core/recur https://clojuredocs.org/clojure.core/recur
roenxi 2y ago
> I'll believe destroying stacktrace information is a valid complaint when people start complaining that for loops destroy the entire history of previous values the loop variables have had. That is a common criticism. You're referring to the functional programmers. They would typically argue that building up state based on transient loop variables is a mistake. The body of a loop ideally should be (at the time any stack trace gets thrown) a pure function of constant values and a range that is being iterated over while being preserved. That makes debugging easier.

vbezhenar 2y ago

Some of the issues partially alleviated by using limited part of tail recursion optimization. You mark some function with tailrec keyword, and compiler verifies that this function calls itself as the last statement. You also wouldn't expect complete stack trace from that function. At the same time it probably helps with 90% of recursive algorithms which would benefit from the tail recursion.

LeFantome 2y ago
That is what Clojure does I believe.