betaFeedback

WorksComputer Science

Graded Intersection Types

Abstract

We introduce graded intersection types, in which arrow domains are multisets of types with coefficients in a semiring. Boolean and natural number grades recover idempotent and non-idempotent intersection types. We give algebraic conditions on the semiring for subject reduction and expansion in finite systems and in locally finite systems with guarded infinite types. We construct a lifting to multisets of grades corresponding, in this general setting, to lifting the idempotent system to the non-idempotent one. We recall the main existing operational characterisations from the literature, and show some general extensions.

Intersection Types. Intersection types [11] were introduced as a refinement of simple types for the λ\lambda-calculus where arrow types σ→τ\sigma\to\tau are replaced with

{σ1,…,σn}→τ,\{\sigma_1,\ldots,\sigma_n\} \to\tau,

i.e. the domain of the arrow becomes a finite set of types (presented as an intersection σ1∩⋯∩σn\sigma_1 \cap\cdots\cap\sigma_n in the original formalism, hence the terminology). The key feature of intersection type systems is that they enjoy not only subject reduction, as any reasonable type system, but also subject expansion: if M→βNM \to_\beta N, any typing of NN can be turned backwards into a typing of MM. As a consequence, intersection types have given rise to neat semantic counterparts (in particular as filter models [1]) and, on the operational side, to characterisations of computational properties: while simple types only guarantee termination, intersection types allow to characterise, e.g., weak [11, 20] or head [22, 23] normalisation.

Non-idempotent intersection types [15, 19] renewed this approach by relaxing indempotence of intersection, i.e. σ∩σ=σ\sigma\cap\sigma= \sigma no longer holds; equivalently arrow types are presented with a finite multiset of types as a domain, as in

[σ1,…,σn]→τ.[\sigma_1,\ldots,\sigma_n] \to\tau.

This shift unveiled a strong connexion with various program analysis tools related to linear logic: in particular, non-idempotent typings are in close correspondence with the standard relational model of the λ\lambda-calculus [2, 8, 9], and with the multilinear approximation of λ\lambda-terms given by Taylor expansion [14, 25]. As a consequence, the characterisations of operational properties (that are made much simpler to prove in a non-idempotent setting, thanks to linearity) could be turned into resource-sensitive results providing quantitative information and exact bounds on, e.g., resource usage or execution time [9].

Graded Types. In the same years, another thread of the literature studied a different enrichment of the domain of arrow types allowing to control the usage of resources by functional programs. Grounded in linear logic again [16] and in its decomposition of the arrow σ→τ\sigma\to\tau into !σ⊸τ!\sigma\multimap\tau (where the exponential modality !! allows for erasure or duplication of its content while the linear arrow ⊸\multimap requires a single use of the argument), bounded linear logic [18] introduced annotated exponentials, as in

!aσ⊸τ,!^{a}\sigma\multimap\tau,

where aa is intuitively a quantity indicating how many times the argument of a program may be used. Graded types [6, 17] then simplified and generalised this idea by allowing the annotation aa to be taken in any semiring, providing control on various aspects of the input of programs; this gave rise to a rich literature on graded coeffects.

Contribution. The present work aims at reconciling these two threads along the lines of a simple observation: the domains of the arrow in idempotent and non-idempotent intersection types (i.e., sets and multisets of types) can be seen as maps from types to booleans and from types to natural numbers, respectively, i.e. as maps associating grades to types. We introduce graded intersection types, a generalisation of intersection types where arrow types can be written as

[σ1:a1,…,σn:an]⊸τ.[\sigma_1 : a_1, \ldots, \sigma_n : a_n] \multimap\tau.

The standard idempotent and non-idempotent settings are the instances where the grades aia_i are taken to be booleans or natural integers, respectively.

In Section 1 we first discuss some algebraic properties of the grading semiring S\mathrm{S}, and we introduce what we call S\mathrm{S}-multisets; then we define the graded intersection type system IS\mathrm{I}_{\mathrm{S}} and its relevant fragment. In Section 2 we establish that, under suitable algebraic conditions on S\mathrm{S}, the system enjoys subject reduction and subject expansion. In Section 3 we extend all the previous work to infinitary graded intersection types relaxing finite support of multisets of types (we consider locally finite support instead) as well as inductive type formation (we consider guarded coinductive formation instead), giving rise to locally finite graded intersection types; their instance with grades taken in the tropical semiring has been thoroughly studied in another work [10]. In Section 4 we introduce the graded counterpart to switching from idempotent to non-idempotent intersection types: we replace single grades with multisets of grades. This can actually be done within the formalism, since these multisets themselves form a semiring with all desired properties. This lifting offers all the usual benefits of non-idempotency and linearity (which is mostly left for future work in the current version of this note). Finally in Section 5 we provide or recall some operational characterisations allowed by graded intersection types. In particular, as expected, unrestricted finite typing in IS\mathrm{I}_{\mathrm{S}} characterises head normalisation.

Related Work. Previous investigations already provided a partial semantic counterpart to this work. In particular Carraro, Ehrhard, and Salibra [12] showed that the graded exponential comonad associated to a resource semiring gives rise to a relational model of the λ\lambda-calculus (the standard relational model being built for the semiring of natural integers). Breuvart and Pagani [BP15] showed how the models generated this way allow to interpret graded types, and Breuvart, Kerjean, and Mirwässer [3] extended this approach to graded types for the differential λ\lambda-calculus. Although it is not explored yet, there should be a direct connection between these semantics and the syntax we introduce in this paper. Extending these semantic approaches to weak resource semirings, e.g. finding a relational model for boolean or tropical grades, is the subject of ongoing work. Extending our syntax with differentiation, or designing a graded Taylor approximation, is another promising perspective.

The infinitary intersection types that we introduce are reminiscent of the ones by Vial [Vial17; Via21], and actually gives rise to a characterisation of the same property of hereditary head normalisation [10]. As opposed to the rather involved external machinery in Vial’s work, our guarded coinductive definition already provides all needed ingredients for the proof.

It is outside the scope of this note to recall the wide literature on graded type systems controlling the coefficients of functional programs in order to ensure good behaviours, or to bound quantitative measures of these behaviours. Let us only mention that one long-term goal of the present work is to build on this literature so as to provide characterisations or exact bounds by putting into work the good properties of intersection types.

Finite Graded Intersection Type Systems

Algebraic Preliminaries

Definition 1 (Semiring). A semiring is a tuple (S,+,0,×,1)(\mathrm{S}, +, 0, \times, 1), where (S,+,0)(\mathrm{S}, +, 0) is a commutative monoid, (S,×,1)(\mathrm{S}, \times, 1) is a monoid, multiplication distributes over addition on both sides, and 00 is

absorbing for multiplication. Throughout this note we also assume that 0≠10 \ne1. We define the algebraic preorder ≤\le on SS by writing a≤ba \le b whenever ∃c\exists c, b=a+cb = a + c.

Standard examples include the natural, boolean and tropical semirings, respectively defined by:

N:=(N,+,0,×,1),2:=({0,1},∨,0,∧,1),T:=(N∪{∞},min⁡,∞,+,0).\mathbb{N} := (\mathbb{N}, +, 0, \times, 1), \qquad\mathbf{2} := (\{0,1\}, \lor, 0, \land, 1), \qquad\mathbf{T} := (\mathbb{N} \cup\{\infty\}, \min, \infty, +, 0).

where N\mathbb{N} denotes the set of natural integers.

For a semiring to give rise to a well-behaved intersection type system enjoying, in particular, subject reduction (see § 2), we need to enforce some algebraic conditions.

Definition 2 (Resource Semiring). Given a semiring (S,+,0,×,1)(S, +, 0, \times, 1), consider the conditions:

Positivitya+b=0⟹a=b=0,No Zero Divisorsa×b=0⟹a=0 or b=0,Discretenessa+b=1⟹a=0 or b=0,Weak Discretenessa+b=1⟹a≥1 or b≥1,Additive Refinementa1+a2=b1+b2⟹∃c11,c12,c21,c22∈S,∀i∈{1,2}, ai=ci1+ci2,∀j∈{1,2}, bj=c1j+c2j,Mixed Refinementa×b=c1+c2⟹∃L finite, ∃(al)l∈L, ∃(bil)i∈{1,2},l∈L,a=∑l∈Lal,∀l∈L, b=b1l+b2l,∀i∈{1,2}, ci=∑l∈Lal×bil.\begin{aligned} \textit{Positivity}\quad&a + b = 0 \quad\Longrightarrow\quad a = b = 0,\\ \textit{No Zero Divisors}\quad&a \times b = 0 \quad\Longrightarrow\quad a = 0 \text{ or } b = 0,\\ \textit{Discreteness}\quad&a + b = 1 \quad\Longrightarrow\quad a = 0 \text{ or } b = 0,\\ \textit{Weak Discreteness}\quad&a + b = 1 \quad\Longrightarrow\quad a \ge1 \text{ or } b \ge1,\\ \textit{Additive Refinement}\quad&a_1 + a_2 = b_1 + b_2 \quad\Longrightarrow\quad\exists c_{11},c_{12},c_{21},c_{22} \in S,\\ &\qquad\forall i \in\{1,2\},\ a_i = c_{i1} + c_{i2},\qquad\forall j \in\{1,2\},\ b_j = c_{1j} + c_{2j},\\ \textit{Mixed Refinement}\quad&a \times b = c_1 + c_2 \quad\Longrightarrow\quad\exists L\ \text{finite},\ \exists(a_l)_{l\in L},\ \exists(b_{il})_{i\in\{1,2\},l\in L},\\ &\qquad a = \sum_{l\in L} a_l,\qquad\forall l \in L,\ b = b_{1l} + b_{2l},\qquad\forall i \in\{1,2\},\ c_i = \sum_{l\in L} a_l \times b_{il}. \end{aligned}

Then SS is said to be a (weak) resource semiring whenever it is positive, has no zero divisors, is (weakly) discrete, additive refining and mixed refining. When contrasting the two notions, we also say strong resource semiring for a resource semiring.

The conditions for a resource semiring are already well-known in the literature: they ensure that the SS-semimodule monad distributes over the powerset monad [13, 7], and they play a crucial role in the construction of an exponential comonad when designing graded versions of the relational and coherent models of linear logic [12 BP15, 21].

We depart from the terminology coined by Carraro, Ehrhard, and Salibra [12] where resource semirings, additive refinement and mixed refinement were called “multiplicity semirings”, “additive splitting” and “multiplicative splitting”, respectively. The first change aims at avoiding ambiguities with existing notions, and is borrowed from Breuvart, Kerjean, and Mirwasser [3]; the latter two bring back the original and standard algebraic terminology [24].

The weak discreteness condition, as far as we know, is new; investigating how it can enter the semantic picture is ongoing work.

Lemma 3 (nn-ary Properties). Let SS be a semiring that is positive and has no zero divisors. The following properties hold, with all the considered index sets being finite. Then:

  1. If SS has discreteness, then it has nn-ary discreteness: if ∑i∈Iai=1\sum_{i\in I} a_i = 1, then exactly one aia_i is non-zero (and is equal to 11).

    If SS has weak discreteness and additive refinement, then it has nn-ary weak discreteness: if ∑i∈Iai≥1\sum_{i\in I} a_i \ge1, then ∃i, ai≥1\exists i,\ a_i \ge1.

  1. If SS has additive refinement, then it has nn-ary additive refinement:

∑i∈Iai=∑j∈Jbj⟹∃(cij)i∈I,j∈J, ∀i∈I, ai=∑j∈Jcij,  ∀j∈J, bj=∑i∈Icij.\sum_{i\in I} a_i = \sum_{j\in J} b_j \quad\Longrightarrow\quad\exists(c_{ij})_{i\in I,j\in J},\ \forall i \in I,\ a_i = \sum_{j\in J} c_{ij},\ \ \forall j \in J,\ b_j = \sum_{i\in I} c_{ij}.
  1. If SS has additive and mixed refinement, then it has nn-ary mixed refinement:

a×b=∑i∈Ici⟹∃L, ∃(al)l∈L, ∃(bil)i∈I,l∈L,a \times b = \sum_{i\in I} c_i \Longrightarrow\exists L,\ \exists(a_l)_{l\in L},\ \exists(b_{il})_{i\in I,l\in L},
a=∑l∈Lal,∀l∈L, b=∑i∈Ibil,∀i∈I, ci=∑l∈Lal×bil.a = \sum_{l\in L} a_l,\qquad\forall l\in L,\ b = \sum_{i\in I} b_{il},\qquad\forall i\in I,\ c_i = \sum_{l\in L} a_l \times b_{il}.

as well as simultaneous nn-ary mixed refinement:

∀x∈X, a×bx=∑i∈Ixcxi⟹∃L, ∃(al)l∈L, ∃(bxil)x∈X,i∈Ix,l∈L,\forall x\in X,\ a\times b_x = \sum_{i\in I_x} c_{xi} \Longrightarrow\exists L,\ \exists(a_l)_{l\in L},\ \exists(b_{xil})_{x\in X,i\in I_x,l\in L},

References

  1. [1][BCD83] Henk Barendregt, Mario Coppo, and Mariangiola Dezani-Ciancaglini. “A filter lambda model and the completeness of type assignment”. In: Journal of Symbolic Logic 48.4 (1983), pp. 931–940. DOI: 10.2307/2273659.DOI
  2. [2][BEM07] Antonio Bucciarelli, Thomas Ehrhard, and Giulio Manzonetto. “Not Enough Points Is Enough”. In: Computer Science Logic (CSL 2007). 2007, pp. 298–312. DOI: 10.1007/978-3-540-74915-8_24.DOI
  3. [3]Flavien Breuvart, Marie Kerjean, and Simon Mirwasser. “Unifying Graded Linear Logic and Differential Operators”. In: Logical Methods in Computer Science 22 (1 2026). DOI: 10.46298/lmcs-22(1:7)2026.DOI
  4. [4]Antonio Bucciarelli, Delia Kesner, and Daniel Ventura. “Non-idempotent intersection types for the Lambda-Calculus”. In: Logic Journal of the IGPL 25.4 (July 2017), pp. 431–464. DOI: 10.1093/jigpal/jzx018.DOI
  5. [6]Aloïs Brunel et al. “A Core Quantitative Coeffect Calculus”. In: Programming Languages and Systems (ESOP 2014). 2014, pp. 351–370. DOI: 10.1007/978-3-642-54833-8_19.DOI
  6. [7]Filippo Bonchi and Alessio Santamaria. “Convexity via Weak Distributive Laws”. In: Logical Methods in Computer Science 18 (4 2022). DOI: 10.46298/lmcs-18(4:8)2022.DOI
  7. [8]Daniel de Carvalho. “Sémantiques de la logique linéaire et temps de calcul”. PhD thesis. Université Aix-Marseille II, 2007. URL: http://theses.univ-amu.fr.lama.univ-amu.fr/2007AIX22066.pdf.
  8. [9]Daniel de Carvalho. “Execution time of λ-terms via denotational semantics and intersection types”. In: Mathematical Structures in Computer Science 28.7 (2017), pp. 1169–1203. DOI: 10.1017/s0960129516000396.DOI
  9. [10]Rémy Cerda and Ugo Dal Lago. Staying Productive Under the Palm Trees. On Graded Coeffect Typing in the Tropical Semiring. 2026. arXiv: 2608.02596.arxiv.org/abs/2608.02596
  10. [11]Mario Coppo and Mariangiola Dezani-Ciancaglini. “A new type assignment for λ-terms”. In: Archiv für Mathematische Logik und Grundlagenforschung 19.1 (1978), pp. 139–156. DOI: 10.1007/bf02011875.
  11. [12]Alberto Carraro, Thomas Ehrhard, and Antonino Salibra. “Exponentials with Infinite Multiplicities”. In: Computer Science Logic (CSL 2010). 2010, pp. 170–184. DOI: 10.1007/978-3-642-15205-4_16.DOI
  12. [13]Maria Manuel Clementino, Dirk Hofmann, and George Janelidze. “The monads of classical algebra are seldom weakly cartesian”. In: Journal of Homotopy and Related Structures 9.1 (2013), pp. 175–197. DOI: 10.1007/s40062-013-0063-2.DOI
  13. [14]Thomas Ehrhard and Laurent Regnier. “Uniformity and the Taylor expansion of ordinary lambda-terms”. In: Theoretical Computer Science 403.2 (2008), pp. 347–372. DOI: 10.1016/j.tcs.2008.06.001.DOI
  14. [15]Philippa Gardner. “Discovering Needed Reductions Using Type Theory”. In: Theoretical Aspects of Computer Software, International Conference TACS ’94, Sendai, Japan, April 19-22, 1994, Proceedings. Ed. by Masami Hagiya and John C. Mitchell. Vol. 789. Lecture Notes in Computer Science. Springer, 1994, pp. 555–574. DOI: 10.1007/3-540-57887-0\_115.DOI
  15. [16]Jean-Yves Girard. “Linear Logic”. In: Theoretical Computer Science 50 (1987), pp. 1–102. DOI: 10.1016/0304-3975(87)90045-4.DOI
  16. [17]Dan R. Ghica and Alex I. Smith. “Bounded Linear Types in a Resource Semiring”. In: Programming Languages and Systems (ESOP 2014). 2014, pp. 331–350. DOI: 10.1007/978-3-642-54833-8_18.DOI
  17. [18]Jean-Yves Girard, Andre Scedrov, and Philip J. Scott. “Bounded linear logic: a modular approach to polynomial-time computability”. In: Theoretical Computer Science 97.1 (1992), pp. 1–66. DOI: 10.1016/0304-3975(92)90386-t.DOI
  18. [19]Assaf J. Kfoury. “A linearization of the Lambda-calculus and consequences”. In: Journal of Logic and Computation 10.3 (2000), pp. 411–436. DOI: 10.1093/logcom/10.3.411.DOI
  19. [20]Jean-Louis Krivine. Lambda-calcul, types et modèles. English translation available at https://www.irif.fr/~krivine/articles/Lambda.pdf. Masson, 1990.
  20. [21]Vincent Moreau and Lê Thành Dũng Nguyễn. Semi-quantitative semantics. Abstract presented at the 10th International Workshop on Trends in Linear Logic and Applications (TLLA 2026). 2026. URL: https://lipn.fr/TLLA/2026/abstracts/tllapaper19.pdf.
  21. [22]Patrick Sallé. “Une généralisation de la théorie des types en λ-calcul (I)”. In: RAIRO. Informatique théorique 14.2 (1980), pp. 143–167. DOI: 10.1051/ita/1980140201431.DOI
  22. [23]Patrick Sallé. “Une généralisation de la théorie des types en λ-calcul (II)”. In: RAIRO. Informatique théorique 14.3 (1980), pp. 301–314. DOI: 10.1051/ita/198014030301.DOI
  23. [24]Alfred Tarski. Cardinal Algebras. New York University Press, 1949. URL: https://archive.org/details/in.ernet.dli.2015.84237.
  24. [25]Takeshi Tsukada and C.-H. Luke Ong. “Plays as Resource Terms via Non-Idempotent Intersection Types”. In: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’16). 2016, pp. 237–246. DOI: 10.1145/2933575.2934553.DOI
  25. [26]Pierre Vial. “Infinitary intersection types as sequences: A new answer to Klop’s problem”. In: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2017). 2017. DOI: 10.1109/lics.2017.8005103.DOI
  26. [27]Pierre Vial. Sequence Types and Infinitary Semantics. 2021. arXiv: 2102.07515.arxiv.org/abs/2102.07515

Paper details

vlnc:W_p9gkwgr6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents