Local Type Inference for Context-Free Session Types
Bernardo Almeida Andreia Mordido Vasco T. Vasconcelos · 2025
Read Local Type Inference for Context-Free Session Types by Bernardo Almeida Andreia Mordido Vasco T. Vasconcelos (2025) 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-2505-20855.txt.
Introduction
Almeida, Mordido, and Vasconcelos built a way to infer the types of message protocols on its own in twenty twenty-five. Session types spell out the allowed pattern of messages between programs. They catch protocol slips while code is compiled. Context-free session types allow richer chains, but writing type notes all through a program is a chore.
Their local type inference method grows out of type checking that works both ways. Known type facts flow through a program as it is checked. The method backs first-class polymorphism. It handles the hard parts context-free types bring, like chaining steps and judging when two types match. The payoff is plain: no type notes are needed where code puts a generic piece to work. The authors call it a step toward easier languages, built on System F with context-free session types.
Catalog record
| CREATOR | Bernardo Almeida Andreia Mordido Vasco T. Vasconcelos |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-20855
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Local Type Inference for Context-Free Session Types Bernardo Almeida Andreia Mordido Vasco T. Vasconcelos Abstract We address the problem of local type inference for a language based on System F with context-free session types. We present an algorithm that leverages the bidirectional type checking approach to propagate type information, enabling first class polymorphism while addressing the intricacies brought about by the sequential composition operator and type equivalence. The algorithm improves the language’s usability by eliminating the need for type annotations at type application sites. 1 Introduction Type inference is a fundamental aspect of programming language design, allowing type information to be automatically determined. This mechanism simplifies code development, while enhancing code readability. By inferring types, compilers gather enough type information to statically verify programs, thereby preventing a range of runtime errors. However, full type inference in expressive type systems such as System F present considerable theoretical and practical challenges. The presence of impredicative polymorphism, where type variables can be instantiated with polymorphic types, increases the complexity of type inference, leading to undecidability of type checking in the general case [ 28 ] . Therefore, type systems based on System F usually impose syntactic constraints via type annotations. Research in this area continues to explore strategies for balancing decidability with the amount of annotations required. While excessive annotations, such as those required in polymorphic applications, can be cumbersome and contribute to code complexity, annotations in top-level function definitions and their bound variables are valuable for documentation and enhance code clarity. Local type inference was proposed by Pierce and Turner [ 20 ] aiming at infering type annotations at application sites. Furthermore, due to its locality (only at the application level) these mechanisms offer better error messages to the programmer than those provided by full type inference. In this work we propose a local type inference algorithm for FreeST [ 4 , 5 ] , a concurrent programming language based on System F where processes communicate on heterogeneously typed-channels governed by context-free session types [ 23 ] . Context-free session types are able to describe non-regular protocols and include types for describing message sending ( ! T ) and receiving ( ? T ), sequential composition of two protocols ( T ; U ) and the neutral element of composition Skip . The sequential composition operator is particularly effective in protocol composition and decomposition. The gain in expressivity comes with a cost: type equivalence, usually defined by a (non-necessarily finite) type bisimulation, presents a substantial challenge. Consequently (local) type inference becomes slightly more complicated than usual since we need to account for a complex notion of type equivalence. Consider as an example the following function that takes an integer value and a channel, sends the successor of the value on the channel, and returns the continuation of that channel. ⬇ f : Int \rightarrow ! Int ; Close \rightarrow Close f x c = send ( x + 1 ) c The channel is of type ! Int ; Close , meaning that an integer should be sent and then the channel should be closed. Function f consumes the initial part of the channel (the ! Int part) and returns the channel (now of type Close ). The primitive send function has type \forall a . a \rightarrow \forall b . ! a ; b \rightarrow b , meaning that, whenever we use it, we start by instantiating type variable a with, say, type T , then provide a value of that type, then instantiate type variable b with, say, type S , and finally provide a channel of type ! T ; S . In return, we expect the continuation of the channel (at this stage of type S ). In practice, the programmer must provide explicit annotations to guide the type checker. In FreeST , type instantiations are denoted by @ . In order to properly type check, our function f should thus be written as follows: ⬇ f : Int \rightarrow ! Int ; Close \rightarrow Close f x c = send @ Int ( x + 1 ) @ Close c To be faithful to the type specified for f , the programmer instantiates type variable a with type Int (through annotation @ Int ) and b with type Close (through annotation @ Close ). After all, the programmer has to figure out not only which annotations are required but also where to place them . In such a small example the task may seem easy, but with more complex protocols things escalate quickly. One example is when we require polymorphic instantiation, that is, the annotation is itself a polymorphic type. Aiming to get rid of this burden of annotations in type applications, we propose a new local type inference for FreeST . Our proposal builds primarily on Quick Look [ 21 ] , which enables the inference of type annotations in polymorphic applications. However, the presence of context-free session types introduces additional subtleties. In particular, we must account for explicit recursive types and the monoidal laws introduced by the sequential composition operator (with type Skip as the identity element), and treats Close and Wait as left absorbing types. The main contributions of our work are: • A local type inference algorithm for FreeST , • A novel type matching algorithm that deals with context-free session types, • A prototype implementation, integrated in the FreeST compiler. The rest of the paper is organised as follows. Section 2 introduces a rather stripped down version of FreeST , yet rich enough to explain the main issues in local type inference for context-free session types. Then, section 3 introduces the inference algorithm. Section 4 evaluates the algorithm, section 5 discusses related work, and section 6 concludes the paper. 2 Syntax This section briefly introduces the language we use to illustrate local type inference. We work with a rather stripped down version of the FreeST programming language [ 3 ] , keeping only the relevant constructors. The language relies on a few base sets: type variables , denoted by \color[rgb]{0,0.5,1}{\alpha},\color[rgb]{0,0.5,1}{\beta},\color[rgb]{0,0.5,1}{\gamma} , term variables denoted by \color[rgb]{1,0.23,0.13}{x},\color[rgb]{1,0.23,0.13}{y},\color[rgb]{1,0.23,0.13}{z} and, anticipating type inference, instantiation variables denoted by \color[rgb]{0,0.5,1}{X},\color[rgb]{0,0.5,1}{Y},\color[rgb]{0,0.5,1}{Z} . The syntax is in figure 1 . \displaystyle\color[rgb]{0,0.5,1}{\sharp}\;::=\;\; \displaystyle\color[rgb]{0,0.5,1}{!}\;\mid\;\color[rgb]{0,0.5,1}{?} Polarities \displaystyle\color[rgb]{0,0.5,1}{\star}\;::=\;\; \displaystyle\color[rgb]{0,0.5,1}{\&}\;\mid\;\color[rgb]{0,0.5,1}{\oplus} Views \displaystyle\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}\;::=\;\; \displaystyle\color[rgb]{0,0.5,1}{\mathsf{End}_{\color[rgb]{0,0.5,1}{\sharp}}}\;\mid\;{\color[rgb]{0,0.5,1}{\sharp}}\,\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}}\;\mid\;{\color[rgb]{0,0.5,1}{\star}}\,\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\{{\ell\colon T_{\ell}}\}}_{\ell\in L}}\;\mid\;\color[rgb]{0,0.5,1}{{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}};{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}}}\;\mid\;\color[rgb]{0,0.5,1}{\mathsf{Skip}}\;\mid\;\color[rgb]{0,0.5,1}{\mu{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\alpha}}}.{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}}}} Types \displaystyle\;\mid\;\color[rgb]{0,0.5,1}{\alpha}\;\mid\;\color[rgb]{0,0.5,1}{{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}}\rightarrow{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}}}\;\mid\;\color[rgb]{0,0.5,1}{\forall{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\alpha}}}.\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}}}\;\mid\;\color[rgb]{0,0.5,1}{X} \displaystyle\color[rgb]{1,0.23,0.13}{\color[rgb]{1,0.23,0.13}{e}}\;::=\;\; \displaystyle\color[rgb]{1,0.23,0.13}{\lambda{x}\colon{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}}}.{\color[rgb]{1,0.23,0.13}{\color[rgb]{1,0.23,0.13}{\color[rgb]{1,0.23,0.13}{e}}}}}\;\mid\;\color[rgb]{1,0.23,0.13}{\Lambda{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\alpha}}}.{\color[rgb]{1,0.23,0.13}{\color[rgb]{1,0.23,0.13}{\color[rgb]{1,0.23,0.13}{e}}}}}\;\mid\;\color[rgb]{1,0.23,0.13}{\color[rgb]{1,0.23,0.13}{h}\;\color[rgb]{1,0.23,0.13}{\pi}_{1}\color[rgb]{0,0,0}{,}\dots,\color[rgb]{1,0.23,0.13}{\pi}_{n}} Expressions \displaystyle\color[rgb]{1,0.23,0.13}{h}\;::=\;\; \displaystyle\color[rgb]{1,0.23,0.13}{x}\;\mid\;\color[rgb]{1,0.23,0.13}{\lambda{x}\colon{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}}}.{\color[rgb]{1,0.23,0.13}{\color[rgb]{1,0.23,0.13}{\color[rgb]{1,0.23,0.13}{e}}}}}\;\mid\;\color[rgb]{1,0.23,0.13}{\Lambda{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\alpha}}}.{\color[rgb]{1,0.23,0.13}{\color[rgb]{1,0.23,0.13}{\color[rgb]{1,0.23,0.13}{e}}}}} Application heads \displaystyle\color[rgb]{1,0.23,0.13}{\pi}\;::=\;\; \displaystyle\color[rgb]{1,0.23,0.13}{\color[rgb]{1,0.23,0.13}{e}}\;\mid\;\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}} Function arguments Figure 1: Syntax of types and expressions Session types include channel closing ( \color[rgb]{0,0.5,1}{\mathsf{Close}} and \color[rgb]{0,0.5,1}{\mathsf{Wait}} , collectively denoted by \color[rgb]{0,0.5,1}{\mathsf{End}_{\color[rgb]{0,0.5,1}{\sharp}}} ), message sending ( {\color[rgb]{0,0.5,1}{!}}\,\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}} ) and receiving ( {\color[rgb]{0,0.5,1}{?}}\,\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}} ), internal ( {\color[rgb]{0,0.5,1}{\oplus}}\,\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\{{\ell\colon T_{\ell}}\}}_{\ell\in L}} ) and external ( {\color[rgb]{0,0.5,1}{\&}}\,\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\{{\ell\colon T_{\ell}}\}}_{\ell\in L}} ) choices, the sequential composition of types ( \color[rgb]{0,0.5,1}{{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}_{\!\!{1}}}};{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}_{\!\!{2}}}}} ) and \color[rgb]{0,0.5,1}{\mathsf{Skip}} , denoting the absence of communication. Functional types include functions ( \color[rgb]{0,0.5,1}{{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}_{\!\!{1}}}}\rightarrow{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}_{\!\!{2}}}}} ) and universal types ( \color[rgb]{0,0.5,1}{\forall{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\alpha}}}.\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}}} ). Pairs and sums, records and variants, the unit type and other standard functional types can be easily incorporated. Recursive types ( \color[rgb]{0,0.5,1}{\mu{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\alpha}}}.{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{\color[rgb]{0,0.5,1}{T}}}}} ) are sessions only, for simplicity. Types are filtered by a collection of type formation rules that essentially guarantee contractiveness, that is, that guarantee that continuous unfolding of recursive types eventually yields a proper (non- \color[rgb]{0,0.5,1}{\mu} ) type constructor. The situation is slightly complicated by the introduction of context-free