program-correctness-prover

Program Correctness Prover

Generate formal proofs establishing correctness of imperative programs.

Overview

This skill takes imperative program code with formal specifications (preconditions and postconditions) and generates complete correctness proofs in Isabelle or Coq using Hoare logic. It handles loop invariant generation, verification condition generation, and proof construction for both partial and total correctness.

How to Use

Provide:

1. Program code: Imperative program (assignments, conditionals, loops)
2. Specification: Precondition and postcondition
3. Target system: Isabelle or Coq
4. Correctness type: Partial or total correctness

The skill will generate:

• Loop invariants (if needed)
• Verification conditions
• Complete formal proof
• Termination argument (for total correctness)

Verification Workflow

Step 1: Analyze Program Structure

Identify program components:

• Assignments: x := E
• Sequences: C1; C2
• Conditionals: if B then C1 else C2
• Loops: while B do C

Step 2: Generate Loop Invariants

For each loop, construct an invariant that:

1. Holds initially: Precondition implies invariant
2. Preserved by loop body: {I ∧ B} C {I}
3. Implies postcondition: I ∧ ¬B ⟹ Q

Strategies:

• Generalize postcondition by replacing constants with loop variables
• Express partial computation at iteration i
• Maintain relationships between variables

Step 3: Generate Verification Conditions

Apply Hoare logic rules to generate VCs:

Assignment: {P[E/x]} x := E {P}

Sequence: Chain intermediate conditions

Conditional: Prove both branches

Loop: Prove initialization, preservation, and termination

Step 4: Construct Proof

Build formal proof in target system:

• Apply Hoare logic rules
• Prove each verification condition
• Use simplification and automation where possible

Step 5: Add Termination Argument (Total Correctness)

Provide variant function V that:

• Is non-negative when loop condition holds
• Strictly decreases each iteration