3 ms·

> Now suppose we want to add a parent link to every node. Don't. You do not need to. Rust does stop you creating self referential structures (easily) In the

by worik 3y ago

> Now suppose we want to add a parent link to every node. Don't. You do not need to. Rust does stop you creating self referential structures (easily) In the case of a binary tree that is not a problem There might exist some specialised case where there is no more memory to allocate at run time, but in the common case it is more efficient in every respect to use algorithms with your data structures and dispense with back links I have been working on a C program built by a (mostly brilliant) programmer that put back links in every structure (parent links in trees, doubly linked lists) and the waste of resources, in a constrained environment, is frustrating Just don't

pizlonator 3y ago
Some algorithms need the parent or bidirectional pointers. If the language doesn’t let you then the language sucks.
- empath-nirvana 3y ago
  This post shows 3 ways of doing it, including essentially the same way you'd do it in C. And it's exactly as dangerous as doing it in C is, but at least you can isolate that dangerous code to one part of your code base.
  - alexchamberlain 3y ago
    > you can isolate that dangerous code to one part of your code base. This is the whole point for me. There are loads of reasons fundamental data structures want to use behaviour the compile can't prove is sound, but humans can burn time discussing, proving the algorithms and testing the implementation. Then, you ask the compiler to prove all the simple glue stuff on top.
    - hinkley 3y ago
      I suspect there's a type theory here where many cases of parent links essentially represent the exact same problem, and if you solve one, you can restate most/all of the others in this form and then it's proven too. You know that popcount bit counting device that treats a word of memory as a short SIMD instruction using the 32 or 64 bit ALU? I learned recently that compilers can detect that and emit popcount instructions if those are faster on the target architecture. I suspect if you can detect that, you could detect a safe parental reference device and let it pass the checker.
- worik 3y ago
  > Some algorithms need the parent or bidirectional pointers. For trees some, not very good, algorithms require parent pointers
fhood 3y ago
I think it's best to think of this as a good toy example, and not get caught up in the specific utility of a "parent" node.
- worik 3y ago
  It is just a bad example. One of the main points is that there are very few algorithms that require back links that create cycles. Cyclic data structures, rare as they are, are also hard to reason about. Even for garbage collectors! If you have to implement one in Rust (I have) it is a bother, a big hassle. It is a good thing that in the general case when a programmer is implementing back links they are doing the Wrong Thing.
deleted 3y ago
[deleted]

by worik 3y ago

pizlonator 3y ago

Some algorithms need the parent or bidirectional pointers. If the language doesn’t let you then the language sucks.

empath-nirvana 3y ago
This post shows 3 ways of doing it, including essentially the same way you'd do it in C. And it's exactly as dangerous as doing it in C is, but at least you can isolate that dangerous code to one part of your code base.
- alexchamberlain 3y ago
  > you can isolate that dangerous code to one part of your code base. This is the whole point for me. There are loads of reasons fundamental data structures want to use behaviour the compile can't prove is sound, but humans can burn time discussing, proving the algorithms and testing the implementation. Then, you ask the compiler to prove all the simple glue stuff on top.
  - hinkley 3y ago
    I suspect there's a type theory here where many cases of parent links essentially represent the exact same problem, and if you solve one, you can restate most/all of the others in this form and then it's proven too. You know that popcount bit counting device that treats a word of memory as a short SIMD instruction using the 32 or 64 bit ALU? I learned recently that compilers can detect that and emit popcount instructions if those are faster on the target architecture. I suspect if you can detect that, you could detect a safe parental reference device and let it pass the checker.
worik 3y ago
> Some algorithms need the parent or bidirectional pointers. For trees some, not very good, algorithms require parent pointers

fhood 3y ago

I think it's best to think of this as a good toy example, and not get caught up in the specific utility of a "parent" node.

worik 3y ago
It is just a bad example. One of the main points is that there are very few algorithms that require back links that create cycles. Cyclic data structures, rare as they are, are also hard to reason about. Even for garbage collectors! If you have to implement one in Rust (I have) it is a bother, a big hassle. It is a good thing that in the general case when a programmer is implementing back links they are doing the Wrong Thing.

deleted 3y ago

[deleted]