There are no tags in the expression and there are no binary search trees.
each expression is installed in a hash table. If the expression being
consed together already
exists in the hash table, that value is returned.
How hard is this to do in lisp? Not very hard.
Assume r and s are in the hash table. To do (hcons r s) you look at
the address of r and address of s, and make the hash code from this. Look
to see if it is already in the hash table. If not, create it.
Thus there is only a single (r . s) in the whole lisp system.
(If r or s is not in the hash table, they can be installed..)
There is a discussion of unique consing in Peter Norvig's paradigms of
AI programming.
What is interesting about this is one can use the hash table idea to
(for example) store all the simplified expressions, or all expressions
with some property. Thus instead of tagging an expression with
"simplified" or "factored" one can use a hash table.
Maple (in particular) makes use of hash coding.
RJF
Andrei Zorine wrote:
> I try to read the paper by Prof. Fateman mentioned previously. Hcons
> are easy to obtain, uconsalt.lisp from MockMMA project works for me:
>
> (C1) load(uconsalt)$
> (C2) q1:sin(x)$
> (C3) q2:q1$
> (C4) ?eq(q1,q2);
> (D4) TRUE
> (C5) q2:sin(x)$
> (C6) ?eq(q1,q2);
> (D6) FALSE
> (C7) q1:?uniq(q1);
> (D7) SIN(x)
> (C8) q2:?uniq(q2);
> (D8) SIN(x)
> (C9) ?eq(q1,q2);
> (D9) TRUE
>
> But the tagging procedure is still unclear to me. Should the tags be
> placed in cdar? What does the binary search tree contain exaclty? Are
> there any examples/drafts available?
> --
> Andrei Zorine
>
> _______________________________________________
> Maxima mailing list
> Maxima@www.math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima