Introduction

XSB is a research-oriented Logic Programming system for Unix and Windows-based systems. In addition to providing all the functionality of Prolog, XSB contains several features not usually found in Logic Programming systems, including

• Evaluation according to the Well-Founded Semantics [44] through full SLG resolution;
• A compiled HiLog implementation;
• A variety of indexing techniques for asserted code, along with a novel transformation technique called unification factoring that can improve program speed and indexing for compiled code;
• A number of interfaces to other software systems, such a C, Java, Perl and Oracle.
• Extensive pattern matching libraries, which are especially useful for Web applications.
• Preprosessors and Interpreters so that XSB can be used to evaluate programs that are based on advanced formalisms, such as extended logic progams (according to the Well-Founded Semantics [1]); Generalized Annotated Programs [23]; and F-Logic [22].
• Source code availability for portability and extensibility.

Though XSB can be used as a Prolog system^1.1, we avoid referring to XSB as such, because of the availability of SLG resolution and the handling of HiLog terms. These facilities, while seemingly simple, significantly extend its capabilities beyond those of a typical Prolog system. We feel that these capabilities justify viewing XSB as a new paradigm for Logic Programming.

To understand the implications of SLG resolution [8], recall that Prolog is based on a depth-first search through trees that are built using program clause resolution (SLD). As such, Prolog is susceptible to getting lost in an infinite branch of a search tree, where it may loop infinitely. SLG evaluation, available in XSB, can correctly evaluate many such logic programs. To take the simplest of examples, any query to the program:

:- table ancestor/2.

ancestor(X,Y) :- ancestor(X,Z), parent(Z,Y).
ancestor(X,Y) :- parent(X,Y).

will terminate in XSB, since ancestor/2 is compiled as a tabled predicate; Prolog systems, however, would go into an infinite loop. The user can declare that SLG resolution is to be used for a predicate by using table declarations, as here. Alternately, an auto_table compiler directive can be used to direct the system to invoke a simple static analysis to decide what predicates to table (see Section 3.8.4). This power to solve recursive queries has proven very useful in a number of areas, including deductive databases, language processing [24,25], program analysis [12,9,5], model checking [32] and diagnosis [34]. For efficiency, we have implemented SLG at the abstract machine level so that tabled predicates will be executed with the speed of compiled Prolog. We finally note that for definite programs SLG resolution is similar to other tabling methods such as OLDT resolution [43] (see Chapter 5 for details).

Example 1.0.1   The use of tabling also makes possible the evaluation of programs with non-stratified negation through its implementation of the well-founded semantics [44]. When logic programming rules have negation, paradoxes become possible. As an example consider one of Russell's paradoxes -- the barber in a town shaves every person who does not shave himself -- written as a logic program.

 
:- table shaves/2.

shaves(barber,Person):- person(Person), tnot(shaves(Person,Person)).
person(barber).
person(mayor).

Logically speaking, the meaning of this progam should be that the barber shaves the mayor, but the case of the barber is trickier. If we conclude that the barber does not have himself our meaning does not reflect the first rule in the program. If we conclude that the barber does shave himself, we have reached that conclusion using information beyond what is provided in the progra. The well-founded semantics, does not treat shaves(barber,barber) as either true or false, but as undefined. Prolog, of course, would enter an infinite loop. XSB's treatment of negation is discussed further in Chapter 5.

The second important extension in XSB is support of HiLog programming [6,39]. HiLog allows a form of higher-order programming, in which predicate ``symbols'' can be variable or structured. For example, definition and execution of generic predicates like this generic transitive closure relation are allowed:

closure(R)(X,Y) :- R(X,Y).
closure(R)(X,Y) :- R(X,Z), closure(R)(Z,Y).

where closure(R)/2 is (syntactically) a second-order predicate which, given any relation R, returns its transitive closure relation closure(R). With XSB, support is provided for reading and writing HiLog terms, converting them to or from internal format as necessary (see Section 4.2). Special meta-logical standard predicates (see Section 6.5) are also provided for inspection and handling of HiLog terms. Unlike earlier versions of XSB (prior to version 1.3.1) the current version automatically provides full compilation of HiLog predicates. As a result, most uses of HiLog execute at essentially the speed of compiled Prolog. For more information about the compilation scheme for HiLog employed in XSB see [39].

HiLog can also be used with tabling, so that the program above can also be written as:

:- table closure(_)(_,_).

closure(R)(X,Y) :- R(X,Y).
closure(R)(X,Y) :- closure(R)(X,Z), R(Z,Y).

A further goal of XSB is to provide in implementation engine for both logic programming and for data-oriented applications such as in-memory deductive database queries and data mining [36]. One prerequisite for this functionality is the ability to load a large amount of data very quickly. We have taken care to code in C a compiler for asserted clauses. The result is that the speed of asserting and retracting code is faster in XSB than in any other Prolog system of which we are aware. At the same time, because asserted code is compiled into SLG-WAM code, the speed of executing asserted code in XSB is faster than that of many other Prologs as well. We note however, that XSB does not follow the semantics of assert specified in [27].

Data oriented applications may also require indices other than Prolog's first argument indexing. XSB offers a variety of indexing techniques for asserted code. Clauses can be indexed on a groups of arguments or on alternative arguments. For instance, the executable directive index(p/4,[3,2+1]) specifies indexes on the (outer functor symbol of) the third argument or on a combination of (the outer function symbol of) the second and first arguments. If data is expected to be structured within function symbols and is in unit clauses, the directive index(p/4,trie) constructs an indexing trie of the p/4 clauses using a left-to-right traversal through each clause. Representing data in this way allows discrimination of information nested arbitrarily deep within clauses. These modes of indexing can be combined: index(p/4,[3,2+1],trie) creates alternative trie indices beginning with the third argument and with the second and first argument. Using such indexing XSB can efficiently perform intensive analyses of in-memory knowledge bases with 1 million or so facts. Indexing techniques for asserted code are covered in Section 6.10.

For compiled code, XSB offers unification factoring, which extends clause indexing methods found in functional programming into the logic programming framework. Briefly, unification factoring can offer not only complete indexing through non-deterministic indexing automata, but can also $factor$ elementary unification operations. The general technique is described in [11], and the XSB directives needed to use it are covered in Section 3.8.

A number of interfaces are available to link XSB to other systems. In UNIX systems XSB can be directly linked into C programs; in Windows-based system XSB can be linked into C programs through a DLL interface. On either class of operating system, C functions can be made callable from XSB either directly within a process, or using a socket library. XSB can access external data in a variety of ways: through an Oracle interface, through an ODBC interface, or through a variety of mechanisms to read data from flat files. These interfaces are all described in Volume 2 of this manual.

Another feature of XSB is its support for extensions of normal logic programs through preprocessing libraries. Currently supported are Extended logic programs (under the well-founded semantics), F-Logic, and Annotated Logic Programs. These libraries are described in Volume 2 of this manual.

Source code is provided for the whole of XSB, including the engine, interfaces and supporting functions written in C, along with the compiler, top-level interpreter and libraries written in Prolog.

It should be mentioned that we adopt some standard notational conventions, such as the name/arity convention for describing predicates and functors, + to denote input arguments, - to denote output arguments, ? for arguments that may be either input or output and # for arguments that are both input and output (can be changed by the procedure). See Section 3.8.4 for more details. Also, the manual uses UNIX syntax for files and directories except when it specifically addresses other operating systems such as Windows.

Finally, we note that XSB is under continuous development, and this document --intended to be the user manual-- reflects the current status (Version 2.2) of our system. While we have taken great effort to create a robust and efficient system, we would like to emphasize that XSB is also a research system and is to some degree experimental. When the research features of XSB -- tabling, HiLog, and Indexing Techniques -- are discussed in this manual, we also cite documents where they are fully explained. All of these documents can be found via the world-wide web or anonymous ftp from $\{$www/ftp$\}$.cs.sunysb.edu, the same host from which XSB can be obtained.

While some of Version 2.2 is subject to change in future releases, we will try to be as upward-compatible as possible. We would also like to hear from experienced users of our system about features they would like us to include. We do try to accomodate serious users of XSB whenever we can. Finally, we must mention that the use of undocumented features is not supported, and at the user's own risk.