We define the *reversal* of a list *L*
to be a list containing exactly the elements of *L* in reversed
order.
The Common LISP built-in function `(reverse L)`
returns the reversal of

USER(1): (reverse '(1 2 3 4)) (4 3 2 1) USER(2): (reverse '(1 (a b) (c d) 4)) (4 (c d) (a b) 1) USER(3): (reverse nil) NIL

Implementing a version of `reverse` is not difficult,
but finding an efficient implementation is not as trivial.
To review what we learned in the last tutorial, let us begin
with a naive implementation of `reverse`:

(defun slow-list-reverse (L) "Create a new list containing the elements of L in reversed order." (if (null L) nil (list-append (slow-list-reverse (rest L)) (list (first L)))))

Notice that this linearly recursive implementation calls
the function `list-append` we implemented in the
the last tutorial. Notice also the new function `list`,
which returns a list containing its arguments. For example,
`(list 1 2)` returns the list `(1 2)`. In general,
`(list x_{1} x_{2} ...
x_{n})`
is just a shorthand for

So, why does `(slow-list-reverse L)` returns
the reversal of

**Case 1:***L*is`nil`.

The reversal of*L*is simply`nil`.**Case 2:***L*is constructed from a call to`cons`.

Then`L`has two components:`(first`and*L*)`(rest`. If we append*L*)`(first`to the end of the reversal of*L*)`(rest`, then we obtain the reversal of*L*)*L*. Of course, we could make use of`list-append`to do this. However,`list-append`expects two list arguments, so we need to construct a singleton list containing`(first`before we pass it as a second argument to*L*)`list-append`.

Let us trace the execution of the function to see how the recursive calls unfold:

USER(3): (trace slow-list-reverse) (SLOW-LIST-REVERSE) USER(4): (slow-list-reverse '(1 2 3 4)) 0: (SLOW-LIST-REVERSE (1 2 3 4)) 1: (SLOW-LIST-REVERSE (2 3 4)) 2: (SLOW-LIST-REVERSE (3 4)) 3: (SLOW-LIST-REVERSE (4)) 4: (SLOW-LIST-REVERSE NIL) 4: returned NIL 3: returned (4) 2: returned (4 3) 1: returned (4 3 2) 0: returned (4 3 2 1) (4 3 2 1)Everything looks fine, until we trace also the unfolding of

USER(9): (trace list-append) (LIST-APPEND) USER(10): (slow-list-reverse '(1 2 3 4)) 0: (SLOW-LIST-REVERSE (1 2 3 4)) 1: (SLOW-LIST-REVERSE (2 3 4)) 2: (SLOW-LIST-REVERSE (3 4)) 3: (SLOW-LIST-REVERSE (4)) 4: (SLOW-LIST-REVERSE NIL) 4: returned NIL 4: (LIST-APPEND NIL (4)) 4: returned (4) 3: returned (4) 3: (LIST-APPEND (4) (3)) 4: (LIST-APPEND NIL (3)) 4: returned (3) 3: returned (4 3) 2: returned (4 3) 2: (LIST-APPEND (4 3) (2)) 3: (LIST-APPEND (3) (2)) 4: (LIST-APPEND NIL (2)) 4: returned (2) 3: returned (3 2) 2: returned (4 3 2) 1: returned (4 3 2) 1: (LIST-APPEND (4 3 2) (1)) 2: (LIST-APPEND (3 2) (1)) 3: (LIST-APPEND (2) (1)) 4: (LIST-APPEND NIL (1)) 4: returned (1) 3: returned (2 1) 2: returned (3 2 1) 1: returned (4 3 2 1) 0: returned (4 3 2 1) (4 3 2 1)What we see here is revealing: given a list of

We can in fact build a much more efficient version
of `reverse` using *auxiliary functions*
and *accumulator variables*:

(defun list-reverse (L) "Create a new list containing the elements of L in reversed order." (list-reverse-aux L nil)) (defun list-reverse-aux (L A) "Append list A to the reversal of list L." (if (null L) A (list-reverse-aux (rest L) (cons (first L) A))))

The function `list-reverse-aux` is an *auxiliary function*
(or a *helper function*). It does not perform any useful
function by itself, but the *driver function*
`list-reverse` could use it as a tool when building a
reversal. Specifically, `(list-reverse-aux L A)`
returns a new list obtained by appending list

Let us articulate why `(list-reverse-aux L A)`
correctly appends

**Case 1:***L*is`nil`.

The reversal of*L*is simply`nil`. The result of appending*A*to the end of an empty list is simply*A*itself.**Case 2:***L*is constructed by`cons`.

Now*L*is composed of two parts:`(first`and*L*)`(rest`. Observe that*L*)`(first`is the last element in the reversal of*L*)*L*. If we are to append*A*to the end of the reversal of*L*, then`(first`will come immediately before the elements of*L*)*A*. Observing the above, we recognize that we obtain the desired result by recursively appending`(cons (first`to the reversal of*L*)*A*)`(rest`.*L*)

USER(17): (trace list-reverse list-reverse-aux) (LIST-REVERSE LIST-REVERSE-AUX) USER(18): (list-reverse '(1 2 3 4)) 0: (LIST-REVERSE (1 2 3 4)) 1: (LIST-REVERSE-AUX (1 2 3 4) NIL) 2: (LIST-REVERSE-AUX (2 3 4) (1)) 3: (LIST-REVERSE-AUX (3 4) (2 1)) 4: (LIST-REVERSE-AUX (4) (3 2 1)) 5: (LIST-REVERSE-AUX NIL (4 3 2 1)) 5: returned (4 3 2 1) 4: returned (4 3 2 1) 3: returned (4 3 2 1) 2: returned (4 3 2 1) 1: returned (4 3 2 1) 0: returned (4 3 2 1) (4 3 2 1)

For each recursive call to `list-reverse-aux`, notice how
the first element of *L* is "peeled off", and is then
"accumulated" in *A*. Because of this observation, we
call the variable *A* an *accumulator variable*.

To better understand how auxiliary functions and accumulator variables are used, let us revisit the problem of computing factorials. The following is an alternative implementation of the factorial function:

(defun fast-factorial (N) "A tail-recursive version of factorial." (fast-factorial-aux N 1)) (defun fast-factorial-aux (N A) "Multiply A by the factorial of N." (if (= N 1) A (fast-factorial-aux (- N 1) (* N A))))Let us defer the explanation of why the function is named "

*Case 1*:*N = 1*

The product of*A*and*1!*is simply*A * 1! = A*.*Case 2*:*N > 1*

Since*N! = N * (N-1)!*, we then have*N! * A = (N-1)! * (N * A)*, thus justifying our implementation.

Tracing both `fast-factorial` and `fast-factorial-aux`,
we get the following:

USER(3): (trace fast-factorial fast-factorial-aux) (FAST-FACTORIAL-AUX FAST-FACTORIAL) USER(4): (fast-factorial 4) 0: (FAST-FACTORIAL 4) 1: (FAST-FACTORIAL-AUX 4 1) 2: (FAST-FACTORIAL-AUX 3 4) 3: (FAST-FACTORIAL-AUX 2 12) 4: (FAST-FACTORIAL-AUX 1 24) 4: returned 24 3: returned 24 2: returned 24 1: returned 24 0: returned 24 24

If we compare the structure of `fast-factorial` with
`list-reverse`, we notice certain patterns underlying
the use of accumulator variables in auxiliary functions:

- An auxiliary function generalizes the functionality of
the driver function by promising to compute
the function of interest and also combine the result with
the value of the accumulator variable.
In the case of
`list-reverse-aux`, our original interest were computing list reversals, but then the auxiliary function computes a more general concept, namely, that of appending an auxiliary list to some list reversal. In the case of`fast-factorial-aux`, our original interest were computing factorials, but the auxiliary function computes a more general value, namely, the product of some auxiliary number with a factorial. - At each level of recursion, the auxiliary function
reduces the problem into a smaller subproblem, and
accumulating intermediate results in the accumulator
variable. In the case of
`list-reverse-aux`, recursion is applied to the sublist`(rest`, while*L*)`(first`is*L*)`cons`'ed with*A*. In the case of`fast-factorial`, recursion is applied to*(N - 1)!*, while*N*is multiplied with*A*. - The driver function initiates the recursion by providing
an initial value for the auxiliary variable.
In the case of computing
list reversals,
`list-reverse`initializes*A*to`nil`. In the case of computing factorials,`fast-factorial`initializes*A*to 1.

Now that you understand how `fast-factorial` works,
we explain where the adjective "fast" come from ...

(defun factorial (N) "Compute the factorial of N." (if (= N 1) 1 (* N (factorial (- N 1)))))It is fair to point out that, as recursion unfolds, stack frames will have to be set up, function arguments will have to be pushed into the stack, so on and so forth, resulting in unnecessary runtime overhead not experienced by the iterative counterpart of the above

int factorial(int N) { int A = 1; while (N != 1) { A = A * N; N = N - 1; } return A; }Because of this and other excuses, programmers conclude that they could write off recursive implementations ...

Modern compilers for functional programming languages usually
implement *tail-recursive call optimizations* which
automatically translate a certain kind of linear recursion into
efficient iterations. A linear recursive function is *tail-recursive*
if the result of each recursive call is returned right away as the
value of the function. Let's examine the implementation of
`fast-factorial` again:

(defun fast-factorial (N) "A tail-recursive version of factorial." (fast-factorial-aux N 1)) (defun fast-factorial-aux (N A) "Multiply A by the factorial of N." (if (= N 1) A (fast-factorial-aux (- N 1) (* N A))))

Notice that, in `fast-factorial-aux`, there is no work
left to be done after the recursive call `(fast-factorial-aux
(- N 1) (* N A))`. Consequently, the compiler will not
create new stack frame or push arguments, but instead simply
bind `(- N 1)` to `N` and `(* N A)`
to `A`, and jump to the beginning of the function.
Such optimization effectively renders `fast-factorial`
as efficient as its iterative counterpart. Notice also
the striking structural similarity between the two.

When you implement linearly recursive functions, you are encouraged to restructure it as a tail recursion after you have fully debugged your implementation. Doing so allows the compiler to optimize away stack management code. However, you should do so only after you get the prototype function correctly implemented. Notice that the technique of accumulator variables can be used even when we are not transforming code to tail recursions. For some problems, the use of accumulator variables offers the most natural solutions.

A data type is *first-class* in a programming language when you
can pass instances of the data type as function arguments
or return them as function values. We are used to treating
numeric and Boolean values as first-class data types in
languages like Pascal and C. However, we might not be familiar to the
notion
that functions could be treated as first-class objects, that is,
functions can be passed as function arguments and returned as
function values. This unique feature of Common LISP and other
functional languages makes it easy to build very powerful abstractions.
In the remaining of this tutorial, we will look at what passing functional
arguments buys us. In the fourth tutorial, when we talk about
imperative programming in LISP, we will return to the topic of
returning functional values.

Frequently, we need to apply a transformation multiple times on the same data object. For example, we could define the following transformation:

(defun double (x) "Multiple X by 2." (* 2 x))We could compute 2

USER(10): (double (double (double (double 1)))) 16Not only is this clumsy, but it also fails to express the very idea that the same transformation is applied multiple times. It would be nice if we can repeat applying a given transformation

(defun repeat-transformation (F N X) "Repeat applying function F on object X for N times." (if (zerop N) X (repeat-transformation F (1- N) (funcall F X))))The definition follows the standard tail recursive pattern. Notice the form

To pass a the function `double` as an argument to
`repeat-transformation`, we need to annotate the function name
`double` by a *closure constructor*,
as in the following:

USER(11): (repeat-transformation (function double) 4 1) 16There is nothing magical going on, the closure constructor is just a syntax for telling Common LISP that what follows is a function rather than a local variable name. Had we not included the annotation, Common LISP will treat the name

To see how the evaluation arrives at the result 16, we could, as usual, trace the execution:

USER(12): (trace repeat-transformation) REPEAT-TRANSFORMATION USER(13): (repeat-transformation #'double 4 1) 0: (REPEAT-TRANSFORMATION #4 1) 1: (REPEAT-TRANSFORMATION # 3 2) 2: (REPEAT-TRANSFORMATION # 2 4) 3: (REPEAT-TRANSFORMATION # 1 8) 4: (REPEAT-TRANSFORMATION # 0 16) 4: returned 16 3: returned 16 2: returned 16 1: returned 16 0: returned 16 16

Notice that exponentiation is not the only use of the
`repeat-transformation` function. Let's say we want to
build a list containing 10 occurrences of the symbol `blah`.
We can do so with the help of `repeat-transformation`:

USER(30): (defun prepend-blah (L) (cons 'blah L)) PREPEND-BLAH USER(31): (repeat-transformation (function prepend-blah) 10 nil) (BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH)

Suppose we want to fetch the 7'th element of the list
`(a b c d e f g h i j)`.
Of course, we could use the
built in function `seventh` to do the job, but for the fun of it, we
could also achieve what we want in the following way:

USER(32): (first (repeat-transformation (function rest) 6 '(a b c d e f g h i j))) GBasically, we apply

(defun list-nth (N L) (first (repeat-transformation (function rest) N L)))(

As you can see, functions that accepts other functions as arguments
are very powerful abstractions. You can encapsulate generic
algorithms in such a function, and parameterize their behavior by
passing in different function arguments. We call a function that
has functional parameters (or return a function as its value)
a *higher-order* function.

One last point before we move on. The closure constructor `function`
is used very often when working with higher-order functions. Common
LISP therefore provide another equivalent syntax to reduce typing.
When we want Common LISP to interpret a name `F`
as a function, instead
of typing `(function F)`, we can also type the shorthand
`#'F`. The prefix `#'` is nothing but an alternative
syntax for the closure constructor. For example, we could enter
the following:

USER(33): (repeat-transformation #'double 4 1) 16 USER(34): (repeat-transformation #'prepend-blah 10 nil) (BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH) USER(35): (first (repeat-transformation #'rest 6 '(a b c d e f g h i j))) G

Some of the functions, like
`prepend-blah` for example, serves no other purpose
but to instantiate the generic algorithm `repeat-transformation`.
It would be tedious if we need to define it as a global function
using `defun`
before we pass it into `repeat-transformation`. Fortunately,
LISP provides a mechanism to help us define functions "in place":

USER(36): (repeat-transformation #'(lambda (L) (cons 'blah L)) 10 nil) (BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH)The first argument

Similarly, we could have computed powers as follows:

USER(36): (repeat-transformation #'(lambda (x) (* 2 x)) 4 1) 16

(apply-func-list (list #'double #'list-length #'rest) '(1 2 3))is equivalent to

(double (list-length (rest '(1 2 3))))

- 10 times the fourth element of the list
`(10 20 30 40 50)`, - the third element of the second element in the list
`((1 2) (3 4 5) (6))`, - the difference between 10 and the length of
`(a b c d e f)`, - a list containing a list containing the symbol
`blah`.

We have seen how we could iterate through a list using linear recursion. We have also seen how such recursion can be optimized if structured in a tail-recursive form. However, many of the the list processing functions look striking similar. Consider the following examples:

(defun double-list-elements (L) "Given a list L of numbers, return a list containing the elements of L multiplied by 2." (if (null L) nil (cons (double (first L)) (double-list-elements (rest L))))) (defun reverse-list-elements (L) "Given a list L of lists, return a list containing the reversal of L's members." (if (null L) nil (cons (reverse (first L)) (reverse-list-elements (rest L)))))We could come up with infinitely many more examples of this sort. Having to write a new function everytime we want to iterate through a list is both time-consuming and error-prone. The solution is to capture the generic logic of list iteration in higher-order functions, and specialize their behaviors by passing in functional arguments.

If we look at the definitions of `double-list-elements`
and `reverse-list-elements`, we see that they
apply a certain function to
the `first` element of their input, then recursively invoke
themselves to
process the `rest` of the input list, and lastly
combine the result of the two function calls using `cons`.
We could capture this
logic into the following function:

(defun mapfirst (F L) "Apply function F to every element of list L, and return a list containing the results." (if (null L) nil (cons (funcall F (first L)) (mapfirst F (rest L)))))

The functions `double-list-elements`
and `reverse-list-elements` can be replaced by the following:

USER(18): (mapfirst #'double '(1 2 3 4)) (2 4 6 8) USER(19): (mapfirst #'reverse '((1 2 3) (a b c) (4 5 6) (d e f))) ((3 2 1) (C B A) (6 5 4) (F E D))

Of course, you could also pass lambda abstractions as arguments:

USER(20): (mapfirst #'(lambda (x) (* x x)) '(1 2 3 4)) (1 4 9 16)

In fact, the higher-order function is so useful that
Common LISP defines a function `mapcar` that does
exactly what `mapfirst` is intended for:

USER(22): (mapcar #'butlast '((1 2 3) (a b c) (4 5 6) (d e f))) ((1 2) (A B) (4 5) (D E))The reason why it is called

The function `mapcar` is an example of *generic iterators*,
which capture the generic logic of iterating through a list.
If we look at what we do the most when we iterate through a list,
we find that the following kinds of iterations occurs most frequently
in our LISP programs:

*Transformation iteration*: transforming a list by systematically applying a monadic function to the elements of the list.*Search iteration*: searching for a list member that satisfies a given condition.*Filter iteration*: screening out all members that does not satisfy a given condition.

Let us begin by writing a function that returns an even element in a list of numbers:

(defun find-even (L) "Given a list L of numbers, return the leftmost even member." (if (null L) nil (if (evenp (first L)) (first L) (find-even (rest L)))))

We notice that the essential logic of searching can be extracted out into the following definition:

(defun list-find-if (P L) "Find the leftmost element of list L that satisfies predicate P." (if (null L) nil (if (funcall P (first L)) (first L) (list-find-if P (rest L)))))The function

USER(34): (list-find-if #'evenp '(1 3 5 8 11 12)) 8 USER(35): (list-find-if #'(lambda (X) (not (null X))) '(nil nil (1 2 3) (4 5))) (1 2 3)

Common LISP defines a built-in function `find-if` which is
a more general version of `list-find-if`. It can be used just
like `list-find-if`:

USER(37): (find-if #'evenp '(1 3 5 8 11 12)) 8 USER(38): (find-if #'(lambda (X) (not (null X))) '(nil nil (1 2 3) (4 5))) (1 2 3)

Given a list of lists, suppose we want to screen out all the member lists with length less than three. We could do so by the following function:

(defun remove-short-lists (L) "Remove all members of L that has length less than three." (if (null L) nil (if (< (list-length (first L)) 3) (remove-short-lists (rest L)) (cons (first L) (remove-short-lists (rest L))))))To articulate the correctness of this implementation, consider the following. The list

*Case 1*:*L*is`nil`.

Removing short lists from an empty list simply results in an empty list.*Case 2*:*L*is constructed by`cons`.

*L*has two components:`(first`and*L*)`(rest`. We have two cases: either*L*)`(first`has fewer than 3 members or it has at least 3 members.*L*)*Case 2.1*:`(first`has fewer than three elements.*L*)

Since`(first`is short, and will not appear in the result of removing short lists from*L*)*L*, the latter is equivalent to the result of removing short lists from`(rest`.*L*)*Case 2.2*:`(first`has at least three elements.*L*)

Since`(first`is not short, and will appear in the result of removing short lists from*L*)*L*, the latter is equivalent to adding`(first`to the result of removing short lists from*L*)`(rest`.*L*)

USER(17): (remove-short-lists '((1 2 3) (1 2) nil (1 2 3 4))) 0: (REMOVE-SHORT-LISTS ((1 2 3) (1 2) NIL (1 2 3 4))) 1: (REMOVE-SHORT-LISTS ((1 2) NIL (1 2 3 4))) 2: (REMOVE-SHORT-LISTS (NIL (1 2 3 4))) 3: (REMOVE-SHORT-LISTS ((1 2 3 4))) 4: (REMOVE-SHORT-LISTS NIL) 4: returned NIL 3: returned ((1 2 3 4)) 2: returned ((1 2 3 4)) 1: returned ((1 2 3 4)) 0: returned ((1 2 3) (1 2 3 4)) ((1 2 3) (1 2 3 4))

Alternatively, we could have removed short lists using Common LISP's
built-in function `remove-if`:

USER(19): (remove-if #'(lambda (X) (< (list-length X) 3)) '((1 2 3) (1 2) nil (1 2 3 4))) ((1 2 3) (1 2 3 4))

The function `(remove-if P L)` constructs
a new version of list

USER(21): (remove-if #'(lambda (X) (zerop (rem x 2))) '(3 6 8 9 10 13 15 18)) (3 9 13 15)Without

(defun remove-even (L) "Remove all members of L that is an even number." (if (null L) nil (if (zerop (rem (first L) 2)) (remove-even (rest L)) (cons (first L) (remove-even (rest L))))))

We could actually implement `list-intersection` using
`remove-if` and lambda abstraction:

(defun list-intersection (L1 L2) "Compute the intersection of lists L1 and L2." (remove-if #'(lambda (X) (not (member X L2))) L1))In the definition above, the lambda abstraction evaluates to a predicate that returns true if its argument is not a member of

The functions we have seen so far return a single value, but some
LISP functions return two or more values. For example, if two arguments
*number* and *divisor* are passed to the `floor`
function, it returns two values, the quotient *q* and the
remainder *r* so that *number = divisor * q + r*.

USER(11): (floor 17 5) 3 2 USER(12): (floor -17 5) -4 3Regular binding constructs like

USER(13): (let ((x (floor 17 5))) x) 3One can use the

USER(14): (multiple-value-bind (x y) (floor 17 5) (+ x y)) 5In the above expression,

One may also write LISP functions that return multiple values:

(defun order (a b) "Return two values: (min a b) and (max a b)." (if (>= a b) (values b a) (values a b)))The

For more information about LISP constructs for handling multiple values, consult section 7.10 of CLTL2.