The borrow checker within | Hacker News Reader

The borrow checker within

smallcultfollowing.com

201 pointsyurivish36 comments

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.

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

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.

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

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

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/

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

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

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.

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.

Leave it to emojis to ruin communication:

    // A thread to consume those values:
    std:<emoji here censored by hn>:spawn(move || {

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.

> 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?

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.

Am I necessarily always allowed to convert a reference to a numeric address?

Yes, it's safe to cast a reference to a raw pointer and a raw pointer to an address.

It might have been nicer in some ways if the language had restricted that a bit more up front, but it would probably have taken some design work to do that while still supporting a lot of the low-level stuff people need to do.

An internal reference could only be cast to a relative memory offset. It’s not a global memory address in disguise like a normal reference. So the same casting rules wouldn't apply.

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.

Previously: https://news.ycombinator.com/item?id=40553643

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.

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

Hence why the sweet spot is to combine automatic resource management, with affine, linear, and effect type systems.

As those languages are doing.

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.

Python adoption, and shipping Chrome everywhere, prove that it isn't microbenchmarks that drive language adoption.

Not every use case is the same as yours though?

What I can tell you is that there are tasks that I cannot do in Python because my work would take 70 times longer to finish than if I did it in Rust. And that’s not a delay on the order of seconds but on the order of weeks.

> Not every use case is the same as yours though?

Spot on, Rust is only for very special use cases, where the only viable alternative would be raw C, or C++ with its wrong defaults, instead of any other compiled language.

Between Python and Rust there is a myriad of compiled languages to chose from, no need for Rust for those 70x improvement.

Yet, to come back to the microbenchmarks reasoning, many folks will still pick up Python's productivity over Rust's 70x speed improvement.

You are a reasonable person. I don’t know why you are arguing that one approach fits every use case. In your earlier post above, you declared a sweet spot that fits everyone. All I’m saying is that the sweet spot depends on the application.

If Python’s productivity made up for its problems, then the OS you’re using (kernel + significant parts of userland) would be written in Python, too. But it isn’t, because sometimes its speed penalty is prohibitive. This is not a controversial statement. And the OS is not a “very special use case.”

I am typing this from an OS that is mostly written in Java, with only enough C, C++ and Rust for when it matters.

Rust will probably never replace Java on this OS, or Kotlin, for the applications on Play Store, that aren't a game engine. It isn't even officially supported on the NDK.

Just like on my fruity devices, it is Swift, with non copyable types that will be used for systems services and firmware, not Rust.

This is the kind of sweet spot I am talking about.

Python only came into the picture, as an example of people that don't look into performance charts before picking their tools.

And if Python community was half as serious as the Lisp community in JIT/AOT toolchains, who knows, maybe some would be crazy enough to create a Python Machine.

> it is Swift, with non copyable types that will be used for systems services and firmware

When you mention firmware, do you know of examples where Swift is used for this, or is this an aspiration? Are you talking about Swift for Arduino maybe, or do you have something else in mind?

We'll see how well it works for those languages. I have strong doubts that it'll be very usable in practice in for example Swift. That's because the boundary between "reference-anywhere" and aliasable-xor-mutable is notoriously problematic to cross, and when your entire ecosystem is "reference-anywhere" (e.g. Swift's core collections), your aliasable-xor-mutable world becomes very limited, to the point where most programmers won't even bother.

That is the point anyway, this is black level 10 dan stuff for many codebases, only to be used when it really matters, no need to write everything like this.

The problem being that most of the time you can't really use it even when it really matters, because the rest of the ecosystem doesn't. “when it really matters, and you have the freedom to do it” is not as good as “when it really matters”.

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 ?

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.

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.

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

Reply on news.ycombinator.com