4 ms·

How do functional languages and, in general, the languages where the use of recursion is pervasive - how do they deal with this?

elipsitz 5y ago
In many cases, with tail call optimization, turning specific types of recursion into iteration (which doesn’t use more than a constant amount of stack space).
- masklinn 5y ago
  Not tail call optimisation, tail call elimination. If the language is based on recursion, you can't just hope it happens commonly enough, it has to happen all the time, even for corecursive functions. Except I've never been super clear on Haskell having TCE or not, because laziness means there are limited opportunities for it to even fire.
  - tome 5y ago
    Because function evaluation is lazy all Haskell (well, GHC) calls are tail calls. The only thing that consumes stack is case.
Verdex 5y ago
So, you can't answer "in general" because things are handled differently depending on the language. I believe Scheme basically only uses the heap (which is necessary because of call/cc iirc). Haskell uses a variation of a G machine (looks like a spineless tagless g machine to be specific). The way that works is that they convert your program into a giant lambda term and then they work on reducing it. This of course looks nothing like a traditional call stack, so you can replace that whole thing with the G machine. Recursion (at least of the non-tail recursive variety) will look like a lambda term slowly getting bigger in heap space. And then I also heard of someone (I forget which language) talking about setting up some logic to look for stack overflows and then throw all the current stack onto a heap and then start over.
- dfox 5y ago
  The part about detecting stack overflows probably refers to implementation strategy in some scheme implementations (IIRC chicken scheme does this) which involve using the platform/machine stack as effectively hardware-assisted nursery generation for generational copying GC, when it gets full (usually well before true overflow) the minor GC cycle gets done and the stack gets completely emptied. In these designs the "stack" is usually used for all allocations, not only for activation records.
  - twoodfin 5y ago
    This is “Cheney on the M.T.A.”, no? https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.7143&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54...
    - kragen 5y ago
      That's right.
miloignis 5y ago
Tail Call Optimization & allocating their own stacks, generally.

elipsitz 5y ago

In many cases, with tail call optimization, turning specific types of recursion into iteration (which doesn’t use more than a constant amount of stack space).

masklinn 5y ago
Not tail call optimisation, tail call elimination. If the language is based on recursion, you can't just hope it happens commonly enough, it has to happen all the time, even for corecursive functions. Except I've never been super clear on Haskell having TCE or not, because laziness means there are limited opportunities for it to even fire.
- tome 5y ago
  Because function evaluation is lazy all Haskell (well, GHC) calls are tail calls. The only thing that consumes stack is case.

Verdex 5y ago

So, you can't answer "in general" because things are handled differently depending on the language. I believe Scheme basically only uses the heap (which is necessary because of call/cc iirc). Haskell uses a variation of a G machine (looks like a spineless tagless g machine to be specific). The way that works is that they convert your program into a giant lambda term and then they work on reducing it. This of course looks nothing like a traditional call stack, so you can replace that whole thing with the G machine. Recursion (at least of the non-tail recursive variety) will look like a lambda term slowly getting bigger in heap space. And then I also heard of someone (I forget which language) talking about setting up some logic to look for stack overflows and then throw all the current stack onto a heap and then start over.

dfox 5y ago
The part about detecting stack overflows probably refers to implementation strategy in some scheme implementations (IIRC chicken scheme does this) which involve using the platform/machine stack as effectively hardware-assisted nursery generation for generational copying GC, when it gets full (usually well before true overflow) the minor GC cycle gets done and the stack gets completely emptied. In these designs the "stack" is usually used for all allocations, not only for activation records.
- twoodfin 5y ago
  This is “Cheney on the M.T.A.”, no? https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.7143&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54...
  - kragen 5y ago
    That's right.

miloignis 5y ago

Tail Call Optimization & allocating their own stacks, generally.