4 ms·

What's a frequently encountered case for such cyclic loops? Without details I'm drawn to trying to break the cycle, either by promoting the shared state to a c

What's a frequently encountered case for such cyclic loops? Without details I'm drawn to trying to break the cycle, either by promoting the shared state to a container object for the set, or by breaking it out into it's own object that multiple things can point at.

solomonb 3y ago
ASTs
- lifthrasiir 3y ago
  ASTs are one of "nicely behaving" data structures. It is like a archetype of abstract data types pervasive in functional programming languages.
- mjevans 3y ago
  An Abstract Syntax Tree / or Double-Linked List both qualify, but they're also a lower level implementation detail than I'd expect to frequently interact with in a reference safety focused language. I've still been meaning to write something in / learn Rust's ways of thinking; is there not an intended replacement for these data structures? Or do they expect it all to go under Unsafe?
  - littlestymaar 3y ago
    > is there not an intended replacement for these data structures? Or do they expect it all to go under Unsafe? For linked-lists, there's one in std and the majority of people should never have to write their own as it's error prone and requires unsafe. For graph use-case then you can either use ECS, arena, ref counting or unsafe, but you're probably better off using/developing a dedicated crate that optimizes it and abstract it away behind an easy to use (and safe) interface.
    - lumost 3y ago
      The one in std uses unsafe. My main concern with learning rust is that you can spend ages trying to learn “the right way” of doing things in rust, when the right way really is to use unsafe.
      - littlestymaar 3y ago
        No, the right way is to use unsafe primitives that have been tested, audited or even formally proven (like the ones in std). Sometimes such a primitive doesn't exist and you should use unsafe yourself, but then you're the one supposed to make sure that your code is in fact sound. If you keep unsafe for small portions of the code you can reason about and extensively test so Miri gives you a good level of confidence, then it's fine to use unsafe. But it's the more expensive option, not the default.
- SkiFire13 3y ago
  An abstract syntax tree can't have cycles by definition.
  - foldr 3y ago
    Technically true, but sometimes you want parent pointers. You then have a more general graph in the underlying representation, but it still represents a tree structure.
    - lumost 3y ago
      Same shows up in Postgres Query* struct for SQL. Copying memory between parser, planner, execution would be too expensive in large queries - so instead you have an arena allocated representation.
- mordae 3y ago
  You usually solve this by using a traversal helper that keeps the stack and next/prev for you without storing them inside the AST explicitly.
rurban 3y ago
a parent field. a doubly linked list
- littlestymaar 3y ago
  Doubly-linked list is something you have almost no reason to ever write. Parent field is something where you have a clear hierarchy (it's not really “cyclic”, so it's the perfect use-case for weak references). When coming from a managed-memory language, this obviously requires some conceptual effort to understand why this is a problem at all and how to deal with it, but when compared to C or C++, the situation is much better in Rust.
  - jacobgorm 3y ago
    Also, a parent field is something you should be able to infer, e.g, keep a stack of parents as you traverse down a search tree following the child pointers, instead of storing parent pointers in the tree nodes.
    - akoboldfrying 3y ago
      That's assuming you traverse the tree down from the root each time. Often you do, but there are cases where you don't -- e.g., if your goal is to determine the lowest common ancestor of two given nodes.
- tialaramex 3y ago
  Your parent said "frequently encountered" and while it's probably true that doubly linked lists may be "frequently encountered" in some people's code they're usually a bad idea and "don't use a list here" is often the right fix, not "conjure a way to make that safe in Rust". It's very noticeable how often people who "need" a linked list actually only wanted a queue (thus Rust's VecDeque) or even a growable array (ie Vec). Aria has a long list of excuses people offer for their linked lists, as well as her discussion of the time before Rust 1.0 when she sent lots of Rust's standard library collections to that farm up-state but wasn't able to send LinkedList. https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/
oconnor663 3y ago
I think a game is a good example, or anything that's kind of like a game in that it's modeling a world that's changing over time. Objects come and go, and they "target" each other or "require" each other or whatever sort of relationships the program wants to express. Those relationships end up forming a graph that might contain cycles. I just put up a blog post about this actually :) https://jacko.io/object_soup.html https://jacko.io/object_soup.html > promoting the shared state to a container object for the set Yeah I think that's a good way to describe these "ECS-ish" patterns.

solomonb 3y ago

ASTs

lifthrasiir 3y ago
ASTs are one of "nicely behaving" data structures. It is like a archetype of abstract data types pervasive in functional programming languages.
mjevans 3y ago
An Abstract Syntax Tree / or Double-Linked List both qualify, but they're also a lower level implementation detail than I'd expect to frequently interact with in a reference safety focused language. I've still been meaning to write something in / learn Rust's ways of thinking; is there not an intended replacement for these data structures? Or do they expect it all to go under Unsafe?
- littlestymaar 3y ago
  > is there not an intended replacement for these data structures? Or do they expect it all to go under Unsafe? For linked-lists, there's one in std and the majority of people should never have to write their own as it's error prone and requires unsafe. For graph use-case then you can either use ECS, arena, ref counting or unsafe, but you're probably better off using/developing a dedicated crate that optimizes it and abstract it away behind an easy to use (and safe) interface.
  - lumost 3y ago
    The one in std uses unsafe. My main concern with learning rust is that you can spend ages trying to learn “the right way” of doing things in rust, when the right way really is to use unsafe.
    - littlestymaar 3y ago
      No, the right way is to use unsafe primitives that have been tested, audited or even formally proven (like the ones in std). Sometimes such a primitive doesn't exist and you should use unsafe yourself, but then you're the one supposed to make sure that your code is in fact sound. If you keep unsafe for small portions of the code you can reason about and extensively test so Miri gives you a good level of confidence, then it's fine to use unsafe. But it's the more expensive option, not the default.
SkiFire13 3y ago
An abstract syntax tree can't have cycles by definition.
- foldr 3y ago
  Technically true, but sometimes you want parent pointers. You then have a more general graph in the underlying representation, but it still represents a tree structure.
  - lumost 3y ago
    Same shows up in Postgres Query* struct for SQL. Copying memory between parser, planner, execution would be too expensive in large queries - so instead you have an arena allocated representation.
mordae 3y ago
You usually solve this by using a traversal helper that keeps the stack and next/prev for you without storing them inside the AST explicitly.

rurban 3y ago

a parent field. a doubly linked list

littlestymaar 3y ago
Doubly-linked list is something you have almost no reason to ever write. Parent field is something where you have a clear hierarchy (it's not really “cyclic”, so it's the perfect use-case for weak references). When coming from a managed-memory language, this obviously requires some conceptual effort to understand why this is a problem at all and how to deal with it, but when compared to C or C++, the situation is much better in Rust.
- jacobgorm 3y ago
  Also, a parent field is something you should be able to infer, e.g, keep a stack of parents as you traverse down a search tree following the child pointers, instead of storing parent pointers in the tree nodes.
  - akoboldfrying 3y ago
    That's assuming you traverse the tree down from the root each time. Often you do, but there are cases where you don't -- e.g., if your goal is to determine the lowest common ancestor of two given nodes.
tialaramex 3y ago
Your parent said "frequently encountered" and while it's probably true that doubly linked lists may be "frequently encountered" in some people's code they're usually a bad idea and "don't use a list here" is often the right fix, not "conjure a way to make that safe in Rust". It's very noticeable how often people who "need" a linked list actually only wanted a queue (thus Rust's VecDeque) or even a growable array (ie Vec). Aria has a long list of excuses people offer for their linked lists, as well as her discussion of the time before Rust 1.0 when she sent lots of Rust's standard library collections to that farm up-state but wasn't able to send LinkedList. https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/

oconnor663 3y ago

I think a game is a good example, or anything that's kind of like a game in that it's modeling a world that's changing over time. Objects come and go, and they "target" each other or "require" each other or whatever sort of relationships the program wants to express. Those relationships end up forming a graph that might contain cycles. I just put up a blog post about this actually :) https://jacko.io/object_soup.html https://jacko.io/object_soup.html > promoting the shared state to a container object for the set Yeah I think that's a good way to describe these "ECS-ish" patterns.