Alternative implementation of closures in C

So I've been working on a new language for a while and the topic of how to implement closures came up. I have seen closures usually implemented on the heap or with some malloc region of memory. This seems suboptimal so I thought of it some more and came up with the idea of using type unions to store local variables. This way closures could be passed around on the stack normally.

Obviously this has downsides if you hold too many local variables or few large ones. Since this has probably been done before, I would like to ask the community what their experiences have been with alternative closure implementations.

Also to note, specialization of functions is an option that could help reign in the size of the closure struct.

couple suggestions

You might get better results if your request is longer and has more detail. For example, since C doesn't have closures per se, this means you have something in mind, but you didn't provide a pointer or hint at a specific sort of organization you assume. My best guess is you're implementing some language L in C, and the closures are for L rather than C as such.

Some languages address optimization of closures (blocks in Smalltalk) on the heap or a more efficient stack context after performing escape analysis (wikipedia), but I haven't done escape analysis myself since the late 90's. Several folks reading your post might think "escape analysis" in the back of their minds, and wonder whether your question could be refined after taking that topic area into account.

One of the early Smalltalk implementation books — the green book, I think — analyzes pooling of block contexts for efficiency, where these resemble closures, and that sort of discussion might give you ideas. (The original Smalltalk spec tended to define blocks as no longer being valid after their creating contexts exited, which is unlike Scheme style closures that live beyond where a lambda gets evaluated.)

By Rys McCusker at Sun, 2013-12-29 05:15 | login or register to post comments

Here is the C code for the prototypical closure that I wrote

#include <stdio.h>

typedef struct { int x; } g_closure;
typedef struct { char c; } h_closure;

typedef struct {
   void (*f)(void);
   union {
      char _null_closure;
      g_closure _g_closure;
      h_closure _h_closure;
   };
} closure;


int g(void *c, int y) {
   g_closure *cl = (g_closure*)c;
   return cl->x + y;
}
int h(void *c) {
   h_closure *cl = (h_closure*)c;
   return cl->c;
}


int main() {
   g_closure c_g = { .x=3 };
   closure c_c = { .f=(void(*)(void))g, ._g_closure=c_g };
   printf("g() = %d\n", ((int(*)(void*,int))c_c.f)(&c_c._null_closure,4));

   h_closure c_h = { .c='c' };
   closure c_c2 = { .f=(void(*)(void))h, ._h_closure=c_h };
   printf("h() = %c\n", ((int(*)(void*))c_c2.f)(&c_c2._null_closure));
}

By andrew johnson at Sun, 2013-12-29 06:21 | login or register to post comments

Something erased all the code comments.

I think your odds of getting responses went down, so I reply mainly as polite followup. It's unclear to me what you want motivated by this C code example. I understand what it does completely, including syntax, expressions, control flow, and changes to memory at runtime. But I don't know why you want to do that, or how it relates to your original question. A relation to term closure seems tenuous. If the code replaced substring closure with foo in names, it would make just as much sense to me.

I implemented a Scheme-like Lisp once, with expressions capturing environment in closures for lazy evalution in delayed promises, for example. But I have trouble seeing the model of closure you intend, and how it maps to the sort of thing I know. Maybe having said this much, someone else will step in and map it out for others. I'll try to keep out of the way now. I was just trying to get you a helpful response.

By Rys McCusker at Sun, 2013-12-29 07:41 | login or register to post comments

Show-stoppers

This seems related to defunctionalisation techniques. And it shares the same fundamental problem: it only works with whole-program compilation, since you have to know all functions in the program to determine the union type. So no separate compilation. Depending on your goals that may be a show-stopper.

But here is the real show-stopper: this approach cannot handle closing over closures! If you have a closure whose closure environment contains another closure, then your union type would need to recursively contain itself as a substructure, which is impossible.

The space-inefficiency of C-style unions is a serious issue, too, of course. And it's not just that you waste space: if you have at least one larger function, passing closures immediately becomes pretty expensive, since you have to copy the big union all the time.

A somewhat separate problem is that in C-like languages with mutable local variables you also have to be aware that creating closure environments by copying will not correctly handle closing over such variables (unless you heap-allocate them).

By Andreas Rossberg at Sun, 2013-12-29 08:56 | login or register to post comments

Re: Whole-program compilation

I am a big fan of whole-program compilation so this idea maybe was born from that influence. For times when normalization is needed, it is still possible to add a max size and allocate all the closures with that size. Extra arguments could go on the heap.

With regards to closing over closures, I suppose it would be possible to recognize when this happens and just allocate heap for it.

By andrew johnson at Sun, 2013-12-29 16:07 | login or register to post comments

Lambda the Ultimate

User login

Navigation