Lune

OOPSLA2022Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. Resource-Aware Soundness for Big-Step SemanticsRiccardo Bianchini, Francesco Dagnino, Paola Giannini, Elena ZuccaOOPSLA 2023 · 6 citations
  2. Functional Ownership through Fractional UniquenessDanielle Marshall, Dominic OrchardOOPSLA 2024 · 6 citations
  3. 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

  1. A graded dependent type system with a usage-aware semanticsPritam Choudhury, Harley Eades III, Richard A. Eisenberg, Stephanie WeirichPOPL 2021 · 33 citations
  2. A relational theory of effects and coeffectsUgo Dal Lago, Francesco GavazzoPOPL 2022 · 22 citations

Related papers

  1. Effects and Coeffects in Call-by-Push-ValueCassia Torczon, Emmanuel Suárez Acevedo, Shubh Agrawal, Joey Velez-Ginorio et al.OOPSLA 2024 · 5 citations
  2. Typing StrictnessDaniel Sainati, Joseph W. Cutler, Benjamin C. Pierce, Stephanie WeirichPOPL 2026
  3. Giving semantics to program-counter labels via secure effectsAndrew K. Hirsch, Ethan CecchettiPOPL 2021 · 2 citations
  4. 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
  5. Reachability types: tracking aliasing and separation in higher-order functional programsYuyan Bao, Guannan Wei, Oliver Bracevac, Yuxuan Jiang et al.OOPSLA 2021 · 19 citations
Dusk over the sea between two cliffs drawn in fine vertical lines