re: Issue: EQUAL-STRUCTURE (Version 5)

[masinter.pa@Xerox.COM]

You've uncovered an ambiguity in the spec for EQUALP that I
hadn't thought of before. I think your analysis points out that
EQUALP's description should mention HASH-TABLEs as a
 special case. There are three possibilities: (1) EQUALP uses EQ
on hash tables, (2) EQUALP descends hash tables, (3) it isn't
specified. If EQUALP were to descend hash tables, we'd have
to say how: I'd guess that you'd have to compare the set of
keys using the hash table test function, and then the values
corresponding to the keys using EQUALP. I like specified better
than unspecified, and EQ better than descending.

(For the rest of cl-cleanup, the relevant part of Kim's message
is...


Date: Sun, 8 Jan 89 15:48:41 PST
 From: IIM%ECLA@ECLC.USC.EDU
Subject: re: Issue: EQUAL-STRUCTURE (Version 5)
To: masinter.pa
cc: IIM%ECLA@ECLC.USC.EDU
In-Reply-To: <890108-134500-3303@Xerox>


> Date: 8 Jan 89 13:44 PST
> From: masinter.pa@Xerox.COM
> 
> You're right. Can I talk you into helping draft a version that says what we
> mean? Kent and I are burned out on this issue, apparently. 
> 
> Preferably so we can have a version for voting on...
> Let me know one way or another asap.

Well, I'd like to help, but I have two serious problems.

First, I expect to have very little time to devote to X3J13 issues for the next
few weeks, other than attending the meeting and discussing things there, since
starting tomorrow I'm going to be embarking on a fairly major low-level change
in our implementation, the completion of which is on the critical path for the
completion of several other projects here.  I'm going to try to address as many
things as I can before I go home today (even if it means not leaving until
tomorrow) but after that I'm likely to be pretty unresponsive for a while.

Second, I'm really not certain myself what it is "we mean", much less what the
"right thing" is, so it's hard for me write it up.  The example problem I keep
having trouble with is hash-tables.  I can't think of any good reason why
EQUALP should specifically recognize them, yet I also think it has to.

Consider the following:
1. Given 2 EQ hash-tables H1 and H2
2. For some set of keys and associated values, install them in both H1 and H2,
   in the same order.
3. Invoke the garbage collector.  (I'm assuming that this will "invalidate" the
   hashing in the tables, requiring a rehash to occur on at least some
   operations.) 
4. Perform some operation on H1 which does not change the key mapping, but
   causes a rehash to occur due to the recent gc.

It is very likely that under a simple component-wise comparison, H1 and H2 are
now no longer equivelent.  Worse yet, I can readily construct situations in
multi-processing or interruptable environments in which a simple component-wise
comparison implementation of EQUALP will return false for (equalp x x), where x
is an eq hash-table.

So we have an existance proof of an ill-defined case.  I think you'll have a
hard time convincing me either that this is the only such case or that these
problems don't arise in "user code".  And it seems to me quite likely that the
set of problem cases will vary between implementations.  What do we do with
such things?  I'm afraid I don't have what I consider to be a good answer.  I
suppose we could punt by saying that EQUALP does component-wise comparisons
always, and add a caveat that this isn't necessarily useful or even "correct"
for some datatypes in some implementations.  I don't think we can say anything
about signaling errors in the bad cases, since if user-defined objects can have
these problems then there really isn't a way to detect when to signal.
Besides, I sort of dislike the idea of an equality predicate which signals
errors. 

kab
-------