195 lines
13 KiB
HTML
195 lines
13 KiB
HTML
|
<!-- Common Lisp HyperSpec (TM), version 7.0 generated by Kent M. Pitman on Mon, 11-Apr-2005 2:31am EDT -->
|
||
|
|
<HTML>
|
||
|
|
<HEAD>
|
||
|
|
<TITLE>CLHS: Issue SXHASH-DEFINITION Writeup</TITLE>
|
||
|
|
<LINK HREF="../Data/clhs.css" REL="stylesheet" TYPE="text/css" />
|
||
|
|
<META HTTP-EQUIV="Author" CONTENT="Kent M. Pitman">
|
||
|
|
<META HTTP-EQUIV="Organization" CONTENT="LispWorks Ltd.">
|
||
|
|
<LINK REL=TOP HREF="../Front/index.htm">
|
||
|
|
<LINK REL=COPYRIGHT HREF="../Front/Help.htm#Legal">
|
||
|
|
<LINK REL=DISCLAIMER HREF="../Front/Help.htm#Disclaimer">
|
||
|
|
<LINK REL=PREV HREF="../Issues/iss335_w.htm">
|
||
|
|
<LINK REL=UP HREF="../Issues/iss336.htm">
|
||
|
|
<LINK REL=NEXT HREF="../Issues/iss337_w.htm">
|
||
|
|
</HEAD>
|
||
|
|
<BODY>
|
||
|
|
<H1><A REV=MADE HREF="http://www.lispworks.com/"><IMG WIDTH=80 HEIGHT=65 ALT="[LISPWORKS]" SRC="../Graphics/LWSmall.gif" ALIGN=Bottom></A><A REL=TOP HREF="../Front/index.htm"><IMG WIDTH=237 HEIGHT=65 ALT="[Common Lisp HyperSpec (TM)]" SRC="../Graphics/CLHS_Sm.gif" ALIGN=Bottom></A> <A REL=PREV HREF="../Issues/iss335_w.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Previous]" SRC="../Graphics/Prev.gif" ALIGN=Bottom></A><A REL=UP HREF="../Issues/iss336.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Up]" SRC="../Graphics/Up.gif" ALIGN=Bottom></A><A REL=NEXT HREF="../Issues/iss337_w.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Next]" SRC="../Graphics/Next.gif" ALIGN=Bottom></A></H1>
|
||
|
|
|
||
|
|
<HR>
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
<H2>Issue SXHASH-DEFINITION Writeup</H2>
|
||
|
|
|
||
|
|
<PRE><B>Issue:</B> <A HREF="iss336.htm">SXHASH-DEFINITION</A><P>
|
||
|
|
<B>References:</B> <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A>, "similarity as constants"<P>
|
||
|
|
Related issues: <A HREF="iss081.htm">CONSTANT-COMPILABLE-TYPES</A><P>
|
||
|
|
<A HREF="iss063.htm">COMPILE-FILE-SYMBOL-HANDLING</A><P>
|
||
|
|
<A HREF="iss080.htm">CONSTANT-COLLAPSING</A><P>
|
||
|
|
<A HREF="iss187.htm">HASH-TABLE-KEY-MODIFICATION</A><P>
|
||
|
|
<B>Category:</B> CLARIFICATION, CHANGE<P>
|
||
|
|
<B>Edit history:</B> v1, 14 Feb 1991, Sandra Loosemore<P>
|
||
|
|
v2, 19 Feb 1991, Sandra Loosemore (comments from KAB)<P>
|
||
|
|
v3, 11 Mar 1991, Sandra Loosemore (additional proposals)<P>
|
||
|
|
v4, 13 Mar 1991, Sandra Loosemore (new proposal)<P>
|
||
|
|
v5, 26 Mar 1991, Sandra Loosemore (amendment from meeting)<P>
|
||
|
|
<B>Status:</B> v5 (proposal SIMILAR-FOR-SXHASH) accepted by X3J13, Mar 1991<P>
|
||
|
|
<P>
|
||
|
|
<B>Problem description:<P>
|
||
|
|
</B><P>
|
||
|
|
The definition of the <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> function is confusing. The relevant<P>
|
||
|
|
words from CLtL are:<P>
|
||
|
|
<P>
|
||
|
|
<A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> computes a hash code for an object and returns the hash<P>
|
||
|
|
code as a non-negative <A REL=DEFINITION HREF="../Body/t_fixnum.htm#fixnum"><B>fixnum</B></A>. A property of <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> is that<P>
|
||
|
|
(<A REL=DEFINITION HREF="../Body/f_equal.htm#equal"><B>EQUAL</B></A> <x> <y>) implies (= (<A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> <x>) (<A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> <y>)).<P>
|
||
|
|
<P>
|
||
|
|
The manner in which the hash code is computed is implementation-<P>
|
||
|
|
dependent but independent of the particular "incarnation" or "core<P>
|
||
|
|
image". Hash values produced by <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> may be written out to files,<P>
|
||
|
|
for example, and meaningfully read in again into an instance of the<P>
|
||
|
|
same implementation.<P>
|
||
|
|
<P>
|
||
|
|
Different people have different interpretations of what the second<P>
|
||
|
|
paragraph is trying to say.<P>
|
||
|
|
<P>
|
||
|
|
An additional problem is that the effects on <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> of destructive <P>
|
||
|
|
operations on the object are not well-specified. Issue <P>
|
||
|
|
<A HREF="iss187.htm">HASH-TABLE-KEY-MODIFICATION</A> dealt only with objects used as keys in <P>
|
||
|
|
hash tables, not with <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A>.<P>
|
||
|
|
<P>
|
||
|
|
<P>
|
||
|
|
<B>Proposal (SXHASH-DEFINITION:SIMILAR-FOR-SXHASH):<P>
|
||
|
|
</B><P>
|
||
|
|
Define <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> as a function with these properties:<P>
|
||
|
|
<P>
|
||
|
|
(1) The result is a non-negative <A REL=DEFINITION HREF="../Body/t_fixnum.htm#fixnum"><B>fixnum</B></A>.<P>
|
||
|
|
<P>
|
||
|
|
(2) (<A REL=DEFINITION HREF="../Body/f_equal.htm#equal"><B>EQUAL</B></A> x y) implies (= (<A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> x) (<A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> y)).<P>
|
||
|
|
<P>
|
||
|
|
(3) If x and y are "similar for SXHASH", then (<A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> x) and <P>
|
||
|
|
(<A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> y) return the same mathematical value even if x and y<P>
|
||
|
|
exist in different sessions of the same Lisp implementation.<P>
|
||
|
|
<P>
|
||
|
|
Objects are "similar for SXHASH" if they are of type string, <P>
|
||
|
|
<A REL=DEFINITION HREF="../Body/t_bt_vec.htm#bit-vector"><B>bit-vector</B></A>, character, cons, number, <A REL=DEFINITION HREF="../Body/a_pn.htm#pathname"><B>pathname</B></A> or symbol, and<P>
|
||
|
|
are "similar as constants".<P>
|
||
|
|
<P>
|
||
|
|
[This assumes that a bug in the specification of "similar as<P>
|
||
|
|
constants" for pathnames (from issue <A HREF="iss081.htm">CONSTANT-COMPILABLE-TYPES</A>) is<P>
|
||
|
|
going to be fixed by the editor. The problem is that the definition<P>
|
||
|
|
of "similar as constants" now implies that the <A REL=DEFINITION HREF="../Body/a_pn.htm#pathname"><B>pathname</B></A> components are<P>
|
||
|
|
recursively compared for being "similar as constants", while <A REL=DEFINITION HREF="../Body/f_equal.htm#equal"><B>EQUAL</B></A><P>
|
||
|
|
talks about components merely being "equivalent". If this change to<P>
|
||
|
|
"similar as constants" is not made, then the presentation of <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A><P>
|
||
|
|
must describe the relationship for pathnames separately, in a way that<P>
|
||
|
|
is compatible with <A REL=DEFINITION HREF="../Body/f_equal.htm#equal"><B>EQUAL</B></A>.]<P>
|
||
|
|
<P>
|
||
|
|
(4) The function is intended for hashing so implementations should<P>
|
||
|
|
return values well distributed within the range of non-negative<P>
|
||
|
|
fixnums.<P>
|
||
|
|
<P>
|
||
|
|
(5) The value returned by <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> on an object within a single session <P>
|
||
|
|
is constant provided that the object is not visibly modified with <P>
|
||
|
|
regard to the equivalence test <A REL=DEFINITION HREF="../Body/f_equal.htm#equal"><B>EQUAL</B></A> (as defined in proposal<P>
|
||
|
|
<A HREF="iss187.htm">HASH-TABLE-KEY-MODIFICATION:SPECIFY</A>).<P>
|
||
|
|
<P>
|
||
|
|
(6) <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> must terminate.<P>
|
||
|
|
<P>
|
||
|
|
<P>
|
||
|
|
<B>Implementation Notes:<P>
|
||
|
|
</B><P>
|
||
|
|
For objects of other types that <A REL=DEFINITION HREF="../Body/f_equal.htm#equal"><B>EQUAL</B></A> compares with <A REL=DEFINITION HREF="../Body/f_eq.htm#eq"><B>EQ</B></A>, item 5<P>
|
||
|
|
restricts <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> to assigning the hash code based on some immutable<P>
|
||
|
|
attribute of the identity of the object, such as its type. Another<P>
|
||
|
|
legitimate implementation technique would be to have <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> assign <P>
|
||
|
|
(and cache) a random hash code for these objects, since there is<P>
|
||
|
|
no requirement that "similar" but non-EQ objects have the same hash<P>
|
||
|
|
code.<P>
|
||
|
|
<P>
|
||
|
|
Although the "similar as constants" relationship on symbols is defined<P>
|
||
|
|
in terms of both the symbol's name and the packages it is accessible<P>
|
||
|
|
in, item 5 disallows using package information to compute the hash<P>
|
||
|
|
code, since changes to the package status of a symbol are not visible<P>
|
||
|
|
to <A REL=DEFINITION HREF="../Body/f_equal.htm#equal"><B>EQUAL</B></A>.<P>
|
||
|
|
<P>
|
||
|
|
<B>Rationale:<P>
|
||
|
|
</B><P>
|
||
|
|
This is probably what CLtL meant to say. Basically, what the proposal<P>
|
||
|
|
does is to combine the original definition of <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A>'s relationship<P>
|
||
|
|
with <A REL=DEFINITION HREF="../Body/f_equal.htm#equal"><B>EQUAL</B></A> with using "similar as constants" to compare objects that<P>
|
||
|
|
exist in different Lisp sessions. For types where <A REL=DEFINITION HREF="../Body/f_equal.htm#equal"><B>EQUAL</B></A> and "similar<P>
|
||
|
|
as constants" differ, or where "similar as constants" is not<P>
|
||
|
|
well-defined, the relationship between Lisp sessions is unspecified.<P>
|
||
|
|
<P>
|
||
|
|
<B>Current Practice:<P>
|
||
|
|
</B><P>
|
||
|
|
Unknown. In many implementations, the hash values returned by<P>
|
||
|
|
<A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> for objects of types that <A REL=DEFINITION HREF="../Body/f_equal.htm#equal"><B>EQUAL</B></A> compares with <A REL=DEFINITION HREF="../Body/f_eq.htm#eq"><B>EQ</B></A> are <P>
|
||
|
|
apparently based on the type of the object.<P>
|
||
|
|
<P>
|
||
|
|
JonL says he knows of at least one implementation that keeps a<P>
|
||
|
|
hash-number slot inside every stored object.<P>
|
||
|
|
<P>
|
||
|
|
<B>Cost to Implementors:<P>
|
||
|
|
</B><P>
|
||
|
|
Probably not too large.<P>
|
||
|
|
<P>
|
||
|
|
<B>Cost to Users:<P>
|
||
|
|
</B><P>
|
||
|
|
The current definition of <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> is pretty garbled and probably<P>
|
||
|
|
most uses of <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> do not depend on much more than the relationship to<P>
|
||
|
|
<A REL=DEFINITION HREF="../Body/f_equal.htm#equal"><B>EQUAL</B></A>. That relationship is preserved in proposal SIMILAR-FOR-SXHASH.<P>
|
||
|
|
<P>
|
||
|
|
Some users may have interpreted the read/print consistency language<P>
|
||
|
|
in CLtL to <A REL=DEFINITION HREF="../Body/f_provid.htm#require"><B>require</B></A> stricter behavior for <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> than is specified by<P>
|
||
|
|
the current proposal. For example, some uses of <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> might assume <P>
|
||
|
|
that arrays that are "similar" under read/print consistency have<P>
|
||
|
|
the same hash codes. These applications could break in implementations<P>
|
||
|
|
that choose to assign unique hash codes to non-EQ arrays.<P>
|
||
|
|
<P>
|
||
|
|
<B>Cost of non-adoption:<P>
|
||
|
|
</B><P>
|
||
|
|
The definition of <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> will continue to be garbled. <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> will<P>
|
||
|
|
be of limited usefulness.<P>
|
||
|
|
<P>
|
||
|
|
<B>Performance impact:<P>
|
||
|
|
</B><P>
|
||
|
|
Probably small.<P>
|
||
|
|
<P>
|
||
|
|
<B>Benefits:<P>
|
||
|
|
</B><P>
|
||
|
|
The cost of non-adoption is avoided.<P>
|
||
|
|
<P>
|
||
|
|
<B>Esthetics:<P>
|
||
|
|
</B><P>
|
||
|
|
Better than the way things are now.<P>
|
||
|
|
<P>
|
||
|
|
<B>Discussion:<P>
|
||
|
|
</B><P>
|
||
|
|
This issue was discussed briefly on the x3j13 mailing list in <P>
|
||
|
|
November 89, but not written up until now.<P>
|
||
|
|
<P>
|
||
|
|
There has been quite a bit of discussion about whether <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> should<P>
|
||
|
|
be required to "work" on circular objects. Some have argued that such<P>
|
||
|
|
a requirement would make it more useful, but others claim that it's<P>
|
||
|
|
pointless to make the requirement since <A REL=DEFINITION HREF="../Body/f_equal.htm#equal"><B>EQUAL</B></A> doesn't have to "work"<P>
|
||
|
|
on circular objects.<P>
|
||
|
|
<P>
|
||
|
|
Barrett says he is concerned about proposal SIMILAR-FOR-SXHASH <P>
|
||
|
|
potentially breaking applications that depend on <A REL=DEFINITION HREF="../Body/f_sxhash.htm#sxhash"><B>SXHASH</B></A> returning<P>
|
||
|
|
the same values for arrays, etc. that are "similar", but concludes<P>
|
||
|
|
that trying to specify what attributes of these objects might or might<P>
|
||
|
|
not be used to compute the hash value is probably not practical.<P>
|
||
|
|
<P>
|
||
|
|
Loosemore, Barrett, Moon, and MacLachlan have expressed agreement in<P>
|
||
|
|
principle with proposal SIMILAR-FOR-SXHASH.<P>
|
||
|
|
</PRE>
|
||
|
|
<HR>
|
||
|
|
|
||
|
|
<A REL=NAVIGATOR HREF="../Front/StartPts.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Starting Points]" SRC="../Graphics/StartPts.gif" ALIGN=Bottom></A><A REL=TOC HREF="../Front/Contents.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Contents]" SRC="../Graphics/Contents.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Master.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Index]" SRC="../Graphics/Index.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Symbol.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Symbols]" SRC="../Graphics/Symbols.gif" ALIGN=Bottom></A><A REL=GLOSSARY HREF="../Body/26_a.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Glossary]" SRC="../Graphics/Glossary.gif" ALIGN=Bottom></A><A HREF="../Front/X3J13Iss.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Issues]" SRC="../Graphics/Issues.gif" ALIGN=Bottom></A><BR>
|
||
|
|
|
||
|
|
<A REL=COPYRIGHT HREF="../Front/Help.htm#Legal"><I>Copyright 1996-2005, LispWorks Ltd. All rights reserved.</I></A><P>
|
||
|
|
</BODY>
|
||
|
|
</HTML>
|