From: Mark Wooding Date: Sat, 3 Aug 2019 15:46:46 +0000 (+0100) Subject: doc/misc.tex: Document many utilities. X-Git-Url: https://git.distorted.org.uk/~mdw/sod/commitdiff_plain/d9db9c73add5814057a80e9969c74419ce30e664 doc/misc.tex: Document many utilities. --- diff --git a/doc/misc.tex b/doc/misc.tex index ad59e8d..178e6ef 100644 --- a/doc/misc.tex +++ b/doc/misc.tex @@ -33,42 +33,129 @@ 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 (@{ @ @! (@ @[@@]) @}^*) \\ \ind @^* \\ @
^*} + Bind each @ (a symbol, not evaluated) to a freshly made gensym whose + name is based on the corresponding @ (a string, evaluated), and + evaluate the @s as an implicit @|progn| in the resulting environment. + If @ is omitted, then the name of the @ 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 @ @]] @{ @ @! (@ @[@@]) @}^*) \\ \ind @^* \\ - @^*} + @^* + \nlret @} + This is a helper to ensure that macro expansions evaluate their arguments + exactly once each, in the correct order. + + Each @ is bound to an appropriate value (often a gensym) and then the + @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 @. When the @ is + evaluated, the behaviour will be as if each @ is evaluated + exactly once each, in order, and each value is captured in the + corresponding @. + + A simple @|once-only| expansion might look something like + \begin{prog} + (let (\=(@_1 (gensym)) \\ + \>\qquad\vdots \\ + \>(@_n (gensym))) \\ \ind + `(let (\=(,@_1 ,@_1) \\ + \>\qquad\vdots \\ + \>(,@_n ,@_n)) \\ \ind + @_1 \dots\ @_m \\ + @_1 \dots\ @_\ell)) + \end{prog} + However, if @|once-only| can determine that some @ is a + constant (e.g., it is @|quote|d, self-evaluating, or reported as + @|constantp| in the given environment @), then it need not allocate a + gensym: it can instead bind the @ directly to the constant value. + + If a @ is omitted, then the value of the corresponding @ + 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}{fun} {parse-body @ \&key :docp :declp @> @ @ @} + Parse the @ into a @, some @s, and a list of + @. + + The @ is assumed to have the general syntax + \begin{prog} + @[[ @ @! @^* @]] \\ + @^* + \end{prog} + A @ is permitted if and only if @ is non-nil, and + declarations are permitted if and only if @ is non-nil; both are + true by default. + + Each return value is a list, which is empty if the corresponding part of + the input @ is missing. Specifically: + \begin{itemize} + \item @ is either nil, or a singleton list containing a string; + \item @ is either nil, or a singleton list containing a + @|(declare \dots)| form gathering up all of the individual + @s within the @; and + \item @ is a list of the remaining forms in the @. + \end{itemize} + Thus, the parsed body-parts can conveniently be spliced into a macro + expansion using @|,@@|. \end{describe} \begin{describe}{fun}{symbolicate \&rest @ @> @} + Return the symbol, interned in the current @|*package*|, whose name is the + concatenation of the names of the given @. \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 @ @> @} + Return non-nil if and only if @ is a locative. \end{describe} \begin{describe}{mac}{locf @ @> @} + Return a fresh locative capturing the @, which may be any expression + usable as the first operand to @|setf|. \end{describe} \begin{describe*} {\dhead{fun}{ref @ @> @} \dhead{fun}{setf (ref @) @}} + Retrieve and return the current value stored in the place captured by the + @. With @|setf|, store the new @ in the place captured by + the @. \end{describe*} \begin{describe}{mac} @@ -77,24 +164,58 @@ These symbols are defined in the @|sod-utilities| package. (@ @[@@]) @}^*) @} \\ \ind @^* \\ @^*} + This is a macro which hides the use of locatives from its caller using + symbol-macros. + + Each @ should be an expression which evaluates to a locative + value (not a general place). These are evaluated once each, left to + right. The @s are then evaluated as an implicit @|progn|, with each + @ defined as a symbol macro which will retrieve -- or, with @|setf|, + modify -- the value referred to by the corresponding locative. + + If a @ is omitted, it defaults to the value of @; 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 @ @ @[@@]} + Evaluate the @. If @ is non-nil, then bind @|it| to + the resulting value and evaluate the @, returning all of its + values. Otherwise, evaluate @, returning all of its values. \end{describe} \begin{describe}{mac}{aand @^*} + Evaluate each @ in turn. If any @ 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 @ @^*} + If @ evaluates to a non-nil value, bind @|it| to that value, and + evaluate the @s as an implicit @|progn|. Otherwise, return nil. \end{describe} \begin{describe}{mac}{acond @{ (@ @^*) @}^*} + Evaluate each @ in turn, until one of them produces a non-nil + value. If the @ is followed by one or more @s, then bind + @|it| to the non-nil value of the @ and evaluate the @s as + an implicit @|progn|; otherwise, simply return the value of the + @. If no @ produces a non-nil value then return nil. \end{describe} \begin{describe*} @@ -104,21 +225,60 @@ These symbols are defined in the @|sod-utilities| package. {aecase @ @{ (@{ @ @! (@^*) @} @^*) @}^*} \dhead{mac}{atypecase @ @{ (@ @^*) @}^*} \dhead{mac}{aetypecase @ @{ (@ @^*) @}^*}} + These are like the Common Lisp macros @|case|, @|ecase|, @|typecase|, and + @|etypecase|, except that @|it| is bound to the value of the @ + while evaluating the matching @s. \end{describe*} \begin{describe}{mac}{asetf @{ @ @ @}^*} + For each @ and @ in turn: bind @|it| to the current value of + the @, evaluate the @ expression, and store the resulting + value back in the @. + + For example, @|(asetf @ (1+ it))| is almost equivalent to @|(incf + @)|, even if evaluating @ has side-effects. \end{describe} \subsection{Metaobject protocol utilities} +The following utilities make use of the introspection features of the CLOS +metaobject protocol. + \begin{describe}{gf}{instance-initargs @} + Return a fresh list of plausible initargs for the given @. + + 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 @ \&rest @} + {\dhead{fun}{copy-instance @ \&rest @ + @> @} \dhead{gf}{copy-instance-using-class @ @ - \&rest @}} + \&rest @ + @> @}} + The @|copy-instance| function creates and returns a fresh copy of a given + @, possibly modifying it according to the given @. + + 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 @, using @|allocate-instance|. + \item For each slot defined by @, 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 @, but inhibiting the usual initialization of slots + from their initforms. + \item Return the new instance. + \end{enumerate} \end{describe*} \begin{describe*} @@ -126,52 +286,172 @@ These symbols are defined in the @|sod-utilities| package. \dhead{gf}{method-specializers @ @> @} \dhead{cls}{eql-specializer} \dhead{gf}{eql-specializer-object @ @> @}} + 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 (@ @ @[@@]) \\ \ind @^*} + 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 @ of @ is unbound, and (b) either + @ is @|t|, or @ is a member of the list @, + then evaluate the @s as an implicit @|progn| and store their + value in the @. Otherwise do nothing. + + The @, @, and @ (if any) are evaluated once + each, left-to-right. \end{describe} \begin{describe}{mac} {define-on-demand-slot @ @ (@) \\ \ind @[[ @^* @! @ @]] \\ @^*} + 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 @ (a + symbol, not evaluated) on an (indirect) instance of @, but the slot + is unbound, then @ is bound to the instance in question and the + @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 + @ is wrapped around the @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 @ @> @} + Return a fresh new list-builder, initially containing no items. \end{describe} \begin{describe}{fun}{lbuild-add @ @ @> @} + Add @ to the end of the list being constructed in @. \end{describe} \begin{describe}{fun}{lbuild-add-list @ @ @> @} + Append @ to the list being constructed in @. 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 @ @> @} + Return the list being constructed in the @. + + 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} -\begin{describe}{cls} - {inconsistent-merge-error (error) \&key :candidates :present} -\end{describe} +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 +@ function appropriately, many different linearization algorithms can +be implemented fairly easily using @|merge-lists| below. -\begin{describe}{gf}{merge-error-candidates @ @> @} -\end{describe} - -\begin{describe}{gf}{merge-error-present-function @ @> @} -\end{describe} +\begin{describe*} + {\dhead{cls} + {inconsistent-merge-error (error) \&key :candidates :present} + \dhead{gf}{merge-error-candidates @ @> @} + \dhead{gf}{merge-error-present-function @ @> @}} + The @|inconsistent-merge-error| condition class used to represent a failure + of the \descref{merge-lists}[function]{fun}. + + The @ 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 @ in any way + without being inconsistent with at least one of the input lists. There is + no default. + + The @ 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 @ \&key :pick (:test \#'eql) :present @> @} + {merge-lists @ \&key :pick :test :present @> @} + Return a merge of the @, considered as partial orderings. + + In more detail: @ should be a list of lists. Each distinct item, as + determined by the @ 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 @ (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 @ function to choose one of them. + Specifically, it invokes @|(funcall @ @ + @)|, where @ are the items it needs to choose + between, and @ is the currently determined prefix of the + final merge. The order of items in the @ list reflects their + order in the input lists: item $x$ precedes item $y$ in @ 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 @ to break the tie.) The default @ + 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} @@ -179,6 +459,9 @@ These symbols are defined in the @|sod-utilities| package. \begin{describe}{fun} {mappend @ @ \&rest @ @> @} + Return the result of appending @ and @, in order. All + but the final list are copied into the @; the last one is used + as-is. \end{describe} \begin{describe}{mac} @@ -190,26 +473,73 @@ These symbols are defined in the @|sod-utilities| package. @^* \\ @^* \-\nlret @^*} + Partition an input list of @ according to the @s. + + First, @ is evaluated, to yield a list. The @ is bound, + an empty list is created for each @|(@ @)| pair, + and an iteration is begun. For each item in the list in turn is assigned + to @; then, the bindings given by the @|:bind| keyword are + performed, as if by @|let*|; and the @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 @ is bound to its + corresponding completed list, and the body @s are evaluated in the + resulting environment (which does not include @), as an implicit + @|progn|, and the macro yields the values of the final @. \end{describe} \begin{describe}{fun}{partial-order-minima @ @ @> @} + Return a list of minimal items from the list @ according to a + non-strict partial order defined by the function @: @|(funcall + @ $x$ $y$)| should return non-nil if and only if $x \preceq y$ in + the partial order. \end{describe} \begin{describe}{fun} {find-duplicates @ @ \&key :key :test} + Call @ on each pair of duplicate items in a @. + Duplicates are determined according to the @ (by default @|identity|) + and @ (by default @|eql|) functions, in the usual way: two items $x$ + and $y$ are considered equal if and only if @|(funcall @ (funcall + @ $x$) (funcall @ $y$))| returns non-nil. + + This function will work for arbitrary @ functions, but it will run + much more efficiently if @ is @|eq|, @|eql|, @|equal|, or @|equalp| + (because it can use hash-tables). \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} {update-position @ @ @ @> @ @} + Assume that we found @ at a particular @ and @ in + a file: return the @ and @ for the next character. \end{describe} \begin{describe}{fun} {backtrack-position @ @ @ @> @ @} + Assume that we are currently at a particular @ and @ in a + file, and wish to \emph{unread} @: return an @ and + @ at which we might plausibly re-read the character, so that + the next call to \descref{update-position}{fun} will return us to @ + and @. (Specifically, the @ will likely be wrong if + @ 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 @ and + @ for any other purpose.) \end{describe} @@ -222,17 +552,42 @@ These symbols are defined in the @|sod-utilities| package. :identity @ @]]) \\ \ind @^* \\ @^*} + If @|*print-escape*| is nil, then simply evaluate the @s as an + implicit @|progn|; otherwise, print an `unreadable' object, as if by + \begin{prog} + (print-unreadable-object + (@ @ + @[:type @@] + @[:identity @@]) \\ \ind + @^*) + \end{prog} \end{describe} \begin{describe}{fun}{print-ugly-stuff @ @ @> @^*} + If @ is a pretty-printing stream, then print a mandatory newline, + and call @ on the underlying non-pretty-printing stream. If + @ is not a pretty-printing stream, then simply call @ on + @ 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{position-aware-output-stream}{cls} 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 @ and a @ + list. \end{describe} \begin{describe}{fun} @@ -240,36 +595,121 @@ These symbols are defined in the @|sod-utilities| package. \=@ @ @ \\ \>\&key :allow-pointless-arguments \nlret @} + Creates and returns a condition object of @, given a + condition designator @ and @. + + 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 @ is a condition object, then the designated condition is + simply @. In this case, if @ is not an empty list and + @ is nil (the default), an error is signalled; + otherwise, the @ are ignored. + + \item If @ is a symbol, then the designated condition is constructed + by calling + \begin{prog} + (apply \#'make-condition @ @) + \end{prog} + + \item If @ is a string or function (i.e., a `format-control'), then + the designated condition is constructed by calling + \begin{prog} + (make-condition \=@ \\ + \>:format-control @ \\ + \>:format-arguments @) + \end{prog} + + \item Otherwise the designator is malformed, and an error is signalled. + \end{itemize} \end{describe} \begin{describe}{fun} {invoke-associated-restart @ @ \&rest @} + Invoke the active restart named @, associated with the given + @, passing a list of @. + + The function attempts to find and invoke a restart with the given name. If + @ is non-nil, then it searches among restarts associated with + that specific condition, and restarts associated with no condition; if + @ is nil, then it searches among all restarts. + + If a matching restart is found, it is invoked, passing the @ + 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 @ @> @}} + 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 @ 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}{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 @ and a + @ list. \end{describe} \begin{describe*} {\dhead{fun}{info @ \&rest @ @> @} \dhead{rst}{noted} \dhead{fun}{noted \&optional @}} + The @|info| function establishes a restart named @|noted| and signals a + condition of default type @|simple-information|, designated by the @ + and @. 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 @ + 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} {promiscuous-cerror @ @ \&rest @} + Establish a @|continue| restart and signal an error of default type + @|simple-error|, designated by @ and @. The restart's + report format is determined by @ and the @. + + 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* @ \&rest @} + A simplified version of \descref{promiscuous-cerror}{fun} 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} @@ -277,6 +717,9 @@ These symbols are defined in the @|sod-utilities| package. \begin{describe}{fun} {whitespace-char-p @ @> @} + Return non-nil if and only if @ is a whitespace character. + + A character is whitespace if @|(peek-char t @)| would skip it. \end{describe} \begin{describe}{fun}