Discovering Procedural Executions of Rule-Based Programs

David Gadbois, Daniel P. MirankerAAAI 1994

Introduction

Rule-based programming, exemplified by languages like OPS5, gained prominence in the early 1990s as a flexible paradigm for building expert systems. By defining logic through declarative "if-then" rules, developers could create complex systems without explicitly managing control flow. However, this flexibility came at a significant performance cost. The standard "match-select-act" interpreter cycle is computationally expensive, often re-evaluating conditions and maintaining global state even for simple logic. The STAR (STatic Analysis of Rules) system was developed to address these inefficiencies by extracting the hidden procedural logic within these programs.

The STAR System Architecture

The core hypothesis of the STAR system is that declarative programs often mask underlying procedural logic. STAR acts as a compiler that "discovers" this logic and transforms it into efficient procedural code.

The STAR System Architecture

The STAR workflow begins by parsing OPS5 code into an internal Abstract Rule Language (ARL). A critical component of this process is the integration of the Otter theorem prover. Otter performs deep type analysis to determine how rules interact—identifying whether rule actions subsume, intersect, or are disjoint from the conditions of other rules. This formal analysis enables three primary optimizations:

  • Rule Jamming: Merging sequential rules into a single operation, similar to function inlining.
  • Branch Factoring: Consolidating rules that differ only by constant values into single rules with if-then-else blocks.
  • Loop Rolling: Identifying "body" and "guard" rule pairs and replacing them with procedural loops that operate on entire data sets at once.

Experimental Evaluation and Results

The researchers evaluated the STAR system using four classic OPS5 benchmarks: Manners (combinatorial search), Waltz (3D line-drawing), ARP (route planning), and Weaver (VLSI routing). These benchmarks represent varying levels of complexity, with Weaver being the most substantial.

Execution Time Performance (Seconds)

As shown in the performance data, the STAR system achieved dramatic gains across the board. The Weaver benchmark saw the most significant improvement, with its execution time dropping from 1654 seconds to 195 seconds—an 8.5x speedup. Furthermore, the number of interpreter cycles required for Weaver was reduced by a factor of 8.4 (from 1718 to 204 cycles). These improvements demonstrate that recognizing procedural "idioms" allows a compiler to bypass the expensive interpreter cycle entirely, often reducing algorithmic complexity from exponential to linear scales.

Conclusion and Future Work

The STAR system demonstrates that the overhead of rule-based systems is not an inherent property of the declarative paradigm but rather a limitation of traditional execution models. By leveraging automated theorem proving, compilers can safely extract procedural logic, paving the way for high-performance expert systems. Future work aims to expand the library of transformations to handle more complex data relationships and to better integrate these techniques with database query processors for set-oriented execution.

Summary updated

BibTeX
@inproceedings{gadbois1994discovering,
  author = {David Gadbois and Daniel P. Miranker},
  title = {{Discovering Procedural Executions of Rule-Based Programs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure