The pros and cons of Cons

Up | Home

The pros and cons of Cons

Table of Contents

1. Introduction

1.1. Cons cells

1.2. Lists and syntactic sugar

2. The initial approach

2.1. A basic Expr structure

2.2. Combining expressions with linked lists

3. The conventional cons cell approach

4. Comparing the two methods

4.1. Disadvantage: Memory impact

4.2. Advantage: Improper lists

4.3. Advantage: Context independence, reusing references

4.4. Advantage: Consistent nil

4.5. Advantage: No list wrappers

4.6. Advantage: Lisp-like C code

1. Introduction

This article is about the advantages and disadvantages of using cons cells when<br>implementing a Lisp-like programming language.

I have been working on a simple Lisp interpreter for some months now, and I have<br>learned many things from my mistakes. I recently changed how lists are<br>internally stored in my interpreter, and I wanted to explain why I decided to<br>use my old approach in the beginning, and why I decided to eventually change<br>into a more conventional cons cell approach.

Throughout this article I will use the Lisp syntax from my interpreter, but the<br>examples can be run in most Lisp dialects with some minor modifications. Just<br>keep in mind that, unlike in Lisp2 dialects (e.g. Common Lisp), there isn&rsquo;t a<br>separate namespace for functions, so you won&rsquo;t see funcall.

First of all, I would like to credit Daniel Kochmański for his help some months<br>ago, and for linking me this email by Erik Naggum, which you might find useful.

1.1. Cons cells

If you are familiar with Lisp languages, you probably know what cons cells are,<br>but I will still give a brief explanation.

The term &ldquo;cons&rdquo; is a bit ambiguous in Lisp, because it&rsquo;s commonly used when<br>talking about a data type, but it&rsquo;s also the name of a procedure that creates an<br>object of that type. Although basically all Lisp dialects have a cons function,<br>the name used to refer to the data type changes among them: Scheme calls them<br>pairs, Emacs Lisp calls them cons cells, and Common Lisp simply calls them<br>cons. In this article, I will use the term &ldquo;cons cell&rdquo; when referring to the<br>data type to avoid confusion.

A cons cell is a Lisp object that simply points to another two to Lisp<br>objects. For historical reasons, the first pointer is called the CAR, and the<br>second pointer is called the CDR1. These CAR and CDR terms are not only<br>used when talking about the pointers themselves, but also when talking about the<br>values that they point to.

Figure 1: Box diagram of a cons cell.

These kinds of diagrams are called box-and-pointer, box-and-arrow, or simply box<br>diagrams, and they are very useful for understanding how complex data structures<br>are stored internally.

The procedures for accessing the CAR and the CDR of a cons cell are called car<br>and cdr. There are also wrappers for combining them, so (caddr x) would return<br>the car of the cdr of the cdr of x.

(car (cons 10 20))<br>⇒ 10

(cdr (cons 10 20))<br>⇒ 20

Finally, I would like to mention dotted pair or cons pair notation. When a dot<br>is encountered inside a list (i.e. between parentheses), the interpreter assumes<br>that the element before the dot is the CAR of the current pair, and the one<br>after the dot is the CDR.

(car '(10 . 20))<br>⇒ 10

(cdr '(10 . 20))<br>⇒ 20

1.2. Lists and syntactic sugar

When people mention lists in the context of Lisp, they are usually talking about<br>something that looks like:

(a b 1 2)

These are called proper lists, but it&rsquo;s important to understand that (usually)<br>the lists are internally stored as chained cons cells, and that the previous<br>notation is just syntactic sugar for:

(a . (b . (1 . (2 . nil))))

As you can see, each element of our list is stored in the CAR of a cons cell,<br>and the CDR points to another cons cell which contains the next element. The CDR<br>of the innermost cons cell is the symbol nil, used to terminate<br>lists2. Although not all Lisp dialects use the<br>symbol nil, there is always a unique value used to terminate proper lists. In<br>box diagrams, a crossed box is used to represent this terminator.

Figure 2: Box diagram of a proper list.

Let me emphasize that there is no &ldquo;list type&rdquo;, it&rsquo;s just a data structure that<br>is built out of cons cells.

2. The initial approach

Now that we know how lists are conventionally represented in Lisps, let&rsquo;s have a<br>look at an alternative implementation.

One of the books that inspired me to write a Lisp interpreter was Build Your Own<br>Lisp by Daniel Holden. The author doesn&rsquo;t use the cons cell approach described<br>above, and although I didn&rsquo;t follow the book, at first glance it didn&rsquo;t seem<br>like a bad idea. This article tries to precisely show its advantages and<br>limitations when compared to the traditional approach explained above.

2.1. A basic Expr structure

First, let&rsquo;s have a look at how a very basic Lisp expression would look like<br>from C, using a tagged union.

enum EExprType...