7. Manipulating List Structure
7.1 Conses
car x
Returns the car of x . 
Example:
(car '(a b c)) => a
cdr x
Returns the cdr of x . 
Example:
(cdr '(a b c)) => (b c)
Officially car and cdr are only applicable to conses and locatives. However, as a matter of convenience, a degree of control is provided over the action taken when there is an attempt to apply one of them to a symbol or a number. There are four mode-switches known as the car-number mode, cdr-number mode, car-symbol mode, and cdr-symbol mode . Here are the meanings of the values of these mode switches:
car-number = 0car of a number is an error. This is the default.
car-number = 1car of a number is nil .
cdr-number = 0cdr of a number is an error. This is the default.
cdr-number = 1cdr of a number is nil .
car-symbol = 0car of a symbol is an error.
car-symbol = 1car of nil is nil , but the car of any other symbol is an error. This is the default.
car-symbol = 2car of any symbol is nil .
car-symbol = 3car of a symbol is its print-name.
cdr-symbol = 0cdr of a symbol is an error.
cdr-symbol = 1cdr of nil is nil , but the cdr of any other symbol is an error. This is the default.
cdr-symbol = 2cdr of any symbol is nil .
cdr-symbol = 3cdr of nil is nil , cdr of any other symbol is its property list.
The values of the mode switches can be altered with the function set-error-mode (see LINK:(set-error-mode-fun)). 'findex "set-error-mode" They are stored as byte fields in the special variable %m-flags . 'vindex "%m-flags" The reason that the two symbol modes default in that fashion is to allow programs to car and cdr off the ends of lists without having to check, which is sometimes useful. A few system functions depend on car and cdr of nil being nil , although they hadn't ought to, so things may break if you change these modes. The value of 3 for the symbol modes exists for compatibility with ancient versions of Maclisp, and should not be used for any other reasons. (The appropriate functions are get-pname (see LINK:(get-pname-fun)) and plist (see LINK:(plist-fun)).) 'findex "get-pname" 'findex "plist" Note: unlike Maclisp, the values of the symbols car and cdr are not used; the various mode switches above serve their purpose. 'vindex "car" 'vindex "cdr" Also unlike Maclisp, this error checking is always done, even in compiled code, regardless of the value of *rset . 'vindex "*rset"
c...r x

All of the compositions of up to four car 's and cdr 's are defined as functions in their own right. The names of these functions begin with "c " and end with "r ", and in between is a sequence of "a "'s and "d "'s corresponding to the composition performed by the function. 

Example:
(cddadr x) is the same as  (cdr (cdr (car (cdr x))))
The error checking for these functions is exactly the same as for car and cdr above.
cons x y
cons is the primitive function to create a new cons , whose car is x and whose cdr is y . 
Examples:
(cons 'a 'b) => (a . b)
(cons 'a (cons 'b (cons 'c nil))) => (a b c)
(cons 'a '(b c d)) => (a b c d)
ncons x
(ncons x) is the same as (cons x nil) . The name of the function is from "nil-cons".
xcons x y
xcons ("exchanged cons") is like cons except that the order of the arguments is reversed. 
Example:
(xcons 'a 'b) => (b . a)
There are two reasons this exists: one is that you might want the arguments to cons evaluated in the other order, and the other is that the compiler might convert calls to cons into calls to xcons for efficiency. In fact, it doesn't.
cons-in-area x y area-number

This function creates a cons in a specific area . (Areas are an advanced feature of storage management; if you aren't interested in them, you can safely skip all this stuff). The first two arguments are the same as the two arguments to cons , and the third is the number of the area in which to create the cons . 

Example:
(cons-in-area 'a 'b my-area) => (a . b)
ncons-in-area x area-number
(ncons-in-area x area-number) = (cons-in-area x nil area-number)
xcons-in-area x y area-number
(xcons-in-area x y area-number) = (cons-in-area y x area-number)
The backquote reader macro facility is also generally useful for creating list structure, especially mostly-constant list structure, or forms constructed by plugging variables into a template. It is documented in the chapter on Macros, see LINK:(macro).
car-location cons
car-location returns a locative pointer to the cell containing the car of cons .
Note: there is no cdr-location function; it is difficult because of the cdr-coding scheme.
7.2 Lists

The following section explains some of the basic functions provided for dealing with lists . There has been some confusion about the term list ever since the beginnings of the language: for the purposes of the following descriptions, a list is the symbol nil , or a cons whose cdr is a list. Note well that although we consider nil to be a list (the list of zero elements), it is a symbol and not a cons, and the listp predicate is not true of it (but perhaps listp will be changed in the future).

last list
last returns the last cons of list . If list is nil , it returns nil . 
Example:
(setq x '(a b c d))
(last x) => (d)
(rplacd (last x) '(e f))
x => '(a b c d e f)
last could have been defined by: 
(defun last (x)
    (cond ((atom x) x)
          ((atom (cdr x)) x)
          ((last (cdr x))) ))
length list
length returns the length of list . The length of a list is the number of top-level conses in it. 
Examples:
(length nil) => 0
(length '(a b c d)) => 4
(length '(a (b c) d)) => 3
length could have been defined by: 
(defun length (x)
    (cond ((atom x) 0)
          ((1+ (length (cdr x)))) ))
or by: 

(defun length (x)
    (do ((n 0 (1+ n))
         (y x (cdr y)))
        ((atom y) n) ))
first Macro
second Macro
third Macro
fourth Macro
fifth Macro
sixth Macro
seventh Macro
(first x) ==> (car x)
(second x) ==> (cadr x)
(third x) ==> (caddr x)
(fourth x) ==> (cadddr x)
etc.
rest1 Macro
rest2 Macro
rest3 Macro
rest4 Macro
(rest1 x) ==> (cdr x)
(rest2 x) ==> (cddr x)
(rest3 x) ==> (cdddr x)
(rest4 x) ==> (cddddr x)
nth n list
(nth n list) returns the n 'th element of list , where the zeroth element is the car of the list. 
Examples:
(nth 1 '(foo bar gack)) => bar
(nth 3 '(foo bar gack)) => nil
Note: this is not the same as the InterLisp function called nth , which is similar to but not exactly the same as the Lisp Machine function nthcdr . Also, some people have used macros and functions called nth of their own in their Maclisp programs, which may not work the same way; be careful. nth could have been defined by: 
(defun nth (n list)
  (do ((i n (1- i))
       (l list (cdr l)))
      ((zerop i) (car l))))
nthcdr n list
(nthcdr n list) cdr s list n times, and returns the result. 
Examples:
(nthcdr 0 '(a b c)) => (a b c)
(nthcdr 2 '(a b c)) => (c)
In other words, it returns the n 'th cdr of the list. This is the similar to InterLisp's function nth , except that the InterLisp function is one-based instead of zero-based; see the InterLisp manual for details. nthcdr is defined by: 
(defun nthcdr (n list)
    (do ((i 0 (1+ i))
	 (list list (cdr list)))
	((= i n) list)))
list &rest args
list constructs and returns a list of its arguments. 
Example:
(list 3 4 'a (car '(b . c)) (+ 6 -2)) => (3 4 a b 4)
list could have been defined by: 
(defun list (&rest args)
    (let ((list (make-list default-cons-area (length args))))
      (do ((l list (cdr l))
	   (a args (cdr a)))
	  ((null a) list)
	(rplaca l (car a)))))
list* &rest args
list* is like list except that the last cons of the constructed list is "dotted". It must be given at least two arguments. 
Example:
(list* 'a 'b 'c 'd) => (a b c . d)
This is like 
(cons 'a (cons 'b (cons 'c 'd)))
list-in-area area-number &rest args
list-in-area is exactly the same as list except that it takes an extra argument, an area number, and creates the list in that area.
make-list area size
This creates and returns a list containing size elements, each of which is nil . size should be a fixnum. The list is allocated in the area specified; if you are not using areas in any special way, just use the value of the symbol default-cons-area . 
Example:
(make-list default-cons-area 3) => (nil nil nil)
Of course, this function is not usually used when the value of the second argument is a constant; if you want a list of three nil s, it is easy enough to type (nil nil nil) . make-list is used when the number of elements is to be computed while the program is being run. make-list and cons are the two primitive list-creation functions which all the other functions call. The difference is that make-list creates a cdr-coded list (see this link).
circular-list &rest args
circular-list constructs a circular list whose elements are args , repeated infinitely. circular-list is the same as list except that the list itself is used as the last cdr, instead of nil . circular-list is especially useful with mapcar , as in the expression 
(mapcar (function +) foo (circular-list 5))
which adds each element of foo to 5.
append &rest lists
The arguments to append are lists. The result is a list which is the concatenation of the arguments. The arguments are not changed (cf. nconc ). 
Example:
(append '(a b c) '(d e f) nil '(g)) => (a b c d e f g)
Note that append copies the top-level list structure of each of its arguments except the last. Thus, to copy a list but not its elements, use (append x nil) . The copylist function is equivalent. A version of append which only accepts two arguments could have been defined by: 
(defun append2 (x y)
    (cond ((null x) y)
          ((cons (car x) (append2 (cdr x) y)) )))
The generalization to any number of arguments could then be made: 
(defun append (&rest args)
    (and args (append2 (car args)
		       (apply (function append) (cdr args)))))
These definitions do not express the full functionality of append ; the real definition minimizes storage utilization by cdr-coding the list it produces, using cdr-next except at the end where a full node is used to link to the last argument, unless the last argument was nil in which case cdr-nil is used.
copylist list &optional area
Returns a list which is equal to list , but not eq . Only the top level of list-structure is copied, i.e. copylist copies in the cdr direction but not in the car direction. The returned list is fully cdr-coded to minimize storage. If the list is "dotted", that is, (cdr (last list)) is a non-nil atom, this will be true of the returned list also. You may optionally specify the area in which to create the new copy.
copylist* list &optional area
This is the same as copylist except that the last cons of the resulting list is never cdr-coded. This makes for increased efficiency if you nconc something onto the list later.
copyalist list &optional area
copyalist is for copying association lists. The top level of list structure of list is copied, just as copylist does. In addition, each element of list which is a cons is replaced in the copy by a new cons with the same car and cdr. You may optionally specify the area in which to create the new copy.
reverse list
reverse creates a new list whose elements are the elements of list taken in reverse order. reverse does not modify its argument, unlike nreverse which is faster but does modify its argument. 
Example:
(reverse '(a b (c d) e)) => (e (c d) b a)
reverse could have been defined by: 
(defun reverse (x)
    (do ((l x (cdr l))         ; scan down argument, 
         (r nil                ; putting each element 
            (cons (car l) r))) ; into list, until 
        ((null l) r)))         ; no more elements.
nconc &rest lists
nconc takes lists as arguments. It returns a list which is the arguments concatenated together. The arguments are changed, rather than copied. (cf. append , LINK:(append-fun)) 
Example:
(setq x '(a b c))
(setq y '(d e f))
(nconc x y) => (a b c d e f)
x => (a b c d e f)
Note that the value of x is now different, since its last cons has been rplacd 'd to the value of y . If the nconc form is evaluated again, it would yield a piece of "circular" list structure, whose printed representation would be (a b c d e f d e f d e f ...) , repeating forever. nconc could have been defined by: 
(defun nconc (x y)		 ;for simplicity, this definition 
    (cond ((null x) y)		 ;only works for 2 arguments. 
          (t (rplacd (last x) y) ;hook y onto  x
              x)))		 ;and return the modified x.
nreverse list
nreverse reverses its argument, which should be a list. The argument is destroyed by rplacd 's all through the list (cf. reverse ). 
Example:
(nreverse '(a b c)) => (c b a)
nreverse could have been defined by: 
(defun nreverse  (x)
    (cond ((null x) nil)
          ((nreverse1 x nil))))

(defun nreverse1 (x y)		;auxiliary function 
    (cond ((null (cdr x)) (rplacd x y))
          ((nreverse1 (cdr x) (rplacd x y)))))
          ;; this last call depends on order of argument evaluation.
Currently, nreverse does something inefficient with cdr-coded lists, however this will be changed. In the meantime reverse might be preferable in some cases.
nreconc x y
(nreconc x y) is exactly the same as (nconc (nreverse x) y) except that it is more efficient. Both x and y should be lists. nreconc could have been defined by: 
(defun nreconc (x y)
    (cond ((null x) y)
          ((nreverse1 x y)) ))
using the same nreverse1 as above.
push Macro
The form is (push item place) , where item is an arbitrary object and place is a reference to a cell containing a list. Usually place is the name of a variable. item is consed onto the front of the list. The form 
(push (hairy-function x y z) variable)
replaces the commonly-used construct 
(setq variable (cons (hairy-function x y z) variable))
and is intended to be more explicit and esthetic. In general, (push item place) expands into (setf place (cons item place)) . (See LINK:(setf-fun) for an explanation of setf .)
pop Macro
The form is (pop place) . The result is the car of the contents of place , and as a side-effect the cdr of the contents is stored back into place . 
Example:
(setq x '(a b c))
(pop x) => a
x => (b c)
In general, (pop place) expands into (prog1 (car place) (setf place (cdr place))) . (See LINK:(setf-fun) for an explanation of setf .)
butlast list
This creates and returns a list with the same elements as list , excepting the last element. 
Examples:
(butlast '(a b c d)) => (a b c)
(butlast '((a b) (c d)) => ((a b))
(butlast '(a)) => nil
(butlast nil) => nil
The name is from the phrase "all elements but the last".
nbutlast list
This is the destructive version of butlast ; it changes the cdr of the second-to-last cons of the list to nil. If there is no second-to-last cons (that is, if the list has fewer than two elements) it returns nil . 
Examples:
(setq foo '(a b c d))
(nbutlast foo) => (a b c)
foo => (a b c)
(nbutlast '(a)) => nil
firstn n list
firstn returns a list of length n , whose elements are the first n elements of list . If list is fewer than n elements long, the remaining elements of the returned list will be nil . 
Example:
(firstn 2 '(a b c d)) => (a b)
(firstn 0 '(a b c d)) => nil
(firstn 6 '(a b c d)) => (a b c d nil nil)
ldiff list sublist
list should be a list, and sublist should be a sublist of list , i.e. one of the conses that make up list . ldiff (meaning List Difference) will return a new list, whose elements are those elements of list that appear before sublist . 
Examples:
(setq x '(a b c d e))
(setq y (cdddr x)) => (d e)
(ldiff x y) => (a b c)
but 
(ldiff '(a b c d) '(c d)) => (a b c d)
since the sublist was not eq to any part of the list.
7.3 Alteration of List Structure
The functions rplaca and rplacd are used to make alterations in already-existing list structure; that is, to change the cars and cdrs of existing conses. The structure is not copied but is physically altered; hence caution should be exercised when using these functions, as strange side-effects can occur if portions of list structure become shared unbeknownst to the programmer. The nconc , nreverse , nreconc , and nbutlast functions already described, and the delq family described later, have the same property. However, they are normally not used for this side-effect; rather, the list-structure modification is purely for efficiency and compatible non-modifying functions are provided.
rplaca x y
(rplaca x y) changes the car of x to y and returns (the modified) x . x should be a cons, but y may be any Lisp object. 
Example:
(setq g '(a b c))
(rplaca (cdr g) 'd) => (d c)
Now  g => (a d c)
rplacd x y
(rplacd x y) changes the cdr of x to y and returns (the modified) x . x should be a cons, but y may be any Lisp object. 
Example:
(setq x '(a b c))
(rplacd x 'd) => (a . d)
Now  x => (a . d)
Note to Maclisp users: rplacd should not be used to set the property list of a symbol, although there is a compatibility mode in which it will work. See car (LINK:(car-fun)). The right way to set a property list is with setplist (see LINK:(setplist-fun)). 'findex "setplist"

subst new old s-exp
(subst new old s-exp) substitutes new for all occurrences of old in s-exp , and returns the modified copy of s-exp . The original s-exp is unchanged, as subst recursively copies all of s-exp replacing elements equal to old as it goes. If new and old are nil , s-exp is just copied, which is a convenient way to copy arbitrary list structure. 
Example:
(subst 'Tempest 'Hurricane
       '(Shakespeare wrote (The Hurricane)))
    => (Shakespeare wrote (The Tempest))
subst could have been defined by: 
(defun subst (new old s-exp)
    (cond ((equal s-exp old) new) ;if item eq to old, replace. 
          ((atom s-exp) s-exp)    ;if no substructure, return arg. 
          ((cons (subst new old (car s-exp))  ;otherwise recurse. 
                 (subst new old (cdr s-exp))))))
Note that this function is not "destructive"; that is, it does not change the car or cdr of any already-existing list structure.
nsubst new old s-exp
nsubst is a destructive version of subst . The list structure of s-exp is altered by replacing each occurrence of old with new . nsubst could have been defined as 
(defun nsubst (new old s-exp)
    (cond ((eq s-exp old) new)	  ;If item eq to old, replace. 
          ((atom s-exp) s-exp)    ;If no substructure, return arg. 
	  (t ;; Otherwise, recurse. 
	     (rplaca s-exp (nsubst new old (car s-exp)))
	     (rplacd s-exp (nsubst new old (cdr s-exp)))
	     s-exp)))
sublis alist S-expression
sublis makes substitutions for symbols in an S-expression (a structure of nested lists). The first argument to sublis is an association list (see the next section). The second argument is the S-expression in which substitutions are to be made. sublis looks at all symbols in the S-expression; if a symbol appears in the association list occurrences of it are replaced by the object it is associated with. The argument is not modified; new conses are created where necessary and only where necessary, so the newly created structure shares as much of its substructure as possible with the old. For example, if no substitutions are made, the result is eq to the old S-expression. 
Example:
(sublis '((x . 100) (z . zprime))
        '(plus x (minus g z x p) 4))
   => (plus 100 (minus g zprime 100 p) 4)
nsublis alist S-expression
nsublis is like sublis but changes the original list structure instead of creating new.
7.4 Cdr-Coding
There is an issue which those who must be concerned with efficiency will need to think about. In the Lisp Machine there are actually two kinds of lists; normal lists and cdr-coded lists. Normal lists take two words for each cons , while cdr-coded lists require only one word for each cons . The saving is achieved by taking advantage of the usual structure of lists to avoid storing the redundant cdrs which link together the conses which make up the list. Ordinarily, rplacd 'ing such a list would be impossible, since there is no explicit representation of the cdr to be modified. However, in the Lisp machine system it is merely somewhat expensive; a 2-word ordinary cons must be allocated and linked into the list by an invisible pointer. This is slower than an ordinary rplacd , uses extra space, and slows down future accessing of the list. One should try to use normal lists for those data structures that will be subject to rplacd ing operations, including nconc and nreverse , and cdr-coded lists for other structures. The functions cons , xcons , ncons , and their area variants make normal lists. The functions list , list* , list-in-area , make-list , and append make cdr-coded lists. The other list-creating functions, including read , currently make normal lists, but this should not be relied upon. Some functions, such as sort , take special care to operate efficiently on cdr-coded lists (sort treats them as arrays). nreverse is rather slow on cdr-coded lists, currently, since it simple-mindedly uses rplacd , however this will be changed. It is currently not planned that the garbage collector compact ordinary lists into cdr-coded lists. (append x nil) is a suitable way to copy a list, converting it into cdr-coded form.
7.5 Tables
Lisp Machine Lisp includes several functions which simplify the maintenance of tabular data structures of several varieties. The simplest is a plain list of items, which models (approximately) the concept of a set .

There are functions to add (cons ), remove (delete , delq , del , del-if , del-if-not , remove , remq , rem , rem-if , rem-if-not ), and search for (member , memq , mem ) items in a list. Set union, intersection, and difference functions are easily written using these.

Association lists are very commonly used. An association list is a list of conses. The car of each cons is a "key" and the cdr is a "datum", or a list of associated data. The functions assoc , assq , ass , memass , and rassoc may be used to retrieve the data, given the key. Structured records can be stored as association lists or as stereotyped cons-structures where each element of the structure has a certain car-cdr path associated with it. However, these are better implemented using structure macros (see this link). Simple list-structure is very convenient, but may not be efficient enough for large data bases because it takes a long time to search a long list. Lisp Machine lisp includes a hashing function (sxhash ) which aids in the construction of more efficient, hairier structures.

memq item list
(memq item list) returns nil if item is not one of the elements of list . Otherwise, it returns the portion of list beginning with the first occurrence of item . The comparison is made by eq . list is searched on the top level only. Because memq returns nil if it doesn't find anything, and something non-nil if it finds something, it is often used as a predicate. 
Examples:
(memq 'a '(1 2 3 4)) => nil
(memq 'a '(g (x y) c a d e a f)) => (a d e a f)
Note that the value returned by memq is eq to the portion of the list beginning with a . Thus rplaca on the result of memq may be used, if you first check to make sure memq did not return nil . 
Example:
(*catch 'lose
	(rplaca (or (memq x z)
		    (*throw 'lose nil))
		y)
	)
memq could have been defined by: 
(defun memq (item list)
    (cond ((atom list) nil)
          ((eq item (car list)) list)
          ((memq item (cdr list))) ))
memq is hand-coded in microcode and therefore especially fast.
member item list
member is like memq , except equal is used for the comparison, instead of eq . member could have been defined by: 
(defun member (item list)
    (cond ((null list) nil)
          ((equal item (car list)) list)
          ((member item (cdr list))) ))
mem predicate item list
mem is the same as memq except that it takes an extra argument which should be a predicate of two arguments, which is used for the comparison instead of eq . (mem 'eq a b) is the same as (memq a b) . (mem 'equal a b) is the same as (member a b) . mem is usually used with equality predicates other than eq and equal , such as = , char-equal or string-equal .
tailp tail list
A tail of a list is anything that can be obtained by taking cdr of it zero or more times. tailp is used to ask whether tail is a tail of list . That is, it cdr 's down list checking at each step whether what it has got is eq to tail . If so, the value is t .
delq item list &optional n
(delq item list) returns the list with all top-level occurrences of item removed. eq is used for the comparison. The argument list is actually modified (rplacd 'ed) when instances of item are spliced out. delq should be used for value, not for effect. That is, use 
(setq a (delq 'b a))
rather than 
(delq 'b a)
The latter is not equivalent when the first element of the value of a is b . (delq item list n) is like (delq item list) except only the first n instances of item are deleted. n is allowed to be zero. If n is greater than the number of occurrences of item in the list, all occurrences of item in the list will be deleted. 
Example:
(delq 'a '(b a c (a b) d a e)) => (b c (a b) d e)
delq could have been defined by: 
(defun delq (item list &optional (n 7777777))  ;7777777 as infinity. 
    (cond ((or (atom list) (zerop n)) list)
          ((eq item (car list))
	   (delq item (cdr list) (1- n)))
          ((rplacd list (delq item (cdr list) n)))))
delete item list &optional n
delete is the same as delq except that equal is used for the comparison instead of eq .
del predicate item list &optional n
del is the same as delq except that it takes an extra argument which should be a predicate of two arguments, which is used for the comparison instead of eq . (del 'eq a b) is the same as (delq a b) . (c.f. mem , LINK:(mem-fun))
remq item list &optional n
remq is similar to delq , except that the list is not altered; rather, a new list is returned. 
Examples:
(setq x '(a b c d e f))
(remq 'b x) => (a c d e f)
x => (a b c d e f)
(remq 'b '(a b c b a b) 2) => (a c a b)
remove item list &optional n
remove is the same as remq except that equal is used for the comparison instead of eq .
rem predicate item list &optional n
rem is the same as remq except that it takes an extra argument which should be a predicate of two arguments, which is used for the comparison instead of eq . (rem 'eq a b) is the same as (remq a b) . (c.f. mem LINK:(mem-fun))
rem-if predicate list
predicate should be a function of one argument. rem-if makes a new list by applying predicate to all of the elements of list and removing the ones for which the predicate returns non-nil . The function's name means "remove if this condition is true".
rem-if-not predicate list
predicate should be a function of one argument. rem-if-not makes a new list by applying predicate to all of the elements of list and removing the ones for which the predicate returns nil . The function's name means "remove if this condition is not true"; i.e. it keeps the elements for which predicate is true.
del-if predicate list
del-if is just like rem-if except that it modifies list rather than creating a new list. See rem-if .
del-if-not predicate list
del-if-not is just like rem-if-not except that it modifies list rather than creating a new list. See rem-if-not .
every list predicate &optional step-function
every returns t if predicate returns non-nil when applied to every element of list , or nil if predicate returns nil for some element. If step-function is present, it replaces cdr as the function used to get to the next element of the list.
some list predicate &optional step-function
some returns a tail of list such that the car of the tail is the first element that the predicate returns non-nil when applied to, or nil if predicate returns nil for every element. If step-function is present, it replaces cdr as the function used to get to the next element of the list.
tailp sublist list
Returns t if sublist is a sublist of list (i.e. one of the conses that makes up list ). Otherwise returns nil .
sxhash S-expression

sxhash computes a hash code of an S-expression, and returns it as a fixnum, which may be positive or negative. A property of sxhash is that (equal x y) implies (= (sxhash x) (sxhash y)) . The number returned by sxhash is some possibly large number in the range allowed by fixnums. It is guaranteed that: .break 1)SAIL sxhash for a symbol will always be positive. .break 2)SAIL sxhash of any particular expression will be constant in a particular implementation for all time, probably. .break 3)SAIL sxhash of any object of type random will be zero. .break 4)SAIL sxhash of a fixnum will = that fixnum. Here is an example of how to use sxhash in maintaining hash tables of S-expressions: 

(defun knownp (x)    ;look up x in the table 
  (prog (i bkt)
    (setq i (plus 76 (remainder (sxhash x) 77)))	
      ;The remainder should be reasonably randomized between
      ;-76 and 76, thus table size must be > 175 octal.
    (setq bkt (aref table i))
      ;bkt is thus a list of all those expressions that hash
      ;into the same number as does x.
    (return (memq x bkt))))
To write an "intern" for S-expressions, one could 
(defun sintern (x)
  (prog (bkt i tem)
    (setq bkt (aref table
		    (setq i (+ 2n-2 (SAIL\ (sxhash x) 2n-1)))))
	;2n-1 and 2n-2 stand for a power of 2 minus one and 
	;minus two respectively.  This is a good choice to 
	;randomize the result of the remainder operation.
    (return (cond ((setq tem (memq x bkt)) 
		   (car tem))
		  (t (aset (cons x bkt) table i)
		     x)))))
assq item alist

(assq item alist) looks up item in the association list (list of conses) alist . The value is the first cons whose car is eq to x , or nil if there is none such. 

Examples:
(assq 'r '((a . b) (c . d) (r . x) (s . y) (r . z)))
	=>  (r . x)

(assq 'fooo '((foo . bar) (zoo . goo))) => nil

(assq 'b '((a b c) (b c d) (x y z))) => (b c d)
It is okay to rplacd the result of assq as long as it is not nil , if your intention is to "update" the "table" that was assq 's second argument. 
Example:
(setq values '((x .  100) (y  . 200) (z .  50)))
(assq 'y values) => (y . 200)
(rplacd (assq 'y values)  201)
(assq 'y values)  => (y . 201) now
A typical trick is to say (cdr (assq x y)) . Assuming the cdr of nil is guaranteed to be nil , this yields nil if no pair is found (or if a pair is found whose cdr is nil .) assq could have been defined by: 
(defun assq (item list)
    (cond ((null list) nil)
          ((eq item (caar list)) (car list))
          ((assq item (cdr list))) ))
assoc item alist
assoc is like assq except that the comparison uses equal instead of eq . 
Example:
(assoc '(a b) '((x . y) ((a b) . 7) ((c . d) .e)))
	=> ((a b) . 7)
assoc could have been defined by: 
(defun assoc (item list)
    (cond ((null list) nil)
          ((equal item (caar list)) (car list))
          ((assoc item (cdr list))) ))
ass predicate item alist
ass is the same as assq except that it takes an extra argument which should be a predicate of two arguments, which is used for the comparison instead of eq . (ass 'eq a b) is the same as (assq a b) . (c.f. mem LINK:(mem-fun))
memass predicate item alist
memass searches alist just like ass , but returns the portion of the list beginning with the pair containing item , rather than the pair itself. (car (memass x y z)) = (ass x y z) .
rassoc item alist
rassoc means reverse assoc . It is like assoc , but it tries to find an element of alist whose cdr (not car) is equal to item . rassoc is defined by: 
(defun rassoc (item in-list) 
    (do l in-list (cdr l) (null l) 
      (and (equal item (cdar l)) 
	   (return (car l)))))
sassq item alist fcn
(sassq item alist fcn) is like (assq item alist) except that if item is not found in alist , instead of returning nil , sassq calls the function fcn with no arguments. sassq could have been defined by: 
(defun sassq (item alist fcn)
    (or (assq item alist)
        (apply fcn nil)))
sassq and sassoc (see below) are of limited use. These are primarily leftovers from Lisp 1.5.
sassoc item alist fcn
(sassoc item alist fcn) is like (assoc item alist) except that if item is not found in alist , instead of returning nil , sassoc calls the function fcn with no arguments. sassoc could have been defined by: 
(defun sassoc (item alist fcn)
    (or (assoc item alist)
        (apply fcn nil)))
pairlis cars cdrs
pairlis takes two lists and makes an association list which associates elements of the first list with corresponding elements of the second list. 
Example:
(pairlis '(beef clams kitty) '(roast fried yu-shiang))
   => ((beef . roast) (clams . fried) (kitty . yu-shiang))
find-position-in-list item list
find-position-in-list looks down list for an element which is eq to item , like memq. However, it returns the numeric index in the list at which it found the first occurence of item , or nil if it did not find it at all. 
Examples:
(find-position-in-list 'a '(a b c)) => 0
(find-position-in-list 'c '(a b c)) => 2
(find-position-in-list 'e '(a b c)) => nil
find-position-in-list-equal item list
find-position-in-list-equal is exactly the same as find-position-in-list , except that the comparison is done with equal instead of eq .
7.6 Tables

[The stuff in FD.SYM will get moved here, leaving a pointer behind, and will be generalized for disembodied property lists and made to clarify the distinction between a plist and a paired list.]

7.7 Tables

A hash table is a Lisp object that works something like a property list. Each hash table has a set of entries , each of which associates a particular key with a particular value . The basic functions that deal with hash tables can create entries, delete entries, and find the value that is associated with a given key. Finding the value is very fast even if there are many entries, because hashing is used; this is an important advantage of hash tables over property lists. A given hash table can only associate one value with a given key ; if you try to add a second value it will replace the first. Hash tables are created with the function make-hash-table , which takes various options. New entries are added to hash tables with the puthash function. To look up a key and find the associated value, the gethash function is used. To remove an entry, use remhash . Here is a simple example. 

(setq a (make-hash-table))

(puthash 'color 'brown a)

(puthash 'name 'fred a)

(gethash 'color a) => brown

(gethash 'name a) => fred
In this example, the symbols color and name are being used as keys, and the symbols brown and fred are being used as the associated values. The hash table has two items in it, one of which associates from color to brown , and the other of which associates from name to fred . Keys do not have to be symbols; they can be any Lisp object. Likewise values can be any Lisp object. The Lisp function eq is used to compare keys, rather than equal . This means that keys are really objects, but it means that it is not reasonable to use numbers other than fixnums as keys. Hash tables are properly interfaced to the relocating garbage collector so that garbage collection will have no perceptible effect on the functionality of hash tables. When a hash table is first created, it has a size , which is the maximum number of entries it can hold. Usually the actual capacity of the table is somewhat less, since the hashing is not perfectly collision-free. With the maximum possible bad luck, the capacity could be very much less, but this rarely happens. If so many entries are added that the capacity is exceeded, the hash table will automatically grow, and the entries will be rehashed (new hash values will be recomputed, and everything will be rearranged so that the fast hash lookup still works). This is transparent to the caller; it all happens automatically. If the calling program is using multiprocessing, it must be careful to make sure that there are never two processes both referencing the hash table at the same time. There is no locking built into hash tables; if you have two processes that both want to reference the same hash table, you must arrange mutual exclusion yourself by using a lock or some other means. Don't worry about this if you don't use multiprocessing; but if you do use multiprocessing, you will have a lot of trouble if you don't understand this.
make-hash-table &rest options
This creates a new hash table. Valid option keywords are:
:sizeSet the initial size of the hash table, in entries, as a fixnum. The default is 100 (octal). The actual size is rounded up from the size you specify to the next "good" size. You won't necessarily be able to store this many entries into the table before it overflows and becomes bigger; but except in the case of extreme bad luck you will be able to store almost this many.
:areaSpecify the area in which the hash table should be created. This is just like the first argument to make-array (see LINK:(make-array-fun)). Defaults to nil (i.e. default-cons-area ).
:rehash-function
Specify the function to be used for rehashing when the table becomes full. Defaults to the internal rehashing function that does the usual thing. If you want to write your own rehashing function, you will have to understand all the internals of how hash tables work. These internals are not documented here, as the best way to learn them is to read the source code.
:rehash-sizeSpecifies how much to increase the size of the hash table when it becomes full. This can be a fixnum which is the number of entries to add, or it can be a flonum which is the ratio of the new size to the old size. The default is 1.3 , which causes the table to be made 30% bigger each time it has to grow.
gethash key hash-table
Find the entry in hash-table whose key is key , and return the associated value. If there is no such entry, return nil . Returns a second value, which is t if an entry was found or nil if there is no entry for key in this table.
puthash key value hash-table
Create an entry associating key to value ; if there is already an entry for key , then replace the value of that entry with value . Returns value .
remhash key hash-table
Remove any entry for key in hash-table . Returns t if there was an entry or nil if there was not.
maphash function hash-table
For each entry in hash-table , call function on two arguments: the key of the entry and the value of the entry.
clrhash hash-table
Remove all the entries from hash-table . Returns the hash table itself.
The describe function (see LINK:(describe-fun)) prints a variety of useful information when applied to a hash table. This hash table facility is similar to the hasharray facility of Interlisp, and some of the function names are the same. However, it is not compatible. The exact details and the order of arguments are designed to be consistent with the rest of the Lisp machine rather than with Interlisp. For instance, the order of arguments to maphash is different, we do not have the Interlisp "system hash table", and we do not have the Interlisp restriction that keys and values may not be nil .
7.8 Sorting

Several functions are provided for sorting arrays and lists. These functions use algorithms which always terminate no matter what sorting predicate is used, provided only that the predicate always terminates. The array sort is not necessarily stable ; that is, equal items may not stay in their original order. However the list sort is stable. After sorting, the argument (be it list or array) is rearranged internally so as to be completely ordered. In the case of an array argument, this is accomplished by permuting the elements of the array, while in the list case, the list is reordered by rplacd 's in the same manner as nreverse . Thus if the argument should not be clobbered, the user must sort a copy of the argument, obtainable by fillarray or append , as appropriate. Should the comparison predicate cause an error, such as a wrong type argument error, the state of the list or array being sorted is undefined. However, if the error is corrected the sort will, of course, proceed correctly. The sorting package is smart about cdr-coded lists.

sort table predicate
The first argument to sort is an array or a list. The second is a predicate, which must be applicable to all the objects in the array or list. The predicate should take two arguments, and return non-nil if and only if the first argument is strictly less than the second (in some appropriate sense). The sort function proceeds to sort the contents of the array or list under the ordering imposed by the predicate, and returns the array or list modified into sorted order, i.e. its modified first argument. Note that since sorting requires many comparisons, and thus many calls to the predicate, sorting will be much faster if the predicate is a compiled function rather than interpreted. 
Example:
(defun mostcar (x)
    (cond ((symbolp x) x)
          ((mostcar (car x)))))

(sort 'fooarray
      (function (lambda (x y)
	  (alphalessp (mostcar x) (mostcar y)))))
If fooarray contained these items before the sort: 
(Tokens (The lion sleeps tonight))
(Carpenters (Close to you))
((Rolling Stones) (Brown sugar))
((Beach Boys) (I get around))
(Beatles (I want to hold your hand))
then after the sort fooarray would contain: 
((Beach Boys) (I get around))
(Beatles (I want to hold your hand))
(Carpenters (Close to you))
((Rolling Stones) (Brown sugar))
(Tokens (The lion sleeps tonight))
sortcar x predicate
sortcar is exactly like sort , but the items in the array or list being sorted should all be conses. sortcar takes the car of each item before handing two items to the predicate. Thus sortcar is to sort as mapcar is to maplist .
The spelling of the names of the next two functions will be corrected at some point.
sort-grouped-array array group-size predicate
sorted-array considers its array argument to be composed of records of -size elements each. These records are considered as units, and are sorted with respect to one another. The predicate is applied to the first element of each record; so the first elements act as the keys on which the records are sorted.
sort-grouped-array-group-key array group-size predicate
This is like sorted-array except that the predicate is applied to four arguments: an array, an index into that array, a second array, and an index into the second array. predicate should consider each index as a subscript of the first element of a record in the corresponding array, and compare the two records. This is more general than sorted-array since the function can get at all of the elements of the relevant records, instead of only the first element.