An Equational Axiomatization of Dynamic Threads via Algebraic Effects DOI: 10.1145/3776706 Journal: PACMPL Volume: 10 POPL 64 1 CCS: Theory of computation Denotational semantics CCS: Theory of computation Categorical semantics CCS: Theory of computation Concurrency

Ohad Kammar, Jack Liell-Cock, Sam Lindley, Cristina Matache, Sam Staton · 2026

Read An Equational Axiomatization of Dynamic Threads via Algebraic Effects DOI: 10.1145/3776706 Journal: PACMPL Volume: 10 POPL 64 1 CCS: Theory of computation Denotational semantics CCS: Theory of computation Categorical semantics CCS: Theory of computation Concurrency by Ohad Kammar, Jack Liell-Cock, Sam Lindley, Cristina Matache, Sam Staton (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-05850.txt.

Description

Concurrent programs spawn threads dynamically, and giving them a complete set of equations has been a long standing goal in semantics. Ohad Kammar, Jack Liell-Cock, and 3 co-authors use algebraic effects to axiomatize dynamic threads. The theory builds on two primitives: fork, which creates a child thread and hands its name to the parent, and wait, which blocks until children finish.

Their parameterized algebraic theory adds basic atomic actions and laws such as associativity of fork. The axiomatization is complete in two senses. It captures equality of labelled posets, an established model of concurrency. It also proves any two open expressions that agree under all closing substitutions. The team then extends the analysis to a small concurrent language with operational and denotational semantics, shown sound, adequate, and fully abstract at first order. The paper was published at a leading programming languages conference.

Catalog record

CREATOROhad Kammar, Jack Liell-Cock, Sam Lindley, Cristina Matache, Sam Staton
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE122 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-05850

Browse the full library · About the Tower of Babel