Tabling: interned terms

Hi Jan,

Is there a plan to implement interned terms?

From the XSB manual:

XSB supports, on request, a special representation of ground terms, known as interned terms (see intern_term/2.) This representation is also sometimes known as a “hash-consing” representation. All interned terms are stored in a global area and each such term is stored only once, with all instances of a given interned (sub-)term pointing to that one stored representation. This can allow for a much more succinct representation of sets of ground terms that share subterms. Importantly interned ground terms, in principle, do not need to be copied into and out of tables. CHAPTER 5. USING TABLING IN XSB: A TUTORIAL INTRODUCTION 95 To take advantage of this possibility, a table must be declared as intern. As an example of a possible use of this mechanism, consider a simple DCG that recognizes all strings of a’s starting with a single b:

:- table bas/2 as intern.
bas --> [b].
bas --> bas, [a].

This predicate must be tabled in order to terminate, since the grammar is leftrecursive. If we use the usual list representation of an input string and use variant tabling, every call to bas/2 and every return will copy the remaining list into the table, and recognition will be quadratic. (For example on my laptop, recognizing a list of one b followed by 10,000 a’s takes about 1.84 seconds, and 20,000 a’s about 7.285 seconds.) If we table bas/2 as intern, the initial ground input list will be interned (copied to intern space) on the first call, and after that every subsequent call of bas/2 will be given an interned term, which need not be copied into (or out of) the table. In this case the complexity will be linear. (For example on my laptop, recognizing a list of one b and 1,000,000 a’s takes less than a second.)

Interning is on the radar. One by one though :slight_smile: Now working on migrating more of the XSB test suite and we have started thinking about tabling with concurrency.

:grin: Thanks! I am glad it’s on the radar!!

I am afraid to open a new thread, and I don’t know whether XSB can do it, but you could also implement polarized “Dependency Graph”. I did this in NewQuel 1989 (if you find it on www I give you $1), it has some advantage if your database has consistency indicators:

:- table consistent/0.
consistent :- ... bla bla ...

Now assume the database is already consistent, i.e. consistent succeeds. What happens when you make assertz/1, retract/1 in dependent facts? Will you always re-evaluate? Polarized dependency handles separately assertz/1 and retract/1,

and can also tell you sometimes when you don’t really need to do something. Polarized “Dependency Graph” means your dependencies are signed, you have positive and negative arcs. With respect to the clause format of Prolog rules, this could simply be

whether the source literal was negated or not.

P.S.: Example where you don’t need to do something. If you assert something for q/1 you don’t need to re-evaluate this consistent/0. In the same vain, if you retract something from p/1, you don’t need to re-evaluate this consistent/0:

:- table consistent/0.
consistent :- forall(p(X),q(X)).

P.P.S.: In the above example forall(C,A) is \+ (C, \+A).

Here is a further future feature request.
I get in SWI-Prolog and compare with YAP:

/* SWI-Prolog */
?- path(a,e,X).
X = 2.

/* YAP Prolog */
?- path(a,e,X).
X = 4 ? ;
X = 3 ? ;
X = 2 ? ;

I am fine with the SWI-Prolog behaviour. When I have specified
a min aggregate I think it doesn’t make much sense to show also
approximate solutions.

What I wonder on the other hand is why this throws an error,
I would like to see no error. So in this case I think the YAP behaviour
is better, more logical:

/* SWI-Prolog */
?- path(a,e,2).
ERROR: Uninstantiated argument expected, found 2
?- path(a,e,1).
ERROR: Uninstantiated argument expected, found 1

/* YAP Prolog */
 ?- path(a,e,2).
 ?- path(a,e,1).


P.S.: The test code is:

% path(+Vertex, +Vertex, -Integer)
:- table path(index,index,min).
path(X, X, 0).
path(X, Y, N) :-
   edge(X, Z),
   path(Z, Y, M),
   N is M+1.

% edge(-Vertex, -Vertex)
edge(a, b).         edge(a, c).
edge(a, d).         edge(b, c).
edge(c, d).         edge(c, e).
edge(d, e).

P.P.S.: My current prototype does the following. I get this for free, since
aggregates from library(advanced/aggregate) also allow an input argument
in the third argument. So its not really an issue for library(advanced/tabling):

?- path(a,e,X). 
X = 2
?- path(a,e,2).
?- path(a,e,1).