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 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. 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
- 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.
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.
- Has a heap garbage collector that works for tabled (and Prolog)
evaluation. After a table is abolished, a table garbage collector
ensures that its space is properly reclaimed.
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
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
- 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.
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
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
An alternate interface that supports access to multiple drivers,
including mySQL drivers.
Java interfaces provided through InterProlog and
- An interface to Perl, and especially to its pattern-matching
Interfaces to libwww routines and various pattern-matching utilities,
all of which are useful for Web applications.
An interface to the stable model generator
the XASP package.
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
In addition to those mentioned above, several important packages are maintained
on top of XSB, inlcuding
- Flora: a highly sophisticated and efficient implementation of
XJ: a system that allows XSB programs to create graphical user
interfaces based on Java's Swing package.
- XMC: a temporal-logic model checker for verifying properties of
concurrent programs. and containing a graphical user
- 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.
Last modified: $Id: about.html,v 1.5 2007/08/24 20:16:04 tswift Exp $