When I try to use structs with cycles as keys in hash tables
with :test #'equalp , clisp dies a horrible death. I can't find a
mention of this topic in the HS. Cycles ought to be manageable by
equalp. Any insights?
I'm running Windows lispbox 0.7, with clisp-2.37-win32-pc386.
From: Robert Maas, see http://tinyurl.com/uh3t
Subject: Re: Equalp on cycles
Date:
Message-ID: <rem-2008apr08-001@yahoo.com>
> From: Gene <············@gmail.com>
> When I try to use structs with cycles as keys in hash tables with
> :test #'equalp , clisp dies a horrible death. I can't find a
> mention of this topic in the HS.
See later for my idea to try.
> Cycles ought to be manageable by equalp.
Who says??? I see no reason whatsoever that equalp should "work"
for circular lists.
Now for my idea: Convert each structure to a string by printing it
to a string-output-stream with *print-circle* true.
(You probably also want *print-pretty* false.)
Then hash on the resultant strings, using #'equal as the test.
I'm curious if this will suffice for your needs.
Gene <············@gmail.com> writes:
> When I try to use structs with cycles as keys in hash tables
> with :test #'equalp , clisp dies a horrible death. I can't find a
> mention of this topic in the HS. Cycles ought to be manageable by
> equalp. Any insights?
Unlike for EQUAL, struct comparison under EQUALP works by comparing
the components recursively. Ignoring hash tables, I don't even know
that EQUALP itself is going to win on such things.
In functions like EQUALP, where you're going to recursively descend
them, if there's no mention of a need for the implementation to do a
circularity check, I'm hard-pressed to think you can depend on one.
> I'm running Windows lispbox 0.7, with clisp-2.37-win32-pc386.
It's generally good to include such information when reporting issues
like this, but in this case I somehow doubt this matters.
FWIW, LispWorks for Windows 5.0.1 (Personal) also doesn't let you
use EQUALP on circular structures.
CL-USER 1 > (defstruct kons kar kdr)
KONS
CL-USER 2 > (setq *print-circle* t)
T
CL-USER 3 > #1=#S(KONS KAR NIL KDR #1#)
#1=#S(KONS :KAR NIL :KDR #1#)
CL-USER 4 > (setq foo *)
#1=#S(KONS :KAR NIL :KDR #1#)
CL-USER 5 > (setq bar #1=#S(KONS KAR NIL KDR #1#))
#1=#S(KONS :KAR NIL :KDR #1#)
CL-USER 6 > (equalp foo bar)
Stack overflow (stack size 16000).
Gene wrote:
> When I try to use structs with cycles as keys in hash tables
> with :test #'equalp , clisp dies a horrible death. I can't find a
> mention of this topic in the HS. Cycles ought to be manageable by
> equalp. Any insights?
Predefined comparison operators are problematic in the general case. Eq
and eql test for (conceptual) object identity, which is pretty
straightforward. Equal and equalp can already become problematic. The
HyperSpec is actually very clear about this: "Object equality is not a
concept for which there is a uniquely determined correct algorithm. The
appropriateness of an equality predicate can be judged only in the
context of the needs of some particular program. Although these
functions take any type of argument and their names sound very generic,
equal and equalp are not appropriate for every application."
In the general case, you should better define your own comparison functions.
See also http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.3068
which is an excellent paper about that topic.
Pascal
--
1st European Lisp Symposium (ELS'08)
http://prog.vub.ac.be/~pcostanza/els08/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza <··@p-cos.net> wrote on Wed, 09 Apr 2008:
> HyperSpec is actually very clear about this: "Object equality is not a
> concept for which there is a uniquely determined correct algorithm.
[...]
> In the general case, you should better define your own comparison functions.
Yeah, yeah, sure. But then you run into the problem that hash tables aren't
required to work with user-defined comparison functions. So now you have to
rewrite all the hash table code too...
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
Puritanism: The haunting fear that someone, somewhere, may be happy.
-- H. L. Mencken
Don Geddis wrote:
> Pascal Costanza <··@p-cos.net> wrote on Wed, 09 Apr 2008:
>> HyperSpec is actually very clear about this: "Object equality is not a
>> concept for which there is a uniquely determined correct algorithm.
> [...]
>> In the general case, you should better define your own comparison functions.
>
> Yeah, yeah, sure. But then you run into the problem that hash tables aren't
> required to work with user-defined comparison functions. So now you have to
> rewrite all the hash table code too...
Are there any current lisp implementations which don't allow for a user
defined hash function? Lispworks, Allegro, CMUCL, SBCL, and Clisp all
allow for user defined hash functions.
Gene <············@gmail.com> writes:
> When I try to use structs with cycles as keys in hash tables
> with :test #'equalp , clisp dies a horrible death. I can't find a
> mention of this topic in the HS. Cycles ought to be manageable by
> equalp. Any insights?
>
> I'm running Windows lispbox 0.7, with clisp-2.37-win32-pc386.
Well, EQUALP is not specified to deal with cycles (in general, few CL
functions are, they usually work on proper-list (and only "by
accident" may work on circular or dotted lists, that is, as long as
you don't loop the cycle or reach the dot)).
But you're right, this is something that is manageable. Only you will
have to manage it yourself.
While detection of a cycle in a list is easy, it will be harder to do
while comparing _two_ trees. And you'll have to implement your
equal-modulo-cycles-p function for all data types that may appear
(lists, vectors, arrays, objects, etc) in your structures.
Some interesting cases:
(equal-modulo-cycles-p '#1=(a b c a b c a b c . #1#) '#2=(a b c . #2#))
(equal-modulo-cycles-p '#1=(a b c a b c a b c . #2#) '#2=(a b c . #1#))
--
__Pascal Bourguignon__