Reflective Reasoning with and between a Declarative Metatheory and the Implementation Code

Fausto Giunchiglia, Paolo Traverso

Introduction

GETFOL is a theorem-proving system designed to achieve true self-reflection. By establishing a mathematically proven, one-to-one mapping between its underlying implementation code and a declarative logical metatheory, the system can use formal logic to reason about, generate, and modify its own executable reasoning strategies.

The Procedural-Declarative Gap

In automated deduction, systems typically operate under two distinct paradigms for metareasoning. The procedural approach involves writing control strategies (tactics) in a programming language to guide the system. The declarative approach uses a logical metatheory to deduce facts about proofs. Historically, these layers have remained separate, with the implementation code acting as a static "black box." GETFOL bridges this gap, allowing a system to deductively reason about its own computational mechanisms and safely modify them during execution.

The GETFOL Architecture

The authors developed GETFOL as an extension of the FOL theorem prover, utilizing a novel architectural approach that links code and logic.

The GETFOL architecture showing the bi-directional mapping between implementation code, metatheory (MT), and object theory (OT).

As shown in Figure 1, the system relies on several key components:

  • Mechanization of Logic: Implementation code (in the functional language GET) is structured so that functions map directly to logical inference rules.
  • Bi-directional Mapping ($m_{up}$ and $m_{down}$): $m_{up}$ translates implementation code into declarative metatheory (MT) axioms, while $m_{down}$ compiles metatheoretic theorems back into executable code.
  • Reflection Rules ($R_{up}$ and $R_{down}$): These rules facilitate context shifts between the Object Theory (base-level logic) and the Metatheory (logic about proofs).
  • Semantic Attachment: Data structures link metatheoretic constants directly to the executable functions and syntactic objects they represent.

Key Insights: Code and Metatheory as One

The most profound insight of this work is that proving a theorem in the declarative metatheory is mathematically equivalent to writing a tactic in the procedural implementation language.

Declarative metatheory axioms representing object-level inference rules.

Because the metatheory axioms (Figure 3) map directly to code, the system can bypass tedious logical deductions by executing the corresponding code—a process where computation serves as a shortcut for deduction. Furthermore, GETFOL can automatically deduce new control strategies through theorem proving and compile them into its own executable code. This enables a form of true self-reflection where the system evolves over time, modifying its own source code without sacrificing logical correctness.

Results and Conclusion

The authors mathematically demonstrated the correctness and completeness of this approach. They proved that any tactic derived through this bi-directional mapping is guaranteed to be correct; the system physically cannot assert a non-theorem using tactics generated via this reflective process.

While the current implementation does not yet address execution errors in the underlying code or all search space constraints, it represents a significant step toward fully self-reflective AI. GETFOL demonstrates that a complex metatheoretic structure can be compiled into native code, executed for speed, and used to assert new theorems, paving the way for more dynamic and verifiable reasoning frameworks.

Summary updated

Abstract

The goal of this paper is to present a theorem prover where the underlying code has been written to behave as the procedural metalevel of the object logic. We have then defined a logical declarative metatheory MT which can be put in a one-to-one relation with the code and automatically generated from it. MT is proved correct and complete in the sense that, for any object level deduction, the wff representing it is a theorem of MT, and viceversa. Such theorems can be translated back in the underlying code. This opens up the possibility of deriving control strategies automatically by metatheoretic theorem proving, of mapping them into the code and thus of extending and modifying the system itself. This seems a first step towards "really" self-reflective systems, it. systems able to reason deductively about and modify their underlying computation mechanisms. We show that the usual logical reflection rules (so called reflection up and down) are derived inference rules of the system.
BibTeX
@inproceedings{giunchiglia1991reflective,
  author = {Fausto Giunchiglia and Paolo Traverso},
  title = {{Reflective Reasoning with and between a Declarative Metatheory and the Implementation Code}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}
Figure