Refinement e-graphs introduce a built-in <= relation alongside the native = equivalence, modeling compiler rewrites as unidirectional refinements from abstract specs to concrete implementations. The author provides a prototype implementation in Rust and a WASM demo, with examples demonstrating how optimization opportunities arise in cases like don't-care terms in digital circuits.
Background
E-graphs are a powerful data structure for representing equivalence classes of terms, widely used in compiler optimization and program analysis. This work extends them by adding an ordering relation to model refinement, a concept relevant to partial evaluation and language semantics.
- Source
- Lobsters
- Published
- Oct 5, 2026 at 10:23 AM
- Score
- 6.0 / 10