Joshua: Uniform Access to Heterogeneous Knowledge Structures, or why Joshing Is Better than Conniving or Planning

Steve Rowley, Howard E. Shrobe, Robert Cassels, Walter HamscherAAAI 1987

Introduction: The Efficiency-Expressivity Trade-off

In the late 1980s, artificial intelligence research faced a fundamental "quandary." Developers were forced to choose between two extremes: the high expressivity of Predicate Calculus, which was flexible but notoriously slow due to uniform search algorithms, and specialized representations like frame-based languages or constraint networks, which were fast but rigid. Integrating these disparate tools often resulted in "black box" systems where internal logic was obscured by messy, ad-hoc workarounds.

The Joshua system was developed to bridge this gap. By introducing a "Protocol of Inference," Joshua allows developers to decouple the high-level logic of a problem from the low-level data structures used to store and process facts. This enables "uniform access" to heterogeneous knowledge bases, allowing for massive performance optimizations without requiring a rewrite of the system's core rules.

The Joshua Architecture: A Protocol of Inference

The core innovation of Joshua is its shift from a monolithic inference engine to a modular, object-oriented framework. Instead of a single algorithm for reasoning, Joshua defines a small set of abstract, generic actions known as the Protocol of Inference.

The primary interfaces for this protocol are ASK and TELL. TELL is used to add information to the system, triggering forward-chaining rules, while ASK queries the system, triggering backward-chaining. Crucially, every statement in Joshua is an instance of a class (or "Flavor" in the Lisp terminology of the time). The steps of inference—such as INSERT (indexing data), FETCH (retrieval), and LOCATE-TRIGGER (finding applicable rules)—are implemented as methods inherited from these classes.

By overriding these methods, developers can "model" a specific domain. For instance, instead of relying on a general search to determine the connectivity of a circuit, a developer can override the INSERT method for a "Wire" predicate to follow direct pointers in a specialized topological data structure. This "Joshing" philosophy emphasizes that flexibility should not come at the cost of a syntactic barrier between the AI and the underlying implementation code.

Case Study: Digital Circuit Troubleshooting

To demonstrate the power of this approach, the authors applied Joshua to a classic AI benchmark: troubleshooting a digital circuit. The task involves identifying which module in a circuit (composed of adders and multipliers) has failed based on discrepancies between observed and predicted output values.

Figure 1: A digital circuit troubleshooting problem where conflicts between expected and observed values must be resolved.

In this scenario, the "knowledge level"—the rules defining how adders and multipliers behave—remains constant. However, the "implementation level" can be swapped. The authors compared a "General" implementation, which used default Lisp-based discrimination networks, against a "Specialized" implementation where the circuit's topology was mirrored directly in the underlying data structures.

Performance Evaluation and Results

The transition to a specialized, modeled implementation yielded dramatic improvements in both efficiency and selectivity. Because the specialized data structures could handle routine tasks like signal propagation procedurally, the inference engine was freed from redundant work.

Table 1: Performance comparison between General and Specialized implementations in Joshua.

As shown in the results, the number of rules fired dropped significantly from 37 to just 5. This reduction in overhead led to a 3.4x speedup in execution time. Furthermore, the "merging" statistic—which measures the percentage of successful rule-merging attempts—jumped from 5% to 38%, indicating that the specialized system was far more selective and wasted much less effort on irrelevant computations.

Conclusion

Joshua represents a pragmatic engineering approach to the challenges of heterogeneous knowledge representation. By leveraging object-oriented inheritance, it provides a mechanism for systematic integration of external tools, such as Truth Maintenance Systems, by overriding only a handful of protocol methods. While it lacks the formal logic foundations of some contemporary systems, its ability to provide high-level flexibility alongside low-level efficiency made it a powerful framework for complex AI applications of its era.

Summary updated

BibTeX
@inproceedings{rowley1987joshua,
  author = {Steve Rowley and Howard E. Shrobe and Robert Cassels and Walter Hamscher},
  title = {{Joshua: Uniform Access to Heterogeneous Knowledge Structures, or why Joshing Is Better than Conniving or Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure