Menu
Analyze the shape of heap data structures to enable precise reasoning about pointer-rich data.
Install with Codex or Claude Copy this prompt, paste it into Codex, Claude, or another assistant, and let it review the skill page and install it for you.
Implement abstract machines for defining and executing operational semantics of programming languages.
Implements alias and points-to analysis for pointer programs. Use for: (1) Optimizing compilers, (2) Verifying memory safety, (3) Program understanding, (4) Parallelization.
Define program meaning through logical assertions and proof rules (Hoare logic).
Transforms closures to explicit environments. Use when: (1) Implementing functional languages, (2) Building compilers, (3) Understanding closures.
Implements common subexpression elimination (CSE). Use when: (1) Building compilers, (2) Optimizing code, (3) Program analysis.
Implements general dataflow analysis framework. Use when: (1) Building compilers, (2) Static analysis tools, (3) Program verification.
Based on SOC occupation classification
| name | shape-analysis |
| description | Analyze the shape of heap data structures to enable precise reasoning about pointer-rich data. |
| version | 1.0.0 |
| tags | ["analysis","pointers","verification","oopsla"] |
| difficulty | advanced |
| languages | ["c","java","python"] |
| dependencies | ["alias-and-points-to-analysis","separation-logician"] |
Shape analysis determines the "shape" of heap data structures (lists, trees, cycles) at each program point. It enables precise reasoning about programs that manipulate pointer-based data structures.
| Concept | Description |
|---|---|
| Shape Graph | Abstract representation of heap structure |
| Shape | Classification (list, tree, cycle, etc.) |
| Heap Abstraction | Summarize multiple concrete heaps |
| Canonicalization | Normalize shape representations |
| Materialization | Create concrete nodes from summary |
alias-and-points-to-analysis - Points-to and alias analysisseparation-logician - Separation logic for shapesalias-and-points-to-analysis - Alias relationshipshoare-logic-verifier - Verification with shapes| Reference | Why It Matters |
|---|---|
| Sagiv, Reps, Wilhelm, "Parametric Shape Analysis via 3-Valued Logic" (POPL 1999/TOPLAS 2002) | TVLA framework |
| Distefano, O'Hearn, Yang, "A Local Shape Analysis Based on Separation Logic" (TACAS 2006) | Separation logic shapes |
| Jones & Muchnick, "A Flexible Approach to Pointer Analysis" (POPL 1982) | Shape graphs |
| Approach | Pros | Cons |
|---|---|---|
| Shape graphs | Simple, intuitive | Limited precision |
| TVLA | Precise | Expensive |
| Separation logic | Compositional | Requires annotations |
A high-quality implementation should have:
| Criterion | What to Look For |
|---|---|
| Soundness | Never miss a possible shape |
| Precision | Distinguish common patterns |
| Efficiency | Reasonable analysis time |
| Usability | Clear output format |
✅ Good: Recognizes lists, trees, cycles; handles loops ⚠️ Warning: Only basic shapes, loses precision in loops ❌ Bad: Returns UNKNOWN for all structures
Real-world shape analysis tools:
| Tool | Why It Matters |
|---|---|
| TVLA | Shape analysis framework |
| Infer | Facebook shape analysis |
| Separator | Separation logic analysis |
| Space | Galois shape analysis |
Current shape analysis research:
| Direction | Key Papers | Challenge |
|---|---|---|
| Automation | "Automatic Shape" | Scale |
| Parallel | "Parallel Shape" | Multi-core |
Common shape analysis bugs:
| Pitfall | Real Example | Prevention |
|---|---|---|
| Precision | Too coarse | Refine |
| Performance | Slow | Widen |