From p.singleton@keele.ac.uk  Thu Aug 10 01:11:08 2000
Received: from mail12.svr.pol.co.uk (mail12.svr.pol.co.uk [195.92.193.215])
	by swi.psy.uva.nl (8.9.3/8.9.3) with ESMTP id BAA04785
	for <prolog@swi.psy.uva.nl>; Thu, 10 Aug 2000 01:10:52 +0200 (MET DST)
Received: from modem4294967178.crime.dialup.pol.co.uk ([195.92.0.246] helo=keele.ac.uk)
	by mail12.svr.pol.co.uk with esmtp (Exim 3.13 #0)
	id 13Mezu-0007no-00
	for prolog@swi.psy.uva.nl; Thu, 10 Aug 2000 00:10:54 +0100
Message-ID: <3991E4A2.393E215E@keele.ac.uk>
Date: Thu, 10 Aug 2000 00:09:22 +0100
From: Paul Singleton <p.singleton@keele.ac.uk>
Organization: SmartArts Computing Consultancy
X-Mailer: Mozilla 4.74 [en] (WinNT; U)
X-Accept-Language: en
MIME-Version: 1.0
To: SWI Prolog <prolog@swi.psy.uva.nl>
Subject: representing terms canonically
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

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

