--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/man/lispref/lists.texi	Mon Aug 13 08:45:50 2007 +0200
@@ -0,0 +1,1819 @@
+@c -*-texinfo-*-
+@c This is part of the XEmacs Lisp Reference Manual.
+@c Copyright (C) 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc. 
+@c See the file lispref.texi for copying conditions.
+@setfilename ../../info/lists.info
+@node Lists, Sequences Arrays Vectors, Strings and Characters, Top
+@chapter Lists
+@cindex list
+@cindex element (of list)
+
+  A @dfn{list} represents a sequence of zero or more elements (which may
+be any Lisp objects).  The important difference between lists and
+vectors is that two or more lists can share part of their structure; in
+addition, you can insert or delete elements in a list without copying
+the whole list.
+
+@menu
+* Cons Cells::              How lists are made out of cons cells.
+* Lists as Boxes::          Graphical notation to explain lists.
+* List-related Predicates:: Is this object a list?  Comparing two lists.
+* List Elements::           Extracting the pieces of a list.
+* Building Lists::          Creating list structure.
+* Modifying Lists::         Storing new pieces into an existing list.
+* Sets And Lists::          A list can represent a finite mathematical set.
+* Association Lists::       A list can represent a finite relation or mapping.
+* Property Lists::          A different way to represent a finite mapping.
+* Weak Lists::              A list with special garbage-collection behavior.
+@end menu
+
+@node Cons Cells
+@section Lists and Cons Cells
+@cindex lists and cons cells
+@cindex @code{nil} and lists
+
+  Lists in Lisp are not a primitive data type; they are built up from
+@dfn{cons cells}.  A cons cell is a data object that represents an
+ordered pair.  It records two Lisp objects, one labeled as the @sc{car},
+and the other labeled as the @sc{cdr}.  These names are traditional; see
+@ref{Cons Cell Type}.  @sc{cdr} is pronounced ``could-er.''
+
+  A list is a series of cons cells chained together, one cons cell per
+element of the list.  By convention, the @sc{car}s of the cons cells are
+the elements of the list, and the @sc{cdr}s are used to chain the list:
+the @sc{cdr} of each cons cell is the following cons cell.  The @sc{cdr}
+of the last cons cell is @code{nil}.  This asymmetry between the
+@sc{car} and the @sc{cdr} is entirely a matter of convention; at the
+level of cons cells, the @sc{car} and @sc{cdr} slots have the same
+characteristics.
+
+@cindex list structure
+  Because most cons cells are used as part of lists, the phrase
+@dfn{list structure} has come to mean any structure made out of cons
+cells.
+
+  The symbol @code{nil} is considered a list as well as a symbol; it is
+the list with no elements.  For convenience, the symbol @code{nil} is
+considered to have @code{nil} as its @sc{cdr} (and also as its
+@sc{car}).
+
+  The @sc{cdr} of any nonempty list @var{l} is a list containing all the
+elements of @var{l} except the first.
+
+@node Lists as Boxes
+@section Lists as Linked Pairs of Boxes
+@cindex box representation for lists
+@cindex lists represented as boxes
+@cindex cons cell as box
+
+  A cons cell can be illustrated as a pair of boxes.  The first box
+represents the @sc{car} and the second box represents the @sc{cdr}.
+Here is an illustration of the two-element list, @code{(tulip lily)},
+made from two cons cells:
+
+@example
+@group
+ ---------------         ---------------
+| car   | cdr   |       | car   | cdr   |
+| tulip |   o---------->| lily  |  nil  |
+|       |       |       |       |       |
+ ---------------         ---------------
+@end group
+@end example
+
+  Each pair of boxes represents a cons cell.  Each box ``refers to'',
+``points to'' or ``contains'' a Lisp object.  (These terms are
+synonymous.)  The first box, which is the @sc{car} of the first cons
+cell, contains the symbol @code{tulip}.  The arrow from the @sc{cdr} of
+the first cons cell to the second cons cell indicates that the @sc{cdr}
+of the first cons cell points to the second cons cell.
+
+  The same list can be illustrated in a different sort of box notation
+like this:
+
+@example
+@group
+    ___ ___      ___ ___
+   |___|___|--> |___|___|--> nil
+     |            |
+     |            |
+      --> tulip    --> lily
+@end group
+@end example
+
+  Here is a more complex illustration, showing the three-element list,
+@code{((pine needles) oak maple)}, the first element of which is a
+two-element list:
+
+@example
+@group
+    ___ ___      ___ ___      ___ ___
+   |___|___|--> |___|___|--> |___|___|--> nil
+     |            |            |
+     |            |            |
+     |             --> oak      --> maple
+     |
+     |     ___ ___      ___ ___
+      --> |___|___|--> |___|___|--> nil
+            |            |
+            |            |
+             --> pine     --> needles
+@end group
+@end example
+
+  The same list represented in the first box notation looks like this:
+
+@example
+@group
+ --------------       --------------       --------------
+| car   | cdr  |     | car   | cdr  |     | car   | cdr  |
+|   o   |   o------->| oak   |   o------->| maple |  nil |
+|   |   |      |     |       |      |     |       |      |
+ -- | ---------       --------------       --------------
+    |
+    |
+    |        --------------       ----------------
+    |       | car   | cdr  |     | car     | cdr  |
+     ------>| pine  |   o------->| needles |  nil |
+            |       |      |     |         |      |
+             --------------       ----------------
+@end group
+@end example
+
+  @xref{Cons Cell Type}, for the read and print syntax of cons cells and
+lists, and for more ``box and arrow'' illustrations of lists.
+
+@node List-related Predicates
+@section Predicates on Lists
+
+  The following predicates test whether a Lisp object is an atom, is a
+cons cell or is a list, or whether it is the distinguished object
+@code{nil}.  (Many of these predicates can be defined in terms of the
+others, but they are used so often that it is worth having all of them.)
+
+@defun consp object
+This function returns @code{t} if @var{object} is a cons cell, @code{nil}
+otherwise.  @code{nil} is not a cons cell, although it @emph{is} a list.
+@end defun
+
+@defun atom object
+@cindex atoms
+This function returns @code{t} if @var{object} is an atom, @code{nil}
+otherwise.  All objects except cons cells are atoms.  The symbol
+@code{nil} is an atom and is also a list; it is the only Lisp object
+that is both.
+
+@example
+(atom @var{object}) @equiv{} (not (consp @var{object}))
+@end example
+@end defun
+
+@defun listp object
+This function returns @code{t} if @var{object} is a cons cell or
+@code{nil}.  Otherwise, it returns @code{nil}.
+
+@example
+@group
+(listp '(1))
+     @result{} t
+@end group
+@group
+(listp '())
+     @result{} t
+@end group
+@end example
+@end defun
+
+@defun nlistp object
+This function is the opposite of @code{listp}: it returns @code{t} if
+@var{object} is not a list.  Otherwise, it returns @code{nil}.
+
+@example
+(listp @var{object}) @equiv{} (not (nlistp @var{object}))
+@end example
+@end defun
+
+@defun null object
+This function returns @code{t} if @var{object} is @code{nil}, and
+returns @code{nil} otherwise.  This function is identical to @code{not},
+but as a matter of clarity we use @code{null} when @var{object} is
+considered a list and @code{not} when it is considered a truth value
+(see @code{not} in @ref{Combining Conditions}).
+
+@example
+@group
+(null '(1))
+     @result{} nil
+@end group
+@group
+(null '())
+     @result{} t
+@end group
+@end example
+@end defun
+
+@need 2000
+
+@node List Elements
+@section Accessing Elements of Lists
+@cindex list elements
+
+@defun car cons-cell
+This function returns the value pointed to by the first pointer of the
+cons cell @var{cons-cell}.  Expressed another way, this function
+returns the @sc{car} of @var{cons-cell}.
+
+As a special case, if @var{cons-cell} is @code{nil}, then @code{car}
+is defined to return @code{nil}; therefore, any list is a valid argument
+for @code{car}.  An error is signaled if the argument is not a cons cell
+or @code{nil}.
+
+@example
+@group
+(car '(a b c))
+     @result{} a
+@end group
+@group
+(car '())
+     @result{} nil
+@end group
+@end example
+@end defun
+
+@defun cdr cons-cell
+This function returns the value pointed to by the second pointer of
+the cons cell @var{cons-cell}.  Expressed another way, this function
+returns the @sc{cdr} of @var{cons-cell}.
+
+As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr}
+is defined to return @code{nil}; therefore, any list is a valid argument
+for @code{cdr}.  An error is signaled if the argument is not a cons cell
+or @code{nil}.
+
+@example
+@group
+(cdr '(a b c))
+     @result{} (b c)
+@end group
+@group
+(cdr '())
+     @result{} nil
+@end group
+@end example
+@end defun
+
+@defun car-safe object
+This function lets you take the @sc{car} of a cons cell while avoiding
+errors for other data types.  It returns the @sc{car} of @var{object} if
+@var{object} is a cons cell, @code{nil} otherwise.  This is in contrast
+to @code{car}, which signals an error if @var{object} is not a list.
+
+@example
+@group
+(car-safe @var{object})
+@equiv{}
+(let ((x @var{object}))
+  (if (consp x)
+      (car x)
+    nil))
+@end group
+@end example
+@end defun
+
+@defun cdr-safe object
+This function lets you take the @sc{cdr} of a cons cell while
+avoiding errors for other data types.  It returns the @sc{cdr} of
+@var{object} if @var{object} is a cons cell, @code{nil} otherwise.
+This is in contrast to @code{cdr}, which signals an error if
+@var{object} is not a list.
+
+@example
+@group
+(cdr-safe @var{object})
+@equiv{}
+(let ((x @var{object}))
+  (if (consp x)
+      (cdr x)
+    nil))
+@end group
+@end example
+@end defun
+
+@defun nth n list
+This function returns the @var{n}th element of @var{list}.  Elements
+are numbered starting with zero, so the @sc{car} of @var{list} is
+element number zero.  If the length of @var{list} is @var{n} or less,
+the value is @code{nil}.
+
+If @var{n} is negative, @code{nth} returns the first element of
+@var{list}.
+
+@example
+@group
+(nth 2 '(1 2 3 4))
+     @result{} 3
+@end group
+@group
+(nth 10 '(1 2 3 4))
+     @result{} nil
+@end group
+@group
+(nth -3 '(1 2 3 4))
+     @result{} 1
+
+(nth n x) @equiv{} (car (nthcdr n x))
+@end group
+@end example
+@end defun
+
+@defun nthcdr n list
+This function returns the @var{n}th @sc{cdr} of @var{list}.  In other
+words, it removes the first @var{n} links of @var{list} and returns
+what follows.
+
+If @var{n} is zero or negative, @code{nthcdr} returns all of
+@var{list}.  If the length of @var{list} is @var{n} or less,
+@code{nthcdr} returns @code{nil}.
+
+@example
+@group
+(nthcdr 1 '(1 2 3 4))
+     @result{} (2 3 4)
+@end group
+@group
+(nthcdr 10 '(1 2 3 4))
+     @result{} nil
+@end group
+@group
+(nthcdr -3 '(1 2 3 4))
+     @result{} (1 2 3 4)
+@end group
+@end example
+@end defun
+
+Many convenience functions are provided to make it easier for you to
+access particular elements in a nested list.  All of these can be
+rewritten in terms of the functions just described.
+
+@defun caar cons-cell
+@defunx cadr cons-cell
+@defunx cdar cons-cell
+@defunx cddr cons-cell
+@defunx caaar cons-cell
+@defunx caadr cons-cell
+@defunx cadar cons-cell
+@defunx caddr cons-cell
+@defunx cdaar cons-cell
+@defunx cdadr cons-cell
+@defunx cddar cons-cell
+@defunx cdddr cons-cell
+@defunx caaaar cons-cell
+@defunx caaadr cons-cell
+@defunx caadar cons-cell
+@defunx caaddr cons-cell
+@defunx cadaar cons-cell
+@defunx cadadr cons-cell
+@defunx caddar cons-cell
+@defunx cadddr cons-cell
+@defunx cdaaar cons-cell
+@defunx cdaadr cons-cell
+@defunx cdadar cons-cell
+@defunx cdaddr cons-cell
+@defunx cddaar cons-cell
+@defunx cddadr cons-cell
+@defunx cdddar cons-cell
+@defunx cddddr cons-cell
+Each of these functions is equivalent to one or more applications of
+@code{car} and/or @code{cdr}.  For example,
+
+@example
+(cadr x)
+@end example
+
+is equivalent to
+
+@example
+(car (cdr x))
+@end example
+
+and
+
+@example
+(cdaddr x)
+@end example
+
+is equivalent to
+
+@example
+(cdr (car (cdr (cdr x))))
+@end example
+
+That is to say, read the a's and d's from right to left and apply
+a @code{car} or @code{cdr} for each a or d found, respectively.
+@end defun
+
+@defun first list
+This is equivalent to @code{(nth 0 @var{list})}, i.e. the first element
+of @var{list}. (Note that this is also equivalent to @code{car}.)
+@end defun
+
+@defun second list
+This is equivalent to @code{(nth 1 @var{list})}, i.e. the second element
+of @var{list}.
+@end defun
+
+@defun third list
+@defunx fourth list
+@defunx fifth list
+@defunx sixth list
+@defunx seventh list
+@defunx eighth list
+@defunx ninth list
+@defunx tenth list
+These are equivalent to @code{(nth 2 @var{list})} through
+@code{(nth 9 @var{list})} respectively, i.e. the third through tenth
+elements of @var{list}.
+@end defun
+
+@node Building Lists
+@section Building Cons Cells and Lists
+@cindex cons cells
+@cindex building lists
+
+  Many functions build lists, as lists reside at the very heart of Lisp.
+@code{cons} is the fundamental list-building function; however, it is
+interesting to note that @code{list} is used more times in the source
+code for Emacs than @code{cons}.
+
+@defun cons object1 object2
+This function is the fundamental function used to build new list
+structure.  It creates a new cons cell, making @var{object1} the
+@sc{car}, and @var{object2} the @sc{cdr}.  It then returns the new cons
+cell.  The arguments @var{object1} and @var{object2} may be any Lisp
+objects, but most often @var{object2} is a list.
+
+@example
+@group
+(cons 1 '(2))
+     @result{} (1 2)
+@end group
+@group
+(cons 1 '())
+     @result{} (1)
+@end group
+@group
+(cons 1 2)
+     @result{} (1 . 2)
+@end group
+@end example
+
+@cindex consing
+@code{cons} is often used to add a single element to the front of a
+list.  This is called @dfn{consing the element onto the list}.  For
+example:
+
+@example
+(setq list (cons newelt list))
+@end example
+
+Note that there is no conflict between the variable named @code{list}
+used in this example and the function named @code{list} described below;
+any symbol can serve both purposes.
+@end defun
+
+@defun list &rest objects
+This function creates a list with @var{objects} as its elements.  The
+resulting list is always @code{nil}-terminated.  If no @var{objects}
+are given, the empty list is returned.
+
+@example
+@group
+(list 1 2 3 4 5)
+     @result{} (1 2 3 4 5)
+@end group
+@group
+(list 1 2 '(3 4 5) 'foo)
+     @result{} (1 2 (3 4 5) foo)
+@end group
+@group
+(list)
+     @result{} nil
+@end group
+@end example
+@end defun
+
+@defun make-list length object
+This function creates a list of length @var{length}, in which all the
+elements have the identical value @var{object}.  Compare
+@code{make-list} with @code{make-string} (@pxref{Creating Strings}).
+
+@example
+@group
+(make-list 3 'pigs)
+     @result{} (pigs pigs pigs)
+@end group
+@group
+(make-list 0 'pigs)
+     @result{} nil
+@end group
+@end example
+@end defun
+
+@defun append &rest sequences
+@cindex copying lists
+This function returns a list containing all the elements of
+@var{sequences}.  The @var{sequences} may be lists, vectors, or strings,
+but the last one should be a list.  All arguments except the last one
+are copied, so none of them are altered.
+
+More generally, the final argument to @code{append} may be any Lisp
+object.  The final argument is not copied or converted; it becomes the
+@sc{cdr} of the last cons cell in the new list.  If the final argument
+is itself a list, then its elements become in effect elements of the
+result list.  If the final element is not a list, the result is a
+``dotted list'' since its final @sc{cdr} is not @code{nil} as required
+in a true list.
+
+See @code{nconc} in @ref{Rearrangement}, for a way to join lists with no
+copying.
+
+Here is an example of using @code{append}:
+
+@example
+@group
+(setq trees '(pine oak))
+     @result{} (pine oak)
+(setq more-trees (append '(maple birch) trees))
+     @result{} (maple birch pine oak)
+@end group
+
+@group
+trees
+     @result{} (pine oak)
+more-trees
+     @result{} (maple birch pine oak)
+@end group
+@group
+(eq trees (cdr (cdr more-trees)))
+     @result{} t
+@end group
+@end example
+
+You can see how @code{append} works by looking at a box diagram.  The
+variable @code{trees} is set to the list @code{(pine oak)} and then the
+variable @code{more-trees} is set to the list @code{(maple birch pine
+oak)}.  However, the variable @code{trees} continues to refer to the
+original list:
+
+@smallexample
+@group
+more-trees                trees
+|                           |
+|     ___ ___      ___ ___   -> ___ ___      ___ ___
+ --> |___|___|--> |___|___|--> |___|___|--> |___|___|--> nil
+       |            |            |            |
+       |            |            |            |
+        --> maple    -->birch     --> pine     --> oak
+@end group
+@end smallexample
+
+An empty sequence contributes nothing to the value returned by
+@code{append}.  As a consequence of this, a final @code{nil} argument
+forces a copy of the previous argument.
+
+@example
+@group
+trees
+     @result{} (pine oak)
+@end group
+@group
+(setq wood (append trees ()))
+     @result{} (pine oak)
+@end group
+@group
+wood
+     @result{} (pine oak)
+@end group
+@group
+(eq wood trees)
+     @result{} nil
+@end group
+@end example
+
+@noindent
+This once was the usual way to copy a list, before the function
+@code{copy-sequence} was invented.  @xref{Sequences Arrays Vectors}.
+
+With the help of @code{apply}, we can append all the lists in a list of
+lists:
+
+@example
+@group
+(apply 'append '((a b c) nil (x y z) nil))
+     @result{} (a b c x y z)
+@end group
+@end example
+
+If no @var{sequences} are given, @code{nil} is returned:
+
+@example
+@group
+(append)
+     @result{} nil
+@end group
+@end example
+
+Here are some examples where the final argument is not a list:
+
+@example
+(append '(x y) 'z)
+     @result{} (x y . z)
+(append '(x y) [z])
+     @result{} (x y . [z])
+@end example
+
+@noindent
+The second example shows that when the final argument is a sequence but
+not a list, the sequence's elements do not become elements of the
+resulting list.  Instead, the sequence becomes the final @sc{cdr}, like
+any other non-list final argument.
+
+The @code{append} function also allows integers as arguments.  It
+converts them to strings of digits, making up the decimal print
+representation of the integer, and then uses the strings instead of the
+original integers.  @strong{Don't use this feature; we plan to eliminate
+it.  If you already use this feature, change your programs now!}  The
+proper way to convert an integer to a decimal number in this way is with
+@code{format} (@pxref{Formatting Strings}) or @code{number-to-string}
+(@pxref{String Conversion}).
+@end defun
+
+@defun reverse list
+This function creates a new list whose elements are the elements of
+@var{list}, but in reverse order.  The original argument @var{list} is
+@emph{not} altered.
+
+@example
+@group
+(setq x '(1 2 3 4))
+     @result{} (1 2 3 4)
+@end group
+@group
+(reverse x)
+     @result{} (4 3 2 1)
+x
+     @result{} (1 2 3 4)
+@end group
+@end example
+@end defun
+
+@node Modifying Lists
+@section Modifying Existing List Structure
+
+  You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
+primitives @code{setcar} and @code{setcdr}.
+
+@cindex CL note---@code{rplaca} vrs @code{setcar}
+@quotation
+@findex rplaca
+@findex rplacd
+@b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
+@code{rplacd} to alter list structure; they change structure the same
+way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
+return the cons cell while @code{setcar} and @code{setcdr} return the
+new @sc{car} or @sc{cdr}.
+@end quotation
+
+@menu
+* Setcar::          Replacing an element in a list.
+* Setcdr::          Replacing part of the list backbone.
+                      This can be used to remove or add elements.
+* Rearrangement::   Reordering the elements in a list; combining lists.
+@end menu
+
+@node Setcar
+@subsection Altering List Elements with @code{setcar}
+
+  Changing the @sc{car} of a cons cell is done with @code{setcar}.  When
+used on a list, @code{setcar} replaces one element of a list with a
+different element.
+
+@defun setcar cons object
+This function stores @var{object} as the new @sc{car} of @var{cons},
+replacing its previous @sc{car}.  It returns the value @var{object}.
+For example:
+
+@example
+@group
+(setq x '(1 2))
+     @result{} (1 2)
+@end group
+@group
+(setcar x 4)
+     @result{} 4
+@end group
+@group
+x
+     @result{} (4 2)
+@end group
+@end example
+@end defun
+
+  When a cons cell is part of the shared structure of several lists,
+storing a new @sc{car} into the cons changes one element of each of
+these lists.  Here is an example:
+
+@example
+@group
+;; @r{Create two lists that are partly shared.}
+(setq x1 '(a b c))
+     @result{} (a b c)
+(setq x2 (cons 'z (cdr x1)))
+     @result{} (z b c)
+@end group
+
+@group
+;; @r{Replace the @sc{car} of a shared link.}
+(setcar (cdr x1) 'foo)
+     @result{} foo
+x1                           ; @r{Both lists are changed.}
+     @result{} (a foo c)
+x2
+     @result{} (z foo c)
+@end group
+
+@group
+;; @r{Replace the @sc{car} of a link that is not shared.}
+(setcar x1 'baz)
+     @result{} baz
+x1                           ; @r{Only one list is changed.}
+     @result{} (baz foo c)
+x2
+     @result{} (z foo c)
+@end group
+@end example
+
+  Here is a graphical depiction of the shared structure of the two lists
+in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
+changes them both:
+
+@example
+@group
+        ___ ___        ___ ___      ___ ___
+x1---> |___|___|----> |___|___|--> |___|___|--> nil
+         |        -->   |            |
+         |       |      |            |
+          --> a  |       --> b        --> c
+                 |
+       ___ ___   |
+x2--> |___|___|--
+        |
+        |
+         --> z
+@end group
+@end example
+
+  Here is an alternative form of box diagram, showing the same relationship:
+
+@example
+@group
+x1:
+ --------------       --------------       --------------
+| car   | cdr  |     | car   | cdr  |     | car   | cdr  |
+|   a   |   o------->|   b   |   o------->|   c   |  nil |
+|       |      |  -->|       |      |     |       |      |
+ --------------  |    --------------       --------------
+                 |
+x2:              |
+ --------------  |
+| car   | cdr  | |
+|   z   |   o----
+|       |      |
+ --------------
+@end group
+@end example
+
+@node Setcdr
+@subsection Altering the CDR of a List
+
+  The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
+
+@defun setcdr cons object
+This function stores @var{object} as the new @sc{cdr} of @var{cons},
+replacing its previous @sc{cdr}.  It returns the value @var{object}.
+@end defun
+
+  Here is an example of replacing the @sc{cdr} of a list with a
+different list.  All but the first element of the list are removed in
+favor of a different sequence of elements.  The first element is
+unchanged, because it resides in the @sc{car} of the list, and is not
+reached via the @sc{cdr}.
+
+@example
+@group
+(setq x '(1 2 3))
+     @result{} (1 2 3)
+@end group
+@group
+(setcdr x '(4))
+     @result{} (4)
+@end group
+@group
+x
+     @result{} (1 4)
+@end group
+@end example
+
+  You can delete elements from the middle of a list by altering the
+@sc{cdr}s of the cons cells in the list.  For example, here we delete
+the second element, @code{b}, from the list @code{(a b c)}, by changing
+the @sc{cdr} of the first cell:
+
+@example
+@group
+(setq x1 '(a b c))
+     @result{} (a b c)
+(setcdr x1 (cdr (cdr x1)))
+     @result{} (c)
+x1
+     @result{} (a c)
+@end group
+@end example
+
+@need 4000
+  Here is the result in box notation:
+
+@example
+@group
+                   --------------------
+                  |                    |
+ --------------   |   --------------   |    --------------
+| car   | cdr  |  |  | car   | cdr  |   -->| car   | cdr  |
+|   a   |   o-----   |   b   |   o-------->|   c   |  nil |
+|       |      |     |       |      |      |       |      |
+ --------------       --------------        --------------
+@end group
+@end example
+
+@noindent
+The second cons cell, which previously held the element @code{b}, still
+exists and its @sc{car} is still @code{b}, but it no longer forms part
+of this list.
+
+  It is equally easy to insert a new element by changing @sc{cdr}s:
+
+@example
+@group
+(setq x1 '(a b c))
+     @result{} (a b c)
+(setcdr x1 (cons 'd (cdr x1)))
+     @result{} (d b c)
+x1
+     @result{} (a d b c)
+@end group
+@end example
+
+  Here is this result in box notation:
+
+@smallexample
+@group
+ --------------        -------------       -------------
+| car  | cdr   |      | car  | cdr  |     | car  | cdr  |
+|   a  |   o   |   -->|   b  |   o------->|   c  |  nil |
+|      |   |   |  |   |      |      |     |      |      |
+ --------- | --   |    -------------       -------------
+           |      |
+     -----         --------
+    |                      |
+    |    ---------------   |
+    |   | car   | cdr   |  |
+     -->|   d   |   o------
+        |       |       |
+         ---------------
+@end group
+@end smallexample
+
+@node Rearrangement
+@subsection Functions that Rearrange Lists
+@cindex rearrangement of lists
+@cindex modification of lists
+
+  Here are some functions that rearrange lists ``destructively'' by
+modifying the @sc{cdr}s of their component cons cells.  We call these
+functions ``destructive'' because they chew up the original lists passed
+to them as arguments, to produce a new list that is the returned value.
+
+@ifinfo
+  See @code{delq}, in @ref{Sets And Lists}, for another function
+that modifies cons cells.
+@end ifinfo
+@iftex
+   The function @code{delq} in the following section is another example
+of destructive list manipulation.
+@end iftex
+
+@defun nconc &rest lists
+@cindex concatenating lists
+@cindex joining lists
+This function returns a list containing all the elements of @var{lists}.
+Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
+@emph{not} copied.  Instead, the last @sc{cdr} of each of the
+@var{lists} is changed to refer to the following list.  The last of the
+@var{lists} is not altered.  For example:
+
+@example
+@group
+(setq x '(1 2 3))
+     @result{} (1 2 3)
+@end group
+@group
+(nconc x '(4 5))
+     @result{} (1 2 3 4 5)
+@end group
+@group
+x
+     @result{} (1 2 3 4 5)
+@end group
+@end example
+
+   Since the last argument of @code{nconc} is not itself modified, it is
+reasonable to use a constant list, such as @code{'(4 5)}, as in the
+above example.  For the same reason, the last argument need not be a
+list:
+
+@example
+@group
+(setq x '(1 2 3))
+     @result{} (1 2 3)
+@end group
+@group
+(nconc x 'z)
+     @result{} (1 2 3 . z)
+@end group
+@group
+x
+     @result{} (1 2 3 . z)
+@end group
+@end example
+
+A common pitfall is to use a quoted constant list as a non-last
+argument to @code{nconc}.  If you do this, your program will change
+each time you run it!  Here is what happens:
+
+@smallexample
+@group
+(defun add-foo (x)            ; @r{We want this function to add}
+  (nconc '(foo) x))           ;   @r{@code{foo} to the front of its arg.}
+@end group
+
+@group
+(symbol-function 'add-foo)
+     @result{} (lambda (x) (nconc (quote (foo)) x))
+@end group
+
+@group
+(setq xx (add-foo '(1 2)))    ; @r{It seems to work.}
+     @result{} (foo 1 2)
+@end group
+@group
+(setq xy (add-foo '(3 4)))    ; @r{What happened?}
+     @result{} (foo 1 2 3 4)
+@end group
+@group
+(eq xx xy)
+     @result{} t
+@end group
+
+@group
+(symbol-function 'add-foo)
+     @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
+@end group
+@end smallexample
+@end defun
+
+@defun nreverse list
+@cindex reversing a list
+  This function reverses the order of the elements of @var{list}.
+Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
+the @sc{cdr}s in the cons cells forming the list.  The cons cell that
+used to be the last one in @var{list} becomes the first cell of the
+value.
+
+  For example:
+
+@example
+@group
+(setq x '(1 2 3 4))
+     @result{} (1 2 3 4)
+@end group
+@group
+x
+     @result{} (1 2 3 4)
+(nreverse x)
+     @result{} (4 3 2 1)
+@end group
+@group
+;; @r{The cell that was first is now last.}
+x
+     @result{} (1)
+@end group
+@end example
+
+  To avoid confusion, we usually store the result of @code{nreverse}
+back in the same variable which held the original list:
+
+@example
+(setq x (nreverse x))
+@end example
+
+  Here is the @code{nreverse} of our favorite example, @code{(a b c)},
+presented graphically:
+
+@smallexample
+@group
+@r{Original list head:}                       @r{Reversed list:}
+ -------------        -------------        ------------
+| car  | cdr  |      | car  | cdr  |      | car | cdr  |
+|   a  |  nil |<--   |   b  |   o  |<--   |   c |   o  |
+|      |      |   |  |      |   |  |   |  |     |   |  |
+ -------------    |   --------- | -    |   -------- | -
+                  |             |      |            |
+                   -------------        ------------
+@end group
+@end smallexample
+@end defun
+
+@defun sort list predicate
+@cindex stable sort
+@cindex sorting lists
+This function sorts @var{list} stably, though destructively, and
+returns the sorted list.  It compares elements using @var{predicate}.  A
+stable sort is one in which elements with equal sort keys maintain their
+relative order before and after the sort.  Stability is important when
+successive sorts are used to order elements according to different
+criteria.
+
+The argument @var{predicate} must be a function that accepts two
+arguments.  It is called with two elements of @var{list}.  To get an
+increasing order sort, the @var{predicate} should return @code{t} if the
+first element is ``less than'' the second, or @code{nil} if not.
+
+The destructive aspect of @code{sort} is that it rearranges the cons
+cells forming @var{list} by changing @sc{cdr}s.  A nondestructive sort
+function would create new cons cells to store the elements in their
+sorted order.  If you wish to make a sorted copy without destroying the
+original, copy it first with @code{copy-sequence} and then sort.
+
+Sorting does not change the @sc{car}s of the cons cells in @var{list};
+the cons cell that originally contained the element @code{a} in
+@var{list} still has @code{a} in its @sc{car} after sorting, but it now
+appears in a different position in the list due to the change of
+@sc{cdr}s.  For example:
+
+@example
+@group
+(setq nums '(1 3 2 6 5 4 0))
+     @result{} (1 3 2 6 5 4 0)
+@end group
+@group
+(sort nums '<)
+     @result{} (0 1 2 3 4 5 6)
+@end group
+@group
+nums
+     @result{} (1 2 3 4 5 6)
+@end group
+@end example
+
+@noindent
+Note that the list in @code{nums} no longer contains 0; this is the same
+cons cell that it was before, but it is no longer the first one in the
+list.  Don't assume a variable that formerly held the argument now holds
+the entire sorted list!  Instead, save the result of @code{sort} and use
+that.  Most often we store the result back into the variable that held
+the original list:
+
+@example
+(setq nums (sort nums '<))
+@end example
+
+@xref{Sorting}, for more functions that perform sorting.
+See @code{documentation} in @ref{Accessing Documentation}, for a
+useful example of @code{sort}.
+@end defun
+
+@node Sets And Lists
+@section Using Lists as Sets
+@cindex lists as sets
+@cindex sets
+
+  A list can represent an unordered mathematical set---simply consider a
+value an element of a set if it appears in the list, and ignore the
+order of the list.  To form the union of two sets, use @code{append} (as
+long as you don't mind having duplicate elements).  Other useful
+functions for sets include @code{memq} and @code{delq}, and their
+@code{equal} versions, @code{member} and @code{delete}.
+
+@cindex CL note---lack @code{union}, @code{set}
+@quotation
+@b{Common Lisp note:} Common Lisp has functions @code{union} (which
+avoids duplicate elements) and @code{intersection} for set operations,
+but XEmacs Lisp does not have them.  You can write them in Lisp if
+you wish.
+@end quotation
+
+@defun memq object list
+@cindex membership in a list
+This function tests to see whether @var{object} is a member of
+@var{list}.  If it is, @code{memq} returns a list starting with the
+first occurrence of @var{object}.  Otherwise, it returns @code{nil}.
+The letter @samp{q} in @code{memq} says that it uses @code{eq} to
+compare @var{object} against the elements of the list.  For example:
+
+@example
+@group
+(memq 'b '(a b c b a))
+     @result{} (b c b a)
+@end group
+@group
+(memq '(2) '((1) (2)))    ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
+     @result{} nil
+@end group
+@end example
+@end defun
+
+@defun delq object list
+@cindex deletion of elements
+This function destructively removes all elements @code{eq} to
+@var{object} from @var{list}.  The letter @samp{q} in @code{delq} says
+that it uses @code{eq} to compare @var{object} against the elements of
+the list, like @code{memq}.
+@end defun
+
+When @code{delq} deletes elements from the front of the list, it does so
+simply by advancing down the list and returning a sublist that starts
+after those elements:
+
+@example
+@group
+(delq 'a '(a b c)) @equiv{} (cdr '(a b c))
+@end group
+@end example
+
+When an element to be deleted appears in the middle of the list,
+removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
+
+@example
+@group
+(setq sample-list '(a b c (4)))
+     @result{} (a b c (4))
+@end group
+@group
+(delq 'a sample-list)
+     @result{} (b c (4))
+@end group
+@group
+sample-list
+     @result{} (a b c (4))
+@end group
+@group
+(delq 'c sample-list)
+     @result{} (a b (4))
+@end group
+@group
+sample-list
+     @result{} (a b (4))
+@end group
+@end example
+
+Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
+splice out the third element, but @code{(delq 'a sample-list)} does not
+splice anything---it just returns a shorter list.  Don't assume that a
+variable which formerly held the argument @var{list} now has fewer
+elements, or that it still holds the original list!  Instead, save the
+result of @code{delq} and use that.  Most often we store the result back
+into the variable that held the original list:
+
+@example
+(setq flowers (delq 'rose flowers))
+@end example
+
+In the following example, the @code{(4)} that @code{delq} attempts to match
+and the @code{(4)} in the @code{sample-list} are not @code{eq}:
+
+@example
+@group
+(delq '(4) sample-list)
+     @result{} (a c (4))
+@end group
+@end example
+
+The following two functions are like @code{memq} and @code{delq} but use
+@code{equal} rather than @code{eq} to compare elements.  They are new in
+Emacs 19.
+
+@defun member object list
+The function @code{member} tests to see whether @var{object} is a member
+of @var{list}, comparing members with @var{object} using @code{equal}.
+If @var{object} is a member, @code{member} returns a list starting with
+its first occurrence in @var{list}.  Otherwise, it returns @code{nil}.
+
+Compare this with @code{memq}:
+
+@example
+@group
+(member '(2) '((1) (2)))  ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
+     @result{} ((2))
+@end group
+@group
+(memq '(2) '((1) (2)))    ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
+     @result{} nil
+@end group
+@group
+;; @r{Two strings with the same contents are @code{equal}.}
+(member "foo" '("foo" "bar"))
+     @result{} ("foo" "bar")
+@end group
+@end example
+@end defun
+
+@defun delete object list
+This function destructively removes all elements @code{equal} to
+@var{object} from @var{list}.  It is to @code{delq} as @code{member} is
+to @code{memq}: it uses @code{equal} to compare elements with
+@var{object}, like @code{member}; when it finds an element that matches,
+it removes the element just as @code{delq} would.  For example:
+
+@example
+@group
+(delete '(2) '((2) (1) (2)))
+     @result{} '((1))
+@end group
+@end example
+@end defun
+
+@quotation
+@b{Common Lisp note:} The functions @code{member} and @code{delete} in
+XEmacs Lisp are derived from Maclisp, not Common Lisp.  The Common
+Lisp versions do not use @code{equal} to compare elements.
+@end quotation
+
+  See also the function @code{add-to-list}, in @ref{Setting Variables},
+for another way to add an element to a list stored in a variable.
+
+@node Association Lists
+@section Association Lists
+@cindex association list
+@cindex alist
+
+  An @dfn{association list}, or @dfn{alist} for short, records a mapping
+from keys to values.  It is a list of cons cells called
+@dfn{associations}: the @sc{car} of each cell is the @dfn{key}, and the
+@sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
+is not related to the term ``key sequence''; it means a value used to
+look up an item in a table.  In this case, the table is the alist, and
+the alist associations are the items.}
+
+  Here is an example of an alist.  The key @code{pine} is associated with
+the value @code{cones}; the key @code{oak} is associated with
+@code{acorns}; and the key @code{maple} is associated with @code{seeds}.
+
+@example
+@group
+'((pine . cones)
+  (oak . acorns)
+  (maple . seeds))
+@end group
+@end example
+
+  The associated values in an alist may be any Lisp objects; so may the
+keys.  For example, in the following alist, the symbol @code{a} is
+associated with the number @code{1}, and the string @code{"b"} is
+associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
+the alist element:
+
+@example
+((a . 1) ("b" 2 3))
+@end example
+
+  Sometimes it is better to design an alist to store the associated
+value in the @sc{car} of the @sc{cdr} of the element.  Here is an
+example:
+
+@example
+'((rose red) (lily white) (buttercup yellow))
+@end example
+
+@noindent
+Here we regard @code{red} as the value associated with @code{rose}.  One
+advantage of this method is that you can store other related
+information---even a list of other items---in the @sc{cdr} of the
+@sc{cdr}.  One disadvantage is that you cannot use @code{rassq} (see
+below) to find the element containing a given value.  When neither of
+these considerations is important, the choice is a matter of taste, as
+long as you are consistent about it for any given alist.
+
+  Note that the same alist shown above could be regarded as having the
+associated value in the @sc{cdr} of the element; the value associated
+with @code{rose} would be the list @code{(red)}.
+
+  Association lists are often used to record information that you might
+otherwise keep on a stack, since new associations may be added easily to
+the front of the list.  When searching an association list for an
+association with a given key, the first one found is returned, if there
+is more than one.
+
+  In XEmacs Lisp, it is @emph{not} an error if an element of an
+association list is not a cons cell.  The alist search functions simply
+ignore such elements.  Many other versions of Lisp signal errors in such
+cases.
+
+  Note that property lists are similar to association lists in several
+respects.  A property list behaves like an association list in which
+each key can occur only once.  @xref{Property Lists}, for a comparison
+of property lists and association lists.
+
+@defun assoc key alist
+This function returns the first association for @var{key} in
+@var{alist}.  It compares @var{key} against the alist elements using
+@code{equal} (@pxref{Equality Predicates}).  It returns @code{nil} if no
+association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
+For example:
+
+@smallexample
+(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
+     @result{} ((pine . cones) (oak . acorns) (maple . seeds))
+(assoc 'oak trees)
+     @result{} (oak . acorns)
+(cdr (assoc 'oak trees))
+     @result{} acorns
+(assoc 'birch trees)
+     @result{} nil
+@end smallexample
+
+Here is another example, in which the keys and values are not symbols:
+
+@smallexample
+(setq needles-per-cluster
+      '((2 "Austrian Pine" "Red Pine")
+        (3 "Pitch Pine")
+        (5 "White Pine")))
+
+(cdr (assoc 3 needles-per-cluster))
+     @result{} ("Pitch Pine")
+(cdr (assoc 2 needles-per-cluster))
+     @result{} ("Austrian Pine" "Red Pine")
+@end smallexample
+@end defun
+
+@defun rassoc value alist
+This function returns the first association with value @var{value} in
+@var{alist}.  It returns @code{nil} if no association in @var{alist} has
+a @sc{cdr} @code{equal} to @var{value}.
+
+@code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
+each @var{alist} association instead of the @sc{car}.  You can think of
+this as ``reverse @code{assoc}'', finding the key for a given value.
+@end defun
+
+@defun assq key alist
+This function is like @code{assoc} in that it returns the first
+association for @var{key} in @var{alist}, but it makes the comparison
+using @code{eq} instead of @code{equal}.  @code{assq} returns @code{nil}
+if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
+This function is used more often than @code{assoc}, since @code{eq} is
+faster than @code{equal} and most alists use symbols as keys.
+@xref{Equality Predicates}.
+
+@smallexample
+(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
+     @result{} ((pine . cones) (oak . acorns) (maple . seeds))
+(assq 'pine trees)
+     @result{} (pine . cones)
+@end smallexample
+
+On the other hand, @code{assq} is not usually useful in alists where the
+keys may not be symbols:
+
+@smallexample
+(setq leaves
+      '(("simple leaves" . oak)
+        ("compound leaves" . horsechestnut)))
+
+(assq "simple leaves" leaves)
+     @result{} nil
+(assoc "simple leaves" leaves)
+     @result{} ("simple leaves" . oak)
+@end smallexample
+@end defun
+
+@defun rassq value alist
+This function returns the first association with value @var{value} in
+@var{alist}.  It returns @code{nil} if no association in @var{alist} has
+a @sc{cdr} @code{eq} to @var{value}.
+
+@code{rassq} is like @code{assq} except that it compares the @sc{cdr} of
+each @var{alist} association instead of the @sc{car}.  You can think of
+this as ``reverse @code{assq}'', finding the key for a given value.
+
+For example:
+
+@smallexample
+(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
+
+(rassq 'acorns trees)
+     @result{} (oak . acorns)
+(rassq 'spores trees)
+     @result{} nil
+@end smallexample
+
+Note that @code{rassq} cannot search for a value stored in the @sc{car}
+of the @sc{cdr} of an element:
+
+@smallexample
+(setq colors '((rose red) (lily white) (buttercup yellow)))
+
+(rassq 'white colors)
+     @result{} nil
+@end smallexample
+
+In this case, the @sc{cdr} of the association @code{(lily white)} is not
+the symbol @code{white}, but rather the list @code{(white)}.  This
+becomes clearer if the association is written in dotted pair notation:
+
+@smallexample
+(lily white) @equiv{} (lily . (white))
+@end smallexample
+@end defun
+
+@defun remassoc key alist
+This function deletes by side effect any associations with key @var{key}
+in @var{alist} -- i.e. it removes any elements from @var{alist} whose
+@code{car} is @code{equal} to @var{key}.  The modified @var{alist} is
+returned.
+
+If the first member of @var{alist} has a @code{car} that is @code{equal}
+to @var{key}, there is no way to remove it by side effect; therefore,
+write @code{(setq foo (remassoc key foo))} to be sure of changing the
+value of @code{foo}.
+@end defun
+
+@defun remassq key alist
+This function deletes by side effect any associations with key @var{key}
+in @var{alist} -- i.e. it removes any elements from @var{alist} whose
+@code{car} is @code{eq} to @var{key}.  The modified @var{alist} is
+returned.
+
+This function is exactly like @code{remassoc}, but comparisons between
+@var{key} and keys in @var{alist} are done using @code{eq} instead of
+@code{equal}.
+@end defun
+
+@defun remrassoc value alist
+This function deletes by side effect any associations with value @var{value}
+in @var{alist} -- i.e. it removes any elements from @var{alist} whose
+@code{cdr} is @code{equal} to @var{value}.  The modified @var{alist} is
+returned.
+
+If the first member of @var{alist} has a @code{car} that is @code{equal}
+to @var{value}, there is no way to remove it by side effect; therefore,
+write @code{(setq foo (remassoc value foo))} to be sure of changing the
+value of @code{foo}.
+
+@code{remrassoc} is like @code{remassoc} except that it compares the
+@sc{cdr} of each @var{alist} association instead of the @sc{car}.  You
+can think of this as ``reverse @code{remassoc}'', removing an association
+based on its value instead of its key.
+@end defun
+
+@defun remrassq value alist
+This function deletes by side effect any associations with value @var{value}
+in @var{alist} -- i.e. it removes any elements from @var{alist} whose
+@code{cdr} is @code{eq} to @var{value}.  The modified @var{alist} is
+returned.
+
+This function is exactly like @code{remrassoc}, but comparisons between
+@var{value} and values in @var{alist} are done using @code{eq} instead of
+@code{equal}.
+@end defun
+
+@defun copy-alist alist
+@cindex copying alists
+This function returns a two-level deep copy of @var{alist}: it creates a
+new copy of each association, so that you can alter the associations of
+the new alist without changing the old one.
+
+@smallexample
+@group
+(setq needles-per-cluster
+      '((2 . ("Austrian Pine" "Red Pine"))
+        (3 . ("Pitch Pine"))
+@end group
+        (5 . ("White Pine"))))
+@result{}
+((2 "Austrian Pine" "Red Pine")
+ (3 "Pitch Pine")
+ (5 "White Pine"))
+
+(setq copy (copy-alist needles-per-cluster))
+@result{}
+((2 "Austrian Pine" "Red Pine")
+ (3 "Pitch Pine")
+ (5 "White Pine"))
+
+(eq needles-per-cluster copy)
+     @result{} nil
+(equal needles-per-cluster copy)
+     @result{} t
+(eq (car needles-per-cluster) (car copy))
+     @result{} nil
+(cdr (car (cdr needles-per-cluster)))
+     @result{} ("Pitch Pine")
+@group
+(eq (cdr (car (cdr needles-per-cluster)))
+    (cdr (car (cdr copy))))
+     @result{} t
+@end group
+@end smallexample
+
+  This example shows how @code{copy-alist} makes it possible to change
+the associations of one copy without affecting the other:
+
+@smallexample
+@group
+(setcdr (assq 3 copy) '("Martian Vacuum Pine"))
+(cdr (assq 3 needles-per-cluster))
+     @result{} ("Pitch Pine")
+@end group
+@end smallexample
+@end defun
+
+@node Property Lists
+@section Property Lists
+@cindex property list
+@cindex plist
+
+A @dfn{property list} (or @dfn{plist}) is another way of representing a
+mapping from keys to values.  Instead of the list consisting of conses
+of a key and a value, the keys and values alternate as successive
+entries in the list.  Thus, the association list
+
+@example
+((a . 1) (b . 2) (c . 3))
+@end example
+
+has the equivalent property list form
+
+@example
+(a 1 b 2 c 3)
+@end example
+
+Property lists are used to represent the properties associated with
+various sorts of objects, such as symbols, strings, frames, etc.
+The convention is that property lists can be modified in-place,
+while association lists generally are not.
+
+Plists come in two varieties: @dfn{normal} plists, whose keys are
+compared with @code{eq}, and @dfn{lax} plists, whose keys are compared
+with @code{equal},
+
+@defun valid-plist-p plist
+Given a plist, this function returns non-@code{nil} if its format is
+correct.  If it returns @code{nil}, @code{check-valid-plist} will signal
+an error when given the plist; that means it's a malformed or circular
+plist or has non-symbols as keywords.
+@end defun
+
+@defun check-valid-plist plist
+Given a plist, this function signals an error if there is anything wrong
+with it.  This means that it's a malformed or circular plist.
+@end defun
+
+@menu
+* Working With Normal Plists::       Functions for normal plists.
+* Working With Lax Plists::          Functions for lax plists.
+* Converting Plists To/From Alists:: Alist to plist and vice-versa.
+@end menu
+
+@node Working With Normal Plists
+@subsection Working With Normal Plists
+
+@defun plist-get plist prop &optional default
+This function extracts a value from a property list.  The function
+returns the value corresponding to the given @var{prop}, or
+@var{default} if @var{prop} is not one of the properties on the list.
+@end defun
+
+@defun plist-put plist prop val
+This function changes the value in @var{plist} of @var{prop} to
+@var{val}.  If @var{prop} is already a property on the list, its value is
+set to @var{val}, otherwise the new @var{prop} @var{val} pair is added.
+The new plist is returned; use @code{(setq x (plist-put x prop val))} to
+be sure to use the new value.  The @var{plist} is modified by side
+effects.
+@end defun
+
+@defun plist-remprop plist prop
+This function removes from @var{plist} the property @var{prop} and its
+value.  The new plist is returned; use @code{(setq x (plist-remprop x
+prop val))} to be sure to use the new value.  The @var{plist} is
+modified by side effects.
+@end defun
+
+@defun plist-member plist prop
+This function returns @code{t} if @var{prop} has a value specified in
+@var{plist}.
+@end defun
+
+In the following functions, if optional arg @var{nil-means-not-present}
+is non-@code{nil}, then a property with a @code{nil} value is ignored or
+removed.  This feature is a virus that has infected old Lisp
+implementations (and thus E-Lisp, due to @sc{RMS}'s enamorment with old
+Lisps), but should not be used except for backward compatibility.
+
+@defun plists-eq a b &optional nil-means-not-present
+This function returns non-@code{nil} if property lists A and B are
+@code{eq} (i.e. their values are @code{eq}).
+@end defun
+
+@defun plists-equal a b &optional nil-means-not-present
+This function returns non-@code{nil} if property lists A and B are
+@code{equal} (i.e. their values are @code{equal}; their keys are
+still compared using @code{eq}).
+@end defun
+
+@defun canonicalize-plist plist &optional nil-means-not-present
+This function destructively removes any duplicate entries from a plist.
+In such cases, the first entry applies.
+
+The new plist is returned.  If @var{nil-means-not-present} is given, the
+return value may not be @code{eq} to the passed-in value, so make sure
+to @code{setq} the value back into where it came from.
+@end defun
+
+@node Working With Lax Plists
+@subsection Working With Lax Plists
+
+Recall that a @dfn{lax plist} is a property list whose keys are compared
+using @code{equal} instead of @code{eq}.
+
+@defun lax-plist-get lax-plist prop &optional default
+This function extracts a value from a lax property list.  The function
+returns the value corresponding to the given @var{prop}, or
+@var{default} if @var{prop} is not one of the properties on the list.
+@end defun
+
+@defun lax-plist-put lax-plist prop val
+This function changes the value in @var{lax-plist} of @var{prop} to @var{val}.
+@end defun
+
+@defun lax-plist-remprop lax-plist prop
+This function removes from @var{lax-plist} the property @var{prop} and
+its value.  The new plist is returned; use @code{(setq x
+(lax-plist-remprop x prop val))} to be sure to use the new value.  The
+@var{lax-plist} is modified by side effects.
+@end defun
+
+@defun lax-plist-member lax-plist prop
+This function returns @code{t} if @var{prop} has a value specified in
+@var{lax-plist}.
+@end defun
+
+In the following functions, if optional arg @var{nil-means-not-present}
+is non-@code{nil}, then a property with a @code{nil} value is ignored or
+removed.  This feature is a virus that has infected old Lisp
+implementations (and thus E-Lisp, due to @sc{RMS}'s enamorment with old
+Lisps), but should not be used except for backward compatibility.
+
+@defun lax-plists-eq a b &optional nil-means-not-present
+This function returns non-@code{nil} if lax property lists A and B are
+@code{eq} (i.e. their values are @code{eq}; their keys are still
+compared using @code{equal}).
+@end defun
+
+@defun lax-plists-equal a b &optional nil-means-not-present
+This function returns non-@code{nil} if lax property lists A and B are
+@code{equal} (i.e. their values are @code{equal}).
+@end defun
+
+@defun canonicalize-lax-plist lax-plist &optional nil-means-not-present
+This function destructively removes any duplicate entries from a lax
+plist.  In such cases, the first entry applies.
+
+The new plist is returned.  If @var{nil-means-not-present} is given, the
+return value may not be @code{eq} to the passed-in value, so make sure
+to @code{setq} the value back into where it came from.
+@end defun
+
+@node Converting Plists To/From Alists
+@subsection Converting Plists To/From Alists
+
+@defun alist-to-plist alist
+This function converts association list @var{alist} into the equivalent
+property-list form.  The plist is returned.  This converts from
+
+@example
+((a . 1) (b . 2) (c . 3))
+@end example
+
+into
+
+@example
+(a 1 b 2 c 3)
+@end example
+
+The original alist is not modified.
+@end defun
+
+@defun plist-to-alist plist
+This function converts property list @var{plist} into the equivalent
+association-list form.  The alist is returned.  This converts from
+
+@example
+(a 1 b 2 c 3)
+@end example
+
+into
+
+@example
+((a . 1) (b . 2) (c . 3))
+@end example
+
+The original plist is not modified.
+@end defun
+
+The following two functions are equivalent to the preceding two except
+that they destructively modify their arguments, using cons cells from
+the original list to form the new list rather than allocating new
+cons cells.
+
+@defun destructive-alist-to-plist alist
+This function destructively converts association list @var{alist} into
+the equivalent property-list form.  The plist is returned.
+@end defun
+
+@defun destructive-plist-to-alist plist
+This function destructively converts property list @var{plist} into the
+equivalent association-list form.  The alist is returned.
+@end defun
+
+@node Weak Lists
+@section Weak Lists
+@cindex weak list
+
+A @dfn{weak list} is a special sort of list whose members are not counted
+as references for the purpose of garbage collection.  This means that,
+for any object in the list, if there are no references to the object
+anywhere outside of the list (or other weak list or weak hash table),
+that object will disappear the next time a garbage collection happens.
+Weak lists can be useful for keeping track of things such as unobtrusive
+lists of another function's buffers or markers.  When that function is
+done with the elements, they will automatically disappear from the list.
+
+Weak lists are used internally, for example, to manage the list holding
+the children of an extent -- an extent that is unused but has a parent
+will still be reclaimed, and will automatically be removed from its
+parent's list of children.
+
+Weak lists are similar to weak hash tables (@pxref{Weak Hash Tables}).
+
+@defun weak-list-p object
+This function returns non-@code{nil} if @var{object} is a weak list.
+@end defun
+
+Weak lists come in one of four types:
+
+@table @code
+@item simple
+Objects in the list disappear if not referenced outside of the list.
+
+@item assoc
+Objects in the list disappear if they are conses and either the car or
+the cdr of the cons is not referenced outside of the list.
+
+@item key-assoc
+Objects in the list disappear if they are conses and the car is not
+referenced outside of the list.
+
+@item value-assoc
+Objects in the list disappear if they are conses and the cdr is not
+referenced outside of the list.
+@end table
+
+@defun make-weak-list &optional type
+This function creates a new weak list of type @var{type}.  @var{type} is
+a symbol (one of @code{simple}, @code{assoc}, @code{key-assoc}, or
+@code{value-assoc}, as described above) and defaults to @code{simple}.
+@end defun
+
+@defun weak-list-type weak
+This function returns the type of the given weak-list object.
+@end defun
+
+@defun weak-list-list weak
+This function returns the list contained in a weak-list object.
+@end defun
+
+@defun set-weak-list-list weak new-list
+This function changes the list contained in a weak-list object.
+@end defun