Are programs in functional languages more likely to have stack overflows?

Question

I am starting to learn ocaml, and am really appreciating the power of recursion in the language. However, one thing that I am worried about is stack overflows.

If ocaml uses the stack for function calls, won't it eventually overflow the stack? For example, if I have the following function:

let rec sum x =
  if x > 1 then f(x - 1) + x
  else x;;

it must eventually cause a stack-overflow. If I was to do the equivalent thing in c++ (using recursion), I know that it would overflow.

So my question is, is there built in safeguards to prevent functional languages from overflowing the stack? If not, are they not less useful like this, since the above summing algorithm, written in a procedural style with a for loop, could handle any number (dis-regarding integer overflow)?

Ramos

hey! that's the name of the site. – Gladwin

Answer 1

All (decent implementations of;-) functional languages optimize tail recursion, but that's not what you're doing here, since the recursive call is not the LAST operation (it needs to be followed by the addition).

So, one soon learns to use an auxiliary function that IS tail recursive (and takes the current total being accumulated as an argument) so the optimizer can do its job, i.e., net of possible O'Caml syntax in which I'm rusty:

let sum x =
  aux(x)(0);;

let rec aux x accum =
  if x > 1 then aux(x - 1)(accum + x)
  else (accum + x);;

Here, the sum happens as an ARGUMENT to the recursive call, i.e., BEFORE the recursion itself, and so tail optimization can kick in (because the recursion IS the last thing that needs to happen!).

Tradesman

OCaml doesn't use commas to delimit its function arguments. It uses spaces. Any arguments that are expressions need to be enclosed in parenthesis. – Ozell

yeah, I think that your code should be if x > 1 then aux (x -1) (accum + x) – Ramos

but +1 for showing how to convert to a tail-recursive function (now that really blows my head - functional programming is hard enough to get my head around the way I had written it) – Ramos

so if I understand correctly, to use tail-calls, the function should be the only operation (no operations allowed on the result of the call, etc.) – Ramos

@a_m0d, tx for the syntax correction, gonna edit to fix it (as I said I'm rusty in O'Caml syntax -- e.g. how to call a function with two arguments -- but the key ideas of functional programming are burned-in deeper;-). – Tradesman

@Ramos again, yes, essentially: tail calls can be optimized if and only if they ARE "the tail", i.e., the last operation in the caller; this can often, though not always!, be obtained through an auxiliary function with "accumulator"-like arguments. – Tradesman

Answer 2

Functional languages typically have a MUCH larger stack. For example, I've written a function specifically to test stack limits in OCaml, and it got to over 10,000 calls before it barfed. However, your point is valid. Stack-overflows are still something you need to watch out for in functional languages.

One of the strategies that functional languages use to mitigate their reliance on recursion is the use of tail-call optimization. If the call to the next recursion of the current function is the last statement in the function, the current call can be discarded from the stack and the new call instantiated in its place. The assembly instructions that are generated will be basically the same as the ones for while-loops in imperative style.

Your function is not tail-call optimizable because the recursion is not the last step. It needs to return first and then it can add x to the result. Usually this is easy to get around, you just create a helper function that passes an accumulator along with the other parameters

let rec sum x =
  let sum_aux accum x =
    if x > 1 then sum_aux (accum + x) (x - 1)
    else x
  in sum_aux 0 x;;

Ozell

Functional languages don't have "larger stacks". The size of the stack (for native code executables) is defined by the OS. OCaml can make more recursive calls probably because of ABI - parameters are passed in registers by default and so less stack space is used. I believe you can achieve the same in C with fastcall calling convention. – Varletry

Thanks for the correction! I think certain versions of Windows (to which I was exposed years ago) require/allow the estimated stack size to be specified at link time. There is a reasonable default, but if your program uses a lot of recursion or has functions with large stack frames you need to request a bigger stack. I guess I had just assumed that this was the way things worked and that OCaml must have been setup to request larger stacks by default, but apparently nicer operating systems don't have this limitation. I hadn't thought to reexamine how call stacks work until now. Thanks! – Ozell

Answer 3

Some functional languages such as Scheme specify that tail recursion must be optimized to be equivalent to iteration; hence, a tail-recursive function in Scheme will never result in a stack overflow, no matter how many times it recurses (presuming, of course, that it doesn't also recurse or engage in mutual recursion in other places besides the end).

Most other functional languages don't require tail recursion to be implemented efficiently; some choose to do so, others do not, but it's relatively easy to implement, so I would expect that most implementations do so.

Leede

I believe this is also true in F#, as examining the emitted IL will show that an ordinary loop is created. See thevalerios.net/matt/2009/01/… – Haroldson

Some of them might require you to write "x + f(x - 1)" instead of "f(x - 1) + x" for it to be considered tail-recursion, right? – Schauer

It still wouldn't be tail-recursive when written like that. – Iconic

@RobertHarvey: Yes, the F# compiler turns tail recursion into a loop, and furthermore tail calls emit the IL .tail opcode which does TCO. (Note: in 'debug' mode, tail calls are turned off by default, so as to preserve stacks for debugging; see the --tailcalls compiler flag.) – Ornithopter

Answer 4

It's certainly easy for novices to write deep recursions that blow the stack. Objective Caml is unusual in that the library List functions are not stack-safe for long lists. Applications like Unison have actually replaced the Caml standard List library with a stack-safe version. Most other implementations do a better job with the stack. (Disclaimer: my information describes Objective Caml 3.08; the current version, 3.11, may be better.)

Standard ML of New Jersey is unusual in that it doesn't use a stack, so your deep recursions keep going until you run out of heap. It's described in Andrew Appel's excellent book Compiling with Continuations.

I don't think there's a serious problem here; it's more a "point of awareness" that if you are going to be writing a lot of recursive code, which you're more likely to do in a functional language, you have to be aware of non-tail calls and of stack size as compared to the size of the data you'll be processing.

Krebs

Answer 5

This is tricky -- in principle yes, but the compilers and runtimes for functional languages account for the increased degree of recursion in functional languages. The most basic is that most functional language runtimes request a much larger stack than normal iterative programs would use. But in addition to that, a functional language compiler is much more able to transform recursive code into a non-recursive due to the much stricter constraints of the language.

Blouin