[bug #22022] hashx-set! and -ref

[bug #22022] hashx-set! and -ref

[Gregory Marton]

URL:
  <http://savannah.gnu.org/bugs/?22022>

                 Summary: hashx-set! and -ref
                 Project: Guile
            Submitted by: gremio
            Submitted on: Monday 01/14/2008 at 22:40
                Category: None
                Severity: 3 - Normal
              Item Group: None
                  Status: None
                 Privacy: Public
             Assigned to: None
             Open/Closed: Open
         Discussion Lock: Any

    _______________________________________________________

Details:

Hashing using ones own hash functions does not survive a hash resize.

If the assoc function returns #t, a segfault or bus error results.

A patch to the test suite demonstrating these and testing a few other things
is attached.

As an enhancement request, it would be nice for the common case to be able to
pass a hash-function argument and assoc to make-hash-table or to have a
(make-hashx-table hash assoc [size]), and in either case to remember the hash
function so that resize works correctly.

Thanks,
Grem




    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Monday 01/14/2008 at 22:40  Name: hash.test.patch  Size: 7kB   By:
gremio

<http://savannah.gnu.org/bugs/download.php?file_id=14801>

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?22022>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/

[bug #22022] hashx-set! and -ref

[Neil Jerram]

Follow-up Comment #1, bug #22022 (project guile):

I think I have a fix for the segfault, but now I'm seeing several other test
failures.  Here's one...

 (pass-if (let ((table (make-hash-table)))
	    (hashx-set! (lambda (k v) 1) assoc table 'foo 'bar)
	    (equal? 
	     'bar (hashx-ref (lambda (k v) 1) assoc table 'baz))))

This one is wrong, isn't it?  It sets an entry with key 'foo, then queries
the entry with key 'baz.  So the result, correctly, is #f.  What was your
intention here?


    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?22022>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/

Re: [bug #22022] hashx-set! and -ref

[Gregory Marton]

Ack.  I think I meant to replace assoc as well, with something like (lambda 
(k alist) (cdar alist)).  My intention was to get it to give me back 'bar 
because the hash functions would accept anything, rather than because it 
was "right" in any sense.

Sorry,
Grem

> Follow-up Comment #1, bug #22022 (project guile):
>
> I think I have a fix for the segfault, but now I'm seeing several other test
> failures.  Here's one...
>
> (pass-if (let ((table (make-hash-table)))
> 	    (hashx-set! (lambda (k v) 1) assoc table 'foo 'bar)
> 	    (equal?
> 	     'bar (hashx-ref (lambda (k v) 1) assoc table 'baz))))
>
> This one is wrong, isn't it?  It sets an entry with key 'foo, then queries
> the entry with key 'baz.  So the result, correctly, is #f.  What was your
> intention here?
>
>
>    _______________________________________________________
>
> Reply to this item at:
>
>  <http://savannah.gnu.org/bugs/?22022>
>
> _______________________________________________
>  Message sent via/by Savannah
>  http://savannah.gnu.org/
>
>

-- 
------ __@   Gregory A. Marton                http://csail.mit.edu/~gremio/
--- _`\<,_                                                                .
-- (*)/ (*)                 A closed mouth gathers no foot.
~~~~~~~~~~~~~~~~-~~~~~~~~_~~~_~~~~~v~~~~^^^^~~~~~--~~~~~~~~~~~~~~~++~~~~~~~

Re: [bug #22022] hashx-set! and -ref

[Neil Jerram]

Gregory Marton <gremio@mit.edu> writes:

> Ack.  I think I meant to replace assoc as well, with something like
> (lambda (k alist) (cdar alist)).

That wouldn't be assoc-like.  (lambda (k al) (car al)) accesses the
correct level of alist structure, but would fault in the case where al
is empty.

So perhaps: (lambda (k al) (and (not (null? al)) (car al))).  With
this, the test passes - are you happy with that?

Thanks,
        Neil

Re: [bug #22022] hashx-set! and -ref

[Gregory Marton]

Yes, thank you.  Apologies again for my carelessness.

Grem

> Gregory Marton <gremio@mit.edu> writes:
>
>> Ack.  I think I meant to replace assoc as well, with something like
>> (lambda (k alist) (cdar alist)).
>
> That wouldn't be assoc-like.  (lambda (k al) (car al)) accesses the
> correct level of alist structure, but would fault in the case where al
> is empty.
>
> So perhaps: (lambda (k al) (and (not (null? al)) (car al))).  With
> this, the test passes - are you happy with that?
>
> Thanks,
>        Neil
>
>

-- 
------ __@   Gregory A. Marton                http://csail.mit.edu/~gremio/
--- _`\<,_                                                                .
-- (*)/ (*)                   There's no place like /home
~~~~~~~~~~~~~~~~-~~~~~~~~_~~~_~~~~~v~~~~^^^^~~~~~--~~~~~~~~~~~~~~~++~~~~~~~

[bug #22022] hashx-set! and -ref

[Neil Jerram]

Follow-up Comment #2, bug #22022 (project guile):

Another one:

   (pass-if (equal? "#<hash-table 34/61>" 
		    (with-output-to-string (lambda () (write table)))))))

Actual output here has 33 instead of 34.  I believe 33 is correct, because
the additions to the hash table run from 2 up to 34, not from 1 up to 34.

Agree?

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?22022>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/

Re: [bug #22022] hashx-set! and -ref

[Gregory Marton]

Thanks, yes.  I initially had a one in there.  Hmmm... it doesn't matter. 
33 is enough to trigger resize.

Thanks,
Grem

> Follow-up Comment #2, bug #22022 (project guile):
>
> Another one:
>
>   (pass-if (equal? "#<hash-table 34/61>"
> 		    (with-output-to-string (lambda () (write table)))))))
>
> Actual output here has 33 instead of 34.  I believe 33 is correct, because
> the additions to the hash table run from 2 up to 34, not from 1 up to 34.
>
> Agree?
>
>    _______________________________________________________
>
> Reply to this item at:
>
>  <http://savannah.gnu.org/bugs/?22022>
>
> _______________________________________________
>  Message sent via/by Savannah
>  http://savannah.gnu.org/
>
>
>
>

-- 
------ __@   Gregory A. Marton                http://csail.mit.edu/~gremio/
--- _`\<,_                                                                .
-- (*)/ (*)               Teach you backwards to speak I can.
~~~~~~~~~~~~~~~~-~~~~~~~~_~~~_~~~~~v~~~~^^^^~~~~~--~~~~~~~~~~~~~~~++~~~~~~~

[bug #22022] hashx-set! and -ref

[Neil Jerram]

Follow-up Comment #3, bug #22022 (project guile):

And here are all the remaining ones.  I've added a (pk ...) in each case, so
the output from make check shows what the actual hash?-ref value was.

;;; (#f)
FAIL: hash.test: auto-resizing hashx: (equal? (quote eq) (pk (hashq-ref table
4)))

;;; (#f)
FAIL: hash.test: auto-resizing hashx: (equal? (quote equal) (pk (hashx-ref
hash equal? table 1/32)))

;;; (#f)
FAIL: hash.test: auto-resizing hashx: (equal? (quote eqv) (pk (hashx-ref
hashv eqv? table 1/33)))

;;; (#f)
FAIL: hash.test: auto-resizing hashx: (equal? (quote eq) (pk (hashx-ref hashq
eq? table 34)))

These cases, together with the neighbouring ones that happen to pass, are
actually out of scope, because the manual says (5.6.12.2 Hash Table
Reference):

-----------manual------------
Like the association list functions, the hash table functions come in
several varieties, according to the equality test used for the keys.
Plain `hash-' functions use `equal?', `hashq-' functions use `eq?',
`hashv-' functions use `eqv?', and the `hashx-' functions use an
application supplied test.

   A single `make-hash-table' creates a hash table suitable for use
with any set of functions, but it's imperative that just one set is
then used consistently, or results will be unpredictable.
-----------manual------------

The rationale for this is what happens when a hash table is resized.  When
that happens, the new hash buckets (vector indices) are recalculated, for all
existing entries in the table, using the hash function that was specified on
the call that caused the resize.  If that hash function is different from the
hash that is later used to try to query particular entries, Guile can look in
the wrong bucket, and the expected entry won't be found.

There's another case, too, where a rehash is done following GC, using a hash
function that was stored at some point in the hashtable data structure.  But I
haven't got right into that, because I think we already have enough to rule
these test cases invalid.

What do you think?


    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?22022>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/

Re: [bug #22022] hashx-set! and -ref

[Gregory Marton]

> What do you think?

I didn't read that part of the spec, so I was confused, and I'll grant that 
the cases may be out of scope.

Moreover, I think the hash specification is problematic.
    (a) the representation seems to wish to hide the current size of the
        hash vector, or at least that would be sensible, but it is exposed
        in the printout and as an argument to the hash-function supplied to
        hashx.  The point at which the hash is resized is unpredictable from
        the user's point of view.  This is three flavors of rep exposure.

    (b) if, as the doc says, "it's imperative that just one set is then used
        consistently, or results will be unpredictable", then it makes sense
        to enforce this.  A common way to enforce it is to ask for the hash
        function just once, at creation time.  By requiring it everywhere,
        we force the user to expose a representation, the hash function and
        equality predicate, between one part of their program and another.

    (c) the assoc requirement is a rep exposure of a third sort -- it exposes
        the fact that buckets are alists.  There is no reason for the user to
        know this, and there is no reason it should be so.  If a future
        implementation wants to do something else, say hash with another
        hash, they will have to emulate assoc-ability to make this API work.
        Moreover, this forces the user to write the assoc function on top of
        their equality predicate, which is neither fast (it's Scheme instead
        of C) nor DRY (Don't Repeat Yourself -- a principle of not
        duplicating code).

If the current set of decisions seems self-consistent and useful to the 
community, then I guess I'd submit an enhancement request, for a new set of 
fast functions:
    (make-hashf-table one-arg-hash-function equality-predicate [size])
    (hashf-set! hashf-table 'key value)
    (hashf-ref hashf-table 'key [default])
    (hashf-remove! hashf-table 'key)
    (hashf-size hashf-table) ===> the number of keys stored
    ... [clear get-handle create-handle for-each for-each-handle map->list

"f" for the functions it stores.

Thanks,
Grem

-- 
------ __@   Gregory A. Marton                http://csail.mit.edu/~gremio/
--- _`\<,_                                                                .
-- (*)/ (*)             Contents may have settled out of court.
~~~~~~~~~~~~~~~~-~~~~~~~~_~~~_~~~~~v~~~~^^^^~~~~~--~~~~~~~~~~~~~~~++~~~~~~~

[bug #22022] hashx-set! and -ref

[Neil Jerram]

Update of bug #22022 (project guile):

                  Status:                    None => Fixed                  
             Open/Closed:                    Open => Closed                 

    _______________________________________________________

Follow-up Comment #4:

(For the bug record...  The following has already been discussed on-list, but
I don't know how to prevent savannah from CC'ing this to bug-guile.) Have
committed (on 2008-01-18) a test and fix for the segfault.  Other failed test
have been agreed to be invalid, as discussed below.  Will commit other,
passing tests from Gregory Marton once copyright papers are in place.


    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?22022>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/

[bug #22022] hashx-set! and -ref

[Neil Jerram]

Follow-up Comment #5, bug #22022 (project guile):

Grem's copyright assignment has now been processed, so his additional
hashtable tests have been committed.

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?22022>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/

Re: [bug #22022] hashx-set! and -ref

[Neil Jerram]

Gregory Marton <INVALID.NOREPLY@gnu.org> writes:

> As an enhancement request, it would be nice for the common case to be able to
> pass a hash-function argument and assoc to make-hash-table or to have a
> (make-hashx-table hash assoc [size]), and in either case to remember the hash
> function so that resize works correctly.

Last email on this topic for tonight...!

Note that anyone wanting to implement this "saner" interface can
straightforwardly do so in Scheme:

(define hash-table-hash-fn (make-object-property))

(define hash-table-assoc-fn (make-object-property))

(define (make-hashx-table hash assoc . args)
  (let ((t (apply make-hash-table args)))
    (set! (hash-table-hash-fn t) hash)
    (set! (hash-table-assoc-fn t) assoc)
    t))

(define (hashx-table-ref t key)
  (hashx-ref (hash-table-hash-fn t) (hash-table-assoc-fn t) t key))

etc.

Regards,
       Neil

Re: [bug #22022] hashx-set! and -ref

[Gregory Marton]

Thank you.  I did something far less elegant already, but it's good to have 
this.  I should also read all of my email before responding.  :-)

Best wishes,
Grem

> Gregory Marton <INVALID.NOREPLY@gnu.org> writes:
>
>> As an enhancement request, it would be nice for the common case to be able to
>> pass a hash-function argument and assoc to make-hash-table or to have a
>> (make-hashx-table hash assoc [size]), and in either case to remember the hash
>> function so that resize works correctly.
>
> Last email on this topic for tonight...!
>
> Note that anyone wanting to implement this "saner" interface can
> straightforwardly do so in Scheme:
>
> (define hash-table-hash-fn (make-object-property))
>
> (define hash-table-assoc-fn (make-object-property))
>
> (define (make-hashx-table hash assoc . args)
>  (let ((t (apply make-hash-table args)))
>    (set! (hash-table-hash-fn t) hash)
>    (set! (hash-table-assoc-fn t) assoc)
>    t))
>
> (define (hashx-table-ref t key)
>  (hashx-ref (hash-table-hash-fn t) (hash-table-assoc-fn t) t key))
>
> etc.
>
> Regards,
>       Neil
>
>
>
>
>

-- 
------ __@   Gregory A. Marton                http://csail.mit.edu/~gremio/
--- _`\<,_                                                                .
-- (*)/ (*)               Truth, Beauty, Love, and Darwinfish!
~~~~~~~~~~~~~~~~-~~~~~~~~_~~~_~~~~~v~~~~^^^^~~~~~--~~~~~~~~~~~~~~~++~~~~~~~