Home » forums » LtU Forum

Garbage Collection as a Lazy Algorithm

Lately I've been thinking of garbage collection in terms of being a lazy algorithm. That is, I see a lot potential similarities between lazy evaluation and garbage collection. One of the main benefits of lazy evaluation is the modularity it provides by allowing finer-grained intermingling of programs (the separation of generation from selection). Garbage collection follows this pattern closely by allowing the allocation of memory anywhere, without having to worry about deallocation. Also, the freeing of unused memory is done dynamically on demand, instead of being determined at compile time. Again, similar to the execution path of a lazy program. And lazy evaluation makes it easier to reason about correctness, but harder to reason about efficiency. Much the same could also be said about GC.

I think the unification of the two concepts could inform both areas. I could see a form of strictness analysis performed on our 'lazy' garbage collector which would produce a region inference algorithm or a compile time garbage collection algorithm. And maybe garbage collection research could help in developing better evaluation strategies. Although I have a harder time seeing it, might a generalization of the idea behind generational GC applied to an evaluation strategy lead to something similar to Optimistic or Eager evaluation? (That is, spend more time on executing younger thunks, etc.)

Are there any papers out there which discuss the lazy aspects of garbage collection?

By Greg Buchholz at 2005-09-15 21:35 | LtU Forum | previous forum topic | next forum topic | other blogs | 7435 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

I see a problem with this

The thunking that is done in a lazy language cannot be dealt with unless that language itself has a garbage collector, to the best of my knowledge. I do believe we (the pl interested community) are at least a year or two away from even seeing use of Dan's work in the a production level langauge implementation effort. Thats the only exploration I know of using a (safe) statically typed language for writing a garbage collector.

[edit: what do you mean by a generalization of generational garbage collectors? As it is, aren't such collectors dependent upon a generally true heuristic for their comparative efficiency?]

By carter at Fri, 2005-09-16 00:28 | login or register to post comments

Yes

As it is, aren't such collectors dependent upon a generally true heuristic for their comparative efficiency?

Yes, but I'd like to see some generally true heuristics applied to lazy evaluation to improve its comparative efficiency (by eliminating common types of space leaks for instance). And thanks for the link to the excellent "Managing Memory with Types" paper.

By Greg Buchholz at Fri, 2005-09-16 16:53 | login or register to post comments

Henry Baker

Henry Baker's Garbage Collection papers are worth reading.

--Shae Erisson - ScannedInAvian.com

By shapr at Sun, 2005-09-18 01:22 | login or register to post comments

Relationship

In a lazy language, there are 2-3 events in every values lifetime: thunk creation (via evaluation), thunk reduction (via forcing) - which may or may not occur, and thunk abandonment (via garbage collection).

By Tim Sweeney at Mon, 2005-09-19 23:23 | login or register to post comments