5 ms·

I feel like tail calls are pretty obvious, the c++ grammar even explicitly calls them out.

by swiley 6y ago

rbanffy 6y ago
This is a magic vs. no-magic thing. TCO is a magical thing that implicitly changes the behavior of code with the same syntax. The code says the stack should blow up, but the compiler saves you from it. I'll side with the Python teaching that explicit is better than implicit. If the code says the stack will blow, then the compiler/runtime should not try to avoid that.
- yvdriess 6y ago
  There's nothing magical about a language that says that a tail-call will reuse the same frame/record/instance. It's only magical and unreliable when it's not in the language spec.
  - leoc 6y ago
    And a well-defined TCO guarantee would probably not rank very high on the already long list of things that make it ... a bit tricky to discern the performance of a function from looking at the text of the function body.
- dTal 6y ago
  It's not any more "magic" than garbage collection. The runtime figures out when memory is no longer required and frees it, through perfectly well-defined and easy-to-model rules. The code doesn't "say" the stack will blow because a finite stack isn't a language guarantee - it's simply an inconvenient fact of life.
qsort 6y ago
Eh, kinda. They are obvious modulo a lot of things, such as what definition of tail call your compiler is using and what optimizations it performs. Your comment piqued my curiosity and I made a little experiment :) The following function: int rec(int n) { if (n < 1) return 0; return 1 + rec(n - 1); } will get TCOd by gcc but not by clang (!!) I don't know, probably I'm not smart enough for TCO, but I just don't want to work like that. It's a minefield.
- yvdriess 6y ago
  That's not a tail recursive call.
  - qsort 6y ago
    That's precisely the point.
    - yvdriess 6y ago
      I'm confused, how are you testing TCO by giving the compiler a non-tail call?
- maverwa 6y ago
  Would you mind sharing the compiler versions and flags used? I tried to look at it in godbolt, but gcc 10.2 -O and clang 11.0 -O look pretty much the same. On the other hand, I know pretty little about C and its compilers ;)
  - qsort 6y ago
    clang 11.0, gcc 7.4, O2. I did that with whatever was already installed on my machines, YMMV.
- CalChris 6y ago
  However, for -O3 on ARMv8, LLVM generates pretty good if slightly inscrutable code [1]: rec: // @rec bic w0, w0, w0, asr #31 ret That's taking the sign bit, replicating it to 32b and then using it as a not'd mask. negative numbers: w0, asr #31 => -1 bic w0, w0, -1 => and w0, w0, 0 => ret 0 positive numbers: w0, asr #31 => 0 bic w0, w0, 0 => and w0, w0, 0xffffffff => ret w0 gcc is also pretty good [2]: rec: cmp w0, 0 csel w0, w0, wzr, gt ret [1] https://godbolt.org/z/q9hM7z https://godbolt.org/z/q9hM7z [2] https://godbolt.org/z/6rbE5e https://godbolt.org/z/6rbE5e
- Hitton 6y ago

I feel like tail calls are pretty obvious, the c++ grammar even explicitly calls them out.

by swiley 6y ago

I feel like tail calls are pretty obvious, the c++ grammar even explicitly calls them out.

This is a magic vs. no-magic thing. TCO is a magical thing that implicitly changes the behavior of code with the same syntax. The code says the stack should blow up, but the compiler saves you from it. I'll side with the Python teaching that explicit is better than implicit. If the code says the stack will blow, then the compiler/runtime should not try to avoid that.

yvdriess 6y ago
There's nothing magical about a language that says that a tail-call will reuse the same frame/record/instance. It's only magical and unreliable when it's not in the language spec.
- leoc 6y ago
  And a well-defined TCO guarantee would probably not rank very high on the already long list of things that make it ... a bit tricky to discern the performance of a function from looking at the text of the function body.
dTal 6y ago
It's not any more "magic" than garbage collection. The runtime figures out when memory is no longer required and frees it, through perfectly well-defined and easy-to-model rules. The code doesn't "say" the stack will blow because a finite stack isn't a language guarantee - it's simply an inconvenient fact of life.

qsort 6y ago

Eh, kinda. They are obvious modulo a lot of things, such as what definition of tail call your compiler is using and what optimizations it performs. Your comment piqued my curiosity and I made a little experiment :) The following function: int rec(int n) { if (n < 1) return 0; return 1 + rec(n - 1); } will get TCOd by gcc but not by clang (!!) I don't know, probably I'm not smart enough for TCO, but I just don't want to work like that. It's a minefield.

yvdriess 6y ago
That's not a tail recursive call.
- qsort 6y ago
  That's precisely the point.
  - yvdriess 6y ago
    I'm confused, how are you testing TCO by giving the compiler a non-tail call?
maverwa 6y ago
Would you mind sharing the compiler versions and flags used? I tried to look at it in godbolt, but gcc 10.2 -O and clang 11.0 -O look pretty much the same. On the other hand, I know pretty little about C and its compilers ;)
- qsort 6y ago
  clang 11.0, gcc 7.4, O2. I did that with whatever was already installed on my machines, YMMV.
CalChris 6y ago
However, for -O3 on ARMv8, LLVM generates pretty good if slightly inscrutable code [1]: rec: // @rec bic w0, w0, w0, asr #31 ret That's taking the sign bit, replicating it to 32b and then using it as a not'd mask. negative numbers: w0, asr #31 => -1 bic w0, w0, -1 => and w0, w0, 0 => ret 0 positive numbers: w0, asr #31 => 0 bic w0, w0, 0 => and w0, w0, 0xffffffff => ret w0 gcc is also pretty good [2]: rec: cmp w0, 0 csel w0, w0, wzr, gt ret [1] https://godbolt.org/z/q9hM7z https://godbolt.org/z/q9hM7z [2] https://godbolt.org/z/6rbE5e https://godbolt.org/z/6rbE5e
Hitton 6y ago