History notes . . .

Origin of Lisp's Strange Keywords

by Carzand Cudders, November 1, 2011
ŠInformation Disciplines, Inc.

NOTE: This document may be circulated or quoted from freely, as long as the copyright credit is included.


A very long era

The death of Artificial Intelligence pioneer John McCarthy last week at age 84 reminded us of the role of LISP, the functional programming language that has been in the mainstream of A.I. programming for an amazing half century. For most of that time span students learning Lisp were puzzled by the central role of two cryptic keywords car and cdr.

Those keywords arose in an era when machine independence wasn't viewed as especially important. They were directly tied to the internal instruction format of IBM's 704-709 line of large-scale computers having 36-bit words.

IBM 704-709 instruction formats

Most of the instructions were of the form:

operation code flags XR operand address
000000000000 ----- 000 000000000000000

The operation code for those instructions always began with 000 or 100. But a few very important instructions had a different format. The designated index register XR was used not for address modification, but as an operand of the instruction (operation code = 001, 010, 011, 110, or 111) itself:

op. decrement XR operand address
111 000000000000000 000 000000000000000

The so-called decrement field was interpreted by the machine as an immediate operand, but since it was the same length as a word address (15 bits) and since other instructions could access it directly, programs could also use it in a data word to designate any directly addressable operand. That brings us to car and cdr.

The basic structure in Lisp

"Lisp" originally stood for "list processing". A Lisp program consists of a bunch of lists. Some of those lists represent functions where the first element names the function and the remaining elements are its operands. Program execution consists, more or less, of evaluating the top-level function. We can visualize a list like this:

     (diagnose, symptom1, symptom2, symptom3)
but how can such a list be efficiently represented in an IBM 709 comnputer?

The original solution, slightly oversimplified here, is elegant and efficient, although inexcusably machine-dependent in nomenclature. A 36-bit word is a node specifying two operands:

Attempts have been made in later dialects of Lisp to replace those meaningless historical keywords, but many Lisp programmers, even now, prefer to stay with the originals. One possible factor is a strange convention for abbreviating combinations of multiple cars and cdrs. See the Wikipedia explanation, if you're interested.


Last modified November 1, 2011

Return to IDI home page
Historical notes.