CODEWITHSUNDEEP
listlisp
bananov
bananov

Reputation: 173

What was a reason to introduce dotted pair in LISP?

Does anyone know what was the historical reason to introduce a dotted pair type to LISP while existing list type covers everything?

Also I am interested in this because dotted pairs often confuse me.

Upvotes: 10

Views: 4187

Answers (3)

eriktous
eriktous

Reputation: 6649

As you can read in the comments to your question, the dotted pair wasn't introduced next to an already existing list type; instead, it was introduced as the initial data structure, and lists are implemented in dotted pairs.

As to the question why the dotted pair was chosen, I believe it was guided by the hardware the original LISP system was implemented on: the IBM 704. As can be read in the wikipedia article on car and cdr, it had a 36-bit word, which could be accessed in four parts: two 15-bit, and two 3-bit parts.
With hardware like this, it's very natural to put a 15-bit address in each of the two 15-bit parts of a machine word, and voilà, you have a 'dotted pair'.

See also the History of Lisp, for more information on the design of the system.

Upvotes: 3

John R. Strohm
John R. Strohm

Reputation: 7667

Read McCarthy's 1960 paper, "Recursive Functions of Symbolic Expressions and Their Computation By Machine, Part I".

He starts by defining S-expressions. One of the rules is that if e1 is an S-expression and e2 is an S-expression, then < e1 . e2 >, the dotted pair, is also an S-expression.

A few lines later, he defines the list notation, as a shorthand for an expression built up of a chain of dotted pairs.

This was the paper that first defined what would eventually become LISP. It didn't become an actual programming language until Steve "Slug" Russell implemented the first interpreter.

Upvotes: 15

JB.
JB.

Reputation: 42104

Existing cons type covers everything (list-related). Dotted-pair notation is merely syntax for a cons literal.

Upvotes: 6

Related Questions