The Deductive Synthesis of Imperative LISP Programs

Zohar Manna, Richard J. WaldingerAAAI 1987

Introduction

In the late 1980s, Zohar Manna and Richard Waldinger extended the "program synthesis as theorem proving" paradigm to address the complexities of imperative programming. While synthesis for purely functional (applicative) programs was well-understood by then, imperative programs—which rely on destructive side effects—posed significant logical challenges. In standard logic, a statement's truth value is static; in an imperative environment, a property like "the list is empty" can change from state to state. This paper introduces a refined situational logic centered on the concept of fluents to derive sound imperative LISP code.

The Problem of State in Logic

The primary difficulty in synthesizing imperative code is ensuring the logic respects the physical reality of computation: once a state is modified, the previous state is effectively destroyed. Earlier situational logic models allowed a program to "go back in time" by referencing an old state variable, leading to logical inconsistencies. Manna and Waldinger's framework ensures that programs always operate on an implicit "current" state, preventing the reuse of modified memory structures.

Formal Framework: Imperative-Program Theory

The authors propose a system based on several key formalisms:

  • Fluents: These are entities that, when evaluated, produce both a return value and a new machine state. This encapsulates side effects within a single logical unit.
  • Linkage and Frame Axioms: Linkage axioms define how high-level functions (e.g., rplaca) alter the state. Frame axioms are equally critical, specifying which parts of the memory remain unchanged during an operation.
  • Deductive Tableau: The synthesis process involves proving a theorem: "For any initial state, there exists a fluent that produces a final state satisfying the goal." The resulting proof is then used to extract the corresponding LISP code.
Initial state of lists a and b before destructive manipulation.

Key Insights: Purity and Isolation

A major contribution of the paper is the discovery of necessary preconditions for destructive programs. For an in-place list reversal to be correct, the input structures must satisfy:

  1. Finiteness: To ensure termination, lists cannot be circular.
  2. Purity: The list structure must not contain "ingrown" pointers (pointing back to its own elements).
  3. Isolation: The lists being manipulated must not share memory (no aliasing).

The deductive system "discovers" these requirements during the proof process; if a proof fails, it often signals a missing assumption about the data's structure.

Synthesis of the nrev2 Program

The framework's efficacy is demonstrated through the manual derivation of nrev2, a complex in-place list reversal algorithm. By starting with a high-level specification—"the output is the reverse of the input"—the system derives low-level destructive LISP commands like rplacd and setq.

The state of the list structure after the synthesized nrev2(a, b) operation.

The resulting program is guaranteed to be correct relative to its specification, provided the identified preconditions of purity and isolation are met.

Conclusion and Future Directions

While the derivations in this seminal work were performed manually, they laid the groundwork for automated imperative synthesis. The authors identified that future systems would need to balance correctness with efficiency, potentially by including memory constraints directly in the initial specification. Although focused on LISP, the underlying theory of fluents and state consumption remains a foundational concept in the formal verification of imperative systems.

Summary updated

BibTeX
@inproceedings{manna1987deductive,
  author = {Zohar Manna and Richard J. Waldinger},
  title = {{The Deductive Synthesis of Imperative LISP Programs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure