5 ms·

I've struggled with Rust just a couple of times, nothing serious, so I'm not an experienced Rustacean by any means. Question: Ownership system obviously impos

by kovrik 9y ago

I've struggled with Rust just a couple of times, nothing serious, so I'm not an experienced Rustacean by any means. Question: Ownership system obviously imposes some limitations, but gives safety in return. Are there any data-structures or algorithms or something that you simply cannot implement in Rust without using unsafe?

justinpombrio 9y ago
> Are there any data-structures or algorithms or something that you simply cannot implement in Rust without using unsafe? No. If you wrap every piece of data in your whole program in RefCell, the borrow checker will leave you alone, and it will be like programming in most other languages. (There are some minor differences, like the fact that your program will be refcounted rather than garbage collected, which doesn't deal with cyclic references, but let's ignore those.) Alternatively, you can wrap your whole program in "unsafe{...}", and use raw pointers everywhere, and it will be similar to programming in C. EDIT: My comment is trying to give a general understanding that will hold most of the time. See the other comments for fun edge cases :-).
- kovrik 9y ago
  But if you use RefCell, then you won't get any useful compile-time checks, will you? In other words: if you have Rust _without_ unsafe and without RefCell (and similar stuff), will you still be able to implement anything in it and keep compile-time checks and other benefits of ownership system?
  - justinpombrio 9y ago
    > But if you use RefCell, then you won't get any useful compile-time checks, will you? If you use RefCell, then the compile-time checks won't be necessary. For example, in Java there are no compile-time checks: everything is just garbage-collected at runtime. Likewise, RefCell is lightweight garbage-collection (modulo cyclic references). > In other words: if you have Rust _without_ unsafe and without RefCell (and similar stuff), will you still be able to implement anything in it and keep compile-time checks and other benefits of ownership system? Ah, in that case there are a lot of things you can't implement: Strings, doubly-linked lists (which is the point of this article), trees with backpointers, graphs, vectors, etc. Fortunately, you rarely need to: if you need a data structure, it's probably already implemented in Rust. The standard library has most common data structures, and there are often crates for less common ones. If you do need to write unsafe Rust, it's about as scary as C. I've written a reasonable amount of Rust code, and only ran into one situation where I (think) I need unsafe code.
    - steveklabnik 9y ago
      You’re confusing Rc and RefCell, RefCell is “borrow checking at runtime”, Rc is “lightweight garbage collection”.
      - justinpombrio 9y ago
        Aaagh, yes! I meant Rc everywhere :-(.
pcwalton 9y ago
In theory, no, because safe Rust is enough to implement the C VM. You could always (again, theoretically) implement whatever data structure you want on top of a giant Vec<u8> heap of memory, asm.js style. Of course, this isn't something you would want to do in practice!
gnarbarian 9y ago
Technically no, as long as safe rust is Turing Complete and the data structures you're talking about aren't defined by unsafe behavior. Practically, I have no idea.
ridiculous_fish 9y ago
XOR linked list? https://en.wikipedia.org/wiki/XOR_linked_list https://en.wikipedia.org/wiki/XOR_linked_list
- justinpombrio 9y ago
  To be fair, you can't implement that in most languages.
cwzwarich 9y ago
You can't implement many concurrent data structures that rely on things like acquire/release consistency or single-copy atomicity in safe Rust.
Const-me 9y ago
Theoretically no, because Turing complete. Practically yes, there’re many well-known algorithms processing linked lists, trees and graphs. These algorithms are used everywhere in practice, processing syntax/expression/DOM/filesystem trees, MRU/LRU lists, objects/dependencies/network/pathfinding graphs. Safe rust implementation of these structures wastes too much resources.
stestagg 9y ago
Something that people don't seem to know how to do (despite several attempts by known rust developers) are zero-copy streaming iterators. Tracking the lifetimes of references in this way gets really hard really quickly, and rust isn't currently able to work it out

by kovrik 9y ago

justinpombrio 9y ago

> Are there any data-structures or algorithms or something that you simply cannot implement in Rust without using unsafe? No. If you wrap every piece of data in your whole program in RefCell, the borrow checker will leave you alone, and it will be like programming in most other languages. (There are some minor differences, like the fact that your program will be refcounted rather than garbage collected, which doesn't deal with cyclic references, but let's ignore those.) Alternatively, you can wrap your whole program in "unsafe{...}", and use raw pointers everywhere, and it will be similar to programming in C. EDIT: My comment is trying to give a general understanding that will hold most of the time. See the other comments for fun edge cases :-).

kovrik 9y ago
But if you use RefCell, then you won't get any useful compile-time checks, will you? In other words: if you have Rust _without_ unsafe and without RefCell (and similar stuff), will you still be able to implement anything in it and keep compile-time checks and other benefits of ownership system?
- justinpombrio 9y ago
  > But if you use RefCell, then you won't get any useful compile-time checks, will you? If you use RefCell, then the compile-time checks won't be necessary. For example, in Java there are no compile-time checks: everything is just garbage-collected at runtime. Likewise, RefCell is lightweight garbage-collection (modulo cyclic references). > In other words: if you have Rust _without_ unsafe and without RefCell (and similar stuff), will you still be able to implement anything in it and keep compile-time checks and other benefits of ownership system? Ah, in that case there are a lot of things you can't implement: Strings, doubly-linked lists (which is the point of this article), trees with backpointers, graphs, vectors, etc. Fortunately, you rarely need to: if you need a data structure, it's probably already implemented in Rust. The standard library has most common data structures, and there are often crates for less common ones. If you do need to write unsafe Rust, it's about as scary as C. I've written a reasonable amount of Rust code, and only ran into one situation where I (think) I need unsafe code.
  - steveklabnik 9y ago
    You’re confusing Rc and RefCell, RefCell is “borrow checking at runtime”, Rc is “lightweight garbage collection”.
    - justinpombrio 9y ago
      Aaagh, yes! I meant Rc everywhere :-(.

pcwalton 9y ago

In theory, no, because safe Rust is enough to implement the C VM. You could always (again, theoretically) implement whatever data structure you want on top of a giant Vec<u8> heap of memory, asm.js style. Of course, this isn't something you would want to do in practice!

gnarbarian 9y ago

Technically no, as long as safe rust is Turing Complete and the data structures you're talking about aren't defined by unsafe behavior. Practically, I have no idea.

ridiculous_fish 9y ago

XOR linked list? https://en.wikipedia.org/wiki/XOR_linked_list https://en.wikipedia.org/wiki/XOR_linked_list

justinpombrio 9y ago
To be fair, you can't implement that in most languages.

cwzwarich 9y ago

You can't implement many concurrent data structures that rely on things like acquire/release consistency or single-copy atomicity in safe Rust.

Const-me 9y ago

Theoretically no, because Turing complete. Practically yes, there’re many well-known algorithms processing linked lists, trees and graphs. These algorithms are used everywhere in practice, processing syntax/expression/DOM/filesystem trees, MRU/LRU lists, objects/dependencies/network/pathfinding graphs. Safe rust implementation of these structures wastes too much resources.

stestagg 9y ago

Something that people don't seem to know how to do (despite several attempts by known rust developers) are zero-copy streaming iterators. Tracking the lifetimes of references in this way gets really hard really quickly, and rust isn't currently able to work it out