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.)
Now working on migrating more of the XSB test suite and we have started thinking about tabling with concurrency.
Thanks! I am glad it’s on the radar!!