Abstract
This paper, originally presented at the first AAAI conference in 1980, marks a significant milestone in the history of formal verification and functional programming. It investigates the application of the Edinburgh LCF (Logic for Computable Functions) system to formally verify the algebraic laws of John Backus’s Functional Programming (FP) systems. By utilizing the ML programming language to script "tactics," the research demonstrates how complex functional properties can be verified through semi-automated subgoaling and structural induction.
Introduction
In the late 1970s, John Backus proposed FP systems as a paradigm shift away from the "von Neumann bottleneck" of traditional imperative programming. FP systems introduced an "algebra of programs," allowing developers to reason about code using mathematical laws. However, verifying these laws manually is an error-prone and laborious process. This paper addresses the need for machine-assisted verification, seeking a middle ground between fully automated "black box" theorem provers and tedious manual proof checkers.
Methodology: The Power of Edinburgh LCF
The author employs Edinburgh LCF, the system responsible for the birth of the ML (Meta-Language) programming language. The core innovation of LCF is the ability to program the proof process itself through "tactics."
Programmable Tactics
A tactic is an ML function that decomposes a "goal" (a formula to be proven) into a list of "subgoals." If the subgoals are proven, the original goal is satisfied. Key tactics described include:
- SIMPTAC (Rewriting): Automatically simplifies expressions based on predefined algebraic rules.
- CONDCASESTAC (Case Analysis): Handles conditional logic by splitting proofs into branches for true, false, and undefined (bottom) states.
- INDTAC (Induction): A specialized tactic for structural induction over lists.
As shown in the figure above, INDTAC functions as an "inverse" of the structural induction rule. It takes a goal involving a list L and generates three subgoals corresponding to the base cases (undefined and empty list) and the inductive step (a list constructed with cons).
Tacticals
To build complex proof strategies, the author uses "tacticals"—higher-order functions like THEN that compose small tactics into sophisticated sequences. This allows for high-level strategy design while the machine ensures every step adheres to rigorous logical rules.
Key Insights and Results
The research highlights several critical advantages of the LCF approach:
- Human-Oriented Automation: Unlike contemporary automated provers, LCF allows the human to provide the high-level strategy while the machine handles the rigorous execution.
- Stronger Formulations: The use of a formal system allowed the author to formulate and prove FP laws in more general forms than originally proposed by Backus.
- Successful Verification: The author successfully verified multiple groups of FP algebraic laws. Notably, for the law
ToALL(G o F) = (ToALL G) o (ToALL F), a single composed tactic—APTAC THEN INDTAC THEN SIMPTAC—was sufficient to complete the proof entirely without human intervention.
Limitations and Conclusion
While powerful, the system requires a significant learning curve; the author noted a two-month period to reach proficiency. Additionally, because LCF reduces every proof to primitive inference rules for maximum rigor, it can be computationally intensive.
In conclusion, this work demonstrated that Edinburgh LCF is a flexible and robust framework for formal methods. By providing a programmable meta-language, it enables researchers to build reusable libraries of proof strategies, paving the way for modern automated reasoning tools in functional programming.
Summary updated