Chapter 1.4

Lists and List Operations

"While the laws of statistics tell you how unlikely a particular coincidence is, they state just as firmly that coincidences do happen."

In the spirit of Lambda Calculus and a pure functional heritage, the Lisp-family of programming languages gets its name from its purpose---LISt Processing. Even though Common Lisp is not a purely-functional programming language, its fundamental syntax has not deviated from this heritage; as you should remember from Chapter 1.1, Cons-Cells are one of two essential forms of Expressions in Lisp, and they are represented using List syntax; and since the other---Atoms---are, by definition, self-evaluating, everything interesting that you can do in Lisp is effectively a List operation. And these are divided into consing and non-consing operations.

This is important to remember---it's the reason there are so many parentheses in Lisp source-code. Every form surrounded by parentheses is a list. The only difference between code and data, syntactically speaking, is that code is read and evaluated whereas data is only read; you can switch to "data mode" by quoting an expression, but quoting isn't a free pass. Lisp still expects to be able to Read the forms you've quoted as valid forms, so the syntax is just as important to data as it is to code.

This is also the key to Lisp's homoiconicity---the same syntax is used to represent both Code and Data, and as a result you can treat Code as Data, and Data as Code. As far as Lisp is concerned, there is no difference between the two.

But Lists are also a proper type in Common Lisp, that descends from sequences. We have already seen some sequence operations on other data types, like Strings, and will explore them further. However, in this chapter, we will focus on Lists as a proper data type and Consing operations on these Lists.

Exercises

• Cons-Cells
• Consing
• Dot-Notation
• More Consing
• CAR and CDR
• More CAR and CDR
• Lists
• More Lists
• Even More CAR and CDR
• Stacks
• PUSH and POP
• More PUSH and POP
• FIRST, REST, and LAST
• List Position
• Appending
• More Appending
• Circular Lists
• Circular Trees
• Quoting
• More Quoting