What's all this list processing stuff about anyway? Even if you're a programmer with no LISP experience, you probably know that LISP stands for list processing. You probably use linked-list structures in your code from time to time and wonder what LISP can do that you can't. Like other languages, LISP has unique properties that make it a powerful language for solving certain types of problems. Unique language properties are often quite handy and an enterprising programmer will incorporate those properties into another language.
The two best-known LISP properties are symbolic processing and list processing. Both concepts can be developed in other languages with a set of generic functions or procedures that operate on appropriate data structures and by developing a proper mental attitude concerning the abstraction.
In this article, I address generic list-processing procedures in C. The same concepts can be adapted for other high-level languages and assembly language.
Most C programmers have used linked-list structures such as the one in Listing One.
typedef struct record
{
struct record *link; /* next record */
char data[ 100]; /* text date */
} RECORD;
In this case, the first item in the structure is a link pointer to the next structure, and the rest of the structure is a place to store data. This, of course, is a simple example. Real-world programming requirements usually result in more complex data struc tures for keeping track of things like airline reservations, satellite ephemeries, journal entries, and so on. Lists are usually built fr om these structures (Figure 1).
List maintenance procedures can be developed to add, delete, and sort list items, among other things. Essentially, by doing so we are processing a list. The difference is that these list procedures usually have a special purpose -- for example, we might write a procedure to add a new record to the head of the list with code as shown in Listing Two.
RECORD *addrecord(rec.list)
RECORD *rec; /* new record */
RECORD *list; /* pointer to head of list */
{
rec->link=list;
return rec;
}
USAGE:
head = addrecord(arecord.head);
Unfortunately, such a procedure can only be used to maintain lists composed of RECORD data structures. However, if we could develop a method of adding a record to a list regardless of the record's structure, we could use this method for every list in our program. LISP performs just this method; the notion of a list is embedded in the language, as are generic procedures for list processing. Let's do the same for C.
The trick is removing the links from the records. We need to define a data structure to construct lists separate from the one that defines list items (Figure 2).
A CONS is a data structure that can construct lists. It consists of two cells, called the "car" cell and the "cdr" (pronounced "could-er") cell. A CONS is a simple structure, but don't let its simplicity fool you. A CONS is to symbolic processing what a binary digit is to numerical processing. By combining CONS we can form lists, binary trees, hierarchies, and an infinite number of other useful data structures.
