Motivation
Imperative, block structured languages establish bindings when a procedure is called and discharge those bindings when the procedure exits (dynamic extent). This works in older languages. For modern languages that support returning procedures as objects, this stack like lifetime for bindings is not enough. Discharging bindings upon procedure exit can cause problems. Here is an example:
(defun compose (f g)
#'(lambda (x)
(funcall f (funcall g x))))
(funcall (compose #'sqrt #'abs) -9.0)
(define (compose f g)
#'(lambda (x)
(f (g x)) ) )
((compose #'sqrt #'abs) -9)
Although intuitively we know that f should be bound to #'sort and g should be bound to #'abs, a naive stack-based, dynamic extend would discharge those bindings when compose returns. The bindings are needed after procedure exit.
In Scheme or Common Lisp, the function represented by a lambda-expression may refer to any lexically apparent variable and get the correct value, even if the construct that established the binding has been exited in the course of execution.
Side note, many OO languages permit returning objects in some way that is similar to the problem of returning a procedure.
Closure Implementation
SCOPE: LEXICAL
EXTENT: INDEFINITE, but sometimes DYNAMIC, depends on implementation and some implementations do both depending on language construct.
IMPLEMENTATION: activation frames, closures
[Note] Note
For illustration purposes, assume always wrap closures, but Scheme compilers are pretty sophisticated, and so optimize closures away into more efficient mechanisms.
Goal: know what variable binding will be used when the procedure (function) is defined. In other words, a static, lexical inspection of the source code is all that is necessary. There is no need to dynamically "play" computer to out guess variable bindings. Specifically, lexical (static) scope with dynamic extent is informally called static scoping.
The most general implementation of static scope with indefinite extent is realized with the "closure." Intuitively a closure "wraps up" a set of variable bindings (an environment) for future use. When a procedure is defined, a closure is created and stored with the procedure compiled code. Later when the procedure is called, the active environment uses a closure while the procedure runs.
[ draw examples for dynamic scoping, but show closures instead ]
[Note] Note
Java is lexically scoped, but exceptions are dynamically scoped. Ada, too.
Optimizing away closures at compile-time
C and C++ and in some cases Ada and Java, have enough information to optimize away closures (which are costly at run-time). C and C++ never need to use closures and instead rely on frames organized in an activation stack. C, C++ assume we cannot pass procedures as arguments, thus the non-local references are always in the same (relative) position in the stack. There are several alternative implementations that organize frames so that their stack-based lookup is faster. Note, Java cannot always rely on this optimization and must use closures sometimes. This is because passing objects...like passing procedures. [ good example: GUI uses (nested) anonymous inner classes, but the new class or instance of the new class is passed elsewhere ]
Closures are required when the bindings of lexically scoped parameters of a function have indefinite extent. (By contrast, in Algol the bindings of lexically scoped parameters of a procedure have dynamic extent.) The function definition
(defun compose (f g)
#'(lambda (x)
(funcall f (funcall g x))))
when given two arguments, immediately returns a function as its value. The parameter bindings for f and g do not disappear (and must have indefinite extent) because the returned function, when called, could still refer to those bindings. Therefore
(funcall (compose #'sqrt #'abs) -9.0)
produces the value 3.0. (An analogous procedure would not necessarily work correctly in typical C or C++ (Algol) implementations.)
# # #
Closure Notes
Lexical Scope Examples
Java Objects vs. Closures
How shall we write this Scheme code in Java?
(define (foo n)
(lambda (i) (set! n (+ n i))))
Foo creates and returns a program for generating a number sequence. Conceptually, n represents a running total and i represesnts an increment. foo's integer argument is the initial running total; foo initializes (injects) this into the the procedure it creates and returns.
(define x (foo 100))
x ==> (lambda (i)
(set! n (+ n i)) )
(x 3)
(x 10)
(define y (foo 50))
(y 3)
(y 10)
(x 5)
(y 5)
Each call to x adds something to n, while updating (i.e., mutating) n, and returns the the new running total. The closure foo creates captures the parameter n, forever.
How do we do this in an OO language, like C++, Java, or Smalltalk?
First, C++, which has no support for closures; use object state, instead.
class foo {
int n;
public:
foo (int m) { n = m; }
int operator() (int i) { n += i; return n; }
};
Using OO the constructor "captures" the value for n in the object (instance's) state. This uses an object "to simulate a closure", as opposed to "pure" non-side-efecting functions.
This would be called as follows:
foo x(100);
cout << x(3);
cout << x(10);
foo y(50)
cout << y(3);
cout << y(10);
cout << x(5);
cout << y(5);
Or in Java, there are two ways. First we could do the syntactic-sugar equivalent of C++.:
public class foo {
private int n;
public foo(int n) {
this.n = n;
}
public int inc(int i) {
n += i; return n;
}
}
...
foo x = new foo(100);
System.err.prtinln(x.inc(3));
System.err.prtinln(x.inc(2));
foo y = new foo(50);
System.err.prtinln(y.inc(3));
System.err.prtinln(y.inc(10));
System.err.prtinln(x.inc(5));
System.err.prtinln(y.inc(5));
Notice that we connot overload operator(), so define a method, inc, instead.
The second way to do this in Java is with anonymous inner classes: Java's (anonymous) inner class provides the potential for a closure-like construct:
interface Incrementor {
int inc (int i);
};
...
class foo
static public Incrementor gen( final int n ) {
return new Incrementor() {
public int inc( int i ) {
n = n + i; // one big prob is here
return n;
}
};
}
}
Assuming a class named foo,
Incrementor x = foo.gen(100);
f.inc(3);
f.inc(2);
This eliminates the need for an instance variable, making use of the closure-like behaviour of inner classes in Java. ONE BIG PROBLEM: it's illegal, because cannot assign to the final variable, n. But note that IBM jikes will compile this without problem, and generate correct bytecodes.
Closures and Cactus Stacks
ST vs. Java
When st supports closure.
(e.g., no need fo final in the inner class)