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.