一句话：提出只需异步进展即可保证可靠性的自由 stuttering 模拟技术 FreeSim，并在 Coq 中机化验证。
行为精化（behavioral refinement）的证明常依赖模拟（simulation）证明，其中 stuttering simulation 允许源或目标单方面“停步”（stutter），被广泛用于 CompCert 等验证工作。为保证可靠性，现有 stuttering simulation 限制证明者只能在有限步 stuttering 之后达到“同步进展”（两侧同时前进），以确保终止程序无法被证明模拟非终止程序。本文指出这一限制既繁琐又是不必要的：只需要求“异步进展”（双方各自可仅通过 stuttering 步取得进展），便可同样保证可靠性。基于此，作者提出 FreeSim（freely-stuttering simulations），并在 Coq 中机化实现。案例研究表明其有效性，包括简化 CompCert 的元理论，以及 DTrees 库——它为 ITrees（Interaction Trees）库引入了双重非确定性。
One of the most common tools for proving behavioral refinements between transition systems is the method of simulation proofs, which has been explored extensively over the past several decades. Stuttering simulations are an extension of traditional simulations—used, for example, in CompCert—in which either the source or target of the simulation is permitted to “stutter” (stay in place) while the other side steps forward. In the interest of ensuring soundness, however, existing stuttering simulations restrict proofs to only perform a finite number of stuttering steps before making synchronous progress —a step of reasoning in which both sides of the simulation progress forward together. This restriction guarantees that a terminating program cannot be proven to simulate a non-terminating one. In this paper, we observe that the requirement to eventually achieve synchronous progress is burdensome and, what’s more, unnecessary: it is possible to ensure soundness of stuttering simulations while only requiring asynchronous progress (progress on both sides of the simulation that may be achieved with only stuttering steps). Building on this observation, we develop a new simulation technique we call FreeSim (short for “freely-stuttering simulations”), mechanized in Coq, and we demonstrate its effectiveness on a range of interesting case studies. These include a simplification of the meta-theory of CompCert, as well as the DTrees library, which enriches the ITrees (Interaction Trees) library with dual non-determinism.
@article{paperbot1885,
title = {Stuttering for Free},
author = {Minki Cho and Youngju Song and Dongjae Lee and Lennard Gäher and Derek Dreyer},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {OOPSLA2},
year = {2023},
doi = {10.1145/3622857}
}