4 ms·

One of the arguments un favour if Tail Calls Elimination it that it allows to implement a goto-state-machine with mutally recursive functions.

• OskarS 3y ago
  Yeah, this is a really interesting point, I should try this again with [[musttail]] on clang.
  • afiori 3y ago
    My understanding is that while it is possible to compile Tail Calls to be as efficient as an inline function it is (often) not possible in C.
• kazinator 3y ago
  But the goto state machine is no easier to understand than the one with gotos. There was an argument like this on the comp.lang.c newsgroup a few years ago. Someone proposed a coding problem: I think it was writing a program that removes comments from C source, but preserves preprocessing directives and all else. So various solutions were posted. I wrote one that used a state machine based on goto; no control structures at all beyond assigning to variables and if/goto. That original poster then revealed his solution. It consisted of mutually tail calling functions. He specifically criticized the goto graph solution. I claimed they are basically the same, and to bolster my argument, I wrote a trivial simple text filter which converted that tail calling solution to a goto graph. Tail calling is not a higher level feature compared to goto. It is only syntactic sugar which leaves the program with the same organization. In some ways, the goto program is easier to understand. Why? Because: 1. The variables of the graph are all declared together in one place. Say you have a local variable x. All goto graph blocks that refer to x are referring to the same thing. In the tail program, every function that does something with x has to declare it for itself as its own parameter. It's not obvious that those x's are supposed to be the same entity. 2. Typically, functional languages, like C, do not have named parameters. The state is passed among the tail-calling function via strictly positional arguments. Not all functions have all the state variables, so a given state variable could be argument 3 in one function or argument 1 in another function. In the goto program it's very clear. If you have bar: x = s + 1; goto foo; we know: oh okay, this block updates the x state from s, and goes to foo. In the functional version: bar(s) -> foo(s + 1) we don't know what s + 1 is doing. We have to read foo: foo(x) -> ... ok, we know that s + 1 will be called x in foo. But is that consistent? Is it the same as every other x we see everywhere in the tail call graph? We easily see that consistency in the goto graph: there is a single x variable in the scope of the entire graph; anything that assigns to x is preparing a new value for that x.
  • afiori 3y ago
    > In some ways, the goto program is easier to understand. Why? Because: > 1. The variables of the graph are all declared together in one place. [...] > 2. Typically, functional languages, like C, do not have named parameters. [...] I have little experience in C, but probably I would try to use a struct for the machine state. Even with no tail calls I think I would try to write the machine as mostly block of bar: step_bar(&state); goto foo; From my optic the benefit of tail calls is the ability to mix flow control and machine steps with function abstractions.
    • kazinator 3y ago
      Yes; or well: void step_bar(state *state) { state.x = state.s + 1 return step_foo(state) } This is where the single dispatch OOP with implicit class-scoped "self" reduces noise: void state::step_bar() { x = s + 1; return step_foo(); } You have the tail calls, all variables in one place: x is always the same x. You know which variables are being set in each state transition; no need to look through parameter positions in function definitions.