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 and Diagnosis may benefit from XSB.

XSB's Tabling implementation:

• Evaluates at the engine level programs with stratified and non-stratified negation, and programs with stratified aggregation.
• Allows full Prolog functionality in tabled code including cuts, (subject to weak semantic restrictions), in meta-logical predicates, in second-order predicates, etc.
• 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.
• Versions 2.4 and later have as 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.
• Versions 2.5 and later have as their default stack management configuration the SLG-WAM configuration, for which a choice of three heap garbage collectors are available.

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.

• XSB provides a variety of read and assert mechanisms for quickly loading dynamic predicates, especially if these predicates are unit clauses.
• 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 a term.
• 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 accessable 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 new 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
• 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. 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.