doc.txt

hash-cons: hash-cons for sharing of cons pairs and structs

_hash-cons_: hash-cons for sharing of cons pairs and structs

Author: Danny Yoo (dyoo@cs.wpi.edu / dyoo@hkn.eecs.berkeley.edu)

Index terms: _hash-cons.ss_, _make-hash-struct.ss_


Intro
-----

This is an implementation of a "hash-cons" function.  hash-cons is
useful when we're trying to reduce a program's memory requirements: if
we're treating our data structures functionally, we can take full
advantage of the sharing of our cons pairs.  When constructing a new
cons pair, we can first check to see if we've already constructed a
pair with the same content: if so, we grab it from our cache.

This package also provides a framework within _make-hash-struct.ss_
for constructing hash-cons-like functions for other structures that
support equal?; see below for details.


Quick Example
-------------

    > (require (planet "hash-cons.ss" ("dyoo" "hash-cons.plt" 1)))
    > (let* ([p1 (hash-cons 4 2)]
             [p2 (hash-cons 4 2)])
        (eq? p1 p2))
    #t



API for "hash-cons.ss"
----------------------

> hash-cons: X Y -> (cons X Y)

Produces a cons pair of the given arguments.  We consult an internal
cache to see if we can reproduce an cons pair that was previously
returned from this function.  The arguments are compared by equal?.
If we can't find a previously existing pair, we then construct a new
pair, add that to the cache, and return that new pair to the user.

This cache is shared across all threads.

WARNING: please do not mutate any pair that comes from hash-cons.



API for "make-hash-struct.ss"
-----------------------------

make-hash-struct.ss provides a single special form _make-hash_struct_:

> make-hash-struct: (X1 X2 ... -> Y)
                    literal-number
                    (X1 X2 ...)
                    ((Y X1 -> void) (Y X2 -> void) ...)
                    -> (X1 X2 ... -> Y)

make-hash-struct makes a constructor that "hash-cons"es its input
based on equal?  It takes in the original constructor, that constructors
arity, a list of dummy values we can use for the fields, and mutators for
those fields.

The signature is a little hideous.  Here's an example of how we might
use make-hash-struct:

    ;; a tree is a
    ;;
    ;;   (make-tree a-key a-left-tree a-right-tree)
    ;;
    ;; where a-key is a number, and a-left-tree and a-right-tree
    ;; are either trees or #f.
    > (define-struct tree (key left right) #f)
    >
    > (require (planet "make-hash-struct.ss" ("dyoo" "hash-cons.plt" 1)))
    >
    > (define -make-tree
        (make-hash-struct make-tree
                          3
                          (0 #f #f)
                          (set-tree-key! set-tree-left! set-tree-right!)))
    > (define mytree (-make-tree 3 (-make-tree 1 #f #f) (-make-tree 1 #f #f)))
    > (eq? (tree-left mytree) (tree-right mytree))
    #t

NOTE: make sure that the structure is inspectable with equal?;
otherwise, the hash-consing function won't be able to effectively
search its cache.

I know this interface is awkward; future revisions of this library may
try to pull more information from the information in the structure
syntax object.


References
----------

I found another hash-cons implementation at:

    http://swiss.csail.mit.edu/classes/symbolic/spring07/readings/hashcons.scm

which references a paper from 1958:

    A.P. Ershov, On programming of arithmetic operators
    http://portal.acm.org/citation.cfm?id=368892.368907&dl=ACM&dl=ACM&CFID=21825082&CFTOKEN=44015210