[Retric]

It's trivial to blow the stack even on languages with tail call optimization.

[sklogic]

Ok, try to blow the stack in a stackless language implementation.

[Retric]

F(x) = F(x) + F(x)

Eventually you hit OOM or some death limit even on a stackless language.

[sklogic]

This is a memory leak now, not a stack overflow.

[Retric]

Thus demonstrating a finite stack. "Stackless" just a more efficent way to use memory. You could get the same things from dynamicly allocating and dealocating stack space as needed.

Put another way, allocating 1GB of stack space on a machine with 2GB of RAM is at worst the equivelent of using a stackless lanugage on a machine limited 1 GB of RAM.

PS: It's actually worse as stackless languages are stricly slower than actually having the equivelent stack space pre alocated and you need to put an pointer for each stack call pluss overhead for alocating memory.

[mytochar]

By writing incorrect recursion? Or in some other way?

[Retric]

Both, the obvious example is the fibinatchi sequence f(x) = f(x-1) + f(x-2). There are lots of efficient ways of coding it but the most obvious O(n^2) approch is n depth and it can't be tail-call optimized.

Granted, you can write much more efficient code that can be tail call optimized, but there complex and less obvious. There are also languages which cache previous results so the native approch becomes O(n) with fairly elegant code that's still depth n.

PS: Anyway, tail call optimization only works when you can rewrite the code as a loop for more complex structures it's less useful.

[sklogic]

> Anyway, tail call optimization only works when you can rewrite the code as a loop

You cannot turn a virtual tail call into a static jump.

[Retric]

Sure, it needs bookkeeping but it's still trivial to create a loop equivalent of any tail call optimizable code that your compiler recognizes.

PS: Feel free to look for any counter example.

[sklogic]

> PS: Feel free to look for any counter example.

Ok, create a loop equivalent for `(define (f g x) (g x))`.

[Retric]

x

Though the mechanical equivalent would be something like:

  huge(input)
  {
  output, continue, current_function = f;
  do{
  if (current_function == f)
  {input = x ; continue = true; current_function=g}
  if (current_function == g)
  { output = input; continue = false;}
  }while(continue);
  return output;
  }

You would then add any function you would tail call optimize into that function. Granted, with the right structure (inside > outside >... > inside) it can show up more than once on the stack but the same thing can happen despite tail call optimization.