I am looking for papers that describe a sort of structure sharing within large
parse trees. The idea is fairly simply - any subtree structure which is
equal to another subtree is not duplicated; instead, a pointer is sent from
the subtree to its copy. In other words, the tree will contain no duplicate
structures, only pointers to equivalent structures will be used wherever
needed.
So far, I have only one lead. Using a hash table, all unique structures are
stored in and all duplicates point to the elements in the table. By modifying
cons, list and append, space is conserved when the tree is built.
The following code illustrates, to some extent, what I am babbling about:
(defvar *cons-hash-table* (make-hash-table :test #'equal))
(defvar *dummy-cons* (cons nil nil))
(defun hash-cons (car cdr)
(setf (car *dummy-cons*) car
(cdr *dummy-cons*) cdr)
(or (gethash *dummy-cons* *cons-hash-table*)
(let ((new-cons (cons car cdr)))
(setf (gethash new-cons *cons-hash-table*) new-cons)
new-cons))))
Therefore, no space is wasted in cons-ing a duplicate structure.
Any help, guidance, direction or leads you can offer would be appreciated.
Please e-mail to ······@stc.comm.mot.com.
Pinku Surana