# Basic LISP Programming

# LISP Tutorial 1: Basic LISP Programming

## LISP Expressions

When you start up the Common LISP environment, you should see a prompt, which means that LISP is waiting for you to enter a LISP expression. In the environment I am using, it looks like the following:

USER(1):

The Common LISP environment follows the algorithm below when interacting with users:

loop read in an expression from the console; evaluate the expression; print the result of evaluation to the console; end loop.

Common LISP reads in an expression, evaluates it, and then prints out the result. For example, if you want to compute the value of *(2 * cos(0) * (4 + 6))*, you type in:

USER(1): (* 2 (cos 0) (+ 4 6))

Common LISP replies:

20.0

before prompting you to enter the next expression. Several things are worth noting:

- LISP expressions are composed of
*forms*. The most common LISP form is*function application*. LISP represents a function call*f(x)*as`(f x)`. For example,*cos(0)*is written as`(cos 0)`. - LISP expressions are case-insensitive. It makes no difference whether we type
`(cos 0)`or`(COS 0)`. - Similarly, “
`+`” is the name of the addition function that returns the sum of its arguments. - Some functions, like “
`+`” and “`*`“, could take an arbitrary number of arguments. In our example, “`*`” took three arguments. It could as well take 2 arguments, as in “`(* 2 3)`“, or 4 arguments, as in “`(* 2 3 4 5)`“. - In general, a function application form looks like
`(`. As in many programming languages (e.g. C/C++), LISP evaluates function calls in*function**argument*_{1}*argument*..._{2}*argument*)_{n}*applicative order*, which means that all the argument forms are evaluated before the function is invoked. That is to say, the argument forms`(cos 0)`and`(+ 4 6)`are respectively evaluated to the values*1*and*10*before they are passed as arguments to the`*`function. Some other forms, like the*conditionals*we will see later, are not evaluated in applicative order. - Numeric values like
`4`and`6`are called*self-evaluating forms*: they evaluate to themselves. To evaluate`(+ 4 6)`in applicative order, the forms`4`and`6`are respectively evaluated to the values*4*and*6*before they are passed as arguments to the`+`function.

Complex arithmatic expressions can be constructed from built-in functions like the following:

Numeric Functions | Meaning |
---|---|

(+ x _{1}x ... _{2}x)_{n} |
The sum of x, _{1}x, …, _{2}x_{n} |

(* x _{1}x ... _{2}x)_{n} |
The product of x, _{1}x, …, _{2}x_{n} |

(- x y) |
Subtract y from x |

(/ x y) |
Divide x by y |

(rem x y) |
The remainder of dividing x by y |

(abs x) |
The absolute value of x |

(max x _{1}x ... _{2}x)_{n} |
The maximum of x, _{1}x, …, _{2}x_{n} |

(min x _{1}x ... _{2}x)_{n} |
The minimum of x, _{1}x, …, _{2}x_{n} |

Common LISP has a rich set of pre-defined numerical functions. For a complete coverage, consult Chapter 12 of the book, *Common LISP, The Language (2nd Edition)* (CLTL2) by Guy Steele. In general, we will not be able to cover all aspects of Common LISP in this tutorial. Adventurous readers should consult CLTL2 frequently for more in-depth explanation of various features of the language.

**Exercise:** Look up pages 376-378 of CLTL2 and find out what the functions `floor` and `ceiling` are for. Then, find out the subtle difference between `mod` and `rem`.

## Defining Functions

Evaluating expressions is not very interesting. We would like to build expression abstractions that could be reused in the future. For example, we could type in the following:

USER(2): (defun double (x) (* x 2)) DOUBLE

In the above, we define a function named `double`, which returns two times the value of its input argument *x*. We can then test-drive the function as below:

USER(3): (double 3) 6 USER(4): (double 7) 14

## Editing, Loading and Compiling LISP Programs

Most of the functions we would like to write is going to be a lot longer than the `double` function. When working with complex programs, it is usually desirable to edit the program with an editor, fully debug the code, and then compile it for faster performance. Use your favorite text editor (mine is `emacs`) to key in the following function definition:

;;; testing.lisp ;;; by Philip Fong ;;; ;;; Introductory comments are preceded by ";;;" ;;; Function headers are preceded by ";;" ;;; Inline comments are introduced by ";" ;;; ;; ;; Triple the value of a number ;; (defun triple (X) "Compute three times X." ; Inline comments can (* 3 X)) ; be placed here. ;; ;; Negate the sign of a number ;; (defun negate (X) "Negate the value of X." ; This is a documentation string. (- X))

Save the above in the file `testing.lisp`. Now load the definition into the LISP environment by typing:

USER(5): (load "testing.lisp") ; Loading ./testing.lisp T

Let us try to see if they are working properly.

USER(6): (triple 2) 6 USER(7): (negate 3) -3

When functions are fully debugged, we can also compile them into binaries:

USER(8): (compile-file "testing.lisp")

Depending on whether your code is well-formed, and what system you are using, some compilation messages will be generated. The compiled code can be loaded into the LISP environment later by using the following:

USER(9): (load "testing") ; Fast loading ./testing.fasl T

## Control Stuctures: Recursions and Conditionals

Now that we are equipped with all the tools for developing LISP programs, let us venture into something more interesting. Consider the definition of factorials:

n! = 1 |
if n = 1 |
||

n! = n * (n – 1)! |
if n > 1 |

We can implement a function to compute factorials using recursion:

(defun factorial (N) "Compute the factorial of N." (if (= N 1) 1 (* N (factorial (- N 1)))))

The `if` form checks if `N` is one, and returns one if that is the case, or else returns *N * (N – 1)!*. Several points are worth noting:

- The condition expression
`(= N 1)`is a relational expression. It returns boolean values`T`or`NIL`. In fact, LISP treats`NIL`as false, and everything else as true. Other relational operators include the following:

Relational Operators Meaning `(=`*x**y*)*x*is equal to*y*`(/=`*x**y*)*x*is not equal to*y*`(<`*x**y*)*x*is less than*y*`(>`*x**y*)*x*is greater than*y*`(<=`*x**y*)*x*is no greater than*y*`(>=`*x**y*)*x*is no less than*y* - The
`if`form is not a*strict function*(strict functions evaluate their arguments in applicative order). Instead, the`if`form evaluates the condition`(= N 1)`before further evaluating the other two arguments. If the condition evaluates to true, then only the second argument is evaluated, and its value is returned as the value of the`if`form. Otherwise, the third argument is evaluated, and its value is returned. Forms that are not strict functions are called*special forms*. - The function is recursive. The definition of
`factorial`involves invocation of itself. Recursion is, for now, our only mechanism for producing looping behavior. Specifically, the kind of recursion we are looking at is called*linear recursion*, in which the function may make at most one recursive call from any level of invocation.

To better understand the last point, we can make use of the debugging facility `trace` (do not compile your code if you want to use `trace`):

USER(11): (trace factorial) (FACTORIAL) USER(12): (factorial 4) 0: (FACTORIAL 4) 1: (FACTORIAL 3) 2: (FACTORIAL 2) 3: (FACTORIAL 1) 3: returned 1 2: returned 2 1: returned 6 0: returned 24 24

Tracing `factorial`allows us to examine the recursive invocation of the function. As you can see, at most one recursive call is made from each level of invocation.

**Exercise:** The *N*‘th *triangular number* is defined to be *1 + 2 + 3 + … + N*. Alternatively, we could give a recursive definition of triangular number as follows:

T(n) = 1 |
if n = 1 |
||

T(n) = n + T(n-1) |
if n > 1 |

Use the recursive definition to help you implement a linearly recursive function `(triangular N)` that returns the

*N*‘th triangular number. Enter your function definition into a text file. Then load it into LISP. Trace the execution of

`(triangular 6)`.

**Exercise:** Write down a recursive definition of *B ^{E}* (assuming that both

*B*and

*E*are non-negative integers). Then implement a linearly recursive function

`(power`that computes

*B**E*)*B*. Enter your function definition into a text file. Then load it into LISP. Trace the execution of

^{E}`(power 2 6)`.

## Multiple Recursions

Recall the definition of Fibonacci numbers:

Fib(n) = 1 |
for n = 0 or n = 1 |
||

Fib(n) = Fib(n-1) + Fib(n-2) |
for n > 1 |

This definition can be directly translated to the following LISP code:

(defun fibonacci (N) "Compute the N'th Fibonacci number." (if (or (zerop N) (= N 1)) 1 (+ (fibonacci (- N 1)) (fibonacci (- N 2)))))

Again, several observations can be made. First, the function call `(zerop N)` tests if `N` is zero. It is merely a shorthand for `(= N 0)`. As such, `zerop` returns either `T` or `NIL`. We call such a boolean function a *predicate*, as indicated by the suffix `p`. Some other built-in shorthands and predicates are the following:

Shorthand | Meaning |
---|---|

(1+ x) |
(+ x 1) |

(1- x) |
(- x 1) |

(zerop x) |
(= x 0) |

(plusp x) |
(> x 0) |

(minusp x) |
(< x 0) |

(evenp x) |
(= (rem x 2) 0) |

(oddp x) |
(/= (rem x 2) 0) |

Second, the `or` form is a logical operator. Like `if`, `or` is not a strict function. It evaluates its arguments from left to right, returning non-`NIL` immediately if it encounters an argument that evaluates to non-`NIL`. It evaluates to `NIL` if all tests fail. For example, in the expression `(or t (= 1 1))`, the second argument `(= 1 1)` will not be evaluated. Similar logical connectives are listed below:

Logical Operators | Meaning |
---|---|

(or x _{1}x ... _{2}x)_{n} |
Logical or |

(and x _{1}x ... _{2}x)_{n} |
Logical and |

(not x) |
Logical negation |

Third, the function definition contains two self references. It first recursively evaluates `(fibonacci (- N 1))` to compute *Fib(N-1)*, then evaluates `(fibonacci (- N 2))` to obtain *Fib(N-2)*, and lastly return their sum. This kind of recursive definitiion is called *double recursion* (more generally, *multiple recursion*). Tracing the function yields the following:

USER(20): (fibonacci 3) 0: (FIBONACCI 3) 1: (FIBONACCI 2) 2: (FIBONACCI 1) 2: returned 1 2: (FIBONACCI 0) 2: returned 1 1: returned 2 1: (FIBONACCI 1) 1: returned 1 0: returned 3 3

Note that in each level, there could be up to two recursive invocations.

**Exercise**: The Binomial Coefficient *B(n, r)* is the coefficient of the term *x ^{r}* in the binormial expansion of

*(1 + x)*. For example,

^{n}*B(4, 2) = 6*because

*(1+x)*. The Binomial Coefficient can be computed using the

^{4}= 1 + 4x + 6x^{2}+ 4x^{3}+ x^{4}*Pascal Triangle*formula:

B(n, r) = 1 |
if r = 0 or r = n |
||

B(n, r) = B(n-1, r-1) + B(n-1, r) |
otherwise |

Implement a doubly recursive function `(binomial N R)` that computes the binomial coefficient

*B(N, R)*.

Some beginners might find nested function calls like the following very difficult to understand:

(+ (fibonacci (- N 1)) (fibonacci (- N 2)))))

To make such expressions easier to write and comprehend, one could define local name bindings to represent intermediate results:

(let ((F1 (fibonacci (- N 1))) (F2 (fibonacci (- N 2)))) (+ F1 F2))

The `let` special form above defines two local variables, `F1` and `F2`, which binds to *Fib(N-1)* and *Fib(N-2)* respectively. Under these local bindings, `let` evaluates `(+ F1 F2)`. The `fibonacci`function can thus be rewritten as follows:

(defun fibonacci (N) "Compute the N'th Fibonacci number." (if (or (zerop N) (= N 1)) 1 (let ((F1 (fibonacci (- N 1))) (F2 (fibonacci (- N 2)))) (+ F1 F2))))

Notice that `let` creates all bindings in parallel. That is, both `(fibonacci (- N 1))` and `(fibonacci (- N 2))` are evaluated first, and then they are bound to `F1` and `F2`. This means that the following LISP code will not work:

(let ((x 1) (y (* x 2))) (+ x y))

LISP will attempt to evaluate the right hand sides first before the bindings are established. So, the expression `(* x 2)` is evaluated before the binding of `x` is available. To perform sequential binding, use the `let*`form instead:

(let* ((x 1) (y (* x 2))) (+ x y))

LISP will bind `1` to `x`, then evaluate `(* x 2)` before the value is bound to `y`.

## Lists

Numeric values are not the only type of data LISP supports. LISP is designed for symbolic computing. The fundamental LISP data structure for supporting symbolic manipulation are lists. In fact, LISP stands for “LISt Processing.”

Lists are containers that supports sequential traversal. List is also a *recursive data structure*: its definition is recursive. As such, most of its traversal algorithms are recursive functions. In order to better understand a recursive abstract data type and prepare oneself to develop recursive operations on the data type, one should present the data type in terms of its *constructors*, *selectors* and *recognizers*.

Constructors are forms that create new instances of a data type (possibly out of some simpler components). A list is obtained by evaluating one of the following constructors:

`nil`: Evaluating`nil`creates an*empty*list;`(cons`: Given a LISP object*x**L*)*x*and a list*L*, evaluating`(cons`creates a list containing*x**L*)*x*followed by the elements in*L*.

Notice that the above definition is inherently recursive. For example, to construct a list containing 1 followed by 2, we could type in the expression:

USER(21): (cons 1 (cons 2 nil)) (1 2)

LISP replies by printing `(1 2)`, which is a more readable representation of a list containing 1 followed by 2. To understand why the above works, notice that `nil` is a list (an empty one), and thus `(cons 2 nil)` is also a list (a list containing 1 followed by nothing). Applying the second constructor again, we see that `(cons 1 (cons 2 nil))`is also a list (a list containing 1 followed by 2 followed by nothing).

Typing `cons` expressions could be tedious. If we already know all the elements in a list, we could enter our list as *list literals*. For example, to enter a list containing all prime numbers less than 20, we could type in the following expression:

USER(22): (quote (2 3 5 7 11 13 17 19)) (2 3 5 7 11 13 17 19)

Notice that we have quoted the list using the `quote` special form. This is necessary because, without the quote, LISP would interpret the expression `(2 3 5 7 11 13 17 19)` as a function call to a function with name “2” and arguments 3, 5, …, 19 The `quote` is just a syntactic device that instructs LISP not to evaluate the a form in applicative order, but rather treat it as a literal. Since quoting is used frequently in LISP programs, there is a shorthand for `quote`:

USER(23): '(2 3 5 7 11 13 17 19) (2 3 5 7 11 13 17 19)

The quote symbol `'` is nothing but a syntactic shorthand for `(quote ...)`.

The second ingredient of an abstract data type are its selectors. Given a composite object constructed out of several components, a selector form returns one of its components. Specifically, suppose a list *L _{1}* is constructed by evaluating

`(cons`, where

*x**L*)_{2}*x*is a LISP object and

*L*is a list. Then, the selector forms

_{2}`(first`and

*L*)_{1}`(rest`evaluate to

*L*)_{1}*x*and

*L*respectively, as the following examples illustrate:

_{2}USER(24): (first '(2 4 8)) 2 USER(25): (rest '(2 4 8)) (4 8) USER(26): (first (rest '(2 4 8))) 4 USER(27): (rest (rest '(2 4 8))) (8) USER(28): (rest (rest (rest '(8)))) NIL

Finally, we look at recognizers, expressions that test how an object is constructed. Corresponding to each constructor of a data type is a recognizer. In the case of list, they are `null` for `nil` and `consp` for `cons`. Given a list *L*, `(null L)` returns

`t`iff

*L*is

`nil`, and

`(consp`returns

*L*)`t`iff

*L*is constructed from

`cons`.

USER(29): (null nil) T USER(30): (null '(1 2 3)) NIL USER(31): (consp nil) NIL USER(32): (consp '(1 2 3)) T

Notice that, since lists have only two constructors, the recognizers are complementary. Therefore, we usually need only one of them. In our following discussion, we use only `null`.

## Structural Recursion with Lists

As we have promised, understanding how the constructors, selectors and recognizers of lists work helps us to develop recursive functions that traverse a list. Let us begin with an example. The LISP built-in function `list-length` counts the number of elements in a list. For example,

USER(33): (list-length '(2 3 5 7 11 13 17 19)) 8

Let us try to see how such a function can be implemented recursively. A given list *L* is created by either one of the two constructors, namely `nil` or a `cons`:

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

The length of an empty list is zero.*Case 2*:*L*is constructed by`cons`.

Then*L*is composed of two parts, namely,`(first`and*L*)`(rest`. In such case, the length of*L*)*L*can be obtained inductively by adding 1 to the length of`(rest`.*L*)

Formally, we could implement our own version of `list-length` as follows:

(defun recursive-list-length (L) "A recursive implementation of list-length." (if (null L) 0 (1+ (recursive-list-length (rest L)))))

Here, we use the recognizer `null` to differentiate how *L* is constructed. In case *L* is `nil`, we return 0 as its length. Otherwise, *L* is a `cons`, and we return 1 plus the length of `(rest L)`. Recall that

`(1+`is simply a shorthand for

*n*)`(+`.

*n*1)Again, it is instructive to use the trace facilities to examine the unfolding of recursive invocations:

USER(40): (trace recursive-list-length) (RECURSIVE-LIST-LENGTH) USER(41): (recursive-list-length '(2 3 5 7 11 13 17 19)) 0: (RECURSIVE-LIST-LENGTH (2 3 5 7 11 13 17 19)) 1: (RECURSIVE-LIST-LENGTH (3 5 7 11 13 17 19)) 2: (RECURSIVE-LIST-LENGTH (5 7 11 13 17 19)) 3: (RECURSIVE-LIST-LENGTH (7 11 13 17 19)) 4: (RECURSIVE-LIST-LENGTH (11 13 17 19)) 5: (RECURSIVE-LIST-LENGTH (13 17 19)) 6: (RECURSIVE-LIST-LENGTH (17 19)) 7: (RECURSIVE-LIST-LENGTH (19)) 8: (RECURSIVE-LIST-LENGTH NIL) 8: returned 0 7: returned 1 6: returned 2 5: returned 3 4: returned 4 3: returned 5 2: returned 6 1: returned 7 0: returned 8 8

The kind of recursion we see here is called *structural recursion*. Its standard pattern is as follows. To process an instance *X* of a recursive data type:

- Use the recognizers to determine how
*X*is created (i.e. which constructor creates it). In our example, we use`null`to decide if a list is created by`nil`or`cons`. - For instances that are atomic (i.e. those created by constructors with no components), return a trivial value. For example, in the case when a list is
`nil`, we return zero as its length. - If the instance is composite, then use the selectors to extract its components. In our example, we use
`first`and`rest`to extract the two components of a nonempty list. - Following that, we apply recursion on one or more components of
*X*. For instance, we recusively invoked`recursive-list-length`on`(rest L)`. - Finally, we use either the constructors or some other functions to combine the result of the recursive calls, yielding the value of the function. In the case of
`recursive-list-length`, we return one plus the result of the recursive call.

**Exercise**: Implement a linearly recursive function `(sum L)` which computes the sum of all numbers in a list

*L*. Compare your solution with the standard pattern of structural recursion.

Sometimes, long traces like the one for list-length may be difficult to read on a terminal screen. Common LISP allows you to capture screen I/O into a file so that you can, for example, produce a hard copy for more comfortable reading. To capture the trace of executing `(recursive-list-length '(2 3 5 7 11 13 17 19))`, we use the `dribble` command:

USER(42): (dribble "output.txt") dribbling to file "output.txt" NIL USER(43): (recursive-list-length '(2 3 5 7 11 13 17 19)) 0: (RECURSIVE-LIST-LENGTH (2 3 5 7 11 13 17 19)) 1: (RECURSIVE-LIST-LENGTH (3 5 7 11 13 17 19)) 2: (RECURSIVE-LIST-LENGTH (5 7 11 13 17 19)) 3: (RECURSIVE-LIST-LENGTH (7 11 13 17 19)) 4: (RECURSIVE-LIST-LENGTH (11 13 17 19)) 5: (RECURSIVE-LIST-LENGTH (13 17 19)) 6: (RECURSIVE-LIST-LENGTH (17 19)) 7: (RECURSIVE-LIST-LENGTH (19)) 8: (RECURSIVE-LIST-LENGTH NIL) 8: returned 0 7: returned 1 6: returned 2 5: returned 3 4: returned 4 3: returned 5 2: returned 6 1: returned 7 0: returned 8 8 USER(44): (dribble)

The form `(dribble "output.txt")` instructs Common LISP to begin capturing all terminal I/O into a file called `output.txt`. The trailing `(dribble)` form instructs Common LISP to stop I/O capturing, and closes the file `output.txt`. If we examine `output.txt`, we will see the following:

dribbling to file "output.txt" NIL USER(43): (recursive-list-length '(2 3 5 7 11 13 17 19)) 0: (RECURSIVE-LIST-LENGTH (2 3 5 7 11 13 17 19)) 1: (RECURSIVE-LIST-LENGTH (3 5 7 11 13 17 19)) 2: (RECURSIVE-LIST-LENGTH (5 7 11 13 17 19)) 3: (RECURSIVE-LIST-LENGTH (7 11 13 17 19)) 4: (RECURSIVE-LIST-LENGTH (11 13 17 19)) 5: (RECURSIVE-LIST-LENGTH (13 17 19)) 6: (RECURSIVE-LIST-LENGTH (17 19)) 7: (RECURSIVE-LIST-LENGTH (19)) 8: (RECURSIVE-LIST-LENGTH NIL) 8: returned 0 7: returned 1 6: returned 2 5: returned 3 4: returned 4 3: returned 5 2: returned 6 1: returned 7 0: returned 8 8 USER(44): (dribble)

## Symbols

The lists we have seen so far are lists of numbers. Another data type of LISP is *symbols*. A symbol is simply a sequence of characters:

USER(45): 'a ; LISP is case-insensitive. A USER(46): 'A ; 'a and 'A evaluate to the same symbol. A USER(47): 'apple2 ; Both alphanumeric characters ... APPLE2 USER(48): 'an-apple ; ... and symbolic characters are allowed. AN-APPLE USER(49): t ; Our familiar t is also a symbol. T USER(50): 't ; In addition, quoting is redundant for t. T USER(51): nil ; Our familiar nil is also a symbol. NIL USER(52): 'nil ; Again, it is self-evaluating. NIL

With symbols, we can build more interesting lists:

USER(53): '(how are you today ?) ; A list of symbols. (HOW ARE YOU TODAY ?) USER(54): '(1 + 2 * x) ; A list of symbols and numbers. (1 + 2 * X) USER(55): '(pair (2 3)) ; A list containing 'pair and '(2 3). (pair (2 3))

Notice that the list `(pair (2 3))`has length 2:

USER(56): (recursive-list-length '(pair (2 3))) 2

Notice also the result of applying accessors:

USER(57): (first '(pair (2 3))) PAIR USER(58): (rest '(pair (2 3))) ((2 3))

Lists containing other lists as members are difficult to understand for beginners. Make sure you understand the above example.

## Example: `nth`

LISP defines a function `(nth N L)` that returns the

*N*‘th member of list

*L*(assuming that the elements are numbered from zero onwards):

USER(59): (nth 0 '(a b c d)) A USER(60): (nth 2 '(a b c d)) C

We could implement our own version of `nth` by linear recursion. Given *N* and *L*, either *L* is `nil` or it is constructed by `cons`.

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

Accessing the*N*‘th element is an undefined operation, and our implementation should arbitrarily return`nil`to indicate this.*Case 2*:*L*is constructed by a`cons`.

Then*L*has two components:`(first`and*L*)`(rest`. There are two subcases: either*L*)*N = 0*or*N > 0*:*Case 2.1*:*N = 0*.

The zeroth element of*L*is simply`(first`.*L*)*Case 2.2*:*N > 0*.

The*N*‘th member of*L*is exactly the*(N-1)*‘th member of`(rest`.*L*)

The following code implements our algorithm:

(defun list-nth (N L) "Return the N'th member of a list L." (if (null L) nil (if (zerop N) (first L) (list-nth (1- N) (rest L)))))

Recall that `(1- N)` is merely a shorthand for `(- N 1)`. Notice that both our implementation and its correctness argument closely follow the standard pattern of structural recursion. Tracing the execution of the function, we get:

USER(61): (list-nth 2 '(a b c d)) 0: (LIST-NTH 2 (A B C D)) 1: (LIST-NTH 1 (B C D)) 2: (LIST-NTH 0 (C D)) 2: returned C 1: returned C 0: returned C C

**Exercise**: LISP has a built-in function `(last L)` that returns a the last

`cons`structure in a given list

*L*.

USER(62): (last '(a b c d)) (d) USER(63): (last '(1 2 3)) (3)

Implement your own version of `last` using linear recursion. You may assume that `(last nil)` returns `nil`. Compare your implementation with the standard pattern of structural recursion.

Notice that we have a standard if-then-else-if structure in our implementation of `list-nth`. Such logic can alternatively be implemented using the `cond` special form.

(defun list-nth (n L) "Return the n'th member of a list L." (cond ((null L) nil) ((zerop n) (first L)) (t (list-nth (1- n) (rest L)))))

The `cond` form above is evaluated as follows. The condition `(null L)` is evaluated first. If the result is true, then `nil` is returned. Otherwise, the condition `(zerop n)` is evaluated. If the condition holds, then the value of `(first L)` is returned. In case neither of the conditions holds, the value of `(list-nth (1- n) (rest L))`is returned.

**Exercise**: Survey CLTL2 section 7.6 (pages 156-161) and find out what other conditional special forms are available in Common LISP. Do you know when the special forms `when` and `unless` should be used instead of `if`?

## Example: `member`

LISP defines a function `(member E L)` that returns non-NIL if

*E*is a member of

*L*.

USER(64): (member 'b '(perhaps today is a good day to die)) ; test fails NIL USER(65): (member 'a '(perhaps today is a good day to die)) ; returns non-NIL '(a good day to die)

We implement our own recursive version as follows:

(defun list-member (E L) "Test if E is a member of L." (cond ((null L) nil) ((eq E (first L)) t) (t (list-member E (rest L)))))

The correctness of the above implementation is easy to justify. The list *L* is either constructed by *nil* or by a call to *cons*:

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

*L*is empty, and there is no way*E*is in*L*.*Case 2*:*L*is constructed by`cons`

Then it has two components:`(first`and*L*)`(rest`. There are two cases, either*L*)`(first`is*L*)*E*itself, or it is not.*Case 2.1*:*E*equals`(first`.*L*)

This means that*E*is a member of*L*,*Case 2.2*:*E*does not equal`(first`.*L*)

Then*E*is a member of*L*iff*E*is a member of`(rest`.*L*)

Tracing the execution of `list-member`, we get the following:

USER(70): (list-member 'a '(perhaps today is a good day to die)) 0: (LIST-MEMBER A (PERHAPS TODAY IS A GOOD DAY TO DIE)) 1: (LIST-MEMBER A (TODAY IS A GOOD DAY TO DIE)) 2: (LIST-MEMBER A (IS A GOOD DAY TO DIE)) 3: (LIST-MEMBER A (A GOOD DAY TO DIE)) 3: returned T 2: returned T 1: returned T 0: returned T T

In the implementation of `list-member`, the function call `(eq x y)` tests if two symbols are the same. In fact, the semantics of this test determines what we mean by a member:

USER(71): (list-member '(a b) '((a a) (a b) (a c))) 0: (LIST-MEMBER (A B) ((A A) (A B) (A C))) 1: (LIST-MEMBER (A B) ((A B) (A C))) 2: (LIST-MEMBER (A B) ((A C))) 3: (LIST-MEMBER (A B) NIL) 3: returned NIL 2: returned NIL 1: returned NIL 0: returned NIL NIL

In the example above, we would have expected a result of `t`. However, since `'(a b)` does not `eq` another copy of `'(a b)` (they are not the same symbol), `list-member` returns `nil`. If we want to account for list equivalence, we could have used the LISP built-in function `equal` instead of `eq`. Common LISP defines the following set of predicates for testing equality:

(= x y) |
True if x and y evaluate to the same number. |

(eq x y) |
True if x and y evaluate to the same symbol. |

(eql x y) |
True if x and y are either = or eq. |

(equal x y) |
True if x and y are eql or if they evaluate to the same list. |

(equalp x y) |
To be discussed in Tutorial 4. |

**Exercise**: What would be the behavior of `list-member` if we replace `eq` by `=`? By `eql`? By `equal`?

## Example: `append`

LISP defines a function `append` that appends one list by another:

USER(72): (append '(a b c) '(c d e)) (A B C C D E)

We implement a recursive version of `append`. Suppose we are given two lists *L1* and *L2*. *L1* is either `nil` or constructed by `cons`.

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

Appending*L2*to*L1*simply results in*L2*.*Case 2*:*L1*is composed of two parts:`(first`and*L1*)`(rest`. If we know the result of appending*L1*)*L2*to`(rest`, then we can take this result, insert*L1*)`(first`to the front, and we then have the list we want.*L1*)

Formally, we define the following function:

(defun list-append (L1 L2) "Append L1 by L2." (if (null L1) L2 (cons (first L1) (list-append (rest L1) L2))))

An execution trace is the following:

USER(73): (list-append '(a b c) '(c d e)) 0: (LIST-APPEND (A B C) (C D E)) 1: (LIST-APPEND (B C) (C D E)) 2: (LIST-APPEND (C) (C D E)) 3: (LIST-APPEND NIL (C D E)) 3: returned (C D E) 2: returned (C C D E) 1: returned (B C C D E) 0: returned (A B C C D E) (A B C C D E)

**Exercise**: LISP defines a function `(butlast L)` that returns a list containing the same elements in

*L*except for the last one. Implement your own version of

`butlast`using linear recursion. You may assume that

`(butlast nil)`returns

`nil`.

## Using Lists as Sets

Formally, lists are ordered sequences. They differ with sets in two ways:

- Sets are unordered, but lists are.
`(a b c)`and`(c b a)`are two different lists. - An element either belong to a set or it does not. There is no notion of multiple occurrences. Yet, a list may contain multiple occurrences of the same element.
`(a b b c)`and`(a b c)`are two different lists.

However, one may use lists to approximate sets, although the performance of such implementation is not the greatest.

We have already seen how we can use the built-in function `member` to test set membership. LISP also defines functions like `(intersection L1 L2)`,

`(union`and

*L1**L2*)`(difference`for boolean operations on sets. In fact, these functions are not difficult to implement. Consider the following implementation of set intersection:

*L1**L2*)(defun list-intersection (L1 L2) "Return a list containing elements belonging to both L1 and L2." (cond ((null L1) nil) ((member (first L1) L2) (cons (first L1) (list-intersection (rest L1) L2))) (t (list-intersection (rest L1) L2))))

The correctness of the implementation is easy to see. *L1* is either an empty set (`nil`) or it is not:

*Case 1*:*L1*is an empty set.

Then its interection with*L2*is obviously empty.*Case 2*:*L1*is not empty.

*L1*has both a`first`component and a`rest`component. There are two cases: either`(first`is a member of*L1*)*L2*or it is not.*Case 2.1*:`(first`is a member of*L1*)*L2*.

`(first`belongs to both*L1*)*L1*and*L2*, and thus belong to their intersection. Therefore, the intersection of*L1*and*L2*is simply`(first`plus the intersection of*L1*)`(rest`and*L1*)*L2*.*Case 2.2*:`(first`is not a member of*L1*)*L2*.

Since`(first`does not belong to*L1*)*L2*, it does not belong to the intersection of*L1*and*L2*. As a result, the intersection of*L1*and*L2*is exactly the intersection of`(rest`and*L1*)*L2*.

A trace of executing the function is given below:

USER(80): (trace list-intersection) (LIST-INTERSECTION) USER(81): (list-intersection '(1 3 5 7) '(1 2 3 4)) 0: (LIST-INTERSECTION (1 3 5 7) (1 2 3 4)) 1: (LIST-INTERSECTION (3 5 7) (1 2 3 4)) 2: (LIST-INTERSECTION (5 7) (1 2 3 4)) 3: (LIST-INTERSECTION (7) (1 2 3 4)) 4: (LIST-INTERSECTION NIL (1 2 3 4)) 4: returned NIL 3: returned NIL 2: returned NIL 1: returned (3) 0: returned (1 3) (1 3)

**Exercise**: Give a linearly recursive implementation of `union` and `difference`.

Posted on April 21, 2012, in lisp. Bookmark the permalink. Leave a comment.

## Leave a comment

## Comments 0