1. 28

  2. 8

    Wouldn’t this be pretty easy to do without mutability?

      1. 1

        Which of those list implementations is immutable?

        I don’t remember reading the PSA about how bad lists are the first time I went through this. To me it stinks of rationalization. There’s a large space of possible data structures out there, and Rust’s borrow checking can’t represent a big chunk of them – including such examples as binary trees with parent pointers. Are they all things we shouldn’t be teaching students of programming?

        1. 19

          The decision procedure seems straight-forward to me:

          1. If you want a tree structure with parent pointers in Rust, see if someone has written a generic data structure that will suit your needs. If not, continue.
          2. Implement the tree structure yourself. If you need to express shared ownership, then use a reference counted type. If this is too annoying or has too much performance overhead, continue.
          3. Use raw pointers and unsafe to express your parent pointers, just like you’d do in C. Spend the time to make sure you’ve gotten it right and expose a safe interface at a module boundary. Enjoy the benefits of using safe code elsewhere. If this doesn’t work for whatever reason, continue.
          4. Compile time borrow checking might not be suitable for your use case. Don’t use Rust.

          I don’t know exactly what would cause someone to go from 3 to 4, although I imagine there are legitimate reasons. Annoyance could be one. I don’t really understand that one too much myself though, unless you for some reason can’t find a way to hide unsafe behind a safe API (which you absolutely should be able to do with a binary tree).

          Maybe the future holds more sophisticated borrow checking. But this is what we have for now. If you think expounding on trade offs is equivalent to “stinking of rationalization,” then so be it. But it seems entirely appropriate to me.

          There is of course a separate issue where many Rust programmers will suggest that one should not implement these data structures themselves. My “rationalization” for this is a conflation of target audience. If you’re just wanting to get a taste for Rust and you want to try it out by implementing a doubly linked list, then people are going to rightfully steer you away from that because it might not be the best way to dip your toes in. If, however, you have a specific use case and know that’s what you need and existing generic data structures aren’t suitable for legitimate reasons, then receiving the aforementioned advice sounds downright patronizing. But that doesn’t make it wrong in every case.

          Common questions have common answers, and not everyone is discerning enough to know when the common answer is inappropriate. We shouldn’t hold that against them. Use it as an opportunity to educate (or, sometimes, delightfully, be educated, because everyone is wrong once in a while).

          1. 5

            I’ll add to your excellent analysis that, at 4, one might just use an external tool to verify the unsafe Rust. There’s quite a few tools, esp for C, that can check that either partly or totally. They require their own expertise. They can be hard to use or have serious limitations. One must also be careful about mismatches between meaning of the Rust code and the “equivalent” version. However, they might be a better option than no mechanical checking on unsafe part or no use of Rust at all in a given project.

            “Maybe the future holds more sophisticated borrow checking.”

            Definitely. The CompSci folks are working on building more flexible models all the time. Most I saw were building on things like linear types rather than affine or using functional languages. There’s at least potential if these people start doing similar things to Rust’s model. Even if main language doesn’t adopt it, an extension for an unsafe piece of Rust or something Rust can call with FFI would still be beneficial.

            1. 2

              Thanks, I hadn’t really considered using unsafe, under the assumption that if I need to use unsafe I might as well use C. But it sounds like there are benefits here. I’ll dig deeper into this.

              I think “this is a limitation of borrow checking” is a perfectly great statement. Where it edges into rationalization is when it says “you shouldn’t need this” as the above link does. Or “if you need this you’re stupid or doing something wrong”, as the above link kinda implies. I see this in the Go community as well, where conversation often jumps from “we don’t know how to do generics well” to “you shouldn’t need generics”. This isn’t from the leaders, but it does get said a lot. (As an ex-Lisp hand I’m reminded of all the times we said “you shouldn’t need this” to noobs, and how it affected Lisp’s adoption.)

              The worldview I’m approaching Rust from is to determine if it can replace C or Java (or other system languages that expose pointers) to the point where someone can go through their career without needing to use those older languages (modulo interop scenarios). That makes me care more about learning situations even if they are rarely relevant in “the real world”.

              1. 6

                Sure. It’s a classic hedge. If you’re writing material and you want to address common mistakes, then these sorts of “don’t do these things” rules make sense, especially if they are prone to overuse. For example, if a lot of beginners are picking up Rust and struggling because they’re trying to write linked lists, then we can either:

                1. Make the process of writing linked lists easier.
                2. Nudge them in another direction.

                The presumption being here that those of us who aren’t beginners in Rust will know when to break these rules. We could probably be more explicit about this in more areas, but it’s hard to be 100% precise all of the time. And you certainly can’t control what others say either. There’s likely a phenomenon at play here too, one that I’ve heard described as “there is nothing like the zeal of the newly converted.” :-)

                Thanks, I hadn’t really considered using unsafe, under the assumption that if I need to use unsafe I might as well use C. But it sounds like there are benefits here. I’ll dig deeper into this.

                To clarify here, because I think this is important, but a key part of Rust’s value proposition isn’t necessarily that you never need to use unsafe, but rather, when you do, it’s usually possible to hide it behind a safe abstraction. That means that when a memory violation bug occurs, you know exactly where to look.

                Of course, that isn’t the complete story. If you legitimately ended up needing to use unsafe in a ton of places, then that would weaken the aforementioned value proposition. The key is striking a balance, and one part of learning Rust is learning when to use unsafe and when not to. It can be tricky, but that’s why a good first approximation is “don’t use unsafe.” :-) The classic uses of unsafe in my experience are:

                1. FFI.
                2. In the implementation of generic data structures that must have as little overhead as possible. These uses are probably the most difficult form of unsafe to get right, partially because of generics. (The nomincon is instructive here.)
                3. Getting around checks like bounds checks, doing unaligned loads/stores, avoiding redundant UTF-8 checks, etc. These are as hard or as easy to get right as in C.
                1. 5

                  The tragic thing here is that that page is awesome from an information content perspective. It’s just a matter of how the parts of the argument are phrased. Compare:

                  “Here’s how you do linked lists in Rust. Be warned, it’s going to be a little klunky compared to other languages, but fortunately you’ll rarely need it in the real world, and there’s often better alternatives.”


                  “Linked lists are awful, but you’re twisting my arm so here’s how you do them in Rust.”

                  What’s nice about the first approach is that it shortcuts the whole cycle of mutual accusations of defensiveness that often happen in these situations. Because really nobody is being defensive, we’re just wondering internally if the other side is being defensive. I learned programming using linked lists, and if you tell me they suck it doesn’t trigger defensiveness. My identity isn’t wrapped up in using linked lists. What it triggers is skepticism. And it’s totally unnecessary and distracting.

                2. 4

                  There are plenty of benefits to writing Rust instead of C even if you typed every single line of code within an unsafe { } block. Rust has a lot of ergonomic improvements compared to C and C++ (my personal favorite is a type system which supports good algebraic data types).

                  It’s also worth mentioning that the reason the unsafe keyword exists in Rust is precisely because there are lots of useful things you might want to do in a program that will violate the borrow checking rules, and you need some way to sidestep it on occasion. The fact that the keyword is named “unsafe” gives people pause when using it - which is normally good, because you should think carefully about writing code that you know can’t be automatically checked for memory safety - but that doesn’t mean that it’s wrong to write a Rust program that uses unsafe blocks, even if you are a beginner.

                  If I want an doubly-linked list in Rust, I can in 12 lines of code do:

                   struct List<T> {
                         item: T,
                        next: Option<*mut List<T>>,
                        prev: Option<*mut List<T>>
                    fn main() {
                        let mut first: List<i32> = List { item: 1, next: None, prev: None };
                        let mut second: List<i32> = List { item: 5000, next: None, prev: Some(&mut first)
                        first.next = Some(&mut second);
                        println!("first item: {}", first.item);
                        println!("second item: {}", unsafe {(*first.next.unwrap()).item});
                        println!("first item again: {}", unsafe {(*second.prev.unwrap()).item});

                  and this will compile with no errors and have exactly the same behavior as the equivalent C program. It’s unsafe of course - and the fact that you have to use unsafe blocks is a good sign that you should think about whether this is a good way to write this program, or at least that you should be very, very careful when writing it. But you can do it. Even if you are a beginner to Rust.

                  1. 2

                    Thanks, I hadn’t really considered using unsafe, under the assumption that if I need to use unsafe I might as well use C. But it sounds like there are benefits here. I’ll dig deeper into this.

                    It’s a long-time practice in safe, systems languages to support escape hatches to do what the safety mechanisms won’t allow to be done. This included writing OS kernels in Pascal, PL/S, Oberon, and Ada. The developers of such languages realized that most of an app doesn’t have to be done unsafely by default. So, they’re usually safe by default. Then, if you need unsafety, you can put it in a specific module that turns off one or more safety features just for that module. Compiler still automatically does static or dynamic checks for everything else. This focuses the mind on the most dangerous modules when looking for low-level problems. Finally, the common practice was to wrap the unsafe code in function calls that (a) may do input validation to ensure the unsafe code receives sane input and/or (b) had its own checkable rules for being called safely in rest of the safe code. Some went further to have formal specifications for correct use of all code with the unsafe code’s logical correctness checked there with language-level correctness checked by eye and code-analysis tools.

                    So, there’s the big picture of how this has been done going back to the 1960’s with Burroughs doing an ALGOL CPU/OS combo. It consistently worked, too, if you look at what caused most crashes and security bulletins. At one point, when hardware was expensive and slow, one source I had said Burroughs even offered to turn off the safety checks for their customers for performance boost. The customers said no: didn’t want the headaches. Software is a lot more complex today on much faster machines. Might as well keep the good practice. :)

                  2. 2

                    I think that’s totally reasonable. In the future, programmers might figure out how stuff that is only doing in unsafe Rust can actually be done in safe Rust. I don’t think the full implications of borrow checkers has been worked out. As it’s better understood, some of these data structures will be revisited. Rust is still useful in the interim time.

            2. 1

              I largely agree. I’m glad the author got it working in Go. I think Swift is another good option, worth a mention; this GitHub repo seems to lay out pretty clearly how to write a doubly-linked list without creating a reference cycle. Avoiding the GC seems quite doable.

              1. 1

                Why not try to implement a data structure that might be better suited to the stye of development? Fingertrees maybe? https://github.com/freebroccolo/fingertree.rs