[HN Gopher] The borrow checker within
___________________________________________________________________
The borrow checker within
Author : yurivish
Score : 183 points
Date : 2024-06-12 13:00 UTC (3 days ago)
(HTM) web link (smallcultfollowing.com)
(TXT) w3m dump (smallcultfollowing.com)
| yuvadam wrote:
| I really enjoyed this post, resonates with many small experiences
| I had learning the various patterns that do and don't work in
| Rust.
|
| Also blows my mind how crazy complex these language design topics
| are.
| Animats wrote:
| Good to see this.
|
| _" There is another theme running through here: moving the
| borrow checker analysis out from the compiler's mind and into
| types that can be expressed. Right now, all types always
| represent fully initialized, unborrowed values. There is no way
| to express a type that captures the state of being in the midst
| of iterating over something or having moved one or two fields but
| not all of them. These changes address that gap."_
|
| I have some misgivings about trying to do everything with types.
| That leads to having to perform complex, hard to understand
| operations on types, as you add and remove restrictions. Keeping
| borrowing orthogonal from types may be clearer. Not sure about
| this, though.
|
| I'd like to see back references addressed, so structs can have
| references to their owners. General concept: when possible, do
| statically what Rc, Weak, and .borrow() can do for backlinks at
| run time. Such static analysis seems possible for non-mutable
| references. Mutable is going to be tough, though. It's a lot like
| compile-time single-lock deadlock detection, where you try to
| check that the same lock is never locked twice in nested
| contexts.
| gpm wrote:
| Immutable back references seem limiting... because how are you
| inserting things if you have a reference saying the thing you
| are inserting it into can't mutate.
|
| If you're willing to use locks or something for interior
| immutability though... I think it should already be possible.
| It works in a toy example: https://play.rust-
| lang.org/?version=stable&mode=debug&editio...
| Animats wrote:
| Right. You can also do that with Rc and borrow.
|
| When nothing in the call tree is using the parent link, it
| should be OK to add children. That's potentially checkable at
| compile time.
| Animats wrote:
| Thinking about this some more, that example has a mutex in
| a single thread program. If it's ever reached while locked,
| the program is stuck. This is a demonstration that the
| backlink problem and single-thread deadlock detection are
| equivalent.
|
| Work on compile time deadlock detection for Rust is
| underway.[1] It's complicated, but do-able.
|
| [1] https://github.com/hlisdero/cargo-check-deadlock
| pas wrote:
| As far as I understand lifetimes are already in the types, just
| elided most of the time. (That said, the type system is already
| full of marker traits, so keeping complexity from growing more
| and more is always an important goal. Hooweeever, this also
| means that people are pretty used to markers, so their
| individual cost is amortized over all of them basically. And
| adding one more might make sense, especially if it can be
| elided in general.)
| Georgelemental wrote:
| Previously: https://news.ycombinator.com/item?id=40553643
| tmpfs wrote:
| These are some really good suggestions.
|
| I think a "syntax for lifetimes on places" (2) is really neat and
| would make lifetimes much easier to reason about, by removing the
| indirection and being explicit about where the borrow is from in
| the declaration makes the intention much clearer.
|
| But my personal favorite is the point about "internal references"
| as I struggled with this a couple of times. I think this would be
| an excellent improvement. In the end I used ouroborous [1] to
| achieve this but having it built in to the language would be
| excellent.
|
| [1] https://docs.rs/ouroboros/latest/ouroboros/
| aabhay wrote:
| It would be cool to annotate the lifetime using this syntax
| instead:
|
| -> &map's mut V
|
| The apostrophe here matches the syntax of lifetimes roughly and
| to me makes it EXTREMELY clear whats going on.
| superb_dev wrote:
| I wanted to share a technique I saw recently related to a post
| linked within this post:
| https://smallcultfollowing.com/babysteps/blog/2015/04/06/mod...
|
| > The primary disadvantage comes about if you try to remove
| things from the graph. The problem then is that you must make a
| choice: either you reuse the node/edge indices, perhaps by
| keeping a free list, or else you leave a placeholder.
|
| There's another option, called generational indices! I discovered
| this from the "generational_arena" crate:
| https://docs.rs/generational-arena/latest/generational_arena...
| alexisread wrote:
| This looks the same as in Vale? I like this technique, and Vale
| tries to go further with index elision to remove the memory and
| checking overhead. https://verdagon.dev/grimoire/grimoire
| pjmlp wrote:
| While I welcome the effort going into improving the lifetimes
| experience in Rust, this also kind of reflects that the approach
| being taken by other languages, meaning keeping automatic memory
| management by default, and only enough affine/linear typing
| support for when performace really, really matters, is a more
| productive approach.
|
| Examples of that approach, D, Swift, Chapel, Linear Haskell,
| OCaml Effects.
|
| The changes on the article, while welcomed in the context of Rust
| typesystem, will make being aware of all borrow check rules even
| more complex, and back into language lawyers kind of C++
| developer experience, unless backed up by IDE tooling, on when to
| write what suggestions.
| pornel wrote:
| > _Unfortunately, most people seem to have taken the wrong
| lesson from Rust. They see all of this business with lifetimes
| and ownership as a dirty mess that Rust has had to adopt
| because it wanted to avoid garbage collection. But this is
| completely backwards! Rust adopted rules around shared mutable
| state and this enabled it to avoid garbage collection. These
| rules are a good idea regardless_
|
| https://without.boats/blog/references-are-like-jumps/
|
| Ownership and borrowing are very useful regardless of
| performance and memory management.
|
| They help to reason about the program, enabling local reasoning
| instead of global. When your function gets an owned object or
| exclusive reference, you know nothing else will mutate it (and
| you get that without resorting to purity/immutability). You
| don't need defensive copies.
|
| In your methods you can return temporary references to internal
| objects, and you don't have to worry that users will keep them
| too long (such as use a handle to a resource after you
| close/delete the resource).
|
| There are many useful patterns that can be expressed with
| control over sharing, copying, and mutability, and memory
| management is just one of them.
| pjmlp wrote:
| Hence why the sweet spot is to combine automatic resource
| management, with affine, linear, and effect type systems.
|
| As those languages are doing.
| nequo wrote:
| Whether that's the sweet spot really depends on what your
| goal is.
|
| The languages that you mention are several times slower
| than Rust for non-IO bound stuff (in the computer language
| benchmarks game). If this speed penalty matters for what
| you are doing, then idiomatic Rust can be much better than
| Haskell or OCaml code tuned for performance.
|
| And when it comes to Linear Haskell specifically, GHC does
| not use linear types for performance optimization. If this
| has changed recently, I'd be thankful for a source to read
| more.
| IshKebab wrote:
| These would be very welcome changes.
|
| How do self references work when the struct is moved, given that
| they're pointers?
|
| Also I'm not sure about having a feature that only works for
| private functions. I can imagine that would be very weird and
| annoying. I think it would be fine if it were allowed for public
| functions too, we just need better built in tooling to warn you
| about API breaking changes. After all you can already break API
| compatibility in obvious and very subtle ways. It would be great
| if Rust said something like "this is an API incompatible change;
| you need to increase the version number".
|
| I think there are third party tools that try to do that but it
| would be great if it was first party.
| alkonaut wrote:
| > How do self references work when the struct is moved, given
| that they're pointers?
|
| Are all references necessarily (global) pointers? Couldn't self
| references be offsets?
| Rusky wrote:
| Yes, they are necessarily global pointers. If a self
| reference is an offset, what happens when you take _its_
| address (and pass that somewhere else that doesn 't know
| where it came from)?
|
| Now every "reference to a reference" (and similar things) can
| _dynamically_ be a global pointer or a relative one, with no
| way to tell how to use it.
| cptroot wrote:
| I believe this self-references proposal won't cover structs
| that point inside themselves. Instead it would only allow you
| to store references that point inside other members heap
| allocations.
| conaclos wrote:
| View types make me think of the modifies clause introduced by
| some verification tools and in an earlier specification of Eiffel
| [1]. Basically the clause allows you to list the fields that are
| affected by a function with mutations.
|
| [1] https://bertrandmeyer.com/2011/07/04/if-im-not-pure-at-
| least...
| cassepipe wrote:
| I am not well versed in Rust so I can't judge the design
| decisions fairly but I do find that cpp2's in, out, inout, move
| and forward keywords for functions arguments much easier to
| follow mentally that rust's lifetime annotations :
| https://youtu.be/6lurOCdaj0Y?feature=shared&t=3076
|
| We can do the same kind of (basic?) borrow checking with those
| can't we ?
| CryZe wrote:
| No, from a quick glance those are only for moves of individual
| values. Lifetimes are something different. They are used for
| relating multiple (> 1) parameters / return values with each
| other. There is no way to have that without having a syntax for
| it.
|
| It's important to note that lifetimes are not just for the
| compiler. They are also documentation / API contracts:
|
| fn add_to_vec<'a>(element: &'a str, vec: &mut Vec<&'a str>) {
| ... }
|
| This documents that the vec passed into the function can't
| outlive the element that's passed in. That's because the string
| (a reference (pointer) to the string data) that's passed in
| gets stored in the vec. So freeing the string and then using
| the vec would result in a use after free.
|
| You can't have this power without a syntax for it. You could of
| course do some global analysis, but now you can't have API
| contracts like this anymore, which are important for semantic
| versioning.
|
| An alternative syntax a language could use would be to have
| arbitrary pre- and post-conditions that the compiler can
| verify, which would be a whole lot more powerful, but also a
| lot more wordy than the short lifetime "tags" that Rust uses.
| kibwen wrote:
| Lifetimes in Rust are about giving you the ability to say "I
| have a reference, and I may not know exactly how long the
| underlying data may live for, but I do know that it will last
| for _at least_ as long as this other thing ". So for example:
| fn get_reference_to_first_element(x: &[u8]) -> &u8 {
| return &x[0] }
|
| There are lifetimes here that express that the reference that
| is returned from this function will live as long as the
| reference that was passed in. In cases like this where the
| association is obvious, the lifetimes are implied and you don't
| need to write them. The desugared form looks like this:
| fn get_reference_to_first_element<'a>(x: &'a [u8]) -> &'a u8 {
| return &x[0] }
|
| Lifetimes are present on structs for the same reason.
|
| A system that is limited to annotating only function input
| parameters would be limited to inferring the programmer's
| intent everywhere, which limits its utility to simple cases
| (which might be fine for some languages, but I suspect will not
| satisfy C++).
|
| In addition, from glancing briefly at that video, it seems as
| though those five keywords seem to be more concerned with
| ensuring use-after-initialization, whereas Rust's lifetime
| system is about preventing use-after-free.
___________________________________________________________________
(page generated 2024-06-15 23:01 UTC)