Path-Based Rules in Object-Oriented Programming

AAAI 1996

TL;DR

This paper introduces R++, a system that seamlessly integrates "path-based rules" into C++. This approach allows AI-style production rules to operate directly on C++ objects, overcoming limitations of previous systems and making AI techniques more accessible to mainstream programmers.

What Problem Does This Paper Address?

Object-oriented programming (OOP) has become a dominant paradigm, yet many powerful AI techniques, particularly rule-based systems, have struggled to integrate effectively. Traditional rule-based systems often operate on separate data structures (working memory) or require cumbersome mechanisms to interact with objects. This creates a disconnect, forcing developers to manage data transfer and synchronization between rule engines and object models. Furthermore, many existing rule systems lack the "locality" inherent in OOP, allowing arbitrary joins between unrelated objects, which can violate design principles and lead to less maintainable code. The authors aim to bridge this gap by creating a rule system that feels like a natural extension of an object-oriented language, specifically C++.

Methods

The core innovation is the concept of path-based rules. Unlike traditional rules that can form arbitrary joins, R++ rules are restricted to following pointers (access paths) between objects. This mirrors how member functions navigate object structures in OOP.

Key aspects of the R++ approach include:

  • Rules as Class Members: Rules are treated as members of classes, similar to data members and member functions. This means rules are associated with specific classes and operate on instances of those classes.
  • Path-Based Conditions: Rule conditions must start with a "root" object and can only access other objects by traversing pointers. This enforces locality and aligns with object-oriented design principles.
  • Seamless Integration: R++ rules are designed to be a "small" addition to C++, requiring minimal new syntax and concepts. They are not an add-on but an integral part of the language.
  • Data-Driven Activation: Rules are triggered automatically by "relevant changes" to object data. There's no need for explicit rule agendas or complex control mechanisms; the object system itself manages rule activation.
  • R++ Translator: The system is implemented via an R++ to C++ translator. This translator generates C++ code that incorporates the rules, allowing them to be compiled and executed as part of a standard C++ program.

Datasets

Not discussed in the paper. The paper focuses on the language and system design, with performance evaluated on synthetic object structures.

Key Insights and Ideas

  • Locality is Key: Restricting rules to follow object pointers (path-based rules) is not a limitation but a strength when integrating with OOP. It enforces the design principle of encapsulation and makes rules more predictable.
  • Rules as "Automatic Member Functions": By treating rules as class members, R++ makes them feel like extensions of existing object-oriented concepts, reducing the learning curve for C++ programmers.
  • Eliminating Working Memory: The need for a separate working memory is eliminated because rules operate directly on the object system, which inherently manages object state and access.
  • "Small" Addition, "Big" Benefit: The goal is to make AI techniques accessible by making the integration feel minor to the programmer, while still providing significant new functionality (e.g., declarative constraint enforcement, event reaction).

Key Results

The paper presents a qualitative argument for the benefits of R++ and includes performance comparisons.

  • Performance: Table 1 shows that R++ can outperform C5 (a C-based superset of OPS5) in rule firing rates, especially with smaller path lengths and branching factors. This speedup is attributed to the elimination of the complex bookkeeping required by the RETE algorithm used in traditional pattern-matching rule systems. For example, with a path length of 1 and a branching factor of 128, R++ achieved 18078 rule firings per second, compared to C5's 1383.
  • Declarative Power: Rules are shown to be effective for enforcing invariants (e.g., rectangle area calculation), detecting constraint violations (e.g., public phones and call waiting), and acting as "watch dogs" for important states.
  • Maintainability: Rules can make programs clearer by expressing multi-object constraints declaratively, reducing the need for scattered procedural logic.

Limitations and Future Work

The authors acknowledge several limitations and suggest future directions:

  • C++ Limitations: C++'s lack of strong control over object creation/destruction and member access monitoring necessitates extensions to the language. The authors had to create an extension rather than just a library.
  • Type Safety: C++'s potential for unsafe casts can lead to violations of encapsulation and incorrect execution.
  • Restrictions on Code: To make the notification mechanism tractable, R++ imposes restrictions: no casts on classes used by rules, and changes to data members must be made via automatically generated "stereotypic modification functions" (e.g., set_<member_name>).
  • Future Work:
    • Batching Changes: Deferring rule execution to treat groups of changes as atomic batches.
  • Integration with Active Databases: Combining R++ with object-oriented databases for more robust systems.
  • Improved Recompilation: Addressing the increased header file size and interdependencies caused by R++ to reduce C++ recompilation times.
  • Branching on Expressions: Allowing rules to branch on arbitrary expressions, not just object pointers.

Summary updated

BibTeX
@inproceedings{1996path,
  title = {{Path-Based Rules in Object-Oriented Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}

Loading related content...

Figure