Lisp labels and anonymous functions

I was playing around with Lisp some more in the last few weeks, and today i came across a little problem with anonymous functions (or lambdas, if you want to).

The problem with anonymous lambda functions is, that they can’t call themselves recursively, since – well they’re anonymous and hence don’t have a name. To get passed this problem, you can let it have an additional function parameter which it will call in place where the recursion would normally take place.

An example for a reverse function, which reverses the elements of its argument (a list) with the help of an accumulator list (which holds the reversed list) could be written like this, without using an additional function:

1
2
3
4
5
6
7
8
9
10
11

(defun myreverse (list &optional (acc nil))
  (let ((head (car list)) (rest (cdr list)))
    (cond
      (head
       (cond
	 ((atom head)
	  (myreverse rest (cons head acc)))
	 (t
	  (myreverse rest (cons (myreverse head) acc)))))
      (t
       acc))))

But, as you can see, the accumulator list is part of the function’s argument list, although optional. To make this function a little bit ’safer’, it shouldn’t be part of the ‘public interface’ of the function. So you’d probably come up with something like this, where you’d use an anonymous helper function, which takes the additional accumulator list and returns it when it’s done reversing the original list:

1
2
3
4
5
6
7
8
9
10
11

(defun myreverse (list)
  (let ((reverse-acc #'(lambda (func list acc)
			(let ((head (car list)) (rest (cdr list)))
			  (cond (head
				 (cond ((atom head)
					(funcall func func rest (cons head acc)))
				       (t
					(funcall func func rest (cons (funcall func func head nil) acc)))))
				(t
				 acc))))))
    (funcall reverse-acc reverse-acc list nil)))

But, as you can see, since anonymous functions can’t call themselves recursively, you need to give it another extra parameter, a function object, which actually gets filled with the anonymous function itself, so it can call itself inside its body. But, fortunately, theres an even better version how to do exactly this in lisp: With the labels special operator, which defines local functions with a given name (like normal functions) which can then get called inside the function body itself and in the body-form of the macro:

1
2
3
4
5
6
7
8
9
10
11

(defun myreverse (list)
  (labels ((myreverse-acc (list acc)
	     (let ((head (car list)) (rest (cdr list)))
	       (cond (head
		      (cond ((atom head)
			     (myreverse-acc rest (cons head acc)))
			    (t
			     (myreverse-acc rest (cons (myreverse-acc head nil) acc)))))
		     (t
		      acc)))))
    (myreverse-acc list nil)))

As you can see, this version is nicer than the first or the second, since it hides the fact, that the reverse function uses an accumulator list and that it is also easier to understand, since you can use an actual name for the function instead of passing the function as an argument to itself, in ordner to make a recursive call. So basically, you can think of a function defined with the labels special operator as a local defun, which I think is really nice.