Exploring the Origins of LISP Abbreviations: SETQ, CAR, and CDR

LISP, one of the oldest high-level programming languages, was developed in the 1950s on the IBM 704 computer. This fascinating period marks the inception of many fundamental programming concepts, including the well-known abbreviations SETQ, CAR, and CDR. This article delves into the historical context and technical details behind these abreviations, providing an in-depth look at the early days of programming.

SETQ: The Art of Assignment

The SETQ special form is a key operation in LISP for assigning values to atoms. Originally, the simpler form SET was used, which evaluated its first argument to determine the atom (or variable) to which the value of its second argument was to be assigned. For instance, the command SET QUOTE A B would set the atom A to B.

It was soon recognized that this pattern was widely used, and to streamline the syntax and improve readability, a modified version SETQ was introduced. The command SETQ A B provided the same functionality as SET QUOTE A B, making it easier and more natural for programmers to use.

IBM 704 and its Registers

The IBM 704, a mainframe computer of the 1950s, had a unique architecture that influenced the development of LISP. Let's explore the terminology and structure of the 704:

Registers: These were the primary storage units within the computer. The IBM 704 used a concept of registers that were different from the memory registers used today. The 704 had a set of registers, including the accumulator (AC) for arithmetic operations and the multiply-quotient (MQ) for multiplication and division. Memory: Information was stored in the memory, which was primarily in the form of punched tape or disks. The primary storage unit for the computer was the word, which was 36 bits long, allowing for a massive capacity of 32,768 words (or approximately 32K of storage).

Each word in the IBM 704 had a specific structure, divided into four parts:

Address (AD): 15 bits, representing the memory address. Decrement (DC): 15 bits, used to manage lists by pointing to the next element. Index (IX): 3 bits, used to select one of the four 15-bit registers. Tag (TG): 3 bits, used to specify the type of the address (e.g., a number, a pointer).

These parts gave rise to the specialized functions CAR and CDR, which were originally Content-of-the-Address-part-of the-Register and Content-of-the-Decrement-part-of-the-Register, respectively. However, as these functions were not widely used, they were eventually dropped in favor of the simplified terms.

CAR and CDR: Navigating Lists in LISP

In the context of LISP, CAR and CDR are indispensable for navigating through list structures. CAR retrieves the first element of a list, while CDR provides access to the rest of the list. For example, given a list (1 2 3 4 5),

CAR 1 2 3 4 5 - 1 CDR 1 2 3 4 5 - 2 3 4 5

These operations are fundamental to LISP programming, especially when working with symbolic data and recursive structures.

Further Reading and Recommendations

For those interested in diving deeper into LISP's early history and the specific details of the IBM 704, Herbert Stoyan's paper, Early LISP History 1956 - 1959, is highly recommended. This paper, presented at the 1984 ACM Conference on Lisp and Functional Programming, offers an insightful look into the development of one of the most influential programming languages in computer science.

Early LISP history 1956 - 1959