Remarks on Algebraic Reconstruction of Types and Effects

Patrycja Balik, Szymon Jędras, Piotr Polesiuk · 2026

Read Remarks on Algebraic Reconstruction of Types and Effects by Patrycja Balik, Szymon Jędras, Piotr Polesiuk (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-2601-15455.txt.

Introduction

Patrycja Balik, Szymon Jędras, and Piotr Polesiuk revisit a landmark algorithm from programming language theory. Their 2026 arXiv paper deals with the 1991 work of Jouvelot and Gifford. That work gave an algebraic way to reconstruct types and effects in a program.

A type-and-effect system tracks what a program returns and what side effects it may cause. The 1991 algorithm is a milestone in that area. It has inspired much later work in static analysis. The authors offer remarks on its algebraic structure, clarifying the firm foundations the classic 1991 algorithm rests firmly on.

Catalog record

CREATORPatrycja Balik, Szymon Jędras, Piotr Polesiuk
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-15455

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Remarks on Algebraic Reconstruction of Types and Effects Patrycja Balik, Szymon Jędras, Piotr Polesiuk Abstract . In their 1991 paper “Algebraic Reconstruction of Types and Effects,” Pierre Jouvelot and David Gifford presented a type-and-effect reconstruction algorithm based on an algebraic structure of effects. Their work is considered a milestone in the development of type-and-effect systems, and has inspired numerous subsequent works in the area of static analysis. However, unlike the later research it spawned, the original algorithm considered a language with higher-rank polymorphism, a feature which is challenging to implement correctly. In this note, we identify subtle bugs related to variable binding in their approach to this feature. We revisit their type system and reconstruction algorithm, and describe the discovered issues. 1. Introduction In 1991, Pierre Jouvelot and David Gifford published the seminal paper “Algebraic Reconstruction of Types and Effects” ( Jouvelot and Gifford 1991 ) . Their work was the foundation of many later results in the area of static analysis ( ( Talpin and Jouvelot 1994 ; Tofte and Talpin 1994 ; Nielson and Nielson 1994 ; Birkedal et al. 1996 ; Fähndrich and Aiken 1997 ; Tofte and Birkedal 1998 ; Nielson et al. 1998 ; Helsen and Thiemann 2004 ; Elsman 2024 ) , to name a few), in which effect information was used internally by the compiler, but not exposed directly to the programmer. However, the original language and algorithm considered by Jouvelot and Gifford treated its effect system as a full-fledged user-facing mechanism, with explicit effect polymorphic lambdas and higher-rank effect polymorphic functions. They have thus anticipated a feature that gained broader interest only much later, e.g. , in the context of practical type-and-effect systems for algebraic effects with handlers ( Plotkin and Pretnar 2013 ; Leijen 2014 ; Wu et al. 2014 ; Bauer and Pretnar 2015 ; Hillerström and Lindley 2016 ; Brachthäuser et al. 2020 ; Biernacki et al. 2019 ; Biernacki et al. 2020 ; Xie et al. 2022 ; Madsen 2022 ; de Vilhena and Pottier 2023 ) . The combination of higher-rank polymorphism and type (and effect) reconstruction is well-known to be tricky on theoretical grounds. It requires a certain amount of type annotations to remain within the realm of decidability ( Odersky and Läufer 1996 ; Botlan and Rémy 2003 ; Peyton Jones et al. 2007 ; Dunfield and Krishnaswami 2013 ; Dunfield and Krishnaswami 2019 ; Emrich et al. 2020 ) . But even with that hurdle out of the way, designing an algorithm to work in this setting is faced with challenges involving the correct handling of the ubiquitous type-variable binders, which is notoriously error-prone. Theorems establishing properties of any such algorithm help assuage worries about its soundness and completeness relative to a declarative type system serving as the specification. However, a pen-and-paper proof may not be sufficient, because small variable-scoping problems are easy to miss when verified by humans. Mechanized proofs provide a greater degree of trust, but tools such as proof assistants took considerable time to reach sufficient maturity for widespread use within the programming languages community. Even the classic type reconstruction algorithm W was first formalized in 1999 ( Naraschewski and Nipkow 1999 ; Dubois and Ménissier-Morain 1999 ) , and required rather tedious management of variable binding. It is therefore no surprise that the proofs within ‘‘Algebraic Reconstruction of Types and Effects’’ had to be verified by hand at the time. We have identified subtle variable-related bugs due to which the algorithm rejects certain valid programs, and in some cases infers incorrect types. 1 1 1 The problems pertain to the higher-rank polymorphism and explicit polymorphism features present in the calculus. The validity of later results building on this algorithm remains unthreatened, because they omitted these mechanisms. In this note, we relate the original type system and the reconstruction algorithm, and describe our findings regarding the aforementioned issues. 2. The Type System In this section we briefly recall the syntax and the type system. As the original presentation uses LISP-like notation, we adapt it to a more modern convention. Moreover, we slightly change the way of representing variable binders to more hygienic, but still equivalent forms. We elaborate on this in Section 2.2 . 2.1. Syntax (type variables) \displaystyle\alpha,\beta,\gamma,\ldots (unification variables) \displaystyle\mathsf{?X},\mathsf{?Y},\mathsf{?Z},\ldots (identifiers) \displaystyle I \displaystyle\Coloneqq\alpha\mid\mathsf{?X} (term variables) \displaystyle x,y,z,f,\ldots (kinds) \displaystyle\kappa \displaystyle\Coloneqq\mathsf{E}\mid\mathsf{T} (effects) \displaystyle\varepsilon \displaystyle\Coloneqq\alpha\mid\mathsf{?X}\mid\iota\mid\varepsilon\cdot\varepsilon (types) \displaystyle\tau \displaystyle\Coloneqq\alpha\mid\mathsf{?X}\mid\tau\rightarrow_{\varepsilon}\tau\mid\forall\alpha^{\kappa}\ldotp\tau (descriptors) \displaystyle\mathsf{D} \displaystyle\Coloneqq\varepsilon\mid\tau (expressions) \displaystyle e \displaystyle\Coloneqq x\mid\lambda x:\tau\ldotp e\mid\lambda x\ldotp e\mid e\;e\mid\Lambda\alpha^{\kappa}\ldotp e\mid e\;[\mathsf{D}] Figure 1. The syntax. The syntax is presented in Figure 1 . We distinguish between type variables and unification variables, and introduce the syntactic category of identifiers, which are either of the two. Since identifiers can represent both types and effects, we have two kinds to distinguish between them: the kind of all types \mathsf{T} and the kind of all effects \mathsf{E} . Effects are built from type variables, unification variables, the pure effect \iota , and the join of two effects \varepsilon_{1}\cdot\varepsilon_{2} . Types consist of type variables, unification variables, effect-annotated arrow types \tau_{1}\rightarrow_{\varepsilon}\tau_{2} , and polymorphic types \forall\alpha^{\kappa}\ldotp\tau , which bind a type variable of a given kind in the type body. Descriptors are either effects or types. The syntax of expressions includes term variables x , lambda abstractions with type annotations \lambda x:\tau\ldotp e , and without type annotations \lambda x\ldotp e , function applications e_{1}\;e_{2} , type abstractions \Lambda\alpha^{\kappa}\ldotp e , and type applications e\;[\mathsf{D}] . Intuitively, the argument type of an unannotated lambda abstraction is to be inferred, but with the restriction that it must be monomorphic , i.e. , it cannot contain any polymorphic types. Formally, monomorphic types are defined by the following inductive relation. \frac{}{\textnormal{{mono}}(\alpha)}\quad\textsc{right=MT-Var}\par\frac{}{\textnormal{{mono}}(\mathsf{?X})}\quad\textsc{right=MT-UnifVar}\par\frac{\textnormal{{mono}}(\tau_{1})\textnormal{{mono}}(\tau_{2})}{\textnormal{{mono}}(\tau_{1}\rightarrow_{\varepsilon}\tau_{2})}\quad\textsc{right=MT-Arrow} 2.2. Differences from the Original Presentation The presented syntax slightly differs from the original, but in aspects that in our view improve readability and do not change the essence of the system. Here we briefly describe these differences. Variables. In the original presentation, binders in types were allowed to bind identifiers (type variables or unification variables) by the grammar. Since binders of unification variables can never occur in source programs or the output of the algorithm, we decided to disallow this in the grammar. The original presentation also reuses the syntactic category of identifiers for term variables. Since term variables are never mixed with type or unification variables, we also treat them as a separate syntactic category. The original grammar of identifiers allows for constants . Constants were used in two ways: as global variables defined outside of the program, and as fresh identifiers generated by the algorithm to represent unknown abstract types introduced by polymorphic quantifiers. In our presentation we use regular type and term variables for both purposes, thus avoiding the need for a separate syntactic category. Pure effect. In the original presentation, there was one distinguished constant representing the pure effect. Since we treat constants as regular type variables, we decided to represent the pure effect as a separate construct \iota in the syntax of effects. Monotypes. Originally, monomorphic types were defined by a separate syntactic category, which included identifiers and arrow types. Since we are biased towards formalizations in proof assistants, we would like to think of separate syntactic categories as

Read the complete text