Cons cells are a great tool for representing a wide variety of list-like structures. In fact, most Lisp programmers, when faced with a programming task that is not bound by performance constraints, will rely on them almost exclusively. Because the manipulation and visualization of structures made of cons cells are central to the design of Lisp, these structures are extremely convenient to use and debug.
In fact, even if you do have performance constraints, structures made of cons cells can often be a great choice. A Lisp compiler can often reduce a change to a cons cell down to a single assembly instruction!
As discussed in Chapter 3, the data (and code) in a Lisp program is represented with syntax expressions. In this format, data is represented using nested lists, often with Lisp symbols at the front of each list explaining the structure of the data.
For example, suppose we wanted to represent the component parts of a house in Lisp:
(defparameter *house* '((walls (mortar (cement)
(water)
(sand))
(bricks))
(windows (glass)
(frame)
(curtains))
(roof (shingles)
(chimney))))This data structure very elegantly captures the hierarchical nature of the parts that make up a house. Since it is structured as a Lisp syntax expression, we can see the lists that make up the levels of the hierarchy. Also, it follows the convention of a syntax expression by putting a symbol at the front of each list. For instance, we can see how the list describing the windows first contains the Lisp symbol windows , which is then followed by three items, representing the glass, frame, and finally the curtains .
As you can see, data that is hierarchical and tree-like in nature can be very naturally expressed in this way. In fact, many Lispers consider XML (a popular format for representing hierarchical data) somewhat of a reinvention of the syntax expression format that Lisp pioneered.
If, however, we move beyond tree-like structures, data stored in a syntax expression can start becoming hard to visualize, even if it’s relatively easy to store the data in cons cells. For instance, suppose we have a mathematical graph stored in a syntax expression. These types of graphs, where any arbitrary node of the graph may be connected to another by an edge, are notoriously hard to visualize in a computer program. Even Lisp’s elegant system for representing cons cells can’t help much for such data. Next, we’ll look at our options for visualizing such graphs.
In mathematics, a graph consists of a bunch of nodes connected by edges. These nodes or edges might have additional data associated with them.
Such graphs can be stored in cons cells, but they are difficult to visualize. We saw this in Chapter 5, when we stored the map of the wizard’s house (which consisted of a directed graph) in two alists: one containing the node information and one containing the edge information. I’ve renamed them *wizard-nodes* and *wizard-edges* for this chapter, as shown here:
(defparameter *wizard-nodes* '((living-room (you are in the living-room.
a wizard is snoring loudly on the couch.))
(garden (you are in a beautiful garden.
there is a well in front of you.))
(attic (you are in the attic. there
is a giant welding torch in the corner.))))
(defparameter *wizard-edges* '((living-room (garden west door)
(attic upstairs ladder))
(garden (living-room east door))
(attic (living-room downstairs ladder))))As you can see, it is hard to get a decent understanding of the structure of this game world from these raw data tables. Unfortunately, data that has the shape of a graph or contains other properties that go beyond simple tree structures are very common. Wouldn’t it be great if we had a tool that could optimally arrange this data to create a pretty drawing of a graph? Luckily, there is a fantastic open source tool that performs exactly this task, which you’ll try out next.