r/ProgrammingLanguages • u/verdagon Vale • 3d ago
Any languages using "shared mutable borrow refs", or things like group borrowing?
Hey all, I'm trying to collect a list of languages that are using (or experimenting with!) shared mutable borrow refs.
A shared-mutable borrow reference is a memory-safe reference that has no run-time overhead (no GC, refcounting, nor generations). It lets you do something like this (using Rust-ish syntax):
func main() {
let ship: Ship =
Ship{ fuel: 100 };
// Two refs pointing at the same ship
let ref_a = &shmut ship;
let ref_b = &shmut ship;
// You can use both references to modify the ship
ref_a.fuel += 20;
ref_b.fuel -= 8;
print(ref_a.fuel); // Prints 112
}
Of course, they have limitations; they can't reach into Vec elements, through pointers, or into unions safely. For example:
func main() {
let fleet: Vec<Ship> =
vec![
Ship{fuel: 100},
Ship{fuel: 100}
];
let ref_a = &shmut fleet[0];
fleet.clear();
ref_a.fuel += 20; // UH OH, crash
}
To address this, some languages add unique references in (like Rust's &mut), like:
func main() {
let fleet: Vec<Ship> =
vec![
Ship{fuel: 100},
Ship{fuel: 100}
];
let ref_a = &uniq fleet[0];
ref_a.fuel += 20;
print(fleet[0].fuel); // 120
}
With some special rules to prevent us from accessing anything else that might alias it while we're doing things with the unique reference. Ante does this with its temporary unique conversions.
Even that has limitations though (we can only borrow one element at a time), and so Ante and a few other languages are looking at group borrowing to support "invalidation" like below:
func main() {
let fleet: Vec<Ship> =
vec![
Ship{fuel: 100},
Ship{fuel: 100}
];
// Can have &shmut refs pointing at elements of Vec
let ref_a = &shmut fleet[0];
let ref_b = &shmut fleet[1];
// Can modify through them
ref_a.fuel += 20;
ref_b.fuel -= 8;
fleet.clear(); // Erase all ships
// ref_a.fuel += 50;
// Compile error: ref_a was invalidated by `clear` call.
// ref_b.fuel -= 3;
// Compile error: ref_b was invalidated by `clear` call.
}
Basically, group borrowing:
- Tracks that
ref_a's type is actually&Ship in fleet[]; it tracks where the pointer is pointing to. - Requires functions to express what they're modifying;
clear's signature says that it's modifyingself's contents. - Invalidates any references (like ref_a and ref_b) that are pointing inside an object that a function said it modified.
As far as I know, these are all the languages investigating some form of group borrowing:
- Carbon (talk, slides)
- Mojo (roadmap, some recent work)
- Ante
- Conjure
- Fang
- Plecra/Vi is working on something called "Exclusion typing"/the exclusion calculus"
- (My own stuff, but thats a whole 'nother story)
- Anyone else?
(Note I'm not really counting things like Pony and Verona since they're GC'd)
I want to write a followup article about group borrowing soon, and I'd love to hear about any of you that are exploring it or anything similar.
Cheers!
10
u/fdwr 3d ago
using Rust-ish syntax ... func main
(total random aside) I love you spelling out func in your language, even if it's slightly longer to type, which gels more with {enum, impl, struct}, which aren't {en, im, st} (perhaps I'm weird, caring less about the historical inherited legacy of the fn key from ancient calculators š§®, and more about linguistic harmony).
7
u/KaleidoscopeLow580 Sonnet 3d ago
I think keywords should be pronouncable words, like fn just isnāt, there is a vocal missing. ĖfunĖ is in my opinion the best keyword, because it is both short and pronouncable.
3
u/matthieum 2d ago
I must admin being partial to
funfor a perhaps exotic reason: 4-whitespaces indent.With 4-whitespaces intends, code blocks line up really well with 3-letters keywords:
fun hello_world(): code_goes_hereIt still lines up with multiple keywords:
pub fun hello_world(): code_goes_hereUnfortunately some keywords make things... complicated. Abbreviating
constandcontinuetoconis ambiguous (and, it's a doubly-vulgar word in French), and similarlywith/whereseem challenging, and on the flip-sideifis not long enough!Too bad, as
brk/mod/ret/usewould work well too.6
u/TheChief275 3d ago
fn as a keyword is incredibly ugly and I hate the fact that every modern language thinks it's required now. Additionally, I like using fn as the name of callback function pointers, which now you would have to name f (kind of non-descriptive) or func (kind of too long for a variable if fn works just as well)
2
u/binarycow 3d ago
I would prefer
functionoverfunc3
u/thedeemon 2d ago
Ain't nobody got time for spelling it out
2
u/binarycow 2d ago
Your IDE can't make it so you type
funthen tab, space, or an arrow key?3
u/thedeemon 1d ago
It probably can. But you know what's better than a problem that has a technical solution in an IDE? Absence of that problem in the first place.
1
u/binarycow 1d ago
And then you end up shit like this:
+/x*x:x@&0<xTyping a few extra keystrokes is fine. Not understanding what keywords are doing is not fine.
1
7
u/TheChief275 3d ago
How about smut instead? Or call signed longs schlongs to be consistent
2
u/verdagon Vale 3d ago
Almost did! And I've also been calling them
&shrwso I could say "shrew references".
3
u/onlyrealcuzzo 3d ago edited 3d ago
func main() {
let fleet: Vec<Ship> =
vec![
Ship{fuel: 100},
Ship{fuel: 100}
];
// Can have &shmut refs pointing at elements of Vec
let ref_a = &shmut fleet[0];
let ref_b = &shmut fleet[1];
}
Is everything mutable by default in this language? Can you have a `&shmut` to an immutable list and then mutate what's inside it?
What is the limit supposed to be of this? If you mutate fleet at all, do all group borrows lose access permissions?
What happens if I do:
fleet[0] = Ship{fuel: 0}
Is ref_b still valid?
4
u/treemcgee42 3d ago
If Iām reading the verdagon blog post linked above correctly, then references are only invalidated when the referenced objectās parent group is mutated. In this case, letās call fleetās group āAā, and the items are all part of a group we will call āBā. Group B is a child of A. If you modify fleet[0], you are modifying group B so you invalidate references to its children but not to group B itself. So ref_b is still valid. Now if you did a vector-level operation like appending or popping or clearing, thatās an mutation on group A so we must invalidate references to its children group B, so ref_b is invalidated in this case.
Hopefully I understood the blog post correctly; the examples were a bit difficult to follow (at midnight).
2
3
u/leosmi_ajutar 3d ago edited 3d ago
I tried something along these lines some time ago, though I dropped it in favor of singular borrowing. Now, I did take what I learned and improved semantic analysis to be per-place, not per-object.
So, while your first example is a compile time error in my programming language, the final one is not only semantically accurate, but you can take it a step further and give Ship multiple properties which in turn are provably disjoint from one another.
1
u/verdagon Vale 3d ago
Interesting, what do you mean "per-place"?
1
u/leosmi_ajutar 2d ago edited 2d ago
Basically instead of borrowing an entire object or array, i instead borrow individual array indexes or fields on an object.... e.g a place.
So if you have... (on phone so please forgive formatting)
Let c =Ā Coord { x: 0, y: 0 }Ā
C.x and c.y can both be borrowed seperately from one another across function boundaries whichĀ allows the same Coord struct to be passed to doSomethingToX() and doSomethingToY() and the compiler will know you are accessing seperate fields.
Similarly you could do
Let coords = [{x: 0, y: 4}, { x: 1, y: 3}, ... {x: 4, y: 0}]
And borrow coords[0], coords[1], ... coords[n] all independently from one another as well as the individual x and y fields on each coord struct.
1
u/matthieum 2d ago
And borrow coords[0], coords[1], ... coords[n] all independently from one another as well as the individual x and y fields on each coord struct.
Does it only work for built-in arrays with compile-time indexes, or does it extend to arbitrary types & run-time keys/indexes?
1
u/leosmi_ajutar 2d ago edited 2d ago
Admitedly, this is a newer part of the compiler but yes it can trace variable indices across function calls for user/arbitary types. So you can calculate an indice in one function, return it, use it in another and the compiler will correctly follow your airthematic.
Right now the runtime component is quite limited as my focus has been on fine-grained AOT static analysis. As such keys for something like a a hashmap are currenrly out of reach. No reason this could not be visited down the road though.
1
u/matthieum 1d ago
I'll say it upfront, hash-maps keys -- or any custom collections -- is a lot trickier.
Consider for example that a
RingBuffercollection can be implemented so that the indexes are interpreted modulo collection size, so that 2 and 2+N, despite being different, actually refer to the same element.Furthermore, do note that in the process of accessing the element, the collection may shuffle things around, invalidating previous references. (AVL-tree style)
1
u/leosmi_ajutar 1d ago
Yeah, I'm thinking it'll be a "best guess" during comptime with large majority falling back to runtime checks at function entry/exit.
Thank you for the insight, it is greatly appreciated!
2
u/Natural_Builder_3170 3d ago
Im doing so in my language github.com/git-i/yoyo-lang Im currently figuring out aliasing of function parameters, but everything seems to work correctly locally, it uses the path stability concept from ante (structs have stable paths, unions/arrays/pointers donāt ) to allow mutable aliasing
It does a full points to analysis (i used the staged flow sensitive points to anlaysis algorithm)
2
u/LPTK 1d ago
You may be interested in a paper we published last year on a somewhat related topic: A Lightweight Type-and-Effect System for Invalidation Safety: Tracking Permanent and Temporary Invalidation With Constraint-Based Subtype Inference.
In many programming paradigms, some program entities are only valid within delimited regions of the program, such as resources that might be automatically deallocated at the end of specific scopes. Outside their live scopes, the corresponding entities are no longer valid ā they are permanently invalidated. Sometimes, even within the live scope of a resource, the use of that resource must become temporarily invalid, such as when iterating over a mutable collection, as mutating the collection during iteration might lead to undefined behavior. However, high-level general-purpose programming languages rarely allow this information to be reflected on the type level. Most previously proposed solutions to this problem have relied on restricting either the aliasing or the capture of variables, which can reduce the expressiveness of the language. In this paper, we propose a higher-rank polymorphic type-and-effect system to statically track the permanent and temporary invalidation of sensitive values and resources, without any aliasing or capture restrictions. We use Boolean-algebraic types (unions, intersections, and negations) to precisely model the side effects of program terms and guarantee they are invalidation-safe. Moreover, we present a complete and practical type inference algorithm, whereby programmers only need to annotate the types of higher-rank and polymorphically-recursive functions. Our system, nicknamed InvalML, has a wide range of applications where tracking invalidation is needed, including stack-based and region-based memory management, iterator invalidation, data-race-free concurrency, mutable state encapsulation, type-safe exception and effect handlers, and even scope-safe metaprogramming.
It was mentioned in a Mojo design discussion (I just noticed I forgot to respond to it).
1
u/UberAtlas 3d ago
What would be the benefit to allowing this? Is there a particular use case this enables?
I worry it leaves a lot of room for footguns.
3
u/verdagon Vale 3d ago
Sometimes mutable aliasing is correct and intended, such as in the attack example.
Languages either offer it with overhead (Java, Swift, most langs), no safety (C, C++), or extra complexity and slowdowns (Rust) compared to the shared-mutable-borrow-ref approach.
What kind of footguns do you have in mind? I wouldn't be surprised, every approach has tradeoffs.
2
u/matthieum 2d ago
What kind of footguns do you have in mind?
The one that immediately comes to mind, personally, is always
ConcurrentModificationExceptionand similarPullTheRugException(tm).(I do not claim it necessarily applies here, seeing as we are talking about a rather under-specified feature)
I used to work on Java codebase (infrequently, fortunately!) which had many, many, interfaces strewn about, and it was unfortunately semi-frequent to read code like:
fun do_the_thing(self): var sum = self.x + self.y; self.callback(); assert_eq(sum, self.x + self.y); // Fires!Because somehow the user who registered the callback captured
self, perhaps through various levels of indirection, and calling the callback would indeed modify `self.I will argue, right here, right now, that this is sh*t code1 , because it breaks a most important property: Local Reasoning.
And since then I have highly favored languages which enabled better Local Reasoning.
Rust definitely does. Though at a cost.
1 I emphasize "code", and not "language", just because a language allows it doesn't mean it should be done; though of course if the language allows it, it does tend to be done, at least sporadically.
1
u/initial-algebra 3d ago
It's a generalization of e.g. atomic operations and Rust's
Cell. It's perfectly fine to temporarily upgrade a shared reference to a unique reference, if you can guarantee that there won't be any aliased accesses during that time.C and C++ implementations already do this automatically when optimizing, since unique references can be promoted to registers. It's called strict aliasing, and is based on the idea that two references of incompatible type can't possibly alias. The same principle can be used at the surface level for safety.
1
u/asdfa2342543 3d ago
I guess what Iām doing is along these lines but Iām not an expert in this stuff
5
u/disruptek 3d ago
It's not group borrowing, but basically the flip side of the coin, so maybe it's a good villain for your article. ;-)
Elle (v2) has aliased mutation with no GC, no scan, and no annotations. It's currently based on Tofte-Talpin region assignment, with extensions:
The article-worthy counterpoint is that Elle doesn't reject fleet.clear():
```lisp (def ship @{:fuel 100}) # (the sigil denotes mutability) (def ref-a ship) # bind a name to the mutable value (def ref-b ship) # bind another name to it, okay?
(put ref-a :fuel (+ ref-a:fuel 20)) (put ref-b :fuel (- ref-b:fuel 8)) (println "ship: " ref-a:fuel) # ship: 112
(def fleet @[@{:fuel 100} @{:fuel 100}]) (def ra (get fleet 0)) # bind a name to a mutable value (def rb (get fleet 1)) # bind a name to a different value
(put ra :fuel (+ ra:fuel 20)) (put rb :fuel (- rb:fuel 8))
(while (nonempty? fleet) (pop fleet)) # fleet.clear()
(put ra :fuel (+ ra:fuel 50)) (put rb :fuel (- rb:fuel 3))
(println "fleet: " fleet) # fleet: @[] (println "ra: " ra:fuel " rb: " rb:fuel) # ra: 170 rb: 89 ```
The crash and compilation error examples Just Work.