Learning Rust with Entirely Too Many Linked Lists
cglab.ca
cglab.ca
(The two basic constructs that are hard to express safely in Rust are back pointers and partially initialized arrays. There's also some trouble with concurrency primitives. See [1])
[1] https://people.mpi-sws.org/~dreyer/papers/rustbelt/paper.pdf
I find it very confusing that you often complain about Rust's complexity, and then also complain that it isn't complex enough (i.e. doesn't have the features required statically reason about complex ownership graphs at compile time). It's fair that maybe there's complexity budget spent in places that you think aren't quite right, but I haven't picked up any reasonable plan for modelling back pointers (from anyone), nor many specific pain points that could be solved in your suggested way while maintaining the low-level nature of Rust.
First, you need to be able to talk about them. A forward ref/back ref pair has to be identified with some form of declaration at compile time. The forward pointer is an ordinary owning pointer. The back pointer is special. So add a variable attribute "back", to be used like much like "mut", but only on a reference field of a struct. Let's see if that's enough.
The invariants to be enforced are:
- If b.bak points to a, a.fwd must point to b.
- If a.fwd points to b, b.bak must be Option(None) or point to a.
These can be enforced by some simple update checks when a.fwd or b.bak is updated. The normal sequence of events is something like:
a.fwd = &mut b;
b.bak = &back a;
b.bak = Option(None);
a.fwd = None; // drop ownership of b, which deallocates it.
If you try to change b.bak to anything but Option(None) or a, that's an error. If you try to change a.fwd while b.bak is not Option(None), that's an error. This can usually be checked at compile time.
Open questions:
- Can the compiler figure out which field of a is the forward ref? That's the ref that owns b. Or is syntax needed in the declaration of the a struct for that.
- What about arrays of forward refs?
In any case, even switching to the correct Option::None syntax, your example doesn't actually make sense: &mut isn't an owning pointer, so it doesn't make sense to try to construct an owning tree with it. Maybe something like
a.fwd = Some(b);
a.fwd.as_mut().unwrap().bak = Some(&back a);
This all seems like it might be possible to solve for some special cases, but pointer aliasing is one of the hardest parts of static analysis. It's essentially impossible to do in the general case, and my intuition is that back pointers get you very close to the general case. It's not even obvious to me how one can get a binary tree with back pointers to work well.
> The compiler might optimize that out, observing that b is dead at deallocation.
Only if b doesn't have a destructor (or has a destructor that can be sufficiently inlined).
That's why they need built-in checking, rather than hacks using "unsafe". Use of back references is going to have to be restricted so you can't get two mutable handles to the same object. The trick is making that work through restrictions which can be checked locally.
> Use of back references is going to have to be restricted so you can't get two mutable handles to the same object. The trick is making that work through restrictions which can be checked locally.
Talk is cheap, and I'm not sure this talk actually says anything of note. Those "ideas" seem to be the most obvious first considerations for working out how this feature might even work:
- disallowing two mutable handles is the fundamental rule of Rust,
- the ability to check locally is a strong convention for programming language implementations, and a very strong one for Rust.
Having some concrete idea that addresses just those two points (no need to worry about syntax or anything like that) would be an improvement on the current situation: I haven't see any for this other than "runtime checking" (already exists in Rust) and "no back references".
---
In other words, vague assertions like "Rust should support back pointers" with syntax ideas are jumping way ahead. The language typically tries to provide building blocks to allow things to be built in libraries, rather than lumping opinionated features into the language. These features will often then require unsafe to create safe abstractions, but this isn't bad: the compiler itself is essentially one large unsafe block.
The place to start would be trying to create a safe back-pointer interface in a library, and seeing if there's anything that is too hard to make truly safe. This has in fact already been done, with Rc/Weak and Arc/Weak, but for zero-overhead/non-reference-counted scenarios, I think a good place to start would be a smart pointer pair like Rc but with a constructor `fn make<T>(val: T) -> (Forward<T>, Back<T>)`.
Furthermore, we're working on an allocator interface that you could use with stdlib stuff that would let you handle it.
The TL;DR is basically "if you want to, you can. It's going to be even easier in the future."
How does Linux handle 1 trillion mallocs of 1MB, on a 8GB system with 500GB hard drive, without failing?
There is nothing magic about Linux, it still cannot allocate and use memory which physically and virtually is simply not there.
Core Rust avoids almost all implicit heap allocations that aren't triggered by operations the programmer sees as allocations.[2] But there are many library functions which allocate and panic if the allocation fails.
[1] https://internals.rust-lang.org/t/notes-interviews-on-fallib... [2] https://www.reddit.com/r/rust/comments/69awhl/how_to_know_wh...
Being "safe" is not about preventing any type of crash. It's about preventing exploitable crashes and behavior.
Glad to see promising new languages pushing progress forward, though. I'm head high in C/C++/asm for decades so many of the complaints about those languages fall flat with me since I'm over the hurdles via sheer years of experience.
I think people are pretty straightforward about Rust's challenges. The borrow checker can be a hurdle and probably needs more work (although it is getting a big boost soon with non-lexical lifetimes). Compile times are not great. The macro system is powerful but can be confusing. People from some mainstream languages may have trouble wrapping their heads around the type system.
Regarding its features, these attributes:
* it can do low level, fast code;
* it's not garbage collected, but is memory safe;
* it has zero cost abstractions (and, conversely, it doesn't have ridiculous, unnecessary, slow abstractions);
* it doesn't ignore the last thirty years of innovation in programming languages (by which I mean it has a modern type system, closures, variant types, and a few other things);
* it doesn't have 30-40 years of cruft;
* it has a standard and very high quality build/packaging system;
* its developers are thoughtful and have good taste;
* it has a reasonably big community and has a good chance of catching on even more widely;
are huge. You say you think its features are exaggerated, but to my mind, what's to exaggerate? That list looks pretty great to me.
It's hard to refute or agree with you when I don't know what you're talking about. :)
If you have experienc with large C++ code bases you probably know how impossible it is to write safe code. Also after you use only unique/linear types, single inharitance (which is advised when working with a big code base), you are writing something that's easier to express in Rust than in C/C++.
Inlined asm will stay of course, Rust doesn't try compete with it.
The fact that large C and C++ code bases exist and the products they drive are successful proves that it is possible to write code in those languages that offers a good enough risk/reward balance.
This is what many Rust fans are missing: you want to sell 100% memory safety, but you're assuming that everyone wants 100% instead of 80 or 90% and that they're willing to pay the price of switching.
* I can work in C and C++, which I can get to X% safe using the techniques and tools A, B, C at the cost of M.
OR
* I can invest in learning Rust and integrating it with my environment to get to 100% at the cost of N.
Is the difference from X% to 100% big enough to pay N instead of M? How big of an X do I need? Is it even possible for me to use A, B and C?
This is how an informed decision would look like, but Rust proponents just keep repeating that X < 100.
This cost-benefit analysis also is substantially different between switching an existing codebase and starting a new one. The fact that Mozilla considers it worthwhile to switch an extremely large C++ codebase to Rust is worth noting.
Not by the Rust development team, which is what matters. They are keenly aware of the challenges, and have done a huge amount of work (particularly over the last six to twelve months) working on ergonomics and developer experience.
It's a primary focus for the Rust community, now and into the future.
Many (perhaps most?) of the specifications lined up for the current "impl period" (a time for building rather than designing) are related to developer ergonomics in some form.
The challenges are not exaggerated, but they do have solutions, so they're not deal-breakers in practice.
The learning curve is steep. It takes effort, but once you get it (and unlearn some C-isms), Rust is a quite productive language.
Some patters and data structures are not understood by borrow checker, so you have to fall back to coding as-safely-as-any-C program. However, thanks to the practice of wrapping risky bits in safe abstractions, they remain only a small fraction of any program.
It might feel that writing any "unsafe" code defeats the promise of Rust, but it doesn't. The concept of safe abstraction is quite powerful, and makes sense even for wrapping 100% C libraries, where you can encode informal constraints form the manual as code, and automatically prevent library API from being misused.
(Though, Rust's own std::collections::HashMap just does robin-hood hashing instead of separate chaining, and everyone's just going to use that, so "what data structure should a separately-chained hash-table use in Rust" is mostly a moot question.)