Continuation Closures

Closures in SNAP, much like closures in arc2c, are simply flat arrays of references to Arc objects. Closures in SNAP are also used to represent functions on the Arc side; that is, what Arc thinks is a function, is actually an object of the class Closure. The Closure object also contains a reference to an Executor, which is a scary name for something that executes. (more about Executor in another post)

Closures in SNAP are expected to be immutable: once they've been constructed, their contained values are not supposed to change (there isn't anything that stops you from doing that on the C++ side, other than a nasty comment). On the other hand, continuation closures have a reusable() member function which specifies whether or not the continuation closure is reusable, i.e. whether or not its contents can be modified with new content. Continuation closures are represented by the KClosure class, which is derived from class Closure.

Why KClosure?

Having a separate KClosure class just for continuations is largely an optimization to avoid allocating excessive amounts of closures. A continuation closure is usually just invoked once, at the end of a normal function. Typically, after the continuation itself ends - when it must invoke another function - its closure can be freed.

Of course, this is a garbage-collected system, and a copying one at that. "Freeing" memory involves not copying things, and "not copying" is what you want to do most of the time. The best you can do is to reuse a piece of memory you've already allocated.

So a continuation can freely reuse its closure, because it won't get invoked again (barring a minor case i'll get to later) and we don't expect there to be any live data that still refers to the continuation.

And since the continuation closure is still a continuation closure, we reuse the memory area by constructing any new continuation closures in the same, current continuation closure. So a continuation which finds that it must invoke another, non-continuation function - which would expect a continuation - can reuse its own continuation closure; this allows us to skip allocating for a large number of cases.

Continuation closures have an invariant. A reference continuation closure can only exist on the stack, or as an entry in another continuation closure. Also, continuation closures cannot possibly form anything other than a straight singly-linked list.

So why have a reusable() member function? The problem is a little feature called 'ccc.

'ccc (known in the Scheme world as call-with-current-continuation or call/cc) captures the continuation and returns it all trussed up. This also means that the continuation might be invoked using the captured continuation closure more than once - and our assumption so far has been that the continuation is invoked only once.

This is solved by having 'ccc call the banreuse() member function on the captured continuation closure, which causes reusable() to always return false afterward. This means that the continuation closure cannot be reused, and the VM will actually copy the continuation closure when reuse is requested (a sort of "copy-on-write").

Continuation closures that are not reusable may safely violate the invariant. Also, such continuation closures may now form any directed graph, and can even be a cyclic graph.

(this optimization was inspired by the parrot article refcounting isn't all bad and its followup what c's memory management gets rightish; instead of a full refcount, i use a single bit which means "more than one reference" - basically, that's the bit toggled by banreuse() and queried by reusable() - and like in the followup i use this only for continuation closures. i suggested this in a post on the Arc forum)

<edit>

Follow-up: can it go even faster?

Due to CPS conversion, code generated by the arc2c compiler (around which the SNAP virtual machine is built) tends to allocate a lot of closure objects, especially continuation closures.

As mentioned in the "what c's memory management gets rightish" link above, making use of a stack-like allocator - where continuation closure frames can be allocated and deallocated in last-in-first-out order - would severely decrease garbage collection pressure. In a CPS implementation like SNAP, this means that, barring 'ccc, a continuation that has exited can have its closure deallocated almost immediately.

This could in fact be done in SNAP; any continuation that exits without reusing its closure can specify deallocation of the closure; the deallocator attempts to deallocate the continuation if's the last allocated structure, or leaves it on the stack if not.

This will of course complicate GC somewhat. It also means that we have for each heap two separate allocation areas: one for normal allocation, and one for LIFO structures. Since the call graph is usually structured as a singly-linked list, this will allow even better reuse of closures; in fact, the current strategy of explicitly reusing can probably be replaced with the LIFO structure..

<edit>

Follow-up: LIFO implemented

LIFO allocation-deallocation schemes have been implemented