\documentclass{report}
\begin{document}
\title{A generic hash table interface specification for Common Lisp}
\author{Ingvar Mattsson (ingvar@hexapodia.net)}
\maketitle

\chapter{Generic, extendable hash tables for Common Lisp}
\section{Rationale}
 The hash table interface specified in the Common Lisp standard is
 only guaranteed to work with keys that are considered equal with
 either of EQ, EQL, EQUAL or EQUALP. It is sometimes useful for an
 application to have hash tables using keys with different equality
 predicates.

\section{Interface specification}

\subsection{Package}
    All symbols of a generic hash implementation should be accessible
    in a package named so that :genhash is a designator for the
    package. This has the limitation of restricting a developer to
    have at most one GENHASH implementation loaded without having to
    do renaming. It has the advantage that an implementation can probe
    for the existence of a GENHASH implementation using FIND-PACKAGE.

    The functional interface presented here is a minimum
    interface. The underlying implementation is up to the implementor,
    though the reference implementation uses CLOS, generic functions
    and methods of those.

    The interface and operation available on generic hash tables are
    designed to be as close as possible to those available for
    built-in Common Lisp hash tables.

\subsection{Functional interface}
\subsubsection{register-test-designator}
    (register-test-designator test-designator hash-function equal-function)

    This function registers a hash table test designator.  It takes a
    hashing function (that should return an integer) and an equality
    predicate (so possible hash collisions acan be resolved).

    Test designators (with the exception of the four pre-defined
    functions) must be symbols.

    If the hash function ever returns a non-integer, the consequences
    are intentionally undefined, but implementors are enouraged to
    make sure an error is signalled.

    The only restrictions on the hash function is that returns an
    integer value and it is required
    that for any two objects (O1 and O2) so that: \\
\begin{quotation}
  (equal-function O1 O2)
\end{quotation}
    implies that
\begin{quotation}
  (= (hash-function O1) (hash-function O2))
\end{quotation}

    This function will raise the HASH-EXISTS condition if an attempt
    to re-register a test designator if the hash-function and test-function
    are not sufficiently similar (the reference implementation
    considers ``sufficiently similar'' to mean ``tests equal with EQL'').


    There are eight pre-defined test designators
\begin{itemize}
  \item CL:EQ
  \item (function CL:EQ)
  \item CL:EQL
  \item (function CL:EQL)
  \item CL:EQUAL
  \item (function CL:EQUAL)
  \item CL:EQUALP
  \item (function CL:EQUALP)
\end{itemize}  
\subsubsection{make-generic-hashtable}
    (make-generic-hashtable \&key size (test 'eql))

This function creates a new hashtable, using the test predicate
specified. If the test predicate specified is any of 'CL:EQ, 'CL:EQL,
'CL:EQUAL, 'CL:EQUALP a generic hash table with that equality
predicate should be constructed (without any need to pre-register
them).

If the test predicate is any of (FUNCTION CL:EQ), (FUNCTION CL:EQL),
(FUNCTION CL:EQUAL) or (FUNCTION CL:EQUALP), either a system hash
table or a generic hash table, using the relevant test predicate,
should be returned.

If the :size keyword is used, the value sould be treated as a hint to
the initial sizing of the hash table.

If no suitable hash table can be constructed because the specific test
doesn't signal a pre-registered generic hash table, the function will
signal an UNKNOWN-HASH-TEST error.

\subsubsection{hashref}
    (hashref key table \&optional (default nil))

    This function is the GENHASH function that corresponds to the
    Common Lisp GETHASH function. It should accept both system hash
    tables and GENHASH hash tables.
\subsubsection{hashrem}
    (hashrem key table)

    This is the GENHASH function that corresponds to the Common Lisp
    REMHASH function. It should accept both system hash tables and
    GENHASH hash tables.
\subsubsection{hashclr}
    (hashclr table)

    This is the GENHASH function that corresponds to the Common Lisp
    CLRHASH function. It should accept both system hash tables and
    GENHASH hash tables.
\subsubsection{hashmap}
    (hashmap function table)

    This is the GENHASH function that corresponds to the Common Lisp
    MAPHASH function. It should accept both system hash tables and
    GENHASH hash tables.

\subsubsection{generic-hash-table-count}
    (generic-hash-table-count table)

    This is the GENHASH function that corresponds to the Common Lisp
    HASH-TABLE-COUNT function. It should accept both system hash tables and
    GENHASH hash tables.

\subsubsection{generic-hash-table-size}
    (generic-hash-table-size table)

    This is the GENHASH function that corresponds to the Common Lisp
    HASH-TABLE-SIZE function. It should accept both system hash tables and
    GENHASH hash tables.

\subsubsection{generic-hash-table-p}
    (generic-hash-table-p table)

    This is the GENHASH function that corresponds to the Common Lisp
    HASH-TABLE-P function. It should accept both system hash tables and
    GENHASH hash tables.


\subsection{Conditions}
\subsubsection{hash-exists}

This condition (warning either a warning or an error, this is
implementation-dependent) is signalled when re-registering a nickname
with ``sufficiently different'' hash-function and equal-function.

\subsubsection{unknown-hash}

This error is signalled when trying to create a generic hash table of an
unknown type.

\subsection{Reference implementation}
    A reference implementation of GENHASH can be retrieved from
      http://src.hexapodia.net/genhash.tar.gz

\subsection{Copying}
    The right to copy and redistribute this document unmodified is hereby
    granted.
\end{document}