4 ms·

Especially when they are explicitly taken into account through escape hatches in the ownership system

chrismorgan 6y ago
Yet the safest escape hatches are decidedly limited. Take Rc<RefCell<_>> nodes in a graph (struct Node { edges: Vec<Rc<RefCell<Node>>> }), for example: mutable cyclic traversal is somewhere between difficult (requiring some typically-significant convolution of your algorithm) and impossible. Meanwhile, a GC language can model the same thing trivially. So you start reaching for more dangerous escape hatches, or modelling the problem in some completely different way that lets you skip the problems of ownership semantics for the given domain.
- fpoling 6y ago
  Modeling an arbitrary graph with reference counting immediately leads to the problem of cycles and the need of some form of GC to collect them. It is better to use a GC from the start (not collecting things until the graph owner decides to discard the whole graph is often a useful approach), or reduce the graph to a tree and use weak references for references between branches. Or even use handles as advocated by the article, which essentially reduces the graph to an array and uses its indexes as weak references.
- DougBTX 6y ago
  > or modelling the problem in some completely different way that lets you skip the problems of ownership semantics for the given domain Maybe that's an interesting way to think about the article too. The obvious way to think about a graph using ownership is to start with a root node, then to say that nodes own other nodes through their edges. But that model won't generalise to disjoint graphs (eg, social network with separate friend groups) and it isn't always clear which node is the "root" node.
  - trumpeta 6y ago
    Graphs are usually persisted as a list of nodes and a list of vertices. The ML approaches usually use tuples or triplets of nodes to represent connectivity and model neighborhood. I wonder if that can not be used to model a graph in a linear system?
    - DougBTX 6y ago
      Yes, that makes a lot of sense. The ownership would be linear: struct Graph { nodes: Vec<Node>, edges: Vec<Edge>, } but the associations between nodes would have an arbitrary structure. The article suggests that handles are better than references anyway (I'd tend to agree in this case) so Edge would be a pair of handles. That seems totally fine, so maybe the "fatal flaw" is overstated...
  - chrismorgan 6y ago
    Fundamentally, this most obvious way of representing a graph (each node has a list of adjacent nodes, which are references to the actual nodes) can only work in an ownership-oriented language for directed acyclic graphs. Blockchains, Git commits, directory trees not supporting links, that sort of thing. (Mind you, for practical reasons many systems will still prefer to invert the tree and probably even traverse from leaf to root; this most obvious way is not actually a good fit for computers a lot of the time, even if it’s conceptually beautiful.) But if your graph is not directed, then ownership is not clear (A → B means A owns B, but with A ↔ B you can’t have both A owning B and B owning A), and if it can be cyclic, single ownership definitely falls apart.
    - chrismorgan 6y ago
      Correction: tree, not directed acyclic graph. Multiple paths to a single node is verboten for single ownership. Note that DAGs may still be useful in single-ownership languages: recursive traversal will never touch a visited node, so if you exclusively borrow the whole graph, then you can safely exclusively borrow any node you traverse (which you couldn’t do if the graph was cyclic; in Rust terms, you’d have to check it at runtime).

Yet the safest escape hatches are decidedly limited. Take Rc<RefCell<_>> nodes in a graph (struct Node { edges: Vec<Rc<RefCell<Node>>> }), for example: mutable cyclic traversal is somewhere between difficult (requiring some typically-significant convolution of your algorithm) and impossible. Meanwhile, a GC language can model the same thing trivially. So you start reaching for more dangerous escape hatches, or modelling the problem in some completely different way that lets you skip the problems of ownership semantics for the given domain.

fpoling 6y ago
Modeling an arbitrary graph with reference counting immediately leads to the problem of cycles and the need of some form of GC to collect them. It is better to use a GC from the start (not collecting things until the graph owner decides to discard the whole graph is often a useful approach), or reduce the graph to a tree and use weak references for references between branches. Or even use handles as advocated by the article, which essentially reduces the graph to an array and uses its indexes as weak references.
DougBTX 6y ago
> or modelling the problem in some completely different way that lets you skip the problems of ownership semantics for the given domain Maybe that's an interesting way to think about the article too. The obvious way to think about a graph using ownership is to start with a root node, then to say that nodes own other nodes through their edges. But that model won't generalise to disjoint graphs (eg, social network with separate friend groups) and it isn't always clear which node is the "root" node.
- trumpeta 6y ago
  Graphs are usually persisted as a list of nodes and a list of vertices. The ML approaches usually use tuples or triplets of nodes to represent connectivity and model neighborhood. I wonder if that can not be used to model a graph in a linear system?
  - DougBTX 6y ago
    Yes, that makes a lot of sense. The ownership would be linear: struct Graph { nodes: Vec<Node>, edges: Vec<Edge>, } but the associations between nodes would have an arbitrary structure. The article suggests that handles are better than references anyway (I'd tend to agree in this case) so Edge would be a pair of handles. That seems totally fine, so maybe the "fatal flaw" is overstated...
- chrismorgan 6y ago
  Fundamentally, this most obvious way of representing a graph (each node has a list of adjacent nodes, which are references to the actual nodes) can only work in an ownership-oriented language for directed acyclic graphs. Blockchains, Git commits, directory trees not supporting links, that sort of thing. (Mind you, for practical reasons many systems will still prefer to invert the tree and probably even traverse from leaf to root; this most obvious way is not actually a good fit for computers a lot of the time, even if it’s conceptually beautiful.) But if your graph is not directed, then ownership is not clear (A → B means A owns B, but with A ↔ B you can’t have both A owning B and B owning A), and if it can be cyclic, single ownership definitely falls apart.
  - chrismorgan 6y ago
    Correction: tree, not directed acyclic graph. Multiple paths to a single node is verboten for single ownership. Note that DAGs may still be useful in single-ownership languages: recursive traversal will never touch a visited node, so if you exclusively borrow the whole graph, then you can safely exclusively borrow any node you traverse (which you couldn’t do if the graph was cyclic; in Rust terms, you’d have to check it at runtime).