Lexical Scope
A variable may name a location where a value can be stored. A variable that does so is said to be bound to the location. . . . By abuse of terminology, the variable is sometimes said to name the value or to be bound to the value. This is not quite accurate, but confusion rarely results from this practice.
--Revised^5 Report on Scheme
Definitions
[Tip] Definition: Lexical Scope
Bindings established in one function are only accessible within the textual region of that function, that's lexical scope.
[Tip] Definition: Closure
A closure saves the current bindings from enclosing blocks for later invocation.
In imperative programming languages (Algol was the original) nested blocks may access local variables of enclosing blocks. Modern languages (lexically Lisp-like languages, Scheme and Common Lisp were the originals) further permit such an inner block (in particular a function or procedure) to be saved for later invocation. The act of saving such an inner block along with the current bindings of variables in the enclosing blocks that are referenced by the inner block, is called closure over or capturing those variables.
Think of a closure as an object that is created when somebody returns a procedure. The closure is constructed with two things: the code for the procedure and the current environment. Sometimes we think of invoking the closure just like invoking the function from which it was built, passing whatever parameters the function accepts, but when the function executes, the enclosing blocks' non-local variables will have the bindings that were in effect when the closure object was constructed.
Since the closure itself is an object that must be managed, it may have either dynamic extent or indefinite extent depending on whether it is only used by inner blocks of the creating block or passed out of the creating block.
[Tip] Definition: Frame, Activation Frame, Activation Record
An frame or activation record is a data structure, associated with the invocation of a block, which could be a function, procedure or control block. The frame stores the locally defined variables, temporaries, and fixed-sized data, and the information required to return to the invoking context. It can be stored on a stack, cactus stack or managed via closure.
In a register-based hardware architecture, the current activation record is typically partially stored in registers. Closures and continuations are specializations of activation records in support of particular language features of LISP, Scheme and related languages. In languages that permit recursion, activation records have dynamic extent. In languages that permit closures or continuations, activation records may have indefinite extent. Although they may not be visible to the programmer, their storage must be managed by the language run-time support. Because they are usually not visible to the programmer, they may be a source of inexplicable memory overhead.
[Tip] Definition: Activation Stack, Control Stack
An activation stack is a stack that stores frames (activation records), particularly subroutine return information.
Typically the control stack is supported and used by the hardware architecture and the operating system, limiting the types and sizes of objects that can be stored on it. Often, only one type of object, a stack frame, is permitted, and the layout of that is defined by the hardware architecture.
[Tip] Definition: Cactus Stack
A cactus stack is an activation stack with branches, and so is cactus shaped.
In languages that support continuations, activation records can have indefinite extent. One continuation implementation optimization to create a fork in the stack below the captured stack frames, so that new frames appear as a parallel branch. Instead of the copying the activation records that are captured, this just involves an extra pointer, so may use less memory and run faster. Further optimization is to do the forking lazily, so captured frames are only duplicated if they are modified.
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.
# # #
Dynamic Scoping of Exceptions.....
Common Lisp Example...
(defun fun1 (x)
(catch 'trap (+ 3 (fun2 x))))
(defun fun2 (y)
(catch 'trap (* 5 (fun3 y))))
(defun fun3 (z)
(throw 'trap z))
fun2's catcher shadows fun1's.
Java examples...
Refinements, Optimizations
activation frames
registers
continuous stack
chunked
cactus stack (n.b., application to threads, to resumption semantics)
continuation passing style (CPS)
call-cc (call-with-current-continuation)
translation into "glorified gotos"
Optimizing bindings
save registers (avoids copies across procedure/continuation boundaries)
[ could draw example showing 2 proc.'s that are co-recursive; then
redraw using continuations; then redraw using save registers ]
References
Guy Lewis Steele Jr. Macaroni is better than spaghetti. In
Proceedings of the Symposium on Artificial Intelligence and
Programming Languages, pages 60--66. These proceedings were
published as a special joint issue of SIGPLAN Notices 12(8) and
SIGART Newsletter 64, August 1977.
(an old paper, but points out why we should do Algol style scoping in Lisp. Probably what influenced T, Orbit, and Scheme's scoping mechanisms)
Guy Lewis Steele Jr. Rabbit: a compiler for Scheme.
MIT Artificial Intelligence Laboratory Technical Report 474, May 1978.
Guy Lewis Steele Jr. Compiler optimization based on viewing LAMBDA as
RENAME + GOTO.
In AI: An MIT Perspective. Patrick Henry Winston Richard Henry Brown, editor.
MIT Press, 1980.