0

What is the main method for reclaiming the memory in LISP? Does LISP really need garbage collection? Would not reference counts suffice?

I just wanted to know whether reference counts are enough or not for memory management in LISP, since I am not much familiar with LISP language and other functional languages either.

Thanks.

closed as unclear what you're asking by gnat, amon, user22815, GlenH7, Bart van Ingen Schenau Nov 10 '14 at 17:59

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat Nov 10 '14 at 16:50
  • 5
    I am voting for “unclear what you're asking”. The question is perfectly clear, and has been discussed elsewhere ad nauseam. The unclear part is what you already know about GC and the issues around refcounting. Without more context, it feels like there is some deeper question or misunderstanding. Could you please edit the post to show your train of thought? – amon Nov 10 '14 at 17:17
  • A significant subset of Lisp can live well without any GC at all, with nothing but a trivial region analysis. – SK-logic Nov 10 '14 at 18:16
  • 2
    Read the garbage collection handbook; it explains that refcounting is a poor way to do GC... – Basile Starynkevitch Nov 11 '14 at 18:42
  • The word LISP hasn't been capitalized that way for several decades. It doesn't refer to a specific language, but to a family tree of languages which share certain characteristics, many of them subjective. Questions about "LISP" that are about concrete implementation features do not make any sense; we can only ask about the detailed technical requirements which underlie a specific dialect in the Lisp family tree. – Kaz Jan 13 '18 at 2:28
9

Reference counting is basically never sufficient for managing memory due to cycles. If a language has mutation we can essentially create a structure like

  -------------------
  |        |        |
  |  Head  |  Tail  |
  |        |        |
  -------------------
     |  |       |
     |  +-------+
     |
  1 <+

I put way too much effort into this lousy diagram

Now that the head is pointed at the tail the counter for the object will never dip to 0, meaning it'll lie around forever. This is a persistant issue for Perl and is the reason for the contortions with weak_prt in C++.

Also frankly a good GC is orders of magnitude faster than reference counting. Bumping those counters constantly (particularly when you need to ensure thread safety) is actually not free. Clever things with generational/parallel garbage collection can give essentially pause free high performance code!

It's a natural question to wonder why we couldn't just start with malloc and free in Lisp and see where that takes us. In a language with closures, however, using manual memory management is a constant perilous battle. You are constantly in grave danger of closing over something with a slightly different lifetime and having things slowly pear-shaped. This complexity is noticeable in C++ with the fine grained notions of capturing and moving in and out of closures, even this destroys the time honored series of tricks in Lisp for simulating objects and other useful creatures.

TLDR: Garbage collection is actually pretty fast and reference counting is just too naive.

  • 3
    There are ascii drawing tools out there - AsciiDraw, etc. – Dan Pichelman Nov 10 '14 at 17:32
  • 1
    Despite the numerous drawbacks, I actually like refcounting quite a lot. For example, it allows me to use the wonderful RAII pattern. Careful usage of weak references allows me to circumvent most pitfalls, but few object graphs are cyclic in the first place. Also, the performance penalty is overstated once we disallow shared memory between threads. In Perl, the easiest way to accidentally leak memory is a closure over itself: my $f; $f = sub { $f }. Unfortunately, that's a common sight when doing functional programming. – amon Nov 10 '14 at 17:36
  • @DanPichelman This makes me a lot happier than it should :D – jozefg Nov 10 '14 at 17:37
  • 1
    @amon I'm not sure about the performance being overstated, since garbage collection allows for better locality, and you only pay for the objects that are alive when a collection occurs. For memory, I can't see any pros to it unless you're doing something embedded and safety-critical where heap allocation isn't allowed. But scoped lifetime or reference counting often makes sense for external, scarce resources like file handles, sockets, or GPU textures. Those things tend to be used in simple nested scopes. – Doval Nov 10 '14 at 17:53
  • 2
    @amon Pure refcounting is undesirable because of the easy memory leaks. Once you add a cycle GC, however, RAII becomes much less attractive in my mind: Cycles are no longer bugs, so other code with references to your objects would be justified to not deal with cycles of their own, but those cycles keep your objects alive, so prompt object destruction goes down the drain. Also, most optimizations of ref counting break the "prompt destruction" property too (cf. A Unified Theory Of Garbage Collection by David Bacon et al.) – user7043 Nov 10 '14 at 18:07
1

Naive reference counting cannot deal with cyclic data structures, since parts of the data structure will cause other parts to have a reference count higher than zero.

On the trivial end, Lisp (in general and Common Lisp in particular) allows you to create read-time cyclic "lists": #1#=(red green blue . #1#) is a never-ending list. They're even useful, in their right place.

Less obvious, if you have a family tree with each person represented as a node with references to parents and children, you suddenly have a graph that cannot be cleaned up using only reference counting. Is it useful? To some extent, yes. It makes looking up both children and parents from a single node effectively O(1) instead of having one of them being effectively O(1) and the other being effectively O(population) (or, admittedly, you can use weak references).

Even less obvious, updating the reference count must by necessity happen at every time a reference is made or unmade and either requires a Read-Copy-Update or a lock acquisition and release. With a periodic GC policy, this is amortised across the whole interval.

  • 1
    There are weak references available in most refcounting implementations. – user7043 Nov 10 '14 at 18:10
  • But that means you need to have two types of references, where a single type of reference would have sufficed, with a more advanced (and not necessarily any slower) GC. Remember that updating a reference count MUSt be lock-protected, so any "reference or de-reference any other object" is suddenly a lock acquisition, instead of amortised at GC time. – Vatine Nov 11 '14 at 11:58
  • Sure, but that is orthogonal. I only object to implying that refcounting can't handle parent references in trees. – user7043 Nov 11 '14 at 12:10
  • It only can with weak references, which is a higher cognitive load on the programmer. – Vatine Nov 11 '14 at 12:54
0

Environment fragments in Lisp have an undetermined lifetime, most of the LISP implementations need garbage collection to reclaim free run-time store.

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