About XSB

Tabled Resolution

Tabled resolution is useful for recursive query computation, allowing programs to terminate correctly in many cases where Prolog does not. Users interested in Parsing, Program Analysis, Model-checking, Data Mining, Diagnosis and Temporal Reasoning may benefit from XSB.

• XSB's Basic Tabling implementation:
• Evaluates at the engine level programs with stratified and non-stratified negation, and programs with stratified aggregation.
• Allows the full functionality of Prolog plus constraints tabled code including cuts, (subject to weak semantic restrictions), in meta-logical predicates, in second-order predicates, when using attributed variables, etc. Dynamic code may also be tabled.
• Allows for declaration of tabled predicates either automatically by the system or manually by the user. Furthermore, tabling can be automatically performed for termination, for efficiency, or for both.
• Provides standard tabling predicates which can be used to program a number of applications in non-monotonic reasoning and knowledge representation.
• Dynamically compiles tables into trie-based SLG-WAM code. which is indexed dynamically and for which full memory management is provided.
• Has a default a tabling strategy called Local Evaluation which is efficient for returning all answers to a query, and is useful for applications such as program analysis and non-monotonic reasoning. As a configuration alternative, Batched Evaluation is a Prolog-like tabling strategy that efficiently returns the first answer to a query.
• After a table is abolished, a table garbage collector ensures that its space is safely reclaimed.
• XSB's Tabling Extensions fully support the basic functionality described above, but may not be fully integraed with one another (yet).
• Call Subsumption can be used to make programs more declarative and efficient by a more robust reuse of tables among calls.
• Incremental tabling can be used for programs that use tabling with call-variance on program fragments that do not require tabled negation. If a table depends on dynamic code (perhaps indirectly) asserts or retracts to the code will automatically propagate incremental changes to the various depending tables.
• Answer Subsumption can be used to extend tabling to support multi-valued logics as well as adding fuzzy or probabilistic reasoning to programs.
• Tabling Declarations for Termination When using subgoal abstraction, tabling ensures termination for all programs with a finite model; when also tabling with radial restraint, tabling ensures sound termination for all programs.

Support for Multi-Threading

Beginning with Version 3.0, XSB supports a configuration that allows multiple threads of computation within a single process under the Posix model.

• All threads within the multi-threaded engine share the same static code and I/O streams.
• For dynamic code or tables, predicates may be declared thread-private or thread-shared. Private predicates are visible only to a given thread, and the space for private predicates is reclaimed upon a thread's exit. Thread-shared predicates are visible to all threads.
• Within default local evaluation, concurrency for shared tables is supported by an optimistic concurrency control called shared completed tables which adds little overhead to computation. Within batched evaluation, non-completed tables are visible to multiple threads as well (this is experimental in version 3.1).
• Posix-style operations are supported for XSB threads, including joining and detaching threads, thread cancellation, message queues, user-defined mutexes, and much else.
• XSB can be called as a multi-threaded server using sockets, or embedded in a process as a multi-threaded subprocesses. When called as a subprocess, threads can maintain the state of a query so that the calling program may backtrack through the answers. The result is that XSB queries serve in a manner somewhat analogous to cursors.

Indexing and Dynamic Code

XSB contains a variety of features to support in-memory data-oriented applications. Using these features, knowledge bases with millions of clauses can be quickly loaded and efficiently indexed.

• Indexes can be created on alternate or joint arguments of dynamic code. Furthermore this indexing can be hash-based, or trie-based if it is necessary to perform indexing deep within alternate arguments of a term.
• XSB provides a variety of read and assert mechanisms for quickly loading dynamic predicates, especially if these predicates are unit clauses.
• In addition to regular assert, Prolog terms can be trie-asserted or trie-interned. The use of tries can significantly improve the speed of asserting (which is relatively fast in XSB).
• XSB provides mechanisms for backtrackable asserts: asserts whose effects become undone upon backtracking.
• For static code XSB provides unification factoring which extends clause indexing by factoring common unifications out of clause heads, and can be used to optimize many Prolog programs.

Interfaces

XSB supports a variety of interfaces. All source code is available so that the interfaces can be tuned as needed or ported to other Prologs. (as some have been!)

• Interfaces under UNIX and Cygwin, to call C functions or to be called by them.
• An ODBC interface, to call data stored in a database accessible by an ODBC driver. This interface translates Datalog clauses into SQL automatically.
• An alternate interface that supports access to multiple drivers, including mySQL drivers.
• Java interfaces provided through InterProlog and YAJXB
• An interface to Perl, and especially to its pattern-matching facilities.
• Interfaces to libwww routines and various pattern-matching utilities, all of which are useful for Web applications.
• An interface to the stable model generator SModels via the XASP package.

HiLog Compilation

HiLog supports a type of higher-order programming in which predicate symbols can be variable or structured. This allows unification to be performed on the predicate symbols themselves in addition to the arguments of the predicates.

XSB's HiLog implementation:

• Includes compiled HiLog. Higher-order predicates execute at essentially the same speed as compiled first-order predicates.
• Includes a fully integrated HiLog preprocessor. HiLog terms can be used anywhere in XSB, including the interpreter level.
• Provides a number of meta-logical standard predicates for HiLog terms.

Packages

In addition to those mentioned above, several important packages are maintained on top of XSB, inlcuding

• Flora: a highly sophisticated and efficient implementation of F-logic
• XJ: a system that allows XSB programs to create graphical user interfaces based on Java's Swing package.
• PITA: is a library that supports probabilistics and fuzzy reasoning with tabling.
• XMC: a temporal-logic model checker for verifying properties of concurrent programs. and containing a graphical user interface.
• xsbdoc: a mechanism for generating manuals for XSB libraries and applications using principles of literate programming. Manuals can be generated in a variety of formats, including html, pdf, ps, and even ASCII text.

XSB has been tested on over a dozen hardware and operating system platforms under Microsoft Windows 95/98, Windows NT, Windows 2000 and various versions of 32-bit UNIX. XSB also has also been ported to 64-bit architectures and has been tested on 64-bit SGI machines and linuxes. Various versions of XSB have been used to construct large-scale commercial systems for the U.S. Customs Service, the U.S. Defense Logistics Agency, the National Security Agency, Medicine Rules, Inc, MdLogix Inc., and many others.