ACM Transactions on Programming Languages and Systems · 2023 · 13 citations · 33 references
ComputingComputer ScienceAlgorithmsFormal MethodsProgramming LanguagesPredicate LogicTermination AnalysisBig-step SemanticsLoop UnrollingModelingNondeterminismOperational SemanticsPredicate Logic SemanticsSmall-step SemanticsWeakest Preconditions
This article gives an in-depth presentation of the omni-big-step and omni-small-step styles of semantic judgments. These styles describe operational semantics by relating starting states to sets of outcomes rather than to individual outcomes. A single derivation of these semantics for a particular starting state and program describes all possible nondeterministic executions (hence the name omni ), whereas in traditional small-step and big-step semantics, each derivation only talks about one single execution. This restructuring allows for straightforward modeling of both nondeterminism and undefined behavior as commonly encountered in sequential functional and imperative programs. Specifically, omnisemantics inherently assert safety (i.e., they guarantee that none of the execution branches gets stuck), while traditional semantics need either a separate judgment or additional error markers to specify safety in the presence of nondeterminism. Omnisemantics can be understood as an inductively defined weakest-precondition semantics (or more generally, predicate-transformer semantics) that does not involve invariants for loops and recursion but instead uses unrolling rules like in traditional small-step and big-step semantics. Omnisemantics were previously described in association with several projects, but we believe the technique has been underappreciated and deserves a well-motivated, extensive, and pedagogical presentation of its benefits. We also explore several novel aspects associated with these semantics, in particular, their use in type-safety proofs for lambda calculi, partial-correctness reasoning, and forward proofs of compiler correctness for terminating but potentially nondeterministic programs being compiled to nondeterministic target languages. All results in this article are formalized in Coq.
33
Separation logic: a logic for shared mutable data structures
John Reynolds · 2003 · 2.2K citations
A Syntactic Approach to Type Soundness
Andy Wright, Matthias Felleisen · Information and Computation · 1994 · 1.1K citations
Gordon Plotkin · SIAM Journal on Computing · 1976 · 639 citations
A Formally Verified Compiler Back-end
Xavier Leroy · Journal of Automated Reasoning · 2009 · 487 citations · Full text
Forward and Backward Simulations
Nancy Lynch, Frits Vaandrager · Information and Computation · 1995 · 402 citations · Full text