Content deleted Content added
Citation bot (talk | contribs) Add: pages. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_webform 2470/3850 |
m →External links: HTTP to HTTPS for Blogspot |
||
| (44 intermediate revisions by 27 users not shown) | |||
Line 1:
{{Short description|Technique for creating lexically scoped first class functions}}
{{
{{
{{Use dmy dates|date=August 2020}}
In [[programming language]]s, a '''closure''', also '''lexical closure''' or '''function closure''', is a technique for implementing [[lexically scoped]] [[name binding]] in a language with [[first-class function]]s. [[Operational semantics|Operationally]], a closure is a [[
== History and etymology ==
The concept of closures was developed in the 1960s for the mechanical evaluation of expressions in the [[λ-calculus]] and was first fully implemented in 1970 as a language feature in the [[
[[Peter
Sussman and [[Harold Abelson|Abelson]] also use the term ''closure'' in the 1980s with a second, unrelated meaning: the property of an operator that adds data to a [[data structure]] to also be able to add nested data structures. This
== Anonymous functions ==
Line 40:
assert h(1)(5) == 6 # h(1) is the closure.
</syntaxhighlight>
the values of <code>a</code> and <code>b</code> are closures, in both cases produced by returning a [[nested function]] with a free variable from the enclosing function, so that the free variable binds to the value of parameter <code>x</code> of the enclosing function. The closures in <code>a</code> and <code>b</code> are functionally identical. The only difference in implementation is that in the first case we used a nested function with a name, <code>g</code>, while in the second case we used an anonymous nested function (using the Python keyword <code>lambda</code> for creating an anonymous function). The original name, if any, used in defining them is irrelevant.
A closure is a value like any other value. It does not need to be assigned to a variable and can instead be used directly, as shown in the last two lines of the example. This usage may be deemed an "anonymous closure".
Line 46:
The nested function definitions are not themselves closures: they have a free variable which is not yet bound. Only once the enclosing function is evaluated with a value for the parameter is the free variable of the nested function bound, creating a closure, which is then returned from the enclosing function.
Lastly, a closure is only distinct from a function with free variables when outside of the scope of the non-local variables, otherwise the defining environment and the execution environment coincide and there is nothing to distinguish these (static and dynamic binding cannot be distinguished because the names resolve to the same values). For example, in the
<syntaxhighlight lang="python">
x = 1
Line 59:
This is most often achieved by a function return, since the function must be defined within the scope of the non-local variables, in which case typically its own scope will be smaller.
This can also be achieved by [[variable shadowing]] (which reduces the scope of the [[non-local variable]]), though this is less common in practice, as it is less useful and shadowing is discouraged. In this example <code>f</code> can be seen to be a closure because <code>x</code> in the body of <code>f</code> is bound to the <code>x</code> in the global namespace, not the <code>x</code> local to <code>g</code>:
<syntaxhighlight lang="python">
x = 0
Line 74:
== Applications ==
The use of closures is associated with languages where functions are [[first-class object]]s, in which functions can be returned as results from [[higher-order function]]s, or passed as arguments to other function calls; if functions with free variables are first-class, then returning one creates a closure. This includes [[functional programming
[[Python (programming language)|Python]] and▼
Closures can also be used in a [[continuation-passing style]] to [[
=== First-class functions ===
Line 96 ⟶ 92:
In this example, the [[Lambda (programming)|lambda expression]] <code>(lambda (book) (>= (book-sales book) threshold))</code> appears within the function <code>best-selling-books</code>. When the lambda expression is evaluated, Scheme creates a closure consisting of the code for the lambda expression and a reference to the <code>threshold</code> variable, which is a [[free variable]] inside the lambda expression.
The closure is then passed to the <code>filter</code> 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
Here is the same example rewritten in [[JavaScript]], another popular language with support for closures:
Line 102 ⟶ 98:
// Return a list of all books with at least 'threshold' copies sold.
function bestSellingBooks(threshold) {
return bookList.filter(book => book.sales >= threshold);
);▼
}
</syntaxhighlight>
The arrow operator <code>
A function may create a closure and return it, as in
<syntaxhighlight lang="javascript">
Line 116 ⟶ 110:
// using an interval of dx, which should be appropriately small.
function derivative(f, dx) {
return
}
</syntaxhighlight>
Line 125 ⟶ 117:
=== State representation ===
A closure can be used to associate a function with a set of "[[Class (computer programming)|private]]" variables, which persist over several invocations of the function. The [[scope (programming)|scope]] of the variable encompasses only the closed-over function, so it cannot be accessed from other program code. These are analogous to [[private variable]]s in [[object-oriented programming]], and in fact closures are
In stateful languages, closures can thus be used to implement paradigms for state representation and [[information hiding]], since the closure's upvalues (its closed-over variables) are of indefinite [[variable (programming)#Scope and extent|extent]], so a value established in one invocation remains available in the next. Closures used in this way no longer have [[referential transparency]], and are thus no longer [[pure function]]s; nevertheless, they are commonly used in impure functional languages such as [[Scheme (programming language)|Scheme]].
Line 148 ⟶ 140:
</syntaxhighlight>
* Closures can be used to implement [[Object-oriented programming|object]] systems.<ref>{{cite web |
Note: Some speakers call any data structure that binds a [[Scope (programming)#Lexical scoping|lexical]] environment a closure, but the term usually refers specifically to functions.
== Implementation and theory ==
Closures are typically implemented with a special [[data structure]] that contains a [[function pointer|pointer to the function code]], plus a representation of the function's lexical environment (i.e., the set of available variables) at the time when the closure was created. The referencing environment [[name binding|binds]] the non-local names to the corresponding variables in the lexical environment at the time the closure is created, additionally extending their lifetime to at least as long as the lifetime of the closure
A language implementation cannot easily support full closures if its run-time memory model allocates all [[automatic variable]]s on a linear [[Stack-based memory allocation|stack]]. In such languages, a function's automatic 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, typically via [[heap allocation]], rather than on the stack, and their lifetime must be managed so they survive until all closures referencing them are no longer in use.
This explains why, typically, languages that natively support closures also use [[Garbage collection (computer science)|garbage collection]]. The alternatives are manual memory management of non-local variables (explicitly allocating on the heap and freeing when done), or, if using stack allocation, for the language to accept that certain use cases will lead to [[undefined behaviour]], due to [[dangling pointer]]s to freed automatic variables, as in lambda expressions in C++11<ref>''[http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2550.pdf Lambda Expressions and Closures]'' C++ Standards Committee. 29 February 2008.</ref> or nested functions in GNU C.<ref>{{cite web |work=GCC Manual
In strict functional languages with immutable data (''e.g.'' [[Erlang (programming language)|Erlang]]), it is very easy to implement automatic memory management (garbage collection), as there are no possible cycles in variables' references. For example, in Erlang, all arguments and variables are allocated on the heap, but references to them are additionally stored on the stack. After a function returns, references are still valid. Heap cleaning is done by incremental garbage collector.
Line 174 ⟶ 166:
As different languages do not always have a common definition of the lexical environment, their definitions of closure may vary also. The commonly held minimalist definition of the lexical environment defines it as a set of all [[Name binding|bindings of variables]] in the scope, and that is also what closures in any language have to capture. However the meaning of a [[Variable (programming)|variable]] binding also differs. In imperative languages, variables bind to relative locations in memory that can store values. Although the relative ___location of a binding does not change at runtime, 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, are performed on the same relative memory ___location. This is often called capturing the variable "by reference". Here is an example illustrating the concept in [[ECMAScript]], which is one such language:
<syntaxhighlight lang="
// Javascript
var f, g;
Line 197 ⟶ 189:
===Example 1: Reference to an unbound variable===
<ref>{{cite web |title=Function.prototype.bind() |url=https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_objects/Function/bind |website=MDN Web Docs |access-date=20 November 2018}}</ref>
<syntaxhighlight lang="
var module = {
x: 42,
Line 211 ⟶ 203:
===Example 2: Accidental reference to a bound variable===
For this example the expected behaviour would be that each link should emit its id when clicked; but because the variable 'e' is bound to the scope above, and lazy evaluated on click, what actually happens is that each on click event emits the id of the last element in 'elements' bound at the end of the [[for loop]].<ref>{{cite web |title=Closures |url=https://developer.mozilla.org/en-US/docs/Web/JavaScript/Closures#Creating_closures_in_loops_A_common_mistake |website=MDN Web Docs |access-date=20 November 2018}}</ref>▼
▲For this example the expected behaviour would be that each link should emit its id when clicked; but because the variable 'e' is bound the scope above, and lazy evaluated on click, what actually happens is that each on click event emits the id of the last element in 'elements' bound at the end of the for loop.<ref>{{cite web |title=Closures |url=https://developer.mozilla.org/en-US/docs/Web/JavaScript/Closures#Creating_closures_in_loops_A_common_mistake |website=MDN Web Docs |access-date=20 November 2018}}</ref>
var elements = document.getElementsByTagName('a');▼
▲<syntaxhighlight lang="ecmascript">
// Incorrect: e is bound to the function containing the 'for' loop, not the closure of "handle"▼
▲var elements= document.getElementsByTagName('a');
for (var e of elements) {
▲//Incorrect: e is bound to the function containing the 'for' loop, not the closure of "handle"
alert(e.id);
}
</syntaxhighlight>
Again here variable <code>e</code> would need to be bound by the scope of the block using <code>handle.bind(this)</code> or the <code>let</code> keyword.
Line 222 ⟶ 217:
On the other hand, many functional languages, such as [[ML (programming language)|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. This is often called capturing the variable "by value". Java's local and anonymous classes also fall into this category—they require captured local variables to be <code>final</code>, which also means there is no need to share state.
Some languages enable
Yet another subset, [[lazy evaluation|lazy]] functional languages such as [[
<syntaxhighlight lang="haskell">
Line 238 ⟶ 233:
</syntaxhighlight>
The binding of <code>r</code> captured by the closure defined within function <code>foo</code> is to the computation <code>(x / y)</code>—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
=== Closure leaving ===
Yet more differences manifest themselves in the behavior of other lexically scoped constructs, such as <code>return</code>, <code>break</code> and <code>continue</code> statements. Such constructs can, in general, be considered in terms of invoking an [[escape continuation]] established by an enclosing control statement (in case of <code>break</code> and <code>continue</code>, such interpretation requires looping constructs to be considered in terms of recursive function calls). In some languages, such as ECMAScript, <code>return</code> refers to the continuation established by the closure lexically innermost with respect to the statement—thus, a <code>return</code> within a closure transfers control to the code that called it. However, in [[Smalltalk]], the superficially similar operator <code>^</code> invokes the escape continuation established for the method invocation, ignoring the escape continuations of any intervening nested closures. The escape continuation of a particular closure can only be invoked in Smalltalk implicitly by reaching the end of the closure's code.
<syntaxhighlight lang="smalltalk">
Line 331 ⟶ 326:
== Closure-like constructs ==
Some languages have features which simulate the behavior of closures. In languages such as
=== Callbacks (C) ===
Some [[C (programming language)|C]] libraries support [[Callback (computer programming)|callbacks]]. This is sometimes implemented by providing two values when registering the callback with the library: a function pointer and a separate <code>void*</code> pointer to arbitrary data of the user's choice. When the library executes the callback function, it passes along the data pointer. This enables the callback to maintain state and to refer to information captured at the time it was registered with the library. The idiom is similar to closures in functionality, but not in syntax. The <code>void*</code> pointer is not [[Type safety|type safe]] so this C idiom differs from type-safe closures in C#, Haskell or ML.
Callbacks are used extensively in [[graphical user interface]] (GUI) [[widget toolkit]]s to implement [[event-driven programming]] by associating general functions of graphical widgets (menus, buttons, check boxes, sliders, spinners, etc.) with application-specific functions implementing the specific desired behavior for the application.
====Nested function and function pointer (C)====
With a [[GNU Compiler Collection]] (GCC) extension, a nested function<ref>{{cite web
|url = https://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html
|title = Nested functions}}</ref> can be used and a function pointer can emulate closures, provided the function does not exit the containing scope. The
<syntaxhighlight lang="c">
Line 419 ⟶ 399:
</syntaxhighlight>
The capturing of <code>final</code> variables enables
Capturing of variables by reference can be emulated by using a <code>final</code> reference to a mutable container, for example, a
With the advent of Java 8's lambda expressions,<ref>{{cite web |url=http://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html |title=Lambda Expressions |work=The Java Tutorials}}</ref> the closure causes the above code to be executed as:
<syntaxhighlight lang="java">
Line 442 ⟶ 419:
</syntaxhighlight>
Local classes are one of the types of [[inner class]] that are declared within the body of a method. Java also supports inner classes that are declared as ''non-static members'' of an enclosing class.<ref>
|
{{cite web |
|
}}</ref> These are defined in the body of the enclosing class and have full access to instance variables of the enclosing class. Due to their binding to these instance variables, an inner class may only be instantiated with an explicit binding to an instance of the enclosing class using a special syntax.<ref>
{{cite web |
|
}}</ref>
Line 499 ⟶ 476:
=== Blocks (C, C++, Objective-C 2.0) ===
{{Main|Blocks (C language extension)}}
[[Apple Inc.|Apple]] introduced [[Blocks (C language extension)|blocks]], a form of closure, as a nonstandard extension into [[C (programming language)|C]], [[C++]], [[Objective-C 2.0]] and in [[Mac OS X Snow Leopard|Mac OS X 10.6 "Snow Leopard"]] and [[
Pointers to block and block literals are marked with <code>^</code>. Normal local variables are captured by value when the block is created, and are read-only inside the block. Variables to be captured by reference are marked with <code>__block</code>. Blocks that need to persist outside of the scope they are created in may need to be copied.<ref>{{cite web |url=https://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/Blocks/Articles/00_Introduction.html |title=Blocks Programming Topics |author=<!-- Unstated staff writer --> |date=8 March 2011 |publisher=Apple Inc. |access-date=2011-03-08}}</ref><ref>{{cite web |url=http://thirdcog.eu/pwcblocks/ |title=Programming with C Blocks on Apple Devices |
<syntaxhighlight lang="objc">
Line 564 ⟶ 541:
=== Function objects (C++) ===
[[C++]] enables defining [[function object]]s by overloading <code>operator()</code>. 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. As of [[C++11|the 2011 revision]], the C++ language also supports closures, which are a type of function object constructed automatically from a special [[language construct]] called ''lambda-expression''. A C++ closure may capture its context either by storing copies of the accessed variables as members of the closure object or by reference. In the latter case, if the closure object escapes the scope of a referenced object, invoking its <code>operator()</code> causes undefined behavior since C++ closures do not extend the lifetime of their context.{{main|
<syntaxhighlight lang="cpp">
Line 594 ⟶ 571:
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 <code>x</code> and <code>y</code>.
The main limitation of Eiffel agents, which distinguishes them from closures in other languages, is that they cannot reference local variables from the enclosing scope. This design decision helps in avoiding ambiguity when talking about a local variable value in a closure - should it be the latest value of the variable or the value captured when the agent is created? Only <code>Current</code> (a reference to current object, analogous to <code>this</code> in Java), its features, and arguments of the agent
=== C++Builder __closure reserved word ===
Embarcadero C++Builder provides the
typedef void (*TMyFunctionPointer)( void );
</syntaxhighlight>In a similar way
typedef void (__closure *TMyMethodPointer)();
</syntaxhighlight>
== See also ==
{{div col}}
* [[Command pattern]]
* [[Currying]]
* [[Lambda calculus]]
* [[Partial application]]
* [[Syntactic closure]]
* [[Value-level programming]]
{{div col end}}
== Notes ==
{{Notelist
== References ==
Line 626 ⟶ 599:
== External links ==
*[https://web.archive.org/web/20160510140804/http://library.readscheme.org/page1.html Original "Lambda Papers"]: A classic series of papers by [[Guy L. Steele Jr.]] and [[Gerald Jay Sussman]] discussing, among other things, the versatility of closures in the context of Scheme (where they appear as ''[[lambda calculus|lambda]] expressions'').
* {{cite web
|last=Gafter
|
|
|
}}
* {{cite web
|last1=Bracha
|
|
}}
*[http://martinfowler.com/bliki/Closure.html Closures]: An article about closures in [[Dynamic typing|dynamically typed]] imperative languages, by [[Martin Fowler (software engineer)|Martin Fowler]].
Line 646 ⟶ 618:
[[Category:Implementation of functional programming languages]]
[[Category:Subroutines]]
[[Category:Articles with example Python (programming language) code]]▼
[[Category:Articles with example Scheme (programming language) code]]▼
[[Category:Articles with example JavaScript code]]▼
[[Category:Articles with example C++ code]]
[[Category:Articles with example Eiffel code]]▼
[[Category:Articles with example C Sharp code]]
[[Category:Articles with example D code]]
[[Category:Articles with example
[[Category:Articles with example Java code]]
▲[[Category:Articles with example JavaScript code]]
[[Category:Articles with example Ruby code]]
[[Category:Articles with example Smalltalk code]]
| |||