5 ms·

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. "

by comex 1y ago

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.

pklausler 1y 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 1y 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 1y 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 1y 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.
thomasmg 1y 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 1y 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 1y 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.) [1] https://github.com/thomasmueller/bau-lang https://github.com/thomasmueller/bau-lang
    - 1y ago
verdagon 1y 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!
codedokode 1y 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.
nmsmith 1y ago
Hi there, I am the Nick whose design we're discussing. You raise some valid points: the blog post enumerates some limitations with Rust's model, but my design (as written) only resolves a subset of those limitations. We probably should have made that a bit clearer. That said, there is still hope! I have been iterating on the design over the last 9 months and am fairly confident that I can model graphs, as long as a few restrictions are imposed, such as not being able to delete nodes. But I can't prove this will work yet, so we will need to wait and see what the next design iteration looks like. I'm fairly confident that the next iteration will be more powerful than the version presented in OP's blog post.
- comex 1y ago
  Good luck! I look forward to seeing the results.

by comex 1y ago

pklausler 1y 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 1y 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 1y 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 1y 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.

thomasmg 1y 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 1y 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 1y 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.) [1] https://github.com/thomasmueller/bau-lang https://github.com/thomasmueller/bau-lang
  - 1y ago

verdagon 1y 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!

codedokode 1y 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.

nmsmith 1y ago

Hi there, I am the Nick whose design we're discussing. You raise some valid points: the blog post enumerates some limitations with Rust's model, but my design (as written) only resolves a subset of those limitations. We probably should have made that a bit clearer. That said, there is still hope! I have been iterating on the design over the last 9 months and am fairly confident that I can model graphs, as long as a few restrictions are imposed, such as not being able to delete nodes. But I can't prove this will work yet, so we will need to wait and see what the next design iteration looks like. I'm fairly confident that the next iteration will be more powerful than the version presented in OP's blog post.

comex 1y ago
Good luck! I look forward to seeing the results.