Steel Bank Common Lisp

Joseph Kiniry writes:
> I'm porting an application (OBJ3) to CMUCL, SBCL, and CLISP.
> 
> I need a function that will define a total order on two arbitrary 
> structures.
> 
> In my other ports, I've used internal functions to get lists of slots, 
> orders on them, etc.
> 
> Do the CMUCL, SBCL, and CLISP developers have suggestions for 
> implementing such a function?  I've dug around the internal 
> functionality, but have not found an obvious solution to this problem.

Should this order be the same on all these implementations?
Should it be the same accross sessions?

In general for structures it's not possible, there's no reflectivity
of structures.  Either you limit yourself to the structure defined
with one of your macros that will keep the fields arround, or you'll
have to use CLOS.

Note that some structure types may be defined to be implemented with
lists or vectors!

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
The world will now reboot; don't bother saving your artefacts.

Hello,

Joseph Kiniry <kiniry@...> writes:

> I need a function that will define a total order on two arbitrary 
> structures.
>
> In my other ports, I've used internal functions to get lists of slots, 
> orders on them, etc.
>
> Do the CMUCL, SBCL, and CLISP developers have suggestions for 
> implementing such a function?  I've dug around the internal 
> functionality, but have not found an obvious solution to this
> problem.

Under SBCL you can get a list of slot descriptions with
  (sb-pcl:class-slots (sb-pcl:find-class <structure-name>))
Then use SB-PCL:SLOT-DEFINITION-... to get slot information.

-- 
Regards,
Alexey Dejneka

"Alas, the spheres of truth are less transparent than those of
illusion." -- L.E.J. Brouwer

Alexey Dejneka <adejneka@...> writes:

> Hello,
>
> Joseph Kiniry <kiniry@...> writes:
>
>> I need a function that will define a total order on two arbitrary 
>> structures.
>>
>> In my other ports, I've used internal functions to get lists of slots, 
>> orders on them, etc.
>>
>> Do the CMUCL, SBCL, and CLISP developers have suggestions for 
>> implementing such a function?  I've dug around the internal 
>> functionality, but have not found an obvious solution to this
>> problem.
>
> Under SBCL you can get a list of slot descriptions with
>   (sb-pcl:class-slots (sb-pcl:find-class <structure-name>))
> Then use SB-PCL:SLOT-DEFINITION-... to get slot information.

Would it be appropriate to suggest SB-INT:PSXHASH?  Values might not
be the same across sessions, but otherwise it seems to me that hash
values could generate a good approximation to a total order.

Cheers,

Christophe

Hi Christophe,

On 24 Nov, 2004, at 17:30, Christophe Rhodes wrote:

> Alexey Dejneka <adejneka@...> writes:
>
>> Hello,
>>
>> Joseph Kiniry <kiniry@...> writes:
>>
>>> I need a function that will define a total order on two arbitrary
>>> structures.
>>>
>>> In my other ports, I've used internal functions to get lists of 
>>> slots,
>>> orders on them, etc.
>>>
>>> Do the CMUCL, SBCL, and CLISP developers have suggestions for
>>> implementing such a function?  I've dug around the internal
>>> functionality, but have not found an obvious solution to this
>>> problem.
>>
>> Under SBCL you can get a list of slot descriptions with
>>   (sb-pcl:class-slots (sb-pcl:find-class <structure-name>))
>> Then use SB-PCL:SLOT-DEFINITION-... to get slot information.
>
> Would it be appropriate to suggest SB-INT:PSXHASH?  Values might not
> be the same across sessions, but otherwise it seems to me that hash
> values could generate a good approximation to a total order.

That is actually a very interesting idea.  This would only work though 
if hash orders were guaranteed consistent across garbage collections...

Joe

> * Joseph Kiniry <xvavel@...> [2004-11-24 19:21:33 +0000]:
>
> My concern was not knowing anything about the quality and completeness
> of CLOS/MOP implementations across CL platforms.

All implementations support MOP to at least "some" degree.
If all you need is a simple introspection (slot list), then
   CLOCC/PORT/sys.lisp:class-slot-list
is your friend.

if you need the advanced MOP features, then you are likely to hit at
least "some" incompatibilities.

Note that the next CLISP release will come with a full MOP
implementation.
<http://www.podval.org/~sds/clisp/impnotes/mop-chap.html>

-- 
Sam Steingold (http://www.podval.org/~sds) running w2k
<http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/>
<http://www.mideasttruth.com/> <http://www.honestreporting.com>
The only intuitive interface is the nipple.  The rest has to be learned.

Joseph Kiniry writes:
> Hi Christophe,
> 
> On 24 Nov, 2004, at 17:30, Christophe Rhodes wrote:
> > Would it be appropriate to suggest SB-INT:PSXHASH?  Values might not
> > be the same across sessions, but otherwise it seems to me that hash
> > values could generate a good approximation to a total order.
> 
> That is actually a very interesting idea.  This would only work though 
> if hash orders were guaranteed consistent across garbage collections...

I was going to propose SXHASH too, but that doesn't remove the need to
implement a full comparison because of the colisions.

Of course, you can use SXHASH to provide a fast comparison for
different bucket objects.

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
The world will now reboot; don't bother saving your artefacts.

Joseph Kiniry <kiniry@...> writes:

> On 24 Nov, 2004, at 17:30, Christophe Rhodes wrote:
>
>> Would it be appropriate to suggest SB-INT:PSXHASH?  Values might not
>> be the same across sessions, but otherwise it seems to me that hash
>> values could generate a good approximation to a total order.
>
> That is actually a very interesting idea.  This would only work though
> if hash orders were guaranteed consistent across garbage collections...

PSXHASH is an (SBCL-internal) function for EQUALP hashing, which must
preserve the hash value for structures across garbage collections
(since two structures which are EQUALP but with different addresses
must hash to the same value, the address of the structure cannot
affect the hash calculation).  For standard-objects, there is no such
guarantee, I think, but I'd be very surprised if any implementation
rehashed all hash tables containing clos objects after GCs --
certainly you're safe in SBCL's case.

Cheers,

Christophe

On Wed, Nov 24, 2004 at 08:58:25PM +0000, Christophe Rhodes wrote:
> Joseph Kiniry <kiniry@...> writes:
> 
> > On 24 Nov, 2004, at 17:30, Christophe Rhodes wrote:
> >
> >> Would it be appropriate to suggest SB-INT:PSXHASH?  Values might not
> >> be the same across sessions, but otherwise it seems to me that hash
> >> values could generate a good approximation to a total order.
> >
> > That is actually a very interesting idea.  This would only work though
> > if hash orders were guaranteed consistent across garbage collections...
> 
> PSXHASH is an (SBCL-internal) function for EQUALP hashing, which must
> preserve the hash value for structures across garbage collections
> (since two structures which are EQUALP but with different addresses
> must hash to the same value, the address of the structure cannot
> affect the hash calculation).  For standard-objects, there is no such
> guarantee, I think, but I'd be very surprised if any implementation
> rehashed all hash tables containing clos objects after GCs --
> certainly you're safe in SBCL's case.

If you're only hashing a modest number of instances, and you want to
avoid writing more than half a dozen lines of code, this could easily
be your best bet. (I have done it, and been satisfied.) But if you
want to get good performance on messy nested data structures, and if
you know something useful about the properties of your data
structures, it might be pretty easy to do a lot better. For example, I
have, in a program of mine, a problem which seems to be described
exactly by your question. In my version of the problem, I happen to
know that the data structure is a directed acyclic graph, so it's easy
to compute a hash effectively. (Also, as it happens, I have just put
up a preprint of a paper which could be thought of as covering more
cases.:-) I also happen to know that it's pretty common for instances
to share enough substructure that PSXHASH (which only wants to flood
to a fixed depth) could return the same value for many instances.
Thus, it was easy to write a custom hashing operation which won big
compared to PSXHASH.

-- 
William Harold Newman <william.newman@...>
"Smart people believe weird things because they are skilled at
defending beliefs they arrived at for nonsmart reasons."
  -- Michael Shermer, Sept. 2002 Scientific American