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.
labels
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 ())))
let
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.