How to implement closures without gc?

Question

I'm designing a language. First, I want to decide what code to generate. The language will have lexical closures and prototype based inheritance similar to javascript. But I'm not a fan of gc and try to avoid as much as possible. So the question: Is there an elegant way to implement closures without resorting to allocate the stack frame on the heap and leave it to garbage collector?

My first thoughts:

1. Use reference counting and garbage collect the cycles (I don't really like this)
2. Use spaghetti stack (looks very inefficient)
3. Limit forming of closures to some contexts such a way that, I can get away with a return address stack and a locals' stack.

I won't use a high level language or follow any call conventions, so I can smash the stack as much as I like.

(Edit: I know reference counting is a form of garbage collection but I am using gc in its more common meaning)

Answer 1

This would be a better question if you can explain what you're trying to avoid by not using GC. As I'm sure you're aware, most languages that provide lexical closures allocate them on the heap and allow them to retain references to variable bindings in the activation record that created them.

The only alternative to that approach that I'm aware of is what gcc uses for nested functions: create a trampoline for the function and allocate it on the stack. But as the gcc manual says:

If you try to call the nested function through its address after the containing function has exited, all hell will break loose. If you try to call it after a containing scope level has exited, and if it refers to some of the variables that are no longer in scope, you may be lucky, but it's not wise to take the risk. If, however, the nested function does not refer to anything that has gone out of scope, you should be safe.

Short version is, you have three main choices:

• allocate closures on the stack, and don't allow their use after their containing function exits.
• allocate closures on the heap, and use garbage collection of some kind.
• do original research, maybe starting from the region stuff that ML, Cyclone, etc. have.

Answer 2

This thread might help, although some of the answers here reflect answers there already.

One poster makes a good point:

It seems that you want garbage collection for closures "in the absence of true garbage collection". Note that closures can be used to implement cons cells. So your question seem to be about garbage collection "in the absence of true garbage collection" -- there is rich related literature. Restricting problem to closures does not really change it.

So the answer is: no, there is no elegant way to have closures and no real GC. The best you can do is some hacking to restrict your closures to a particular type of closure. All this is needless if you have a proper GC.

So, my question reflects some of the other ones here - why do you not want to implement GC? A simple mark+sweep or stop+copy takes about 2-300 lines of (Scheme) code, and isn't really that bad in terms of programming effort. In terms of making your programs slower:

1. You can implement a more complex GC which has better performance.
2. Just think of all the memory leaks programs in your language won't suffer from.
3. Coding with a GC available is a blessing. (Think C#, Java, Python, Perl, etc... vs. C++ or C).

Answer 3

I understand that I'm very late, but I stumbled upon this question by accident.

I believe that full support of closures indeed requires GC, but in some special cases stack allocation is safe. Determining these special cases requires some escape analysis. I suggest that you take a look at the BitC language papers, such as Closure Implementation in BitC. (Although I doubt whether the papers reflect the current plans.) The designers of BitC had the same problem you do. They decided to implement a special non-collecting mode for the compiler, which denies all closures that might escape. If turned on, it will restrict the language significantly. However, the feature is not implemented yet.

I'd advise you to use a collector - it's the most elegant way. You should also consider that a well-built garbage collector allocates memory faster than malloc does. The BitC folks really do value performance and they still think that GC is fine even for the most parts of their operating system, Coyotos. You can migitate the downsides by simple means:

• create only a minimal amount of garbage
• let the programmer control the collector
• optimize stack/heap use by escape analysis
• use an incremental or concurrent collector
• if somehow possible, divide the heap like Erlang does

Many fear garbage collectors because of their experiences with Java. Java has a fantastic collector, but applications written in Java have performance problems because of the sheer amount of garbage generated. In addition, a bloated runtime and fancy JIT compilation is not really a good idea for desktop applications because of the longer startup and response times.

Answer 4

Use reference counting and garbage collect the cycles (I don't really like this)

It's possible to design your language so there are no cycles: if you can only make new objects and not mutate old ones, and if making an object can't make a cycle, then cycles never appear. Erlang works essentially this way, though in practice it does use GC.

Answer 5

The C++ 0x spec defines lambdas without garbage collection. In short, the spec allows non-deterministic behavior in cases where the lambda closure contains references which are no longer valid. For example (pseudo-syntax):

(int)=>int create_lambda(int a)
{
    return { (int x) => x + a }
}

create_lambda(5)(4)    // undefined result

The lambda in this example refers to a variable (a) which is allocated on the stack. However, that stack frame has been popped and is not necessarily available once the function returns. In this case, it would probably work and return 9 as a result (assuming sane compiler semantics), but there is no way to guarantee it.

If you are avoiding garbage collection, then I'm assuming that you also allow explicit heap vs. stack allocation and (probably) pointers. If that is the case, then you can do like C++ and just assume that developers using your language will be smart enough to spot the problem cases with lambdas and copy to the heap explicitly (just like you would if you were returning a value synthesized within a function).

Answer 6

If you have the machinery for a precise copying GC, you could allocate on the stack initially and copy to the heap and update pointers if you discover at exit that a pointer to this stack frame has escaped. That way you only pay if you actually do capture a closure that includes this stack frame. Whether this helps or hurts depends on how often you use closures and how much they capture.

You might also look into C++0x's approach (N1968), though as one might expect from C++ it consists of counting on the programmer to specify what gets copied and what gets referenced, and if you get it wrong you just get invalid accesses.

Answer 7

So the question: Is there an elegant way to implement closures without resorting to allocate the stack frame on the heap and leave it to garbage collector?

GC is the only solution for the general case.

Answer 8

You could work with the assumption that all closures will be called eventually and exactly one time. Now, when the closure is called you can do the cleanup at the closure return.

How do you plan on dealing with returning objects? They have to be cleaned up at some point, which is the exact same problem with closures.

Answer 9

Or just don't do GC at all. There can be situations where it's better to just forget the memory leak and let the process clean up after it when it's done.

Depending on your qualms about GC, you might be afraid of the periodic GC sweeps. In this case you could do a selective GC when an item falls out of scope or the pointer changes. I'm not sure how expensive this would be though.

@Allen

What good is a closure if you can't use them when the containing function exits? From what I understand that's the whole point of closures.

Answer 10

Better late than never?

You might find this interesting: Differential Execution.

It's a little-known control stucture, and its primary use is in programming user interfaces, including ones that can change dynamically while in use. It is a significant alternative to the Model-View-Controller paradigm.

I mention it because one might think that such code would rely heavily on closures and garbage-collection, but a side effect of the control structure is that it eliminates both of those, at least in the UI code.

Answer 11

Create multiple stacks?

Answer 12

I guess if the process is very short, which means it cannot use much memory, then GC is unnecessary. The situation is analogous to worrying about stack overflow. Don't nest too deeply, and you cannot overflow; don't run too long, and you cannot need the GC. Cleaning up becomes a matter of simply reclaiming the large region that you pre-allocated. Even a longer process can be divided into smaller processes that have their own heaps pre-allocated. This would work well with event handlers, for example. It does not work well, if you are writing compiler; in that case, a GC is surely not much of a handicap.

Answer 13

I've read that the last versions of ML use GC only sparingly