I’m pretty impressed, but also skeptical. There’s a contradiction in this post.
Near the beginning of the post is a list of use cases for mutable aliasing. "Back-references", "doubly-linked lists", "delegates" - all cases where you have persistent objects with references to each other, i.e. a cyclic graph of objects.
Near the end, the post says: “The mutual isolation restriction will influence our programs' data to look like trees, similar to how Rust's borrow checker does.” In other words, the proposed approach can’t actually support those use cases!
The post continues by saying it improves on Rust’s borrow checker by having “much more relaxed rules around how we access those trees from the outside”. That may be true, and I’m legitimately looking forward to playing with this in Mojo. But it’s a much smaller improvement (while still coming at the cost of added complexity). It doesn’t really “get the best of both worlds” as the post says earlier.
To be fair, there may be ways to apply similar ideas to get some subset of use cases for cyclic object graphs to work. Some of verdagon’s past blog posts have proposed mechanisms that do something like that. But that would be a whole different thing from what’s being proposed here.
thomasmg · 3h ago
I think you are right. The post talks about mutable vs immutable borrows, and how to have multiple mutable borrows, safely. But doubly-linked list are hard in Rust due to ownership, and not borrowing. (Doubly linked lists could be supported by "splitting" and "merging" ownership: having "half"-owners, and then you can merge ownership.)
I understand the reason for having 1 mutable xor n immutable references... but I think Rust made the wrong choice here: now we see two versions of each method, one with mutable and another without mutable. It's similar to the async coloring problem, but instead of async / not async, in Rust you have mutable and non-mutable. It would simplify things a lot for the programmer (not for the compiler, OK), if all borrows are mutable. Sure the compiler can't always emit noalias, and multi-threading gets slower... But with a sane memory model (as in Java), I think it would be simpler for the programmer.
comex · 3h ago
But how would you prevent use-after-free? In other words, how do you prevent a child object's method from reaching out to its parent object and, say, clearing the container that contains the child object? Specifically, how do you do that without reference counting or garbage collection.
thomasmg · 3h ago
Well the distinction between mutable and immutable borrows doesn't solve use-after-free. What prevents use-after-free is ownership. There is one owner, and the owner can not free the memory as long as there is a borrower (it doesn't matter whether the borrower is mutable or not). So that's the task of the borrow checker.
For my own programming language [1], I have only mutable borrowers (similar to Java), and a much simpler borrow checker: a method that holds a borrow can not call a method that potentially frees an object of the same type (directly or indirectly). I'm not sure yet if this is sufficient; it's still a borrow checker, just a very simple one. (My language uses reference counting by default, but does support single ownership + borrowing.)
I'm looking forward to your experience with this approach!
Bit off topic, but is there any particular reason you went with a go-like `ident type` syntax over the more common ones like the C or the ML one?
codedokode · 2h ago
For back links, can we have a special pointer type (back link to owner) that automatically gets updated when the object is moved/copied? Also auto-initialized when object is created.
pklausler · 3h ago
It could be made to work in a language like Haskell, where cyclic structures can arise only in limited circumstances (recursive `let` groups) and can be given a distinct runtime representation.
comex · 3h ago
Well, if everything is immutable like in Haskell, then you don't really run into the problems described in the blog post in the first place. You can live with Rust's "no mutable aliasing" rule instead.
pklausler · 2h ago
Obviously; but the point was, if the language were to limit the circumstances in which circular structures can arise, one could exploit that fact.
gf000 · 36m ago
I was thinking that the type system can in certain cases determine that no circular reference is possible for an instance of this type - in that case it could e.g. use an RC (for a region only having that type of objects), and fallback to either an arena-like pattern of freeing everything at once (if only internal circular references exist), or a tracing GC.
verdagon · 3h ago
This approach solves one borrow checking pain point (by allowing temporary mutable aliasing, even across function boundaries), but the post might actually be a bit conservative in saying it will influence our programs' data to look like trees.
As a thought experiment, I've been imagining how this would handle an architecture like e.g. Google Earth's, where a program's classes are divided into multiple "layers". For example, an upper "business logic" layer (DocumentManager, Document, CardManager, Card, StateManager) might have references to the more general "services" lower layer (NetworkService, FileService).
With Nick's system, we could have a group annotation on these various upper-layer classes, like e.g. `Document[s: group IService]`. With these annotations, these upper-layer classes can have references to the services themselves (though not their contents). This might let services' methods mutate the services' contents even though others have references to them (though not their contents). The services' methods would have to communicate that they're modifying the contents of the services (via a `mut` annotation), and the compiler would prevent holding references to the services' contents across those callsites. But also, those contents are private anyway, so the user wouldn't have those references anyway.
If that turns out to be true (Nick and I are still exploring it) then he's found a way to make borrowing work for some DAG-shaped program architectures, rather than just strictly tree-shaped architectures.
On top of that, if we compose this approach with linear types, I think we can get at least halfway towards compile-time-memory-safe back-references. TBD whether that works, but that would be pretty exciting.
TL;DR: My saying it only supports tree-shaped programs is me hedging and being conservative.
Still, until these things are proven to work, I should be more consistent in when I'm conservative vs optimistic. I'll update the article to address that. Thanks for pointing that out and helping me be more consistent!
leoc · 4h ago
In memory-safety discussions it needs to be borne in mind that 'simply fix the hardware' is also a viable approach; or at least it's a lot more viable than it was or seemed to be a few decades ago https://en.wikipedia.org/wiki/Capability_Hardware_Enhanced_R... . Memory-safe BSD and applications running on real memory-safe RISC-V hardware apparently already exist, though obviously, yes, even in a best case existing architectures would not come close to being fully displaced for a long time. That said, I really hope the process isn't being further delayed by attempts to grub license money.
astrange · 6m ago
Secure hardware needs software cooperation to work - for instance to avoid type confusion you need to tag memory with types, but malloc() doesn't know the type of memory it's allocating.
comex · 3h ago
True. To be fair, CHERI guarantees only security, while borrow checking (when it works) guarantees both security and correctness. If you write to a freed pointer or out-of-bounds, CHERI guarantees that your write either crashes or lands somewhere harmless, rather than corrupting other data. But borrow checking guarantees you won't perform such writes in the first place.
Yet while correctness may excite programmers, it's security that gets the decision makers' attention. At the end of the day, security is just much more impactful.
We'll see if Morello ever makes its way to the types of CPUs used on phones and higher-performance devices.
Big fan of Verona, I love their memory safety approach as well. I wrote a bit about it in the Grimoire [0] too. IIRC they plan for the user to specify whether a region is backed by an arena allocator or GC, which sounds pretty nice. It's kind of hard to track down details though, most of my knowledge comes from reading David Chisnall's comments on lobste.rs.
I had a somewhat related idea to this which was simply to track reference stability (i.e., is there any operation beyond freeing the data outright that will invalidate them).
A reference into a vector is unstable so you can only have 1 mut xor N read. A reference into an arena is stable so you can have all the muts you want, but they cannot be sent across threads.
Reference to object vs reference to contents is also related, you can safely have multiple mut references to the same object that cannot invalidate each other, even if they invalidate references to the contents.
This can be tracked with path analysis as employed by Hylo (Hylo only has second class references, but I mean the algorithm they use to track paths is applicable).
mrkeen · 7h ago
> Because of those "inaccessible" rules, we can never have a readwrite reference and a readonly reference to an object at the same time.
I can't not see this as a good thing. It's almost at the level of "the only thing an ownership system does".
If my thread is operating on a struct of 4 int64s, do I now have to think about another read-only thread seeing that struct in an invalid partially-written state?
wavemode · 7h ago
Ideally, the rules for single-threaded references and references that are allowed to be shared across threads would be different.
zozbot234 · 7h ago
That's why Cell<T> and RefCell<T> are a thing. Both allow you to mutate shared references, but disable shared access across threads. The qcell crate even includes a version of Cell/RefCell that's "branded" by a region/lifetime, just like in this proposal.
codedokode · 2h ago
As I remember, Cell only allows moving/copying data from/to cell so if you have a 128-byte object inside do you have to copy it to modify? Or this can be optimized?
codedokode · 4h ago
Even with a single thread you need to ensure that the object you are accessing, still exists and was not freed.
wavemode · 3h ago
If you're talking about stack objects, that's what lifetimes are for.
If you're talking about heap, you can accomplish that by restricting that the references can't be used to free or invalidate the memory. But you could still allow them to be mutable.
codedokode · 4h ago
The general rule to prevent any data races (as I guess) between threads is that at any point of time there can be either one writer or multiple readers to the same object. Rust guarantees this by not allowing to have any other references if you have a read-write (mutable) reference.
Note that Rust is more strict than necessary - theoretically you can have multiple writable and readable references, but not use them simultaneously and observe the rule. But it is difficult (or even impossible) to verify during compilation so Rust doesn't allow it. C allows it but leaves verification to the author which doesn't work well and doesn't scale.
This situation can happen if you have a graph of objects. For example, in an OS you might have a Process object having references to a list of opened Files, and have a File hold reference back to Process that opened it. In this case you cannot ever have a writable reference to the Process from anywhere because Files already have multiple reading references. And Files can have only read-only references to the Process that opened them.
So you have to use only read-only references and additional structures like Cell, Arc etc. that allow safe writing through them. They are cheap, but not free and ideally we as developers want to have memory safety for free. That's the problem yet to solve.
Note that there are other ways to achieve safety:
- use C and manually verify that your program never breaks this rule - requires god level coding skills
- immutable data - after the writer finished writing, data are "frozen" and can be safely shared without any checks and no rules are broken. Very good, but modification is expensive and requires you to clone the data or use clever and complicated design (for example, if you have 10-elements array but shared a reference only to first 7 elements, you can safely append to the last 3 elements because nobody else knows about them - that's how ring buffers work). See immer C++ library for example.
- atomic variables - allow safe reading and writing at the same time, but can hold at most 8 bytes. Note that using a same variable from different CPU cores causes L1 cache line migrations which, last time I measured it, takes about 2-3 ns or ~10-15 cycles.
- mutexes - ensure rule is observed but make everyone wait. Python's approach.
- using only a single thread. JavaScript's approach. You can have multiple references but you still need to ensure they are pointing to a live object (JS solves this by using an expensive garbage collector).
And by the way if you know more methods or ideas please share them!
titzer · 4h ago
> And by the way if you know more methods or ideas please share them!
Use a transaction manager (HTM or STM). The STM is going to boil down to lockfree synchronization, logging, and retry. Transactions can fail and retry.
But ultimately, all inter-thread communication boils down to programs (or libraries) using barriers for acquire/release semantics and/or using compare/swap and atomic read-modify-write.
> at any point of time there can be either one writer or multiple readers
Time is a slippery notion in concurrency. Most language-level memory models (e.g. Java) or even hardware-level concurrency models focus on happens-before relations, which are induced by executing certain operations. At the hardware level, you can basically think that a CPU receives asynchronous updates about cache lines from other processors (potentially out of order). While technically the cache coherence protocol pushes cache lines into processors, you can't ever guarantee that one "writer" can "push" updates into all other CPUs. Instead, you have to rely on those other CPUs executing either fences or being forced to execute fences through global OS means, such as IPIs. Those other CPUs executing fences (barriers) or other atomic operations induce happens-before relations.
codedokode · 3h ago
> Time is a slippery notion in concurrency. Most language-level memory models (e.g. Java) or even hardware-level concurrency models focus on happens-before relations, which are induced by executing certain operations
You are correct, but for simplicity we can assume that the CPU executes one operation at a time and still have a valid model for reasoning about data races.
> But ultimately, all inter-thread communication boils down to programs (or libraries) using barriers for acquire/release semantics and/or using compare/swap and atomic read-modify-write.
Interesting. I read about STM and it reminded me of "modification box" algorithm for modifying immutable trees, which also uses versions. So it is another clever but complicated trick. Also it seems that it requires locking? That's not very good given that locks often need syscalls.
mrkeen · 1h ago
> Also it seems that it requires locking?
STM requires locking in the same way that GC requires malloc. It gets it right so that the programmer doesn't mess it up.
astrange · 1m ago
A non-compacting GC still needs a good malloc because it needs to avoid heap fragmentation.
titzer · 3h ago
> Also it seems that it requires locking? That's not very good given that locks often need syscalls.
AFAIU in most STMs all the fast paths are implemented using lock-free algorithms with just barriers.
codedokode · 2h ago
How do you implement "commit" part safely (writing changes to the object) without locking the object?
kibwen · 8h ago
> In any language, when we hand a function a reference to an object, that function can't destroy the object, nor change its type
This isn't quite true. While Rust doesn't currently support this, people have proposed the concept of `&own` references that take ownership of the object and free it when the reference goes out of scope (consider that Rust's standard destructor signature, `fn drop(&mut)`, should probably take one of these hypothetical owning references). I addition, I believe that languages with typestate can cause types to change as a result of function calls, although I don't quite understand the details.
verdagon · 8h ago
Great point =) That's true for a lot of languages (including Mojo too), so I should have said "non-owning reference" there. I'll update the post to clarify. Thanks for catching that!
modulared · 7h ago
> I believe that languages with typestate can cause types to change as a result of function calls
Do you have any specific languages?
skywal_l · 8h ago
I don't understand your comment. `drop` takes a *mutable* reference. But by default, references in Rust are immutable.
codedokode · 1h ago
Drop takes an object itself ("owned reference"), as I remember. Mutable ref allows reading/writing but not destroying or passing the ownership.
Owner = can read/write/destroy
Mutable ref = can read/write
Immutable ref = can only read, guarantered not to change
shared references are immutable in Rust, mut references and shared references are both references.
Ygg2 · 7h ago
Kibwen is saying that there was an idea to have `fn drop(&mut x)` from Drop trait become `fn drop_own(&own x)`. Then `&own` would do mutation and drop the owner of the reference. A regular &mut reference shouldn't do that outside of `drop(&mut x)`.
wavemode · 7h ago
An &own reference seems like it would just be equivalent to a Box.
steveklabnik · 1h ago
Box heap allocates, references do not.
wavemode · 9m ago
> `&own` references that take ownership of the object and free it when the reference goes out of scope
How can you free something if it's not allocated
littlestymaar · 7h ago
Intriguing, what would be the purpose of such owning references compared to just passing ownership? Is that to have a way to reliably avoid memcopying large objects when passing them by value?
kibwen · 6h ago
> Is that to have a way to reliably avoid memcopying large objects when passing them by value?
I believe so, yes. Currently the only way to transfer ownership is by-value, and LLVM might optimize away the memcpy, but also it might not.
nixpulvis · 7h ago
No mention of how this is safe when operating on data across threads? One of the biggest wins for Rust is sane treatment of references when using parallelism.
TL;DR: Mutability is tracked at the group level, so we can share an immutable group with any number of threads (especially good with structured concurrency) or lend a mutable group to a single other thread. References themselves are still aliasable, regardless of the group's mutability.
Taking an existing (mutable, aliasing) group and temporarily interpreting it as immutable has precedent (I did it in Vale [0]) so I like the approach, but I might be biased ;)
(This is from my memory of how Nick's proposal works, I'll ask him to give a better answer once morning hits his Australia timezone)
No, Tree Borrows is aimed at defining the semantics of memory accesses. It does not provide a way to statically check whether they are correct, which is what the borrow checker and this proposal aim to do.
estebarb · 7h ago
I'm not sure if I understand it correctly. So, if I have a hashtable, adding or removing an element would invalidate existing pointers to any other element in the hashtable? I guess it makes sense from a memory release POV, but... I end up thinking that for databases using GC or RC is a better approach. Maybe I'm biased, but I have found far easier to work on databases written in C or C#. For that kind of programs I felt Rust overrestrictive and forcing to more dangerous patterns such as replacing pointers with offsets.
verdagon · 7h ago
Yep, adding or removing an element would invalidate existing pointers to any other element in the hash table. This is generally regarded as a good thing if your elements are stored contiguously in the hash table, because a resize would cause any existing pointers to dangle. This should be true for C, and might be true for C# if you're using `struct`s which put the data inline (memory's a bit fuzzy on C#'s rules for references to structs though, maybe someone can chime in).
This new approach still requires us to be mindful of our data layout. Not caring about data layout is still definitely a strength of GC and RC. I'm actually hoping to find a way to blend Nick's approach seamlessly with reference counting (preferably without risking panics or deadlocks) to get the best of both worlds, so that we can consider it for Mojo. I consider that the holy grail of memory safety, and some recent developments give me some hope for that!
(Also, I probably shouldn't mention it since it's not ready, but Nick's newest model might have found a way to solve that for separate-chaining hash maps where addresses are stable. We might be able to express that to the type system, which would be pretty cool.)
jfecher · 4h ago
> I'm actually hoping to find a way to blend Nick's approach seamlessly with reference counting (preferably without risking panics or deadlocks) to get the best of both worlds, so that we can consider it for Mojo. I consider that the holy grail of memory safety, and some recent developments give me some hope for that!
Ante's approach manages to blend a similar scheme for safe, shared mutability with Rc. There are some examples on the most recent blog post on its website of it. IMO combined with its shared types it emulates high-level GC'd code very well.
estebarb · 5h ago
Thanks for the answer. For instance, usually those containers are used as indexes in DBs, so they contain pointers to data, not the data itself. That is an scenario where the references shouldn't be invalidated.
Idk if it may be possible to introduce "semantic monitors". Say, a field within a class and an external container must be updated together. In practice the only time when I have needed to break the single ownership is for keeping internal data views. I know it is safe, but convincing Rust of that is painful.
codedokode · 4h ago
Rc is slightly expensive and Gc is super expensive. I would prefer a memory safety for free.
As for C, it leaves verifying the safety up to you, it is not easy at all and I would rather spend time on something else using safe languages.
Near the beginning of the post is a list of use cases for mutable aliasing. "Back-references", "doubly-linked lists", "delegates" - all cases where you have persistent objects with references to each other, i.e. a cyclic graph of objects.
Near the end, the post says: “The mutual isolation restriction will influence our programs' data to look like trees, similar to how Rust's borrow checker does.” In other words, the proposed approach can’t actually support those use cases!
The post continues by saying it improves on Rust’s borrow checker by having “much more relaxed rules around how we access those trees from the outside”. That may be true, and I’m legitimately looking forward to playing with this in Mojo. But it’s a much smaller improvement (while still coming at the cost of added complexity). It doesn’t really “get the best of both worlds” as the post says earlier.
To be fair, there may be ways to apply similar ideas to get some subset of use cases for cyclic object graphs to work. Some of verdagon’s past blog posts have proposed mechanisms that do something like that. But that would be a whole different thing from what’s being proposed here.
I understand the reason for having 1 mutable xor n immutable references... but I think Rust made the wrong choice here: now we see two versions of each method, one with mutable and another without mutable. It's similar to the async coloring problem, but instead of async / not async, in Rust you have mutable and non-mutable. It would simplify things a lot for the programmer (not for the compiler, OK), if all borrows are mutable. Sure the compiler can't always emit noalias, and multi-threading gets slower... But with a sane memory model (as in Java), I think it would be simpler for the programmer.
For my own programming language [1], I have only mutable borrowers (similar to Java), and a much simpler borrow checker: a method that holds a borrow can not call a method that potentially frees an object of the same type (directly or indirectly). I'm not sure yet if this is sufficient; it's still a borrow checker, just a very simple one. (My language uses reference counting by default, but does support single ownership + borrowing.)
[1] https://github.com/thomasmueller/bau-lang
Bit off topic, but is there any particular reason you went with a go-like `ident type` syntax over the more common ones like the C or the ML one?
As a thought experiment, I've been imagining how this would handle an architecture like e.g. Google Earth's, where a program's classes are divided into multiple "layers". For example, an upper "business logic" layer (DocumentManager, Document, CardManager, Card, StateManager) might have references to the more general "services" lower layer (NetworkService, FileService).
With Nick's system, we could have a group annotation on these various upper-layer classes, like e.g. `Document[s: group IService]`. With these annotations, these upper-layer classes can have references to the services themselves (though not their contents). This might let services' methods mutate the services' contents even though others have references to them (though not their contents). The services' methods would have to communicate that they're modifying the contents of the services (via a `mut` annotation), and the compiler would prevent holding references to the services' contents across those callsites. But also, those contents are private anyway, so the user wouldn't have those references anyway.
If that turns out to be true (Nick and I are still exploring it) then he's found a way to make borrowing work for some DAG-shaped program architectures, rather than just strictly tree-shaped architectures.
On top of that, if we compose this approach with linear types, I think we can get at least halfway towards compile-time-memory-safe back-references. TBD whether that works, but that would be pretty exciting.
TL;DR: My saying it only supports tree-shaped programs is me hedging and being conservative.
Still, until these things are proven to work, I should be more consistent in when I'm conservative vs optimistic. I'll update the article to address that. Thanks for pointing that out and helping me be more consistent!
Yet while correctness may excite programmers, it's security that gets the decision makers' attention. At the end of the day, security is just much more impactful.
We'll see if Morello ever makes its way to the types of CPUs used on phones and higher-performance devices.
It was interesting enough that I knew I had to write a post about it. Happy to answer any questions!
I think you guys should check out Verona (https://www.microsoft.com/en-us/research/project/project-ver...).
[0] https://verdagon.dev/grimoire/grimoire
A reference into a vector is unstable so you can only have 1 mut xor N read. A reference into an arena is stable so you can have all the muts you want, but they cannot be sent across threads.
Reference to object vs reference to contents is also related, you can safely have multiple mut references to the same object that cannot invalidate each other, even if they invalidate references to the contents.
This can be tracked with path analysis as employed by Hylo (Hylo only has second class references, but I mean the algorithm they use to track paths is applicable).
I can't not see this as a good thing. It's almost at the level of "the only thing an ownership system does".
If my thread is operating on a struct of 4 int64s, do I now have to think about another read-only thread seeing that struct in an invalid partially-written state?
If you're talking about heap, you can accomplish that by restricting that the references can't be used to free or invalidate the memory. But you could still allow them to be mutable.
Note that Rust is more strict than necessary - theoretically you can have multiple writable and readable references, but not use them simultaneously and observe the rule. But it is difficult (or even impossible) to verify during compilation so Rust doesn't allow it. C allows it but leaves verification to the author which doesn't work well and doesn't scale.
This situation can happen if you have a graph of objects. For example, in an OS you might have a Process object having references to a list of opened Files, and have a File hold reference back to Process that opened it. In this case you cannot ever have a writable reference to the Process from anywhere because Files already have multiple reading references. And Files can have only read-only references to the Process that opened them.
So you have to use only read-only references and additional structures like Cell, Arc etc. that allow safe writing through them. They are cheap, but not free and ideally we as developers want to have memory safety for free. That's the problem yet to solve.
Note that there are other ways to achieve safety:
- use C and manually verify that your program never breaks this rule - requires god level coding skills
- immutable data - after the writer finished writing, data are "frozen" and can be safely shared without any checks and no rules are broken. Very good, but modification is expensive and requires you to clone the data or use clever and complicated design (for example, if you have 10-elements array but shared a reference only to first 7 elements, you can safely append to the last 3 elements because nobody else knows about them - that's how ring buffers work). See immer C++ library for example.
- atomic variables - allow safe reading and writing at the same time, but can hold at most 8 bytes. Note that using a same variable from different CPU cores causes L1 cache line migrations which, last time I measured it, takes about 2-3 ns or ~10-15 cycles.
- mutexes - ensure rule is observed but make everyone wait. Python's approach.
- using only a single thread. JavaScript's approach. You can have multiple references but you still need to ensure they are pointing to a live object (JS solves this by using an expensive garbage collector).
And by the way if you know more methods or ideas please share them!
Use a transaction manager (HTM or STM). The STM is going to boil down to lockfree synchronization, logging, and retry. Transactions can fail and retry.
But ultimately, all inter-thread communication boils down to programs (or libraries) using barriers for acquire/release semantics and/or using compare/swap and atomic read-modify-write.
> at any point of time there can be either one writer or multiple readers
Time is a slippery notion in concurrency. Most language-level memory models (e.g. Java) or even hardware-level concurrency models focus on happens-before relations, which are induced by executing certain operations. At the hardware level, you can basically think that a CPU receives asynchronous updates about cache lines from other processors (potentially out of order). While technically the cache coherence protocol pushes cache lines into processors, you can't ever guarantee that one "writer" can "push" updates into all other CPUs. Instead, you have to rely on those other CPUs executing either fences or being forced to execute fences through global OS means, such as IPIs. Those other CPUs executing fences (barriers) or other atomic operations induce happens-before relations.
You are correct, but for simplicity we can assume that the CPU executes one operation at a time and still have a valid model for reasoning about data races.
> But ultimately, all inter-thread communication boils down to programs (or libraries) using barriers for acquire/release semantics and/or using compare/swap and atomic read-modify-write.
Interesting. I read about STM and it reminded me of "modification box" algorithm for modifying immutable trees, which also uses versions. So it is another clever but complicated trick. Also it seems that it requires locking? That's not very good given that locks often need syscalls.
STM requires locking in the same way that GC requires malloc. It gets it right so that the programmer doesn't mess it up.
AFAIU in most STMs all the fast paths are implemented using lock-free algorithms with just barriers.
This isn't quite true. While Rust doesn't currently support this, people have proposed the concept of `&own` references that take ownership of the object and free it when the reference goes out of scope (consider that Rust's standard destructor signature, `fn drop(&mut)`, should probably take one of these hypothetical owning references). I addition, I believe that languages with typestate can cause types to change as a result of function calls, although I don't quite understand the details.
Do you have any specific languages?
Owner = can read/write/destroy
Mutable ref = can read/write
Immutable ref = can only read, guarantered not to change
How can you free something if it's not allocated
I believe so, yes. Currently the only way to transfer ownership is by-value, and LLVM might optimize away the memcpy, but also it might not.
TL;DR: Mutability is tracked at the group level, so we can share an immutable group with any number of threads (especially good with structured concurrency) or lend a mutable group to a single other thread. References themselves are still aliasable, regardless of the group's mutability.
Taking an existing (mutable, aliasing) group and temporarily interpreting it as immutable has precedent (I did it in Vale [0]) so I like the approach, but I might be biased ;)
(This is from my memory of how Nick's proposal works, I'll ask him to give a better answer once morning hits his Australia timezone)
[0] https://verdagon.dev/blog/zero-cost-borrowing-regions-part-1...
[0] https://perso.crans.org/vanille/treebor/aux/preprint.pdf
This new approach still requires us to be mindful of our data layout. Not caring about data layout is still definitely a strength of GC and RC. I'm actually hoping to find a way to blend Nick's approach seamlessly with reference counting (preferably without risking panics or deadlocks) to get the best of both worlds, so that we can consider it for Mojo. I consider that the holy grail of memory safety, and some recent developments give me some hope for that!
(Also, I probably shouldn't mention it since it's not ready, but Nick's newest model might have found a way to solve that for separate-chaining hash maps where addresses are stable. We might be able to express that to the type system, which would be pretty cool.)
Ante's approach manages to blend a similar scheme for safe, shared mutability with Rc. There are some examples on the most recent blog post on its website of it. IMO combined with its shared types it emulates high-level GC'd code very well.
Idk if it may be possible to introduce "semantic monitors". Say, a field within a class and an external container must be updated together. In practice the only time when I have needed to break the single ownership is for keeping internal data views. I know it is safe, but convincing Rust of that is painful.
As for C, it leaves verifying the safety up to you, it is not easy at all and I would rather spend time on something else using safe languages.