VI. The logic of functions

LISP deals with lists. Because you typically access the elements of a list one at a time until you reach the end of the list, most functions have the same basic structure. The following rules are not ironclad, but work well for a majority of the LISP functions you will ever write.

Rule 1: Begin with a `COND`.

Any but the most trivial functions should begin with `COND`. The rest of the function consists of enumerating all the possible cases.

Rule 2: Test for a `NULL` (empty) list.

The first case should do the simplest work, in a nonrecursive fashion. For example, 90% of all functions that process a list will first test `NULL`, and deal directly with the empty list.

Rule 3: Do something with the `CAR`, recur with the `CDR`.

For each case after the first, you should notice what the above (failed) conditions are telling you. For example, if your first condition was `(NULL L)`, then in the second clause you know that `L` is not the empty list (or you would never have gotten to the second clause).

Since the list isn't empty, it has a `CAR` and a `CDR`. If you want to apply some operation to every element of a list, it is now safe to apply that operation to the `CAR`; recurring with the `CDR` will the operation to be applied to the remaining list elements. Note that the "operation" you apply may be quite complex.

Rule 3a: To delete the `CAR`, just ignore it and recur with the `CDR`.

Rule 3b: To keep the `CAR`, `CONS` it onto the result of recurring with the `CDR`.

If the first thing in your list should be ignored, that is, the result of your function should be the same even if that first element were not there, then just call the function without that first element. As an example, to remove all the top-level atoms from a list of S-expressions:

``````    (DEFUN REMATOMS (L)

(COND

((NULL L)  L)

((ATOM (CAR L))  (REMATOMS (CDR L)))

(T  (CONS (CAR L)  (REMATOMS (CDR L)))) ) )``````

Rule 3c: To transform the elements of a list, `CONS` the transformed `CAR` onto the result of recurring with the `CDR`.

When you want to perform an operation on every element of a list, and form a list of the results, you can do this by performing the operation on the `CAR`, recurring with the `CDR`, then `CONS`ing the modified `CAR` onto the modified `CDR`. As an example, to add 1 to every element of a list of numbers (using the `1+` function):

``````    (DEFUN ADDONE (L)

(COND

((NULL L)  L)

(T  (CONS (1+ (CAR L))  (ADDONE (CDR L)))) ) )``````

Rule 4: In each case of a COND you can use the fact that all previous tests have failed.

Programming in LISP is largely a matter of enumerating all the possible cases and writing a clause to deal with each. In each clause you know that the tests of all the preceding clauses failed, and you write a test to bite off a small section of the possibilities that are left.

Be sure that you always check the arguments of a function for legality before you call the function with them. For example, don't call `(CAR L)` until you know that `L` is a nonempty list. Don't call ```(EQ X Y)``` until you know that `X` and `Y` are atoms.

Rule 5: Use `T` as the last test in a `COND`.

Your `COND` should cover all possible cases, and return a value for each case. Using `T` for the last test makes this a "catchall" case. It's poor practice to assume you can think of all possible cases.

Where algorithmic languages use assignment statements, sequential execution of statements, and loops, LISP uses function composition and recursion. Programmers used to an algorithmic language may therefore find LISP to be difficult and confusing. It takes some experience with the language before the beauty of LISP begins to be apparent.

Most implementations of LISP provide constructs similar to those found in algorithmic languages. These are best avoided by the beginning LISP programmer, as they allow the novice to "write Fortran programs in LISP'' and never fully master the LISP approach to programming.