Representing Closures

This came to mind after running into some correct but confusing behaviour with respect to capture by reference. A lot of the complication in compiling closures in, say, an interpreter is making sure that value references can outlive the stack frame in which the value is defined. Usually this is done by using a special node for indirection, where the value is hoisted when it's stack frame is popped.

We can draw some pictures. Before v is popped from the stack:

+------------+
|      v     |<-----------+
+------------+            |
|            |            |
|            |            +--------------+
|            |            |  indirection |
|            |            +--------------+
+------------+                  ^
|  closure   |                  |
+------------+------------------+

After the stack frame for v is removed it is rehomed to the indirection node:

+------------+         +-----------+
|  closure   +-------->|     v     |
+------------+         +-----------+

This requires heap allocation, and usually a garbage collector to clean up the allocated redirection node. This isn't good for freestanding binaries, or higher performance systems.

Capture by reference is confusing. This example in Python illustrates why:

>>> [f() for f in [lambda: i for i in range(0, 10)]]
[9, 9, 9, 9, 9, 9, 9, 9, 9, 9]

What matters is the position of a variable in memory, not its value. It's not clear in the above that i is a single mutating value, and its position is what is captured by the lambda.

This is a particularly weird thing to do by default in languages which have pointers (Go for example). If we want to capture by reference, we can just capture the address.

In a low-level language with pointers, capture by value seems more reasonable and far less confusing. Capture by reference can easily be achieved by capturing a pointer. In a fictional language, where ergonomics have not been considered:

x = 5;

function f(x) {
  return x + 5;        // Capture by value
}

function g(x) {
  p = &x;              // Capture "by reference"
  return x + *p;
}

Proper lifetime management is left to the programmer, possibly enforced by the compiler.

This point of view also has the advantage of an easy and efficient representation, at least where the size of captures are known at compile time. When compiling closures, it's easy to track the items which are captured, and where they are on the stack. Its then easy to make sure these values are copied when the closure is constructed.

So we can represent a closure as a simple value structure on the stack (it's possible that the number of captures and the exact address to call can be removed).

+-------------+
|  capture 1  |
+-------------+
|  capture 2  |
+-------------+
|             |
|             |
+-------------+
|  capture n  |
+-------------+
|  #captures  |
+-------------+
|  jump addr  |
+-------------+

Calling this closure is a normal function call. The compiler knows where the captures are on the stack, and so can locate them easily enough (like a local variable, actually) in the inner function block. Keeping values on the stack keeps access efficient.

These are just some rough thoughts. There are some issues and questions:

• Copying closures around with lots of captures isn't particularly efficient. Sometimes it may be useful to put these on the heap.
• Can we actually get away with not tracking the number of captures a closure makes?
• Can we avoid storing the function address with the captures?