In functional languages, how is the compiler able to translate non-tail recursion into loops to avoid stack overflows (if at all)?

Question

I've been recently learning about functional languages and how many don't include for loops. While I don't personally view recursion as more difficult than a for loop (and often easier to reason out) I realized that many examples of recursion aren't tail recursive and therefor cannot use simple tail recursion optimization in order to avoid stack overflows. According to this question, all iterative loops can be translated into recursion, and those iterative loops can be transformed into tail recursion, so it confuses me when the answers on a question like this suggest that you have to explicitly manage the translation of your recursion into tail recursion yourself if you want to avoid stack overflows. It seems like it should be possible for a compiler to do all the translation from either recursion to tail recursion, or from recursion straight to an iterative loop with out stack overflows.

Are functional compilers able to avoid stack overflows in more general recursive cases? Are you really forced to transform your recursive code in order to avoid stack overflows yourself? If they aren't able to perform general recursive stack-safe compilation, why aren't they?

Answer 1

Any recursive function can be converted into a tail recursive one. For instance, consider the transition function of a Turing machine, that is the mapping from a configuration to the next one. To simulate the turing machine you just need to iterate the transition function until you reach a final state, that is easily expressed in tail recursive form. Similarly, a compiler typically translates a recursive program into an iterative one simply adding a stack of activation records.

You can also give a translation into tail recursive form using continuation passing style (CPS). To make a classical example, consider the fibonacci function. This can be expressed in CPS style in the following way, where the second parameter is the continuation (essentially, a callback function):

def fibc(n, cont):
    if n <= 1:
        return cont(n)
    return fibc(n - 1, lambda a: fibc(n - 2, lambda b: cont(a + b)))

Again, you are simulating the recursion stack using a dynamic data structure: in this case, lambda abstractions.

The use of dynamic structures (lists, stacks, functions, etc.) in all previous examples is essential. That is to say, that in order to simulate a generic recursive function iteratively, you cannot avoid dynamic memory allocation, and hence you cannot avoid stack overflow, in general.

So, memory consumption is not only related to the iterative/recursive nature of the program. On the other side, if you prevent dynamic memory allocation, your programs are essentially finite state machines, with limited computational capabilities (more interesting would be to parametrise memory according to the dimension of inputs).

In general, in the same way as you cannot predict termination, you cannot predict an unbound memory consumption of your program: working with a Turing complete language, at compile time you cannot avoid divergence, and you cannot avoid stack overflow.

Answer 2

Tail Call Optimization:

The natural way to do arguments and calls is to sort out the cleaning up when exiting or when returning.

For tail calls to work you need to alter it so that the tail call inherits the current frame. Thus instead of making a new frame it massages the frame so that the next call returns to the current functions caller instead of this function, which really only cleans up and returns if it's a tail call.

Thus TCO is all about cleaning up before the last call.

Continuation Passing Style - make tail calls out of everything

A compiler can change the code such that it only does primitive operations and pass it to continuations. Thus the stack usage gets moved onto the heap since the computation to be continued is made a function.

An example is:

function hypotenuse(k1, k2) {
  return sqrt(add(square(k1), square(k2)))
}

becomes

function hypotenuse(k, k1, k2) {
  (function (sk1) {
    (function (sk2) {
      (function (ar) {
         k(sqrt(ar));
      }(add(sk1,sk2));
    }(square(k2));
  }(square(k1));
}

Notice every function has exactly one call now and the order of evaluation is set.