Abstract
This paper presents FORLOG, a logic programming environment designed to combine the expressive declarative nature of Prolog with the flexible, multi-context reasoning of an Assumption-based Truth Maintenance System (ATMS). FORLOG overcomes the limitations of traditional ATMS consumer architectures by replacing standard unification with equality reasoning and Skolemization. This allows for the manipulation of complex data structures and existential variables within a high-performance, forward-chaining data-flow network, enabling reversible reasoning and efficient handling of contradictory search spaces.
Introduction
In the late 1980s, AI researchers sought to merge the strengths of logic programming and truth maintenance systems. While Prolog offered a powerful declarative language, its rigid search strategies were often insufficient for complex problem-solving tasks like mechanical design. Conversely, the ATMS provided a robust framework for managing multiple contradictory contexts simultaneously but was restricted to simple forward implications. FORLOG was developed to bridge this gap, providing a full-fledged logic programming environment built upon the ATMS.
The Challenge: Beyond Simple Implications
The primary hurdle was the "Consumer Architecture" typically paired with an ATMS. This architecture was limited in its ability to handle complex data structures (e.g., lists, trees) and existential variables. Without these, the system could not perform sophisticated reasoning tasks. FORLOG addresses these limitations through several key technical innovations that allow it to handle first-order logic while maintaining the efficiency of forward-chaining systems.
Methodology and Architecture
FORLOG's architecture is centered on a data-flow network that optimizes rule firing, similar to the RETE algorithm or the Warren Abstract Machine.
Skolemization and Equality Reasoning
Unlike Prolog, which uses unification to bind variables, FORLOG represents logical variables as Skolem constants. This allows the system to reason about "partial" or unknown objects without immediate binding. The system employs an equality reasoning engine to determine when antecedent patterns are satisfied. If the equality of two terms is unknown, "listeners" are established in the data-flow network, which trigger once sufficient information is asserted.
Program Completion and Reversibility
To enable backward-chaining style reasoning (from goals to facts) within a forward-chaining framework, FORLOG utilizes "program completion." By transforming implications into equivalences, the system can reason in both directions while maintaining rigorous justifications for every derived fact. This makes FORLOG programs inherently reversible; for instance, the append predicate can be used to find possible inputs given a resulting list.
Data-Flow Compilation
FORLOG programs are compiled into a sophisticated network that manages the "detachment" of consequents. This process is particularly complex when dealing with existential variables, requiring a sequence of unifications and Skolem constant creations. The compiler transforms logical disjunctions and equalities into a branching structure that the ATMS can navigate.
Key Insights
- Solving the "Un-outing" Problem: One of the most significant advantages of the ATMS integration is the ability to handle the "un-outing" problem. In traditional systems, switching between different search branches often requires expensive backtracking. In FORLOG, "consumers" (pending inferences) are treated as explicit objects on a global agenda. Because they are indexed by their ATMS labels, the system can stop reasoning in one context and resume in another seamlessly.
- Equality as a Trigger: The use of "listeners" for equality allows FORLOG to handle under-constrained problems gracefully. If the system cannot immediately decide which branch of a logical "OR" is true, it can assume both possibilities in different ATMS contexts. The truth maintenance system then manages these parallel realities, identifying contradictions as they arise.
Evaluation and Applications
The system was implemented in Interlisp-D and evaluated against standard logic programming benchmarks, most notably the append predicate. Beyond benchmarks, FORLOG was applied to a small-scale expert system for molecular biology and identified as a powerful tool for mechanical design. In design tasks, the ability to maintain and reason about multiple contradictory design paths simultaneously—facilitated by the ATMS—provides a significant advantage over traditional depth-first search methods.
Conclusion
FORLOG represents a significant advancement in integrating logic programming with truth maintenance. By moving beyond simple unification to a more flexible equality-based reasoning system, it allows for high-performance, reversible reasoning across multiple contexts, making it uniquely suited for complex engineering and design domains.
Summary updated