16
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ The Cat Programming Language looks like an example of a function, stack-based language. $\endgroup$
    – Petr
    Commented Sep 11, 2016 at 12:30
  • 2
    $\begingroup$ 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 $\endgroup$
    – Andrej Bauer
    Commented Sep 11, 2016 at 16:47
  • 1
    $\begingroup$ My mistake. Do you know the answer to my question? $\endgroup$
    – Nicholas Grasevski
    Commented Sep 11, 2016 at 20:41
  • 9
    $\begingroup$ 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). $\endgroup$
    – cody
    Commented Sep 12, 2016 at 0:09
  • 2
    $\begingroup$ 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. $\endgroup$
    – Martin Berger
    Commented Sep 12, 2016 at 7:44

1 Answer 1

Reset to default
22
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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? $\endgroup$
    – Andreas Rossberg
    Commented Sep 12, 2016 at 17:53
  • $\begingroup$ @andreasrossberg: I thought about mentioning that, but left it out since you can use the y combinator for recursion. $\endgroup$
    – Neel Krishnaswami
    Commented Sep 12, 2016 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.