6.13 Asserting, Retracting, and Other Database Modifications

XSB provides an array of features for modifying the dynamic database. As a default, using assert/1, clauses can be asserted using first-argument indexing in a manner that is now standard to Prolog implementations. However, a variety of other behaviors 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, and 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 after it is retracted. Furthermore, the size of any index table expands dynamically as clauses are asserted.

All dynamic predicates are compiled into SLG-WAM code, however the manner of their compilation may differ, and the differences in compilation affect the semantics for the predicate. If a dynamic predicate $P/n$ is given an indexing directive of trie, clauses for $P/n$ will be compiled using trie instructions; otherwise clauses for $P/n$ will be compiled into SLG-WAM instructions along the lines of static predicates.

Consider first dynamic predicates that use any indexing other than trie - including multiple or joint indices and star indexing. XSB asserts WAM code for such clauses so that that the execution time of dynamic code is similar to compiled code for unit and binary clauses. Furthermore, tabling can be used by explicitly declaring a predicate to be both dynamic and tabled. In Version 3.0, when the clause of a dynamic predicate is asserted as WAM code, the ``immediate semantics'' rather than the ISO Semantics of assert/retract [40]. The immediate semantics allows assert and retract to be fast and spatially efficient, but requires that significant care must be taken when modifying the definition of a predicate which is currently being executed.

If a dynamic predicate is given an indexing directive of trie, clauses of the predicate are compiled (upon a call assert/1) using trie instructions as described in [46]. Creation of trie-based dynamic code is significantly faster than creation of other dynamic code, and execution time may also be faster. However, trie-based predicates can only be used 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.

asserta(+Clause)

If the index specification for the predicate is not trie, 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.

Note that because of the precedence of :-/2, asserting a clause containing this operator requires an extra set of parentheses: assert((Head :- Body)).

Error Cases

• Clause is not instantiated
  • instantiation_error
• Clause is not a callable clause.
  • domain_error(callable,Clause)
• Clause has a head that is a static built-in
  • permission_error(modify,builtin,Clause)
• Clause has a head that is a static user predicate
  • permission_error(modify,static,Clause)

assertz(+Clause)

If the index specification for the predicate is not trie, 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. Error cases are as with asserta/1.

Note that because of the precedence of :-/2, asserting a clause containing this operator requires an extra set of parentheses: assert((Head :- Body)).

assert(+Clause)

If the index specification for the predicate is not trie, this predicate adds a dynamic clause, Clause, to the database after any other clauses for the same predicate currently in the database (acting as assertz/1). If the index specification for the predicate is trie, the clause is asserted arbitrarily within the trie. Error cases are as with assertz/1.

Note that because of the precedence of :-/2, asserting a clause containing this operator requires an extra set of parentheses: assert((Head :- Body)).

assert(+Clause,+AorZandVar,+Index)

This is a lower-level interface to (non-trie-indexed) assert. It is normally not needed except in one particular situation, when assert aborts because it needs too many registers. In this case, this lower-level assert may allow the offending clause to be correctly asserted.

The default implementation of non-trie-indexed assert generates code with a single pass through the asserted term. Because of this, it cannot know when it has encountered the final occurrence of a variable, and thus it can never release (and thus re-use) registers that are used to refer to variables. Since there is a limit of 255 registers in the XSB virtual machine, asserting a clause with more than this many distinct variables results in an error. There is an alternative implementation of assert that initially traverses the clause to determine the number of occurrences of each variable and thus allows better use of registers during code generation.

Clause is the clause to assert. AorZandVar is an integer whose lower 2 bits are used: The low-order bit is 0 if the clause is to be added as the first clause, and 1 if it is to be added as the last clause. If the second bit (2) is on, then the clause is traversed to count variable occurrences and so improve register allocation for variables; if it is 0, the default one-pass code-generation is done. So, for example, if AorZandVar is 3, then the clause will be asserted as the last one in the predicate and the better register allocation will be used. Index indicates the argument(s) on which to index.

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)).

The technical details on space reclamation are as follows. When retract is called, a check is made to determine whether it is safe to reclaim space for that clause. Safety is ensured when:

• A check is made of the choice point stack indicating that no choice point will backtrack into space that is being reclaimed; AND
  • The predicate is thread-private; OR
  • there is a single active thread
• AND if the predicate is tabled, there is no incomplete table for that predicate.

If it is safe to reclaim space for the clause, space is reclaimed immediately. Otherwise the clause is marked so that its space may later be reclaimed through garbage collection. (See gc_dynamic/1).

Error Cases

• Clause is not instantiated
  • instantiation_error
• Clause is not a callable clause.
  • domain_error(callable,Clause)
• Clause has a head that is a static built-in
  • permission_error(modify,builtin,Clause)
• Clause has a head that is a static user predicate
  • permission_error(modify,static,Clause)

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. Conditions for space reclamation and error cases are as with retract/1.

abolish(+PredSpec)

Removes all information about the specified predicate. PredSpec is of the form Pred/Arity. Everything about the abolished predicate is completely forgotten by the system (including the dynamic or static property, whether the predicate is tabled, and whether the predicate is thread-shared or thread-private) ^6.7. Any completed tables for the predicate are also removed.

It is an error to abolish a predicate when there is more than 1 active thread, regardless of whether the predicate is thread-private or thread-shared. The reason for this is that, even if PredInd denotes a thread-private predicate, one thread may be making use of PredInd as another thread abolishes it. abolish/1 throws an error in such a case to prevent such a semantic inconsistency. Similarly, if there is a non-completed table for PredInd, an error is thrown to prevent incompleteness in the tabled computation.

ISO Compatability Note: Version 3.0 of XSB allows static predicates to be abolished and their space reclaimed. Such space is reclaimed immediately, and unlike the case for abolished static code, no check is made to ensure that XSB's choice point stack is free of choice points for the abolished static predicate. Abolishing static code is thus dangerous and should be avoided unless a user is certain it is safe to use.

Error Cases

• PredInd, Pred or Arity is not instantiated
  • instantiation_error
• Arity is not in the range 0..255 (max_arity)
  • domain_error(arity_indicator,Arity)
• PredInd indicates a static built-in
  • permission_error(modify,builtin,Predind)
• abolish/1 is called when there is more than 1 active thread.
  • misc_error
• PredInd has a non-completed table in the current thread.
  • table_error
• There are active backtrack points to a (dynamic) clause for PredInd ^6.8.
  • misc_error

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.

Error Cases

• Head or Body is not instantiated
  • instantiation_error
• Head (or Body) is not a callable clause.
  • domain_error(callable,Head)
• Head is a static built-in
  • permission_error(access,builtin,Head)
• Head is a static user predicate
  • permission_error(access,static,Clause)

gc_dynamic(-N)

Invokes the garbage collector for dynamic clauses that have been retracted, or whose predicate has been abolished. When called with more than 1 active thread, gc_dynamic/1 will always perform garbage collection for that thread's private retracted clauses; however in Version 3.0, it will only perform garbage collection for retracted thread-shared clauses if there is a single active thread. N is the number or shared and/or private frames left to be collected - if N is unified to 0, then all possible garbage collecting has been performed. N is unified to -1 garbage collection was not attempted (due to multiple active threads).

By default, gc_dynamic/1 is called automatically at the top level of the XSB interpreter, when abolishing a predicate, and when calling retractall for an ``open'' term containing no variable bindings.

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 non-variable, 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 non-variable 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 non-variable and if so, use an index based on both those values. Otherwise, it would see if the first argument is non-variable and if so, use an index based on it. Otherwise, it would see if the fourth argument is non-variable 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 [46], 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 [30] 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.