Strong Normalisation for Asynchronous Effects

Danel Ahman; Ilja Sobolev

arxiv: 2602.05528 · v2 · submitted 2026-02-05 · 💻 cs.PL · cs.LO

Strong Normalisation for Asynchronous Effects

Danel Ahman , Ilja Sobolev This is my paper

Pith reviewed 2026-05-16 07:18 UTC · model grok-4.3

classification 💻 cs.PL cs.LO

keywords strong normalisationasynchronous effectsalgebraic effectseffect handlersprogramming calculistrong normalizationAgda formalisationconcurrent effects

0 comments

The pith

The asynchronous effects calculus is strongly normalising once general recursion is removed.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that a calculus supporting asynchronous algebraic effects through decoupled signalling of operations and interrupting computations with their results becomes strongly normalising when general recursion is removed. This covers both sequential programs and their parallel compositions, which model pre-emptive multi-threading and cancellable remote calls. The authors also show that the sequential fragment remains strongly normalising after reintroducing a controlled form of interrupt-driven recursion. Proofs build compositionally on an existing top-top lifting method and are formalised in Agda. A reader would care because termination guarantees are a basic safety property for languages that combine effects with concurrency.

Core claim

If general recursion is removed from the asynchronous effects calculus, the remaining system is strongly normalising in both its sequential and parallel components. Moreover, the sequential part remains strongly normalising when a controlled amount of interrupt-driven recursive behaviour is added back.

What carries the argument

Compositional extension of Lindley and Stark's top-top lifting technique, applied to the calculus whose operations are split into signals that request implementations and interrupts that deliver results to handlers.

If this is right

Every well-typed program terminates, including those that use parallel composition of threads.
The sequential fragment still terminates when interrupt handlers are allowed to trigger limited recursion.
Normalisation holds uniformly across the sequential and concurrent fragments of the language.
The top-top lifting technique extends directly to asynchronous variants of algebraic effects.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Designers of languages with async effects could adopt similar recursion restrictions to obtain termination without losing basic concurrency primitives.
The same controlled-interrupt approach might be tested in other models such as actor calculi or session-typed processes.
Mechanised proofs in Agda open the door to verified extensions that add more concurrency features while preserving normalisation.

Load-bearing premise

That removing general recursion, or restricting reintroduced recursion to controlled interrupt forms, prevents any infinite reduction sequences in well-typed terms.

What would settle it

A closed well-typed term in the recursion-free calculus that admits an infinite reduction sequence would falsify the claim.

read the original abstract

Asynchronous effects of Ahman and Pretnar complement the conventional synchronous treatment of algebraic effects with asynchrony based on decoupling the execution of algebraic operation calls into signalling that an operation's implementation needs to be executed, and into interrupting a running computation with the operation's result, to which the computation can react by installing matching interrupt handlers. Beyond providing asynchrony for algebraic effects, the resulting core calculus also naturally models examples such as pre-emptive multi-threading, (cancellable) remote function calls, and multi-party applications. In this paper, we study the normalisation properties of this calculus. We prove that if one removes general recursion from it, then the remaining calculus is strongly normalising, including both its sequential and parallel parts. To cover more interesting programs, we also prove that the sequential part of the calculus remains strongly normalising when a controlled amount of interrupt-driven recursive behaviour is reintroduced. Our normalisation proofs are structured compositionally as an extension of Lindley and Stark's $\top\top$-lifting-based approach for proving strong normalisation of effectful languages. All our results are also formalised in Agda.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

They deliver a machine-checked Agda proof that the asynchronous effects calculus is strongly normalising without general recursion, covering sequential and parallel fragments, plus controlled interrupt recursion for the sequential part.

read the letter

The main thing to know is that this paper gives a full Agda formalisation proving strong normalisation for the asynchronous effects calculus once general recursion is removed. The result covers both the sequential and parallel parts, and they also show the sequential fragment stays strongly normalising when a limited form of interrupt-driven recursion is added back in. The proof extends Lindley and Stark's compositional top-top lifting approach to handle the signalling and interrupt mechanics of asynchrony. Having the whole argument checked in Agda against the operational semantics is the strongest part of the work. It removes any doubt about whether the lifting handles the parallel and asynchronous cases correctly. The paper does a reasonable job of making the result more applicable by reintroducing controlled recursion rather than stopping at the fully terminating fragment. This is a clear, incremental advance on the prior definition of the calculus by Ahman and Pretnar. The main limitation is the recursion restriction itself. Dropping general recursion is necessary for the strong normalisation claim, but it does narrow the practical reach. The controlled interrupt version helps, yet it still rules out many natural recursive patterns one might want in real programs. The abstract gives no step-by-step view of how the lifting is adapted for parallelism, but the formalisation makes that less of an issue. This paper is for people working on algebraic effects, type theory for concurrency, and normalisation proofs in effectful languages. A reader who needs formal termination results for similar calculi will find it directly useful. It deserves peer review because the machine-checked proof supplies concrete evidence that the claims are reliable, even if the scope stays within the subfield.

Referee Report

0 major / 2 minor

Summary. The paper claims to prove strong normalisation for a calculus of asynchronous algebraic effects once general recursion is removed, covering both sequential and parallel fragments. It additionally shows that the sequential fragment remains strongly normalising when a controlled form of interrupt-driven recursion is reintroduced. The proofs are structured as a compositional extension of Lindley and Stark's ⊤⊤-lifting technique and are fully formalised in Agda.

Significance. If the result holds, the work supplies a machine-checked normalisation theorem for a calculus that directly models asynchronous effects such as pre-emptive multi-threading, cancellable remote calls, and multi-party interaction. The Agda formalisation, which verifies the proofs against the operational semantics, constitutes a clear strength: the argument is parameter-free, extends an established technique without circularity, and discharges the recursion-restriction hypothesis explicitly.

minor comments (2)

[Abstract] Abstract: the summary of the lifting argument does not indicate how asynchrony (signalling and interrupt handlers) is accommodated inside the ⊤⊤-lifting construction; a single sentence on this point would improve visibility without lengthening the abstract.
[Proof section (likely §4 or §5)] The manuscript would benefit from an explicit statement, early in the proof section, of the precise inductive hypothesis used for the parallel fragment; this would make the compositional structure easier to follow.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the paper, the recognition of the significance of the strong normalisation result for the asynchronous effects calculus, and the recommendation to accept. We are pleased that the compositional extension of the ⊤⊤-lifting technique and the Agda formalisation were viewed as strengths.

Circularity Check

0 steps flagged

No significant circularity; machine-checked Agda proof extends established technique

full rationale

The paper's central results are a compositional extension of Lindley and Stark's ⊤⊤-lifting for strong normalisation, applied after explicitly removing general recursion (or reintroducing only controlled interrupt-driven recursion). All proofs are parameter-free and fully formalised in Agda against the operational semantics, providing independent verification. No steps reduce by construction to fitted inputs, self-definitions, or load-bearing self-citations; the Lindley-Stark citation is external prior work whose technique is re-verified here rather than assumed without check.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard definition of the asynchronous effects calculus from prior work and the established ⊤⊤-lifting technique, with no free parameters, no invented entities, and only standard type-theoretic assumptions.

axioms (2)

domain assumption Operational semantics and typing rules of the asynchronous effects calculus as previously defined
The normalisation proof assumes the core calculus definition from Ahman and Pretnar.
standard math Properties of the ⊤⊤-lifting technique for proving strong normalisation in effectful languages
The proof extends Lindley and Stark's existing method.

pith-pipeline@v0.9.0 · 5487 in / 1405 out tokens · 100447 ms · 2026-05-16T07:18:29.639862+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We prove that if one removes general recursion from it, then the remaining calculus is strongly normalising... structured compositionally as an extension of Lindley and Stark’s ⊤⊤-lifting-based approach

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.