X-Git-Url: https://git.distorted.org.uk/~mdw/sod/blobdiff_plain/984c3fc3a94a81c2e6752031ed6a8b9a6c948658..7d8d3a165fa725b686d1c89b78179a4d5705d11a:/doc/misc.tex?ds=inline

diff --git a/doc/misc.tex b/doc/misc.tex
index abc15eb..859ec51 100644
--- a/doc/misc.tex
+++ b/doc/misc.tex
@@ -30,77 +30,263 @@
 
 These symbols are defined in the @|sod-utilities| package.
 
+
+\subsection{Macro utilities}
+
+We begin with some simple utilities which help with writing macros.  Several
+of these are standard.
+
 \begin{describe}{mac}
-    {with-gensyms (@{ @<var> @! (@<var> @[@<name>@]) @}^*) \\ \ind
-      @<declaration>^* \\
-      @<form>^*}
+    {with-gensyms (@{ @<var> @! (@<var> @[@<name>@]) @}^*)      \\ \ind
+      @<declaration>^*                                          \\
+      @<form>^*
+     \-\nlret @<value>^*}
+  Bind each @<var> (a symbol, not evaluated) to a freshly made gensym whose
+  name is based on the corresponding @<name> (a string, evaluated), and
+  evaluate the @<form>s as an implicit @|progn| in the resulting environment.
+  If @<name> is omitted, then the name of the @<var> is used as a default; a
+  bare symbol may be written in place of a singleton list.
 \end{describe}
 
 \begin{describe}{mac}
     {once-only (@[[ :environment @<env> @]]
-                @{ @<var> @! (@<var> @[@<value-form>@]) @}^*) \\ \ind
-      @<declaration>^* \\
-      @<form>^*}
+                @{ @<var> @! (@<var> @[@<value-form>@]) @}^*)   \\ \ind
+      @<declaration>^*                                          \\
+      @<form>^*
+     \-\nlret @<result-form>}
+  This is a helper to ensure that macro expansions evaluate their arguments
+  exactly once each, in the correct order.
+
+  Each @<var> is bound to an appropriate value (often a gensym) and then the
+  @<form>s are evaluated as an implicit @|progn| in the resulting environment
+  to produce an output form.  This output form is then enclosed in one or
+  more binding forms to produce a @<result-form>.  When the @<result-form> is
+  evaluated, the behaviour will be as if each @<value-form> is evaluated
+  exactly once each, in order, and each value is captured in the
+  corresponding @<var>.
+
+  A simple @|once-only| expansion might look something like
+  \begin{prog}
+    (let (\=(@<var>_1 (gensym))                                 \\
+          \>\qquad\vdots                                        \\
+          \>(@<var>_n (gensym)))                                \\ \ind
+      `(let (\=(,@<var>_1 ,@<value-form>_1)                     \\
+             \>\qquad\vdots                                     \\
+             \>(,@<var>_n ,@<value-form>_n))                    \\ \ind
+         @<declaration>_1 \dots\ @<declaration>_m               \\
+         @<form>_1 \dots\ @<form>_\ell))
+  \end{prog}
+  However, if @|once-only| can determine that some @<value-form> is a
+  constant (e.g., it is @|quote|d, self-evaluating, or reported as
+  @|constantp| in the given environment @<env>), then it need not allocate a
+  gensym: it can instead bind the @<var> directly to the constant value.
+
+  If a @<value-form> is omitted, then the value of the corresponding @<var>
+  is used.  It is conventional usage for a macro to wrap @|once-only| around
+  its body so as to convert the arguments which it should evaluate into safe
+  gensyms capturing their runtime values.  (Not that the simple expansion
+  given above can't do this correctly.)  A bare symbol may be written in
+  place of a singleton list.
 \end{describe}
 
-\begin{describe}{mac}
+\begin{describe}{fun}
     {parse-body @<body> \&key :docp :declp
       @> @<doc-string> @<declarations> @<body-forms>}
+  Parse the @<body> into a @<doc-string>, some @<declaration>s, and a list of
+  @<body-forms>.
+
+  The @<body> is assumed to have the general syntax
+  \begin{prog}
+    @[[ @<doc-string> @! @<declaration>^* @]]                   \\
+    @<form>^*
+  \end{prog}
+  A @<doc-string> is permitted if and only if @<docp> is non-nil, and
+  declarations are permitted if and only if @<declp> is non-nil; both are
+  true by default.
+
+  Each return value is a list, which is empty if the corresponding part of
+  the input @<body> is missing.  Specifically:
+  \begin{itemize}
+  \item @<doc-string> is either nil, or a singleton list containing a string;
+  \item @<declarations> is either nil, or a singleton list containing a
+    @|(declare \dots)| form gathering up all of the individual
+    @<declaration>s within the @<body>; and
+  \item @<body-forms> is a list of the remaining forms in the @<body>.
+  \end{itemize}
+  Thus, the parsed body-parts can conveniently be spliced into a macro
+  expansion using @|,@@|.
+\end{describe}
+
+\begin{describe}{fun}{symbolicate \&rest @<symbols> @> @<symbol>}
+  Return the symbol, interned in the current @|*package*|, whose name is the
+  concatenation of the names of the given @<symbols>.
 \end{describe}
 
+
+\subsection{Locatives}
+
+A \emph{locative} is a value which remembers where another value is stored,
+-- whether it's in a variable, an array element, a structure slot, a hash
+table, etc.\ -- and can modify and retrieve it.
+
+Some Lisp systems have highly efficient locatives which actually keep track
+of the machine addresses of the places to which they refer.  Common Lisp does
+not implement true locatives of this kind, but something sufficiently useful
+can be synthesized.
+
+These locatives can't usefully be compared.  It should be possible to compare
+true locatives, such that two locatives compare equal if and only if they
+refer to the same place; but that doesn't work for these locatives.
+
 \begin{describe}{cls}{loc}
+  The type of locative objects.
 \end{describe}
 
 \begin{describe}{fun}{locp @<object> @> @<generalized-boolean>}
+  Return non-nil if and only if @<object> is a locative.
 \end{describe}
 
 \begin{describe}{mac}{locf @<place> @> @<locative>}
+  Return a fresh locative capturing the @<place>, which may be any expression
+  usable as the first operand to @|setf|.
 \end{describe}
 
 \begin{describe*}
     {\dhead{fun}{ref @<locative> @> @<value>}
      \dhead{fun}{setf (ref @<locative>) @<value>}}
+  Retrieve and return the current value stored in the place captured by the
+  @<locative>.  With @|setf|, store the new @<value> in the place captured by
+  the @<locative>.
 \end{describe*}
 
 \begin{describe}{mac}
     {with-locatives
         @{ @<var> @! (@{ @<var> @!
-                         (@<var> @[@<locative>@]) @}^*) @} \\ \ind
-      @<declaration>^* \\
-      @<form>^*}
+                         (@<var> @[@<locative>@]) @}^*) @}      \\ \ind
+      @<declaration>^*                                          \\
+      @<form>^*
+     \-\nlret @<values>^*}
+  This is a macro which hides the use of locatives from its caller using
+  symbol-macros.
+
+  Each @<locative> should be an expression which evaluates to a locative
+  value (not a general place).  These are evaluated once each, left to
+  right.  The @<form>s are then evaluated as an implicit @|progn|, with each
+  @<var> defined as a symbol macro which will retrieve -- or, with @|setf|,
+  modify -- the value referred to by the corresponding locative.
+
+  If a @<locative> is omitted, it defaults to the value of @<var>; a
+  bare symbol may be used in place of a singleton list.
 \end{describe}
 
+
+\subsection{Anaphorics}
+
+An anaphoric macro implicitly binds a well-known name to a value of interest,
+in the course of doing something else.  The concept was popularized by Paul
+Graham \cite{FIXME:OnLisp}.
+
+The macros described here all bind the variable @|it|.
+
 \begin{describe}{sym}{it}
+  The symbol @|it| is exported by the @|sod-utilities| package.
 \end{describe}
 
-\begin{describe}{mac}{aif @<condition> @<consequent> @[@<alt>@]}
+\begin{describe}{mac}{aif @<condition> @<consequent> @[@<alt>@] @> @<value>^*}
+  Evaluate the @<condition>.  If @<condition> is non-nil, then bind @|it| to
+  the resulting value and evaluate the @<consequent>, returning all of its
+  values.  Otherwise, evaluate @<alt>, returning all of its values.
 \end{describe}
 
-\begin{describe}{mac}{awhen @<condition> @<form>^*}
+\begin{describe}{mac}{aand @<form>^* @> @<value>^*}
+  Evaluate each @<form> in turn.  If any @<form> evaluates to nil, then stop
+  and return nil.  Each form except the first is evaluated with @|it| bound
+  to the (necessarily non-nil) value of the previous form.  If all but the
+  last form evaluate non-nil, then return all the values of the final form.
+\end{describe}
+
+(No @|aor| is provided, since @|it| would necessarily be bound to nil.)
+
+\begin{describe}{mac}{awhen @<condition> @<form>^* @> nil}
+  If @<condition> evaluates to a non-nil value, bind @|it| to that value, and
+  evaluate the @<form>s as an implicit @|progn|.  Otherwise, return nil.
 \end{describe}
 
-\begin{describe}{mac}{acond @{ (@<condition> @<form>^*) @}^*}
+\begin{describe}{mac}{acond @{ (@<condition> @<form>^*) @}^* @> @<value>^*}
+  Evaluate each @<condition> in turn, until one of them produces a non-nil
+  value.  If the @<condition> is followed by one or more @<form>s, then bind
+  @|it| to the non-nil value of the @<condition> and evaluate the @<form>s as
+  an implicit @|progn|; otherwise, simply return the value of the
+  @<condition>.  If no @<condition> produces a non-nil value then return nil.
 \end{describe}
 
 \begin{describe*}
-    {\dhead{mac}
-      {acase @<scrutinee> @{ (@{ @<case> @! (@<case>^*) @} @<form>^*) @}^*}
-     \dhead{mac}
-      {aecase @<scrutinee> @{ (@{ @<case> @! (@<case>^*) @} @<form>^*) @}^*}
-     \dhead{mac}{atypecase @<scrutinee> @{ (@<type> @<form>^*) @}^*}
-     \dhead{mac}{aetypecase @<scrutinee> @{ (@<type> @<form>^*) @}^*}}
+    {\dhead{mac}{acase @<scrutinee>
+                  @{ (@{ @<case> @! (@<case>^*) @} @<form>^*) @}^*
+                  @> @<value>^*}
+     \dhead{mac}{aecase @<scrutinee>
+                  @{ (@{ @<case> @! (@<case>^*) @} @<form>^*) @}^*
+                  @> @<value>^*}
+     \dhead{mac}{atypecase @<scrutinee> @{ (@<type> @<form>^*) @}^*
+                  @> @<value>^*}
+     \dhead{mac}{aetypecase @<scrutinee> @{ (@<type> @<form>^*) @}^*
+                  @> @<value>^*}}
+  These are like the Common Lisp macros @|case|, @|ecase|, @|typecase|, and
+  @|etypecase|, except that @|it| is bound to the value of the @<scrutinee>
+  while evaluating the matching @<form>s.
 \end{describe*}
 
-\begin{describe}{mac}{asetf @{ @<place> @<value> @}^*}
+\begin{describe}{mac}{asetf @{ @<place> @<value> @}^* @> @<value>^*}
+  For each @<place> and @<value> in turn: bind @|it| to the current value of
+  the @<place>, evaluate the @<value> expression, and store the resulting
+  value back in the @<place>.  Return the @<value>(s) stored by the final
+  pair: there may be more than one value, e.g., if @<place> is a @|values|
+  form.
+
+  For example, @|(asetf @<place> (1+ it))| is almost equivalent to @|(incf
+  @<place>)|, even if evaluating @<place> has side-effects.
 \end{describe}
 
-\begin{describe}{gf}{instance-initargs @<instance>}
+
+\subsection{Metaobject protocol utilities}
+
+The following utilities make use of the introspection features of the CLOS
+metaobject protocol.
+
+\begin{describe}{gf}{instance-initargs @<instance> @> @<initargs-list>}
+  Return a fresh list of plausible initargs for the given @<instance>.
+
+  This is done by digging through the instance's class's slot definitions and
+  enquiring about their initargs.  Initargs which are handled by methods on
+  @|shared-initialize| or similar generic functions won't be discovered.
 \end{describe}
 
 \begin{describe*}
-    {\dhead{fun}{copy-instance @<instance> \&rest @<initargs>}
+    {\dhead{fun}{copy-instance @<instance> \&rest @<initargs>
+                  @> @<new-instance>}
      \dhead{gf}{copy-instance-using-class @<class> @<instance>
-                                          \&rest @<initargs>}}
+                                          \&rest @<initargs>
+                  @> @<new-instance>}}
+  The @|copy-instance| function creates and returns a fresh copy of a given
+  @<instance>, possibly modifying it according to the given @<initargs>.
+
+  It immediately calls @|copy-instance-using-class|, calling it with the
+  instance's class and the instance itself, and simply returns the result of
+  that generic function.
+
+  The default method on @|copy-instance-using-class| should work for most
+  classes, but may be overridden to cope with special effects.  It works as
+  follows.
+  \begin{enumerate}
+  \item Allocate a fresh instance of @<class>, using @|allocate-instance|.
+  \item For each slot defined by @<class>, if that slot is bound in the
+    original instance, then set the corresponding slot in the new instance to
+    the same value.
+  \item Call @|shared-initialize| on the new instance, providing it the given
+    list of @<initargs>, but inhibiting the usual initialization of slots
+    from their initforms.
+  \item Return the new instance.
+  \end{enumerate}
 \end{describe*}
 
 \begin{describe*}
@@ -108,120 +294,610 @@ These symbols are defined in the @|sod-utilities| package.
      \dhead{gf}{method-specializers @<method> @> @<list>}
      \dhead{cls}{eql-specializer}
      \dhead{gf}{eql-specializer-object @<specializer> @> @<value>}}
+  These are precisely the MOP functions and class: the symbols are
+  re-exported for portability, because different Lisp systems define these
+  symbols in different packages.
 \end{describe*}
 
+
+\subsection{Other CLOS utilities}
+
+Some other minor CLOS utilities.
+
+\begin{describe}{mac}
+    {default-slot (@<instance> @<slot> @[@<slot-names>@])       \\ \ind
+      @<form>^*}
+  This macro is useful in methods (usually @|:after| methods) on
+  @|shared-initialize|, to set slots to some sensible default values in the
+  case where no suitable initarg was given, and default initialization is too
+  complicated to be done using an initform.
+
+  Set a slot to a default value, obeying the @|shared-initialize| protocol.
+  If (a) the named @<slot> of @<instance> is unbound, and (b) either
+  @<slot-names> is @|t|, or @<slot> is a member of the list @<slot-names>,
+  then evaluate the @<form>s as an implicit @|progn| and store their
+  value in the @<slot>.  Otherwise do nothing.
+
+  The @<instance>, @<slot>, and @<slot-names> (if any) are evaluated once
+  each, left-to-right.
+\end{describe}
+
+\begin{describe}{mac}
+    {define-on-demand-slot @<class> @<slot> (@<instance>)       \\ \ind
+      @[[ @<declaration>^* @! @<doc-string> @]]                 \\
+      @<form>^*}
+  This macro makes slots with delayed initialization: rather than being
+  set when the object is constructed, the slot's initial value is only
+  calculated when it's first requested.  This is useful if calculating the
+  slot value is expensive and often not required, or if it's not possible to
+  initialize the slot along with the rest of the object because of dependency
+  cycles.
+
+  The macro arranges things as follows.  Whenever @|slot-value| is called
+  (possibly indirectly, via a reader function) to read the named @<slot> (a
+  symbol, not evaluated) on an (indirect) instance of @<class>, but the slot
+  is unbound, then @<instance> is bound to the instance in question and the
+  @<form>s are evaluated as an implicit @|progn| within the lexical
+  environment of the @|define-on-demand-slot| call, and the resulting value
+  is used as the initial value of the slot.  (Furthermore, a block named
+  @<slot> is wrapped around the @<form>s, allowing an early return if that
+  should be useful.)
+
+  This macro currently works by defining a method on @|slot-unbound|.
+\end{describe}
+
+
+\subsection{Building lists}
+
+Many Lisp functions end up constructing lists.  In simple cases, a function
+like @|mapcar| will just do the job directly.  In more complex cases, a
+common idiom is to build the list using @|push| for each element in turn; but
+a list built this way ends up in the wrong order, so an additional pass,
+usually using @|nreverse|, is necessary to fix it.
+
+A `list builder' is an object which can be used to construct a list in the
+right order.  (Currently, a list-builder is simply a cons cell, whose cdr
+points to the first cons-cell of the list, and whose car points to its last
+cons; an empty list-builder is a cons whose cdr is nil and whose car is the
+cons itself, i.e., @|\#1=(\#1\# . nil)|.)
+
 \begin{describe}{fun}{make-list-builder \&optional @<initial> @> @<builder>}
+  Return a fresh new list-builder, initially containing no items.
 \end{describe}
 
 \begin{describe}{fun}{lbuild-add @<builder> @<item> @> @<builder>}
+  Add @<item> to the end of the list being constructed in @<builder>.
 \end{describe}
 
 \begin{describe}{fun}{lbuild-add-list @<builder> @<list> @> @<builder>}
+  Append @<list> to the list being constructed in @<builder>.  The list is
+  \emph{not} copied: adding further items to the list will clobber cdr of its
+  final cons-cell.
 \end{describe}
 
 \begin{describe}{fun}{lbuild-list @<builder> @> @<list>}
+  Return the list being constructed in the @<builder>.
+
+  It is permitted to continue adding items to the list: this will mutate the
+  list in-place.  Often, this is what you want.  For example, one might write
+  an analogue to @|pushnew| like this:
+  \begin{prog}
+    (defun lbuild-add-new
+        (builder item \&key key test test-not \&rest keywords)  \\ \ind
+      (declare (ignore key test test-not))                      \\
+      (when (apply \#'member item (lbuild-list builder)
+                   keywords)                                    \\ \ind
+        (lbuild-add builder item)))
+  \end{prog}
 \end{describe}
 
+
+\subsection{Merging lists}
+
+The following machinery merges lists representing a partial order.  The
+primary use for this is in computing class precedence lists during class
+finalization.  By building the input lists and choosing the tie-breaking
+@<pick> function appropriately, many different linearization algorithms can
+be implemented fairly easily using @|merge-lists| below.
+
+\begin{describe*}
+    {\dhead{cls}
+       {inconsistent-merge-error (error) \&key :candidates :present}
+     \dhead{gf}{merge-error-candidates @<error> @> @<list>}
+     \dhead{gf}{merge-error-present-function @<error> @> @<function>}}
+  The @|inconsistent-merge-error| condition class used to represent a failure
+  of the \descref{fun}{merge-lists}[function].
+
+  The @<candidates> are a list of offending items from the input lists, in
+  some order: the error is reporting that the function has failed because it
+  is not possible to order the items listed in @<candidates> in any way
+  without being inconsistent with at least one of the input lists.  There is
+  no default.
+
+  The @<present> function is used to convert the input items into
+  human-readable descriptions (printed using @|princ|); the default is
+  @|identity|, which will simply print the items in a `friendly' format.
+  (Using @|prin1-to-string| would print their machine-readable escaped forms
+  instead.)
+
+  The functions @|merge-error-candidates| and @|merge-error-present-function|
+  respectively retrieve the candidates list and presentation function
+  assigned to a condition when it was created.
+\end{describe*}
+
+\begin{describe}{fun}
+    {merge-lists @<lists> \&key :pick :test :present @> @<list>}
+  Return a merge of the @<lists>, considered as partial orderings.
+
+  In more detail: @<lists> should be a list of lists.  Each distinct item, as
+  determined by the @<test> function (by default, @|eql|) appears in the
+  result list exactly once.  Furthermore, if, in some input list, an item $x$
+  appears earlier than a different item $y$, then $x$ will also precede $y$
+  in the output list.
+
+  If the input lists contradict each other (e.g., list $A$ has $x$ before
+  $y$, but list $B$ has $y$ before $x$), then an error of type
+  @|inconsistent-merge-error| is signalled, with the offending items attached
+  as candidates, and the function @<present> (by default, @|identity|) as the
+  presentation function.
+
+  Frequently, a collection of input lists has multiple valid merges.
+  Whenever @|merge-lists| must decide between two or more equally good
+  candidates, it calls the @<pick> function to choose one of them.
+  Specifically, it invokes @|(funcall @<pick> @<candidates>
+  @<merge-so-far>)|, where @<candidates> are the items it needs to choose
+  between, and @<merge-so-far> is the currently determined prefix of the
+  final merge.  The order of items in the @<candidates> list reflects their
+  order in the input lists: item $x$ precedes item $y$ in @<candidates> if
+  any only if an occurrence of $x$ appears in an earlier input list than
+  $y$.  (This completely determines the order of candidates: if two items
+  appear in the same list, then that list would have ordered them and we
+  wouldn't have to call @<pick> to break the tie.)  The default @<pick>
+  function simply chooses the item appearing in the earliest list, i.e.,
+  effectively
+  \begin{prog}
+    (lambda (candidates merge-so-far)                           \\ \ind
+      (declare (ignore merge-so-far))                           \\
+      (car candidates))
+  \end{prog}
+\end{describe}
+
+
+\subsection{Other list utilities}
+
 \begin{describe}{fun}
     {mappend @<function> @<list> \&rest @<more-lists> @> @<result-list>}
+  Return the result of appending @<list> and @<more-lists>, in order.  All
+  but the final list are copied into the @<result-list>; the last one is used
+  as-is.
 \end{describe}
 
-\begin{describe}{cls}{inconsistent-merge-error (error) \&key :candidates}
+\begin{describe}{mac}
+    {categorize (\=@<item-var> @<items>
+                   @[[ :bind (@{ @<var> @!
+                                 (@<var> @[@<value>@]) @}^*) @]])
+                                                                \\ \ind\ind
+        (@{ (@<cat-var> @<cat-predicate>) @}^*)               \-\\
+      @<declaration>^*                                          \\
+      @<form>^*
+     \-\nlret @<value>^*}
+  Partition an input list of @<items> according to the @<cat-predicate>s.
+
+  First, @<items> is evaluated, to yield a list.  The @<item-var> is bound,
+  an empty list is created for each @|(@<cat-var> @<cat-predicate>)| pair,
+  and an iteration is begun.  For each item in the list in turn is assigned
+  to @<item-var>; then, the bindings given by the @|:bind| keyword are
+  performed, as if by @|let*|; and the @<cat-predicate>s are evaluated in the
+  resulting environment, one by one, until one of them returns non-nil.  When
+  this happens, the item is added to the corresponding list.  If no predicate
+  matches the item, an error is signalled.
+
+  Once this iteration is complete, each @<cat-var> is bound to its
+  corresponding completed list, and the body @<form>s are evaluated in the
+  resulting environment (which does not include @<item-var>), as an implicit
+  @|progn|, and the macro yields the values of the final @<form>.
+\end{describe}
+
+\begin{describe}{fun}{partial-order-minima @<items> @<order> @> @<list>}
+  Return a list of minimal items from the list @<items> according to a
+  non-strict partial order defined by the function @<order>: @|(funcall
+  @<order> $x$ $y$)| should return non-nil if and only if $x \preceq y$ in
+  the partial order.
+\end{describe}
+
+\begin{describe}{fun}{cross-product \&rest @<pieces>}
+  Return the cross product of the @<pieces>.
+
+  Each arguments may be a list, or a (non-nil) atom, which is equivalent to a
+  singleton list containing just that atom.  Return a list of all possible
+  lists which can be constructed by taking one item from each argument list
+  in turn, in an arbitrary order.
 \end{describe}
 
-\begin{describe}{gf}{merge-error-candidates @<error> @> @<list>}
+\begin{describe}{fun}
+    {find-duplicates @<report> @<sequence> \&key :key :test}
+  Call @<report> on each pair of duplicate items in a @<sequence>.
+  Duplicates are determined according to the @<key> (by default @|identity|)
+  and @<test> (by default @|eql|) functions, in the usual way: two items $x$
+  and $y$ are considered equal if and only if @|(funcall @<test> (funcall
+  @<key> $x$) (funcall @<key> $y$))| returns non-nil.
+
+  The @<report> function is called as @|(funcall @<report> @<duplicate>
+  @<previous>)|.  Duplicates are reported in order; the @<previous> item is
+  always the first matching item in the sequence.
+
+  This function will work for arbitrary @<test> functions, but it will run
+  much more efficiently if @<test> is @|eq|, @|eql|, @|equal|, or @|equalp|,
+  because it can use hash-tables.  (The generic implementation for lists is
+  especially inefficient.)
 \end{describe}
 
+
+\subsection{Position tracking}
+
+The following functions are used to maintain file positions: see
+\xref{sec:parsing.floc}.  Columns are counted starting from zero at the far
+left.  (No particular origin is needed for line numbers.)  Newlines, vertical
+tabs, and form-feeds all move to the start of the next line; horizontal tabs
+move to the next multiple of eight columns; other characters simply advance
+to the next column.
+
 \begin{describe}{fun}
-    {merge-lists @<lists> \&key :pick (:test \#'eql) @> @<list>}
+    {update-position @<character> @<line> @<column>
+      @> @<new-line> @<new-column>}
+  Assume that we found @<character> at a particular @<line> and @<column> in
+  a file: return the @<new-line> and @<new-column> for the next character.
 \end{describe}
 
+\begin{describe}{fun}
+    {backtrack-position @<character> @<line> @<column>
+      @> @<old-line> @<old-column>}
+  Assume that we are currently at a particular @<line> and @<column> in a
+  file, and wish to \emph{unread} @<character>: return an @<old-line> and
+  @<old-column> at which we might plausibly re-read the character, so that
+  the next call to \descref{fun}{update-position} will return us to @<line>
+  and @<column>.  (Specifically, the @<old-column> will likely be wrong if
+  @<character> is a horizontal tab.  It is expected that this won't matter:
+  the purpose of this function is to set things up so that the
+  @|update-position| call that will accompany re-reading the character will
+  return the correct values, rather than to use the @<old-line> and
+  @<old-column> for any other purpose.)
+\end{describe}
+
+
+\subsection{Object printing}
+
 \begin{describe}{mac}
-    {categorize (\=@<item-var> @<items>
-                   @[[ :bind (@{ @<var> @! (@<var> @[@<value>@]) @}^*) @]])
-                                                                 \\ \ind\ind
-        (@{ (@<cat-var> @<cat-predicate>) @}^*) \- \\
-      @<declaration>^* \\
-      @<body-form>^* \-
-     \nlret @<value>^*}
+    {maybe-print-unreadable-object
+        (@<object> @<stream>
+         @[[ :type @<type> @!
+             :identity @<identity> @]])                         \\ \ind
+      @<declaration>^*                                          \\
+      @<form>^*}
+  If @|*print-escape*| is nil, then simply evaluate the @<form>s as an
+  implicit @|progn|; otherwise, print an `unreadable' object, as if by
+  \begin{prog}
+    (print-unreadable-object
+        (@<object> @<stream>
+         @[:type @<type>@]
+         @[:identity @<identity>@])                             \\ \ind
+      @<form>^*)
+  \end{prog}
+\end{describe}
+
+\begin{describe}{fun}{print-ugly-stuff @<stream> @<func> @> @<value>^*}
+  If @<stream> is a pretty-printing stream, then print a mandatory newline,
+  and call @<func> on the underlying non-pretty-printing stream.  If
+  @<stream> is not a pretty-printing stream, then simply call @<func> on
+  @<stream> directly.
+
+  The main purpose for this is to be able to access features of the
+  underlying stream which a pretty-printing stream can't proxy.  Most
+  notably, this is used by C fragment output, which takes advantage of an
+  underlying \descref{cls}{position-aware-output-stream} to print @|\#line|
+  directives, so that a C~compiler will blame the original fragment in the
+  Sod module source rather than the generated C code.
+\end{describe}
+
+
+\subsection{Condition utilities}
+
+The following definitions are useful when working with conditions.
+
+\begin{describe}{cls}
+    {simple-control-error (control-error simple-error)
+        \&key :format-control :format-arguments}
+  This is the obvious multiply-inherited subclass of @|control-error| whose
+  print form is determined by a @<format-control> and a @<format-arguments>
+  list.
 \end{describe}
 
 \begin{describe}{fun}
-    {frob-identifier @<string> \&key :swap-case :swap-hyphen
-      @> @<frobbed-string>}
+    {designated-condition
+        \=@<default-type> @<datum> @<arguments>                 \\
+        \>\&key :allow-pointless-arguments
+      \nlret @<condition>}
+  Creates and returns a condition object of @<default-type>, given a
+  condition designator @<datum> and @<arguments>.
+
+  The Common Lisp specification carefully explains how a `datum' and an
+  argument list together form a `condition designator', and how such a pair
+  are to be converted into a condition object with some default type, but
+  there's no mechanism provided to simply do this task.  (Functions like
+  @|error| and @|signal| implicitly, but have possibly-undesirable
+  side-effects, and don't allow control over the default type.)
+
+  \begin{itemize}
+
+  \item If @<datum> is a condition object, then the designated condition is
+    simply @<datum>.  In this case, if @<arguments> is not an empty list and
+    @<allow-pointless-arguments> is nil (the default), an error is signalled;
+    otherwise, the @<arguments> are ignored.
+
+  \item If @<datum> is a symbol, then the designated condition is constructed
+    by calling
+    \begin{prog}
+      (apply \#'make-condition @<datum> @<arguments>)
+    \end{prog}
+
+  \item If @<datum> is a string or function (i.e., a `format-control'), then
+    the designated condition is constructed by calling
+    \begin{prog}
+      (make-condition \=@<default-type>                         \\
+                      \>:format-control @<datum>                \\
+                      \>:format-arguments @<arguments>)
+    \end{prog}
+
+  \item Otherwise the designator is malformed, and an error is signalled.
+  \end{itemize}
+\end{describe}
+
+\begin{describe}{fun}
+    {invoke-associated-restart @<restart> @<condition> \&rest @<arguments>}
+  Invoke the active restart named @<restart>, associated with the given
+  @<condition>, passing a list of @<arguments>.
+
+  The function attempts to find and invoke a restart with the given name.  If
+  @<condition> is non-nil, then it searches among restarts associated with
+  that specific condition, and restarts associated with no condition; if
+  @<condition> is nil, then it searches among all restarts.
+
+  If a matching restart is found, it is invoked, passing the @<arguments>
+  list.  Otherwise, an error (of class @|control-error|) is signalled.
+\end{describe}
+
+\begin{describe*}
+    {\dhead{cls}{enclosing-condition (condition) \&key :condition}
+     \dhead{gf}{enclosed-condition @<enclosing-condition> @> @<condition>}}
+  An @|enclosing condition| is a condition which contains another condition
+  within it.  Objects of type @|enclosing-condition| are used to add
+  additional information to an existing condition, or to alter the type of a
+  condition without losing information.
+
+  When an @|enclosing-condition| is constructed, the @<condition> argument
+  names the existing condition to be enclosed.  This enclosed condition can
+  be retrieved by calling @|enclosed-condition|.
+\end{describe*}
+
+\begin{describe}{cls}{information (condition) \&key}
+  A condition of class @|information| conveys information which might be of
+  interest, but does not of itself indicate that anything is wrong.
+
+  Within a compiler, @|information| conditions may be signalled in order to
+  present the user with additional diagnostic information about a recently
+  reported error.
 \end{describe}
 
-\begin{describe}{fun}{whitespace-char-p @<character> @> @<generic-function>}
+\begin{describe}{cls}
+    {simple-information (simple-condition information)          \\ \ind
+      \&key :format-control :format-arguments}
+  This is the obvious multiply-inherited subclass of @|information|
+  whose print-representation is determined by a @<format-control> and a
+  @<format-arguments> list.
 \end{describe}
 
+\begin{describe*}
+    {\dhead{fun}{info @<datum> \&rest @<arguments> @> @<flag>}
+     \dhead{rst}{noted}
+     \dhead{fun}{noted \&optional @<condition>}}
+  The @|info| function establishes a restart named @|noted| and signals a
+  condition of default type @|simple-information|, designated by the @<datum>
+  and @<arguments>.  The @|info| function returns non-nil if and only if the
+  associated @|noted| restart was invoked.
+
+  The @|noted| restart accepts no arguments.
+
+  The @|noted| function finds and invokes a @|noted| restart: if @<condition>
+  is non-nil, then only the restart associated with that condition (and those
+  not associated with any condition) are considered; otherwise, all
+  conditions are considered.
+\end{describe*}
+
 \begin{describe}{fun}
-    {update-position @<character> @<line> @<column>
-      @> @<new-line> @<new-column>}
+    {promiscuous-cerror @<continue-string> @<datum> \&rest @<arguments>}
+  Establish a @|continue| restart and signal an error of default type
+  @|simple-error|, designated by @<datum> and @<arguments>.  The restart's
+  report format is determined by @<continue-string> and the @<arguments>.
+
+  Some implementations of @|cerror| associate the @|continue| restart which
+  they establish with the condition they signal.  This interferes with
+  special effects -- specifically, enclosing the signalled condition and
+  resignalling it.  The @|promiscuous-cerror| function carefully avoids
+  associating its restart with the condition.
+\end{describe}
+
+\begin{describe}{fun}{cerror* @<datum> \&rest @<arguments>}
+  A simplified version of \descref{fun}{promiscuous-cerror} which uses the
+  hardcoded string @|Continue| for the restart.  This makes calling the
+  function more similar to other condition-signalling functions, at the
+  expense of some usability in environments which don't continue after
+  continuable errors automatically.
 \end{describe}
 
+
+\subsection{Very miscellaneous utilities}
+
 \begin{describe}{fun}
-    {backtrack-position @<character> @<line> @<column>
-      @> @<old-line> @<old-column>}
+    {whitespace-char-p @<character> @> @<generalized-boolean>}
+  Return non-nil if and only if @<character> is a whitespace character.
+
+  A character is whitespace if @|(peek-char t @<stream>)| would skip it.
 \end{describe}
 
 \begin{describe}{fun}
-    {compose @<function> \&rest @<more-functions> @> @<function>}
+    {frob-identifier @<string> \&key :swap-case :swap-hyphen
+      @> @<frobbed-string>}
+  Return a `frobbed' version of the identifier @<string>.  Two different
+  transformations can be applied.
+
+  \begin{itemize}
+
+  \item If @<swap-case> is non-nil (the default), and the letters in
+    @<string> are either all uppercase or all lowercase, then switch the case
+    of all of the letters.
+
+  \item If @<swap-hyphen> is non-nil (the default), and @<string> contains
+    either hyphens @`--' or underscores @`_', but not both, then replace the
+    hyphens by underscores or \emph{vice-versa}.
+
+  \end{itemize}
+
+  (These are the `obvious' transformations to convert a C identifier into a
+  Lisp symbol.)
+
+  Some examples:
+  \begin{itemize}
+  \item @|(frob-identifier "foo")| $\Longrightarrow$ @|"FOO"|
+  \item @|(frob-identifier "FOO")| $\Longrightarrow$ @|"foo"|
+  \item @|(frob-identifier "FooBar")| $\Longrightarrow$ @|"FooBar"|
+  \item @|(frob-identifier "Foo-Bar")| $\Longrightarrow$ @|"Foo_Bar"|
+  \item @|(frob-identifier "Foo_Bar")| $\Longrightarrow$ @|"Foo-Bar"|
+  \item @|(frob-identifier "foo_bar")| $\Longrightarrow$ @|"FOO-BAR"|
+  \item @|(frob-identifier "foo_bar" :swap-hyphen nil)| $\Longrightarrow$
+    @|"FOO_BAR"|
+  \item @|(frob-identifier "foo_bar" :swap-case nil)| $\Longrightarrow$
+    @|"foo-bar"|
+  \item @|(frob-identifier "foo_bar" :swap-case nil :swap-hyphen nil)|
+    $\Longrightarrow$ @|"foo_bar"|
+  \end{itemize}
 \end{describe}
 
-\begin{describe}{fun}{symbolicate \&rest @<symbols> @> @<symbol>}
+\begin{describe}{fun}
+    {compose @<functions> @> @<function>}
+  Return the left-to-right composition zero or more @<functions>.
+
+  Let $f_1$, $f_2$, \ldots, $f_n$ be functions, and let $g = @|(compose $f_1$
+  $f_2$ $\cdots$ $f_n$)|$ is their composition.  If $g$ is applied to
+  arguments, the effect is as follows: first, $f_1$ is applied to the
+  arguments, yielding some value; $f_2$ is applied to this value, yielding a
+  second value; and so on, until finally the value yielded by $f_n$ is
+  returned as the result of $g$.  Note that this is the reverse of the usual
+  mathematician's convention, but the author finds this ordering
+  significantly easier to work with:
+  \[ g = f_n \circ \cdots \circ f_2 \circ f_1 \]
+
+  If any of the input functions return multiple values then \emph{all} of the
+  values are passed on to the next function in the list.  (If the last
+  function returns multiple values then all of the values are returned from
+  the composition.
+
+  The result of composing no functions is a function which simply returns all
+  of its arguments as values; essentially, $@|(compose)| \equiv
+  @|\#'values|$.
 \end{describe}
 
-\begin{describe}{mac}
-    {maybe-print-unreadable-object (@<object> @<stream>
-                                    @[[ :type @<type> @!
-                                        :identity @<identity> @]]) \\ \ind
-      @<declaration>^* \\
-      @<form>^*}
+\begin{describe}{mac}{defvar-unbound @<name> @<documentation> @> @<name>}
+  Define a variable called @<name>, with a @<documentation> string.
+
+  The Common Lisp @|defvar| macro accepts both an initial value and a
+  doc-string as optional arguments, in that order, with the result that it's
+  not possible to define a variable and establish a documentation string for
+  it without also giving it an initial value.  The @|defvar-unbound| macro,
+  on the other hand, never changes the symbol's variable-value.
 \end{describe}
 
 \begin{describe}{mac}
     {dosequence (@<var> @<sequence>
                  @[[ :start @<start> @! :end @<end> @!
-                     :indexvar @<var> @]]) \\ \ind
-      @<declaration>^* \\
+                     :indexvar @<index-var> @]])                \\ \ind
+      @<declaration>^*                                          \\
       @{ @<tag> @! @<statement> @}^*}
+  Iterate over a @<sequence>.  Common Lisp has a rich collection of iteration
+  primitives, and a rich collection of functions for working with sequences,
+  but no macro for iterating over the items of a sequence.
+
+  First, the @<sequence> is evaluated.  If @<start> and/or @<end> are
+  provided, they are also evaluated (in that order), which should produce
+  integers; @<end> may be also be nil.  If not provided, or nil (in the case
+  of @<end>), @<start> and @<end> default respectively to zero and the length
+  of the @<sequence>.  For each item in the sequence between the @<start> and
+  @<end> positions (i.e., each item in @|(subseq @<sequence> @<start>
+  @<end>)|, in order, the body is evaluated as an implicit @|tagbody|, with
+  @<var> bound to the item and, if provided, @<index-var> bound to the item's
+  index.  It is not specified whether the @<var> and @<index-var> are
+  let-bound or mutated in each iteration.
+
+  Unlike other Common Lisp @|do|\dots\ forms, there is no `result' form.
 \end{describe}
 
 \begin{describe}{mac}
     {define-access-wrapper @<from> @<to>
                            @[[ :read-only @<read-only-flag> @]]}
-\end{describe}
+  Define @<from> as a function of one argument, so that @|(@<from> @<thing>)|
+  is equivalent to @|(@<to> @<thing>)|.  If @<read-only-flag> is nil (the
+  default), then also define @|(setf @<from>)| so that @|(setf (@<from>
+  @<thing>) @<value>)| is equivalent to @|(setf (@<to> @<thing>) @<value>)|.
 
-\begin{describe}{mac}
-    {default-slot (@<instance> @<slot> @[@<slot-names>@]) \\ \ind
-      @<form>^*}
+  In a @|defstruct| form, the accessor function names are constructed based
+  on the structure name and slot names.  The structure name and accessor
+  names are part of the exported interface, but the slot names ideally
+  shouldn't be.  This causes a problem when the slot name which will lead to
+  the right accessor is already an external symbol in some package.  You can
+  solve this problem by choosing an internal name for the symbol, and then
+  using this macro to define an accessor function with the name that you
+  want, in terms of the accessor that @|defstruct| made.
 \end{describe}
 
-\begin{describe}{mac}
-    {define-on-demand-slot @<class> @<slot> (@<instance>) \\ \ind
-      @[[ @<declaration>^* @! @<doc-string> @]] \\
-      @<form>^*}
-\end{describe}
+\begin{describe}{fun}
+    {distinguished-point-shortest-paths @<root> @<neighbours-func>
+      @> @<list>}
+  Calculate the shortest path from the @<root> to each node reachable from it
+  in a directed graph.  The nodes of the graph can be any kind of object;
+  they will be compared using @|eql|.
 
-%%%--------------------------------------------------------------------------
-\section{Condition utilities} \label{sec:misc.condition}
+  The @<neighbours-func> should be a function which, given a node~$v$ as its
+  only argument, returns a list of cons cells @|($v'$ . $c'$)|, one for each
+  node~$v'$ adjacent to $v$, indicating the cost $c'$ of traversing the arc
+  from $v$ to $v'$.
 
-These symbols are defined in the @|sod-parser| package.
+  The return value is a list of cons cells @|($c$ . $p$)|, where $p$ is list
+  of nodes, in reverse order, along a path from the @<root> to some other
+  node, and $c$ is the total cost of traversing this path.  (Therefore @|(car
+  $p$)| is the destination node, and @|(car (last $p$))| is always the
+  @<root> itself.)
 
-\begin{describe}{cls}{enclosing-condition (condition) \&key :condition}
+  The function runs in $O(n^2)$ time, where $n$ is the number of nodes
+  reachable from the @<root>.  Currently, it uses an algorithm due to Edsger
+  Dijkstra.
 \end{describe}
 
-\begin{describe}{gf}
-    {enclosed-condition @<enclosing-condition> @> @<condition>}
-\end{describe}
 
-\begin{describe}{fun}{cerror* @<datum> \&rest @<arguments>}
+\subsection{Other exported symbols}
+
+\begin{describe}{sym}{int}
+  The symbol @|int| is exported by the @|sod-utilities| package, without
+  giving it any particular meaning.  This is done because it's given
+  non-conflicting meanings by two different packages, and it's more
+  convenient for user code not to have to deal with an unnecessary symbol
+  conflict.  Specifically, the @|sod| package wants to define it as a C type
+  specifier, see \descref{cls}{simple-c-type}; and @|optparse| wants to
+  define it as an option handler, see \descref{opt}{int}.
 \end{describe}
 
 %%%--------------------------------------------------------------------------
 \section{Option parser} \label{sec:misc.optparse}
 
-These symbols are defined in the @!optparse| package.
+Most of these symbols are defined in the @|optparse| package.
 
 \begin{describe}{fun}{exit \&optional (@<code> 0) \&key :abrupt}
 \end{describe}
@@ -251,9 +927,10 @@ These symbols are defined in the @!optparse| package.
 \end{describe}
 
 \begin{describe}{fun}
-    {make-option \=@<long-name> @<short-name> \+ \\
-                   \&optional @<arg-name> \\
-                   \&key :tag :negated-tag :arg-optional-p :documentation \-
+    {make-option \=@<long-name> @<short-name>                 \+\\
+                   \&optional @<arg-name>                       \\
+                   \&key :tag :negated-tag
+                         :arg-optional-p :documentation       \-
       \nlret @<option>}
 \end{describe}
 
@@ -268,8 +945,8 @@ These symbols are defined in the @!optparse| package.
      \dhead{fun}{setf (opt-negated-tag @<option>) @<tag>}
      \dhead{fun}{opt-arg-name @<option> @> @<string-or-null>}
      \dhead{fun}{setf (opt-arg-name @<option>) @<string-or-null>}
-     \dhead{fun}{opt-optional-p @<option> @> @<generalized-boolean>}
-     \dhead{fun}{setf (opt-optional-p @<option>) @<generalized-boolean>}
+     \dhead{fun}{opt-arg-optional-p @<option> @> @<generalized-boolean>}
+     \dhead{fun}{setf (opt-arg-optional-p @<option>) @<generalized-boolean>}
      \dhead{fun}{opt-documentation @<option> @> @<string-or-null>}
      \dhead{fun}{setf (opt-documentation @<option>) @<string-or-null>}}
 \end{describe*}
@@ -306,6 +983,9 @@ These symbols are defined in the @!optparse| package.
       \&key :format-control :format-arguments}
 \end{describe}
 
+\begin{describe}{fun}{option-parse-error @<msg> \&optional @<args>}
+\end{describe}
+
 \begin{describe}{fun}{option-parse-remainder @<option-parser>}
 \end{describe}
 
@@ -340,7 +1020,7 @@ These symbols are defined in the @!optparse| package.
 \begin{describe}{opt}{inc \&optional @<maximum> @<step>}
 \end{describe}
 
-\begin{describe}{opt}{dec \&optional <minimum> <step>}
+\begin{describe}{opt}{dec \&optional @<minimum> @<step>}
 \end{describe}
 
 \begin{describe}{opt}{read}
@@ -424,6 +1104,9 @@ These symbols are defined in the @!optparse| package.
           @<form>^*) @}^*}
 \end{describe}
 
+\begin{describe}{fun}{sod-frontend:augment-options @<options-list>}
+\end{describe}
+
 %%%--------------------------------------------------------------------------
 \section{Property sets} \label{sec:misc.pset}
 
@@ -445,6 +1128,7 @@ These symbols are defined in the @!optparse| package.
 
 \begin{describe*}
     {\dhead{fun}{p-name @<property> @> @<name>}
+     \dhead{meth}{property}{file-location (@<property> property) @> @<floc>}
      \dhead{fun}{p-value @<property> @> @<value>}
      \dhead{fun}{p-type @<property> @> @<type>}
      \dhead{fun}{p-key @<property> @> @<symbol>}
@@ -452,9 +1136,6 @@ These symbols are defined in the @!optparse| package.
      \dhead{fun}{setf (p-seenp @<property>) @<boolean>}}
 \end{describe*}
 
-\begin{describe}{gf}{decode-property @<raw-value> @> @<type> @<value>}
-\end{describe}
-
 \begin{describe}{gf}
     {coerce-property-value @<value> @<type> @<wanted> @> @<coerced-value>}
 \end{describe}
@@ -514,12 +1195,17 @@ These symbols are defined in the @!optparse| package.
 \end{describe}
 
 \begin{describe}{fun}
+    {parse-property @<scanner> @<pset>
+      @> @<result> @<success-flag> @<consumed-flag>}
+\end{describe}
+
+\begin{describe}{fun}
     {parse-property-set @<scanner>
       @> @<result> @<success-flag> @<consumed-flag>}
 \end{describe}
 
 %%%--------------------------------------------------------------------------
-\section{Miscellaneous translator features} \label{sec:misc.pset}
+\section{Miscellaneous translator features} \label{sec:misc.misc}
 
 \begin{describe}{var}{*sod-version*}
 \end{describe}
@@ -527,7 +1213,23 @@ These symbols are defined in the @!optparse| package.
 \begin{describe}{var}{*debugout-pathname*}
 \end{describe}
 
-\begin{describe}{fun}{test-module @<path> @<reason>}
+\begin{describe}{fun}
+    {test-module @<path> \&key :reason :clear :backtrace @> @<status>}
+\end{describe}
+
+\begin{describe}{fun}
+    {test-parse-c-type @<string>
+      @> t @<c-type> @<kernel> @<string> @! nil @<indicator>}
+\end{describe}
+
+\begin{describe}{fun}
+    {test-parse-pset @<string>
+      @> t @<pset> @! nil @<indicator>}
+\end{describe}
+
+\begin{describe}{mac}
+    {test-parser (@<scanner> \&key :backtrace) @<parser> @<input>
+      @> @<result> @<status> @<remainder>}
 \end{describe}
 
 \begin{describe}{fun}{exercise}
