playbooks

home / skills / a5c-ai / babysitter / soundness-proof-assistant

soundness-proof-assistant skill

/plugins/babysitter/skills/babysit/process/specializations/domains/science/computer-science/skills/soundness-proof-assistant

This skill guides you through constructing type soundness proofs, covering progress and preservation, with lemma generation and mechanization guidance.

npx playbooks add skill a5c-ai/babysitter --skill soundness-proof-assistant

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

Files (1)
SKILL.md
1.0 KB
---
name: soundness-proof-assistant
description: Assist in constructing type soundness proofs using progress and preservation theorems
allowed-tools:
  - Bash
  - Read
  - Write
  - Edit
  - Glob
  - Grep
metadata:
  specialization: computer-science
  domain: science
  category: programming-language-theory
  phase: 6
---

# Soundness Proof Assistant

## Purpose

Provides expert guidance on constructing type soundness proofs for programming language type systems.

## Capabilities

- Progress theorem proof templates
- Preservation theorem proof templates
- Substitution lemma generation
- Canonical forms lemma derivation
- Proof case enumeration
- Mechanization guidance

## Usage Guidelines

1. **Lemma Identification**: Identify required supporting lemmas
2. **Progress Proof**: Prove progress theorem by cases
3. **Preservation Proof**: Prove preservation theorem
4. **Substitution Lemmas**: Prove substitution preserves typing
5. **Mechanization**: Translate to proof assistant

## Tools/Libraries

- Coq
- Agda
- Lean
- Twelf

Overview

This skill assists researchers and language designers in constructing type soundness proofs using progress and preservation theorems. It provides targeted templates, lemma generators, and step-by-step guidance for each proof obligation. The goal is practical: reduce boilerplate, enumerate cases, and prepare proofs for mechanization in common proof assistants.

How this skill works

The skill inspects a language specification (syntax, typing rules, and operational semantics) and generates proof outlines for progress and preservation. It enumerates evaluation and typing cases, proposes substitution and canonical-forms lemmas, and offers concrete proof steps. It can also suggest translations of manual proofs into Coq, Lean, Agda, or Twelf styles for mechanization.

When to use it

  • Designing or validating a new type system
  • Teaching progress and preservation proof techniques
  • Preparing proofs for mechanization in Coq/Lean/Agda/Twelf
  • Refactoring language semantics or adding new features (e.g., references, polymorphism)
  • Auditing the soundness of extensions or plugins

Best practices

  • Start by writing a minimal, well-typed subset of the language to isolate proof structure
  • Identify and prove necessary supporting lemmas (substitution, canonical forms) before tackling main theorems
  • Enumerate evaluation and typing cases exhaustively and name them consistently
  • Keep proofs modular so lemmas can be reused when extending the language
  • When mechanizing, mirror paper proof structure and use automation tactics sparingly to keep proofs readable

Example use cases

  • Generate a progress proof outline for a lambda calculus with integers and booleans
  • Produce a preservation proof template for a simply typed lambda calculus with references
  • Derive substitution and canonical-forms lemmas for a language with pattern matching
  • Enumerate proof cases and provide proof sketches to port a paper proof into Coq or Lean
  • Assess how adding polymorphic types affects soundness obligations

FAQ

Can this produce fully mechanized proofs automatically?

It generates mechanization guidance and skeletons suitable for Coq/Lean/Agda/Twelf but does not claim to finish every proof automatically; user refinement is usually required.

Which proof assistants are supported in guidance?

Guidance targets common assistants: Coq, Lean, Agda, and Twelf, with suggestions for tactics and structuring definitions.

How does it handle complex features like subtyping or effects?

It identifies additional lemmas and case splits such features introduce and provides tailored proof outlines, but complex interaction often needs manual design choices.