Modification of the Database

XSB provides an array of features for modifying the dynamic database. Using assert/1, clauses can be asserted using first-argument indexing in a manner that is now standard to Prolog implementations. While this is the default behavior for XSB, other behavior can be specified using the (executable) directives index/3 and index/2. For instance, dynamic clauses can be declared to have multiple or joint indexes, while this indexing can be either hash-based as is typical in Prolog systems or based on tries. No matter what kind of indexing is used, space is dynamically allocated when a new clause is asserted and, unless specified otherwise, released when it is retracted. Furthermore, the size of any index table expands dynamically as clauses are asserted.

Consider first dynamic predicates that use traditional hash-based indexing. XSB asserts WAM code for such clauses, leading to execution times similar to compiled code for unit and binary clauses. Furthermore, tabling can be used with a dynamic predicate by explicitly declaring a predicate to be both dynamic and tabled. For clauses that are asserted as WAM code, the ``immediate semantics'' of dynamic predicates is used, not the so-called ``logical semantics'' of assert/retract [33]. This means that significant care must be taken when modifying the definition of a predicate which is currently being executed. Notice that this makes some operations difficult. For example, one might try to retract from dynamically asserted predicates, p/1 and q/1, exactly their intersection, by issuing the following query:

:- p(X), q(X), retract(p(X)), retract(q(X)), fail.

Neither retract/1 nor retractall/1 support this behavior, due to their techniques for space reclamation. One alternative is to use findall/3 to collect the intersection first, before retracting. Another is to use the predicates retract_nr/1 and reclaim_space/1, described below.

Asserting clauses as WAM code might be considerably slow for some applications. To remedy this, XSB provides an alternative to assert/1 which implements assert's functionality using the trie-based tabling data structures [39]. Though trie-based dynamic code can be created (and usually executed) significantly faster than using assert/1, users of the following predicates should be aware that trie-based assert can be used only for unit clauses where a relation is viewed as a set, and where the order of the facts is not important.

XSB does not at this time fully support dynamic predicates defined within compiled code. The only way to generate dynamic code is by explicitly asserting it, or by using the standard predicate load_dyn/1 to read clauses from a file and assert them (see the section Asserting Dynamic Code in Volume 2). There is a dynamic/1 predicate (see page ) that declares a predicate within the system so that if the predicate is called when no clauses are presently defining it, the call will quietly fail instead of issuing an ``Undefined predicate'' error message.

assert(+Clause)

adds a dynamic clause, Clause, to the database. Clause must be of one of the forms: Head or Head :- Body. Note that because of the precedence of :-/2, using the second form requires an extra set of parentheses: assert((Head :- Body)). Default: first-argument indexing.

asserta(+Clause)

If the index specification for the preicate is not tries, this predicate adds a dynamic clause, Clause, to the database before any other clauses for the same predicate currently in the database. If the index specification for the predicate is trie, the clause is asserted arbitrarily within the trie, and a warning message sent to stderr.

assertz(+Clause)

If the index specification for the predicate is not tries, this predicate adds a dynamic clause, Clause, to the database after any other clauses for the same predicate currently in the database. If the index specification for the predicate is trie, the clause is asserted arbitrarily within the trie, and a warning message sent to stderr.

retract(+Clause)

removes through backtracking all clauses in the database that match with Clause. Clause must be of one of the forms: Head or Head :- Body. Note, that because of the precedence of :-/2, using the second form requires an extra set of parentheses: retract((Head :- Body)). Space is reclaimed when a clause is retracted.

retractall(+Head)

removes every clause in the database whose head matches with Head. The predicate whose clauses have been retracted retains the dynamic property (contrast this behavior with that of predicates abolish/[1,2] below). Predicate retractall/1 is determinate and always succeeds. The term Head is not further instantiated by this call.

abolish(+PredSpec)

Removes the definition of the specified predicate. PredSpec is of the form Pred/Arity. Everything about the abolished predicate is completely forgotten by the system (including the dynamic property). There is also an abolish/2 which takes Pred and Arity as its two arguments.

clause(+Head,?Body)

Returns through backtracking all dynamic clauses in the database whose head matches Head and Body matches Body. For facts the Body is true.

retract_nr(+Clause)

Performs just as retract/1 does, except that it does not reclaim the space used by the retracted clause. This is provided to allow programmers to modify dynamic clauses while executing them (a practice that is discouraged.) For example, to retract an intersection, as described above, one could do:

:- p(X), q(X), retract_nr(p(X)), retract_nr(q(X)), fail.

In order to reclaim space after using retract_nr/1, see reclaim_space/1 below. Predicate retract_nr/1 is not a standard predicate and must be imported from module assert. retract_nr/1 is provided for (partial) compatibility with the retract/1 predicate of SB-Prolog.

reclaim_space(+Head)

Runs through the dynamic code for the predicate indicated by Head, and reclaims space for any clauses that have been deleted from that predicate by retract_nr/1. This cannot safely be used when execution is still within some invocation of the specified predicate, or will backtrack into such a scope. To complete our example of retracting the intersection of dynamic predicates:

:- p(X), q(X), retract_nr(p(X)), retract_nr(q(X)), fail ;
reclaim_space(p(_)), reclaim_space(q(_)).

would do the trick. Notice that the reclaim_space calls must be made after execution has completely failed out of choice points for q(X) and p(X). Predicate reclaim_space/1 is not standard but must be imported from module assert. As with retract_nr, the use of this predicate is discouraged; it is provided for (partial) compatibility with SB-Prolog.

index(+PredSpec, +IndexSpec)

In general, XSB supports hash-based indexing on various arguments or combinations of arguments, along with trie-based indexing. The availability of various kinds of indexing depends on whether code is static (e.g. compiled) or dynamic (e.g. asserted or loaded with load_dyn/1). The executable directive index/2 does not re-index an already existing predicate but takes effect only for clauses asserted after the directive has been given. Index directives can be given to the compiler as part of source code or executed during program execution (analogously to op/3).

• Hash-based Indexing
  • Static Predicates In this case IndexSpec must be a non-negative integer which indicates the argument on which an index is to be constructed. If IndexSpec is 0, then no index is kept (possibly an efficient strategy for predicates with only one or two clauses.)
  • Dynamic Predicates For a dynamic predicate, (to which no clauses have yet been asserted), IndexSpec is either an IndexElt or a list of IndexElts. Each IndexElt defines an index and specifies an argument or group of arguments that make up the search key of the index. An argument is indicated by a small integer (ArgNo) indicating the argument number (starting from 1) to use in the index. An argument indicator may optionally be annotated as *(ArgNo). The argument number alone indicates that only the main functor symbol of the indicated argument will participate in the index. When annotated with the asterisk, the first 5 fields in the corresponding term (in a depth-first traversal of the term) will be used in the index. If there are fewer than 5, they all will be used. If any of the first 5 is a variable, then the index cannot be used.

    An index is usually on a single argument, in which case the IndexElt consists of a single argument indicator. However, sometimes one wants an index on multiple arguments, meaning that the values of several arguments are to be concatenated to create the search key of the index. Such a multi-argument (or joint) index is indicated by using an IndexElt that has up to 3 argument indicators separated by the + (plus) operator, e.g., 1+2+3.

    For example, index(p/3,[2,1]) indicates that clauses asserted to the predicate p/3 should be indexed on both the second and the first argument. Subsequent calls to p/3 will first check to see if the second argument is nonvariable, and if so use that index, using the main functor symbol of that argument. If the second argument is variable, it will next check to see if the first argument is nonvariable and if so, use that index, built on the main functor symbol of the first argument.

    index(p/3,[*(2),1]) would result in similar behavior as the previous example, but the first index to be tried (on the second argument) would be built using more of the term value in that second argument position (not just the main functor symbol.)

    As another example, one could specify: index(p/5,[1+2,1,4]). After clauses are asserted to it, a call to p/5 would first check to see if both the first and second arguments are nonvariable and if so, use an index based on both those values. Otherwise, it would see if the first argument is nonvariable and if so, use an index based on it. Otherwise, it would see if the fourth argument is nonvariable and if so use an index based on it. As a last resort, it would use no index but backtrack through all the clauses in the predicate. In all these cases, the indexes are built using only the main functor symbol in the indicated argument position. (Notice that it may well make sense to include an argument that appears in a joint specification later alone, as 1 in this example, but it never makes sense forcing the single argument to appear earlier. In that case the joint index would never be used.)

    If we want to use similar indexing on p/5 of the previous example, except say argument 1 takes on complex term values and we want to index on more of those terms, we might specify the index as index(p/5,[*(1)+2,*(1),4]).

• Trie-based Indexing The executable declaration index(Predspec,trie) causes clauses for Predspec to be asserted using tries (see [39], which is available through the XSB web page). The name trie indexing is something of a misnomer since the trie itself both indexes the term and represents it. In XSB, the above trie index is formed using a left-to-right traversal of the unit clauses. These indexes can be very effective if discriminating information lies deep within a term, and if there is sharing of left-prefixes of a term, can reduce the space needed to represent terms. Furthermore, asserting a unit clause as a trie is much faster than asserting it using default WAM code.

  Despite these advantages, representing terms as tries leads to semantic differences from asserted code, of which the user should be aware. First, the order of clauses within a trie is arbitrary: using asserta/1 or assertz for a predicate currently using trie indexing will give the same behavior as using assert. Also, the current version of XSB only allows trie indexing for unit clauses.

  Trie-based indexing is available only for dynamic predicates.

dynamic(+PredSpec)

is an executable predicate which converts a predicate specified as (Predicate/Arity) to a dynamic predicate. If Predicate is not previously defined, it will be initialized to empty (so that calls to it quietly fail, instead of issuing ``Undefined predicate'' error messages.) If the predicate is previously defined and dynamic, dynamic/1 is a noop. If previously defined as compiled, Predicate will be converted to dynamic, which means that clauses can be added, although the compiled portion cannot be manipulated. Note that dynamic/1 can be used like a compiler directive, since it will be passed through to be executed when the module is loaded. Note, however, that the semantics is different from that of the standard [25] when the file contains clauses defining the so-specified predicate.

table(+PredSpec)

is an executable predicate, where PredSpec is a predicate specification for a dynamic predicate. (This is also a compiler directive when PredSpec specifies a compiled predicate. See the section of this manual on compiler directives.) This predicate declares a dynamic predicate to be tabled. It simply saves information to be used at the time of assert and so it must be called before any clauses are asserted into the specified predicate in order for the predicate to be tabled.