|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
Any but the most trivial functions should begin with
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
and deal directly with the empty list.
Rule 3: Do something with the
CAR, recur with the
For each case after the first, you should notice what the above (failed) conditions
are telling you. For example, if your first condition was
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
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
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. To keep the
CONS it onto the
result of recurring with the
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 3b: To transform the elements of a list,
CONS the transformed
CAR onto the result of recurring with the
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
recurring with the
CONSing the modified
CAR onto the modified
CDR. As an example, to add 1
to every element of a list of numbers (using the
(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
until you know that
L is a nonempty list. Don't call
X Y) until you know that
Y are atoms.
Rule 5: Use
T as the last test in a
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.