14
$\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

$\endgroup$
  • $\begingroup$ The Cat Programming Language looks like an example of a function, stack-based language. $\endgroup$ – Petr Pudlák Sep 11 '16 at 12:30
  • 1
    $\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 Sep 11 '16 at 16:47
  • $\begingroup$ My mistake. Do you know the answer to my question? $\endgroup$ – Nicholas Grasevski Sep 11 '16 at 20:41
  • 5
    $\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 Sep 12 '16 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 Sep 12 '16 at 7:44
16
$\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).

$\endgroup$
  • 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 Sep 12 '16 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 Sep 12 '16 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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