[r6rs-discuss] immutable hash tables and eqv?

From: R. Kent Dybvig <dyb>
Date: Thu, 24 May 2007 13:02:24 -0400

> I couldn't find a way to create an immutable hash table. Given that this is
> not possible, this seems to indicate that hash-tables are inferior to a
> library implementing hash-tables on top of records. Such a
> hash-table-library can provide immutable hash-tables, and these immutable
> hash-tables will have the ability to be eqv? even if they reside at
> different locations in the store because they are immutable records.

As Anton points out, immutable hashtables can be created with hashtable-copy.

Furthermore, in r5.93rs, there is no guarantee that (eqv? x x) => #t if x
is an immutable record (or pair, vector, string, or hashtable). There is
no difference between eqv?'s treatment of hashtables and records.

I think this decision to (un)specify eqv? in this manner was a mistake
and hope we can agree to fix the mistake. If we do, I expect that it will
continue to work the same for hashtables as it does for records.

Incidentally, one reason I think it's a mistake is that it destroys the
programmer's ability to use eq? or eqv? hashtables with immutable pairs,
vectors, records, etc., as keys. So, for example, I can't use hashtables
to virtually add properties to an existing immutable object. To make
this more concrete, suppose I want to use a hashtable to record source
information on an s-expression, and I haven't imported the mutable-pairs
library. Then I can't reliably retrieve the source information from the
hashtable because the implementation is not required to make eqv? or eq?
work for the immutable pairs that make up portions of the s-expression.

You're absolutely right, however, that you can use records to create a
kind of hash table that isn't mutable in the ordinary sense but for which
eqv? behaves as you want. You can do this by including a mutable field
that you don't use for anything. This is the general (and unpleasant)
workaround to regaining reliable eqv? semantics for otherwise immutable
records. For pairs, one can regain reliable eqv? semantics by importing
from the mutable-pairs library. Presumably even (import (only
immutable-pairs)) will do. Yuck.

> Also, this language in the desciption of eqv? is a bit confusing for me:
>
> [eqv? should return #f if...]
> Obj1 and obj2 are mutable objects such as pairs, vectors,
> strings, mutable records (library chapter 6), ports
> (library section 8.2), and hashtables (library chapter
> 13) that denote distinct locations.

The word "mutable" should have appeared before the word "hashtable". In
fact, the two existing occurrences of the word "mutable" should be
removed (here and also in the related paragraph under "eqv? should return
#t if ...), since the modifiers aren't necessary with either the old or
current semantics. (With the current semantics, the storage model already
allows an immutable pair, record, etc., to be held in different sets of
locations simultaneously.) Removing the word "mutable" from the sentence
may also prevent the kind of confusion you experienced.

Kent
Received on Thu May 24 2007 - 13:02:24 UTC