Lambda the Ultimate

Here is the idea: Popular wisdom dictates that functional languages need garbage collection, but is it really true. For example C++ style move semantics seem to solve the problem of returning a closure from a function, you create an object to contain a copy of all the local variables and functions, and then swap the local copy of the handle with the calling functions allocation, so when the function returns it destroys the empty handle from the caller, leaving the caller with the handle to the closure.

On this basis any acyclic datatype can be stored in the heap, but its lifetime managed from the stack handle (this is what RAII is doing in C++ STL).

I guess this is a degenerate case of reference counting, where we limit references to two types, a unique 'owning' reference (lets call it a handle to disambiguate) , that when it goes out of scope releases the memory (its unique and un-copyable so no need to count references), and an 'ephemeral' reference (lets call it a pointer) that is restricted in that it cannot be 'leaked' to a scope more short lived than the scope in which the handle exists. This all sounds a lot like Ada access variables - but note the change from the scope in which the handle was created, to the any scope in which the handle exists, as returning handles by move semantics is possible. This allows a constructor to return a handle into a scope which is also allowed to hold pointers to the object.

It doesn't sound like it really needs anything new, just a combination of Ada's access variable, and the mechanism for converting closures into objects described above.

What potential problems might there be? Could this work, or is there some overlooked flaw?

A real time collector for reconfigurable hardware seems kinda like a nice little 'hardware' implementation.

It is thus quite a tour de force that the authors of the following paper have built a provably correct real-time collec- tor for reconfigurable hardware (field programmable gate arrays). How can this be? It turns out the FPGA setting makes the problem simpler in some ways than is the case with software GC running on stock processors. They can reasonably impose simple uniformity on the memory and its layout; they can exploit single-clock read-modify-write steps; and perhaps most importantly they have, via dual ported memory, com- pletely concurrent memory access. This all leads to one of the cleanest and per- haps most understandable implemen- tations of a concurrent GC that has ever been presented. The other prerequisites for real-time collection also follow eas- ily. It is difficult to find the right word to express the feeling I get seeing such a so- phisticated algorithmic idea reduced to such a straightforward hardware imple- mentation—“Cool!” will have to suffice. (emphasis mine)

(this researcher seems to me (an ignorant neophyte admittedly), to have quite a bit of interesting work on GC, among other interesting things.)

Generational Real-Time Garbage Collection

Abstract. While real-time garbage collection is now available in pro- duction virtual machines, the lack of generational capability means ap- plications with high allocation rates are subject to reduced throughput and high space overheads.

Since frequent allocation is often correlated with a high-level, object- oriented style of programming, this can force builders of real-time sys- tems to compromise on software engineering.

We have developed a fully incremental, real-time generational col- lector based on a tri-partite nursery, which partitions the nursery into regions that are being allocated, collected, and promoted. Nursery col- lections are incremental, and can occur within any phase of a mature collection.

We present the design, mathematical model, and implementation of our collector in IBM’s production Real-time Java virtual machine, and show both analytically and experimentally that the collector achieves real-time bounds comparable to a non-generational Metronome-style col- lector, while cutting memory consumption and total execution times by as much as 44% and 24% respectively.

p.s. i'm less interested in supporting OO everywhere than i am in having kick-ass GCs, i assume that using something more FP with a GC like this would be never less performant anyway.