Building Lists with Cons Cells

Introduction

Welcome to a new module: Working with Lists: The Heart of Lisp. In our previous lesson, you mastered progn, a tool for executing a sequence of actions where only one expression is expected. This allowed you to build more complex conditional logic, like our dev-backup-current-file command, which performed multiple steps in its "then" branch.

We've often encountered lists in our code, using them to hold data like '(a b c). But what is a list from Lisp's point of view? This question is central to understanding the language. As someone interested in the Lisp philosophy, you'll find this lesson particularly revealing. It uncovers the simple, elegant foundation upon which Lisp's most powerful features, including its famed "code as data" paradigm, are built.

Today, we will focus on this learning outcome: Explain how lists are built from cons cells. We will dissect the Lisp list and discover that it's not a primitive data type but a structure cleverly assembled from a single, fundamental building block: the cons cell.

1. The Cons Cell: Lisp's Fundamental Building Block

At the very bottom of Lisp's data structures, we find the cons cell. The name is short for "construct cell". It is an object that simply holds two values or, more accurately, pointers to two values.

That's it. This two-part container is the atom from which we can build molecules of staggering complexity.

Traditionally, these two parts are called the car and the cdr (pronounced "could-er").

car: A pointer to the first value.
cdr: A pointer to the second value.

The origin of these names is historical, dating back to the IBM 704 computer, where they stood for "Contents of the Address part of the Register" and "Contents of the Decrement part of the Register." While the names are archaic, they are deeply ingrained in Lisp culture.

Let's see how to create one. The function to do this is, fittingly, cons. To get a hands-on feel for this, please watch the first part of the following video.

Types, Conditionals, and Loops - Learning Emacs Lisp #2

This segment from a System Crafters video introduces the cons cell, the cons function for creating it, and the car/cdr functions for accessing its parts.

Please watch from 00:43:21 to 00:45:35. Focus on how a cons cell is defined as a pair of two values and how car and cdr retrieve the left and right values, respectively.

As the video demonstrated, if you evaluate (cons 1 2) in your *scratch* buffer (using C-x C-e), Emacs will print (1 . 2).

This dotted pair notation is the textual representation of a single cons cell. The dot signifies that this is not a list, but a fundamental pair: the car is 1 and the cdr is 2.

Visually, you can think of it like this:

Cons Cells and Linked Lists — This diagram shows the basic structure of a cons cell. It has two slots, `car` and `cdr`, each capable of holding a value or a pointer to another object.

2. From Cons Cells to Lists: The Chain

So, how do we get from a simple pair like (1 . 2) to a list like (1 2 3)? The answer is by linking cons cells together into a chain.

A proper Lisp list is a sequence of cons cells where:

The car of each cell holds an element of the list.
The cdr of each cell points to the next cons cell in the chain.
The cdr of the final cell is set to nil to signify the end of the list.

The value nil is special in Lisp; it represents both boolean false and the empty list ().

The following article provides a fantastic, detailed explanation with clear ASCII diagrams that illustrate this chain-like structure.

Lisp lists and destructive functions

This article provides a superb textual and visual explanation of cons cells and how they form lists. The ASCII diagrams are particularly helpful for building a mental model.

Please read sections 2 ('cons cell'), 3 ('cons cells in diagrams'), and 4 ('lists'). Focus on the definition of a cons cell, how the diagrams represent it, and crucially, how the article shows a list being constructed as a linked chain of these cells terminated by nil.

Let's put the article's explanation into practice. Based on what you just read, what would you expect the output of this expression to be?

(cons 1 (cons 2 (cons 3 nil)))

Try evaluating it in your *scratch* buffer. You will get (1 2 3). Emacs sees this specific chain of cons cells ending in nil and knows to print it as a standard list.

The article rightly quotes from Practical Common Lisp: "The key to understanding lists is to understand that they’re largely an illusion built on top of... cons cells."

This structure allows for nesting. The car of a cons cell can point to any Lisp object, including another list. This is how you create nested data structures, which is invaluable for organizing complex information, whether it's for a program's configuration or for world-building in speculative fiction.

Lisp List Structure with Cons Cells — This diagram illustrates a nested list. The `car` of the second cons cell points not to a simple symbol, but to the beginning of another list structure, `(BRAVE NEW)`.

3. Practical Demonstration

To see this concept in action again, let's return to the video from System Crafters, which demonstrates precisely this list-building process.

Types, Conditionals, and Loops - Learning Emacs Lisp #2

This video segment visually walks through the process of building a list by chaining cons calls together.

Watch from 00:46:24 to 00:48:23. Pay close attention to how nested cons calls result in a list and how (cons element existing-list) works. This is because an existing-list is already a valid chain of cons cells ending in nil.

The key insight here is that (cons 'a '(b c)) works because '(b c) is just a stand-in for (cons 'b (cons 'c nil)). When you cons 'a onto it, you are creating a new first link in the chain, resulting in (cons 'a (cons 'b (cons 'c nil))), which is the list (a b c).

Conclusion

This lesson took you under the hood of Lisp's most important data structure. While the concept can be abstract at first, internalizing it is a major step toward fluency in Elisp.

Key Takeaways:

Lisp lists are not a primitive data type; they are an emergent structure built from cons cells.
A cons cell is a simple object with two pointers: car (the value) and cdr (the next link).
A proper list is a chain of cons cells where the cdr of the final cell is nil.
The dotted pair notation, like (1 . 2), represents a single cons cell whose cdr is not nil or another cons cell.

Preview of the Next Lesson

We have now seen the "hard way" to build a list: by manually chaining cons calls. This is fundamental for understanding the structure, but it's not very convenient for everyday use.

In the next lesson, we will explore the practical ways to work with lists. We will cover:

Creating lists easily using the list function and the quote special form (').
Accessing elements using car, cdr, and functions like nth.

This will equip you with the tools to start creating and manipulating list data effectively in your own functions.