Sequential storage of terms

The database predicates in this section use keys which may be any Prolog term subject to the following restrictions:

• Keys are atomic values or structures where only the principal functor is used. For example, the key value derived from foo(a,1,bar(X)) is foo(,,_).
• Keys with names beginning with a dollar sign ($) are reserved for internal use by Arity/Prolog32.
• Floating point numbers may not be used as keys.

The Arity/Prolog32 database assigns a reference number to each term. Unlike a key, the reference number is unique for each term stored in the database. A reference number is written as a tilde (~) followed by a hexadecimal number such as:

~418FBC

Terms are doubly-linked together in a chain. The first and last terms stored under a key do not have a previous and next reference, respectively.

The database key predicates allow you to:

• Control the order in which terms appear in the database. You can add terms to the beginning, end, or middle of a chain of terms.
• Move freely through the database to locate terms. You can move forward or backward, or to a specific point within a chain.
• Delete a term or replace one term with another.
• Simply examine the terms that are stored in the database.

For flexibility, Arity/Prolog32 allows interleaved operations that access and update to terms stored under a Key. For example, a program could examine each term and delete it under if some condition holds. During the sequential retrieval of terms (using the recorded/3 or recorded_tro/3 predicate) the doubly-linked chain of references is used to locate the next term to be returned. And during the deletion of a term stored under a key (using the erase/1 or hard_erase/1 predicate) the doubly-linked list is adjusted. However, this flexibility can lead to serious errors. Arity/Prolog32 provides predicates described in the section that may be used to perform the operations your program requires without introducing such errors. A discussion of the considerations for when to use recorded/3, recorded_tro/3, erase/1 and hard_erase/1 is provided below.

All of the predicates described in this section perform their operations in the current workspace and data world.

Storing terms under database keys

recorda(+Key, +Term, -Ref)

The recorda/3 predicate adds Term at the beginning of the chain of terms having the same Key, creating the Key if it does not already exist. It returns the database reference Ref that has been assigned to the term.

recordz(+Key, +Term, -Ref)

The recordz/3 predicate adds a term at the end of the chain of terms having the same Key, creating the Key if it does not already exist. It returns the database reference Ref that has been assigned to the term.

record_after(+Ref, +Term, -NewRef)

record_before(+Ref, +Term, -NewRef)

The record_after/3 and record_before/3 predicates insert a term into a chain of terms after and before the given Ref, respectively. Each predicate returns the database reference for the newly stored term to NewRef.

replace(+Ref, +Term)

The replace/2 predicate looks up the term that has the given database reference and replaces that term with the one you have specified.

replace(+Ref, +Term, -Ref1)

The replace/3 predicate is similar to replace/2 except that it may move the location of the term in the database if as a result better use of space results. If the term is stored under a database key, then it will remain in the same relative position in the key's sequence of terms. If the term does not move, then Ref1 will be equal to Ref.

load_key(+File, +Key)

load_key(+File, +Key, -Lines)

The load_key/2 and load_key/3 predicates are used to read a File as strings, line by line, recording the strings under a database Key. The load_key/3 predicate returns the number of Lines actually read.

begin_choices(+Key)

end_choices(+Key)

The begin_choices/1 predicate has effect in one specific context: During the process of consulting code, any terms that appear between begin_choices/1 and its matching end_choices/1 are loaded into the database under Key.

You specify a key and the terms to record by placing them in a file according to the following example:

begin_choices(Key).
Term1.
...
TermN.
end_choices(Key).

Reviewing Terms stored under database keys

instance(+Ref, -Term)

The instance predicate returns the term that is associated with the database reference Ref.

recorded(+Key, +Term, -Ref)

recorded_tro(+Key, +Term, -Ref)

The recorded/3 and recorded_tro/3 predicates unify terms stored under Key to Term and unify Ref with the Term's database reference. Both predicates are non-deterministic and in most situations behave identically.

Unlike the recorded/3 predicate, the recorded_tro/3 predicate is written to "look ahead" to the term beyond the term that is being returned. This is done so that recorded_tro/3 can take advantage of "tail recursion optimization." Tail recursion optimization is an optimization technique whereby the system recognizes the completion of processing and determines that is can reuse stack space. In addition, there are important considerations for when to use one or the other predicates if terms are being added or erased from Key during an active use of recorded/3 or recorded_tro/3. Discussion of these considerations is taken up below.

recorded_nth(+Key, +Nth, -Term, -Ref)

The recorded_nth/4 predicate returns the Nth Term stored under the specified database Key and the database reference Ref associated with the Term.

recorded_ref(+InitRef, +Dir, -Term, -Ref)

The recorded_ref/4 predicate returns through backtracking the terms recorded before or after an initial database reference InitRef. If Dir = -1, the terms stored before InitRef are returned. If Dir=1, the terms are stored after InitRef are returned. The recorded_ref/4 predicate does not return the Term associated with InitRef.

For the purposes of the discussion regarding the choice of use between recorded/3 and recorded_tro/3, the recorded_ref/4 predicate operates like recorded/3. There is no tro version of recorded_ref/4.

recorded_terms(+Key, +Term, -List)

The recorded_terms/3 predicate is used to gather in a List all terms stored under a database Key that unify with a provided Term. Terms are returned in the List in the order they were stored in under the database Key. If Term is provided as a variable, then all terms stored in the Key will be returned.

key(+Key, -Ref)

The key/2 predicate returns the reference Ref for the specified Key. Ref does not have an associated stored term and cannot be used with instance/2.

key_count(+Key, -Count)

The key_count/2 predicate returns a Count of the number of terms stored under a given database Key.

keys(-Key)

The keys/1 predicate returns through backtracking each Key used in the current data world.

nref(+Ref, -NextRef)

pref(+Ref, -PrevRef)

The nref/2 and pref/2 predicates return the reference number of the next or previous term a chain of terms, respectively. These predicates fail if there is no next or previous term in the chain. Note that the chain may have been created from an orphan ref or by storing terms under a key.

mth_ref(+Ref, +Dir, -NextRef)

The mth_ref/3 predicate is a more general form of the nref and pref predicates. You specify a Direction (either -1 for previous or 1 for next) and the nth_ref/3 predicate returns the Next database reference.

nth_ref(+Key, +N, -Ref)

The nth_ref/3 predicate returns the database reference for the term some number of positions away from the top of a chain of terms. The Key argument names the key under which the term is stored. The N argument gives the number of positions away from the top of the key the desired term can be found. N can be positive or negative. The nth_ref/3 predicate fails if the absolute value of N is greater than the number of terms stored under a key.

sortkey(+Key)

The sortkey/1 predicate performs a quicksort on the terms stored under the specified database Key. The terms are sorted in the standard order and replaced in the key. The term lowest in sort order is placed first, the highest term is placed last. Duplicates are not removed. Refs assigned to terms under Key may be changed by sortkey/1.

write_key(+Key, +File, +Backup)

The write_key/3 predicate is provided for writing a Key containing terms to a file. All terms stored under Key are written to the File specified using the write/2 predicate (operators are used, no quoting). If Backup=1 and there currently exists a version of file, the old file is saved as a .BAK file.

Removing Terms from the Database

The predicates described in this section can be used to remove a single term or all terms from a database key. There are two methods for removing a term from the database, either by a soft erase (erase/1) or a hard erase (hard_erase/1). A discussion of the considerations for when to use recorded/3, recorded_tro/3, erase/1 and hard_erase/1 is provided later in this section.

erase(+Ref)

The erase/1 predicate performs a soft erase removing the term that has the given database reference number. The system keeps track of the terms that have been erased with the erase predicate. These terms can be removed with the expunge predicate. In addition, the nref and pref pointers remain so that the database reference can be used with predicates, such as nref/2 or recorded_ref/4.

If a term is soft erased (using erase/1), then the term is marked for removal, most of the space taken by the stored term is released but the previous and next reference pointers remain intact. This enables nref/2, pref/3 and recorded/3 to execute without error, but an attempt to use instance/2 with the soft erased reference results in an error. A soft erased record may be permanently deleted using expunge/0 or by eraseall/0. The following demonstrates the use of erase/1 and the effects of soft erasure.

?- recordz(bar, 1, R).
R = ~418FAC
yes
?- recordz(bar, 2, R).
R = ~418FA8
yes
?- recordz(bar, 3, R).
R = ~418FA4
yes

?- erase(~418fa8).
yes

?- recorded(bar, X, R).
X = 1
R = ~418FAC ->;
X = 3
R = ~418FA4 ->;
no

?- nref(~418fa8, X).
X = ~418FA4
yes

?- instance(~418fa8, X).
ERR 200 Illegal use of an erased ref or key

expunge

The expunge/0 predicate is necessary when your program requires the database space to be recovered after the use of the erase/1 or retract/1 predicates. When you use the erase/1 or retract/1 predicates, the system keeps a record of each term that is erased (the pointers to the erased terms remain). The expunge/0 predicate eliminates the references to the erased terms and thus frees this space for use.

You do not have to use the expunge/0 predicate each time you use erase/1 or retract/1. Generally, you should use the expunge predicate in the following circumstances:

• After your program uses erase or retract a number of times.
• Immediately before saving the database using the save predicate, provided you are sure that the you will not be using the eliminated references after the save.

It is important to note that expunge/0 should only be used after you are sure that eliminating the record of erased terms will not result in the elimination of a reference used later in your program. For instance, if you have a backtracking procedure which uses recorded/3 to return a term and erase/1 and recordz/3 to erase and add terms, you would not use expunge/0 until after this procedure was completed. This is because recorded uses the references for the term it is returning to determine the reference to the next term.

eraseall(+Key)

The eraseall/1 predicate removes all the terms that are stored under the specified key.

hard_erase(+Ref)

The hard_erase/1 predicate erases the term with the specified reference number. However, unlike the erase/1 predicate, the hard_erase/1 predicate does not keep track of the terms which have been erased. As such, the hard_erase/1 predicate should only be used if your program is designed so that there is no danger of the system referencing a database term that you have previously eliminated. Such a situation can occur when you have a backtracking procedure which returns a term using recorded_tro and then erases that term.

Since hard_erase/1 does not keep track of erased terms, it is not necessary to use the expunge/0 predicate in conjunction with hard_erase/1.

When to use recorded/3, recorded_tro/3, erase/1, and hard_erase/1

The recorded/3 and recorded_tro/3 and the erase/1 and hard_erase/1 predicates perform similar functions. However, depending on the context in which they are used, it is advisable, and sometimes mandatory, that one predicate be used over another.

The following table outlines the use of recorded/3 and recorded_tro/3 in conjunction with the **erase/1, hard_erase/1, record_after/3, record_before/3, recorda/3 and recordz/3 predicates.

Notes:

• Note 1: No further uses of a reference that has been removed by hard_erase/1 are allowed.

• Note 2: When recorded_tro/3 has returned the last term stored under a key, no more choices will be returned. The use of record_after/3 and recordz/3 will affect only subsequent uses of recorded_tro/3.

If your are using erase/1, you should use the expunge/0 predicate when you are sure all erased references will not be used in future execution.

The primary disadvantage of the recorded/3 predicate is that a choice point remains after the last record is found which inhibits tail recursion optimization. While generally a minor consideration in program efficiency, the use of recorded/3 may be important in some circumstances.

The primary disadvantage of the erase/1 predicate is that space is not fully recovered at the time erase/1 executes. The use of expunge/0 may be expensive in time for large databases.

In general, you should use the recorded_tro/3 and hard_erase/1 predicates rather than the recorded/3 and erase/1 predicates.

It is useful to see how the recorded_tro/3 and recorded/3 predicates are implemented in order to understand their use. The recorded_tro/3 predicate used by Arity/Prolog32 is implemented similar to the following:

recorded_tro(Key, Term, Ref) :-
    key(Key, KRef),              % Ref for Key
    nref(KRef, R),               % Ref for first term
    tsearch(R, Term, Ref).

tsearch(R, Term, Ref) :-
    nref(R, R1),
    !,
    tsearch1(R, Term, Ref, R1).
tsearch(R, Term, R) :-
    instance(R, Term).

tsearch1(R, Term, R, _) :-
    instance(R, Term).
tsearch1(_, Term, Ref, NRef) :-
    tsearch(NRef, Term, Ref).

What this definition shows is that the recorded_tro/3 predicate keeps track of the current reference as well as the next reference for terms in the database. This is done so that recorded_tro/3 can take advantage of tail recursion optimization. However, if you have a procedure in which you add a record directly following the current record returned by recorded_tro/3, that record will not be returned upon backtracking.

In contrast, the recorded/3 predicate does not use a look ahead reference. It is implemented similar to the following:

recorded(Key,Term,Ref) :-
    key(Key, KRef),
    nref(KRef, R),
    search(R, Term, Ref).

search(R, Term, R) :-
    instance(R, Term).
search(R, Term, Ref) :-
    nref(R, R1),
    search(R1,Term,Ref).

With the recorded/3 predicate, you will not encounter a problem if you have a procedure in which you eliminate a term and add a new term to the database and then backtrack to the recorded predicate. However, recorded/3 does not take advantage of tail recursion optimization and therefore may not be as efficient as recorded_tro/3.