Graph-based data structures

[OOTS]

Hello,

a few days ago I read an article about Rue in a german IT magazine. Since I'm working on a programming language with similar design goals as a hobby project, I'm quite interested in Rue.

After having skimmed over the available documentation (tutorial and language spec) my understanding is that there are two different "kinds" of datatypes in Rue: "copy"-able types and "move" types. From what I've seen, borrowing is supported, but only for the duration of a function call.

While that is fine for an experimental language, I think this model is not sufficient to store graphs or graph-like data structures. E.g., if one wanted to implement a shortest-path algorithm such as Dijkstra's algorithm, one would first need an in-memory representation of the graph. One natural implementation is to create a struct Node which stores a list of outgoing (and maybe) incoming edges. If the struct Node would be @copy-able, one would have to change all copies of a given node if one wanted to add an edge. If the struct Node was not copy-able it wouldn't be possible to store multiple references to the same struct.
(There are other ways to represent a graph in memory, e.g. via incidence matrices, but ... they appear a bit unnatural to me.)

Another example would be (HTML-style) DOM trees, where each node not only stores references to it's children but also to it's parent. In fact, I think even implementing a doubly-linked list would not be possible within the current model.

I'd be curious to know/hear your thoughts about this limitation. Is it something you'd be willing to accept permanently? If not, do you have any plans to extend the model and allow references (in some way)?

[DorianListens]

I recently read an interesting paper about graph data structures and mutable value semantics: Who Owns the Contents of a Doubly-Linked List?.

From the abstract:

Despite their popularity, systems enforcing full ownership guarantees such as Rust leave many users frustrated with the inability to represent notionally self-referential data structures - e.g., doubly-linked lists - using first-class references. This frustration has motivated a number of proposals to relax on full ownership to support idioms common in languages with pervasive reference semantics. In this paper, we take a look at the way value-oriented languages address this issue and study representations of arbitrary graph-like data structures without references.

The examples in the paper (including Dijkstra's algorithm, and a doubly-linked list) are implemented in Swift, but using the same reference-free approach @steveklabnik has described for Rue, at least as far as I understand it.

The core of the design described in the paper is clarifying the difference between "whole" and "part" relationships. Instead of each node containing references representing edges in the graph, the graph itself contains edge relationships between the various nodes.

The claim in the paper is that implementing arbitrary graphs is not only possible and ergonomic using mutable value semantics, but that it even comes with performance improvements over the reference based approach.

[steveklabnik]

Hey @OOTS , I didn't realize Heise had written about Rue, thanks for the heads up :)

Basically, I haven't given a ton of thought to this specifically, but as @DorianListens mentions, there shouldn't be any fundamental incompatibility here. Now, that doesn't mean that Rue as of today has this capability: a much funnier problem with the language as currently implemented is that there's no way to get a String out of an array, for example. I have a lot more work to do. So, it wouldn't shock me if this were impossible right now, but I'd hope that it's a temporary limitation, yeah.

[parasyte]

This is an old discussion, but since it wasn't mentioned previously here is another perspective. Niko Matsakis wrote about using vector indices to implement graph data structures in 2015: https://smallcultfollowing.com/babysteps/blog/2015/04/06/modeling-graphs-in-rust-using-vector-indices/

After reading this article, I wrote the same algorithm using real references with an arena (just a hobby project, not published anywhere). The original code with indices ends up much easier to read and reason about.

The primary disadvantage described in the article applies to the arena-based graph as well: removal is hard. The arena gently suggests that the only certain way to remove a node from the graph is to drop the whole graph. (Nodes and edges have the same lifetime as the arena. They can outlive their removal in unanticipated ways. Strictly speaking, nodes and edges allocated within the arena cannot be freed independently of the arena.)

Perhaps more surprisingly, nodes and graphs allocated within one graph's arena can be used in another graph's arena as long as the lifetimes are the same. This is almost exactly identical to the second mentioned disadvantage with the added lifetime equality constraint. Harder to abuse but can still plausibly happen.

Ultimately, I agree with the article's conclusion: use reference counting if stronger guarantees are needed around a large dynamic graph when the application is built around it.

One additional benefit to indices: They can be made smaller than usize, potentially saving a great deal of memory for large graphs. u32 has a practical limit of 4.29 billion nodes and edges at half of the memory cost for usize on 64-bit platforms. Reference counted pointers are larger still. (See https://floooh.github.io/2018/06/17/handles-vs-pointers.html for additional benefits to indices.)