The Design of Hammer, Part II

The main appeal of first-class functions is that they are ridiculously simple (yes, really) and yet also ridiculously powerful. For proof, one only needs to take a look at the design of the original Lambda Calculus, the very first formalization of the notion of universal computation. Due to their appeal, first-class functions have pretty much become a must-have feature of almost all "new" programming languages. Even the notoriously conservative Java is considering "lambdas" for its next iteration.

Though the idea of first-class functions is pretty simple, their implementation is not. The vast majority of languages that provide them also require some sort of automatic memory management. Those that insist on manual memory management, like C++ or ATS, require the programmer to specify where to allocate the set of captured variables (henceforth called a "closure") and when to deallocate them.

The main difficulty comes from the interaction of lexical scoping and unrestricted mutability. If the free variables of the closure are simply captured as copies, then when one of them is modified the effect will not be observable from its original scope. On the other hand, if they are captured as pointers, then it is unsafe to do anything with them since the originals may have gone out of scope in the time between the closure's construction and its invocation. The mainstream solution is to allocate all variables on the heap and deallocate them if and only if the runtime can prove that they are no longer needed.

Unfortunately, this solution is unacceptable for a systems programming language. The details of automatic memory management are mandated by the language's implementation, which the programmer has no control over. If you're lucky, you'll have one of those cutting-edge pause-less garbage collectors. If not, good luck with writing real-time applications. If you are working on a embedded platform, your machine might not even have enough memory to accommodate the overhead of garbage collection.

Hammer avoids the above problems by assuming that variables are immutable. This allows closures to indiscriminately capture by value, eliminating the need for garbage collection. Imagine a naive implementation:

struct foo {
  size_t size; // = sizeof(struct foo);

  return_t (*function)(struct foo *, parameter_t);
  t0 var0;
  t1 var1;
  ...
};

The programmer can handle a lambda expression like any other literal, so he has complete control over where the closure is stored. To invoke:

...
return_t val = (*foo.function)(&foo, parameter);
...

Simple, isn't it? Immutability by default has other benefits, which will be explained in the next post.