Special Delivery: Programming with Mailbox Types (Extended Version)
Pith reviewed 2026-05-24 08:43 UTC · model grok-4.3
The pith
Pat is the first programming language to incorporate mailbox types for detecting actor communication errors.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Mailbox types, which capture mailbox contents as commutative regular expressions and are augmented with interfaces for finer-grained control, can be embedded in a full programming language Pat together with an algorithmic type checker that detects four specific classes of behavioural error in addition to data-type mistakes.
What carries the argument
Mailbox types that represent mailbox contents via commutative regular expressions, together with quasi-linear typing to manage aliasing and a co-contextual algorithmic system obtained via backwards bidirectional typing.
If this is right
- Type checking in Pat catches protocol violations, unexpected messages, forgotten replies and self-deadlocks before execution.
- The algorithmic type system is sound and complete with respect to the declarative system.
- Quasi-linear typing combined with backwards bidirectional typing suffices to handle aliasing and nested contexts.
- The language supports higher-order functions, sums, products and lists while still enforcing mailbox protocols.
Where Pith is reading between the lines
- The same mailbox-type discipline could be retrofitted to existing actor runtimes such as Erlang or Akka.
- Interfaces for finer-grained mailbox reasoning may generalise to other message-passing calculi.
- The co-contextual approach may simplify type inference for other behavioural type systems that must cope with aliasing.
Load-bearing premise
The difficulties created by aliasing and nested evaluation contexts when moving mailbox types from a process calculus into a programming language can be solved by quasi-linear typing plus a co-contextual algorithmic checker.
What would settle it
An actor program that performs a protocol violation, sends an unexpected message, omits a required reply, or deadlocks on itself yet is accepted by the Pat type checker (or a well-behaved program that the checker rejects).
Figures
read the original abstract
The asynchronous and unidirectional communication model supported by mailboxes is a key reason for the success of actor languages like Erlang and Elixir for implementing reliable and scalable distributed systems. Although actors eliminate many of the issues stemming from shared memory concurrency, they remain vulnerable to communication errors such as protocol violations and deadlocks. Behavioural types make it possible to detect communication errors early in the development process, but most work has addressed channel-based languages rather than actor languages. Mailbox types are a novel behavioural type system for actors first introduced for a process calculus, and capture the contents of a mailbox as a commutative regular expression. Due to aliasing and nested evaluation contexts, moving from a process calculus to a programming language is challenging. This paper presents Pat, the first programming language incorporating mailbox types, and describes an algorithmic type system. Pat is a higher-order functional language with sums, products, and lists, along with interfaces that allow finer-grained reasoning about mailbox contents. Typechecking in Pat detects four classes of behavioural error: protocol violation, unexpected message, forgotten reply and self-deadlock, as well as the usual data type errors. The Pat type system makes essential use of quasi-linear typing to tame some of the complexity introduced by aliasing. We make use of a co-contextual algorithmic type system, achieved through a novel use of backwards bidirectional typing, and we prove it sound and complete with respect to our declarative type system. We implement a type checker, and use it to demonstrate the expressiveness of Pat on a factory automation case study and a series of examples from the Savina actor benchmark suite. This establishes a foundation for applying mailbox typing to practical actor languages.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces Pat, the first programming language to incorporate mailbox types (commutative regular expressions over mailbox contents). Pat is a higher-order functional language with sums, products, and lists, plus interfaces for finer-grained mailbox reasoning. It defines a declarative type system and an algorithmic variant (via quasi-linear typing and backwards-bidirectional co-contextual typing) that is proved sound and complete w.r.t. the declarative system; the implementation detects protocol violations, unexpected messages, forgotten replies, self-deadlocks, and ordinary data-type errors. The system is evaluated on a factory-automation case study and Savina actor benchmarks.
Significance. If the soundness/completeness claims and the handling of aliasing via quasi-linear types hold, the work supplies the first practical bridge from mailbox-type process calculi to a full programming language, enabling early detection of four classes of actor communication errors. The claimed machine-checked or detailed proofs, the implemented checker, and the concrete case-study evaluation are explicit strengths that would make the contribution self-contained and reproducible.
major comments (2)
- [§4] §4 (algorithmic type system) and the associated soundness/completeness theorem: the central claim that the co-contextual backwards-bidirectional algorithm is sound and complete rests on the quasi-linear discipline; without an explicit statement of the quasi-linearity invariant preserved by the algorithmic rules (or a machine-checked proof artifact), it is difficult to verify that aliasing and nested evaluation contexts are fully tamed.
- [§3] §3 (quasi-linear typing) and the transition from the prior process calculus: the manuscript states that quasi-linear typing suffices to address aliasing, yet the load-bearing step—how the type rules prevent duplication of mailbox references inside higher-order functions or nested contexts—is only sketched; a small counter-example showing what would go wrong without quasi-linearity would make the design choice falsifiable.
minor comments (3)
- The abstract and introduction repeatedly cite the four error classes; a single running example that illustrates each class (with the corresponding mailbox-type error message) would improve readability.
- Notation for commutative regular expressions and interfaces is introduced without an early concrete example; adding one before the formal rules would help readers unfamiliar with the prior calculus paper.
- [Evaluation] The Savina evaluation reports successful type-checking but does not tabulate type-checking times or the size of the generated constraints; these metrics would strengthen the practicality claim.
Simulated Author's Rebuttal
We thank the referee for the constructive review and the recommendation of minor revision. The comments highlight opportunities to improve clarity around the quasi-linear discipline and its role in the algorithmic type system. We address each point below and will incorporate the suggested clarifications.
read point-by-point responses
-
Referee: [§4] §4 (algorithmic type system) and the associated soundness/completeness theorem: the central claim that the co-contextual backwards-bidirectional algorithm is sound and complete rests on the quasi-linear discipline; without an explicit statement of the quasi-linearity invariant preserved by the algorithmic rules (or a machine-checked proof artifact), it is difficult to verify that aliasing and nested evaluation contexts are fully tamed.
Authors: We agree that an explicit statement of the invariant would aid verification. In the revised manuscript we will add a concise paragraph in §4 that states the quasi-linearity invariant (mailbox references may not be duplicated except through the controlled mechanisms of interfaces and the co-contextual rules) and indicates how each algorithmic rule preserves it. The existing soundness and completeness proofs in the appendix already rely on this invariant via the correspondence with the declarative system; we will add a short lemma linking the invariant to the algorithmic judgements. We do not currently provide a machine-checked artifact, as the proofs were developed by detailed hand-written case analysis. revision: yes
-
Referee: [§3] §3 (quasi-linear typing) and the transition from the prior process calculus: the manuscript states that quasi-linear typing suffices to address aliasing, yet the load-bearing step—how the type rules prevent duplication of mailbox references inside higher-order functions or nested contexts—is only sketched; a small counter-example showing what would go wrong without quasi-linearity would make the design choice falsifiable.
Authors: We accept that a concrete counter-example would strengthen the exposition. In the revision we will insert a short example in §3 that shows a higher-order function receiving a mailbox reference; without the quasi-linear restriction the reference could be duplicated and passed to two distinct actor creations, violating the mailbox-type invariant. The example will be accompanied by the corresponding typing derivation that fails under the quasi-linear rules. revision: yes
Circularity Check
No significant circularity detected
full rationale
The paper's core contributions consist of the design of the new language Pat, its declarative type system, an algorithmic version with explicit soundness and completeness proofs relative to the declarative system, and an implementation evaluated on case studies. These elements are developed directly to address aliasing and nested contexts via quasi-linear typing and backwards-bidirectional typing. Prior process-calculus work is cited only as background for the mailbox-type concept; the extension to a full programming language with interfaces, sums/products/lists, and error detection classes is presented as an independent step with its own formal development and implementation. No derivation step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation chain. The claims remain self-contained against external benchmarks and case studies.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Mailbox contents can be modeled by commutative regular expressions
- ad hoc to paper Quasi-linear typing tames aliasing and nested evaluation contexts sufficiently for a practical language
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We make essential and novel use of quasi-linear typing to tame some of the complexity introduced by aliasing, and our algorithmic type system is necessarily co-contextual, achieved through a novel use of backwards bidirectional typing
-
IndisputableMonolith/Foundation/AbsoluteFloorClosure.leanabsolute_floor_iff_bare_distinguishability unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Mailbox types are a novel behavioural type system for mailboxes first introduced for a process calculus by de’Liguoro and Padovani in 2018
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.
Reference graph
Works this paper leans on
-
[1]
L 3: A Linear Language with Locations. Fundam. Informaticae 77, 4 (2007), 397–449. 27 , , Simon Fowler, Duncan Paul Attard, Franciszek Sowul, Simon J. Gay, and Phil Trinder Bernardo Almeida, Andreia Mordido, Peter Thiemann, and Vasco T. Vasconcelos
work page 2007
-
[2]
Polymorphic lambda calculus with context-free session types. Inf. Comput. 289, Part (2022), 104948. Roberto M. Amadio, Ilaria Castellani, and Davide Sangiorgi
work page 2022
-
[3]
On Bisimulations for the Asynchronous pi-Calculus. Theor. Comput. Sci. 195, 2 (1998), 291–324. Davide Ancona, Viviana Bono, Mario Bravetti, Joana Campos, Giuseppe Castagna, Pierre-Malo Deniélou, Simon J. Gay, Nils Gesbert, Elena Giachino, Raymond Hu, Einar Broch Johnsen, Francisco Martins, Viviana Mascardi, Fabrizio Montesi, Rumyana Neykova, Nicholas Ng, ...
work page 1998
-
[4]
Behavioral Types in Programming Languages. Found. Trends Program. Lang. 3, 2-3 (2016), 95–230. https://doi.org/10.1561/2500000031 Mehdi Bagherzadeh and Hridesh Rajan
-
[5]
Journal of the ACM (JACM) 11, 4 (1964), 481–494
Derivatives of regular expressions. Journal of the ACM (JACM) 11, 4 (1964), 481–494. Avik Chaudhuri
work page 1964
-
[6]
Fair termination of binary sessions. Proc. ACM Program. Lang. 6, POPL (2022), 1–30. Silvia Crafa and Luca Padovani
work page 2022
- [7]
-
[8]
Bidirectional Typing. ACM Comput. Surv. 54, 5 (2022), 98:1–98:38. Robert Ennals, Richard Sharp, and Alan Mycroft
work page 2022
-
[9]
Linear Types for Packet Processing. In Programming Languages and Systems, 13th European Symposium on Programming, ESOP 2004, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004, Barcelona, Spain, March 29 - April 2, 2004, Proceedings (Lecture Notes in Computer Science, Vol. 2986), David A. Schmidt (Ed.). Springer,...
-
[10]
Linear type theory for asynchronous session types.J. Funct. Program. 20, 1 (2010), 19–50. Rosita Gerbo and Luca Padovani
work page 2010
- [11]
-
[12]
Types for Dyadic Interaction. In CONCUR ’93, 4th International Conference on Concurrency Theory, Hildesheim, Germany, August 23-26, 1993, Proceedings (Lecture Notes in Computer Science, Vol. 715), Eike Best (Ed.). Springer, 509–523. https://doi.org/10.1007/3-540-57208-2_35 Kohei Honda, Vasco Thudichum Vasconcelos, and Makoto Kubo
-
[13]
Multiparty Asynchronous Session Types. J. ACM 63, 1 (2016), 9:1–9:67. Mark W. Hopkins and Dexter Kozen
work page 2016
-
[14]
Foundations of Session Types and Behavioural Contracts. ACM Comput. Surv. 49, 1 (2016), 3:1–3:36. https://doi.org/10.1145/2873052 Shams Mahmood Imam and Vivek Sarkar
-
[15]
Information and Computation 185, 2 (2003), 182–210
Modelling environments in call-by-value programming languages. Information and Computation 185, 2 (2003), 182–210. Sam Lindley and J. Garrett Morris
work page 2003
-
[16]
Rumyana Neykova and Nobuko Yoshida
Springer, 95–109. Rumyana Neykova and Nobuko Yoshida. 2017a. Let it recover: multiparty protocol-induced recovery. In CC. ACM, 98–108. Rumyana Neykova and Nobuko Yoshida. 2017b. Multiparty Session Actors. Log. Methods Comput. Sci. 13, 1 (2017). Leo Osvald, Grégory M. Essertel, Xilun Wu, Lilliam I. González Alayón, and Tiark Rompf
work page 2017
-
[17]
Springer, 88–102. Luca Padovani. 2018a. Deadlock-Free Typestate-Oriented Programming. Art Sci. Eng. Program. 2, 3 (2018),
work page 2018
-
[18]
Luca Padovani. 2018b. Mailbox Calculus Checker. https://boystrange.github.io/mcc/ Luca Padovani. 2018c. A type checking algorithm for concurrent object protocols. Journal of Logical and Algebraic Methods in Programming 100 (2018), 16–35. https://doi.org/10.1016/j.jlamp.2018.06.001 Luca Padovani
- [19]
-
[20]
On Context-Free Languages. J. ACM 13, 4 (1966), 570–581. Benjamin C. Pierce and David N. Turner
work page 1966
- [21]
-
[22]
Intrinsically typed compilation with nameless labels. Proc. ACM Program. Lang. 5, POPL (2021), 1–28. Alceste Scalas, Nobuko Yoshida, and Elias Benussi
work page 2021
-
[23]
An Interaction-based Language and its Typing System. In PARLE ’94: Parallel Architectures and Languages Europe, 6th International PARLE Conference, Athens, Greece, July 4-8, 1994, Proceedings (Lecture Notes in Computer Science, Vol
work page 1994
-
[24]
Maritsas, George Philokyprou, and Sergios Theodoridis (Eds.)
, Constantine Halatsis, Dimitris G. Maritsas, George Philokyprou, and Sergios Theodoridis (Eds.). Springer, 398–413. https://doi.org/10.1007/3-540-58184-7_118 Samira Tasharofi, Peter Dinges, and Ralph E. Johnson
-
[25]
ACM Transactions on Programming Languages and Systems (TOPLAS) 39, 4 (2017), 1–46
Scaling reliably: Improving the scalability of the Erlang distributed actor platform. ACM Transactions on Programming Languages and Systems (TOPLAS) 39, 4 (2017), 1–46. 29 , , Simon Fowler, Duncan Paul Attard, Franciszek Sowul, Simon J. Gay, and Phil Trinder Vasco T. Vasconcelos
work page 2017
-
[26]
Fundamentals of session types. Inf. Comput. 217 (2012), 52–70. Philip Wadler
work page 2012
-
[27]
Propositions as sessions. J. Funct. Program. 24, 2-3 (2014), 384–418. Noam Zeilberger
work page 2014
-
[28]
Pat programs are type checked following the six-stage pipeline of Fig
Pat type checking pipeline C SUPPLEMENTARY IMPLEMENTATION AND EVALUATION MATERIAL Our typechecking tool processes Pat programs specified in plain text files that are structured in three segments: (1) Interface definitions that establish the set of messages that a mailbox can receive; (2) Function definitions that specify processes that are instantiable us...
work page 2012
-
[29]
The Robot 39 , , Simon Fowler, Duncan Paul Attard, Franciszek Sowul, Simon J
When a part is requested, the Warehouse transitions to theengaged state and awaits a Deliver message from the Door, notifying the Robot collecting the part via a Delivered message (lines 86–92). The Robot 39 , , Simon Fowler, Duncan Paul Attard, Franciszek Sowul, Simon J. Gay, and Phil Trinder acknowledges the delivery by sending PartTaken, as the guard o...
work page 2018
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.