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
Though XSB can be used as a Prolog system1.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 , 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).
:- table shaves/2. shaves(barber,Person):- person(Person), tnot(shaves(Person,Person)). person(barber). person(mayor).
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).
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 . 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 .
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 elementary unification operations. The general technique is described in , 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.