LISP Tutorial 2: Advanced Functional Programming in LISP

Auxiliary Functions and Accumulator Variables

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 L:

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)

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)
    (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 x1 x2 ... xn) is just a shorthand for (cons x1 (cons x2 ... (cons xn nil) ... )). So, the expression (list (first L)) in the listing above returns a singleton list containing the first element of L.

So, why does (slow-list-reverse L) returns the reversal of L? The list L is constructed either by nil or by cons:

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

USER(3): (trace 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: 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 list-append:
USER(9): (trace 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: 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 N element, slow-list-reverse makes O(N) recursive calls, with each level of recursionl involving a call to the linear-time function list-append. The result is that slow-list-reverse is an O(N2) function.

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)
    (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 A to the reversal of list L. By passing nil as A to list-reverse-aux, the driver function list-reverse obtains the reversal of L.

Let us articulate why (list-reverse-aux L A) correctly appends A to the reversal of list L. Again, we know that either L is nil or it is constructed by cons:

Tracing both list-reverse and list-reverse-aux, we get the following:
USER(17): (trace 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.

Factorial Revisited

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)
    (fast-factorial-aux (- N 1) (* N A))))
Let us defer the explanation of why the function is named "fast-factorial", and treat it as just another way to implement factorial. Notice the structural similarity between this pair of functions and those for computing list reversal. The auxiliary function (fast-factorial-aux N A) computes the product of A and the N'th factorial. The driver function computes N! by calling fast-factorial-aux with A set to 1. Now, the correctness of the auxiliary function (i.e. that (fast-factorial-aux N A) indeed returns the product of N! and A) can be established as follows. N is either one or larger than one.

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

USER(3): (trace fast-factorial fast-factorial-aux)  
USER(4): (fast-factorial 4)
     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

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

  1. 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.
  2. 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 L), while (first L) is cons'ed with A. In the case of fast-factorial, recursion is applied to (N - 1)!, while N is multiplied with A.
  3. 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 ...

Tail Recursions

Recursive functions are usually easier to reason about. Notice how we articulate the correctness of recursive functions in this and the previous tutorial. However, some naive programmers complain that recursive functions are slow when compared to their iterative counter parts. For example, consider the original implementation of factorial we saw in the previous tutorial:
(defun factorial (N)
  "Compute the factorial of N."
  (if (= N 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 factorial function:
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)
    (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.

Exercise: Recall that the N'th triangular number is defined to be 1 + 2 + 3 + ... + N. Give a tail-recursive implementation of the function (fast-triangular N) which returns the N'th triangular number.

Exercise: Give a tail-recursive implementation of the function (fast-power B E) that raises B to the power E (assuming that both B and E are non-negative integers).

Exercise: Give a tail-recursive implementation of the function (fast-list-length L), which returns the length of a given list L.

Functions as First-Class Objects

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 24 by applying the double transformation 4 times on 1:
USER(10): (double (double (double (double 1))))
Not 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 F on X for N times by simply writing (repeat-transformation F N X). The following function does just that:
(defun repeat-transformation (F N X)
  "Repeat applying function F on object X for N times."
  (if (zerop N)
    (repeat-transformation F (1- N) (funcall F X))))
The definition follows the standard tail recursive pattern. Notice the form (funcall F X). Given a function F and objects X1 X2 ... Xn, the form (funcall F X1 X2 ... Xn) invoke the function F with arguments X1, X2, ..., Xn. The variable N is a counter keeping track of the remaining number of times we need to apply function F to the accumulator variable X.

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)
There 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 double as a variable name, and then report an error since the name double is not defined.

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

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

Higher-Order Functions

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))
USER(31): (repeat-transformation (function prepend-blah) 10 nil)

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)))
Basically, we apply rest six times before apply first to get the seventh element. In fact, we could have defined the function list-nth (see previous tutorial) in the following way:
(defun list-nth (N L)
  (first (repeat-transformation (function rest) N L)))
(list-nth numbers the member of a list from zero onwards.)

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)
USER(34): (repeat-transformation #'prepend-blah 10 nil)
USER(35): (first (repeat-transformation #'rest 6 '(a b c d e f g h i j)))

Lambda Expressions

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)
The first argument (lambda (L) (cons 'blah L)) is a lambda expression. It designates an anonymous function (nameless function) with one parameter L, and it returns as a function value (cons 'blah L). We prefix the lambda expression with the closure constructor #' since we want Common LISP to interpret the argument as a function rather than a call to a function named lambda.

Similarly, we could have computed powers as follows:

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

Exercise: Define a function (apply-func-list L X) so that, given a list L of functions and an object X, apply-func-list applies the functions in L to X in reversed order. For example, the following expression
(apply-func-list (list #'double #'list-length #'rest) '(1 2 3))
is equivalent to
(double (list-length (rest '(1 2 3))))

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

Iterating Through a List

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)
    (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)
    (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)
    (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 mapcar is that the function first was called car in some older dialects of LISP (and rest was called cdr in those dialects; Common LISP still supports car and cdr but we strongly advice you to stick with the more readable first and rest). We suggest you to consider using mapcar whenever you are tempted to write your own list-iterating functions.

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:

  1. Transformation iteration: transforming a list by systematically applying a monadic function to the elements of the list.
  2. Search iteration: searching for a list member that satisfies a given condition.
  3. Filter iteration: screening out all members that does not satisfy a given condition.
As we have already seen, mapcar implements the generic algorithm for performing transformation iteration. In the following, we will look at the analogous of mapcar for the remaining iteration categories.

Search Iteration

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)
    (if (evenp (first L))
        (first L)
      (find-even (rest L)))))

Exercise: Implement a function that, when given a list L of lists, return a non-empty member of 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)
    (if (funcall P (first L))
        (first L)
      (list-find-if P (rest L)))))
The function list-find-if examines the elements of L one by one, and return the first one that satisfies predicate P. The function can be used for locating even or non-nil members in a list:
USER(34): (list-find-if #'evenp '(1 3 5 8 11 12))
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))
USER(38): (find-if #'(lambda (X) (not (null X))) '(nil nil (1 2 3) (4 5)))
(1 2 3)

Exercise: Use find-if to define a function that searches among a list of lists for a member that has length at least 3.

Exercise: Use find-if to define a function that searches among a list of lists for a member that contains an even number of elements.

Exercise: Use find-if to define a function that searches among a list of numbers for a member that is divisible by three.

Filter Iteration

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)
    (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 L is either nil or constructed by cons. A typical execution trace is the following:
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: 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 L that contains only members not satisfying predicate P. For example, we can remove all even members from the list (3 6 8 9 10 13 15 18) by the following:

USER(21): (remove-if #'(lambda (X) (zerop (rem x 2))) '(3 6 8 9 10 13 15 18))
(3 9 13 15)
Without remove-if, we would end up having to implement a function like the following:
(defun remove-even (L)
  "Remove all members of L that is an even number."
  (if (null L)
    (if (zerop (rem (first L) 2))
        (remove-even (rest L))
      (cons (first L) (remove-even (rest L))))))

Exercise: Demonstrate the correctness of remove-even using arguments you have seen in this tutorial.

Exercise: Observe the recurring pattern in remove-short-lists and remove-even, and implement your own version of remove-if.

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 L2. Therefore, the remove-if expression removes all elements of L1 that is not a member of L2. This precisely gives us the intersection of L1 and L2.

Exercise: Use remove-if and lambda abstractions to implement list-difference.

Exercise: Look up the functionality of remove-if-not in CTRL2. Re-implement list-intersection using remove-if-not and lambda abstraction.

Functions Returning Multiple Values

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)
USER(12): (floor -17 5)
Regular binding constructs like let and let* only allows us to catch the first returned value of a multiple-valued function, as the following example illustrates:
USER(13): (let ((x (floor 17 5))) x)
One can use the multiple-value-bind to receive the results of a multiple-valued function:
USER(14): (multiple-value-bind (x y) (floor 17 5) 
            (+ x y))
In the above expression, (x y) is the list of variables binding to the returned values, (floor 17 5) is the expression generating multiple results. Binding the two values of (floor 17 5) to x and y, LISP then evaluates the expression (+ x y).

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 values special form returns its arguments as multiple values.

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

Exercise: Implement a tail-recursive function (list-min-max L) that returns two values: the minimum and maximum members of a list L of numbers.