playbooks

home / skills / a5c-ai / babysitter / loop-invariant-generator

loop-invariant-generator skill

/plugins/babysitter/skills/babysit/process/specializations/domains/science/computer-science/skills/loop-invariant-generator

This skill helps automatically generate and verify loop invariants for algorithm proofs using formal methods and theorem provers.

npx playbooks add skill a5c-ai/babysitter --skill loop-invariant-generator

Review the files below or copy the command above to add this skill to your agents.

Files (1)
SKILL.md
1.2 KB
---
name: loop-invariant-generator
description: Automatically generate and verify loop invariants for algorithm correctness proofs
allowed-tools:
  - Bash
  - Read
  - Write
  - Edit
  - Glob
  - Grep
metadata:
  specialization: computer-science
  domain: science
  category: algorithm-analysis
  phase: 6
---

# Loop Invariant Generator

## Purpose

Provides expert guidance on generating and verifying loop invariants for algorithm correctness proofs using formal methods.

## Capabilities

- Infer candidate loop invariants from code structure
- Verify initialization, maintenance, and termination conditions
- Generate formal proof templates
- Handle nested loops and complex data structures
- Export to theorem provers (Dafny, Why3)
- Suggest invariant strengthening

## Usage Guidelines

1. **Code Analysis**: Analyze loop structure and identify key properties
2. **Candidate Generation**: Generate candidate invariants from code patterns
3. **Verification**: Check initialization, maintenance, termination
4. **Strengthening**: Refine invariants to prove desired properties
5. **Export**: Generate proof obligations for theorem provers

## Tools/Libraries

- Dafny
- Why3
- SMT solvers (Z3, CVC5)
- Static analysis frameworks

Overview

This skill automatically generates and verifies loop invariants to support formal correctness proofs for algorithms. It inspects loop code, proposes candidate invariants, checks initialization, maintenance, and termination, and produces proof templates you can export to theorem provers. The tool targets nested loops and complex data structures and suggests strengthening when proofs fail.

How this skill works

The skill analyzes loop structure and variable usage to infer likely properties and relationships (e.g., bounds, monotonicity, preserved relations). It then generates candidate invariants and runs verification checks: initialization (holds before the loop), maintenance (preserved by each iteration), and termination-related assertions. When an invariant is insufficient, it proposes strengthened forms and creates proof obligations exportable to Dafny, Why3, or SMT solvers like Z3 and CVC5. It also handles nested loops by producing layered invariants and cross-loop relations.

When to use it

  • When proving algorithm correctness for loops in imperative code
  • While developing formal proofs for sorting, searching, or numerical algorithms
  • When preparing proofs for verification tools (Dafny, Why3) or SMT solvers
  • To audit and strengthen invariants in legacy code with unclear correctness guarantees
  • When teaching or documenting formal verification steps for loops

Best practices

  • Start by providing the loop body and relevant pre/post-conditions to focus candidate generation
  • Validate generated invariants against initialization and a few representative iterations before formal verification
  • Use suggested strengthening only when verification fails; prefer minimal invariants for readability
  • Export proof obligations to your preferred theorem prover and iteratively discharge failures with counterexample inspection
  • Annotate complex data-structure invariants (e.g., heaps, graphs) with intended abstractions to improve inference accuracy

Example use cases

  • Generate invariants for a sorting routine (e.g., insertion sort, quicksort partition) and export a Dafny proof template
  • Infer loop invariants that preserve heap or BST properties across iterations and verify maintenance
  • Produce and strengthen invariants for nested loops in dynamic programming implementations
  • Create proof obligations for termination and correctness to feed into Z3 or CVC5 during CI verification
  • Assist educators by auto-generating invariant examples and stepwise proof sketches for classroom exercises

FAQ

What theorem provers can I export to?

You can export proof obligations and templates to Dafny and Why3, and generate SMT queries for Z3 or CVC5.

Can it handle nested loops and complex data structures?

Yes. The tool produces layered invariants for nested loops and supports common data-structure abstractions, though annotations improve accuracy.

How do I refine an invariant if verification fails?

The skill will suggest invariant strengthenings and counterexamples. Use those suggestions, inspect failing iterations, and iterate until initialization, maintenance, and termination conditions are satisfied.