Lune

POPL2023Top-tier venue

Towards a Higher-Order Mathematical Operational Semantics

Sergey Goncharov, Stefan Milius, Lutz Schröder, Stelios Tsampas, Henning Urbat

Abstract

Compositionality proofs in higher-order languages are notoriously involved, and general semantic frameworks guaranteeing compositionality are hard to come by. In particular, Turi and Plotkin’s bialgebraic abstract GSOS framework, which has been successfully applied to obtain off-the-shelf compositionality results for first-order languages, so far does not apply to higher-order languages. In the present work, we develop a theory of abstract GSOS specifications for higher-order languages, in effect transferring the core principles of Turi and Plotkin’s framework to a higher-order setting. In our theory, the operational semantics of higher-order languages is represented by certain dinatural transformations that we term pointed higher-order GSOS laws . We give a general compositionality result that applies to all systems specified in this way and discuss how compositionality of the SKI calculus and the λ-calculus w.r.t. a strong variant of Abramsky’s applicative bisimilarity are obtained as instances.

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.

9 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

  • Bialgebraic Reasoning on Higher-order Program Equivalence cites Weak Similarity in Higher-Order Mathematical Operational Semantics
  • Abstract Operational Methods for Call-by-Push-Value cites Bialgebraic Reasoning on Higher-order Program Equivalence
  • Abstract Operational Methods for Call-by-Push-Value cites Weak Similarity in Higher-Order Mathematical Operational Semantics
  • Composing Codensity Bisimulations cites Weak Similarity in Higher-Order Mathematical Operational Semantics
  • Weak Similarity in Higher-Order Mathematical Operational Semantics cites A Cellular Howe Theorem
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers9

  1. Weak Similarity in Higher-Order Mathematical Operational SemanticsHenning Urbat, Stelios Tsampas, Sergey Goncharov, Stefan Milius et al.LICS 2023 · 10 citations
  2. Diagrammatic Algebra of First Order LogicFilippo Bonchi, Alessandro Di Giorgio, Nathan Haydon, Pawel SobocinskiLICS 2024 · 5 citations
  3. Bialgebraic Reasoning on Higher-order Program EquivalenceSergey Goncharov, Stefan Milius, Stelios Tsampas, Henning UrbatLICS 2024 · 4 citations
  4. Abstract Operational Methods for Call-by-Push-ValueSergey Goncharov, Stelios Tsampas, Henning UrbatPOPL 2025 · 3 citations
  5. Composing Codensity BisimulationsMayuko Kori, Kazuki Watanabe, Jurriaan Rot, Shin-ya KatsumataLICS 2024 · 2 citations

Builds on2

  1. Algebraic models of simple type theories: A polynomial approachNathanael Arkor, Marcelo FioreLICS 2020 · 10 citations
  2. A Cellular Howe TheoremPeio Borthelle, Tom Hirschowitz, Ambroise LafontLICS 2020 · 9 citations

Related papers

  1. Higher Order Bayesian Networks, ExactlyClaudia Faggian, Daniele Pautasso, Gabriele VanoniPOPL 2024 · 4 citations
  2. An Algebraic Approach to Formal System MetatheoryFrancesco GavazzoLICS 2026
  3. The Duality of λ-AbstractionVikraman Choudhury, Simon J. GayPOPL 2025 · 2 citations
  4. Higher-Order Behavioural Conformances via FibrationsHenning UrbatPOPL 2026
  5. A relational theory of effects and coeffectsUgo Dal Lago, Francesco GavazzoPOPL 2022 · 22 citations
Dusk over the sea between two cliffs drawn in fine vertical lines