Lisp: Tears of Joy, Part 6

Closures

Suppose you want to write a function that saves some value it can examine the next time it runs. For example, functions that generate random numbers often use the previously generated random number to help generate the next. To do this, you need to lay aside a value such that a function can get at it next time.

It’s a risky proposition if you use a global variable or a property list to store such a value. If you get careless, and write another function that uses the same global variable or property, the two functions may interact in a way you never intended. It is even more problematic if you wish to have several incarnations of the same function around, each remembering what it computed previously, but not interfering with one another. Using a single, global object does not accommodate this.

For example, suppose you want a function that will give you the next even number each time it is called. You could write this as a function that uses the global variable *evenum* to remember the last value it computed:

> (defun generate-even()
  (setq *evenum* (+ *evenum* 2)))
GENERATE-EVEN
> (setq *evenum* 0)
0
> (generate-even)
2
> (generate-even)
4
> (generate-even)
6

This works fine, but some other function could come along and clobber evenum in between calls. And we could not use generate-even to generate two sequences of even numbers simultaneously, independent of the other.

The solution to this problem is to make a version of a function that has variables only it can access. This is done by taking a function that contains some free symbols, and producing a new function in which all those free symbols are given their own, unique variables (free symbols are symbols used to designate variables within a function, but which are not formal parameters of that function).

This is as if we replaced each free symbol with a new symbol, one we were certain no other function could ever use. When this new function is run, then, its free symbols will reference variables that no other function can reference. If the values of some of these variables are changed, their new values will be retained until the next time the function is run.

However, changes to these variables will not have any effect outside of this function; moreover, the values of these variables cannot be accessed or altered outside of this function.

In this example, we would like to produce a version of generate-even that has its own private copy of the free variable *evenum*. When we create this version of generate-even, we would like its version of *evenum* to be initialised at whatever value *evenum* currently has.

No matter what happens subsequently to the original version, this will not affect the new version. When we run this new version, it would update its private copy of *evenum*. This would not affect the version of *evenum* known to the original function, but the new, updated copy of *evenum* would be available to the new function the next time it is run.

In other words, we take a sort of snapshot of a function, with respect to the current status of its free symbols. We can then manipulate this picture, rather than the function itself. The picture has about the same logical structure as the original, but if we change something in the picture, the original does not change. In fact, we should be able to take any number of such snapshots, and manipulate each one a bit differently. The alterations to each snapshot would serve to record its current state of affairs. Each snapshot could be looked at and altered quite independently of the others.

When we take such a snapshot of a function, it is called a closure of that function. The name is derived
from the idea that variables denoted by the free symbols of that function, normally ‘open’ to the world outside that function, are now closed to the outside world.

In Common Lisp, closures of functions are created by supplying the function function with a lambda expression as argument. If the free symbols of that lambda expression happen to be parameters of the function within which the lambda expression is embedded, function will return a snapshot of the function denoted by the lambda expression. This snapshot will contain its own variables corresponding to each of the lambda expression’s free symbols.

For example, we can use function to write a version of generate-even that will produce a closure that includes the free symbol *evenum* in the picture:

> (defun generate-even (*evenum*)
      (function
          (lambda()
              (setq *evenum* (+ *evenum* 2)))))
GENERATE-EVEN
> (setq gen-even-1 (generate-even 0))
#<FUNCTION :LAMBDA NIL (SETQ *EVENUM* (+ *EVENUM* 2))>
> (funcall gen-even-1)
2
> (funcall gen-even-1)
4
> (funcall gen-even-1)
6

When generate-even is called, Lisp creates a new variable corresponding to *evenum*, as Lisp always produces new variables corresponding to the formal parameters of a function. Then the function function returns a closure of the specified lambda expression. Since a new variable corresponding to *evenum* exists at this time, the closure gets this version of *evenum* as its own.

When we exit this call to generate-even, no code can reference this variable that is closed off to the outside world. We save this closure by assigning it to the variable gen-even-1.

Next, let us use funcall to invoke this function (funcall is like apply, but expects the arguments right after the function name. In this case, there are none, as the lambda expression of generate-even, and hence, the closure produced from it, is a function of no arguments).

Lisp prints out the closure as #<FUNCTION :LAMBDA NIL (SETQ *EVENUM* (+ *EVENUM* 2))>.

Remember that the notation used to print closures is not a part of the Common Lisp standard. This is because it is not really meaningful to talk about printing a closure. Therefore, other implementations of Common Lisp may use a different notation.

We run this closure a couple of times, and each time it produces a new value. We can create as many independent closures of the same function as we like. For example, if we make another closure of generate-even right now…

> (setq gen-even-2 (generate-even 0))
#<FUNCTION :LAMBDA NIL (SETQ *EVENUM* (+ *EVENUM* 2))>
> (funcall gen-even-2)
2
> (funcall gen-even-2)
4
> (funcall gen-even-1)
8
> (funcall gen-even-1)
10
> (funcall gen-even-2)
6

This closure starts off with its version of *evenum* at the value 0. Each closure has its own independent variable corresponding to the symbol *evenum*. Therefore, a call to one function has no effect on the value of *evenum* in the other.

Close that function!

When we close off the free symbols of a function, a new problem presents itself. The closed variables are inaccessible outside of the closure, so it would be difficult to write a set of functions that shared the same closed variable.

For example, suppose we want to write a pair of functions where one returns the next even number, and the other the next odd number. However, we want them to work in tandem, so that a call to one advances the other. For example, if we call the even number generator three times in a row, it should return 2, 4, and 6. Then a call to the odd number generator should return 7. If we call it again, it should return 9. The next time we call the even number generator, it should return 10.

It is easy to write a single pair of such functions. For example, we could do the following:

> (defun generate-even()
      (setq *seed* (cond ((evenp *seed*) (+ *seed* 2))
          (t (1+ *seed*)))))
GENERATE-EVEN

> (defun generate-odd()
      (setq *seed* (cond ((oddp *seed*) (+ *seed* 2))
          (t (1+ *seed*)))))
GENERATE-ODD

> (setq *seed* 0)
0
> (generate-even)
2
> (generate-odd)
3
> (generate-even)
4
> (generate-even)
6
> (generate-odd)
7

However, if we want to make closures of these functions, we are in trouble. If we use closure to produce a closure of each function, each closure would get its own version of *seed*. The closure of generate-even could not influence the closure of generate-odd, and the converse would also be true.

But this is not what we want. The solution to this problem is to create closures of a number of functions in the same context. The functions closed together would share their variables with one another, but not with anyone else. For example, here is a function that creates a list of two closures, one of which generates even numbers and the other, odd:

> (defun generate-even-odd (*seed*)
    (list
        (function
            (lambda()
                (setq *seed* (cond ((evenp *seed*) (+ *seed* 2))
                    (t (1+ *seed*))))))

         (function
             (lambda()
                 (setq *seed* (cond ((oddp *seed*) (+ *seed* 2))
                     (t (1+ *seed*))))))))
GENERATE-EVEN-ODD
> (setq fns (generate-even-odd 0))
(#FUNCTION :LAMBDA NIL (SETQ *SEED* (COND ((EVENP *SEED*) (+ *SEED* 2)) (T (1+ *SEED*))))>
(#FUNCTION :LAMBDA NIL (SETQ *SEED* (COND ((ODDP *SEED*) (+ *SEED* 2)) (T (1+ *SEED*))))>)
> (funcall (car fns))
2
> (funcall (car fns))
4
> (funcall (cadr fns))
5
> (funcall (cadr fns))
7
> (funcall (car fns))
8

Some readers who aren’t actively using Lisp may have forgotten some of what we covered earlier in this series, so here is a brief explanation of the keywords used in the code above.

• (cond ((test expression*)*)) — Evaluates test expressions until one returns true. If that test has no corresponding expressions, returns the value of the test. Otherwise, evaluates the expressions in order, returning the value(s) of the last. If no test returns true, returns nil.
• car — The primitive functions for extracting the elements of lists are car and cdr. The car of a list is the first element, and the cdr is everything after the first element:

  > (car `(a b c))
  A
  > (cdr `(a b c))
  (B C)

• caddr — Common Lisp defines functions like caddr, which is an abbreviation for “car of cdr of cdr“. All the functions of the form c_x_r, where _x_ is a string of up to four as or ds, are defined in Common Lisp. With the possible exception of cadr, which refers to the second element, it is not a good idea to use them in code that anyone else is going to
  read.
• (evenp i) — Returns true if i is even; (oddp i) — returns true if i is odd.

The call to generate-even-odd produces a pair of closures, one for each call to function. This pair shares access to an otherwise private copy of the variable *seed*. Subsequent calls to generate-even-odd would create additional pairs of such closures, each pair sharing a variable all its own.