How can I instantiate immutable mutually recursive objects?

Question

I have an immutable recursive type:

public sealed class Foo
{
    private readonly object something;
    private readonly Foo other; // might be null

    public Foo(object something, Foo other)
    {
        this.something = something;
        this.other = other;
    }
    public object Something { get { return something; } }
    public Foo Other { get { return other; } }
}

I need to instantiate two objects of this type that refer to each other, i.e. a.Other == b && b.Other == a.

I don't want to abandon the immutability invariants because Foo is intended for use as a flyweight. I can (and I think must) abandon readonly on the fields, and leave the "guts" mutable, but the public interface must be immutable.

Is popsicle immutability the only way to get this done?

I'm trying to model a collection of types. Each type has a name and several attributes. Each attribute has a name and a type. There are a few mutually recursive types, and that's where this problem arose.

Answer 1

There are other ways to get it done, but they might not have properties that you want.

Suppose you wanted to represent an immutable tree of values, built from the leaves up. That's pretty straightforward. You might have a node constructor that takes a value and a list of child nodes. That makes it pretty straightforward to construct new trees out of old trees, and they're guaranteed to be acyclic.

Now suppose you want to represent an immutable directed graph of values. Now you have the problem that nodes can have cycles; there might not be a "leaf" to build the graph from. The solution is to abandon the principle that the node knows what its neighbours are. You could represent an immutable graph by making an immutable set of nodes, and an immutable list of edges. To add a node to the immutable graph you construct a new graph with that node added to the node set. Similarly for adding an edge; you construct a new list of edges. Now the fact that there are cycles in the topology of the graph is irrelevant; no one object has a cycle in what objects it references.

Without knowing more about your actual problem space it is hard to say what immutable data structure would work for your application. Can you tell us more about what you're trying to do?

I'm trying to model a collection of types. Each type has a name and several attributes. Each attribute has a name and a type. There are a few mutually recursive types, and that's where this problem arose.

Well geez, you should have said so in the first place. If there's one thing I know about, it's analysis of types. Obviously the compiler needs to be able to handle all kinds of crazy type situations, including types with cyclic base classes, cycles involving inner types, type arguments, type constraints and so on.

In the C# compiler we solve these problems mostly by making objects "staged" in their immutability. That is, when we first create a set of types, each type object knows its name and its position in source code (or metadata). The name then becomes immutable. We then resolve the base types and check them for cycles; the base types then become immutable. Then we check the type constraints... then we resolve the attributes... and so on, until everything is analyzed.

I have considered other ways of doing this. For example, we might use the same technique that I just suggested for graphs: make an immutable object, called, say "compilation", to which you can add types, thereby producing new immutable compilations. The compilation can keep track of the "edges" between a type and its base type in an immutable hash map, and can then check the resulting graph for cycles. The down side is then that a type does not know its base type; you have to ask the compilation what the base type of a type is.

You could do the same thing here. You could have a class "typeset" that contains a set of immutable types, and a multi-map from type to a set of immutable attributes. You can build up the set of types and the set of attributes however you like; the thing that changes is the map, not the type.

The down side of this is that you no longer ask the type for its attributes; you ask the typeset for the attributes of a type. That might not meet your needs if you need to pass types around independently of any typeset.

Answer 2

It is definitely impossible using write-once immutability. Let me explain why. You can set fields' values only at constructor. So if you want a to refer to b you have to pass reference to b to a's constructor. But b will be already frozen. So the only option is to instantiate b in a's constructor. But this is impossible, because you can't pass reference to a, because this is invalid inside constructor.

From this point popsicle immutability is the simplest and most elegant solution. Another way is to create static method Foo.CreatePair that will instantiate two objects, set cross reference and return frozen object.

public sealed class Foo
{
    private readonly object something;
    private Foo other; // might be null

    public Foo(object something, Foo other)
    {
        this.something = something;
        this.other = other;
    }
    public object Something { get { return something; } }
    public Foo Other { get { return other; } private set { other = value; } }

    public static CreatePair(object sa, object sb)
    {
        Foo a = new Foo(sa, null);
        Foo b = new Foo(sb, a);
        a.Other = b;
        return a;
    }
}