[racket] General-purpose "hash-consing"

From: Tony Garnock-Jones (tonyg at ccs.neu.edu)
Date: Mon Jun 30 20:54:38 EDT 2014

Hi all,

I'd love any comments on the following as a general technique for
"hash-consing" - that is, making (equal?) imply (eq?). (Corollary: two
canonicalized values will be (eq?) iff they are (equal?).)

Is it worth considering this as something to push into the C runtime for
speed?

  #lang racket/base
  (provide canonicalize)
  (require ffi/unsafe/atomic)

  (define canonical-values (make-weak-hash))

  (define (canonicalize val)
    (start-atomic)
    (define b (hash-ref canonical-values
                        val
                        (lambda ()
                          (hash-set! canonical-values
                                     val
                                     (make-weak-box val))
                          #f)))
    (end-atomic)
    (if b (weak-box-value b) val))

See also
https://gist.github.com/tonyg/86d0052c9c28431e1546#file-hashcons-rkt-L9-L17,
where I have test cases demonstrating simple uses of canonicalize and
its interactions with the garbage collector.

Regards,
  Tony

Posted on the users mailing list.