Subject: representing terms canonically

From: Paul Singleton <[email-masked]>
Date: Thu, 10 Aug 2000 00:09:22 +0100

I want to represent general Prolog terms in a non-Prolog environment (e.g.
structures in Java or Visual Basic; byte strings in databases or networks)
with all these properties if possible:

 * no loss of information
    + an equivalent term should be reconstructable from the foreign repn.
      (I can do this :-)
    + preserve internal order of any variables (I can see how to do this)

 * compactly
    + cyclic terms have finite representations
    + recombinant terms are not "exploded"
    + common atoms, variables (of course) and subterms are factored out

 * canonically
    + all (inc. cyclic) terms denoting the "same" term (apart from renaming
      of variables) have a single common representation

I suspect it is obvious to some others that canonical repn of cyclic terms
is in general impossible, or infeasible to compute?  It just seems likely
to me...

I want to factor out common atoms because some may be very large.

I want to preserve variable order in case it is significant, e.g. indexed
sets of lemmas for some theorem prover or other interpreter...

I want to represent cyclic terms finitely because I can't guarantee that
applications won't build them, and anyway some applications may use them
(whether they *should* is irrelevant, I hope).

I'm willing to assume that no atom gc or stack shifting occurs while any
particular term is being exported.

I reckon this needs facilities not provided in the FLI: e.g. get the
dictionary address of an atom, and the heap address of a compound term

I have a tentative algorithm for factoring common subterms based on
maintaining a hash value for each subterm during traversal, then using
a safe (cycle-detecting) comparison...

And that's as far as I've got - comments, help and advice please.

Paul Singleton