Table of Contents
1 Introduction
I'm working through Paul Graham's excellent 1993 book, On Lisp.
In one sections he discusses how to make recursive calls to closures. As the Wiki entry says: "In computer science, a closure is a first-class function with free variables that are bound in the lexical environment."
This is exactly correct. I guess I've known about closures for at least 15 years, maybe longer. Thus, when reading Graham's discussion of closures in Lisp, I didn't figure that I'd learn much new, but was certainly looking forward to the discussion from a Lisp perspective.
His first example caught me off-guard:
(defun list+ (lst n) (mapcar #’(lambda (x) (+ x n)) lst))
He writes: "If we look closely at the function which is passed to mapcar within list+, it’s actually a closure. The instance of n is free, and its binding comes from the surrounding environment. Under lexical scope, every such use of a mapping function causes the creation of a closure." (p.18)
I'd never thought the nature of the lambda expression when using mapcar in a lexical scope. I wouldn't have called it closure. Probably because the lambda expression is created and destroyed within the lexical scope of the enclosed variable.
Graham's definition was forcing me to call something a closure, before the lexical scope had been destroyed.
I was introduced to closures through Perl and blessed
pointers. Anonymous functions were created, closed around my variables (free
lexical variables in perl are my variables) and their reference
returned. With the lexical environment destroyed upon that return, the
variable entry removed from the symbol table, there was no way to get to it,
unless you could manipulate it through calls to the closure. (Hello object
oriented programming.)
Graham's presentation made me question whether or not the value of the enclosed variable could be changed after the function had been instantiated, but before the lexical scope was destroyed.
What if I played with the enclosed variable before the lexical scope vanished?
Of course the question is really this: does the closure have the address or the value of n?
I felt like I knew the answer, even though my brain kept repeating, "you cannot access variables contained in closures, you cannot access variables contained in closures, warning, warning."
But I knew I could. I became a mad scientist, or at least like Gene Wilder's interpretation of one: "It could work!"
(defun test (n) (let ((x 0)) (setq x #'(lambda () (setq n (1+ n)))) (setq n 33) x))
Then: (setq x (test 1) and (funcall x)
What's the value returned by the funcall?
That's what got me. My brain kept repeating that enclosed variables could not
be changed, therefore the value 2 must be returned. After all, n is enclosed.
But then comes the realization that the lexical scope of n had not vanished
after the instantiation of the closure into x. The variable n is still
very much accessible outside the closure for one brief, fleeting,
s-expression, (setq n 33).
Of course the value 34 is returned. It's obvious.
2 More
Graham follows up with another problem:
"a function defined in a lambda-expression doesn’t have a name and therefore has no way of referring to itself. This means that in Common Lisp we can’t use lambda to define a recursive function." (p. 21)
This means that one of the most common idiom's in Lisp (recursion, the sine qua non of Lisp, it would seem) is not available when using another common idiom mapcar.
Of course,there is a way around this using labels. On page 22 he gives the
following example:
(defun count-instances (obj lsts) (labels ((instances-in (lst) (if (consp lst) (+ (if (eq (car lst) obj) 1 0) (instances-in (cdr lst))) 0))) (mapcar #’instances-in lsts)))
This function works as follows:
> (count-instances ’a ’((a b c) (d a r p a) (d a r) (a a))) (1 2 1 2)
This illustrates recursion, but I don't like the function.
If the list is something like:
> (count-instances ’a ’((((a)) b c) (d (a r p a)) ((d a) r) (((a)) a)))
Then the result is: (0 0 0 1)
I don't think that's as interesting as returning the number of first level grouped objects, no matter how deeply embedded in the tree, or in this case: (1 2 1 2).
I decided to try and modify it to suit me. Fortunately it's pretty easy to do:
(defun count-instances-new (obj lsts) (labels ((instances-in (lst) (if (consp lst) (if (consp (car lst)) (+ (instances-in (car lst)) (instances-in (cdr lst))) (+ (if (eq (car lst) obj) 1 0) (instances-in (cdr lst)))) (if (eq lst obj) 1 0)))) (mapcar #'instances-in lsts)))
3 Conclusion
Learn Lisp. You'll be a better programmer!
