Coeffects for sharing and mutation
Riccardo Bianchini, Francesco Dagnino, Paola Giannini, Elena Zucca, Marco Servetto
Abstract
In type-and-coeffect systems , contexts are enriched by coeffects modeling how they are actually used, typically through annotations on single variables. Coeffects are computed bottom-up, combining, for each term, the coeffects of its subterms, through a fixed set of algebraic operators. We show that this principled approach can be adopted to track sharing in the imperative paradigm, that is, links among variables possibly introduced by the execution. This provides a significant example of non-structural coeffects, which cannot be computed by-variable, since the way a given variable is used can affect the coeffects of other variables. To illustrate the effectiveness of the approach, we enhance the type system tracking sharing to model a sophisticated set of features related to uniqueness and immutability. Thanks to the coeffect-based approach, we can express such features in a simple way and prove related properties with standard techniques.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
3 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- A relational theory of effects and coeffects cites A graded dependent type system with a usage-aware semantics
- Resource-Aware Soundness for Big-Step Semantics cites A relational theory of effects and coeffects
- Resource-Aware Soundness for Big-Step Semantics cites A graded dependent type system with a usage-aware semantics
- Functional Ownership through Fractional Uniqueness cites Resource-Aware Soundness for Big-Step Semantics
- Functional Ownership through Fractional Uniqueness cites A graded dependent type system with a usage-aware semantics
- Modeling Reachability Types with Logical Relations: Semantic Type Soundness, Termination, Effect Safety, and Equational Theory cites Functional Ownership through Fractional Uniqueness
Cited by top-tier papers3
- Resource-Aware Soundness for Big-Step SemanticsRiccardo Bianchini, Francesco Dagnino, Paola Giannini, Elena ZuccaOOPSLA 2023 · 6 citations
- Functional Ownership through Fractional UniquenessDanielle Marshall, Dominic OrchardOOPSLA 2024 · 6 citations
- Modeling Reachability Types with Logical Relations: Semantic Type Soundness, Termination, Effect Safety, and Equational TheoryYuyan Bao, Songlin Jia, Guannan Wei, Oliver Bracevac et al.OOPSLA 2025 · 3 citations
Builds on2
Related papers
- Effects and Coeffects in Call-by-Push-ValueCassia Torczon, Emmanuel Suárez Acevedo, Shubh Agrawal, Joey Velez-Ginorio et al.OOPSLA 2024 · 5 citations
- Typing StrictnessDaniel Sainati, Joseph W. Cutler, Benjamin C. Pierce, Stephanie WeirichPOPL 2026
- Giving semantics to program-counter labels via secure effectsAndrew K. Hirsch, Ethan CecchettiPOPL 2021 · 2 citations
- A Lightweight Type-and-Effect System for Invalidation Safety: Tracking Permanent and Temporary Invalidation with Constraint-Based Subtype InferenceCunyuan Gao, Lionel ParreauxOOPSLA 2025 · 4 citations
- Reachability types: tracking aliasing and separation in higher-order functional programsYuyan Bao, Guannan Wei, Oliver Bracevac, Yuxuan Jiang et al.OOPSLA 2021 · 19 citations
