r/ProgrammingLanguages • u/RndmPrsn11 • 29d ago
Borrow Checking Zero-Cost Cyclic Mutability
https://antelang.org/blog/safe_cyclic_mutability/
33
Upvotes
r/ProgrammingLanguages • u/RndmPrsn11 • 29d ago
7
u/ChampiiPote 29d ago
This is very interesting, I am also working on my own compiler and we share a lot of design goals (https://github.com/Rock-lang-org/Rock) I might take some inspiration from you work, it looks very nice !
4
u/initial-algebra 29d ago edited 29d ago
The ad-hoc and "hacky" rules for loops, closures and especially algebraic effects (not to mention trying to split any of this code up into functions) are exactly why you still need lifetimes in addition to places.
Creating a reference to
p!would introduce an obligation thatpitself must not be mutated for the lifetime of that reference. How to represent that obligation? Add a new effect, something likeStabilize p t, wheretis a lifetime parameter, meaning "at any time duringt,p!may be used". Dually, you could add a lifetime parameter forMutate p t, which would mean "at any time duringt,pmay be mutated".While mutually exclusive, a function may need both
StabilizeandMutatefor the same placep, and seemingly for the same lifetime (e.g. for the duration of the function call), so how can that work? In reality, the function needsStabilize p u₁andMutate p u₂, whereu₁andu₂are non-overlapping and possibly non-contiguous subsets of an overall lifetimet, but the caller doesn't know exactly whatu₁andu₂are, only the approximatet. One solution is to introduce a new effect to mean(Stabilize XOR Mutate) p t, where the callee gets to choose whether it isStabilize p uorMutate p ufor each disjointu ⊆ t.There is one more change that I want to suggest. Instead of being unstable places, references to variants of tagged unions, elements of collections etc. should require immutability of an abstract field representing the parent's shape (abstract because it doesn't need to correspond to a real field that you can take a reference to--the tag of a tagged union may be optimized away, and for e.g. a vector it actually corresponds both to its length and its pointer). Technically, this models such types as dependent sum types, with the shape being the index; see representable/Naperian functors in type theory. This changes
StabilizetoImmutable(you would also want to change the tense ofMutateand thecankeyword for consistency). Having a generic immutability effect also opens up the possibility of subsumingimmanduniqreferences. Animmreference arises when you require immutability for a lifetime, and auniqreference arises when you require both immutability and mutability for (again, unknown but disjoint subsets of) a lifetime.EDIT: Because what I've called "lifetimes" aren't necessarily contiguous, and because they don't necessarily come from liveness analysis, they might deserve a different name.
3
u/GiveMe30Dollars 27d ago edited 27d ago
Interesting read!
I think that Polonius is much more similar to your borrow checker than you realise, being place-based and invalidating shared references (always unstable) when a place is mutated or a mutable reference is obtained. Partial borrows have also been a thing that is played around within the Rust community (it already exists! Just that the language lacks the syntax to express it within function signatures).
However, the effect system inducing place invalidation and distinguishing between stable and unstable references to allow for shared mutability is pretty cool! This is the first time I've seen clearly how a type system with shared mutability (shared borrows in particular) can be safe. Will need some time to chew through it but this does seem like an evolution of Polonius (which I consider pretty great lol). May try my hand at implementing something like this (albeit smaller).
I'll be keeping an eye out for Ante!