Where do closures come from?

Common Lisp's function form is usually described as a device for switching between namespaces: it evaluates its argument in the “function” namespace instead of the normal “variable” namespace.

Older sources have a completely different idea: they say function makes closures. The Hyperspec says:

If name is a lambda expression, then a lexical closure is returned.

and

function creates a closure of the lambda expression

Both of these lines were inherited from CLtL, so this is not a new interpretation, nor one incompatible with the best of knowledge. What's going on?

To begin with, these two interpretations of function aren't observably different in portable Common Lisp. The only portable way to get a closure is by (function (lambda ...)) or by macros like defun that might expand to it. ((lambda ...) expands to (function (lambda ...)), because unlike all other special forms, lambda is in the function namespace, but that's just a historical quirk.) The only way to use lambda without function is ((lambda ...) ...), which has the same semantics regardless of whether it makes a closure. So portable code can't tell the difference.

Implementation-specific extensions can. If compile is extended to non-null lexical environments, it will make closures out of lambda-expressions without any help from function. Or if there's a named-lambda form that makes closures, it's unnecessarily complex to attribute the closure in (function (lambda ...)) to function.

So Common Lisp culture favors the simpler interpretation: lambda makes closures, and function is a mere namespacing operator.

Like so many oddities of CL, the old interpretation comes from Lisp Machine Lisp. The 1984 Lisp Machine Manual introduces function by saying it “has two distinct, though related, meanings.” The first is to get a symbol's function definition, and the second is to make a closure:

(let (a)
  (mapcar (function (lambda (x) (push x a))) l))
passes mapcar a specially designed closure made from the function represented by (lambda (x) (push x a)). When mapcar calls this closure, the lexical environment of the function form is put again into effect, and the a in (push x a) refers properly to the binding made by this let.

These two meanings were reflected in implementations. Guy Steele's reference interpreter (in the CL mailing list archive) doesn't bother to make a closure for ((lambda ...) ...), only for (function (lambda ...)). But when optimizing compilers became the norm, it no longer seemed silly (or inefficient) for lambda to always make a closure, so reinterpreting function as a namespacing operator made sense.

Surprisingly, this is not the first time function has been reinterpreted. The Pitmanual says Maclisp's function didn't make closures — it took a different form, *function, to even partially do that. function was equivalent to quote, except that in compiled code it would make a compiled function instead of just a lambda-expression — it permitted compilation but didn't change scoping. When Lisp Machine Lisp changed it to make closures, that was largely backward compatible, since most lambdas were intended to use lexical scope anyway. (I'm not sure when compilers started to use lexical scope — was that in Maclisp?)

I don't think any other language construct has had so many unrelated meanings over the years, let alone done so while preserving the meaning of existing code. function was originally a hint to the compiler, then a way to make closures, and then a namespacing operator. Its history probably ends there, since most new lisps eschew multiple namespaces and omit function rather than repurpose it, but three unrelated meanings is impressive.

4 comments:

  1. The only way to use lambda without function is ((lambda ...) ...)

    That was true in CLtL1, but in CLtL2/ANSI CL, it's false. A lambda expression in operand position is a macro that evaluates to a closure, and is equivalent to (function (lambda ...)). This change was made so that ISLisp would be a subset of ANSI CL. In ISLisp, lambda is a special form rather than a macro, and (function (lambda ...)) is an error; only (function ) is valid, so (function ...) really is just a namespace switcher. See pp. 23-24 (physical pages 30-31) of the ISLisp 2007 standard.

    I'm not sure when compilers started to use lexical scope.

    Right from the beginning. See p. 78 (physical page 86) of the Lisp 1.5 Programmer's Manual. In Lisp 1.5 compiled functions there are ordinary variables, which are allocated on the stack and are not visible outside the function where they are bound; special variables, which are dynamic and shallow bound, with their previous values saved on the stack; and common variables, which are bound on the interpreter's deep-binding alist and are evaluated in compiled code by calling eval. Only common variables allow communication between compiled and interpreted code other than by call and return. It is noted that in order for (lambda (x y) (maplist x (function (lambda (j) (cons (car j) y))))) to do what we expect when compiled, y must be declared special or common; if not, its global value will be used in the nested function.

    ReplyDelete
    Replies
    1. Since the lambda macro expands to (function (lambda ...)) it can't distinguish whether it's lambda or function that makes closures. I mentioned the macro the first paragraph, but it was out of place there; moved to the part about distinguishability.

      Delete
  2. For "(function )" read "(function <identifier>)".

    ReplyDelete

It's OK to comment on old posts.