<p>All of the following comments are premised on the choice of a standard implementation strategy using closures to represent function values and a call-by-value evaluation order:</p>

<ol>
<li><p>For the pure lambda calculus, garbage collection is not necessary. This is because it is not possible to form cycles in the heap: every newly-allocated value can only contain references to previously-allocated values, and so the memory graph forms a DAG -- so reference counting suffices to manage memory.</p></li>
<li><p>Most implementations do not use reference counting for two reasons. </p>

<ol>
<li>They support a form of pointer type (eg, the <code>ref</code> type constructor in ML), and so true cycles in the heap can be formed.</li>
<li>Reference counting is much less efficient than garbage collection, since 

<ul>
<li>it requires a lot of additional space to keep the reference counts, and </li>
<li>updating the counts is usually wasted work, and </li>
<li>the updates to the counts create a bunch of write contention which kills parallel performance.</li>
</ul></li>
</ol></li>
<li><p>Linearly-typed languages can eliminate the reference count (essentially because counts are 0-1: either the value has a single reference to it or it is dead and can be freed). </p></li>
<li><p>However, stack allocation still does not suffice. This is because it is possible to form function values which refer to free variables (i.e., we need to implement function closures), if you allocate things on the stack, then live values can be interleaved with dead values, and this will cause incorrect asymptotic space usage. </p></li>
<li><p>You can get the right asymptotics by replacing a stack with a "spaghetti stack" (ie, implement the stack as a linked list in the heap, so that you can cut out dead frames as needed).</p></li>
<li><p>If you want a real stack discipline, you can use type systems based on "ordered logic" (essentially linear types minus exchange). </p></li>
</ol>

CC BY-SA 3.0
2016-09-12T17:53:35.567Z
Isn't the more basic reason for (2) that -- even without observable side effects -- implementations want to have an efficient operator for (mutual) recursion, i.e., one that actually forms a cycle in the heap?
Andreas Rossberg
CC BY-SA 3.0
2016-09-12T22:58:27.690Z
@andreasrossberg: I thought about mentioning that, but left it out since you can use the y combinator for recursion.
Neel Krishnaswami
CC BY-SA 3.0
2016-09-12T16:19:55.920Z
2016-09-12T16:19:55.920Z
Neel Krishnaswami
<p>What's stopping ghc from translating Haskell into a concatenative programming language such as combinatory logic and then simply using stack allocation for everything? According to Wikipedia, the translation from lambda calculus to combinatory logic is trivial, and also, concatenative programming languages can rely solely on a stack for memory allocation. Is it feasible to do this translation and thus eliminate garbage collection for languages such as Haskell and ocaml? Are there downsides to doing this?</p>

<p>EDIT: moved here <a href="https://stackoverflow.com/questions/39440412/why-do-functional-programming-languages-require-garbage-collection">https://stackoverflow.com/questions/39440412/why-do-functional-programming-languages-require-garbage-collection</a></p>

CC BY-SA 3.0
2016-09-11T12:30:01.110Z
The [Cat Programming Language](http://www.artima.com/weblogs/viewpost.jsp?thread=160177) looks like an example of a function, stack-based language.
Petr
CC BY-SA 3.0
2016-09-11T16:47:50.793Z
This is *not* a research-level question, as garbage collection is covered in undergraduate courses on programming languages (as well as the need for it). Please move over to cs.stackexchange.com
Andrej Bauer
CC BY-SA 3.0
2016-09-11T20:41:04.987Z
My mistake. Do you know the answer to my question?
Nicholas Grasevski
CC BY-SA 3.0
2016-09-12T00:09:27.933Z
I think there's some research level response to be given to this question, as I remember struggling with it during my grad years as well: everything in a language like Haskell *looks like* a function application, which lives on the stack. I think explaining why closures are necessary, why they live on the heap, and perhaps what "data escaping the function scope" has to do with it would make a very informative answer (which I'm not sure I'm qualified to give, unfortunately).
cody
CC BY-SA 3.0
2016-09-12T07:44:08.190Z
I agree that parts of the question is research level. There are alterantive approaches to managing memory, e.g. region based (following Tofte, Talpin), affine type-based (Rust). The translation of $\lambda$-calculus into combinators leads to a blowup in size.
Martin Berger
<pl.programming-languages><functional-programming><haskell>
Why do functional programming languages require garbage collection?
Nicholas Grasevski
# Why do functional programming languages require garbage collection?

(Asked by: username_0 on 2016-09-11)

What's stopping ghc from translating Haskell into a concatenative programming language such as combinatory logic and then simply using stack allocation for everything? According to Wikipedia, the translation from lambda calculus to combinatory logic is trivial, and also, concatenative programming languages can rely solely on a stack for memory allocation. Is it feasible to do this translation and thus eliminate garbage collection for languages such as Haskell and ocaml? Are there downsides to doing this?

EDIT: moved here <https://stackoverflow.com/questions/39440412/why-do-functional-programming-languages-require-garbage-collection>

**Tags:** pl.programming-languages, functional-programming, haskell
> **Comments:**
> **username_1**: The [Cat Programming Language](http://www.artima.com/weblogs/viewpost.jsp?thread=160177) looks like an example of a function, stack-based language.  
> **username_2**: This is *not* a research-level question, as garbage collection is covered in undergraduate courses on programming languages (as well as the need for it). Please move over to cs.stackexchange.com  
> **username_0**: My mistake. Do you know the answer to my question?  
> **username_3**: I think there's some research level response to be given to this question, as I remember struggling with it during my grad years as well: everything in a language like Haskell *looks like* a function application, which lives on the stack. I think explaining why closures are necessary, why they live on the heap, and perhaps what "data escaping the function scope" has to do with it would make a very informative answer (which I'm not sure I'm qualified to give, unfortunately).  
> **username_4**: I agree that parts of the question is research level. There are alterantive approaches to managing memory, e.g. region based (following Tofte, Talpin), affine type-based (Rust). The translation of $\lambda$-calculus into combinators leads to a blowup in size.  

---

## 1 answers

### Answer by username_5 on 2016-09-12. Score: 22

All of the following comments are premised on the choice of a standard implementation strategy using closures to represent function values and a call-by-value evaluation order:

1. For the pure lambda calculus, garbage collection is not necessary. This is because it is not possible to form cycles in the heap: every newly-allocated value can only contain references to previously-allocated values, and so the memory graph forms a DAG -- so reference counting suffices to manage memory.
2. Most implementations do not use reference counting for two reasons.

   1. They support a form of pointer type (eg, the `ref` type constructor in ML), and so true cycles in the heap can be formed.
   2. Reference counting is much less efficient than garbage collection, since
      * it requires a lot of additional space to keep the reference counts, and
      * updating the counts is usually wasted work, and
      * the updates to the counts create a bunch of write contention which kills parallel performance.
3. Linearly-typed languages can eliminate the reference count (essentially because counts are 0-1: either the value has a single reference to it or it is dead and can be freed).
4. However, stack allocation still does not suffice. This is because it is possible to form function values which refer to free variables (i.e., we need to implement function closures), if you allocate things on the stack, then live values can be interleaved with dead values, and this will cause incorrect asymptotic space usage.
5. You can get the right asymptotics by replacing a stack with a "spaghetti stack" (ie, implement the stack as a linked list in the heap, so that you can cut out dead frames as needed).
6. If you want a real stack discipline, you can use type systems based on "ordered logic" (essentially linear types minus exchange).

> **Comments:**
> **username_6**: Isn't the more basic reason for (2) that -- even without observable side effects -- implementations want to have an efficient operator for (mutual) recursion, i.e., one that actually forms a cycle in the heap?  
> **username_5**: @andreasrossberg: I thought about mentioning that, but left it out since you can use the y combinator for recursion.  

---

