Re: Facts versus terms

On 12/20/2013 11:49 AM, G�nter Kniesel wrote:
>
> Am 20.12.2013 07:45, schrieb Richard A. O'Keefe:
>
>> Why on earth are you representing an AST as a bunch of
>> facts instead of a simple tree?
>
> Hi Richard,
>
> I don't know why Baltasar is doing it but I can tell you why
> we are doing it and I would apreciate your opinion.
>
> In a nutshell:
>     Feasibility,
>     scalability,
>     speed.
>
> In a slightly bigger nutshell:
>   1. sheer size of the AST
>   2. locality of access
>   3. locality of tranformation.
>
> More elaborate:
>
> 1. Our ASTs typically have several million or tenth of million of nodes
> representing programs with several million lines of code.
>
> Representing that as one gigantic term and working on it recusively is
> prohibitive. We have done some experiments and even a few thousand nodes
> in a complex, deeply nested structure have blown the stack.
>
>
> 2. One never needs to traverse the whole program but instead typically
> has to access a small part of it to infer some property of this part. To
> do that one often has to access some "remote" elements, e.g. elements of
> other classes. Those are "far away" in a term representation, needing a
> lot of term traversal to reach them. In a fact representation they are
> accessible in constant time due to the great indexing mechanisms of
> current Prolog implementations.
>
>
> 3. If a part of the program has a "bad" property we want to transform it
> so that some "good" property holds instead. The transformation of a term
> would mean copying the entire terrm with some small modifications.
> That is prohibitive feasibility-, scalability-, and speed-wise if it
> means copying one million (sub)terms just to change 10 of them.
>
> Again, facts are the only way to do these things. They give us tenth of
> seconds or milliseconds run-time, regadless of the size of the program.
> Only the number of occurrences of "bad" things influences the run-time.
>
> -----------------------------------------------------------------------
>
> Having said all that, I should add that we know and appreciate your book
> and all the tips you shared on this list. We ARE applying them where
> they are applicable.
>
> I am curious to know how you would do it otherwise or whether you know
> of any systems that have succeeded scaling a term-based approach to
> terms of this size.

I don't exactly remember where, but there is an article about
representing XML documents as a set of facts (called something with
`logic' and `xml'). This opposed to SWI-Prolog's library that represents
an XML document as a tree of terms. The idea of SWI-Prolog's library is
that it is way easier to traverse the tree and assert facts than to
recompose the tree from the small facts. Also, the tree might live
short. Represented as a term, you don't have to worry about the module
to store it, predicate names (and conflicts), etc.

I guess it mostly depends on what you want to do. If you want (as you
do) more or less `random access' to tree that itself is a source of
(mostly) static background knowledge, small facts are probably the way
to go. If you want to define some mapping/rewrite operation on a
volatile tree, a tree of terms is generally cleaner and more practical.

Memory wise, I don't know.  The term-representation is more compact and
64-bit systems pose no (practical) limit on the stack size.

	Cheers --- Jan
_______________________________________________
SWI-Prolog mailing list
[email protected]
https://lists.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog