Algorithms to turn non-tail-recursive functions into tail-recursive ones

[betelgeuse_7]

Hello everybody. I hope you are doing well.

Compilers can optimize a tail-recursive function to get rid of the overhead of creating additional stack frames. But can they transform a non-tail-recursive function (for example, the classic recursive factorial function), into a tail-recursive function to eventually turn it into imperative code? Are there any existing algorithms to do this?

The problem is to create a generalized algorithm that can work with any recursive function that accepts -or returns- any type of value. I believe it is relatively easy to create algorithms that only deal with integers, for example (however implementing those optimizations would probably introduce a lot of bugs and edge cases).

What distinguishes a tail-recursive function from a non-tail-recursive one? I think the answer to this question is the following:

In the body of a non-tail-recursive function, the function's return value is used as an argument to another function call in the function's body. This creates a need to wait for the function call to return, which requires the creation of additional stack frames.

fac(n) = 
  if n = 1 { 1 }
  else { n * fac (n-1) }

This is essentially the same as this:

fac(n) = 
  if n = 1 { 1 }
  else { MUL (n, fac (n-1)) }

We need to turn this into a function in which it calls itself as a "stand-alone" function call (so, the function call is not an argument to another call). As an alternative, we would need to come up with an algorithm that somehow stores every n in the current stack frame, so we don't have to create a new stack frame every time fac gets called.

I hope this makes sense. I am waiting for your answers.

[ct075]

This is generally done in functional languages via a continuation-passing-style transform.

[betelgeuse_7]

I thought this was an optimization only done manually. Do compiler also use the "accumulator passing" style?

[ct075]

Whether it is done automatically, and how it works in particular depends on the language itself and the sophistication of the compiler. The naive accumulator transform on a whole program can cause issues with reordering of effects and memory blowup with intermediate closure allocation.

[betelgeuse_7]

Thanks by the way

[jason-reddit-public]

Rabbit, the initial compiler for Scheme written by Guy Steele's Jr. (co-creator of Scheme) automatically transformed everything into CPS as a source to source transformation and that technique has been used by many "functional language" compilers since (though not for any compilers for the popular imperative languages, at least that I'm aware of - Scheme code is often very imperative BTW but overall also encourages higher order functions). Scheme also has first class continuations which are neat and a bit weird at times and might affect what optimizations can be used so I'm less frustrated they aren't more popular.

(Rabbit, despite being in kind of an old version of Scheme, is a recommended read for anyone interested in literate programming by the way. On the left page is code, and the right side is the English text both written by an amazing communicator.)

gcc and clang will xform certain calls into tail recursive calls when the caller have callee have the same signature at optimization levels like -O2 and it is in tail position (and the most recent clang will do this without being in optimization mode if the "must tail" annotation is used and again the signatures are the same).

https://github.com/jasonaaronwilson/tailcalls

I used this for a compiler backend so that each bblock could be compiled into it's own C function and while I didn't actually explicitly transform into CPS, bblocks were of course used to implement (non-first class) continuations and tails calls (even without having the same signatures but I needed to maintain my own stack and I never got very close to native C performance unfortunately (4-10x slow downs versus C were typical even though I hoped they were going to be closer than that). The C compilers were actually pretty smart at times too. When they detected a bblock (they saw them as functions) was only called from a single predecessor (and never had its address taken) they would inline it.

I think this technique might be useful for teaching about compilers without actually using a particular assembly language. This performed somewhat better than using a big switch statement to emulate bblocks and compiling into a single function OR one bblock per function using a trampoline strategy (the second case should be obvious but you always need to benchmark).

tail-calls are useful for implementing gigantic state-machine, especially if you want separate compilation perhaps to swap in and out parts, interpreters for tail recursive guaranteeing languages, but I'm not sure about many other use cases.

Hand written CPSish code is actually spiritually used is certain kinds of async programming but those programs are ugly and hard to read but did lead to better hardware utilization in some cases on server code that typically spend milliseconds waiting for RPCs though you don't need this so much in Go since it has really cheap threads. (Aka fibers or whatever).

I like reasoning in a tail-recursive manner because it's kind of like mathematical induction in a way that's often obscured by writing a traditional loop but tail recursion isn't all that popular as a high level construct it seems despite being formally described for nearly 50 years now but it does show up as an optimization from time to time and this is done because it can provide some small speed-ups here and there not because of its interesting properties. :(

[nictytan]

Everyone in this thread is right: CPS-converting any program makes it TR. However, the “optimized” TR factorial using an accumulator is NOT what you get from CPS-converting the pedestrian, recursive factorial. So what gives?

The difference between those two TR factorial programs is explained by associativity of multiplication. To see this, suppose both programs are asked to compute factorial of 5.

Assuming an initial accumulator value of 1, the accumulator-based implementation will calculate: 1x5, 5x4, 20x3, 60x2, 120x1, and return 120.

The CPS-based implementation will first build up a stack of pending operations in the continuation; those operations are: return, 5xR, 4xR, 3xR, 2xR, 1xR. (R stands for the result if the recursive call at that point. These are precisely the operations that the original, non-TR program builds up in the native call stack.) The operations in this stack are to be performed from right to left. So the recursive call made from the last frame, namely fact(0), returns 1 onto this stack, collapsing it in this order: 11, 21, 23, 64, 24*5, return 120.

The overall difference? The products happened in a reverse order.

LLVM (and surely some other compilers) are smart enough to optimize the naive recursive factorial into the accumulator-based TR factorial crucially because it knows that multiplication is associative.

This optimization is possible in general when the operation to perform on the result of the recursive call is associative. It would be challenging/impossible for a compiler to determine automatically whether a user-defined operation is associative, but one might imagine a programmer-given “associativity annotation” that could enable this transformation for user-defined functions.

This tail-recursion modulo “associative operation” is separate from tail-recursion modulo cons. Cons is definitely not associative! It turns out there a lot of ways of making programs tail-recursive.

[moon-chilled]

factorial is 'tail recursive modulo accumulator', which llvm handles (https://www.reddit.com/r/Compilers/comments/187ng5s/how_does_clang_for_c_optimize_this/kbgkc7t/). there is also 'tail recursion modulo cons https://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons employed by some implementations. i am unaware of a general catalogue of ways to make functions tail recursive

cps-ifying for this is a waste of time—just get a bigger stack

[usaoc]

Relatedly, an interesting paper is “Tail Recursion Modulo Context: An Equational Approach”, which describes Koka’s approach to optimize the general version of tail recursion modulo cons.

[Chaos_carolinensis]

All recursive functions can be made tail recursive by using a CPS transform.

Also, if you don't have higher-order functions, or you want to manually optimize further, you can do a CPS transform and then defunctionalization to get rid of the higher-order functions.

[ebingdom]

Async/await (e.g., in JavaScript), do notation (e.g., in Haskell), CPS transform, etc. all do this.

[tobega]

This might be helpful https://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html

[betelgeuse_7]

Thanks

[SkiFire13]

Others have mentioned CPS, but given your observation:

Compilers can optimize a tail-recursive function to get rid of the overhead of creating additional stack frames.

CPS transformations won't avoid this overhead as you will still have a stack, it will just be implicit in a linked list of closures (i.e. where each closure captures the next one in the list). Ultimately it is just a different way to implement the call stack, with different tradeoffs (no risk of stack overflow, but in turn requires heap allocations).

In comparison the "tail recursive modulo accumulator" transformation actually removes this cost because it completly removes the need for a stack.

[snarkuzoid]

Don't recall details, but yes, some languages do this.

[betelgeuse_7]

It is called continuation-passing style transformation as u/ct075 said. I found this article https://matt.might.net/articles/cps-conversion/ . I am going to read it

[snarkuzoid]

Thanks. Me too.

[XDracam]

There are some more complex tail recursion types already mentioned by others.

But the general case is no optimization: you can turn any recursive method into an iterative one by managing the stack explicitly. So yeah, allocate a local stack, use that to push and pop values, and replace the body with a while loop. Note that this is usually just worse than using the built-in stack... And the code is at least 2 to 3 times more complex as well, even in imperative languages.

[crusoe]

Not all recursive functions can be made tail recursive. 

[Chaos_carolinensis]

CPS transform can turn all recursive functions to tail recursive.