We present a novel approach to debugging expressively rich knowledge representation and reasoning (KRR) logic Rulelog. Rulelog is an extended form of declarative logic programs (LP) under the wellfounded semantics, which allows higher-order logic formulas as axioms in combination with defeasibility mechanisms that include rule cancellation and priorities, along with default and explicit negation. Rulelog also supports strong knowledge interchange with all current major semantic web standards for logical KRR. Rulelog has been implemented in Flora-2 and Silk, both on top of XSB; and (less completely) in Cyc. The debugging approach described here is part of an integrated development environment, most fully implemented in Silk. The approach includes: reasoning trace analysis, based on tabled LP inferencing tables and forestlog; and justi cation graphs, which treat why-not and defeasibility as well as provenance. The reasoning trace analysis treats performance and runaway computations, including non-termination as well as classic subgoal-ordering issues that arise in database query optimization. Non-termination can be prevented entirely by leveraging the restraint (bounded rationality) feature of Rulelog. Revision/authoring of knowledge is interactive, based on a rapid edit-test-inspect loop and incremental truth maintenance.
1.1
Rulelog is an expressively rich knowledge representation and reasoning (KRR)
logic, based on a unique set of features that include:
1. defeasibility, based on argumentation theories (AT's) [
These theories provide features such as rule cancellation and priorities, along
with default and explicit negation.
2. higher-order syntax, based on HiLog [
Rulelog is the logic that was used in the Silk system [
The semantics of Rulelog is speci ed transformationally, into logic programs
(LP) that are normal: those with logical functions and with default negation
under the well-founded semantics. Using these transformations, Rulelog has been
implemented most fully to date in Silk, which is architected as a Java layer that
sits on top of Flora-2 [
Rulelog supports strong semantic knowledge interchange with not only LP but also with rst-order logic (FOL), and thus with all current major semantic technology standards for logical KRR, including RDF(S), SPARQL, SQL, XQuery, OWL-RL, OWL-DL, RIF-Core, and RIF-BLD, as well as with ISO Common Logic and thus SBVR.
Rulelog provides a good target for text-based authoring of knowledge [
Rulelog has been application-piloted in the domain of college-level biology for the task of question-answering in e-learning, in Project Halo. However, Rulelog is applicable to many other domains and tasks, e.g., that involve policies, contracts, law, and/or information integration. 1 The Silk development e ort, including maintenance, ended in April 2013.
The expressivity of Rulelog raises a number of issues both in debugging and in understanding the behavior of Rulelog derivations.
The justi cation problem is a problem of explaining missing or unexpected (e.g., wrong or unintended) answers. This task is complicated not only by the types of inference used, but also by the transformations used to implement Rulelog reasoning. Answers to a query may be di erent than expected due to defeasibility or due to unexpected inferences made by the use of the higher-order reasoning provided by the HiLog component.
The performance/termination problem is a problem of indicating why a derivation has taken up more resources than expected | including non-termination as an extreme case. To explain the context of this problem, one of the major objectives of the Silk implementation of Rulelog was to be usable by knowledge engineers (KE's) who are competent in logic, but who are not necessarily computer programmers. Such usage can give rise to knowledge bases constructed in a declarative manner, but with little attention to procedural aspects. Queries to such knowledge bases may lead to derivations that take longer than expected. In addition, as mentioned earlier, Rulelog uses logical functions both explicitly and implicitly (the later due to existential quanti cation, which is part of omniformity), and this use of logical functions can lead to non-termination.2 While some performance issues can be addressed by optimizing compilers, users still need to understand what parts of a knowledge base give rise to poor performance or non-termination, so that these parts can be remedied.
Understanding Rulelog derivations is complicated by the semantics of Rulelog, which unlike rst-order logic, is a xed-point logic that supports recursive de nitions. A Rulelog derivation, therefore, can be seen as a sequence of evaluations of recursive components in which the answers to a given subquery may be mutually dependent on answers to numerous other subqueries. Such a derivation can be partially modeled via a graph whose vertices are Rulelog atoms and whose edges are direct dependencies of the truth of one Rulelog atom on another. As will be shown later, such dependencies are implicit in our solution to the justi cation problem, but are explicit in our solutions to the performance/termination problem.
To partially address the justi cation and performance/termination problems, support is given by the tabled resolution of XSB, which serves as the computational underpinning of Rulelog in Silk. Although the details of tabling are quite complex, at a high level it handles recursive query evaluation by registering each tabled subgoal in a derivation. The rst time a subgoal S is encountered in a derivation, a table is created for S and program clause resolution is used to derive answers for S, which are added to the table for S as they are derived. Subsequent calls to S need only resolve against answers in its table. In addition, 2 FOL and normal LP also have this potential for non-termination in inferencing, for the same reason. tabling keeps partial track of dependency information in order to determine the truth values of atoms in the 3-valued well-founded semantics. Although tables are central to the derivation strategy of Silk, they can also be examined by users to help understand features of a derivation.
A basic requirement in debugging is that the edit-test-inspect loop be rapid. This is addressed in Silk (and XSB and Flora-2) by the use of incremental methods for tabling in XSB and Flora-2. Such incremental tabling essentially constitutes truth maintenance.
The considerations so far indicate that a creative approach must be taken to
understanding correctness, performance, and termination. Note that because of
the complications of the transformations from Rulelog to normal logic programs,
together with the technical details of tabled resolution, an interactive-debugger
approach like that used in Prolog and other languages is impractical. Instead, we
have developed a number of novel tools, each of which has an analytic
component, which examines the internal structures of the engine and produces textual
output, and a presentation component that makes the textual output more
comprehensible to the user. The presentation components were incorporated into an
overall graphical integrated development environment (IDE) for Silk, based on
Eclipse, called Silklipse [
Explanation of inferencing results, often called justi cation, has a long history
in KRR, starting with the venerable truth maintenance systems [
In this example, the relevant asserted logical rules in the KB can be described in English as follows: cell52 is a red blood cell.
Eukaryotic cells have nuclei. (This rule has tag r1.) Red blood cells are a subclass of eukaryotic cells.
Red blood cells do not have nuclei. (This rule has tag r2.) r2 has higher priority than r1. 3
3.1
Table dump: Examining Subqueries, Answers, and Rules Although simple and powerful, the table dump approach lacks two main features needed to fully address the performance/termination problem. First, it does not provide an overview of how given subqueries in a derivation relate to one another through rules, and does not display information about the recursive components whose computation is central to a Rulelog derivation. Second, no information is provided about the order of events in a derivation, such as when subqueries were made, answers derived, and so on.
Within Silk, details of a Rulelog derivation can be reconstructed through
another kind of trace-based analysis. XSB provides a mechanism to create a
more dynamic trace or log of a derivation, called a forest log [
The form of tabling used by XSB is called SLG resolution. The operational semantics of SLG evaluation (and hence a Rulelog derivation) can be modeled as a sequence of forests of trees, where each tree corresponds to a tabled subquery S, and represents the immediate subqueries that S produces along with any answers to S. In fact, each SLG operation is modeled as a function from forests to forests that creates a new tree, or adds a node or label to an existing tree.
Within XSB, SLG resolution is executed using a byte-code virtual machine analogous to that used by Java. An internal XSB ag can be set so that any byte-code instruction that corresponds to a tabling operation will log information about itself and its operands as a Prolog-readable term. For instance, if (tabled) subgoal S1 is called in the context of subgoal S2, and it is the rst time S1 is called in an evaluation, a fact of the form is logged, where ctr (mnemonic for \counter") is a sequence number for the fact. When a derivation ends or is interrupted, the log can be loaded into XSB and analyzed as a set of Prolog facts. Within XSB, the logging system is written at a very low level for e ciency. Turning on full logging usually does not slow down Flora-2 performance by more than 70-80%. XSB also provides routines to load logs and index their facts on various arguments. Based on the logging libraries, logs containing hundreds of millions of facts have been loaded and analyzed. 3.3
Once a log has been loaded, a user may ask for an overview of a computation, which provides information on the total number of calls to tabled subgoals, the number of distinct tabled subgoals, the number of answers, and so on. In addition, the overview provides aggregate information on the number of mutually recursive components, and the number of subgoals in the components. Finally, the overview contains information indicating how strati ed the negation (negation-as-failure, i.e., naf) was in a derivation by listing the total number of atoms whose truth value was unde ned, along with a count of the various SLG operations used to evaluate well-founded negation.
Some derivations may give rise to very large recursive components|due to an unanticipated e ect of higher-orderness, a knowledge base that is not su ciently modularized, or other reasons. The analysis routines allow given recursive components to be examined, by listing the subqueries in the component, along with the pairs of calling and called subgoals within the components.
By examining this output, users can usually x whatever problems gave rise to large recursive components. However for a very large component C, the number of subqueries in C may be on the order of 105 or more and the number of calling/caller pairs may be on the order of 106. In such a case diplaying every subquery or pair may be confusing at best. The analysis routines thus provide several abstraction routines that allow a user to coalesce similar atoms. For instance, if a component contained the subqueries p(a,X), p(b,X), p(c,X) ..., the analysis routines could use mode abstraction to coalesce all of these terms to p(bound,free), or even predicate abstraction to coalesce all these terms to p/2. Recursive component analysis together with abstraction of atoms has been used to analyze the behavior of reasoning that was translated from Cycorp's inference engine into the Silk implementation of Rulelog, for example. 3.4
Runaway computation occurs when a query does not terminate or takes too long to come back with an answer. The rst type of problem occurs typically due to the presence of function symbols and the second is largely due to computations that produce very large intermediate results most of which could be avoided with smarter evaluation strategies, such as subgoal reordering. The problem of determining whether a query is terminating or not has long been known to be undecidable, and the known su ciency tests for them are weak for practical purposes. Cost-based optimization of LP via subgoal reordering has not been well studied for the case when recursion and logical functions are present.
The rst tools we have developed for runaway give the user the means to interrupt the computation and inspect various statistics and the table dump, as described earlier. The user can also request the computation to stop after producing the desired number of answers.
One sophisticated diagnostic tool we have developed to tackle the
non-termination problem is called the Terminyzer (short for \(non-)Termination
Analyzer") [
Terminyzer also has a heuristic that may suggest the user to allow the system to reorder subgoals at run time and this avoid non-termination. For instance, in a composite subgoal p(?X,?Y), q(?X) , Terminyzer may detect that p(?X,?Y) is an in nite predicate. However, this in nity may be due to the in nite number of ?X-values. If q(?X) binds ?X to a concrete value rst, non-termination will not occur. In such a case, Terminyzer may suggest the user to wrap the o ending subgoal with a suitable delay quanti er|a novel facility supported by Flora-2 and Silk. For instance, if the above subgoal is rewritten as wish(ground(?X))^p(?X,?Y), q(?X), the system will not try to evaluate p(?X,?Y) unless ?X is bound. If it is not bound, the evaluation of p(?X,?Y) is postponed and q(?X) will be evaluated next. If this binds ?X then all is well and p(?X,?Y) can be evaluated next without a runaway. If ?X is still unbound, some other subgoal may, perhaps, bind it, so p(?X,?Y) remains delayed. Only when the system determines that ?X cannot be bound no matter what, p(?X,?Y) is submitted for evaluation. If this happens, the user would have to use the information provided by Terminyzer to decide whether the runaway is a mistake or is semantically justi ed. In the rst case, this information will help the user x the mistake; in the second, restraint could be used to prevent the runaway.
The presentation component of Terminyzer is integrated with Silklipse. 4
Another advanced way to control runaways is to use restraint, an approach to
bounded rationality (and pragmatic incompleteness) that is semantically sound
despite non-monotonicity [
While Terminyzer is used for nding mistakes in user's knowledge base, i.e., in situations when runaway computation is not intended, restraint is used when the knowledge base is correct. This typically occurs when the user query of interest or one of its subqueries has an in nite number of answers, but only the rst few need to be returned to the user.
One type of restraint is to limit a norm on subgoals, e.g., term size or depth, to be upper-bounded by a constant, which is called the radius. By setting the radius to a small enough value, radial restraint can be used to prevent runaways altogether.
There are several other useful types of restraint as well. In skipping restraint, conditions are speci ed (via rules) for when some other rules instances should be skipped, i.e., treated as having unde ned truth value. In unsafety restraint: a literal that is (irremediably) unsafe with respect to NAF is treated as having unde ned truth value. Likewise, an external-query (a.k.a. sensor ) literal that is unsafe with respect to binding mode requirements is treated as having unde ned truth value. In unreturn restraint, an external-query literal that does not return|e.g., due to network failure or server failure | is treated as having unde ned truth value. In some situations, unsafety and unreturn restraints are preferable to throwing an error. Radial and skipping restraint are voluntary kinds of bounded rationality: the user speci es desired limits on reasoning via meta-rules knowledge. The limitation is cleanly semantic and speci ed as part of the knowledge base itself. By contrast, unsafety and unreturn are involuntary : limitations on reasoning are imposed by the circumstances of the inferencing mechanism and/or external environment.
All the above types of restraint straightforwardly combine with each other.
They furthermore straightforwardly combine with the \anytime" approach to
temporally bounded rationality [
The tools we have described can be combined in a number of ways. The typical process of knowledge debugging goes as follows. A user runs a (test) query of interest. If the execution of the query does not take an unexpectedly/undesirably large amount of time or space, there is no performance/termination issue. The user looks at the answers to the query, and employs the justi cation tools to examine the explanation of those answers in terms of supporting conclusions and their associated assertions (rules knowledge). Along the way, the user looks for wrong or missing conclusions, and wrong or missing rules. The user may issue some other related queries as part of this investigation, and look at their explanations as well.
However, if execution of the query does take an unexpectedly/undesirably large amount of time or space, there is a performance/termination issue. At this point, the user needs to determine whether the runaway is due to nontermination or merely due to an ine cient computation. The rst step in determining the culprit is to look at the table dump of the trace. If these show very large terms with deeply nested repeated function symbols, non-termination is the likely problem, and Terminyzer can be further employed to nd the actual rule sequences that cause the problem. Otherwise, the user would use the table dump and the forest log tools to identify foci of computational e ort, by looking for large tables (via table dump) or large recursive components (via forest log). The user next drills down progressively from the macroscopic (more aggregated and general) to the microscopic (more detailed and speci c). Once su ciently microscopic, the user then also employs the justi cation tools (as described above)|and/or employs restraint, especially in order to ensure termination (e.g., by limiting term size).
As usual in any kind of debugging, the above steps are iterated as needed. 6
The debugging tools and process we have described have been used e ectively for expressively rich Rulelog knowledge bases (KB's) of substantial size, ranging up to tens of thousands of (non-fact) rules. \Expressively rich" here means with expressiveness beyond that of (normal) LP. Trace-based analysis has been used for forest logs ranging up to hundreds of millions of facts, as mentioned earlier.
An important direction for future work is how to empower Subject Matter
Experts (SME's), who lack skills in logic, to most e ectively and e ciently debug
knowledge, e.g., KB's that they author via text-based techniques [
This work was supported by Vulcan, Inc., as part of the Halo Advanced Research project. Thanks to the rest of the Silk team, especially Paul Haley (Automata, Inc.) and Keith Goolsbey (Cycorp), for helpful discussions. Michael Kifer and Senlin Liang were also supported, in part, under the NSF grant 0964196.