20. Defstruct

20.1 Introduction to Structure Macros
defstruct provides a facility in Lisp for creating and using aggregate datatypes with named elements. These are like "structures" in PL/I, or "records" in PASCAL. In the last chapter we saw how to use macros to extend the control structures of Lisp; here we see how they can be used to extend Lisp's data structures as well. To explain the basic idea, assume you were writing a Lisp program that dealt with space ships. In your program, you want 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 (X and Y), velocity (X and Y), and mass. How do you represent a space ship? Well, the representation could be a 5-list of the x-position, y-position, and so on. Equally well it could be an array of five elements, the zeroth being the x-position, the first being the y-position, and so on. The problem with both of these representations is that the "elements" (such as x-position) occupy places in the object which are quite arbitrary, and hard to remember (Hmm, was the mass the third or the fourth element of the array?). This would make programs harder to write and read. What we would like to see are names, easy to remember and to understand. If the symbol foo were bound to a representation of a space ship, then 
(ship-x-position foo)
could return its x-position, and 
(ship-y-position foo)
its y-position, and so forth. defstruct does just this. defstruct itself is a macro which defines a structure. For the space ship example above, we might define the structure by saying: 
(defstruct (ship)
     ship-x-position
     ship-y-position
     ship-x-velocity
     ship-y-velocity
     ship-mass)
(This is a very simple case of defstruct ; we will see the general form later.) The evaluation of this form does several things. First, it defines ship-x-position to be a macro which expands into an aref form; that is, (ship-x-position foo) would turn into (aref foo 0) . All of the "elements" are defined to refer to sequentially increasing elements of the array, e.g., (ship-mass foo) would turn into (aref foo 4) . So a ship is really implemented as an array, although that fact is kept hidden. These macros are called the accessor macros , as they are used to access elements of the structure. defstruct will also define make-ship to be a macro which expands into a call to make-array which will create an array of the right size (namely, 5 elements). So (setq x (make-ship)) will make a new ship, and x will be bound to it. This macro is called the constructor macro , because it constructs a new structure. We also want to be able to change the contents of a structure. To do this, we use the setf macro (see LINK:(setf-fun)), as follows (for example): 
(setf (ship-x-position x) 100)
Here x is bound to a ship, and after the evaluation of the setf form, the ship-x-position of that ship will be 100. The way this works is that the setf form expands into (aset 100 x 0) ; again, this is invisible to the programmer. By itself, this simple example provides a powerful structure definition tool. But, in fact, defstruct has many other features. First of all, we might want to specify what kind of Lisp object to use for the "implementation" of the structure. The example above implemented a "ship" as an array, but defstruct can also implement structures as array-leaders and as lists. (For array-leaders, the accessor macros expand into calls to array-leader , and for lists, to car, cadr, caddr, and so on.) Most structures are implemented as arrays. Lists take slightly less storage, but elements near the end of a long list are slower to access. Array leaders allow you to have a homogeneous aggregate (the array) and a heterogeneous aggregate with named elements (the leader) tied together into one object. defstruct allows you to specify to the constructor macro what the various elements of the structure should be initialized to. It also lets you give, in the defstruct form, default values for the initialization of each element.
20.2 Setf and Locf
In Lisp, for each function to access (read) any piece of information, there is almost always a corresponding function to update (write) it as well. For example, symeval accesses a symbol's value cell, and set updates it. array-leader accesses the contents of an array leader element, and store-array-leader updates it. The knowledge of how these functions correspond is accessible through a macro called setf . setf is particularly useful in combination with structure-accessing macros, such as those created with defstruct , because the knowledge of the representation of the structure is embedded inside the macro, and the programmer shouldn't have to know what it is in order to alter an element of the structure.
setf Macro
setf takes a form which accesses something, and "inverts" it to produce a corresponding form to update the thing. The form for setf is 
(setf access-form  value )
It expands into an update form, which stores the result of evaluating the form value into the place referenced by the access-form . 
Examples:
(setf (array-leader foo 3) 'bar)
		===> (store-array-leader 'bar foo 3)
(setf a 3) ===> (setq a 3)
(setf (plist 'a) '(foo bar)) ===> (setplist 'a '(foo bar))
(setf (aref q 2) 56) ===> (aset 56 q 2)
(setf (cadr w) x) ===> (rplaca (cdr w) x)
locf Macro
locf takes a form which accesses some cell, and produces a corresponding form to create a locative pointer to that cell. The form for locf is 
(locf access-form )

Examples:
(locf (array-leader foo 3)) ===> (ap-leader foo 3)
(locf a) ===> (value-cell-location 'a)
(locf (plist 'a)) ===> (property-cell-location 'a)
(locf (aref q 2)) ===> (aloc q 2)
Both setf and locf work by means of property lists. When the form (setf (aref q 2) 56) is expanded, setf looks for the setf property of the symbol aref . The value of the setf property of a symbol should be a cons whose car is a pattern to be matched with the access-form , and whose cdr is the corresponding update-form , with the symbol si:val in the place of the value to be stored. The setf property of aref is a cons whose car is (aref array . subscripts) and whose cdr is (aset si:val array . subscripts) . If the transformation which setf is to do cannot be expressed as a simple pattern, an arbitrary function may be used. When the form (setf (foo bar) baz) is being expanded, if the setf property of foo is a symbol, the function definition of that symbol will be applied to two arguments, (foo bar) and baz , and the result will be taken to be the expansion of the setf . Similarly, the locf function uses the locf property, whose value is analogous. For example, the locf property of aref is a cons whose car is (aref array . subscripts) and whose cdr is (aloc array . subscripts) . There is no si:val in the case of locf . As a special case, setf and locf allow a variable as the reference. In this case they turn into setq and value-cell-location , respectively. For the sake of efficiency, the code produced by setf and locf does not preserve order of evaluation of the argument forms. This is only a problem is the argument forms have interacting side-effects. In addition, the value produced by setf is dependant on the structure type and is not guaranteed; setf should be used for side effect only.
20.3 How to Use Defstruct
defstruct Macro
A call to defstruct looks like: 
(defstruct (name  option-1  option-2  ...)
	   item-1 
	   item-2 
	   ...)
name must be a symbol; it is the name of the structure. It is used for many different things, explained below. option-n may be either a symbol (which should be one of the recognized option names, listed below) or a list (whose car should be one of the option names and the rest of which should be "arguments" to the option). item-n may be in any of three forms: 
(1) 	item-name 
(2) 	(item-name default-init) 
(3) 	((item-name-1  byte-spec-1  default-init-1 )
	(item-name-2  byte-spec-2  default-init-2 )
		...)
item-name must always be a symbol, and each item-name is defined as an access macro. Each item allocates one entry of the physical structure, even though in form (3) several access macros are defined. In form (1), item-name is simply defined as a macro to return the corresponding element of the structure. The constructor macro will initialize that entry to nil (or 0 in a numeric array) by default. In form (2), the access macro is defined the same way, but the default initialization is provided by the user of defstruct . In form (3), several access macros are defined, and each one refers to the single structure element allocated for this item . However, if byte-spec is a fixnum, the access macros will ldb that byte from the entry (see the function ldb , LINK:(ldb-fun)). byte-spec may also be nil , in which case the usual form of access macro is defined, returning the entire entry in the structure. Note that it is possible to define two or more different overlapping byte fields. (If more than one of these has a default-init the results of initializing the entry are undefined and unpredictable.) For example, if the third item of a call to defstruct were 
	((foo-high-byte 1010)
	 (foo-low-byte 0010)
	 (foo-whole-thing nil))
then (foo-high-byte foo) would expand to (ldb 1010 (aref foo 2)) , and (foo-whole-thing foo) would expand to (aref foo 2) . Form (3) can also be used if you want to have an element with more than one access macro. By putting ((foo nil) (bar nil)) , both foo and bar will be defined identically.
20.4 Options to Defstruct
Note that options which take no arguments may be given as just a symbol, instead of a list.
:arrayThe structure should be implemented as an array. This is the default. (No arguments.)
:array-leaderThe structure should implemented as be an array-leader. (No arguments.)
:listThe structure should be implemented as a list. (No arguments.)
ed-arraySee LINK:(grouped-array).
:timesUsed byed arrays. See LINK:(grouped-array).
:sizeTakes one argument, a symbol. The symbol gets set to the size of the structure, at load-time (not compile-time).
:size-macroOne argument, a symbol. The symbol gets defined as a macro, which expands into the size of the structure.
:constructorOne argument, a symbol which will be the name of the constructor macro. If the option is not present, the name of the constructor will be made by concatenating "make-" with the name of the structure. If the argument is nil , do not define any constructor macro.
:namedNo argument. This causes the constructor to create named structure arrays (and thus may not be used with the :list option) and automatically allocate the appropriate slot in the structure and put the name of the structure there as the named-structure symbol.
:default-pointer
One argument. The access macros will be defined in such a way that if they are called on no "arguments", the argument to the :default-pointer option will be used instead. (Normally, access macros will signal an error if their "argument" is missing.)
:make-arrayOne argument, arguments to the make-array function. See below.
:includeOne argument, the name of a structure. The structure being defined will start out the same as that structure, with some additional elements added at the end.
20.5 Using the Constructor Macro
If the argument to the :constructor option is nil , no constructor macro is defined. But otherwise, defstruct creates a constructor macro, which will create an instance of the structure. This section explains how the constructor macro interprets its "arguments". A call to a constructor macro, in general, has the form 
(name-of-constructor-macro 
        symbol-1  form-1 
        symbol-2  form-2 
        ...)
Each symbol may be either a name of an item of the structure, or a specially recognized keyword. All form s are evaluated. If symbol is the name of an item , then that element of the created structure will be initialized to the value of form . If no symbol is present for a given item, then the item will be initialized in accordance with the default initialization specified in the call to defstruct . If the defstruct itself also did not specify any initialization, the element will be initialized to nil , unless the structure is implemented by a numeric array , in which case it will be initialized to 0 . (In other words, the initialization specified to the constructor overrides the initialization specified to defstruct .) There are two symbols which are specially recognized by the constructor. One is :make-array , which should only be used for array and array-leader type structures. The value of form is used as the argument list to the make-array function call created by the constructor. This way, you can specify the area in which you wish the structure to be created, the type of the array to be created, and so on. Of course, if you provided all of the arguments to make-array , the constructor would not be able to do its job; so the constructor overrides your specifications of certain elements. If the structure is array type, your specification of the array's dimensions (the third argument to make-array ) is ignored; if it is of array-leader type, the array-leader argument (the fifth argument to make-array ) is ignored. Also, in both cases the named-structure argument (the seventh argument to make-array ) is ignored. They are ignored because it is the constructor macro's job to fill them in. If the list you provide is shorter than the number of arguments to make-array , it will be as if you had given the missing elements as nil . Similarly, if your list is too long, the extra elements will be ignored. If you do not provide the :make-array keyword at all, the arguments default from the value of the :make-array option to defstruct . If you did not even provide that, the default argument lists are:
For array s:
(default-array-area 'art-q whatever nil nil nil whatever)
For array-leader s:
(default-array-area 'art-q 0 nil whatever nil whatever)
The second keyword recognized by the constructor is :times , which should only be used for ed-arrays. Its value is the number of repetitions of the structure in theed-array. If :times is not provided, it defaults from the :times option of defstruct. If you did not even provide that, the default is 1.
20.6 Grouped Arrays
Theed array feature allows you to store several instances of a structure side-by-side within an array. This feature is somewhat limited, and requires that the structure be implemented as an array, that it not have any :include option, and that it not be a named structure. The accessor macros are defined to take a "first argument" which should be a fixnum, and is the index into the array of where this instance of the structure starts. It should be a multiple of the size of the structure, for things to make sense. Note that the "size" of the structure (as given in the :size symbol and the :size-macro) is the number of elements in one instance of the structure; the actual length of the array is the product of the size of the structure and the number of instances. The number of instances to be created by the creator macro is given as the argument to the :times or ed-array option, or the :times keyword of the constructor macro (see below).
20.7 Grouped Arrays

The named structure feature provides a very simple form of user-defined data type. Any array may be made a named structure, although usually the :named option of defstruct is used to create named structures. The principle advantages to a named structure are that it has a more informative printed representation than a normal array and that the describe function knows how to give a detailed description of it. Because of these improved user-interface features it is recommended that "system" data structures be implemented with named structures. Another kind of user-defined data type, more advanced but less efficient, is provided by the actor feature (see LINK:(actor)). A named structure has an associated symbol, called its "named structure symbol", which represents what user-defined type it is an instance of; the typep function, applied to the named structure, will return this symbol. If the array has a leader, then the symbol is found in element 1 of the leader; otherwise it is found in element 0 of the array. (Note: if a numeric-type array is to be a named structure, it must have a leader, since a symbol cannot be stored in any element of a numeric array.) The named structure symbol should be defined as a function. The functions which know about named structures will apply this function to several arguments. The first is a "keyword" symbol to identify the calling function, and the second is the named structure itself. The rest of the arguments passed depend on the caller; any named structure function should have a "&rest" parameter to absorb any extra arguments that might be passed. Just what the function is expected to do depends on the keyword it is passed as its first argument. The following are the keywords defined at present:
:which-operations
Should return a list of the names of the operations the function handles.
:printThe arguments are :print, the named structure, the stream to output to, the current depth in list-structure, and t if slashification is enabled (prin1 versus princ). The printed representation of the named structure should be output to the stream. If the named structure symbol is not defined as a function, or :print is not in its :which-operations list, the printer will default to a reasonable printed representation.
:describeThe arguments are :describe and the named structure. It should output a description of itself to standard-output. If the named structure symbol is not defined as a function, or :describe is not in its :which-operations list, the describe system will check whether the named structure was created by using the :named option of defstruct; if so, the names and values of the structure's fields will be enumerated.
The following functions operate on named structures.

named-structure-p x
This predicate returns t if x is a named structure; otherwise it returns nil.
named-structure-symbol x
x should be a named structure. This returns x's named structure symbol: if x has an array leader, element 1 of the leader is returned, otherwise element 0 of the array is returned.
make-array-into-named-structure array
array is made to be a named structure, and is returned.
named-structure-invoke str op &rest args
str should be a named structure, and op should be a keyword symbol. The function definition of the named structure symbol is called with appropriate arguments.