Why do functional programming languages require garbage collection?

Question

According to Wikipedia, the translation from lambda calculus to combinatory logic is trivial. Concatenative programming languages can rely solely on a stack for memory allocation.

What's stopping GHC from translating Haskell into a concatenative programming language, such as combinatory logic, and then simply using stack allocation for everything?

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?

Answer 1

Suppose I have a function that generates a linked list of some size. The size is the function parameter.

The question is: where do I have to allocate memory for the list? I can't allocate it on the function's stack, since it's invalid after the function is out. And I can't allocate it on the caller's stack, since I don't know how many memory I need to allocate before the function call. So I need to allocate it on the heap.

I think there may be RAII with manual heap management usable, But I can't see how to eliminate heap allocation at all.

---

Edit

I can't fit all my thoughts in the comment, so I write them here.

There is no magic about stack-based allocation languages. You still need to know when your data is relevant and remove them when they're not.

Imagine you have a separate stack, and your function has control to push and pop data in it. First, there is no automatic memory management anymore, i.e. the function terminates but the data is not deallocated automatically. Second, if you function allocates some memory, needed to support e.g. the list calculation, then all that stuff will be shuffled with the list that you want to return. No chance you can free unused memory (other lists, trees or so) since you have just push and pop operations. If you have other operations, then what is the difference with the heap?

What about few stacks, not one?

You need to allocate them somewhere, manage their growth and sometimes get them back. That stacks are separate constructions that you need manage by hands. No automatic memory management.

Stack-based languages are ok, but forget about the huge amount of algorithms, that was invented with the concept "get memory from somewhere" and "put the memory back", like hash maps, red-black trees, linked lists. Of course, we can allocate all of those structs on a stack, but we can't free their parts if they don't need anymore.

What about "trivial" lambda calculus translation to Turing machine?

Of course, it is trivial, if you resources are infinite. The math theory clarifies nothing about time and memory complexity of such translated constructions. It just approves that both of that models are equivalent, and all that we can say with Turing machine we can say with lambda calculus, and vice-versa. No guarantees that it can work with real-life limitations.

Answer 2

A concatenative programming language is every bit as capable of running out of memory as a functional programming language.

The fundamental challenge garbage collection addresses is freeing memory that is not, or is not known to be, used in a stack-like fashion. It is most especially useful when there is no clear place in the source code that can be pinpointed as the end of the object's lifetime.

If you simply translate a functional language into a concatenative one with only stack allocation, then you will end up overflowing the stack.

There have definitely been various efforts over the years to reduce the need for garbage collection. One interesting (but very complicated) attempt is the region inference system used in the ML Kit. Unfortunately, that's a bit much for most programmers, including myself, to understand. I believe others have worked on such systems since; I don't know the current state of the art.

The take-away is that some very heavy compiler machinery, along with careful programmer discipline and perhaps special annotations, can sometimes reduce or eliminate the need for garbage collection; no trivial transformation is going to do the trick.