Classical Notions of Computation and the Hasegawa-Thielecke Theorem
Open Access
- 8 January 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (POPL) , 2112-2141
Abstract
In the spirit of the Curry-Howard correspondence between proofs and programs, we define and study a syntax and semantics for classical logic equipped with a computationally involutive negation, using a polarised effect calculus, the linear classical L-calculus. A main challenge in designing a denotational semantics for the calculus is to accommodate both call-by-value and call-by-name evaluation strategies, which leads to a failure of associativity of composition. In order to tackle this issue, we define a notion of adjunction between graph morphisms on non-associative categories, which we use to formulate polarized and non-associative notions of symmetric monoidal closed duploid and of dialogue duploid. We show that they provide a direct style counterpart to adjunction models: linear effect adjunctions for the (linear) call-by-push-value calculus and dialogue chiralities for linear continuations, respectively. In particular, we show that the syntax of the linear classical L-calculus can be interpreted in any dialogue duploid, and that it defines in fact a syntactic dialogue duploid. As an application, we establish, by semantic as well as syntactic means, the Hasegawa-Thielecke theorem, which states that the notions of central map and of thunkable map coincide in any dialogue duploid (in particular, for any double negation monad on a symmetric monoidal category).Keywords
All Related Versions
Funding Information
- European Research Council (670624)
This publication has 58 references indexed in Scilit:
- Models of a Non-associative Composition2014
- The Duality of Computation under Focus2010
- Focalisation and Classical Realisability2009
- The structure of exponentials: Uncovering the dynamics of linear logic proofs2005
- λμ-Calculus: An algorithmic interpretation of classical natural deduction2005
- Call-By-Push-Value: A Subsuming Paradigm2003
- Call-By-Push-Value2003
- Notions of Computation Determine Monads2002
- Weakly distributive categoriesJournal of Pure and Applied Algebra, 1997
- A λ-calculus structure isomorphic to Gentzen-style sequent calculus structure1995