Lune

POPL2026Top-tier venue

A Family of Sims with Diverging Interests

Nicolas Chappe

Abstract

Simulations are widely-used notions of program refinement. This paper discusses and compares several of them, in particular notions of simulation that are both weak and sensitive to divergence. Complex simulation proofs performed in proof assistants, for instance in a verified compilation setting, often rely on variants of normed simulation, which is not complete with respect to divergence-sensitive weak simulation. We propose to bridge this gap with µdiv-simulation, a novel notion of simulation that is equivalent to classical divergence-sensitive weak simulation, and designed to be as comfortable to use as modern characterizations of normed simulation. We then define a parameterized notion of simulation that covers strong simulation, weak simulation, µdiv-simulation, and 9 more notions of simulation, and jointly establish various "up-to" reasoning techniques for these 12 notions. Our results are formalized in Rocq and instantiated on two case studies: Choice Trees and a CompCert pass. Verified compilation is a major motivation for our study, but because we work with an abstract LTS setting, our results are also relevant to other fields that make use of divergence-sensitive weak simulation, such as model checking.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Choice Trees: Representing Nondeterministic, Recursive, and Impure Programs in Coq cites Interaction trees: representing recursive and impure programs in Coq
  • Simuliris: a separation logic framework for verifying concurrent program optimizations cites Interaction trees: representing recursive and impure programs in Coq
  • Stuttering for Free cites Choice Trees: Representing Nondeterministic, Recursive, and Impure Programs in Coq
  • Stuttering for Free cites Interaction trees: representing recursive and impure programs in Coq
  • Stuttering for Free cites Simuliris: a separation logic framework for verifying concurrent program optimizations
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on5

  1. Interaction trees: representing recursive and impure programs in CoqLi-yao Xia, Yannick Zakowski, Paul He, Chung-Kil Hur et al.POPL 2020 · 133 citations
  2. Simuliris: a separation logic framework for verifying concurrent program optimizationsLennard Gäher, Michael Sammler, Simon Spies, Ralf Jung et al.POPL 2022 · 33 citations
  3. Choice Trees: Representing Nondeterministic, Recursive, and Impure Programs in CoqNicolas Chappe, Paul He, Ludovic Henrio, Yannick Zakowski et al.POPL 2023 · 21 citations
  4. Stuttering for FreeMinki Cho, Youngju Song, Dongjae Lee, Lennard Gäher et al.OOPSLA 2023 · 11 citations
  5. Exploiting Undefined Behavior in C/C++ Programs for Optimization: A Study on the Performance ImpactLucian Popescu, Nuno P. LopesPLDI 2025 · 2 citations

Related papers

  1. Compiling with continuations, correctlyZoe Paraskevopoulou, Anvay GroverOOPSLA 2021 · 10 citations
  2. Proof Repair across Quotient Type EquivalencesCosmo Viola, Max Fan, Talia RingerOOPSLA 2025 · 1 citation
  3. Definitional Proof Irrelevance Made AccessibleThiago Felicissimo, Yann Leray, Loïc Pujet, Nicolas Tabareau et al.LICS 2026
  4. Encode the Cake and Eat It Too: Controlling Computation in Type Theory, LocallyYann Leray, Théo WinterhalterPOPL 2026
  5. Incremental Certified ProgrammingTomás Díaz, Kenji Maillard, Nicolas Tabareau, Éric TanterOOPSLA 2025
Dusk over the sea between two cliffs drawn in fine vertical lines