hash-consing

[David Bartley <Bartley%ti-csl.csnet@CSNET-RELAY.ARPA>]

Has anyone had any experience with systems that use hashing CONS?  I
remember the idea was in vogue 15 or 20 years ago as a way to lower
memory consumption, speed up EQUAL, and for theoretical (heretical?)
reasons.  The idea is to use hashing techniques to make pairs that are
EQUAL? also be EQ?.

The disadvantages seem to be (1) slower CONS, (2) unclear semantics
for SET-CAR! and SET-CDR!, (3) separate spaces or tags (or something)
if both hashed and regular CONS exist, and (4) GC complications.  Are
there any experimental results that demonstrate any significant
compensating advantages?  If so, what are the circumstances?

The definition of CONS in the RRRRS guarantees that every pair
returned is unique, so hashing would seem to be out of the question.
However, I wonder if a HASH-CONS procedure has any merit.

Regards,
David Bartley
-------