# Contextual Equivalence

> Use when working with a skill for proving contextual equivalence between programs using operational semantics, bisimulation, and related techniques.

- Skill: `tomevault-io/contextual-equivalence` (Agent Skill, multi-file: 2 files)
- Install (CLI): `npx skillmds@latest add tomevault-io/contextual-equivalence`
- Raw SKILL.md: https://api.skillmd.com/api/skills/tomevault-io/contextual-equivalence/raw
- Safety review: pending (external: skill-scanner PASS, skillspector PASS)
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- Author: tomevault-io (https://skillmd.com/u/tomevault-io)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/tomevault-io/contextual-equivalence

---


# Contextual Equivalence

**Domain**: Program Verification / Programming Languages

## Overview

A skill for proving contextual equivalence between programs using operational semantics, bisimulation, and related techniques.

## Capabilities

- Prove that two programs are contextually equivalent
- Build bisimulation relations for behavioral equivalence
- Use operational semantics to reason about program behavior
- Apply contextual equivalence in compiler verification

## Techniques

- **Operational Semantics**: Small-step and big-step semantics
- **Bisimulation**: Trace equivalence, bisimilarity proofs
- **Contextual Equivalence**: Observation-based equivalence
- **Game Semantics**: Interactive models of computation

## Use Cases

- Compiler correctness proofs
- Program transformation verification
- Optimization validation
- Language meta-theory development

## References

| Reference | Why It Matters |
|-----------|----------------|
| **Morris, "Lambda Calculus Types and Models" (1968)** | Original contextual equivalence formulation |
| **Milner, "Operational and Algebraic Semantics" (1997)** | Comprehensive overview of contextual equivalence |
| **Gunter, "Semantic Foundations for Programming Languages"** | Formal treatment of program equivalence |
| **Reynolds, "Theories of Programming Languages"** | Contextual equivalence in type theory |

See also: `../simply-typed-lambda-calculus`, `../bisimulation-checker`, `../operational-semantics-definer`

## Research Tools & Artifacts

Real-world contextual equivalence verification:

| Tool | Why It Matters |
|------|----------------|
| **Coq** | Interactive proof of contextual equivalence |
| **Twelf** | Logical framework for LF |
| **Agda** | Dependent types for equivalence proofs |
| **Nuprl** | Constructive verification system |
| **HOL** | Higher-order logic proofs |

### Key Verification Projects

- **CompCert**: Verified compiler with contextual equivalence
- **GHC correctness**: Haskell compiler verification
- **CakeML**: Verified ML compiler

## Research Frontiers

Current contextual equivalence research:

| Direction | Key Papers | Challenge |
|-----------|------------|-----------|
| **Untyped equivalence** | "Equivalence in untyped λ-calculus" | Full abstraction |
| **Relational** | "Relational Reasoning" (2008) | Semantic relations |
| **Step-indexed** | "Step-indexed Bisimulation" (2005) | Recursive types |
| **Logical relations** | "Logical Relations" (1998) | Semantics |
| **Game semantics** | "Game Semantics" (1997) | Full abstraction |

### Hot Topics

1. **Probabilistic equivalence**: Contextual equivalence for probabilistic programs
2. **Differential privacy**: Verifying privacy via equivalence
3. **Quantum equivalence**: Quantum program equivalence

## Implementation Pitfalls

Common equivalence proof bugs:

| Pitfall | Real Example | Prevention |
|---------|--------------|------------|
| **Incomplete contexts** | Missing context forms | Prove completeness |
| **Bisimulation too strong** | Fails for equivalent programs | Use weak bisimulation |
| **Recursive types** | Fixed-point handling | Use step-indexing |
| **Non-termination** | Divergence not handled | Use contextual equivalence |
| **State** | State in language | Relational reasoning |

---
> Converted and distributed by [TomeVault](https://tomevault.io/claim/rainoftime) — claim your Tome and manage your conversions.
<!-- tomevault:4.0:skill_md:2026-04-11 -->