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