Closures ― Andreas Zwinkau

The concept of a closure in the context of programming seems to be as confusing as traits. The Wikipedia definition isn't easy to understand:

A closure is a first-class function with free variables that are bound in the lexical environment

That is a nice definition, but it takes a little understanding.

Anonymous functions

First the notion of a first-class function is essential. It means that a function is a thing that can be created, destroyed, assigned and passed around. Consider the following code:

f = function(x) { return x(x) }

The variable f gets a function assigned. Before we dig deeper think about names for a while. What is the name of the function? Is it f? If we assign g = f afterwards, does the same function have two names? What is the name of the function before it gets assigned to f? At this point you should understand the concept of anonymous functions or think about the questions a little more.

That anonymous function takes one argument x. The programming language at hand doesn't require static types, so we don't know anything about x so far, but it is a variable with an assigned value. It could also have an anonymous function assigned.

Judging from the body of the anonymous function the argument x must be a function, because it is called. The body of the function contains strange code. It calls the argument function x and passes x as an argument, too. Now the most difficult question in this article: What happens at the statement f(f)?

Using a closure

After understanding anonymous functions the concept of a closure isn't hard anymore. Consider the accumulator function:

mk_acc = function() {
    sum = 0;
    acc = function(x) {
        sum = sum + x;
        return sum;
    }
    return acc;
}

The mk_acc function generates accumulator functions. An accumulator function takes a number, adds it to sum and returns the sum. The sum variable is a free variable in the acc function, but bound in the (lexical) environment of the generated inner function. It is used in the expression sum + x, before it is declared by an assignment sum =. In contrast x is bound to be the argument of the acc function.

So sum grows with every call to the accumulator function, which means that two function calls with equal arguments to an accumulator return a different result:

a = mk_acc();
print a(2);        # prints 2
print a(2);        # prints 4
print a(2);        # prints 6

Storage of the state

It is clear that an accumulator function holds some internal state, since the sum is stored. Where is that storage located? Consider the case, where two accumulators are generated:

a = mk_acc();
b = mk_acc();
print a(2);        # prints 2
print b(2);        # prints what?

Clearly a "2" will be printed first, but what is the second printed number? Is it "2" or "4"? Actually that depends on the semantics of the programming language. Both scenarios are possible. The inner anonymous function is generated multiple times and all these function may be bound to the same sum or get their own sum variable.

Implementation

Many programmers are familiar with C. In C a function is just a pointer into some code, hence a function pointer may be passed around. There is just no syntax to generate an anonymous function in C (though there is an extension).

I can think of an elaborate trick, to create an anonymous function in C nevertheless. Use LLVM to JIT a function. The getPointerToFunction method returns something like an anonymous function.

For closures with internal state a function needs to be more than a function pointer though. Consider the mk_acc function above. The sum variable is a local variable, hence it lives on the stack. If every acc function has its own sum variable, then an accumulator function consists (at least) of a pointer to code and a copy of sum. If all acc functions share a sum variable instead, the first idea is to include a pointer to the stack address of sum. No, that is a mistake, because after the program returns from mk_acc the stack frame is freed and may be overwritten. Therefore the compiler must create a global variable instead, which stores the value of sum.

Use cases

The classical use case, where closures shine are callbacks as used in event-based systems, like all GUI frameworks I've seen. In C the callback register function usually takes an additional void pointer to transfer some information for the callback. This shows how closures have to be made explicit, if they are not built-in. Java on the other hand got anonymous classes in version 1.1 instead, which can also be closures.

Another use case is applying a function to a bunch of objects. Consider a graph data structure G and the task to find all nodes that hold a value with a given range x to y. With closures the API can be easily designed to allow the terse solution:

filter(range_checker(x,y), G);

The range_checker function is like mk_acc and returns a filter function, which is applied to every node in G and is used by filter to select the right nodes. In C a solution could look like this:

range r;
r.lower = x;
r.upper = y;
filter(&range_checker, G, &r);

Anonymous functions

Using a closure

Storage of the state

Implementation

Use cases

Further reading