Hacker News Reader

Comment by amelius | Hacker News Reader

Wait until you've read this:

https://news.ycombinator.com/item?id=16442743

If you want to write a linked list like you do in C, just use pointers instead of references, mark your code as unsafe, and basically you have it.

I'm not suggesting this is a good idea, but I'm tired of the linked list argument which kind of implies Rust is much harder than C for an equivalent linked list implementation. If you explicitly choose to lose the extra guarantees, Rust is about as easy as C to write a linked list in.

I think I understand this. It's difficult to write concurrency-safe linked list operations in C too. This is a case where I would lean on the standard library for sure. Is there a different kind of problem you'd recommend to just dip your toes in?

Implementing a singly-linked list in Rust is much easier, because you can use `Option<Box<...>>`. (That is, each node in the list can hold the unique pointer to its tail, so it's easier for the compiler to prove to itself that everything you're doing is fine.)

Working through the Entirely Too Many Linked Lists book in general is super helpful, since it deliberately runs into the cases that are hard.

Implementing a hash table in Rust would probably be fine as a toe dip too. It's that multiple-references-to-each-object part that really burns you in the doubly-linked list case.

https://github.com/carols10cents/rustlings http://exercism.io/

These are probably the two best sites for small, exercise training programs in Rust. Once you've gotten through a few of them, you'd probably be ready to build something useful, which might be more interesting.

Important correction: unsafe Rust is as hard as C or C++. It means that for many developers it's just impossible to write their own linked list in Rust.

Writing a linked list in C is an exercise for undergraduates. I hope that almost all developers can do it with a little effort. Writing a linked list in C is not hard. Using it correctly is the hard part. In a safe language like Rust you can write your linked list using unsafe code and then build a safe interface around it.

It isn't even a college level exercise to do linked lists in any language. The gp is probably getting at c being hard to write safe code at large scales, which I agree with, but linked lists are not large scale.

I really want to amend that. Writing a doubly linked list in safe Rust is very hard if you want to hand out references to its contents. If you're willing to use `Rc<RefCell<...>>` or `Arc<Mutex<...>>`, then it gets doable again (albeit pretty verbose), but you can no longer hand out pure references. That's because a reference means "I have statically verified that no one else can possibly mutate this things as long as this reference is valid." `RefCell` and `Mutex` replace some of that static guarantee with runtime bookkeeping, which is great for situations where your objects don't have unique owners, but it requires you to manage all your references with smart pointers, and your APIs can't hide that (in safe code).

Wait until you see what it took to do one in C with the formally-checked, safety guarantees of Rust around the time Rust was being developed:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.553...

https://ac.els-cdn.com/S0167642313000191/1-s2.0-S01676423130...

Ok, so author needed to know C extremely well (i.e. "language lawyer"), comfortable with separation logic, able to turn informal requirements into specifications, use of ghost code, and have a SMT solver. The solvers often fail on some stuff that requires formal proof by rare experts. However, that expert was able to automatically verify a singly-linked list with just 113 ghost statements for the 90 statements in C. That's more specs than code! Industrial case studies in other article give more examples. More importantly, when making the C code as verifiably safe as Rust, the effort required had developers cranking it out at rate of two lines of code per hour.

Both manual and automated proof with separation logic has a lot more automation since then. Yet, I think programmers will more easily learn to intuitively and heuristically structure their programs to pass Rust's automated, formal checker than learning expert-level C, separation logic, and/or formal proof. And Rust can still do reference counting or unsafe operation in event it can't check something.

This write-up you all keep linking doesn't prove what you think it proves. Unless you're just saying verified handling of mutable state with cycles is extremely difficult in any language with Rust just one example. That would be true. The article also proves Rust ecosystem comes with nice guides on doing that stuff with minimal effort vs what it takes to learn same stuff for C code.

> Both manual and automated proof with separation logic has a lot more automation since then. Yet, I think programmers will more easily learn to intuitively and heuristically structure their programs to pass Rust's automated, formal checker than learning expert-level C, separation logic, and/or formal proof.

Yeah but aren't these formal proof methods a lot more general, and thus more widely applicable? In other words, does Rust provide the right balance between security and complexity?

Rust has what we often call a "lightweight" formal method. These are those with simpler types of specification and/or more automated use. They tend to be quite specialized since that improves automation. The limited properties it proves are why it's so much easier to use than the general methods.

Also note that the problems the borrow checker handles are really hard to do safely in general without overhead. They're hard to test for and debug, too. So, the use of a limited logic with automation just for that makes sense. It's why the other tools for C code were developed, too. Before that, people were using things like SPIN model checker for such things. Again, that looks like overkill to get just a few safety properties vs Rust's built-in method that's simpler.

This has been my experience with Rust.

When I try to learn a new language, I typically want to: (a) read a lot of code people have written in that language and (b) implement algorithms that I understand well, while keeping in an idiomatic style.

When I tried to do this with Rust, I was shocked by how difficult it was to implement certain algorithms (specifically, operations on Linked Lists and Graphs). Maybe I'd do better if I chose a small project to work on, but it disturbs me to know that such elementary problems are so difficult to solve.

The difficulty of writing self-referential data structures in Rust arises on HN often. Every time, the answer is, broadly, the same:

- It is certainly difficult

- Strategies and approaches from low-level languages which are at least cosmetically similar will probably be unavailing

- In some (many?) cases, crates (Rental, Petgraph, Spade) exist that already implement them. Their design can be studied

- There's an entire book (http://cglab.ca/~abeinges/blah/too-many-lists/book/) devoted to writing linked lists in Rust. It's highly informative

Without wishing to explicitly criticise your approach to learning Rust, I'll note that for the vast majority of programmers, it's likely to be frustrating for quite a while.

Worth noting: Many of the examples in that book that required unstable/nightly at the time, now work on stable Rust.

It is really not difficult if you go the petgraph way. Just use a vector and indices into it instead of references.

That's sort of depressing. "Just make your own virtual memory space to get around Rust's PITA memory management" sounds like giving up.

If you don't want to manage memory, why are you using any systems language? Python, JS, Go, and any number of other languages will be much kinder to you.

What I meant to say (hence the downvotes...) is that Rust's "borrow checker" is enough of a nuisance that this graph library replaced memory addresses, i.e. pointers, with indexes into an array, effectively creating its own virtual address space.

See [0] for example.

0: https://doc.rust-lang.org/src/alloc/linked_list.rs.html#46-5...

Reply on news.ycombinator.com