Lune

POPL2022Top-tier venue

Layered and object-based game semantics

Arthur Oliveira Vale, Paul-André Melliès, Zhong Shao, Jérémie Koenig, Léo Stefanesco

Abstract

Large-scale software verification relies critically on the use of compositional languages, semantic models, specifications, and verification techniques. Recent work on certified abstraction layers synthesizes game semantics, the refinement calculus, and algebraic effects to enable the composition of heterogeneous components into larger certified systems. However, in existing models of certified abstraction layers, compositionality is restricted by the lack of encapsulation of state.

In this paper, we present a novel game model for certified abstraction layers where the semantics of layer interfaces and implementations are defined solely based on their observable behaviors. Our key idea is to leverage Reddy's pioneer work on modeling the semantics of imperative languages not as functions on global states but as objects with their observable behaviors. We show that a layer interface can be modeled as an object type (i.e., a layer signature) plus an object strategy. A layer implementation is then essentially a regular map, in the sense of Reddy, from an object with the underlay signature to that with the overlay signature. A layer implementation is certified when its composition with the underlay object strategy implements the overlay object strategy. We also describe an extension that allows for non-determinism in layer interfaces.

After formulating layer implementations as regular maps between object spaces, we move to concurrency and design a notion of concurrent object space, where sequential traces may be identified modulo permutation of independent operations. We show how to express protected shared object concurrency, and a ticket lock implementation, in a simple model based on regular maps between concurrent object spaces.

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.

5 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Compositionality and Observational Refinement for Linearizability with Crashes cites Refinement-Based Game Semantics for Certified Abstraction Layers
  • Compositionality and Observational Refinement for Linearizability with Crashes cites A Compositional Theory of Linearizability
  • DimSum: A Decentralized Approach to Multi-language Semantics and Verification cites CompCertO: compiling certified open C components
  • Choice Trees: Representing Nondeterministic, Recursive, and Impure Programs in Coq cites Refinement-Based Game Semantics for Certified Abstraction Layers
  • Unifying Compositional Verification and Certified Compilation with a Three-Dimensional Refinement Algebra cites DimSum: A Decentralized Approach to Multi-language Semantics and Verification
  • Unifying Compositional Verification and Certified Compilation with a Three-Dimensional Refinement Algebra cites Refinement-Based Game Semantics for Certified Abstraction Layers
  • Unifying Compositional Verification and Certified Compilation with a Three-Dimensional Refinement Algebra cites CompCertO: compiling certified open C components
  • A Compositional Theory of Linearizability cites Concurrent Separation Logic Meets Template Games
  • A Compositional Theory of Linearizability cites Refinement-Based Game Semantics for Certified Abstraction Layers
  • CompCertO: compiling certified open C components cites Refinement-Based Game Semantics for Certified Abstraction Layers
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers5

  1. Choice Trees: Representing Nondeterministic, Recursive, and Impure Programs in CoqNicolas Chappe, Paul He, Ludovic Henrio, Yannick Zakowski et al.POPL 2023 · 21 citations
  2. DimSum: A Decentralized Approach to Multi-language Semantics and VerificationMichael Sammler, Simon Spies, Youngju Song, Emanuele D'Osualdo et al.POPL 2023 · 18 citations
  3. A Compositional Theory of LinearizabilityArthur Oliveira Vale, Zhong Shao, Yixuan ChenPOPL 2023 · 7 citations
  4. Unifying Compositional Verification and Certified Compilation with a Three-Dimensional Refinement AlgebraYu Zhang, Jérémie Koenig, Zhong Shao, Yuting WangPOPL 2025 · 2 citations
  5. Compositionality and Observational Refinement for Linearizability with CrashesArthur Oliveira Vale, Zhongye Wang, Yixuan Chen, Peixin You et al.OOPSLA 2024 · 1 citation

Builds on4

  1. CompCertO: compiling certified open C componentsJérémie Koenig, Zhong ShaoPLDI 2021 · 18 citations
  2. Virtual timeline: a formal abstraction for verifying preemptive schedulers with temporal isolationMengqi Liu, Lionel Rieg, Zhong Shao, Ronghui Gu et al.POPL 2020 · 17 citations
  3. Refinement-Based Game Semantics for Certified Abstraction LayersJérémie Koenig, Zhong ShaoLICS 2020 · 17 citations
  4. Concurrent Separation Logic Meets Template GamesPaul-André Melliès, Léo StefanescoLICS 2020 · 1 citation

Related papers

  1. The Geometry of Causality: Multi-token Geometry of Interaction and Its Causal UnfoldingSimon Castellan, Pierre ClairambaultPOPL 2023 · 2 citations
  2. Reachability Types, Traces and Full AbstractionBenedict Bunting, Andrzej S. MurawskiLICS 2025 · 2 citations
  3. Verifying higher-order concurrency with data automataAlex Dixon, Ranko Lazic, Andrzej S. Murawski, Igor WalukiewiczLICS 2021 · 2 citations
  4. CompCertOC: Verified Compositional Compilation of Multi-threaded Programs with Shared StacksLing Zhang, Yuting Wang, Yalun Liang, Zhong ShaoPLDI 2025
  5. Verified Lock-Free Session Channels with LinkingThomas Somers, Robbert KrebbersOOPSLA 2024 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines