Introduction
Formal software specifications serve as mathematical blueprints, yet their creation is fraught with difficulty. Developers often struggle to reconcile their mental models with the logical implications of the axioms they write. Traditional theorem provers are typically goal-directed, requiring the user to pose specific questions. However, during the exploratory phase of design, users often do not know what questions to ask. This paper introduces the Forward Inference Engine (FIE), an automated "kibitzer" designed to volunteer information by deriving shallow but significant consequences from a set of axioms.
The Challenge of Forward Inference
The primary obstacle in forward inference is the "combinatorial explosion." Without constraints, a system can generate a vast number of technically valid but trivial or redundant logical statements. FIE addresses this by focusing on "interestingness"—identifying consequences that are simple enough for a human to grasp quickly but non-obvious enough to reveal flaws in the specification.
System Architecture and Methodology
FIE utilizes a typed version of first-order logic and a modified resolution theorem proving approach. When a new fact is introduced, the engine integrates it into the existing knowledge base through a three-phase pipeline:
- Isolation and Simplification: The new fact is canonicalized and simplified. Redundant terms are removed to ensure the logic is in its most concise form.
- Inter-clause Simplification: The system leverages existing knowledge to further refine the new fact. This phase employs Subsumption—discarding a fact if a more general version is already known—and Conditional Equality Canonicalization, which uses conditional logic (e.g., "if A=B") to standardize terms.
- Consequence Generation: FIE generates new facts using standard Resolution and a specialized Uniqueness Resolution rule.
The Interestingness Heuristic
To prevent the system from overwhelming the user, FIE employs a heuristic that prioritizes "shallow" consequences. Generally, the engine discards any new result that is more complex than its parent facts, where complexity is measured by the number of literals or the depth of function nesting. This constraint forces the engine to find immediate, high-impact implications that often point directly to missing assumptions or logical contradictions.
Uniqueness Resolution
A key innovation in FIE is the treatment of uniqueness. In human reasoning, it is often implicit that an object can only occupy one state or location at a time. FIE formalizes this through Uniqueness Resolution, which efficiently handles single-valued relations. This prevents the need for the user to explicitly define every negative constraint (e.g., "if the ship is in Port A, it is not in Port B"), significantly reducing the clutter in the knowledge base.
Evaluation and Key Results
The system was evaluated using specifications written in Gist, covering domains such as file systems, package routers, and maritime logistics.
Performance
In a representative test case, FIE integrated 10 new clauses with 23 existing ones to produce 27 "interesting" clauses in under 10 CPU seconds on a VAX 750 running Interlisp. This performance suggests that the "kibitzer" can operate in near real-time, providing immediate feedback during the specification process.
Bug Discovery: The "Ship" Example
FIE’s utility is best demonstrated by its ability to uncover hidden assumptions. In a "world of ships" model, a user failed to declare "grain" and "fuel" as disjoint types. While the user assumed a cargo could not be both, FIE derived a consequence showing that a ship could technically carry a hybrid "grain-fuel" cargo. By reporting this "obvious" contradiction, FIE alerted the user to a missing axiom.
Limitations and Future Directions
Despite its successes, FIE faces challenges with certain types of logical structures:
- The $N^2$ Problem: Expressing that $n$ objects are all distinct currently requires $n^2$ individual inequality facts, which can overwhelm the output.
- Transitivity: Relations like "A is inside B, and B is inside C" often trigger a cascade of uninteresting inferences that are difficult to filter.
Future work involves using "uninteresting" intermediate facts for internal simplification without displaying them to the user and extending the engine's capabilities to assist in debugging database schemas.
Conclusion
The "kibitzer" philosophy represents a shift from theorem proving as a goal-oriented task to theorem proving as a collaborative exploration. By focusing on shallow, interesting consequences, FIE provides a mirror for the developer’s logic, revealing the unintended side effects of their specifications before implementation begins.
Summary updated