YAP 7.1.0
Internal Data Base

Some programs need global information for, e.g. More...

Detailed Description

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).
If you like being short, use T instead of YapTerm.
Definition: yapt.hh:266

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/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

Modules

 Atom to Atomic Family of Built-ins.
 Maintain a light-weight map where the key is an atom, and the value can be any constant.
 

Class Documentation

◆ db_globs

struct db_globs

Definition at line 208 of file dbase.c.

Public Attributes

link_entry * lr
 
link_entry * LinkAr
 
DBReftofref
 
DBRef found_one
 
UInt sz
 

Member Data Documentation

◆ found_one

DBRef found_one

Definition at line 219 of file dbase.c.

◆ LinkAr

link_entry * LinkAr

Definition at line 209 of file dbase.c.

◆ lr

link_entry* lr

Definition at line 209 of file dbase.c.

◆ sz

UInt sz

Definition at line 220 of file dbase.c.

◆ tofref

DBRef* tofref

Definition at line 213 of file dbase.c.

◆ visitel

struct visitel

Definition at line 585 of file dbase.c.

Public Attributes

CELL * addr
 

Member Data Documentation

◆ addr

CELL* addr

Definition at line 585 of file dbase.c.

◆ recorda_at/3

class recorda_at/3

recorda_at(+ R0, T,- R)

Makes term T the record preceding record with reference R0, and unifies R with its reference

◆ recordz/3

class recordz/3

recordz(+ K, T,- R)

Makes term T the last record under key K and unifies R with its reference

◆ recordz_at/3

class recordz_at/3

recordz_at(+ R0, T,- R)

Makes term T the record following record with reference R0, and unifies R with its reference

◆ key_statistics/4

class key_statistics/4

key_statistics(+ K,- Entries,- Size,- IndexSize)

Returns several statistics for a key K Currently, it says how many entries we have for that key, Entries, what is the total size spent on entries, Size, and what is the amount of space spent in indices

◆ erase/1

class erase/1

erase(+ R)

The term referred to by R is erased from the internal database If reference R does not exist in the database, erase just fails

◆ eraseall/1

class eraseall/1

eraseall(+ K)

All terms belonging to the key K are erased from the internal database The predicate always succeeds

◆ erased/1

class erased/1

erased(+ R)

Succeeds if the object whose database reference is R has been erased

◆ instance/2

class instance/2

instance(+ R,- T)

If R refers to a clause or a recorded term, T is unified with its most general instance If R refers to an unit clause C, then T is unified with _C_ :- true When R is not a reference to an existing clause or to a recorded term, this goal fails

◆ recorded/3

class recorded/3

Definition at line 5371 of file dbase.c.

◆ recorda/3

class recorda/3

Macro Definition Documentation

◆ AllocDBSpace

#define AllocDBSpace (   V)    ((DBRef)Yap_AllocCodeSpace(V))

Definition at line 163 of file dbase.c.

◆ AtomHash

#define AtomHash (   t)    (Unsigned(t) >> 4)

Definition at line 191 of file dbase.c.

◆ CheckDBOverflow

#define CheckDBOverflow (   X)
Value:
if (CodeMax + X >= (CELL *)visited - 1024) { \
goto error; \
}

Definition at line 593 of file dbase.c.

◆ CheckVisitOverflow

#define CheckVisitOverflow ( )
Value:
if ((CELL *)tovisit + 1024 >= ASP) { \
goto error2; \
}

Definition at line 599 of file dbase.c.

◆ db_check_trail

#define db_check_trail (   x)
Value:
{ \
if (Unsigned(dbg->tofref) == Unsigned(x)) { \
goto error_tr_overflow; \
} \
}

Definition at line 304 of file dbase.c.

◆ DB_MARKED

#define DB_MARKED (   d0)    ((CELL *)(d0) < CodeMax && (CELL *)(d0) >= tbase)

Definition at line 652 of file dbase.c.

◆ DB_UNWIND_CUNIF

#define DB_UNWIND_CUNIF ( )
Value:
while (visited < (visitel *)AuxSp) { \
RESET_VARIABLE(visited->addr); \
visited++; \
}
Definition: dbase.c:585

Definition at line 586 of file dbase.c.

◆ DBLength

#define DBLength (   V)    (sizeof(DBStruct) + (Int)(V) + CellSize)

Definition at line 162 of file dbase.c.

◆ DISCONNECT_OLD_ENTRIES

#define DISCONNECT_OLD_ENTRIES   1

Definition at line 142 of file dbase.c.

◆ DualHashFieldMask

#define DualHashFieldMask   ((CELL)0xffffL)

Definition at line 183 of file dbase.c.

◆ FourHashFieldMask

#define FourHashFieldMask   ((CELL)0xffffffffL)

Definition at line 185 of file dbase.c.

◆ FreeDBSpace

#define FreeDBSpace (   V)    Yap_FreeCodeSpace(V)

Definition at line 164 of file dbase.c.

◆ FrstDBRef

#define FrstDBRef (   V)    ((V)->First)

Definition at line 159 of file dbase.c.

◆ FunctorHash

#define FunctorHash (   t)    (Unsigned(t) >> 4)

Definition at line 192 of file dbase.c.

◆ HashFieldMask

#define HashFieldMask   ((CELL)0xffL)

Definition at line 182 of file dbase.c.

◆ InQueue

#define InQueue   32

Definition at line 157 of file dbase.c.

◆ LARGE_IDB_LINK_TABLE

#define LARGE_IDB_LINK_TABLE   1

Definition at line 195 of file dbase.c.

◆ MarkThisRef

#define MarkThisRef (   Ref)    ((Ref)->NOfRefsTo++)

Definition at line 580 of file dbase.c.

◆ MkCode

#define MkCode   CodeDBBit

Definition at line 153 of file dbase.c.

◆ MkFirst

#define MkFirst   1

Definition at line 152 of file dbase.c.

◆ MkIfNot

#define MkIfNot   16

Definition at line 156 of file dbase.c.

◆ MkLast

#define MkLast   4

Definition at line 154 of file dbase.c.

◆ NextDBRef

#define NextDBRef (   V)    ((V)->Next)

Definition at line 160 of file dbase.c.

◆ NumberHash

#define NumberHash (   t)    (Unsigned(IntOfTerm(t)))

Definition at line 193 of file dbase.c.

◆ ONE_FIELD_SHIFT

#define ONE_FIELD_SHIFT   8

Definition at line 187 of file dbase.c.

◆ Register

#define Register   register

Definition at line 147 of file dbase.c.

◆ SIZEOF_LINK_ENTRY

#define SIZEOF_LINK_ENTRY   4

Definition at line 200 of file dbase.c.

◆ THREE_FIELDS_SHIFT

#define THREE_FIELDS_SHIFT   24

Definition at line 189 of file dbase.c.

◆ ToSmall

#define ToSmall (   V)    ((link_entry)(Unsigned(V) >> 3))

Definition at line 169 of file dbase.c.

◆ TripleHashFieldMask

#define TripleHashFieldMask   ((CELL)0xffffffL)

Definition at line 184 of file dbase.c.

◆ TWO_FIELDS_SHIFT

#define TWO_FIELDS_SHIFT   16

Definition at line 188 of file dbase.c.

◆ WithRef

#define WithRef   8

Definition at line 155 of file dbase.c.

Typedef Documentation

◆ link_entry

typedef BITS32 link_entry

Definition at line 199 of file dbase.c.

Function Documentation

◆ Yap_db_nth_recorded()

Int Yap_db_nth_recorded ( PredEntry pe,
Int Count  USES_REGS 
)

Definition at line 3027 of file dbase.c.

◆ Yap_dequeue_tqueue()

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

Definition at line 5021 of file dbase.c.

◆ Yap_destroy_tqueue()

void Yap_destroy_tqueue ( db_queue *dbq  USES_REGS)

Definition at line 4986 of file dbase.c.

◆ Yap_enqueue_tqueue()

bool Yap_enqueue_tqueue ( db_queue father_key,
Term t  USES_REGS 
)

Definition at line 4998 of file dbase.c.

◆ Yap_ErCl()

void Yap_ErCl ( DynamicClause clau)

Definition at line 4068 of file dbase.c.

◆ Yap_ErDBE()

void Yap_ErDBE ( DBRef  entryref)

Definition at line 4189 of file dbase.c.

◆ Yap_ErLogUpdCl()

void Yap_ErLogUpdCl ( LogUpdClause clau)

Definition at line 4062 of file dbase.c.

◆ Yap_EvalMasks()

CELL Yap_EvalMasks ( register Term  tm,
CELL *  keyp 
)

Definition at line 577 of file dbase.c.

◆ Yap_FetchClauseTermFromDB()

Term Yap_FetchClauseTermFromDB ( void *  ref)

Definition at line 4922 of file dbase.c.

◆ Yap_FetchTermFromDB()

Term Yap_FetchTermFromDB ( void *  ref)

Definition at line 4915 of file dbase.c.

◆ Yap_FindLUIntKey()

PredEntry * Yap_FindLUIntKey ( Int  key)

Definition at line 2679 of file dbase.c.

◆ Yap_init_tqueue()

void Yap_init_tqueue ( db_queue dbq)

Definition at line 4979 of file dbase.c.

◆ Yap_InitBackDB()

void Yap_InitBackDB ( void  )

Definition at line 5450 of file dbase.c.

◆ Yap_LUInstance()

Term Yap_LUInstance ( LogUpdClause cl,
UInt  arity 
)

Definition at line 4679 of file dbase.c.

◆ Yap_new_ludbe()

LogUpdClause * Yap_new_ludbe ( Term  t,
PredEntry pe,
UInt  nargs 
)

Definition at line 1936 of file dbase.c.

◆ Yap_PopTermFromDB()

Term Yap_PopTermFromDB ( void *  ref)

Definition at line 4929 of file dbase.c.

◆ Yap_Recordz()

Int Yap_Recordz ( Atom  at,
Term  t2 
)

Definition at line 2177 of file dbase.c.

◆ Yap_ReleaseTermFromDB()

void Yap_ReleaseTermFromDB ( void *  ref)

Definition at line 5312 of file dbase.c.

◆ Yap_StoreTermInDB()

DBTerm * Yap_StoreTermInDB ( Term  t,
int  nargs 
)

Definition at line 4962 of file dbase.c.

◆ Yap_StoreTermInDBPlusExtraSpace()

DBTerm * Yap_StoreTermInDBPlusExtraSpace ( Term  t,
UInt  extra_size,
UInt *  sz 
)

Definition at line 4967 of file dbase.c.

◆ Yap_unify_immediate_ref()

Int Yap_unify_immediate_ref ( DBRef ref  USES_REGS)

Definition at line 2509 of file dbase.c.

Macros

#define DISCONNECT_OLD_ENTRIES   1
 
#define Register   register
 
#define MkFirst   1
 
#define MkCode   CodeDBBit
 
#define MkLast   4
 
#define WithRef   8
 
#define MkIfNot   16
 
#define InQueue   32
 
#define FrstDBRef(V)   ((V)->First)
 
#define NextDBRef(V)   ((V)->Next)
 
#define DBLength(V)   (sizeof(DBStruct) + (Int)(V) + CellSize)
 
#define AllocDBSpace(V)   ((DBRef)Yap_AllocCodeSpace(V))
 
#define FreeDBSpace(V)   Yap_FreeCodeSpace(V)
 
#define ToSmall(V)   ((link_entry)(Unsigned(V) >> 3))
 
#define HashFieldMask   ((CELL)0xffL)
 
#define DualHashFieldMask   ((CELL)0xffffL)
 
#define TripleHashFieldMask   ((CELL)0xffffffL)
 
#define FourHashFieldMask   ((CELL)0xffffffffL)
 
#define ONE_FIELD_SHIFT   8
 
#define TWO_FIELDS_SHIFT   16
 
#define THREE_FIELDS_SHIFT   24
 
#define AtomHash(t)   (Unsigned(t) >> 4)
 
#define FunctorHash(t)   (Unsigned(t) >> 4)
 
#define NumberHash(t)   (Unsigned(IntOfTerm(t)))
 
#define LARGE_IDB_LINK_TABLE   1
 
#define SIZEOF_LINK_ENTRY   4
 
#define db_check_trail(x)
 
#define MarkThisRef(Ref)   ((Ref)->NOfRefsTo++)
 
#define DB_UNWIND_CUNIF()
 
#define CheckDBOverflow(X)
 
#define CheckVisitOverflow()
 
#define DB_MARKED(d0)   ((CELL *)(d0) < CodeMax && (CELL *)(d0) >= tbase)
 

Typedefs

typedef BITS32 link_entry
 
typedef struct db_globs dbglobs
 

Functions

CELL Yap_EvalMasks (register Term tm, CELL *keyp)
 
LogUpdClauseYap_new_ludbe (Term t, PredEntry *pe, UInt nargs)
 
Int Yap_Recordz (Atom at, Term t2)
 
Int Yap_unify_immediate_ref (DBRef ref USES_REGS)
 
PredEntryYap_FindLUIntKey (Int key)
 
Int Yap_db_nth_recorded (PredEntry *pe, Int Count USES_REGS)
 
void Yap_ErLogUpdCl (LogUpdClause *clau)
 
void Yap_ErCl (DynamicClause *clau)
 
void Yap_ErDBE (DBRef entryref)
 
Term Yap_LUInstance (LogUpdClause *cl, UInt arity)
 
Term Yap_FetchTermFromDB (void *ref)
 
Term Yap_FetchClauseTermFromDB (void *ref)
 
Term Yap_PopTermFromDB (void *ref)
 
DBTermYap_StoreTermInDB (Term t, int nargs)
 
DBTermYap_StoreTermInDBPlusExtraSpace (Term t, UInt extra_size, UInt *sz)
 
void Yap_init_tqueue (db_queue *dbq)
 
void Yap_destroy_tqueue (db_queue *dbq USES_REGS)
 
bool Yap_enqueue_tqueue (db_queue *father_key, Term t USES_REGS)
 
bool Yap_dequeue_tqueue (db_queue *father_key, Term t, bool first, bool release USES_REGS)
 
void Yap_ReleaseTermFromDB (void *ref)
 
void Yap_InitBackDB (void)