The Layered Architecture of a System for Reasoning about Programs

Charles RichIJCAI 1985

Abstract

Cake is a hybrid reasoning system developed for the Programmer's Apprentice project. It employs a modular, eight-layered architecture to manage the complexity of program verification, integrating truth maintenance with domain-specific reasoning for types, algebra, and plan calculus. By partitioning reasoning into specialized layers, Cake avoids the computational pitfalls of uniform theorem provers while supporting incremental program design.

Introduction

Reasoning about software is inherently difficult due to the multi-layered abstractions involved. Early AI approaches often relied on "uniform" theorem provers, which frequently succumbed to "state-space explosion" when faced with realistic program sizes. Furthermore, software development is an iterative process; a reasoning system must be able to retract facts and update knowledge incrementally—a capability known as Truth Maintenance.

Cake, developed in the mid-1980s at the MIT Artificial Intelligence Laboratory, addresses these challenges through a sophisticated layered architecture. It moves away from monolithic systems toward a modular, hybrid approach designed to power the "Programmer’s Apprentice."

The Cake Architecture

The core philosophy of Cake is that a hybrid system should use different data abstractions to view the same underlying information through specialized lenses. The architecture consists of eight layers divided into two primary levels:

The Predicate Calculus Level

This level handles the foundational logic and domain-specific properties:

  • Truth Maintenance: The foundation of the system, tracking dependencies between facts and performing simple deductions to allow for incremental updates.
  • Equality: Manages congruence closure (e.g., if $a=b$, then $f(a)=f(b)$).
  • Demons: Pattern-matching triggers for "trap-door" inferences upon the creation of new terms.
  • Algebraic: Specialized procedures for properties like commutativity, transitivity, and associativity.
  • Types: Manages type hierarchies (e.g., "B is a subtype of C") and domain/range constraints.

The Plan Level

This level bridges the gap between code and logic:

  • Plan Calculus: Maps program features like data flow and control flow into logical formulae.
  • Plan Recognition & Synthesis: Higher-level layers intended to help the system understand existing code or generate new plans.

Case Study: Proving Plan Correctness

The system's efficacy is demonstrated through a representative reasoning problem: proving that a composition of two operations, "Plan XY," correctly implements a higher-level "Operation Z."

Specification of Operation Z

As shown in Figure 1, Operation Z is defined with specific inputs, outputs, and constraints, including function commutativity and type subtyping. The reasoning task requires coordinating knowledge across multiple layers, such as the Types layer triggering a demon that informs the Algebraic layer.

Composition of Plan XY and its mapping to Operation Z

Figure 6 illustrates the composition of Plan XY and how its internal data flows map to the specification of Operation Z. The proof involves symbolic evaluation and algebraic substitution. In tests on a Symbolics 3600 Lisp Machine, this complex reasoning task was completed in approximately 10 seconds—a significant achievement for automated reasoning in 1985.

Key Insights and Discussion

The most significant contribution of Cake is the partitioning for control. By breaking reasoning into specialized layers, the system can utilize efficient, local algorithms rather than a slow, global search. This approach intentionally trades off deductive completeness for tractability and control.

However, the interaction between layers remains a challenge. The author notes that these interactions are "highly tuned," and adding new functionality can occasionally trigger "computational explosions" where the system over-invests in trivial inferences. Future work aimed to refine the type hierarchy and complete the plan synthesis and recognition layers, which represent the "holy grail" of the project.

Conclusion

Cake represents a pivotal shift in AI reasoning for software engineering. Its layered architecture demonstrates that modularity and specialized data abstractions can provide the control necessary for automated reasoning in complex, evolving domains.

Summary updated

BibTeX
@inproceedings{rich1985layered,
  author = {Charles Rich},
  title = {{The Layered Architecture of a System for Reasoning about Programs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1985},
}
Figure