Common Lisp the Language, 2nd Edition

19.1. Introduction to Structures

The structure facility is embodied in the defstruct macro, which allows the user to create and use aggregate data types with named elements. These are like ``structures'' in PL/I, or ``records'' in Pascal.

As an example, assume you are writing a Lisp program that deals with space ships in a two-dimensional plane. In your program, you need to represent a space ship by a Lisp object of some kind. The interesting things about a space ship, as far as your program is concerned, are its position (represented as x and y coordinates), velocity (represented as components along the x and y axes), and mass.

A ship might therefore be represented as a record structure with five components: x-position, y-position, x-velocity, y-velocity, and mass. This structure could in turn be implemented as a Lisp object in a number of ways. It could be a list of five elements; the x-position could be the car, the y-position the cadr, and so on. Equally well it could be a vector of five elements: the x-position could be element 0, the y-position element 1, and so on. The problem with either of these representations is that the components occupy places in the object that are quite arbitrary and hard to remember. Someone looking at (cadddr ship1) or (aref ship1 3) in a piece of code might find it difficult to determine that this is accessing the y-velocity component of ship1. Moreover, if the representation of a ship should have to be changed, it would be very difficult to find all the places in the code to be changed to match (not all occurrences of cadddr are intended to extract the y-velocity from a ship).

Ideally components of record structures should have names. One would like to write something like (ship-y-velocity ship1) instead of (cadddr ship1). One would also like a more mnemonic way to create a ship than this:

(list 0 0 0 0 0)

Indeed, one would like ship to be a new data type, just like other Lisp data types, that one could test with typep, for example. The defstruct facility provides all of this.

defstruct itself is a macro that defines a structure. For the space ship example, one might define the structure by saying:

(defstruct ship 
  x-position 
  y-position 
  x-velocity 
  y-velocity 
  mass)

This declares that every ship is an object with five named components. The evaluation of this form does several things:

• It defines ship-x-position to be a function of one argument, a ship, that returns the x-position of the ship; ship-y-position and the other components are given similar function definitions. These functions are called the access functions, as they are used to access elements of the structure.

• The symbol ship becomes the name of a data type of which instances of ships are elements. This name becomes acceptable to typep, for example; (typep x 'ship) is true if x is a ship and false if x is any object other than a ship.

• A function named ship-p of one argument is defined; it is a predicate that is true if its argument is a ship and is false otherwise.

• A function called make-ship is defined that, when invoked, will create a data structure with five components, suitable for use with the access functions. Thus executing

  (setq ship2 (make-ship))
  

  sets ship2 to a newly created ship object. One can specify the initial values of any desired component in the call to make-ship by using keyword arguments in this way:

  (setq ship2 (make-ship :mass *default-ship-mass* 
                         :x-position 0 
                         :y-position 0))
  

  This constructs a new ship and initializes three of its components. This function is called the constructor function because it constructs a new structure.

• The #S syntax can be used to read instances of ship structures, and a printer function is provided for printing out ship structures. For example, the value of the variable ship2 shown above might be printed as

  #S(ship  x-position 0  y-position 0  x-velocity nil 
           y-velocity nil  mass 170000.0)
  

• A function called copy-ship of one argument is defined that, when given a ship object, will create a new ship object that is a copy of the given one. This function is called the copier function.

• One may use setf to alter the components of a ship:

  (setf (ship-x-position ship2) 100)
  

  This alters the x-position of ship2 to be 100. This works because defstruct behaves as if it generates an appropriate defsetf form for each access function.

This simple example illustrates the power of defstruct to provide abstract record structures in a convenient manner. defstruct has many other features as well for specialized purposes.