<!-- -*- Mode: HTML-*- -->
<!-- cleqcmp.html : Generic Equality and Comparisons for Common --
-- Lisp.
-->
<!DOCTYPE HTML PUBLIC
"-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<title>Generic Equality and Comparison for Common Lisp</title>
</head>
<body>
<h1>Generic Equality and Comparison for <strong>Common Lisp</strong></h1>
<p>
Marco Antoniotti<br />
Dipartimento di Informatica, Sistemistica e Comunicazione<br />
Università degli Studi di Milano Bicocca<br />
Viale Sarca 336, U14, Milan (MI), Italy<br />
<tt>mantoniotti</tt> at <tt>common-lisp.net</tt>,
<tt>marco.antoniotti</tt> at <tt>unimib.it</tt>
</p>
<p>2011-02-28</p>
<h1>Abstract</h1>
<p>
This document presents new generic functions for <strong>Common
Lisp</strong> that provide user hooks for extensible
<em>equality</em> and <em>comparison tests</em>, as well as generic
<em>hashing</em>. This is in addition to the standard equality and
comparison predicates. The current proposal is <em>minimal</em>, in
the sense that it just provides one conceptually simple set of hooks
in what is considered a cross-language consensus.
</p>
<h1>Introduction</h1>
<p>
Several <strong>Common Lisp</strong> functions rely on the
<code>:test</code> keyword to pass a predicate to be used in their
operations. This is a satisfactory solution in most cases, yet,
while <em>writing</em> algorithms and libraries it would be useful
to have "hooks" in the type and class system allowing for
the definition of <i>extensible</i> <em>equality</em> and
<em>comparison tests</em>.
</p>
<p>
This proposal contains a <b>minimal</b> set of (generic) functions
that can be recognized in several language specifications, e.g., Java.
</p>
<p>
The specification is centered on two concepts: that of an
<em>equality</em> test and that of a <em>comparison</em> generic
operator. The <em>comparison</em> operator returns different values
depending on whether the its execution determines the <em>ordering
relationship</em> (or lack thereof) of two objects.
</p>
<p>
In addition to these two basic concepts, the specification provides
notion of generic hash function too. Of course, there are several
"caveats" to be taken into consideration in the interplay between
equality and hashing.
</p>
<h1>Description</h1>
<p>
The the proposal describes the <em>equality</em> and
<em>comparison</em> operators. The <em>equality</em> operator is
called <code>EQUALS</code> and some synonyms are also defined. The
<em>comparison</em> operators is called <code>COMPARE</code>. The
utility functions <code>LT</code>, <code>GT</code>, <code>LTE</code>,
and <code>GTE</code> are also defined. Some synonyms are also
defined. The <em>hashing</em> operator is called
<code>HASH-CODE</code>.
</p>
<p>
The <em>comparison</em> operator returns one of four values: the
symbols <code><</code>, <code>></code>, <code>=</code>, or
<code>/=</code>. The intent of such definition is to make it
usable in conjunction with <code>case</code>, <code>ccase</code>, and
<code>ecase</code>; also, its intent is to make it possible to capture
<em>partial orders</em> among objects in a set.
</p>
<h1>Equality and Comparison Dictionary</h1>
<h2>Standard Generic Function <code>EQUALS</code></h2>
<h3>Syntax:</h3>
<dl>
<dt> <code>EQUALS</code> <i>a</i> <i>b</i>
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code>
→ <i>result</i></p></dt>
</dl>
<p><b>Note:</b> Maybe it would make sense to supply a
\<code>:key</code> parameter (defaulting to <code>identity</code>) as
well.</p>
<h3>Known Method Signatures:</h3>
<dl>
<dt> <code>EQUALS</code> (<i>a</i> <code>T</code>) (<i>b</i> <code>T</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code>
<dt> <code>EQUALS</code> (<i>a</i> <code>number</code>) (<i>b</i> <code>number</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code>
<dt> <code>EQUALS</code> (<i>a</i> <code>cons</code>) (<i>b</i> <code>cons</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code>
<dt> <code>EQUALS</code> (<i>a</i> <code>character</code>) (<i>b</i> <code>character</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <i>case-sensitive-p</i> <code>&allow-other-keys</code>
<dt> <code>EQUALS</code> (<i>a</i> <code>string</code>) (<i>b</i> <code>string</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <i>case-sensitive-p</i> <code>&allow-other-keys</code>
<dt> <code>EQUALS</code> (<i>a</i> <code>array</code>) (<i>b</i> <code>array</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code>
<dt> <code>EQUALS</code> (<i>a</i> <code>hash-table</code>) (<i>b</i> <code>hash-table</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code>
<i>recursive-p</i>
(<i>by-key</i> <code>t</code>)
(<i>by-value</i> <code>t</code>)
(<i>check-properties</i> <code>t</code>)
<code>&allow-other-keys</code>
</dl>
<h3>Arguments and Values:</h3>
<dl>
<dt><i>a</i> <i>b</i> -- <strong>Common Lisp</strong> objects.
<dt><i>recursive-p</i> -- a <em>generalized boolean</em>; default is <code>NIL</code>.
<dt><i>result</i> -- a <code>boolean</code>.
<dt><i>keys</i> -- a <code>list</code> (as per the usual behavior).
<dt><i>by-key</i> -- a <em>generalized boolean</em>; default is <code>T</code>.
<dt><i>by-values</i> -- a <em>generalized boolean</em>; default is <code>T</code>.
<dt><i>check-properties</i> -- a <em>generalized boolean</em>; default is <code>NIL</code>.
<dt><i>case-sensitive-p</i> -- a <em>generalized boolean</em>; default is <code>T</code>.
</dl>
<h3>Description:</h3>
<p>The <code>EQUALS</code> generic functions defines methods to test for
"equality" of two objects <i>a</i> and <i>b</i>. When two
objects <i>a</i> and <i>b</i> are <code>EQUALS</code> under an
appropriate and context-dependent notion of "equality", then the
function returns <code>T</code> as <i>result</i>; otherwise <code>EQUALS</code>
returns <code>NIL</code> as <i>result</i>.</p>
<p>If the optional argument <i>recursive-p</i> is <code>T</code>, then
<code>EQUALS</code> <em>may</em> recurse down the "structure" of <i>a</i>
and <i>b</i>. The description of each known method contains the
relevant information about its <i>recursive-p</i> dependent
behavior.</p>
<p><code>EQUALS</code> provides some default behavior, but it is intended mostly
as a hook for users. As such, it is allowed to add keyword arguments
to user-defined <code>EQUALS</code> methods, as the <code>&key</code> and
<code>&allow-other-keys</code> lambda-list markers imply.</p>
<h4>Known Method Descriptions:</h4>
<p>The following are the descriptions of <code>EQUALS</code> known methods;
unless explicitely mentioned <i>recursive-p</i> and <i>keys</i>
are to be considered as <code>ignore</code>ed.
<dl>
<dt> <code>EQUALS</code> (<i>a</i> <code>T</code>) (<i>a</i> <code>T</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code>
<dd><p>The default behavior for two objects <i>a</i> and <i>b</i> of
type/class <code>T</code> is to fall back on the
function <code>equalp</code>.
</dd>
</dt>
<dt> <code>EQUALS</code> (<i>a</i> <code>number</code>) (<i>a</i> <code>number</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code>
<dd><p>The default behavior for two objects <i>a</i> and <i>b</i> of
type/class <code>number</code> is to bypass <code>equalp</code> and to fall back
directly on the function <code>=</code><br />
<b>Note:</b> it may be
worthwhile to add a <code>:epsilon</code> keyword describing the tolerance
of the equality test and other keys describing the "nearing"
direction (<b>Subnote:</b> must check the correct numerics
terminology.)
</dd>
</dt>
<dt> <code>EQUALS</code> (<i>a</i> <code>cons</code>) (<i>a</i> <code>cons</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code>
<dd><p>The default behavior for two objects <i>a</i> and <i>b</i> of
type/class <code>cons</code> is to call the function <code>tree-equal</code>
with <code>EQUALS</code> as \<code>:test</code>.
</dd>
</dt>
<dt> <code>EQUALS</code> (<i>a</i> <code>character</code>) (<i>a</i> <code>character</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code>
<i>recursive-p</i>
(<i>case-sensitive-p</i> <code>T</code>)
<code>&allow-other-keys</code>
<dd><p>The behavior for two <code>character</code> objects depends on the value of
the keyword parameter <i>recursive-p</i> <i>case-sensitive-p</i>: if non-<code>NIL</code> (the
default) then the test uses <code>char=</code>,
otherwise <code>char-equal</code>.
</dd>
</dt>
<dt> <code>EQUALS</code> (<i>a</i> <code>string</code>) (<i>a</i> <code>string</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code>
<i>recursive-p</i>
(<i>case-sensitive-p</i> <code>T</code>)
<code>&allow-other-keys</code>
<dd><p>The behavior for two <code>string</code> objects depends on the value of
the keyword parameter <i>case-sensitive-p</i>: if non-<code>NIL</code> (the
default) then the test uses <code>string=</code>,
otherwise <code>string-equal</code>.
</dd>
</dt>
<dt> <code>EQUALS</code> (<i>a</i> <code>array</code>) (<i>a</i> <code>array</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code>
<dd><p>The default behavior for two objects <i>a</i> and <i>b</i> of
type/class <code>array</code> is to call <code>EQUALS</code> element-wise, as per
<code>equalp</code>. The <i>recursive-p</i> argument is passed
unmodified in each element-wise call to <code>EQUALS</code>.</p>
<p><b>Example:</b> the following may be an implementation of
<code>EQUALS</code> on <code>array</code>s (modulo "active elements",
fill-pointers and other details).
<pre>
(defmethod equals ((a array) (b array)
&rest keys
&key recursive-p &allow-other-keys)
(let ((a-ts (array-total-size a))
(b-ts (array-total-size b))
)
(when (/= a-ts b-ts) (return-from equiv nil))
(loop for i from 0 below a-ts
always (apply #'equiv (row-major-aref a i)
(row-major-aref b i)
recursive-p
keys))
))
</pre>
</dd>
</dt>
<dt> <code>EQUALS</code> (<i>a</i> <code>structure-object</code>) (<i>a</i> <code>structure-object</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code>
<dd><p>The <code>EQUALS</code> default behaviour for two <code>structure-object</code>s
is to fall back on <code>equalp</code></p>
<p><b>Note:</b> an alternative choice would be to fall back on <code>eq</code>.</p>
<p>In this case a Java (or C++) programmer may find the connection
more immediate, as this would make the behavior of <code>EQUALS</code>
similar to the default <code>java.lang.Object equals</code> method.</p>
<p>Another reason to fall back on <code>eq</code> would be to make the
behavior between the treatment of <code>structure-object</code>s and
<code>standard-object</code>s uniform.</p>
</dd>
</dt>
<dt> <code>EQUALS</code> (<i>a</i> <code>standard-object</code>) (<i>a</i> <code>standard-object</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code>
<dd><p>The <code>EQUALS</code> default behaviour for two <code>standard-object</code>s
is to fall back on <code>eq</code>.</p>
</dd>
</dt>
<dt> <code>EQUALS</code> (<i>a</i> <code>hash-table</code>) (<i>a</i> <code>hash-table</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code>
<i>recursive-p</i>
(<i>by-key</i> <code>t</code>)
(<i>by-value</i> <code>t</code>)
(<i>check-properties</i> <code>t</code>)
<code>&allow-other-keys</code>
<dd><p>The <code>EQUALS</code> default behaviour for
two <code>hash-table</code> object is the following. If <i>a</i>
and <i>b</i> are <code>eq</code>, the <i>result</i>
is <code>T</code>. Otherwise, first it is checked that the two
hash-tables have the same number of entries, then three tests are
performed "in parallel".
<ol>
<li>if <i>by-key</i> is non-<code>NIL</code> then the <em>keys</em> of the
<i>a</i> and <i>b</i> are compared with <code>EQUALS</code> (with
<i>recursive-p</i> passed as-is). The semantics of this test
are as if the following code were executed
<pre>
(loop for k1 in (ht-keys a)
for k2 in (ht-keys b)
always (equiv k1 k2 recursive-p))
</pre>
If <i>by-key</i> is <code>NIL</code>, the subtest is true.
</li>
<li> if <i>by-value</i> is non-<code>NIL</code> then the <em>values</em> of the
<i>a</i> and <i>b</i> are compared with <code>EQUALS</code> (with
<i>recursive-p</i> passed as-is). The semantics of this test
are as if the following code were executed
<pre>
(loop for v1 in (ht-values a)
for v2 in (ht-values b)
always (equiv v1 v2 recursive-p))
</pre>
If <i>by-value</i> is <code>NIL</code>, the subtest is true.
</li>
<li> if <i>check-properties</i> is non-<code>NIL</code> then all the
standard hash-table properties are checked for equality using
<code>eql</code>, <code>=</code>, or <code>null</code> as needed.
Implementation-dependent properties are checked accordingly.
If <i>check-properties</i> is <code>NIL</code>, the subtest is true.
</li>
</ol>
<i>result</i> is computed as the conjunction of the previous subtests.
</dd>
</dt>
</dl>
<p><b>Synonyms:</b> the name <code>EQUALS</code> is Latin for "equal"; of
course, this may not be the best name for a <strong>Common Lisp</strong> function; some
synonims may be the symbol <code>==</code> or
<code>EQUIV</code>. In general, synonyms should be defined by setting their
<code>fdefinition</code> to <code>(symbol-function 'equals)</code>.
</p>
<h3>Examples:</h3>
<pre>
cl-prompt> <b>(equals 42 42)</b>
<i>T</i>
cl-prompt> <b>(equals 42 'a)</b>
<i>NIL</i>
cl-prompt> <b>(equals "abc" "abc")</b>
<i>T</i>
cl-prompt> <b>(equals (make-hash-table) (make-hash-table))</b>
<i>T</i>
cl-prompt> <b>(equals "FOO" "Foo")</b>
<i>T</i>
cl-prompt> <b>(equals "FOO" "Foo" :case-sensitive-p nil)</b>
<i>NIL</i>
cl-prompt> <b>(defstruct foo a s d)</b>
<i>FOO</i>
cl-prompt> <b>(equals (make-foo :a 42 :d "a string")
(make-foo :a 42 :d "a string"))</b>
<i>NIL</i> ; If falling back on EQUALP. <i>T</i> if falling back on EQ.
cl-prompt> <b>(equals (make-foo :a 42 :d "a bar")
(make-foo :a 42 :d "a baz"))</b>
<i>NIL</i>
cl-prompt> <b>(defmethod equals ((a foo) (b foo)
&key (recursive-p t)
&allow-other-keys)
(declare (ignore recursive-p))
(or (eq a b)
(= (foo-a a) (foo-a b))))</b>
<i>#<STANDARD METHOD equals (FOO FOO)></i>
cl-prompt> <b>(equals (make-foo :a 42 :d "a bar")
(make-foo :a 42 :d "a baz"))</b>
<i>T</i>
</pre>
<h3>Side Effects:</h3>
<p>
None.
<h3>Affected By:</h3>
<p>
TBD.
<h3>Exceptional Situations:</h3>
<p>
TBD.
<h2>Standard Generic Function <code>COMPARE</code></h2>
<h3>Syntax:</h3>
<dl>
<dt> <code>COMPARE</code> <i>a</i> <i>b</i>
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code> →
<i>result</i>
</dt>
</dl>
<h3>Known Method Signatures:</h3>
<dl>
<dt> <code>COMPARE</code> (<i>a</i> <code>T</code>) (<i>a</i> <code>T</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i>
<code>&allow-other-keys</code>
</dt>
<dt> <code>COMPARE</code> (<i>a</i> <code>number</code>) (<i>a</i> <code>number</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i>
<code>&allow-other-keys</code>
</dt>
<dt> <code>COMPARE</code> (<i>a</i> <code>character</code>) (<i>a</i> <code>character</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code>
<i>recursive-p</i>
(<i>case-sensitive-p</i> NIL)
<code>&allow-other-keys</code>
</dt>
<dt> <code>COMPARE</code> (<i>a</i> <code>string</code>) (<i>a</i> <code>string</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code>
<i>recursive-p</i>
(<i>case-sensitive-p</i> NIL)
<code>&allow-other-keys</code>
</dt>
<dt> <code>COMPARE</code> (<i>a</i> <code>symbol</code>) (<i>a</i> <code>symbol</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i>
<code>&allow-other-keys</code>
</dt>
</dl>
<h3>Arguments and Values:</h3>
<dl>
<dt><i>a</i> <i>b</i> -- <strong>Common Lisp</strong> objects.
<dt><i>recursive-p</i> -- a <em>generalized boolean</em>; default is <code>NIL</code>.
<dt><i>result</i> -- a <code>symbol</code> of type <code>(member < > = /=)</code>.
<dt><i>keys</i> -- a <code>list</code> (as per the usual behavior).
<dt><i>case-sensitive-p</i> -- a <em>generalized boolean</em>; default is <code>T</code>.
</dl>
<h3>Description:</h3>
<p>The generic function <code>COMPARE</code> defines
methods to test the <em>ordering</em> of two objects <i>a</i> and
<i>b</i>, if such order exists. The <i>result</i> value returned
by <code>COMPARE</code> is one of the four symbols: \texttt{<}, \texttt{>},
\texttt{=}, or \texttt{/=}. The <code>COMPARE</code> function returns
<code>/=</code> as <i>result</i> by default; thus it can represent
<em>partial orders</em> among objects. The equality tests should be
coherent with what the generic function <code>EQUALS</code> does.</p>
<p>If the optional argument <i>recursive-p</i> is <code>T</code>, then
<code>COMPARE</code> <em>may</em> recurse down the "structure" of <i>a</i>
and <i>b</i>. The description of each known method contains the
relevant information about its <i>recursive-p</i> dependent
behavior.
</p>
<h4>Known Methods Descriptions:</h4>
<dl>
<dt> <code>COMPARE</code> (<i>a</i> <code>T</code>) (<i>a</i> <code>T</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i>
<code>&allow-other-keys</code>
<dd><p>The default behavior for <code>COMPARE</code> when applied to two objects
<i>a</i> and <i>b</i> of "generic" type/class is to return the
symbol <code>/=</code> as <i>result</i>. The intended meaning is to
signal the fact that no ordering relation is known among them.</p>
</dd>
</dt>
<dt> <code>COMPARE</code> (<i>a</i> <code>number</code>) (<i>a</i> <code>number</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i>
<code>&allow-other-keys</code>
<dd><p>The default behavior for two objects <i>a</i> and <i>b</i> of
type/class <code>number</code> is to compute <i>result</i> according to
the standard predicates <code><</code>, <code>></code>,
and <code>=</code>.
</dd>
</dt>
<dt> <code>COMPARE</code> (<i>a</i> <code>character</code>) (<i>a</i> <code>character</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code>
<i>recursive-p</i>
(<i>case-sensitive-p</i> NIL)
<code>&allow-other-keys</code>
<dd><p>The behavior for two <code>string</code> objects depends on
the value of the keyword parameter <i>case-sensitive-p</i>: if
non-<code>NIL</code> (the default) then the test
uses <code>string<</code>, <code>string></code>,
and <code>string=</code> to compute <i>result</i>; otherwise
it uses <code>string-lessp</code>, <code>string-greaterp</code>,
and <code>string-equal</code>.</p>
</dd>
</dt>
<dt> <code>COMPARE</code> (<i>a</i> <code>string</code>) (<i>a</i> <code>string</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code>
<i>recursive-p</i>
(<i>case-sensitive-p</i> NIL)
<code>&allow-other-keys</code>
<dd><p>The behavior for two <code>string</code> objects depends on the value of
the keyword parameter <i>case-sensitive-p</i>: if non-<code>NIL</code> (the
default) then the test
uses <code>string</code>, <code>string></code>,
and <code>string=</code> to compute <i>result</i>; otherwise
it
uses <code>string-lessp</code>, <code>string-greaterp</code>,
and <code>string-equal</code>.</p>
</dd>
</dt>
<dt> <code>COMPARE</code> (<i>a</i> <code>symbol</code>) (<i>a</i> <code>symbol</code>)
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i>
<code>&allow-other-keys</code></dt>
<dd><p>When called with two <code>symbol</code>s, the method returns <code>=</code> if
<i>a</i> and <i>b</i> are <code>eq</code>, otherwise it
returns <code>/=</code>.</p>
</dd>
</dt>
</dl>
<h3>Examples:</h3>
<pre>
cl-prompt> <b>(compare 42 0)</b>
<i>></i>
cl-prompt> <b>(compare 42 1024)</b>
<i><</i>
cl-prompt> <b>(compare pi pi)</b>
<i>=</i>
cl-prompt> <b>(compare pi 3.0s0)</b>
<i>></i>
cl-prompt> <b>(compare 'this-symbol 'this-symbol)</b>
<i>=</i>
cl-prompt> <b>(compare 'this-symbol 'that-symbol)</b>
<i>/=</i>
cl-prompt> <b>(compare '(q w e r t y) '(q w e r t y))</b>
<i>=</i>
cl-prompt> <b>(compare #(q w e r t y) #(q w e r t y 42))</b>
<i>/=</i>
cl-prompt> <b>(compare "asd" "asd")</b>
<i>=</i>
cl-prompt> <b>(compare "asd" "ASD")</b>
<i>></i>
cl-prompt> <b>(compare "asd" "ASD" t :case-sensitive-p nil)</b>
<i>=</i>
cl-prompt> <b>(defstruct foo a s d)</b>
<i>FOO</i>
cl-prompt> <b>(compare (make-foo :a 42) (make-foo :a 42))</b>
<i>/=</i>
cl-prompt> <b>(defmethod compare ((a foo) (b foo)
&rest keys
&key recursive-p &allow-other-keys)
(let ((d-r (apply #'compare (foo-d a) (foo-d b) keys))
(a-r (apply #'compare (foo-a a) (foo-a b) keys))
)
(if (eq d-r a-r) d-r '/=)))</b>
<i>#<STANDARD METHOD compare (FOO FOO)></i>
cl-prompt> <b>(compare (make-foo :a 0 :d "I am a FOO")
(make-foo :a 42 :d "I am a foo"))</b>
<i>/=</i>
cl-prompt> <b>(compare (make-foo :a 0 :d "I am a FOO")
(make-foo :a 42 :d "I am a foo")
:case-sensitive-p nil)</b>
<i><</i>
cl-prompt> <b>(compare (make-array 3 :initial-element 0)
(vector 1 2 42))</b>
Error: Uncomparable objects #(0 0 0) and #(1 2 42).
</pre>
<h2>Functions <code>LT</code>, <code>LTE</code>, <code>GT</code>, and <code>GTE</code></h2>
<h3>Syntax:</h3>
<dl>
<dt> <code>LT</code> <i>a</i> <i>b</i>
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code> →
<i>result</i>
</dt>
<dt> <code>LTE</code> <i>a</i> <i>b</i>
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code> →
<i>result</i>
</dt>
<dt> <code>GT</code> <i>a</i> <i>b</i>
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code> →
<i>result</i>
</dt>
<dt> <code>GTE</code> <i>a</i> <i>b</i>
<code>&rest</code> <i>keys</i>
<code>&key</code> <i>recursive-p</i> <code>&allow-other-keys</code> →
<i>result</i>
</dt>
</dl>
<p><b>Synonyms:</b> the full-name synonyms <code>lessp</code>,
<code>not-greaterp</code>, <code>greaterp</code>, and <code>not-lessp</code> are
provided s well. Their implementation should be based on setting the
relevant <code>fdefinition</code>.
<h3>Description:</h3>
<p>The functions <code>LT</code>, <code>LTE</code>, <code>GT</code>,
and <code>GTE</code> are shorthands for calls
to <code>COMPARE</code>. Each one calls <code>COMPARE</code> as
<pre>
(apply #'compare a b keys)
</pre>
The appropriate result is returned when <code>COMPARE</code>, on its turn,
returns <code><</code>, <code>></code>, or <code>=</code>. If compare returns
<code>/=</code>, then no ordering relation can be
established, and the
functions <code>LT</code>, <code>LTE</code>, <code>GT</code>,
and <code>GTE</code>
signal an error.<br />
<b>Note:</b> decide which error.</p>
<p>If the keyword argument <i>recursive-p</i> is <code>T</code>, then
<code>EQUALS</code> <em>may</em> recurse down the "structure" of <i>a</i>
and <i>b</i>. The description of each known method contains the
relevant information about its <i>recursive-p</i> dependent
behavior.</p>
<h3>Examples:</h3>
<pre>
cl-prompt> <b>(lt 42 0)</b>
<i>NIL</i>
cl-prompt> <b>(lt 42 1024)</b>
<i>T</i>
cl-prompt> <b>(gte pi pi)</b>
<i>T</i>
cl-prompt> <b>(greaterp pi 3.0s0)</b>
<i>T</i>
cl-prompt> <b>(lt "asd" "asd")</b>
<i>NIL</i>
cl-prompt> <b>(lte "asd" "ASD")</b>
<i>NIL</i>
cl-prompt> <b>(lte "asd" "ASD" :case-sensitive-p nil)</b>
<i>T</i>
cl-prompt> <b>(defstruct foo a s d)</b>
<i>FOO</i>
cl-prompt> <b>(defmethod compare ((a foo) (b foo)
&rest keys
&key recursive-p &allow-other-keys)
(let ((d-r (apply #'compare (foo-d a) (foo-d b) keys))
(a-r (apply #'compare (foo-a a) (foo-a b) keys))
)
(if (eq d-r a-r) d-r '/=)))</b>
<i>#<STANDARD METHOD compare (FOO FOO)></i>
cl-prompt> <b>(lte (make-foo :a 0 :d "I am a FOO")
(make-foo :a 42 :d "I am a foo"))</b>
Error: Uncomparable objects
#S(FOO :a 0 :s NIL :d "I am a FOO") and
#S(FOO :a 0 :s NIL :d "I am a foo")
cl-prompt> <b>(lte (make-foo :a 0 :d "I am a FOO")
(make-foo :a 42 :d "I am a foo")
:case-sensitive-p nil) </b>
<i><</i>
cl-prompt> <b>(lte (make-array 3 :initial-element 0)
(vector 1 2 42)) </b>
Error: Uncomparable objects #(0 0 0) and #(1 2 42).
</pre>
<h3>Side Effects:</h3>
<p>
None.
<h3>Affected By:</h3>
<p>
TBD.
<h3>Exceptional Situations:</h3>
<p>
An "error" is signalled when called on a pair of objects for which
no predicate is defined (which is like what happens for undefined
methods).
<h2>Standard Generic Function <code>HASH-CODE</code></h2>
<h3>Syntax:</h3>
<dl>
<dt> <code>HASH-CODE</code> <i>a</i> → <i>result</i> </dt>
</dl>
<h3>Known Method Signatures:</h3>
<dl>
<dt> <code>HASH-CODE</code> (<i>a</i> <code>T</code>)</dt>
</dl>
<h3>Arguments and Values:</h3>
<dl>
<dt><i>a</i> -- a <strong>Common Lisp</strong> object.</dt>
<dt><i>result</i> -- a positive fixnum in the range <code>(mod
array-total-size-limit)</code>.</dt>
</dl>
<h3>Description:</h3>
<p>The <code>HASH-CODE</code> generic function is provided as a companion
to <code>EQUALS</code> for the benefit of those <strong>Common
Lisp</strong> implementations that provide a handle on the inner
working of hash tables (usually in the form of an extra
<code>:sxhash</code> or <code>:hash-function</code> keyword argument
to <code>make-hash-table</code>), or for bottom-up hash table
implementations.</p>
<p><code>HASH-CODE</code> is modeled after the Java
<code>hashCode()</code> method of <code>java.lang.Object</code>.
The same description applies almost unchanged.</p>
<p>The general contract of <code>HASH-CODE</code> is the following.
<ul>
<li>Whenever it is invoked on the same object more than once during
an a <strong>Common Lisp</strong> session, the
<code>HASH-CODE</code> generic function must consistently return
the same fixnum, provided no information used in
<code>EQUALS</code> comparisons on the object <i>a</i> is
modified. This integer need not remain consistent from one
<strong>Common Lisp</strong> session to another.</li>
<li>If two objects are equal according to the <code>EQUALS</code> generic
predicate, then calling the <code>HASH-CODE</code> generic function
on each of the two objects must produce the same integer
result.</li>
<li>It is not required that if two objects are unequal according to
the <code>EQUALS</code> generic predicate, then calling the
<code>HASH-CODE</code> generic function on each of the two objects
must produce distinct integer
results. However, the programmer should be aware that producing
distinct integer results for unequal objects may improve the
performance of hashtables.</li>
</ul>
<h4>Known Method Descriptions:</h4>
<dl>
<dt><code>HASH-CODE</code> (<i>a</i> <code>T</code>)
<dd> The only method defined for <code>HASH-CODE</code> is the
default one, which simply resolves to a call to
<code>sxhash</code>. An implementation of the method can be:
<pre>
(defmethod <code>HASH-CODE</code> ((a T)) (sxhash a))
</pre>
</dd>
</dl>
<h3>Examples:</h3>
<p>None.
<h3>Notes:</h3>
<p>The implementation of <code>HASH-CODE</code> should coordinate with that of
<code>EQUALS</code>. In particular, Section 18.1.2 ``Modifying Hash Table Keys''
of [ANSIHyperSpec] and the definiton of <code>sxhash</code> in the same
document should be taken into consideration.
<h3>Side Effects:</h3>
<p>
None.
<h3>Affected By:</h3>
<p>
The actual implementation of the <code>EQUALS</code> methods.
<h3>Exceptional Situations:</h3>
<p>
TBD.
<h1>References</h1>
<dl>
<dt><a name="KMPcmp">[KMP97]</a>
K. M. Pitman, <i>The Best of Intentions: EQUAL Rights -- and Wrongs -- in Lisp</i></dt>
<dd>published online
at <a href="http://www.nhplace.com/kent/PS/EQUAL.html"><tt>http://www.nhplace.com/kent/PS/EQUAL.html</tt></a>,
1997.
</dd>
<dt><a name="ANSIHyperSpec">[ANSISpec]</a>
<i>The <strong>Common Lisp</strong> Hyperspec,</i></dt>
<dd>published online at
<a href="http://www.lisp.org/HyperSpec/FrontMatter/index.html"><tt>http://www.lisp.org/HyperSpec/FrontMatter/index.html</tt></a>, 1994.
</dl>
<h1>License</h1>
<p>
This document is put in the public-domain.
</body>
</html>
<!-- end of file : cleqcmp.html -->