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:



        ((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 CONSing 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):



        ((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.

Previous page First page Next page

Copyright 1995, 2000 by David Matuszek
All rights reserved.
Last updated January 10, 2002