5 ms·

Which is where the 'get out of jail' card in the form of 'unsafe' code is useful. You can always fall back to not having those guarantees checked if you're writ

by rkangel 10y ago

Which is where the 'get out of jail' card in the form of 'unsafe' code is useful. You can always fall back to not having those guarantees checked if you're writing core, low level, well tested code. You can then ensure the right guarantees are made by typing at the interface, and ensure the code is used correctly. This is why writing data structures in Rust is considered an 'advanced' topic.

bsaul 10y ago
This last sentence sounds a bit worrying. Writing data structures such as graph is just as common as writing if then else... if this is an advanced topic, then maybe an intermediate library providing common patterns for building elaborate structure would be welcome ( that's usually what stdlib types are about, but with the borrow checker, maybe those aren't enough).
- rkangel 10y ago
  In languages like C it is quite common. In languages like Rust where there is a greater power of abstraction, it is less common as there exist versions of structures that wouldn't implementable in a re-usable way in C. Think of some examples you've had to implement in the past - you'll likely find implementations either in the stdlib or in cargo. Yes, you will on occasion need to implement your own datastructure to meet a particular need. If you do that you're going to have to sit down and think about it, work out the guarantees, ensure that it doesn't leak etc.. All the things you'd have to do in C, but you have to do it rarely. There are some intermediate libraries (things like 'Cell') that allow for writing structures that wouldn't otherwise be possible.
- burntsushi 10y ago
  For graphs, you can use petgraph: https://docs.rs/petgraph https://docs.rs/petgraph
- plinkplonk 10y ago
  I've been wrestling with this very concept. I often find myself writing custom variants of datastructures and relatively uncommon datastructures, and a language that makes this difficult isn't very motivating to get into. What is really needed is good documentation on this specific aspect. If on the hand if the messaging is "if you find yourself reaching for unsafe, it is likely you need to rethink your code's design" and then also "common datastructures are hard to write without unsafe" there is some slight dissonance there (imho, ime). I'm not looking for 'blessed libraries' of prebuilt datastructures. I want to code up datastructures (e.g quadtrees, graphs etc), and good guidance on when exactly unsafe is the only way to get this done. I don't really want to pause in the middle of a project and have to spend serious amounts of time coding up a (custom/unusual) datastructure just because there is no way without using unsafe (etc). Right now there doesn't seem to be good guidance on this aspect (writing datastructures in Rust) which is presented as an "advanced topic" and "the wrong way / the hard way" to learn Rust. (there is the linked list book, which serves as a starting point, and using Cell etc seems to work - I'm still struggling - which is fine, that is how people learn.) PS: None of the above is really a criticism of Rust the language or the team. I think Rust is great, I'm just a bit frustrated with the 'build common datastructures being "advanced" ' aspect, but in the end it is probably just that I haven't been able to wrap my head around Rust yet
  - kernelbandwidth 10y ago
    In the same way that we're really only starting to learn patterns that make good use of affine typing, I think this will get easier as we discover better (for Rust) design patterns. Which is basically what you're asking for; I think we're still in a mixture of discovering and documenting said patterns because some standard approaches don't work the same. So far, it seems to me that a lot of 'textbook' data structures require unsafe, at least to translate in a mostly 1:1 manner. I think more novel patterns will emerge around non-1:1 translations in safe code, which may push at least some data structures out of the 'advanced Rust' territory. I recently ran into this myself while implementing an order statistic red-black tree in (safe) Rust, which shouldn't be particularly complicated, but has been a good bit more verbose than C++ or Java would have been, primarily because I did a lot of manual bookkeeping to avoid unsafe. Still, it was enlightening and I very much enjoy using Rust.
  - kazagistar 10y ago
    One of the better Rust tutorials shows how to handle a number of different strategies for data structures, including using unsafe: "Learning Rust With Entirely Too Many Linked Lists". http://cglab.ca/~abeinges/blah/too-many-lists/book/ http://cglab.ca/~abeinges/blah/too-many-lists/book/
  - Manishearth 10y ago
    I think the messaging is like this because folks approach Rust and often try to write Rust code as if it were C. You can do this in C++; you can't do this in Rust. unsafe is highly discouraged, but designing the innards of abstractions like datastructures is one of the places where you basically need it. Be aware that good generic datastructures are just as hard in C++. See https://news.ycombinator.com/item?id=13580418 https://news.ycombinator.com/item?id=13580418 . Naive datastructure implementations often have strict aliasing bugs or mess up on the destruction behavior. Using unsafe to write datastructures in Rust isn't particularly hard; it's just as tricky as it is in C++. Having to use unsafe is annoying, but it's a minor annoyance. The nomicon helps teach how you're supposed to use unsafe.
- wyldfire 10y ago
  > Writing data structures such as graph is just as common as writing if then else... I disagree. For everyone involved -- designing data structures should be a less frequent activity than designing flow control IMO. While I would consider it part of a foundation of one's foray into computer science, it's not a common activity of most programmers. (Note the distinction between these educational/occupational terms.) Most people just don't do this often. The fact that Rust enables very simple composition via crates means that we really can all use petgraph without much indigestion. The risk this enables is that we become dependent on critical packages like this. Hopefully we all got a glimpse of the left-pad awfulness and learned how to avoid the same problems for Rust.
  - steveklabnik 10y ago
    > Hopefully we all got a glimpse of the left-pad awfulness and learned how to avoid the same problems for Rust. Crates.io is never gonna have the left-pad issue, by design. npm also changed their policies after left-pad so it can't happen there again, too.
- jerf 10y ago
  Writing data structures in all languages is an advanced topic, if by "data structures" you mean data structures sufficiently generic and powerful enough to be used by a very wide variety of programmers. Do not be confused by the fact that you were able to bash together a linked-list library in C for some task or other that seemed to work for you; it almost certainly has bugs, suboptimal memory usage if not outright leaks, inefficiencies, and an API that would render it not very popular as a generic library for everyone to use. The reason is that "sufficiently generic and powerful enough to be used by a wide variety of programmers" is intrinsically a very high bar. Under every language you use are some frightfully subtle data structures, and the easier they are to use (i.e., Python dicts), the more frightfully subtle they are under the hood. (Since certain people have developed a knee twitch with the word "generic" lately, let me note that I mean generic in its most, ahem, generic sense, not specifically the programming language research term.)
  - bsaul 10y ago
    "if by "data structures" you mean data structures sufficiently generic and powerful enough to be used by a very wide variety of programmers" Nope, not what i meant. Just a data structure suited to my very specific problem, optimized just for my particular case. That's usually much easier than solving the general problem in a generic manner. And that should be possible to do easily in a programming language.
    - humanrebar 10y ago
      > Just a data structure suited to my very specific problem I think the point is that it's harder to do this properly than it seems like it is, especially in a systems language. I've seen many "working" shared pointers in C++ that only worked if you used them in the way the original authors happened to use them. They wouldn't work if, say, you put a bunch of them in a std::vector. So some of this is about what "works" means to different people.

by rkangel 10y ago

bsaul 10y ago

This last sentence sounds a bit worrying. Writing data structures such as graph is just as common as writing if then else... if this is an advanced topic, then maybe an intermediate library providing common patterns for building elaborate structure would be welcome ( that's usually what stdlib types are about, but with the borrow checker, maybe those aren't enough).

rkangel 10y ago
In languages like C it is quite common. In languages like Rust where there is a greater power of abstraction, it is less common as there exist versions of structures that wouldn't implementable in a re-usable way in C. Think of some examples you've had to implement in the past - you'll likely find implementations either in the stdlib or in cargo. Yes, you will on occasion need to implement your own datastructure to meet a particular need. If you do that you're going to have to sit down and think about it, work out the guarantees, ensure that it doesn't leak etc.. All the things you'd have to do in C, but you have to do it rarely. There are some intermediate libraries (things like 'Cell') that allow for writing structures that wouldn't otherwise be possible.
burntsushi 10y ago
For graphs, you can use petgraph: https://docs.rs/petgraph https://docs.rs/petgraph
plinkplonk 10y ago
I've been wrestling with this very concept. I often find myself writing custom variants of datastructures and relatively uncommon datastructures, and a language that makes this difficult isn't very motivating to get into. What is really needed is good documentation on this specific aspect. If on the hand if the messaging is "if you find yourself reaching for unsafe, it is likely you need to rethink your code's design" and then also "common datastructures are hard to write without unsafe" there is some slight dissonance there (imho, ime). I'm not looking for 'blessed libraries' of prebuilt datastructures. I want to code up datastructures (e.g quadtrees, graphs etc), and good guidance on when exactly unsafe is the only way to get this done. I don't really want to pause in the middle of a project and have to spend serious amounts of time coding up a (custom/unusual) datastructure just because there is no way without using unsafe (etc). Right now there doesn't seem to be good guidance on this aspect (writing datastructures in Rust) which is presented as an "advanced topic" and "the wrong way / the hard way" to learn Rust. (there is the linked list book, which serves as a starting point, and using Cell etc seems to work - I'm still struggling - which is fine, that is how people learn.) PS: None of the above is really a criticism of Rust the language or the team. I think Rust is great, I'm just a bit frustrated with the 'build common datastructures being "advanced" ' aspect, but in the end it is probably just that I haven't been able to wrap my head around Rust yet
- kernelbandwidth 10y ago
  In the same way that we're really only starting to learn patterns that make good use of affine typing, I think this will get easier as we discover better (for Rust) design patterns. Which is basically what you're asking for; I think we're still in a mixture of discovering and documenting said patterns because some standard approaches don't work the same. So far, it seems to me that a lot of 'textbook' data structures require unsafe, at least to translate in a mostly 1:1 manner. I think more novel patterns will emerge around non-1:1 translations in safe code, which may push at least some data structures out of the 'advanced Rust' territory. I recently ran into this myself while implementing an order statistic red-black tree in (safe) Rust, which shouldn't be particularly complicated, but has been a good bit more verbose than C++ or Java would have been, primarily because I did a lot of manual bookkeeping to avoid unsafe. Still, it was enlightening and I very much enjoy using Rust.
- kazagistar 10y ago
  One of the better Rust tutorials shows how to handle a number of different strategies for data structures, including using unsafe: "Learning Rust With Entirely Too Many Linked Lists". http://cglab.ca/~abeinges/blah/too-many-lists/book/ http://cglab.ca/~abeinges/blah/too-many-lists/book/
- Manishearth 10y ago
  I think the messaging is like this because folks approach Rust and often try to write Rust code as if it were C. You can do this in C++; you can't do this in Rust. unsafe is highly discouraged, but designing the innards of abstractions like datastructures is one of the places where you basically need it. Be aware that good generic datastructures are just as hard in C++. See https://news.ycombinator.com/item?id=13580418 https://news.ycombinator.com/item?id=13580418 . Naive datastructure implementations often have strict aliasing bugs or mess up on the destruction behavior. Using unsafe to write datastructures in Rust isn't particularly hard; it's just as tricky as it is in C++. Having to use unsafe is annoying, but it's a minor annoyance. The nomicon helps teach how you're supposed to use unsafe.
wyldfire 10y ago
> Writing data structures such as graph is just as common as writing if then else... I disagree. For everyone involved -- designing data structures should be a less frequent activity than designing flow control IMO. While I would consider it part of a foundation of one's foray into computer science, it's not a common activity of most programmers. (Note the distinction between these educational/occupational terms.) Most people just don't do this often. The fact that Rust enables very simple composition via crates means that we really can all use petgraph without much indigestion. The risk this enables is that we become dependent on critical packages like this. Hopefully we all got a glimpse of the left-pad awfulness and learned how to avoid the same problems for Rust.
- steveklabnik 10y ago
  > Hopefully we all got a glimpse of the left-pad awfulness and learned how to avoid the same problems for Rust. Crates.io is never gonna have the left-pad issue, by design. npm also changed their policies after left-pad so it can't happen there again, too.
jerf 10y ago
Writing data structures in all languages is an advanced topic, if by "data structures" you mean data structures sufficiently generic and powerful enough to be used by a very wide variety of programmers. Do not be confused by the fact that you were able to bash together a linked-list library in C for some task or other that seemed to work for you; it almost certainly has bugs, suboptimal memory usage if not outright leaks, inefficiencies, and an API that would render it not very popular as a generic library for everyone to use. The reason is that "sufficiently generic and powerful enough to be used by a wide variety of programmers" is intrinsically a very high bar. Under every language you use are some frightfully subtle data structures, and the easier they are to use (i.e., Python dicts), the more frightfully subtle they are under the hood. (Since certain people have developed a knee twitch with the word "generic" lately, let me note that I mean generic in its most, ahem, generic sense, not specifically the programming language research term.)
- bsaul 10y ago
  "if by "data structures" you mean data structures sufficiently generic and powerful enough to be used by a very wide variety of programmers" Nope, not what i meant. Just a data structure suited to my very specific problem, optimized just for my particular case. That's usually much easier than solving the general problem in a generic manner. And that should be possible to do easily in a programming language.
  - humanrebar 10y ago
    > Just a data structure suited to my very specific problem I think the point is that it's harder to do this properly than it seems like it is, especially in a systems language. I've seen many "working" shared pointers in C++ that only worked if you used them in the way the original authors happened to use them. They wouldn't work if, say, you put a bunch of them in a std::vector. So some of this is about what "works" means to different people.