Hash consing
In
symbolic and dynamic programming algorithms.[citation needed
]
Hash consing is most commonly implemented with hash tables storing weak references that may be garbage-collected when the data stored therein contains no references from outside the table.[2][3]
Example
Simple, not very efficient, but suitable for demonstration of the concept implementation of a memoizer by means of hash table and weak references in Scheme:
;; weak hashes
;;
(require 'hash-table)
(define (make-weak-table . args)
(apply make-hash-table args))
(define (weak-table-set! table key data)
(let ((w (hash-table-ref table key #f)))
(if w
(vector-set! w 0 data)
(let ((w (make-weak-vector 1)))
(vector-set! w 0 data)
(hash-table-set! table key w)))))
(define (weak-table-ref table key)
(let ((w (hash-table-ref table key #f)))
(if w
(vector-ref w 0)
#f)))
;; memoizer factory: for given (side-effect-free) procedure,
;; return a procedure which does the same memoizing some of results
;; in the sense of equal? on the whole list of args
;;
(define (make-weak-memoizer proc)
(let ((cache (make-weak-table equal?)))
(lambda args
(let ((x (weak-table-ref cache args)))
(if (bwp-object? x)
(let ((r (apply proc args)))
(weak-table-set! cache args r)
r)
x)))))
History
A hash consing compilation technique was presented by A.P. Ershov in 1958.[4][5] The term "hash consing" originates from implementations in the context of Lisp in the 1970s.[6][7]
See also
References
- ].
- ISBN 0-07-001115-X.
- ^ Filliâtre, Jean-Christophe; Conchon, Sylvain (2006). "Type-Safe Modular Hash-Consing". Workshop on ML. ACM.
- S2CID 15986378.
- ^ "Sharing and Common Subexpression Elimination in EDSL compilation". okmij.org. Retrieved 27 April 2023.
- Xerox Palo Alto Research CenterTechnical Report CSL-73-1.
- ^ Goto, Eiichi (1974). Monocopy and associative algorithms in extended Lisp (PDF) (Technical report). Tokyo: University of Tokyo Technical Report TR 74-03.
Further reading
- Ershov, A.P. (1958). "On programming of arithmetic operations". S2CID 15986378.
- Jean Goubault. Implementing Functional Languages with Fast Equality, Sets and Maps: an Exercise in Hash Consing. In Journées Francophones des Langages Applicatifs (JFLA’93), pages 222–238, Annecy, February 1993.
 | This computer science article is a stub. You can help Wikipedia by expanding it. |