Re: [Chicken-users] This may be a bug in chickens hash tables - or my bad
Ivan Shmakov scripsit: > Given that the basic idea of hashing is to produce a key out of > the object’s /value/, the change of the value – and mutation > does just that – changes the hash. Well, yes and no. SRFI 69 and other Scheme hash table frameworks support at least two kinds of hashing: hash by value and hash by identity. If you have a large tree structure made with pairs, and you want to keep ancillary information about some but not all of the pairs, an identity-based hash table will let you keep the information associated with *a particular pair*. Otherwise, if you had a tree like (a (b c) (b c)), then any information associated with the first (b c) would be overwritten if you associated information with the second (b c). This is quite independent of whether you ever mutate the tree or not. -- John Cowan http://www.ccil.org/~cowanco...@ccil.org As you read this, I don't want you to feel sorry for me, because, I believe everyone will die someday. --From a Nigerian-type scam spam ___ Chicken-users mailing list Chicken-users@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] This may be a bug in chickens hash tables - or my bad
Am 18.12.2015 um 18:35 schrieb John Cowan: > Ivan Shmakov scripsit: > >> Given that the basic idea of hashing is to produce a key out of >> the object’s /value/, the change of the value – and mutation >> does just that – changes the hash. > > Well, yes and no. SRFI 69 and other Scheme hash table frameworks > support at least two kinds of hashing: hash by value and hash by > identity. If you have a large tree structure made with pairs, and > you want to keep ancillary information about some but not all of > the pairs, an identity-based hash table will let you keep the information > associated with *a particular pair*. Otherwise, if you had a tree like > (a (b c) (b c)), then any information associated with the first (b c) > would be overwritten if you associated information with the second (b c). > This is quite independent of whether you ever mutate the tree or not. Not necessarily. Given the typical vector+alist implementation, this would still allow to associate values to each particular pair. The problem really arises only around the question what hash-by-identity actually means. I would understand the language as: "two objects comparing eq? will hash to the same value". This would imply that the hash value would have to be somehow (implementation specific) being derived from a unique property of the particular object. (Easy if we'd assume malloc als allocator: just tag the address bits as fixnum. Harder for moving garbage collectors.) So the question is kind of nitpicking: does the srfi-69 /mandate/ that at least the hash-by-identity will produce the same value for the same object over the livetime of the object even if the object is mutated? If so, then we should change the chicken manual to document a deviation from the standard. Until we have a good idea how to fix it, that is. Otherwise I'd still put a warning into the manual. For boneheads like me. I mean: the problem is trivial to work around, once you know what you're dealing with. /Jörg ___ Chicken-users mailing list Chicken-users@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] This may be a bug in chickens hash tables - or my bad
I may be completely misunderstanding something here, but don't you have to use equal? and not eq? for record structures? K. On Wed, Dec 16, 2015 at 10:09 PM, Jörg F. Wittenberger < joerg.wittenber...@softeyes.net> wrote: > Ah, great to learn. > > a) You are right: Per SRFI-69 it is actually undefined. Per chicken > manual it returns the new value associated with key. > > As I've seen the latter (e.g. in the iup egg) actually being used, we > might at least want to keep the behavior in chicken. > > b) But does not matter much. I ran into this originally from > hash-table-ref signaling a missing key. > > The attached, modified test case fails because it i) does not find the > key object hence hash-table-fold'ing the tree to ii) find an association > with the very key the lookup failed for before. > > My hypothesis (after lightly reading the srfi-69.scm source) that the > eq?-hash procedure produces a different hash value for the lookup before > and after the mutation. Hence the lookup fails while walking the tree > succeeds. > > /Jörg > > Am 16.12.2015 um 21:55 schrieb Peter Bex: > > On Wed, Dec 16, 2015 at 09:47:31PM +0100, Jörg F. Wittenberger wrote: > >> Hi, > >> > >> I always assumed that (make-hash-table eq?) would create a hash table > >> usable with arbitrary chicken objects as keys. > >> > >> That is especially structures like objects created via define-record > >> should be valid as keys. That is: referencing the table using the very > >> same object (comparing eq? to the key object of the insert operation) > >> will succeed. > >> > >> However this fails for me. At least after the key object was mutated > >> between insert and reference time. > >> > >> See attached test case. > >> > >> Am I trying something illegal here? > >> > >> Thanks > >> > >> /Jörg > > > >> (use srfi-69) > >> > >> (define objtbl (make-hash-table eq?)) > >> > >> (define (register! obj arg) > >> (hash-table-update! objtbl obj identity (lambda () (list obj arg > >> > >> (assert (eq? (register! 1 1) (register! 1 2))) > > > > I believe the return value of hash-table-update! is undefined. > > > > Cheers, > > Peter > > > > > ___ > Chicken-users mailing list > Chicken-users@nongnu.org > https://lists.nongnu.org/mailman/listinfo/chicken-users > > ___ Chicken-users mailing list Chicken-users@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] This may be a bug in chickens hash tables - or my bad
Am 17.12.2015 um 11:08 schrieb Kristian Lein-Mathisen: > I may be completely misunderstanding something here, but don't you have to > use equal? and not eq? for record structures? AFAIK eq? should hold true when the two objects are the same. Equal? will compare all the slots. (The latter is not defined to be so by Scheme, but it's what chicken does (if I remember the manual correctly)). > > K. > > On Wed, Dec 16, 2015 at 10:09 PM, Jörg F. Wittenberger < > joerg.wittenber...@softeyes.net> wrote: > >> Ah, great to learn. >> >> a) You are right: Per SRFI-69 it is actually undefined. Per chicken >> manual it returns the new value associated with key. >> >> As I've seen the latter (e.g. in the iup egg) actually being used, we >> might at least want to keep the behavior in chicken. >> >> b) But does not matter much. I ran into this originally from >> hash-table-ref signaling a missing key. >> >> The attached, modified test case fails because it i) does not find the >> key object hence hash-table-fold'ing the tree to ii) find an association >> with the very key the lookup failed for before. >> >> My hypothesis (after lightly reading the srfi-69.scm source) that the >> eq?-hash procedure produces a different hash value for the lookup before >> and after the mutation. Hence the lookup fails while walking the tree >> succeeds. >> >> /Jörg >> >> Am 16.12.2015 um 21:55 schrieb Peter Bex: >>> On Wed, Dec 16, 2015 at 09:47:31PM +0100, Jörg F. Wittenberger wrote: Hi, I always assumed that (make-hash-table eq?) would create a hash table usable with arbitrary chicken objects as keys. That is especially structures like objects created via define-record should be valid as keys. That is: referencing the table using the very same object (comparing eq? to the key object of the insert operation) will succeed. However this fails for me. At least after the key object was mutated between insert and reference time. See attached test case. Am I trying something illegal here? Thanks /Jörg >>> (use srfi-69) (define objtbl (make-hash-table eq?)) (define (register! obj arg) (hash-table-update! objtbl obj identity (lambda () (list obj arg (assert (eq? (register! 1 1) (register! 1 2))) >>> >>> I believe the return value of hash-table-update! is undefined. >>> >>> Cheers, >>> Peter >>> >> >> >> ___ >> Chicken-users mailing list >> Chicken-users@nongnu.org >> https://lists.nongnu.org/mailman/listinfo/chicken-users >> >> > ___ Chicken-users mailing list Chicken-users@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] This may be a bug in chickens hash tables - or my bad
On Wed, Dec 16, 2015 at 09:47:31PM +0100, Jörg F. Wittenberger wrote: > Hi, > > I always assumed that (make-hash-table eq?) would create a hash table > usable with arbitrary chicken objects as keys. > > That is especially structures like objects created via define-record > should be valid as keys. That is: referencing the table using the very > same object (comparing eq? to the key object of the insert operation) > will succeed. > > However this fails for me. At least after the key object was mutated > between insert and reference time. > > See attached test case. > > Am I trying something illegal here? > > Thanks > > /Jörg > (use srfi-69) > > (define objtbl (make-hash-table eq?)) > > (define (register! obj arg) > (hash-table-update! objtbl obj identity (lambda () (list obj arg > > (assert (eq? (register! 1 1) (register! 1 2))) I believe the return value of hash-table-update! is undefined. Cheers, Peter signature.asc Description: Digital signature ___ Chicken-users mailing list Chicken-users@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-users
[Chicken-users] This may be a bug in chickens hash tables - or my bad
Hi, I always assumed that (make-hash-table eq?) would create a hash table usable with arbitrary chicken objects as keys. That is especially structures like objects created via define-record should be valid as keys. That is: referencing the table using the very same object (comparing eq? to the key object of the insert operation) will succeed. However this fails for me. At least after the key object was mutated between insert and reference time. See attached test case. Am I trying something illegal here? Thanks /Jörg (use srfi-69) (define objtbl (make-hash-table eq?)) (define (register! obj arg) (hash-table-update! objtbl obj identity (lambda () (list obj arg (assert (eq? (register! 1 1) (register! 1 2))) (define-record foo bar) (define o1 (make-foo (list 23))) (define r1 (register! o1 1)) (assert (eq? r1 (register! o1 2))) (assert (eq? r1 (register! o1 3))) (foo-bar-set! o1 (list 42)) (assert (eq? r1 (register! o1 4))) ___ Chicken-users mailing list Chicken-users@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] This may be a bug in chickens hash tables - or my bad
Ah, great to learn. a) You are right: Per SRFI-69 it is actually undefined. Per chicken manual it returns the new value associated with key. As I've seen the latter (e.g. in the iup egg) actually being used, we might at least want to keep the behavior in chicken. b) But does not matter much. I ran into this originally from hash-table-ref signaling a missing key. The attached, modified test case fails because it i) does not find the key object hence hash-table-fold'ing the tree to ii) find an association with the very key the lookup failed for before. My hypothesis (after lightly reading the srfi-69.scm source) that the eq?-hash procedure produces a different hash value for the lookup before and after the mutation. Hence the lookup fails while walking the tree succeeds. /Jörg Am 16.12.2015 um 21:55 schrieb Peter Bex: > On Wed, Dec 16, 2015 at 09:47:31PM +0100, Jörg F. Wittenberger wrote: >> Hi, >> >> I always assumed that (make-hash-table eq?) would create a hash table >> usable with arbitrary chicken objects as keys. >> >> That is especially structures like objects created via define-record >> should be valid as keys. That is: referencing the table using the very >> same object (comparing eq? to the key object of the insert operation) >> will succeed. >> >> However this fails for me. At least after the key object was mutated >> between insert and reference time. >> >> See attached test case. >> >> Am I trying something illegal here? >> >> Thanks >> >> /Jörg > >> (use srfi-69) >> >> (define objtbl (make-hash-table eq?)) >> >> (define (register! obj arg) >> (hash-table-update! objtbl obj identity (lambda () (list obj arg >> >> (assert (eq? (register! 1 1) (register! 1 2))) > > I believe the return value of hash-table-update! is undefined. > > Cheers, > Peter > (use srfi-69) (define objtbl (make-hash-table eq?)) (define (register! obj arg) (hash-table-update! objtbl obj identity (lambda () (list obj arg (assert (eq? (register! 1 1) (register! 1 2))) (define-record foo bar) (define o1 (make-foo (list 23))) (define r1 (register! o1 1)) (assert (eq? r1 (register! o1 2))) (assert (eq? r1 (register! o1 3))) (foo-bar-set! o1 (list 42)) #;(assert (eq? r1 (register! o1 4))) (unless (hash-table? (hash-table-ref/default objtbl o1 #f)) (assert (not (hash-table-fold objtbl (lambda (k v i) (or i (eq? k o1))) #f signature.asc Description: OpenPGP digital signature ___ Chicken-users mailing list Chicken-users@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-users
