Defining local functions

In the discussion of the conversion of recursive functions to iteration (tail recursion) in recursion and iteration, we used an additional parameter to improve the efficiency of the functions under consideration. The cost of doing this is elegance and abstraction. The user of the function has to supply the initial value of that parameter, yet that value is private to the implementation of the function and is always the same. One solution is to define two functions, for example: (defun reverse-list (l) (reverse-list-aux l ())) (defun reverse-list-aux (l x) (if (null l) x (reverse-list-aux (cdr l) (cons (car l) x)))) However, a neater solution is to use a local function definition. There are two commonly-used forms for defining local functions in Lisp: labels and named let.


The labels form looks like this: (labels ((fn-name-1 arg-list-1 body-1) ... (fn-name-m arg-list-m body-m)) exp-1 ... exp-n) At first sight this might seem unnecessary, since we can use let to associate names with (anonymous) functions as follows: (let ((fn-name-1 (lambda arg-list-1 body-1)) ... (fn-name-m (lambda arg-list-m body-m))) exp-1 ... exp-n) However, this does not mean the same, since any reference to fn-name-i in any of the anonymous functions will be to the association outside the scope of the let form. So the purpose of labels is to permit the definition of local mutually recursive functions. In effect, labels is equivalent to: (let ((fn-name-1 ()) ... (fn-name-m ())) (setq fn-name-1 (lambda arg-list-1 body-1)) ... (setq fn-name-1 (lambda arg-list-1 body-1)) exp-1 ... exp-n) We can now return to the case in question, namely reverse-list, and using labels we can make the following definition: (defun reverse-list (l) (labels ((loop (l x) (if (null l) x (loop (cdr l) (cons (car l) x))))) (loop l ())))


Surely let is for local declarations? What has this to do with local function definition? The key phrase is named let, which looks like this:

(let name ((id-1 exp-1) ... (id-m exp-m)) exp-m+1 ... exp-n)

The name of the let is associated with a function taking as many arguments as there are local variable declarations. The first time this function is called, the values of the expressions initializing the local declarations are passed as parameters. Subsequent calls, from the body of the let, control the recursion. In effect, named let is equivalent to:

(labels ((name (id-1 ... id-m) exp-m+1 ... exp-n)) (name exp-1 ... exp-m)) We can again rewrite reverse-list now, this time using a named let. (defun reverse-list (l) (let loop ((l l) (x ())) (if (null l) x (loop (cdr l) (cons (car l) x))))) This can often be neater than labels, when only a single local function is required.
Julian Padget,, this version December 9, 1994