← All papers
First page of Escape with Your Self: Sound and Expressive Bidirectional Typing with Avoidance for Reachability Types

Escape with Your Self: Sound and Expressive Bidirectional Typing with Avoidance for Reachability Types

Songlin Jia, Guannan Wei, Siyuan He, Yuyan Bao, Tiark Rompf

cs.PL Apr 12, 2024 · v6
The declarative reachability type system, its soundness proofs, and the bidirectional typing algorithm with its soundness and termination proofs are mechanized in Lean 4.
Reasoning about programs in the presence of mutation and aliasing is notoriously difficult. Rust has popularized lifetime-based ownership tracking in systems programming, but its "shared XOR mutable" model is fundamentally at odds with higher-level functional programming. Reachability types offer an alternative: they enable safe sharing and escape of mutable data by tracking which resources each expression's result can reach. To track internal reachability within complex object graphs, reachability types adopt self-references that let components refer to enclosing resources from inside, just like `this` pointers in OO languages. While natural for declaratively typing escaping data, self-references complicate subtyping and furthermore type inference: variance restricts where self-references may appear, yet useful type conversions must allow them to vary in controlled ways, which in turn imposes constraints on inference. As an undesirable result, prior works require programmers to insert term-level coercions for even just avoidance – avoiding ill-scoped names in types. With all prior works being declarative, we investigate algorithmic reachability types in this work. We introduce a refined subtyping relation that permits more flexible usages of self-references. We further develop a sound and decidable bidirectional typing algorithm, implemented and verified in Lean. The algorithm automatically avoids ill-scoped names in types, and infers qualifiers via a lightweight unification mechanism. As a step towards practical reachability programming, we show that the system is capable of tracking diverse reachability patterns without explicit coercions in complex Church-encoded datatypes.

Reachability types track which resources an expression can reach and use self-references to describe internal reachability, but self-references complicate subtyping and inference. Prior systems are purely declarative and need programmer-inserted term-level coercions even for avoidance, i.e. keeping ill-scoped names out of types.

The authors define G<:, a refined declarative reachability type system that combines type and qualifier subtyping so self-references can vary in controlled ways. They then develop G⇔, a bidirectional typing algorithm that infers types and qualifiers using a lightweight unification over qualifier holes. G⇔ also applies avoidance conversions automatically. Both systems and their metatheory are mechanized in Lean 4, with soundness proved via a logical relation model.

The algorithm is proven sound with respect to G<: and terminating, though incomplete. It tracks diverse reachability patterns in Church-encoded and natively supported data structures such as pairs and lists without explicit coercions. The artifact is released on Zenodo and GitHub.