The Internal Data Base

Some programs need global information for, e.g.

counting or collecting data obtained by backtracking. As a rule, to keep this information, the internal data base should be used instead of asserting and retracting clauses (as most novice programmers do), . In YAP (as in some other Prolog systems) the internal data base (i.d.b. for short) is faster, needs less space and provides a better insulation of program and data than using asserted/retracted clauses. The i.d.b. is implemented as a set of terms, accessed by keys that unlikely what happens in (non-Prolog) data bases are not part of the term. Under each key a list of terms is kept. References are provided so that terms can be identified: each term in the i.d.b. has a unique reference (references are also available for clauses of dynamic predicates).

There is a strong analogy between the i.d.b. and the way dynamic predicates are stored. In fact, the main i.d.b. predicates might be implemented using dynamic predicates:


 recorda(X,T,R) :- asserta(idb(X,T),R).
 recordz(X,T,R) :- assertz(idb(X,T),R).
 recorded(X,T,R) :- clause(idb(X,T),R).

We can take advantage of this, the other way around, as it is quite easy to write a simple Prolog interpreter, using the i.d.b.:


 asserta(G) :- recorda(interpreter,G,_).
 assertz(G) :- recordz(interpreter,G,_).
 retract(G) :- recorded(interpreter,G,R), !, erase(R).
 call(V) :- var(V), !, fail.
 call((H :- B)) :- !, recorded(interpreter,(H :- B),_), call(B).
 call(G) :- recorded(interpreter,G,_).

In YAP, much attention has been given to the implementation of the i.d.b., especially to the problem of accelerating the access to terms kept in a large list under the same key. Besides using the key, YAP uses an internal lookup function, transparent to the user, to find only the terms that might unify. For instance, in a data base containing the terms


 b
 b(a)
 c(d)
 e(g)
 b(X)
 e(h)

stored under the key k_49 "k/1", when executing the query


 :- recorded(k(_),c(_),R).

recorded would proceed directly to the third term, spending almost the time as if a(X) or b(X) was being searched. The lookup function uses the functor of the term, and its first three arguments (when they exist). So, recorded(k(_),e(h),_) would go directly to the last term, while recorded(k(_),e(_),_) would find first the fourth term, and then, after backtracking, the last one.

This mechanism may be useful to implement a sort of hierarchy, where the functors of the terms (and eventually the first arguments) work as secondary keys.

In the YAP's i.d.b. an optimized representation is used for terms without free variables. This results in a faster retrieval of terms and better space usage. Whenever possible, avoid variables in terms in terms stored in the i.d.b.

Functions:

1. static Int recorda(USES_REGS1):

1. static Int p_rcdap(USES_REGS1):

1. static Int p_rcda_at(USES_REGS1):

1. static Int recordz(USES_REGS1):

1. Int Yap_Recordz(Atom at, Term t2):

1. static Int p_rcdzp(USES_REGS1):

1. static Int p_rcdz_at(USES_REGS1):

1. static Int p_rcdstatp(USES_REGS1):

1. static Int p_drcdap(USES_REGS1):

1. static Int p_drcdzp(USES_REGS1):

1. static Int p_still_variant(USES_REGS1):

1. static int copy_attachments(CELL *ts USES_REGS):

1. static Term GetDBLUKey(PredEntry *ap):

1. static int UnifyDBKey(DBRef DBSP, PropFlags flags, Term t):

1. static int UnifyDBNumber(DBRef DBSP, Term t):

1. Int Yap_unify_immediate_ref(DBRef ref USES_REGS):

1. static Term GetDBTerm(DBTerm *DBSP, int src USES_REGS):

1. static Term GetDBTermFromDBEntry(DBRef DBSP USES_REGS):

1. static Int lu_nth_recorded(PredEntry *pe, Int Count USES_REGS):

1. static Int nth_recorded(DBProp AtProp, Int Count USES_REGS):

1. Int Yap_db_nth_recorded(PredEntry *pe, Int Count USES_REGS):

1. static Int p_db_key(USES_REGS1):

1. static Int i_recorded(DBProp AtProp, Term t3 USES_REGS):

1. static Int c_recorded(int flags USES_REGS):

1. static Int lu_recorded(PredEntry *pe USES_REGS):

1. static Int in_rded_with_key(USES_REGS1):

1. static Int recorded(USES_REGS1):

1. static Int co_rded(USES_REGS1):

1. static Int in_rdedp(USES_REGS1):

1. static Int co_rdedp(USES_REGS1):

1. static Int p_somercdedp(USES_REGS1):

1. static Int p_first_instance(USES_REGS1):

1. static UInt index_sz(LogUpdIndex *x):

1. static Int lu_statistics(PredEntry *pe USES_REGS):

1. static Int p_key_statistics(USES_REGS1):

1. static Int p_lu_statistics(USES_REGS1):

1. static Int p_total_erased(USES_REGS1):

1. static Int lu_erased_statistics(PredEntry *pe USES_REGS):

1. static Int p_key_erased_statistics(USES_REGS1):

1. static Int p_heap_space_info(USES_REGS1):

1. static void complete_lu_erase(LogUpdClause *clau):

1. static void EraseLogUpdCl(LogUpdClause *clau):

1. static void PrepareToEraseLogUpdClause(LogUpdClause *clau, DBRef dbr):

1. static void PrepareToEraseClause(DynamicClause *clau, DBRef dbr):

1. static yamop * find_next_clause(DBRef ref0 USES_REGS):

1. static void ErDBE(DBRef entryref USES_REGS):

1. static void ErasePendingRefs(DBTerm *entryref USES_REGS):

1. static void RemoveDBEntry(DBRef entryref USES_REGS):

1. static void MyEraseClause(DynamicClause *clau USES_REGS):

1. void Yap_ErDBE(DBRef entryref):

1. static void EraseEntry(DBRef entryref):

1. static Int p_jump_to_next_dynamic_clause(USES_REGS1):

1. void Yap_ErLogUpdCl(LogUpdClause *clau):

1. void Yap_ErCl(DynamicClause *clau):

1. static Int p_erase(USES_REGS1):

1. static Int p_increase_reference_counter(USES_REGS1):

1. static Int p_decrease_reference_counter(USES_REGS1):

1. static Int p_current_reference_counter(USES_REGS1):

1. static Int p_erase_clause(USES_REGS1):

1. static Int p_eraseall(USES_REGS1):

1. static Int p_erased(USES_REGS1):

1. static Int static_instance(StaticClause cl, PredEntry ap USES_REGS):

1. static Int exo_instance(Int i, PredEntry *ap USES_REGS):

1. static Int mega_instance(yamop code, PredEntry ap USES_REGS):

1. static Int p_instance(USES_REGS1):

1. Term Yap_LUInstance(LogUpdClause *cl, UInt arity):

1. static Int p_instance_module(USES_REGS1):

1. static void keepdbrefs(DBTerm *entryref USES_REGS):

1. static void ReleaseTermFromDB(DBTerm *ref USES_REGS):

1. static int NotActiveDB(DBRef my_dbref):

1. static DBEntry * NextDBProp(PropEntry *pp):

1. static Int cont_current_key_integer(USES_REGS1):

1. static Int cont_current_key(USES_REGS1):

1. static Int init_current_key(USES_REGS1):

1. Term Yap_FetchTermFromDB(void *ref):

1. Term Yap_FetchClauseTermFromDB(void *ref):

1. Term Yap_PopTermFromDB(void *ref):

1. static DBTerm * StoreTermInDB(Term t USES_REGS):

1. DBTerm * Yap_StoreTermInDB(Term t):

1. DBTerm * Yap_StoreTermInDBPlusExtraSpace(Term t, UInt extra_size, UInt *sz):

1. void Yap_init_tqueue(db_queue *dbq):

1. void Yap_destroy_tqueue(db_queue *dbq USES_REGS):

1. bool Yap_enqueue_tqueue(db_queue *father_key, Term t USES_REGS):

1. bool Yap_dequeue_tqueue(db_queue father_key, Term t, bool first, bool release USES_REGS):

1. static Int p_init_queue(USES_REGS1):

1. static Int p_enqueue(USES_REGS1):

1. static Int p_enqueue_unlocked(USES_REGS1):

1. static Int p_dequeue(USES_REGS1):

1. static Int p_dequeue_unlocked(USES_REGS1):

1. static Int p_peek_queue(USES_REGS1):

1. static Int p_clean_queues(USES_REGS1):

1. static Int p_slu(USES_REGS1):

1. static Int p_hold_index(USES_REGS1):

1. static Int p_fetch_reference_from_index(USES_REGS1):

1. static Int p_resize_int_keys(USES_REGS1):

1. void Yap_ReleaseTermFromDB(void *ref):

1. static Int p_install_thread_local(USES_REGS1):

1. void Yap_InitDBPreds(void):

1. void Yap_InitBackDB(void):