4 ms·

The linked list debate should really be improved. From a practical perspective there are many reasons why one may wish to model a cyclic, linked datastructure.

by lumost 5y ago

The linked list debate should really be improved. From a practical perspective there are many reasons why one may wish to model a cyclic, linked datastructure. Simple examples: You have a social networking site that you are prototyping. You choose to start your data model with a simple Person struct which contains a list of Person called friends. You have an e-commerce site and choose a data model which has a User struct which contains a Cart reference, and a Cart struct containing a User reference for its owning user. You have any problem which involves a graph data-structure. In Rust the best way to work around these issues is to have explicit lookup's by id rather than direct traversable references, or use unsafe. There are no other mechanisms. It's a missing feature that really should be highlighted early in the docs or even as a compiler error such as "cyclic ownership detected in Struct X -> References Y -> References Z in main.rs#128 consider removing the cycle or using Rc, Arena, or unsafe allocations" As it stands if you create a reference cycle in rust you'll get a ton of compiler errors that force you to learn the rest of the ownership rules just to find out that this is something you can never do.

dystroy 5y ago
What I meant in this article is that designing the ways to deal with graph-like structures should be done after the ownership model has been understood. If you start your first program directly on this kind of problem, you'll be only fighting the borrow checker and not really enjoying Rust. I should probably have taken my own experience with broot rather than the linked list example (which hurts many fans of its theoretical beauty).
nauticacom 5y ago
I don't enjoy writing Rust but its perspective on this is at least internally consistent. What are the alternatives for managing cyclic, linked data structures in other languages? In languages with manual memory management you can do it, but it's incredibly easy to mess up. You either have to maintain the entire mental model of who owns what data and what data has been initialized in your head or write it down and risk that becoming out of date. In languages with a GC, the implementors have assumed this complexity for you. Depending on what style of GC your language uses the exact strategy will be different, but on a GC is a comparatively complex piece of code, especially one which handles reference cycles well like we're talking about here. Either way, the complexity is there somewhere. If you manage memory yourself, you deal with the complexity yourself in a hard-to-debug way. If you can accept the tradeoffs of a GC, then the complexity is abstracted behind the GC. Because Rust is designed for use-cases where you can't accept the tradeoffs of a GC, it has to surface that inherent complexity somewhere. It decides to surface it with ownership semantics, which at least make the rules you're following in manual languages explicit and (largely) unbreakable. Yeah it's complex, but the underlying problem is complex. I can use GC languages, so I do, but you'd be no better off in C.
- lumost 5y ago
  The challenge is that rust is not explicit about what it can't do. There are GCs for rust that don't really work, and the borrow checker disallows reference cycles. The rust docs try to pretend this is never a problem and that people writing such structures are doing it wrong which is imho a problem.
  - dystroy 5y ago
    You might be confusing mean goal and end goal. Nobody needs to write a linked list, except when interviewing. What you need (a feature, a performance improvement, etc.) is usually better served with other structures, especially in languages which don't heavily favor heap allocations (in a GC based language you've already paid the allocation cost when creating the object anyway). I think there's now some evidence that Rust prevents developers neither from making efficient applications nor from efficiently making them.
    - lumost 5y ago
      This is certainly valid for some number of uses, however there isn't a good way of mapping all reasonable uses of linked structures to unlinked structures except via associative array. There are many linked structures such as an Linked hashmap or LRU cache that can’t be efficiently represented in safe rust. There are engineers who need to code and use such structures outside of an interview context, these engineers must use unsafe to code valid programs. I honestly wouldn’t mind if the docs were simply upfront on the need to use unsafe and the insufficiency of any alternative for these situations. Long ago it was thought that users would simply use something along the lines of GC<Type> to handle these situations, but none of the rust GC projects materialized.
- ridiculous_fish 5y ago
  I struggle with even non-cyclic linked data structures in Rust. For example consider a binary tree: struct Node { value: usize, left: Option<Box<Node>>, right: Option<Box<Node>>, } I want to write a function to increment the value of every Node. This is trivial with recursion, but that risks blowing the stack. So I try an iterative version using an explicit stack, but the borrow checker doesn't understand explicit stacks, only the C stack, so it rejects my code. There's no inherent underlying complexity to transforming a recursive function to an iterative one, yet it is legitimately hard in Rust.
Zababa 5y ago
Rust has weak pointers, couldn't they be used to avoid that? https://doc.rust-lang.org/std/rc/struct.Weak.html https://doc.rust-lang.org/std/rc/struct.Weak.html

by lumost 5y ago

dystroy 5y ago

What I meant in this article is that designing the ways to deal with graph-like structures should be done after the ownership model has been understood. If you start your first program directly on this kind of problem, you'll be only fighting the borrow checker and not really enjoying Rust. I should probably have taken my own experience with broot rather than the linked list example (which hurts many fans of its theoretical beauty).

nauticacom 5y ago

I don't enjoy writing Rust but its perspective on this is at least internally consistent. What are the alternatives for managing cyclic, linked data structures in other languages? In languages with manual memory management you can do it, but it's incredibly easy to mess up. You either have to maintain the entire mental model of who owns what data and what data has been initialized in your head or write it down and risk that becoming out of date. In languages with a GC, the implementors have assumed this complexity for you. Depending on what style of GC your language uses the exact strategy will be different, but on a GC is a comparatively complex piece of code, especially one which handles reference cycles well like we're talking about here. Either way, the complexity is there somewhere. If you manage memory yourself, you deal with the complexity yourself in a hard-to-debug way. If you can accept the tradeoffs of a GC, then the complexity is abstracted behind the GC. Because Rust is designed for use-cases where you can't accept the tradeoffs of a GC, it has to surface that inherent complexity somewhere. It decides to surface it with ownership semantics, which at least make the rules you're following in manual languages explicit and (largely) unbreakable. Yeah it's complex, but the underlying problem is complex. I can use GC languages, so I do, but you'd be no better off in C.

lumost 5y ago
The challenge is that rust is not explicit about what it can't do. There are GCs for rust that don't really work, and the borrow checker disallows reference cycles. The rust docs try to pretend this is never a problem and that people writing such structures are doing it wrong which is imho a problem.
- dystroy 5y ago
  You might be confusing mean goal and end goal. Nobody needs to write a linked list, except when interviewing. What you need (a feature, a performance improvement, etc.) is usually better served with other structures, especially in languages which don't heavily favor heap allocations (in a GC based language you've already paid the allocation cost when creating the object anyway). I think there's now some evidence that Rust prevents developers neither from making efficient applications nor from efficiently making them.
  - lumost 5y ago
    This is certainly valid for some number of uses, however there isn't a good way of mapping all reasonable uses of linked structures to unlinked structures except via associative array. There are many linked structures such as an Linked hashmap or LRU cache that can’t be efficiently represented in safe rust. There are engineers who need to code and use such structures outside of an interview context, these engineers must use unsafe to code valid programs. I honestly wouldn’t mind if the docs were simply upfront on the need to use unsafe and the insufficiency of any alternative for these situations. Long ago it was thought that users would simply use something along the lines of GC<Type> to handle these situations, but none of the rust GC projects materialized.
ridiculous_fish 5y ago
I struggle with even non-cyclic linked data structures in Rust. For example consider a binary tree: struct Node { value: usize, left: Option<Box<Node>>, right: Option<Box<Node>>, } I want to write a function to increment the value of every Node. This is trivial with recursion, but that risks blowing the stack. So I try an iterative version using an explicit stack, but the borrow checker doesn't understand explicit stacks, only the C stack, so it rejects my code. There's no inherent underlying complexity to transforming a recursive function to an iterative one, yet it is legitimately hard in Rust.

Zababa 5y ago

Rust has weak pointers, couldn't they be used to avoid that? https://doc.rust-lang.org/std/rc/struct.Weak.html https://doc.rust-lang.org/std/rc/struct.Weak.html