Documentation and news entry for SB-SEQUENCE:{MAP,CONCATENATE,MERGE}

[sbcl.git] / doc / manual / beyond-ansi.texinfo

@node  Beyond the ANSI Standard
@comment  node-name,  next,  previous,  up
@chapter Beyond the ANSI Standard

SBCL is derived from CMUCL, which implements many extensions to the
ANSI standard. SBCL doesn't support as many extensions as CMUCL, but
it still has quite a few.  @xref{Contributed Modules}.

@menu
* Reader Extensions::
* Package-Local Nicknames::
* Package Variance::
* Garbage Collection::
* Metaobject Protocol::
* Extensible Sequences::
* Support For Unix::
* Customization Hooks for Users::
* Tools To Help Developers::
* Resolution of Name Conflicts::
* Hash Table Extensions::
* Random Number Generation::
* Miscellaneous Extensions::
* Stale Extensions::
* Efficiency Hacks::
@end menu

@node Reader Extensions
@comment  node-name,  next,  previous,  up
@section Reader Extensions
@cindex Reader Extensions

SBCL supports extended package prefix syntax, which allows specifying
an alternate package instead of @code{*package*} for the reader to use
as the default package for interning symbols:

@lisp
<package-name>::<form-with-interning-into-package>
@end lisp

Example:

@lisp
  'foo::(bar quux zot) == '(foo::bar foo::quux foo::zot)
@end lisp

Doesn't alter @code{*package*}: if @code{foo::bar} would cause a
read-time package lock violation, so does @code{foo::(bar)}.

@node  Package-Local Nicknames
@comment  node-name,  next,  previous,  up
@section Package-Local Nicknames
@cindex Package-Local Nicknames

SBCL allows giving packages local nicknames: they allow short and
easy-to-use names to be used without fear of name conflict associated
with normal nicknames.

A local nickname is valid only when inside the package for which it
has been specified. Different packages can use same local nickname for
different global names, or different local nickname for same global
name.

Symbol @code{:package-local-nicknames} in @code{*features*} denotes the
support for this feature.

@findex @cl{defpackage}
@defmac @cl{defpackage} name [[option]]* @result{} package

Options are extended to include

@itemize
@item
@code{:local-nicknames (@var{local-nickname} @var{actual-package-name})*}

The package has the specified local nicknames for the corresponding
actual packages.
@end itemize

Example:

@lisp
(defpackage :bar (:intern "X"))
(defpackage :foo (:intern "X"))
(defpackage :quux (:use :cl) (:local-nicknames (:bar :foo) (:foo :bar)))
(find-symbol "X" :foo) ; => FOO::X
(find-symbol "X" :bar) ; => BAR::X
(let ((*package* (find-package :quux)))
  (find-symbol "X" :foo))               ; => BAR::X
(let ((*package* (find-package :quux)))
  (find-symbol "X" :bar))               ; => FOO::X
@end lisp
@end defmac

@include fun-sb-ext-package-local-nicknames.texinfo
@include fun-sb-ext-package-locally-nicknamed-by-list.texinfo
@include fun-sb-ext-add-package-local-nickname.texinfo
@include fun-sb-ext-remove-package-local-nickname.texinfo

@node  Package Variance
@comment  node-name,  next,  previous,  up
@section Package Variance

Common Lisp standard specifies that ``If the new definition is at
variance with the current state of that package, the consequences are
undefined;'' SBCL by default signals a full warning and retains as
much of the package state as possible.

This can be adjusted using @code{sb-ext:*on-package-variance*}:

@include var-sb-ext-star-on-package-variance-star.texinfo

@node  Garbage Collection
@comment  node-name,  next,  previous,  up
@section Garbage Collection
@cindex Garbage collection

SBCL provides additional garbage collection functionality not
specified by ANSI.

@include var-sb-ext-star-after-gc-hooks-star.texinfo
@include fun-sb-ext-gc.texinfo

@subsection Finalization
@cindex Finalization

Finalization allows code to be executed after an object has been
garbage collected. This is useful for example for releasing foreign
memory associated with a Lisp object.

@include fun-sb-ext-finalize.texinfo
@include fun-sb-ext-cancel-finalization.texinfo

@subsection Weak Pointers
@cindex Weak pointers

Weak pointers allow references to objects to be maintained without
keeping them from being garbage collected: useful for building caches
among other things.

Hash tables can also have weak keys and values: @pxref{Hash Table
Extensions}.

@include fun-sb-ext-make-weak-pointer.texinfo
@include fun-sb-ext-weak-pointer-value.texinfo

@subsection Introspection and Tuning

@include var-sb-ext-star-gc-run-time-star.texinfo
@include fun-sb-ext-bytes-consed-between-gcs.texinfo
@include fun-sb-ext-dynamic-space-size.texinfo
@include fun-sb-ext-get-bytes-consed.texinfo
@include fun-sb-ext-gc-logfile.texinfo
@include fun-sb-ext-generation-average-age.texinfo
@include fun-sb-ext-generation-bytes-allocated.texinfo
@include fun-sb-ext-generation-bytes-consed-between-gcs.texinfo
@include fun-sb-ext-generation-minimum-age-before-gc.texinfo
@include fun-sb-ext-generation-number-of-gcs-before-promotion.texinfo
@include fun-sb-ext-generation-number-of-gcs.texinfo

@node Metaobject Protocol
@comment  node-name,  next,  previous,  up
@section Metaobject Protocol

@subsection AMOP Compatibility of Metaobject Protocol

SBCL supports a metaobject protocol which is intended to be compatible
with AMOP; present exceptions to this (as distinct from current bugs)
are:

@itemize

@item
@findex @sbmop{compute-effective-method}
@code{compute-effective-method} only returns one value, not two.

There is no record of what the second return value was meant to
indicate, and apparently no clients for it.

@item
@tindex @cl{generic-function}
@tindex @cl{standard-generic-function}
@tindex @sbmop{funcallable-standard-object}
@tindex @cl{standard-object}
@tindex @cl{function}
The direct superclasses of @code{funcallable-standard-object} are
@code{(function standard-object)}, not @code{(standard-object function)}.

This is to ensure that the @code{standard-object} class is the last of
the standardized classes before @code{t} appearing in the class
precedence list of @code{generic-function} and
@code{standard-generic-function}, as required by section 1.4.4.5 of the
ANSI specification.

@item
@findex @cl{ensure-generic-function}
@findex @sbmop{generic-function-declarations}
the arguments @code{:declare} and @code{:declarations} to
@code{ensure-generic-function} are both accepted, with the leftmost
argument defining the declarations to be stored and returned by
@code{generic-function-declarations}.

Where AMOP specifies @code{:declarations} as the keyword argument to
@code{ensure-generic-function}, the Common Lisp standard specifies
@code{:declare}.  Portable code should use @code{:declare}.

@item
@findex @sbmop{validate-superclass}
@findex @sbmop{finalize-inheritance}
@tindex @cl{standard-class}
@tindex @sbmop{funcallable-standard-class}
@tindex @cl{function}
@findex @sbmop{class-prototype}
although SBCL obeys the requirement in AMOP that
@code{validate-superclass} should treat @code{standard-class} and
@code{funcallable-standard-class} as compatible metaclasses, we
impose an additional requirement at class finalization time: a class
of metaclass @code{funcallable-standard-class} must have
@code{function} in its superclasses, and a class of metaclass
@code{standard-class} must not.

@findex @cl{typep}
@findex @cl{class-of}
@findex @cl{subtypep}
After a class has been finalized, it is associated with a class
prototype which is accessible by a standard mop function
@code{class-prototype}.  The user can then ask whether this object is a
@code{function} or not in several different ways: whether it is a
function according to @code{typep}; whether its @code{class-of} is
@code{subtypep} @code{function}, or whether @code{function} appears in
the superclasses of the class.  The additional consistency requirement
comes from the desire to make all of these answers the same.

The following class definitions are bad, and will lead to errors
either immediately or if an instance is created:
@lisp
(defclass bad-object (funcallable-standard-object)
  ()
  (:metaclass standard-class))
@end lisp
@lisp
(defclass bad-funcallable-object (standard-object)
  ()
  (:metaclass funcallable-standard-class))
@end lisp
The following definition is acceptable:
@lisp
(defclass mixin ()
  ((slot :initarg slot)))
(defclass funcallable-object (funcallable-standard-object mixin)
  ()
  (:metaclass funcallable-standard-class))
@end lisp
and leads to a class whose instances are funcallable and have one slot.

@tindex @sbmop{funcallable-standard-object}
Note that this requirement also applies to the class
@code{funcallable-standard-object}, which has metaclass
@code{funcallable-standard-class} rather than
@code{standard-class} as AMOP specifies.

@item
the requirement that ``No portable class @math{C_p} may inherit, by
virtue of being a direct or indirect subclass of a specified class, any
slot for which the name is a symbol accessible in the
@code{common-lisp-user} package or exported by any package defined in
the ANSI Common Lisp standard.'' is interpreted to mean that the
standardized classes themselves should not have slots named by external
symbols of public packages.

The rationale behind the restriction is likely to be similar to the ANSI
Common Lisp restriction on defining functions, variables and types named
by symbols in the Common Lisp package: preventing two independent pieces
of software from colliding with each other.

@item
@findex @sbmop{slot-value-using-class}
@findex @setf{@sbmop{slot-value-using-class}}
@findex @sbmop{slot-boundp-using-class}
specializations of the @code{new-value} argument to @code{(setf
slot-value-using-class)} are not allowed: all user-defined methods must
have a specializer of the class @code{t}.

This prohibition is motivated by a separation of layers: the
@code{slot-value-using-class} family of functions is intended for use in
implementing different and new slot allocation strategies, rather than
in performing application-level dispatching.  Additionally, with this
requirement, there is a one-to-one mapping between metaclass, class and
slot-definition-class tuples and effective methods of @code{(setf
slot-value-using-class)}, which permits optimization of @code{(setf
slot-value-using-class)}'s discriminating function in the same manner as
for @code{slot-value-using-class} and @code{slot-boundp-using-class}.

Note that application code may specialize on the @code{new-value}
argument of slot accessors.

@item
@findex @cl{defclass}
@findex @sbmop{ensure-class}
@findex @sbmop{ensure-class-using-class}
@findex @cl{find-class}
@findex @cl{class-name}
the class named by the @code{name} argument to @code{ensure-class}, if
any, is only redefined if it is the proper name of that class;
otherwise, a new class is created.

This is consistent with the description of @code{ensure-class} in AMOP
as the functional version of @code{defclass}, which has this behaviour;
however, it is not consistent with the weaker requirement in AMOP, which
states that any class found by @code{find-class}, no matter what its
@code{class-name}, is redefined.

@item
@findex @sbmop{slot-definition-name}
@tindex @cl{structure-class}
@findex @cl{defstruct}
an error is not signaled in the case of the @code{:name} initialization
argument for @code{slot-definition} objects being a constant, when the
slot definition is of type @code{structure-slot-definition} (i.e. it is
associated with a class of type @code{structure-class}).

This allows code which uses constant names for structure slots to
continue working as specified in ANSI, while enforcing the constraint
for all other types of slot.

@item
@tindex @cl{t}
@tindex @cl{built-in-class}
@findex @sbmop{validate-superclass}
@findex @cl{defclass}
the class named @code{t} is not an instance of the @code{built-in-class}
metaclass.

AMOP specifies, in the ``Inheritance Structure of Metaobject Classes''
section, that the class named @code{t} should be an instance of
@code{built-in-class}.  However, it also specifies that
@code{validate-superclass} should return true (indicating that a direct
superclass relationship is permissible) if the second argument is the
class named @code{t}.  Also, ANSI specifies that classes with metaclass
@code{built-in-class} may not be subclassed using @code{defclass}, and
also that the class named @code{t} is the universal superclass,
inconsistent with it being a @code{built-in-class}.

@end itemize

@subsection Metaobject Protocol Extensions

In addition, SBCL supports extensions to the Metaobject protocol from
AMOP; at present, they are:

@itemize

@item
@findex @cl{defmethod}
@findex @cl{find-class}
@findex @sbmop{intern-eql-specializer}
@findex @sbpcl{make-method-specializers-form}
@findex @sbmop{make-method-lambda}
compile-time support for generating specializer metaobjects from
specializer names in @code{defmethod} forms is provided by the
@code{make-method-specializers-form} function, which returns a form
which, when evaluated in the lexical environment of the
@code{defmethod}, returns a list of specializer metaobjects.  This
operator suffers from similar restrictions to those affecting
@code{make-method-lambda}, namely that the generic function must be
defined when the @code{defmethod} form is expanded, so that the
correct method of @code{make-method-specializers-form} is invoked.
The system-provided method on @code{make-method-specializers-form}
generates a call to @code{find-class} for each symbol specializer
name, and a call to @code{intern-eql-specializer} for each @code{(eql
@var{x})} specializer name.

@item
@findex @cl{find-method}
@findex @sbpcl{parse-specializer-using-class}
@findex @sbpcl{unparse-specializer-using-class}
run-time support for converting between specializer names and
specializer metaobjects, mostly for the purposes of
@code{find-method}, is provided by
@code{parse-specializer-using-class} and
@code{unparse-specializer-using-class}, which dispatch on their first
argument, the generic function associated with a method with the given
specializer.  The system-provided methods on those methods convert
between classes and proper names and between lists of the form
@code{(eql @var{x})} and interned eql specializer objects.

@item
@vindex @sbpcl{+slot-unbound+}
@findex @sbmop{standard-instance-access}
@findex @sbmop{funcallable-standard-instance-access}
distinguishing unbound instance allocated slots from bound ones when
using @code{standard-instance-access} and
@code{funcallable-standard-instance-access} is possible by comparison
to the constant @code{+slot-unbound+}.

@end itemize

@node Extensible Sequences
@comment  node-name,  next,  previous,  up
@section Extensible Sequences

@menu
* Iterator Protocol::
* Simple Iterator Protocol::
@end menu

ANSI Common Lisp has a class @code{sequence} with subclasses @code{list} and
@code{vector} on which the ``sequence functions'' like @code{find},
@code{subseq}, etc. operate. As an extension to the ANSI specification,
SBCL allows additional subclasses of @code{sequence} to be defined
@footnote{A motivation, rationale and additional examples for the design
of this extension can be found in the paper @cite{Rhodes, Christophe
(2007): User-extensible sequences in Common Lisp} available for download
at
@url{http://www.doc.gold.ac.uk/~mas01cr/papers/ilc2007/sequences-20070301.pdf}.}.
@tindex @cl{sequence}
@tindex @cl{vector}
@findex @cl{find}
@findex @cl{subseq}

Users of this extension just make instances of @code{sequence} subclasses
and transparently operate on them using sequence functions:
@lisp
(coerce (subseq (make-instance 'my-sequence) 5 10) 'list)
@end lisp
From this perspective, no distinction between builtin and user-defined
@code{sequence} subclasses should be necessary.
@findex @cl{coerce}
@findex @cl{subseq}
@findex @cl{make-instance}
@tindex @cl{list}

Providers of the extension, that is of user-defined @code{sequence}
subclasses, have to adhere to a ``sequence protocol'' which consists of
a set of generic functions in the @code{sequence} package.
@c
A minimal @code{sequence} subclass has to specify @code{standard-object} and
@code{sequence} as its superclasses and has to be the specializer of the
@code{sequence} parameter of methods on at least the following generic
functions:
@tindex @cl{sequence}
@tindex @cl{standard-object}

@include fun-sb-sequence-length.texinfo
@include fun-sb-sequence-elt.texinfo
@include fun-sb-sequence-setf-elt.texinfo
@include fun-sb-sequence-adjust-sequence.texinfo
@include fun-sb-sequence-make-sequence-like.texinfo

@code{make-sequence-like} is needed for functions returning
freshly-allocated sequences such as @code{subseq} or
@code{copy-seq}. @code{adjust-sequence} is needed for functions which
destructively modify their arguments such as @code{delete}. In fact, all
other sequence functions can be implemented in terms of the above
functions and actually are, if no additional methods are
defined. However, relying on these generic implementations, in
particular not implementing the iterator protocol can incur a high
performance penalty @xref{Iterator Protocol}.
@tindex @cl{sequence}
@findex @sequence{make-sequence-like}
@findex @cl{subseq}
@findex @cl{copy-seq}
@findex @sequence{adjust-sequence}

In addition to the mandatory functions above, methods on the sequence
functions listed below can be defined.

There are two noteworthy irregularities:
@itemize
@item
The function @code{sb-sequence:emptyp} does not have a counterpart in
the @code{cl} package. It is intended to be used instead of
@code{length} when working with lazy or infinite sequences.

@item
The functions @code{map}, @code{concatenate} and @code{merge} receive a
type designator specifying the type of the constructed sequence as their
first argument. However, the corresponding generic functions
@code{sb-sequence:map}, @code{sb-sequence:concatenate} and
@code{sb-sequence:merge} receive a prototype instance of the requested
@code{sequence} subclass instead.
@end itemize

@include fun-sb-sequence-emptyp.texinfo

@itemize
@item
@code{sb-sequence:count}, @code{sb-sequence:count-if}, @code{sb-sequence:count-if-not}

@item
@code{sb-sequence:find}, @code{sb-sequence:find-if}, @code{sb-sequence:find-if-not}

@item
@code{sb-sequence:position}, @code{sb-sequence:position-if}, @code{sb-sequence:position-if-not}

@item
@code{sb-sequence:subseq}

@item
@code{sb-sequence:copy-seq}

@item
@code{sb-sequence:fill}

@item
@include fun-sb-sequence-map.texinfo

@item
@code{sb-sequence:nsubstitute}, @code{sb-sequence:nsubstitute-if},
@code{sb-sequence:nsubstitute-if-not}, @code{sb-sequence:substitute},
@code{sb-sequence:substitute-if}, @code{sb-sequence:substitute-if-not}

@item
@code{sb-sequence:replace}

@item
@code{sb-sequence:nreverse}, @code{sb-sequence:reverse}

@item
@include fun-sb-sequence-concatenate.texinfo

@item
@code{sb-sequence:reduce}

@item
@code{sb-sequence:mismatch}

@item
@code{sb-sequence:search}

@item
@code{sb-sequence:delete}, @code{sb-sequence:delete-if}, @code{sb-sequence:delete-if-not},
@code{sb-sequence:remove}, @code{sb-sequence:remove-if}, @code{sb-sequence:remove-if-not},

@item
@code{sb-sequence:delete-duplicates}, @code{sb-sequence:remove-duplicates}

@item
@code{sb-sequence:sort}, @code{sb-sequence:stable-sort}

@item
@include fun-sb-sequence-merge.texinfo
@end itemize

In the spirit of @code{dolist}, generic sequences can be traversed using
the macro
@findex @cl{dolist}

@include macro-sb-sequence-dosequence.texinfo

@node Iterator Protocol
@comment  node-name,  next,  previous,  up
@subsection Iterator Protocol

The iterator protocol allows subsequently accessing some or all elements
of a sequence in forward or reverse direction. Users first call
@code{make-sequence-iterator} to create an iteration state and
receive functions to query and mutate it. These functions allow, among
other things, moving to, retrieving or modifying elements of the
sequence. An iteration state consists of a state object, a limit object,
a from-end indicator and the following six functions to query or mutate
this state:
@findex @sequence{make-sequence-iterator}
@deffn {Function} @code{step function} sequence iterator from-end
Moves the iterator one position forward or backward in the associated
sequence depending on the iteration direction.
@end deffn
@deffn {Function} @code{endp function} sequence iterator limit from-end
Returns non-@code{nil} when the iterator has reached the end of the
associated sequence with respect to the iteration direction.
@end deffn
@deffn {Function} @code{element function} sequence iterator
Returns the sequence element associated to the current position of the
iteration.
@end deffn
@deffn {Function} @code{setf element function} new-value sequence iterator
Destructively modifies the associates sequence by replacing the sequence
element associated to the current iteration position with a new value.
@end deffn
@deffn {Function} @code{index function} sequence iterator
Returns the position of the iteration in the associated sequence.
@end deffn
@deffn {Function} @code{copy function} sequence iterator
Returns a copy of the iteration state which can be mutated independently
of the copied iteration state.
@end deffn

An iterator is created by calling:

@include fun-sb-sequence-make-sequence-iterator.texinfo

Note that @code{make-sequence-iterator} calls
@code{make-simple-sequence-iterator} when there is no specialized
method for a particular @code{sequence} subclass. @xref{Simple Iterator
Protocol}.
@findex @sequence{make-sequence-iterator}
@findex @sequence{make-simple-sequence-iterator}
@tindex @cl{sequence}

The following convenience macros simplify traversing sequences using
iterators:

@include macro-sb-sequence-with-sequence-iterator.texinfo
@include macro-sb-sequence-with-sequence-iterator-functions.texinfo

@node Simple Iterator Protocol
@comment  node-name,  next,  previous,  up
@subsection Simple Iterator Protocol

For cases in which the full flexibility and performance of the general
sequence iterator protocol is not required, there is a simplified
sequence iterator protocol consisting of a few generic functions which
can be specialized for iterator classes:

@include fun-sb-sequence-iterator-step.texinfo
@include fun-sb-sequence-iterator-endp.texinfo
@include fun-sb-sequence-iterator-element.texinfo
@include fun-sb-sequence-setf-iterator-element.texinfo
@include fun-sb-sequence-iterator-index.texinfo
@include fun-sb-sequence-iterator-copy.texinfo

Iterator objects implementing the above simple iteration protocol are
created by calling the following generic function:

@include fun-sb-sequence-make-simple-sequence-iterator.texinfo

@node  Support For Unix
@comment  node-name,  next,  previous,  up
@section Support For Unix

@menu
* Command-line arguments::
* Querying the process environment::
* Running external programs::
@end menu

@node Command-line arguments
@subsection Command-line arguments
@vindex @sbext{@earmuffs{posix-argv}}

The UNIX command line can be read from the variable
@code{sb-ext:*posix-argv*}.

@node Querying the process environment
@subsection Querying the process environment

The UNIX environment can be queried with the
@code{sb-ext:posix-getenv} function.

@include fun-sb-ext-posix-getenv.texinfo

@node Running external programs
@subsection Running external programs

External programs can be run with @code{sb-ext:run-program}.
@footnote{In SBCL versions prior to 1.0.13, @code{sb-ext:run-program}
searched for executables in a manner somewhat incompatible with other
languages.  As of this version, SBCL uses the system library routine
@code{execvp(3)}, and no longer contains the function,
@code{find-executable-in-search-path}, which implemented the old
search.  Users who need this function may find it
in @file{run-program.lisp} versions 1.67 and earlier in SBCL's CVS
repository here
@url{http://sbcl.cvs.sourceforge.net/sbcl/sbcl/src/code/run-program.lisp?view=log}. However,
we caution such users that this search routine finds executables that
system library routines do not.}

@include fun-sb-ext-run-program.texinfo

When @code{sb-ext:run-program} is called with @code{wait} equal to
NIL, an instance of class @var{sb-ext:process} is returned.  The
following functions are available for use with processes:

@include fun-sb-ext-process-p.texinfo

@include fun-sb-ext-process-input.texinfo

@include fun-sb-ext-process-output.texinfo

@include fun-sb-ext-process-error.texinfo

@include fun-sb-ext-process-alive-p.texinfo

@include fun-sb-ext-process-status.texinfo

@include fun-sb-ext-process-wait.texinfo

@include fun-sb-ext-process-exit-code.texinfo

@include fun-sb-ext-process-core-dumped.texinfo

@include fun-sb-ext-process-close.texinfo

@include fun-sb-ext-process-kill.texinfo

@node  Customization Hooks for Users
@comment  node-name,  next,  previous,  up
@section Customization Hooks for Users

The toplevel repl prompt may be customized, and the function
that reads user input may be replaced completely.
@c <!-- FIXME but I don't currently remember how -->

The behaviour of @code{require} when called with only one argument is
implementation-defined.  In SBCL, @code{require} behaves in the
following way:

@include fun-common-lisp-require.texinfo
@include var-sb-ext-star-module-provider-functions-star.texinfo

Although SBCL does not provide a resident editor, the @code{ed}
function can be customized to hook into user-provided editing
mechanisms as follows:

@include fun-common-lisp-ed.texinfo
@include var-sb-ext-star-ed-functions-star.texinfo

Conditions of type @code{warning} and @code{style-warning} are
sometimes signaled at runtime, especially during execution of Common
Lisp defining forms such as @code{defun}, @code{defmethod}, etc.  To
muffle these warnings at runtime, SBCL provides a variable
@code{sb-ext:*muffled-warnings*}:

@include var-sb-ext-star-muffled-warnings-star.texinfo

@node Tools To Help Developers
@comment  node-name,  next,  previous,  up
@section Tools To Help Developers
@findex @cl{trace}
@findex @cl{inspect}

SBCL provides a profiler and other extensions to the ANSI @code{trace}
facility.  For more information, see @ref{Macro common-lisp:trace}.

The debugger supports a number of options. Its documentation is
accessed by typing @kbd{help} at the debugger prompt. @xref{Debugger}.

Documentation for @code{inspect} is accessed by typing @kbd{help} at
the @code{inspect} prompt.

@node Resolution of Name Conflicts
@section Resolution of Name Conflicts
@tindex @sbext{name-conflict}
@findex @sbext{name-conflict-symbols}

The ANSI standard (section 11.1.1.2.5) requires that name conflicts in
packages be resolvable in favour of any of the conflicting symbols.  In
the interactive debugger, this is achieved by prompting for the symbol
in whose favour the conflict should be resolved; for programmatic use,
the @code{sb-ext:resolve-conflict} restart should be invoked with one
argument, which should be a member of the list returned by the condition
accessor @code{sb-ext:name-conflict-symbols}.

@node    Hash Table Extensions
@comment  node-name,  next,  previous,  up
@section Hash Table Extensions
@cindex Hash tables

Hash table extensions supported by SBCL are all controlled by keyword
arguments to @code{make-hash-table}.

@include fun-common-lisp-make-hash-table.texinfo

@include macro-sb-ext-define-hash-table-test.texinfo

@include macro-sb-ext-with-locked-hash-table.texinfo

@include fun-sb-ext-hash-table-synchronized-p.texinfo

@include fun-sb-ext-hash-table-weakness.texinfo

@node    Random Number Generation
@comment  node-name,  next,  previous,  up
@section Random Number Generation
@cindex Random Number Generation

The initial value of @code{*random-state*} is the same each time SBCL
is started. This makes it possible for user code to obtain repeatable
pseudo random numbers using only standard-provided functionality. See
@code{seed-random-state} below for an SBCL extension that allows to
seed the random number generator from given data for an additional
possibility to achieve this. Non-repeatable random numbers can always
be obtained using @code{(make-random-state t)}.

The sequence of numbers produced by repeated calls to @code{random}
starting with the same random state and using the same sequence of
@code{limit} arguments is guaranteed to be reproducible only in the
same version of SBCL on the same platform, using the same code under
the same evaluator mode and compiler optimization qualities. Just two
examples of differences that may occur otherwise: calls to
@code{random} can be compiled differently depending on how much is
known about the @code{limit} argument at compile time, yielding
different results even if called with the same argument at run time,
and the results can differ depending on the machine's word size, for
example for limits that are fixnums under 64-bit word size but bignums
under 32-bit word size.

@include fun-sb-ext-seed-random-state.texinfo

Some notes on random floats: The standard doesn't prescribe a specific
method of generating random floats. The following paragraph describes
SBCL's current implementation and should be taken purely informational,
that is, user code should not depend on any of its specific properties.
The method used has been chosen because it is common, conceptually
simple and fast.

To generate random floats, SBCL evaluates code that has an equivalent
effect as
@lisp
(* limit
   (float (/ (random (expt 2 23)) (expt 2 23)) 1.0f0))
@end lisp
(for single-floats) and correspondingly (with @code{52} and
@code{1.0d0} instead of @code{23} and @code{1.0f0}) for double-floats.
Note especially that this means that zero is a possible return value
occurring with probability @code{(expt 2 -23)} respectively
@code{(expt 2 -52)}. Also note that there exist twice as many
equidistant floats between 0 and 1 as are generated. For example, the
largest number that @code{(random 1.0f0)} ever returns is
@code{(float (/ (1- (expt 2 23)) (expt 2 23)) 1.0f0)} while
@code{(float (/ (1- (expt 2 24)) (expt 2 24)) 1.0f0)} is the
largest single-float less than 1. This is a side effect of the fact
that the implementation uses the fastest possible conversion from bits
to floats.

SBCL currently uses the Mersenne Twister as its random number
generator, specifically the 32-bit version under both 32- and 64-bit
word size. The seeding algorithm has been improved several times by
the authors of the Mersenne Twister; SBCL uses the third version
(from 2002) which is still the most recent as of June 2012. The
implementation has been tested to provide output identical to the
recommended C implementation.

While the Mersenne Twister generates random numbers of much better
statistical quality than other widely used generators, it uses only
linear operations modulo 2 and thus fails some statistical
tests@footnote{See chapter 7 "Testing widely used RNGs" in
@cite{TestU01: A C Library for Empirical Testing of Random Number
Generators} by Pierre L'Ecuyer and Richard Simard, ACM Transactions on
Mathematical Software, Vol. 33, article 22, 2007.}.
For example, the distribution of ranks of (sufficiently large) random
binary matrices is much distorted compared to the theoretically
expected one when the matrices are generated by the Mersenne Twister.
Thus, applications that are sensitive to this aspect should use a
different type of generator.

@node    Miscellaneous Extensions
@comment  node-name,  next,  previous,  up
@section Miscellaneous Extensions

@include fun-sb-ext-array-storage-vector.texinfo
@include fun-sb-ext-delete-directory.texinfo
@include fun-sb-ext-get-time-of-day.texinfo
@include macro-sb-ext-wait-for.texinfo
@include fun-sb-ext-assert-version-gt=.texinfo

@node Stale Extensions
@comment  node-name,  next,  previous,  up
@section Stale Extensions

SBCL has inherited from CMUCL various hooks to allow the user to
tweak and monitor the garbage collection process. These are somewhat
stale code, and their interface might need to be cleaned up. If you
have urgent need of them, look at the code in @file{src/code/gc.lisp}
and bring it up on the developers' mailing list.

SBCL has various hooks inherited from CMUCL, like
@code{sb-ext:float-denormalized-p}, to allow a program to take
advantage of IEEE floating point arithmetic properties which aren't
conveniently or efficiently expressible using the ANSI standard. These
look good, and their interface looks good, but IEEE support is
slightly broken due to a stupid decision to remove some support for
infinities (because it wasn't in the ANSI spec and it didn't occur to
me that it was in the IEEE spec). If you need this stuff, take a look
at the code and bring it up on the developers' mailing
list.


@node  Efficiency Hacks
@comment  node-name,  next,  previous,  up
@section Efficiency Hacks

The @code{sb-ext:purify} function causes SBCL first to collect all
garbage, then to mark all uncollected objects as permanent, never again
attempting to collect them as garbage. This can cause a large increase
in efficiency when using a primitive garbage collector, or a more
moderate increase in efficiency when using a more sophisticated garbage
collector which is well suited to the program's memory usage pattern. It
also allows permanent code to be frozen at fixed addresses, a
precondition for using copy-on-write to share code between multiple Lisp
processes.  This is less important with modern generational garbage
collectors, but not all SBCL platforms use such a garbage collector.

@include fun-sb-ext-purify.texinfo

The @code{sb-ext:truly-the} special form declares the type of the
result of the operations, producing its argument; the declaration is
not checked. In short: don't use it.

@include special-operator-sb-ext-truly-the.texinfo

The @code{sb-ext:freeze-type} declaration declares that a
type will never change, which can make type testing
(@code{typep}, etc.) more efficient for structure types.