CS Paper Radar

A Quantitative Interpretation of Useful Call-by-Value

Pablo Barenbaum, Delia Kesner, Mariana Milicich

cs.LO ·submitted 2026-10-29 14:35 UTC · v2

Abstract

In this work, we present the first semantic interpretation of useful call-by-value evaluation through a non-idempotent intersection type system called U. One first contribution of this paper is a characterisation of termination of useful call-by-value evaluation via U-typability. That is, a term is typable in system U if and only if it terminates in the useful call-by-value strategy. As a second contribution, we show that system U provides a quantitative interpretation for useful call-by-value evaluation, offering exact step-count information for program evaluation. Even though the specification of the operational semantics of useful evaluation is highly complex, system U is notably simple. As far as we know, system U is one of the scarce quantitative type systems capturing exactly the substitution step-count for variables and abstractions in an open call-by-value strategy. Our third contribution is a termination-equivalence result between standard call-by-value, which may perform erasing reductions, and useful call-by-value, which is non-erasing. To establish this result, we introduce a non-erasing restriction of standard call-by-value, a refinement that serves as an intermediate calculus bridging standard and useful call-by-value. We show that all three calculi have the same termination behaviour, and hence induce the same observational equivalence.

Closest papers

Nearest neighbours by meaning across the whole index.

Context Types: Bunched Modalities for Unifying Safety and Reachability

cs.PL cs.LO ·2026-11-10 ·Zhe Zhou, Benjamin Delaware, Suresh Jagannathan
hot direction similarity 0.66
Abstract

Most type systems are designed to verify safety properties: the judgement $e : τ$ holds if $e$ may evaluate to any value contained in the denotation of $τ$, but nothing more. More recent type systems have considered the complementary class of reachability properties: in these systems, the typing judgment holds if $e$ must be able to evaluate to every value denoted by $τ$, and possibly more. This paper introduces a refinement type system for higher-order functional programs where types can capture both safety and reachability properties. Simultaneously supporting both is challenging because each imposes different constraints on how variable bindings in a typing context are interpreted. We address this challenge by treating typing contexts as a kind of resource that mediates which capabilities are available when typing a program. We formalize this notion by developing a resource algebra of contextual capabilities and a bunched modal context logic over this algebra. We then interpret our type system in this logic, establishing soundness with respect to a denotational semantics that unifies safety and reachability guarantees within a single typing judgement.

0.41

Cambria: Resource Abstraction for Parametrized Algebraic Effects and Handlers

cs.PL ·2026-08-28 ·Jack Liell-Cock, Sam Staton
theory similarity 0.65
Abstract

The algebraic effects and handlers paradigm separates the concerns of the interface and implementation of computational effects in programming languages. We present Cambria, a language that extends this framework to the parametrized setting. Effect signatures may use abstract parameter types that are instantiated by the handler along with the operation implementations. Parameters abstract over resources, such as memory locations or thread IDs, permitting algebraic effects to encode dynamic allocation. They are first-class in the type system but erased at runtime, requiring no coercions or type-directed reduction. We prove parametricity via a step-indexed logical relation, formalizing the abstraction guarantee provided by parametrized handlers. We also establish type safety and classify the annotations needed for completeness of the type inference algorithm. We demonstrate Cambria's practicality with a working implementation and provide examples including local state, Pólya's urn, and concurrent thread management. The last is a parametrized effect whose abstract thread IDs are shared between concurrent computations, going beyond standard instances. Cambria is the first calculus with user-defined resource-allocating effects that guarantees, via parametricity, that client code cannot depend on how a handler represents its resources.

0.10

Verified Implementation of the Next-gen Borrow Checking Algorithm for Rust via Abstract Interpretation

cs.PL ·2026-11-04 ·Jinhua Wu, Yuting Wang, Zhemin Chen
theory similarity 0.65
Abstract

Borrow checking is a central mechanism for Rust to ensure temporal memory safety. Its correctness is based on the intuition that the Aliasing XOR Mutability discipline guarantees that programs without borrow errors inherently could not access invalid references (i.e., pointers). However, existing work on formalizing borrow checking treats it either as a component of type systems or as symbolic execution describing resource transfer. None provides a direct explanation of the correctness of borrow checking algorithms such as Non-Lexical Lifetimes (NLL) or Polonius in the official Rust compiler that function more like static pointer analysis. We take a first step toward solving this problem by formalizing Polonius, the next-generation borrow- checking algorithm for the Rust compiler, on a core subset of Rust. We prove its correctness by showing that any program accepted by Polonius does not access invalid references at runtime. The key observation is that, when borrow checking is performed lazily, Polonius could be treated as a forward abstract interpretation on abstract domains recording pointer aliasing (borrowing) relations. By providing a concrete semantics that formally describes the Aliasing XOR Mutability discipline, we prove the soundness of this abstract interpretation, from which we derive memory safety of checked programs. This formulation of Polonius is implemented and formally verified in the abstract interpretation framework of CompCert. The correctness proofs are generated by an agentic AI under human guidance using paper proofs as proof outline. To the best of our knowledge, this is the first comprehensive formalization and verification of a borrow checking algorithm as manifested in the Rust compiler.

0.13

On Eliminating the Impossible with Dependent Types: Choreographic Libraries with Proof-Carrying Located Values

cs.PL ·2026-08-20 ·Simon Daniel, Timon Böhler, David Richter, Pascal Weisenburger, Mira Mezini
similarity 0.64
Abstract

With growing complexity, distributed software systems become increasingly challenging to maintain and reason about. When implementing a distributed protocol, developers must ensure manually that the different components fit together. Choreographic programming addresses this challenge by specifying global protocols in a single program and projecting them into communicating processes, so-called endpoints. Recent choreographic approaches are designed as programming libraries that embed this paradigm into a host language like Haskell or Rust. In these designs, we observe common cases of partiality: unreachable branches in endpoint projection (EPP) and located-value access can trigger runtime errors or undefined behavior, relying on manual discipline of library maintainers rather than being statically type-checked. Also, some programs require users to write down dummy branches that should not be reachable, for example when branching on sum types. To close this gap, we use the dependently typed Lean programming language to implement a similar choreographic library. We show how we are able to move from a partial EPP to a total EPP function, and also eliminate cases of partiality in user-written code with pattern matching on sum types. ChorLean ensures total EPP and safe value access via proof-carrying located values, passing Lean's totality checker without undefined cases, while supporting the same feature set as libraries like MultiChor.

0.25

Strict Capabilities with a PNVI Escape Hatch

cs.PL ·2026-11-16 ·Yihe Li, Sai Dhawal Phaye, Roland H. C. Yap, Trevor E. Carlson, Gregory J. Duck
position similarity 0.62
Abstract · 22 pages, 1 figure, 2 tables

Capability systems enforce memory safety by tying pointers to their originating allocations, preventing forgery, use-after-free, and out-of-bounds accesses. Yet conventional capabilities are simultaneously too strict and not strict enough for C: they reject common low-level idioms involving integer casts or raw pointer bytes, while failing to enforce type correctness and sub-object bounds. Proposed Provenance Not Via Integers (PNVI) semantics expose this tension by permitting representation-level manipulation while retaining strict rules for ordinary pointer operations. We argue that these requirements call for two interoperable abstractions rather than a compromise within one. Strict capabilities enforce provenance, liveness, type correctness, and (sub-)object bounds; ordinary capability operations preserve these invariants. Exposed representations are non-dereferenceable, integer-like values that support arbitrary integer and byte-level manipulation under PNVI semantics while retaining unforgeability guarantees. They carry no directly usable memory-access authority: converting an exposed representation back to a strict capability reconstructs provenance under PNVI rules and validates type and bounds before access. Thus, low-level C idioms can use an explicit escape hatch without weakening ordinary capability derivation. We realize this design using Fully Randomized Pointers (FRP) and dynamic type metadata. Evaluation on low-level pointer idioms, Juliet tests, and existing C benchmarks shows that strict type and sub-object safety can coexist with low-level pointer manipulation.

0.38

Polymorphic First-Class Environments

cs.PL ·2026-10-27 ·Jinhao Tan, Jam Kabeer Ali Khan, Bruno C. d. S. Oliveira
theory similarity 0.62
Abstract

First-class environments expose runtime environments as ordinary values and support a substitution-free, environment-based operational semantics. They also support applications such as first-class modules, dynamic composition of environment fragments, and sandboxing via local environments. Existing environment-based calculi, however, are mostly studied in a simply typed setting and stop short of System F and polymorphism. We present $F_E$, a polymorphic calculus with first-class environments that conservatively extends System F with a small-step environment semantics. $F_E$ eliminates all forms of substitution in System F. Term and type abstractions evaluate to closures, boxes run code under local environments, and box types expose the local typing assumptions of both. Manifest types, together with a two-sided type equivalence, play a dual role: they model type-level instantiation, and enable transparent type components in environments and modules. We prove type soundness, normalization, decidability, and standard properties of type equivalence, and conservativity over System F. The metatheory of $F_E$ is based on instantiation lemmas rather than substitution lemmas. This foundation supports polymorphic first-class modules with dynamic composition and sandboxing. We study $F_E$ in two forms. Our main presentation is an explicit, type-passing calculus that follows conventional System F. We also develop an implicitly-typed variant aligned with the semantics of polymorphic functional languages. All metatheory is mechanized in the Rocq theorem prover.

0.07

Preserving Separation Logic Specifications through Compilation

cs.PL ·2026-10-27 ·Carmine Abate, Kleio Liotati, František Farka, Sebastian Ertel
similarity 0.62
Abstract · 42 pages (25 pages main text, references, 13 pages of appendices), 6 figures, 1 table. Rocq mechanization available from the authors on requ…

Program specifications in separation logic describe ownership of resources and serve as logical interfaces for local reasoning. Compiler correctness, expressed as semantics preservation, does not by itself supply such an interface for compiled code, because it does not explicitly relate source and target resources and assertions. We investigate WP-preserving compilation: when a compiler translates a source program, the weakest preconditions that the program satisfies in a separation logic carry over to the compiled program. Our proof technique consists of a resource-aware simulation over interaction trees: it relates the resources required by corresponding source and target events, and tracks ownership through target operations, such as register accesses, that have no source counterpart. We apply the approach to a compiler from a structured imperative language to an assembly-like language, first for closed programs and then extended with modules and function calls. In the extended setting, each module can be verified in the source logic and compiled separately; its specifications carry over to the compiled module and are preserved when compiled modules are linked. All results are mechanized in Rocq.

0.24

Linking as Evaluation: Correct Separate Compilation via First-Class Environments

cs.PL ·2026-11-03 ·Jam Kabeer Ali Khan, Jinhao Tan, Bruno C. d. S. Oliveira
similarity 0.62
Abstract · 36 pages, including references and appendices

Separate compilation is central to modular software: components are compiled independently and linked into an executable. Separate compilation is correct when a linked program behaves like the program formed by merging its sources. This property is less routine to prove than type soundness because it requires a formal account of linking. We present $λ_{\mathsf{SCE}}$, a simply typed calculus in which linking, modules, and environments are all first-class. Programmers control module linking through a link operator, which a type-directed elaboration translates into ordinary terms of a core calculus of first-class environments. The core calculus's existing evaluation rules then perform the linking: linking as evaluation. Linking independently compiled modules yields the same core term as elaborating their source link. Therefore, compilation and linking commute by construction. As a result, separate compilation correctness follows directly from the semantics preservation for both static and dynamic linking. All meta-theory is mechanized in Lean 4, and we implement a compiler to WebAssembly in OCaml.

0.25