Facts versus terms (was: Asserting a fact when triggering a rule)

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.

Regards,
Günter