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).