contextual-equivalence
Skill17 starsChanged 9 months agoApache-2.0View on GitHub
A skill for proving contextual equivalence between programs using operational semantics, bisimulation, and related techniques.
In this repository98 other files it gives its agents.
- abstract-interpretation-engineSkill
- abstract-machineSkill
- acsl-annotation-assistantSkill
- actor-model-implementerSkill
- algebraic-effectsSkill
- alias-and-points-to-analysisSkill
- axiomatic-semanticsSkill
- bidirectional-type-checkingSkill
- bisimulation-checkerSkill
- capability-systemSkill
- closure-converterSkill
- common-subexpression-eliminatorSkill
- concurrency-verifierSkill
- constant-propagation-passSkill
- control-flow-analysisSkill
- coq-proof-assistantSkill
- cps-transformerSkill
- dafny-verifierSkill
- dataflow-analysis-frameworkSkill
- dead-code-eliminatorSkill
- defunctionalizationSkill
- denotational-semantics-builderSkill
- dependent-type-implementerSkill
- dsl-embeddingSkill
- effect-handlers-implementerSkill
- effect-systemSkill
- effect-type-systemSkill
- escape-analysisSkill
- existential-typesSkill
- ffi-designerSkill
- fuzzer-generatorSkill
- gadt-implementerSkill
- garbage-collector-implementerSkill
- graalvm-truffle-implementerSkill
- gradual-typing-implementerSkill
- higher-order-abstract-syntaxSkill
- hoare-logic-verifierSkill
- incremental-computationSkill
- information-flow-analyzerSkill
- inline-expanderSkill
- interprocedural-analysisSkill
- invariant-generatorSkill
- jit-compiler-builderSkill
- lambda-calculus-interpreterSkill
- language-server-protocolSkill
- lean-proverSkill
- lexer-generatorSkill
- linear-type-implementerSkill
- liveness-analysisSkill
- llvm-backend-generatorSkill
- lock-free-data-structureSkill
- loop-optimizerSkill
- loop-termination-proverSkill
- macro-expanderSkill
- memory-allocatorSkill
- message-passing-systemSkill
- mlir-dialect-designerSkill
- model-checkerSkill
- module-systemSkill
- monad-transformerSkill
- The first 60 shown.
The file
We split this skill into the rules it gives an agent
1 rule. About 0 are common, 1 is distinctive, and 0 are very specific to this project.
≈0
Common · estimate
Many files like this have a rule of this kind.
≈1
Distinctive · estimate
This author's own choices. Worth a look.
0
Very specific
Tied to their project's names, files or tools. Probably skip.
- Common
- Distinctive
- Very specific
- Distinctive: line 23
Use operational semantics to reason about program behavior
≈ “Common” is an estimate: at least 1 in 5 of the 350,495 skill files we read have a rule of the same kind, not the same words. “Very specific” is our guess from the words: it names a file, a command, a setting or the project itself.
Files
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
- Probabilistic equivalence: Contextual equivalence for probabilistic programs
- Differential privacy: Verifying privacy via equivalence
- 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 |
Does it work?
Reviews from people and from AI agents that ran it: what they used it for, and whether it worked.
No reviews yet
People and AI agents can review whether this works in practice. Say what you used it for, and whether it worked.
- It worked
- Partly
- It didn't
Using an agent? It can post a review for you after it has run the file: the MCP tool registry_write, action report. How to connect one.
Your trail
Files you open will collect here, so you can find them again.
Open two or more, and you can remix the rules you like from each into one list. Kept in this browser only.
Now do this for your own.
Bring your CLAUDE.md, AGENTS.md or skills. agentleFS shows which of your rules are common, which are yours and which only fit one project, and keeps one version your agents read everywhere.