© Copyright Kirk Rader 2023. All rights reserved.

Lexical Closures

The observant reader may have noticed that examples of mutually recursive lambda expressions in the description of tail recursion were shown using disjoint sets of variable names, where factorial was defined as having an argument named n while its local helper function had a corresponding argument named x. This was done for clarity of exposition: it is very obvious which variables belong to which functions when they all have different names where their lexical scopes overlap.

This is not actually a requirement of Scheme, though a good practice from the point of view of maintability, where normal lambda bindings are lexically scoped. For example, the same example of function composition could have be written with both functions having overlapping sets of variable names with no change in meaning or outcome:

(define (factorial n)
    (let f ((n n)
            (a 1))
        (if (<= n 1)
            (f (- n 1) (* a n)))))

It simply would have been a bit harder to describe what was going since in this case there are two different variables, both named n.

Historically, not all Lisp dialects have been lexically scoped in this way. Bindings for all variables existed in a single global environment in very early implementations of Lisp. This fact meant that there were times that the programmer actually did have to take care to use disjoint variable names for mutually recursive functions to avoid "name collisions" that could affect the outcome of a computation. That "bug" was sometimes exploited as a "feature" by some algorithms, so modern lexically scoped Lisp dialects often have alternative versions of special forms like lambda, let etc. that share a single, global name space. Some Scheme dialects, for example, have defined things like a fluid-let special form that works like ordinary let but whose bindings are in a single "fluid" (a.k.a. "dynamic") environment.

But wait! There's more!

If all there were to a lambda function's variable bindings that they are lexically scoped, they would not be substantially different from, say, pointers to functions in languages like C. The lexical environments that are created by lambda binding in Scheme (and other modern dialects like Common Lisp) represent "closures" over their entire run-time context such that a function object, when treated as a data value, "remembers" the lexical environment in which it was created. Mutliple invocations of the same such function create distinct such "closed" environments, also known as "closures." Consider:

(define (make-foo a)
    (lambda () a))

(define foo1 (make-foo 1))

(define foo2 (make-foo 2))

After evaluating the three preceding expressions in a Scheme environment, you will have three global variables, all of which are bound to functions.

The function make-foo returns an anonymous function whose lexical closure includes a definition for the local variable a. Each anonymous function returned by make-foo "remembers" the value which was passed to make-foo when it was invoked with its own "closed over" binding of a. Both foo1 and foo2 are bound to functions made using calls to make-foo, but with different values for a. In particular, invoking foo1 returns 1 while invoking foo2 returns 2:



What this means is that anonymous functions in Scheme can be used in many cases where you might need to define some custom data structure in other programming languages. In fact, lexical closures are so powerful that there is a saying among Scheme programmers to the effect that "objects are a poor man's closures." One of (if not the) earliest commercially significant object-orietned programming systems was Flavors that ran on Symbolics' Lisp Machines. The earliest versions of Flavors implemented objects using lexical closures directly, rather like a more sophisticated version of make-foo. The "message passing style" of method invocation this created was a heavy influence on the design of Smalltalk. Flavors was later rewritten to have a very different style of syntax (and far more sophisticated features) but lexical closures remained deeply buried within it. That later style was then the original model for CLOS when Common Lisp running on generic hardware replaced Zetalisp running on Lisp Machines as the both the de facto and de jure standard for commercially deployed Lisp.

[This author still misses many features of Flavors / CLOS — especially the MOP (Meta Object Protocol). While a pale shadow lives on for Java programs in the form of aspectj, the full power of lexical closures and a MOP can really only be experienced in dialects of Lisp to which CLOS based frameworks have been ported.]