Imagine a programming language where the references can be mutual. What exactly does this mean and would such a feature be useful?

Basics

Standard way to declare reference attribute is to set its name and type. We imagine a case where one could also declare attribute in the target class which would become mutually tied to the currently defined attribute. The declaration could look as in the following example.

class Person {
    passport: Passport.person;
}
class Passport {
    person: Person.passport;
}

Having an instance adam of the Person class setting adam.passport = a would automatically set a.person = adam. Additionally, if the passport a was already set to another person, then setting the attribute would remove this passport from its previous owner.

Defining and working with many data structures becomes quite easy. A linked list would be defined as follows.

// linked list
class LinkNode {
    next: LinkNode.previous;
    previous: LinkNode.next;
}

Adding a new element is now just about setting the new node correctly. As the back references are set automatically, we do not need to change other entries manually in order to keep the data consistent. Adding a new element to a linked list would look similar as follows.

node = new LinkNode(20);
node.prev = head.prev;
// would set: head.prev.next = node
node.next = head;
// would set: head.prev = node

The side-effects can be quite confusing and debugging unexpected assignment would become tedious. For this reason, it is unreasonable to implement this feature in classical-style languages. However, this model can work nicely in a setting with transactions, where such side-effects do not cause such problems.

Data structures

In tree structures each node has a list of its children while each child points to its parent. This is another natural use case for reference linking.

// tree
class TreeNode {
    children: TreeNode.parent[]
    parent: TreeNode.children
}

Trying to specialize these, binary trees cannot be described by simple linking because its left and right child both link to the parent attribute. To declare these attributes correctly, we need to link one attribute to multiple ones. Setting the parent attribute manually becomes ambiguous as we do not know which linked attribute should we change. We may resolve this by forbidding assignment of this attribute or defaulting the assignment to one attribute (which seems to be a pretty confusing solution for the programmer).

// binary tree
class BinaryTreeNode {
    left: BinaryTreeNode.parent[]
    right: BinaryTreeNode.parent[]
    parent: BinaryTreeNode.left | BinaryTreeNode.right
}

However, we may resolve the assignment issue when substitution is taking place. E.g. setting x.parent = node.parent may infer the chosen attribute by what is currently set. We may see this in the following implementation of leftRotation which is used in AVL tree.

// AVL tree method
void leftRotation(BinaryTreeNode node) {
    assert(node.right);
    let x = node.right;
    x.parent = node.parent;
    node.right = x.left
    node.parent = x;
}

One can also link a attribute to itself. This defines a mutual relation. In this way, we may define a graph structure where each node lists its neighbors.

// graph
class Node {
    neighbor: Node.neighbor[]
}

Similarly, we may tie two attributes to create an oriented relation.

// oriented graph
class Node {
    outNeighbor: Node.inNeighbor[]
    inNeighbor: Node.outNeighbor[]
}

Further

The described feature seems useful, however, only time will show if this is useful enough. Keeping the code short is nice, but feature which accomplishes only that is just a gimmick. It seems that there are other issues which would need to be tackled.

• What data structure should the linked sets be? – Sets are better for adding and removing asymptotically, but for small numbers arrays are better.
• It is not efficient to keep links for attributes which could contain too many values. – This could typically happen if we link object to its type because there may be many instances of the same type.
• If two arrays are linked should the links consider indices? – Links could tie elements of an array together.