17
$\begingroup$

In programming languages, closures are a popular and often desired feature. Wikipedia says (emphasis mine):

In computer science, a closure (...) is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its immediate lexical scope.

So a closure is essentially a (anonymous?) function value which can use variables outside of its own scope. In my experience, this means it can access variables that are in scope at its definition point.

In practice, the concept seems to be diverging, though, at least outside of functional programming. Different languages implement different semantics, there even seem to be wars of opinons on. Many programmers do not seem to know what closures are, viewing them as little more than anonymous functions.

Also, there seem to exist major hurdles when implementing closures. Most notable, Java 7 was supposed to include them but the feature was pushed back to a future release.

Why are closures so hard (to understand and) to realise? This is too broad and vague a question, so let me focus it more with these interconnected questions:

  • Are there problems with expressing closures in common semantic formalisms (small-step, big-step, ...)?
  • Are existing type systems not suited for closures and can not be extended easily?
  • Is it problematic to bring closures in line with a traditional, stack-based procedure translation?

Note that the question relates mostly to procedural, object-oriented and scripting languages in general. As far as I know, functional languages do not have any problems.

$\endgroup$
  • $\begingroup$ Good question. Closures have been implemented in Scala, and Martin Odersky wrote the Java 1.5 compiler, so it's not clear why they are not in Java 7. C# has them. (I'll try to write a better answer later.) $\endgroup$ – Dave Clarke Mar 12 '12 at 8:08
  • 4
    $\begingroup$ Impure functional languages like Lisp and ML accommodate closures just fine, so there can't be an intrinsic semantic reason for them to be problematic. $\endgroup$ – Gilles Mar 12 '12 at 8:19
  • $\begingroup$ I included the item because I have been struggling to imagine what a small-step semantic might look like for closures. It may very well be that closures in themselves are not a problem but including them in a language that is not designed with them in mind is hard. $\endgroup$ – Raphael Mar 12 '12 at 8:21
  • 1
    $\begingroup$ Take a look at pdfs.semanticscholar.org/73a2/… - Lua authors made it very clever way and discuss general problems of implementing closures as well $\endgroup$ – Bulat Jun 30 '18 at 11:21
10
$\begingroup$

May I direct you to the Funarg problem wikipedia page? At least this is how the compiler people used to reference the closure implementing problem.

So a closure is essentially a (anonymous?) function value which can use variables outside of its own scope. In my experience, this means it can access variables that are in scope at its definition point.

While this definition makes sense, it does not help describe the problem of implementing first-class functions in a traditional runtime-stack based language. When it comes to implementation issues, first class functions can be roughly divided into two classes:

  • Local variables in the functions are never used after the function returns.
  • Local variables can be used after the function returns.

The first case (downwards funargs) is not that hard to implement and can be found on even the older procedural languages, like Algol, C and Pascal. C kind of skirts the issue, since it does not allow nested functions but Algol and Pascal do the necessary bookkeeping to allow inner functions to reference the stack variables of the outer function.

The second case (upwards funargs), on the other hand, requires activation records to be saved outside the stack, in the heap. This means that it is very easy to leak memory resources unless the language runtime includes a garbage collector. While almost everything is garbage collected today, requiring one is still a significant design decision and was even more so some time ago.


As for the particular example of Java, if I remember correctly, the main issue was not actually being able to implement closures, but how to introduce them to the language in a way that was not redundant with existing features (like anonymous inner classes) and that did not clash with existing features (like checked exceptions - a problem that is not trivia l to solve and that most people don't think of at first).

I can also think of other things that make first class functions less trivial to implement, such as deciding what to do with "magical" variables such as this, self or super and how to interact with existing control flow operators, such as break and return (do we want to allow for non-local returns or not?). But in the end, the recent popularity of first-class functions seems to indicate that languages that don't have them mostly do so for historical reasons or due to some significant design decision early on.

$\endgroup$
  • 1
    $\begingroup$ Do you know of any languages which distinguish the upward- and downward cases? In .NET languages, a generic method which expected to receive a downward-only function could receive a structure of the generic type along with a delegate that would receive such a structure as a byref (in C#, a "ref parameter"). If caller encapsulated all variables of interest in the structure, the delegate could be fully static, avoiding any need for a heap allocation. Compilers don't offer any nice syntax help for such constructs, but the Framework could support them. $\endgroup$ – supercat Jan 30 '14 at 18:07
  • 2
    $\begingroup$ @supercat: Rust has multiple closure types that let you enforce at compile time if an inner function will need to use the heap. However, this doesn't mean an implementation can't try to avoid heap allocations without forcing you to care about all those extra types. A compiler can try to infer the function lifetimes or it can use runtime checks in order to lazily save variables to the heap only when strictly needed (check out the "lexical scope" section of the Evolution of Lua paper for details) $\endgroup$ – hugomg Jan 30 '14 at 19:38
5
$\begingroup$

We can look at how closures are implemented in C#. The scale of the transformations the C# compiler performs makes it clear that their way of implementing closures is quite a lot of work. There may be easier ways to implement closures, but I'd think the C# compiler team would be aware of this.

Consider the following pseudo-C# (I cut out a bit of C# specific stuff):

int x = 1;
function f = function() { x++; };
for (int i = 1; i < 10; i++) {
    f();
}
print x; // Should print 9

The compiler transforms this into something like this:

class FunctionStuff {
   int x;
   void theFunction() {
       x++;
   }
}

FunctionStuff theClosureObject = new FunctionStuff();
theClosureObject.x = 1;
for (int i = 1; i < 10; i++) {
    theClosureObject.theFunction();
}
print theClosureObject.x; // Should print 9

(in reality, the variable f will still be created, where f is a 'delegate' (= function pointer), but this delegate is still associated with the theClosureObject object - I left this part out for clarity for those that aren't familiar with C#)

This transformation is quite massive and tricky: consider closures inside closures and the interplay of closures with the rest of the C# language features. I can imagine that the feature was pushed back for Java, as Java 7 already has quite a lot of new features.

$\endgroup$
  • $\begingroup$ I can see where this is going; having multiple closures and the main scope access the same variable is going to be messy. $\endgroup$ – Raphael Mar 12 '12 at 15:04
  • $\begingroup$ To be honest, this is more due to using the existing OO framework for implementing closures then any real problem with them. Other languages just allocate the variables in a separate, method-less, structure and then let multiple closures share it if they want to. $\endgroup$ – hugomg Mar 12 '12 at 15:08
  • $\begingroup$ @Raphael: how do you feel about closures inside closures? Hang on, let me add that in. $\endgroup$ – Alex ten Brink Mar 12 '12 at 15:08
5
$\begingroup$

To answer part of your question. The formalism described by Morrisett and Harper covers big- and small-step semantics of higher-order polymorphic languages containing closures. There are papers before these providing the kinds of semantics you are looking for. Look, for example, at the SECD machine. Adding mutable references or mutable locals into these semantics is straightforward. I don't see that there are any technical problems in providing such semantics.

$\endgroup$
  • $\begingroup$ Thank you for the reference! It does not seem to make for light reading, but that is probably to be expected from a semantics paper. $\endgroup$ – Raphael Mar 14 '12 at 6:34
  • 1
    $\begingroup$ @Raphael: There are probably simpler ones around. I'll try to find something and get back to you. In any case, Figure 8 has the semantics you are looking for. $\endgroup$ – Dave Clarke Mar 14 '12 at 6:35
  • $\begingroup$ Maybe you can give a rough overview resp. the central ideas in your answer? $\endgroup$ – Raphael Mar 14 '12 at 7:17
  • 2
    $\begingroup$ @Raphael. Perhaps I could refer you to my lecture notes I use for a programming languages course, which gives you a quick introduction. Please look up handouts 8 and 9. $\endgroup$ – Uday Reddy May 28 '12 at 0:01
  • 1
    $\begingroup$ That link appears either dead or behind invisible authentication. (cs.cmu.edu/afs/cs/user/rwh/public/www/home/papers/gcpoly/tr.pdf). I get 403 forbidden. $\endgroup$ – Ben Fletcher Jun 7 '18 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.