Jump to content

Closure (computer programming)

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Pi Delport (talk | contribs) at 20:18, 13 June 2007 (SICP is great, but there's no reason to single it out in this way). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer science, a closure is a semantic concept referring to a function paired with an environment. When called, the function can reference elements of the environment required for the function’s evaluation. Typically, a closure occurs when one function appears entirely within the body of another, and the inner function refers to local variables of the outer function. At runtime, when the outer function executes, a closure is formed, consisting of the inner function’s code and references to any variables of the outer function required by the closure. The exact nature of a closure's environment and the relation between this environment and its associated function will vary from language to language and depend upon both the features of the language and how closures were implemented.

The distinguishing feature of closures is the ability to associate an "intermediate" set of data with a function where the data set is distinct from both the global data of the program and data local to the function itself. As a consequence closures can be used to hide state, implement higher-order functions and defer evaluation.

The concept of closures was developed in the 60’s and was first fully implemented as a language feature in the programming language Scheme. Since then, some form of closures is a feature common to many languages.

Examples

Closures typically appear in languages in which functions are first-class values—in other words, such languages allow functions to be passed as arguments, returned from function calls, bound to variable names, etc., just like simpler types such as strings and integers. For example, consider the following function written in Scheme: 

 ; Return a list of all books with at least THRESHOLD copies sold.
 (define (best-selling-books threshold)
   (filter 
     (lambda (book) (>= (book-sales book) threshold))
     book-list))

In this example, the lambda expression (lambda (book) (>= (book-sales book) threshold)) appears within the function best-selling-books. When the lambda expression is evaluated, Scheme creates a closure consisting of the code for the lambda and a reference to the threshold variable, which the lambda uses.

The closure is then passed to the filter function, which calls it repeatedly to determine which books are to be added to the result list and which are to be discarded. Because the closure itself has a reference to threshold, it can use that variable each time filter calls it. The function filter itself might be defined in a completely separate file.

Here is the same example rewritten in ECMAScript, another popular language with support for closures: 

 // Return a list of all books with at least 'threshold' copies sold.
 function bestSellingBooks(threshold) {
   return bookList.filter(
       function(book) { return book.sales >= threshold; }
     );
 }

The function keyword is used here instead of lambda, and Array.filter method instead of a global filter function, but otherwise the structure and the effect of the code is the same.

A function may create a closure and return it. The following example is a function that returns a function.

In Scheme: 

 ; Return a function that approximates the derivative of f
 ; using an interval of dx, which should be appropriately small.
 (define (derivative f dx)
   (lambda (x) (/ (- (f (+ x dx)) (f x)) dx)))

In ECMAScript: 

 // Return a function that approximates the derivative of f
 // using an interval of dx, which should be appropriately small.
 function derivative(f, dx) {
   return function(x) {
     return (f(x + dx) - f(x)) / dx;
   }
 }

Because the closure in this case outlives the scope of the function that creates it, the variables f and dx live on after the function derivative returns. In languages without closures, the lifetime of a local variable coincides with the execution of the scope where that variable is declared. In languages with closures, variables must continue to exist as long as any existing closures have references to them. This is most commonly implemented using some form of garbage collection.

Uses of closures

Closures have many uses:

  • Designers of software libraries can allow users to customize behavior by passing closures as arguments to important functions. For example, a function that sorts values can accept a closure argument that compares the values to be sorted according to a user-defined criterion.
  • Because closures delay evaluation—i.e., they do not "do" anything until they are called—they can be used to define control structures. For example, all Smalltalk's standard control structures, including branches (if/then/else) and loops (while and for), are defined using objects whose methods accept closures. Users can easily define their own control structures as well.
  • Multiple functions can be produced which close over the same environment, enabling them to communicate privately by altering that environment.
  • Closures can be used to implement object systems [1], and may in fact be better alternatives to objects [2].

Note: Some speakers call any data structure that binds a lexical environment a closure, but the term usually refers specifically to functions.

Differences in semantics

As different languages do not always have a common definition of the lexical environment, their definitions of closure may vary as well. The commonly held minimalist definition of the lexical environment defines it as a set of all bindings of variables in the scope, and that is also what closures in any language have to capture. It should be noted though that the meaning of a variable binding also differs. In imperative languages, variables bind to locations in memory, which can in turn store values. The binding can never change, but the value in the bound location can. In such languages, since closure captures the binding, any operation on the variable, whether done from the closure or not, is performed on the same memory location. Here is an example illustrating the concept in ECMAScript, which is one such language: 

var f, g;
function foo()
{
  var x = 0;
  f = function() { ++x; };
  g = function() { --x; };
  x = 1;
  print(f()); // "2"
}
foo();
g(); // "1"
f(); // "2"

Note how function foo, as well as both closures, use the same memory location bound to local variable x together.

On the other hand, many functional languages, such as ML, bind variables directly to values. In this case, since there is no way to change the value of the variable once it is bound, there is no need to share the state between closures - they just use the same values.

Yet another subset, lazy functional languages such as Haskell, bind variables to a result of a computation in the future. Consider this example in Haskell: 

 foo x y = let r = x / y
           in (\z -> z + r)
 f = foo 1 0
 main = do putStr (show (f 123))

The binding of r captured by the closure defined within function foo is to the computation (x / y) - which in this case results in division by zero. However, since it is the computation that is captured, and not the value, the error only manifests itself when the closure is invoked, and actually attempts to use the captured binding.

Yet more differences manifest themselves as other lexically scoped constructs, such as return, break and continue statements in C-like languages. Such constructs can in general be considered to be accessible lexical bindings to an escape continuation (in case of break and continue, such interpretation requires looping constructs to be considered in terms of recursive function calls). In some languages, such as ECMAScript, this binding is implicitly reintroduced in every closure, thus hiding the lexical binding from the enclosing scope - thus, a return statement from within the closure transfers control to the code which called it. In Smalltalk, however, only top-level definitions introduce such binding, and closures capture it rather than rebinding it. The following examples in ECMAScript and Smalltalk highlight the difference: 

 "Smalltalk"
 foo
   | xs |
   xs := #(1 2 3 4).
   xs do: [:x | ^x].
   ^0
 bar
   Transcript show: (self foo) "prints 1"

 // ECMAScript
 function foo() {
   var xs = new Array(1, 2, 3, 4);
   xs.forEach(function(x) { return x; });
   return 0;
 }
 print(foo()); // prints 0

Both code snippets seem to do the same thing at the first glance, bearing in mind that ^ in Smalltalk is analogous to ECMAScript return. The difference is that in ECMAScript example, return will leave the closure, but not function foo, whereas in Smalltalk example, ^ will return from method foo, and not just from the closure. The latter allows more expressiveness - in Smalltalk, do: is defined as a plain method, and there is nothing special about it, while ECMAScript has to introduce a special language construct, foreach, to express the same thing. On the other hand, there is an issue of captured continuation outliving the scope in which it was created. Consider: 

 foo
   ^[ x: | ^x ]
 bar
   | f |
   f := self foo.
   f value: 123 "error!"

When block returned by method foo is invoked, it attempts to return a value from foo. Since the call to foo has already completed, this operation results in an error.

Some languages, such as Ruby, allow the programmer to choose the way he wants return to be captured. An example in Ruby: 

 def foo
   f = Proc.new { return "return from foo from inside proc" }
   f.call # control leaves foo here
   return "return from foo"
 end
 
 def bar
   f = lambda { return "return from lambda" }
   f.call # control does not leave bar here
   return "return from bar"
 end
 
 puts foo # prints "return from foo from inside proc"
 puts bar # prints "return from bar"

Both Proc.new and lambda in this example are ways to create a closure, but semantics of the closures thus created are different with respect to the return statement.

Closure-like constructs in other languages

In C, libraries that support callbacks sometimes allow a callback to be registered using two values: a function pointer and a separate void* pointer to arbitrary data of the user's choice. Each time the library executes the callback function, it passes in the data pointer. This allows the callback to maintain state and to refer to information captured at the time it was registered. The idiom is similar to closures in functionality, but not in syntax.

Several object-oriented techniques and language features simulate some features of closures. For example:

Eiffel

Eiffel includes inline agents defining closures. An inline agent is an object representing a routine, defined by giving the code of the routine in line. For example, in 

OK_button.click_event.subscribe(
    agent(x, y: INTEGER) do
        country := map.country_at_coordinates(x, y)
        country.display
    end
)

the argument to `subscribe' is an agent, representing a procedure with two arguments; the procedure finds the country at the corresponding coordinates and displays it. The whole agent is `subscribed' to the event type `click_event' for a certain button, so that whenever an instance of the event type occurs on that button — because a user has clicked the button — the procedure will be executed with the mouse coordinates being passed as arguments for x and y.

The main limitation of Eiffel agents, which distinguishes them from true closures, is that they cannot reference local variables from enclosing scope. Only Current (a reference to current object, analogous to this in Java), its features, and arguments of the agent itself can be accessed from within the agent body.

C++

C++ allows defining function objects by overloading operator(). These objects behave somewhat like functions in a functional programming language. They may be created at runtime and may contain state, but they do not implicitly capture local variables as closures do. Two proposals to introduce C++ language support for closures (both proposals call them lambda functions) are being considered by the C++ Standards Committee [3], [4]. The main difference between these proposals is that one stores a copy of all the local variables in a closure by default, and another stores references to original variables. Both provide functionality to override the default behaviour. If some form of these proposals is accepted, one would be able to write 

 void foo(string myname) {
   typedef vector<string> names;
   int y;
   names n;
   // ...
   names::iterator i =
     find_if(n.begin(), n.end(), <>(const string& s){return s != myname && s.size() > y;});
   // i is now either n.end() or points to the first string in n
   // which is not equal to  myname and which length is greater than y
 }

Java

Java allows defining "anonymous classes" inside a method; an anonymous class may refer to names in lexically enclosing classes, or final (i.e., read-only) variables in the lexically enclosing method, as long as they are not shadowed by members of the anonymous class. 

 class CalculationWindow extends JFrame {
     private JButton btnSave;
     ...
 
     public final void calculateInSeparateThread(final URI uri) {
         // The expression "new Runnable() { ... }" is an anonymous class.
         Runnable runner = new Runnable() {
                 void run() {
                     // It can access final local variables:
                     calculate(uri);
                     // It can access private fields of the enclosing class:
                     // Always update the Graphic components into the Swing Thread
                     SwingUtilities.invokeLater(new Runnable() {
                          public void run() {
                              btnSave.setEnabled(true);
                          }
                     });                   
                 }
             };
         new Thread(runner).start();
     }
 }

Note that some features of closures can be emulated by using a final reference to a single-element array. The inner class will not be able to change the value of the reference itself, but it will be able to change the value of the element in the array referenced. This technique is not limited to Java, and will work in other languages with similar restrictions, e.g. Python.

A language extension providing fully featured closures for Java is under consideration for Java SE 7. [5]

Implementation and theory

Closures are typically implemented with a special data structure that contains a pointer to the function code, plus a representation of the function's lexical environment (e.g., the set of available variables and their values) at the time when the function was created.

A language implementation cannot easily support full closures if its run-time memory model allocates all local variables on a linear stack. In such languages, a function's local variables are deallocated when the function returns. However, a closure requires that the free variables it references survive the enclosing function's execution. Therefore those variables must be allocated so that they persist until no longer needed. This explains why typically languages that natively support closures use garbage collection.

A typical modern Scheme implementation allocates local variables that might be used by closures dynamically and stores all other local variables on the stack.

Closures are closely related to Actors in the Actor model of concurrent computation where the values in the function's lexical environment are called acquaintances. An important issue for closures in concurrent programming languages is whether the variables in a closure can be updated and if so how these updates can be synchronized. Actors provide one solution (Will Clinger 1981).

See also

Notes

References

Retrieved from "https://wiki.riteme.site/w/index.php?title=Closure_(computer_programming)&oldid=137977730"