Channels ▼


The Power of LISP for C Programmers

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   */
Listing One: Linked-list structure.

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

Figure 1: Common approach to linked lists.

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 */
   return rec;
head = addrecord(arecord.head);
Listing Two: Use of linked-list structure.

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

Figure 2: Improved approach to linked lists.

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.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.