How to model a circular reference between immutable objects in C#?

Question

In the following code example, we have an class for immutable objects that represents a room. North, South, East, and West represent exits into other rooms.

public sealed class Room { public Room(string name, Room northExit, Room southExit, Room eastExit, Room westExit) { this.Name = name; this.North = northExit; this.South = southExit; this.East = eastExit; this.West = westExit; } public string Name { get; } public Room North { get; } public Room South { get; } public Room East { get; } public Room West { get; } } 

So we see, this class is designed with a reflexive circular reference. But because the class immutable, I'm stuck with a 'chicken or the egg' problem. I'm certain that experienced functional programmers know how deal with this. How can it be handled in C#?

I'm endeavoring to code a text-based adventure game, but using functional programming principles just for the sake of learning. I'm stuck on this concept and can use some help!!! Thanks.

UPDATE:

Here's a working implementation based on Mike Nakis' answer regarding lazy initialization:

using System; public sealed class Room { private readonly Func<Room> north; private readonly Func<Room> south; private readonly Func<Room> east; private readonly Func<Room> west; public Room( string name, Func<Room> northExit = null, Func<Room> southExit = null, Func<Room> eastExit = null, Func<Room> westExit = null) { this.Name = name; var dummyDelegate = new Func<Room>(() => { return null; }); this.north = northExit ?? dummyDelegate; this.south = southExit ?? dummyDelegate; this.east = eastExit ?? dummyDelegate; this.west = westExit ?? dummyDelegate; } public string Name { get; } public override string ToString() { return this.Name; } public Room North { get { return this.north(); } } public Room South { get { return this.south(); } } public Room East { get { return this.east(); } } public Room West { get { return this.west(); } } public static void Main(string[] args) { Room kitchen = null; Room library = null; kitchen = new Room( name: "Kitchen", northExit: () => library ); library = new Room( name: "Library", southExit: () => kitchen ); Console.WriteLine( $"The {kitchen} has a northen exit that " + $"leads to the {kitchen.North}."); Console.WriteLine( $"The {library} has a southern exit that " + $"leads to the {library.South}."); Console.ReadKey(); } } 

Answer 1

Obviously, you can not do it using exactly the code you posted, because at some point you will need to construct an object which needs to be connected to another object that has not been constructed yet.

There are two ways that I can think of (that I have used before) to do this:

Using two phases

All the objects are constructed first, without any dependencies, and once they have all been constructed, they are connected. This means that the objects need to go through two phases in their life: a very short mutable phase, followed by an immutable phase which lasts throughout the rest of their lifetime.

You can come across the exact same kind of problem when modelling relational databases: one table has a foreign key which points to another table, and the other table may have a foreign key which points to the first table. The way this is handled in relational databases is that the foreign key constraints can (and usually are) specified with an extra ALTER TABLE ADD FOREIGN KEY statement which is separate from the CREATE TABLE statement. So, first you create all your tables, then you add your foreign key constraints.

The difference between relational databases and what you want to do is that relational databases continue to allow ALTER TABLE ADD/DROP FOREIGN KEY statements throughout the lifetime of the tables, while you will probably set an 'IamImmutable` flag and refuse any further mutations once all dependencies have been realized.

Using lazy initialization

Instead of a reference to a dependency you pass a delegate which will return the reference to the dependency when needed. Once the dependency has been fetched, the delegate is never invoked again.

The delegate will usually take the form of a lambda expression, so it will look only slightly more verbose than actually passing dependencies to the constructors.

The (tiny) downside of this technique is that you have to waste the storage space needed to store the pointers to the delegates which will only be used during the initialization of your object graph.

You can even create a generic "lazy reference" class which implements this so that you do not have to re-implement it for every single one of your members.

Here is such a class written in Java, you can easily transcribe it in C#

(My Function<T> is like the Func<T> delegate of C#)

package saganaki.util; import java.util.Objects; /** * A {@link Function} decorator which invokes the given {@link Function} only once, when actually needed, and then caches its result and never calls it again. * It behaves as if it is immutable, which includes the fact that it is thread-safe, provided that the given {@link Function} is also thread-safe. * * @param <T> the type of object supplied. */ public final class LazyImmutable<T> implements Function<T> { private static final boolean USE_DOUBLE_CHECK = false; //TODO try with "double check" private final Object lock = new Object(); @SuppressWarnings( "FieldAccessedSynchronizedAndUnsynchronized" ) private Function<T> supplier; @SuppressWarnings( "FieldAccessedSynchronizedAndUnsynchronized" ) private T value; /** * Constructor. * * @param supplier the {@link Function} which will supply the supplied object the first time it is needed. */ public LazyImmutable( Function<T> supplier ) { assert supplier != null; assert !(supplier instanceof LazyImmutable); this.supplier = supplier; value = null; } @Override public T invoke() { if( USE_DOUBLE_CHECK ) { if( supplier != null ) doCheck(); return value; } doCheck(); return value; } private void doCheck() { synchronized( lock ) { if( supplier != null ) { value = supplier.invoke(); supplier = null; } } } @Override public String toString() { if( supplier != null ) return "(lazy)"; return Objects.toString( value ); } } 

This class is supposed to be thread-safe, and the "double check" stuff is related to an optimization in the case of concurrency. If you are not planning to be multi-threaded, you can strip all that stuff away. If you decide to use this class in a multi-threaded setup, be sure to read about the "double check idiom". (This is a long discussion beyond the scope of this question.)

Answer 2

The lazy initialization pattern in Mike Nakis' answer works just fine for a one-time initialization between two objects, but becomes unwieldy for multiple inter-related objects with frequent updates.

It's much simpler and more manageable to keep the links between rooms outside the room objects themselves, in something like an ImmutableDictionary<Tuple<int, int>, Room>. That way, instead of creating circular references, you're just adding a single, easily updateable, one-way reference to this dictionary.

Answer 3

The way to do this in a functional style is to recognize what you are actually constructing: a directed graph with labeled edges.

Room library = new Room("Library"); Room ballroom = new Room("Ballroom"); Thing chest = new Thing("Treasure chest"); Thing book = new Thing("Ancient Tome"); Dungeon dungeon = Dungeon.Empty .WithRoom(library) .WithRoom(ballroom) .WithThing(chest) .WithThing(book) .WithPassage("North", library, ballroom) .WithPassage("South", ballroom, library) .WithContainment(library, chest) .WithContainment(chest, book); 

A dungeon is a data structure which keeps track of a bunch of rooms and things, and what the relationships between them are. Each "with" call returns a new, different immutable dungeon. The rooms don't know what is north and south of them; the book doesn't know it's in the chest. The dungeon knows those facts, and that thing has no problem with circular references because there are none.

Answer 4

Chicken and an egg is right. This makes no sense in c#:

A a = new A(b); B b = new B(a); 

But this does:

A a = new A(); B b = new B(a); a.setB(b); 

But that means A is not immutable!

You can cheat:

C c = new C(); A a = new A(c); B b = new B(c); c.addA(a); c.addB(b); 

That hides the problem. Sure A and B have immutable state but they refer to something that is not immutable. Which could easily defeat the point of making them immutable. I hope C is at least as thread safe as you need.

There is a pattern called freeze-thaw:

A a = new A(); B b = new B(a); a.addB(b); a.freeze(); 

Now 'a' is immutable. 'A' isn't but 'a' is. Why is that ok? So long as nothing else knows about 'a' before it's frozen, who cares?

There is a thaw() method but it doesn't ever change 'a'. It makes a mutable copy of 'a' that can be updated then frozen as well.

The downside of this approach is that the class isn't enforcing immutability. Following procedure is. You can't tell if it's immutabile from the type.

I don't really know an ideal way to solve this problem in c#. I know ways to hide the problems. Sometimes that's enough.

When it's not I use a different approach to avoid this problem altogether. For example: look at how the state pattern is implemented here. You'd think they'd do that as a circular reference but they don't. They crank out new objects every time the state changes. Sometimes it's easier to abuse the garbage collector then to figure out how to get eggs out of chickens.

Answer 5

Some smart people voiced their opinions on this already, but I just think that it isn't the room's responsibility to know what its neighbours are.

I think it's the building's responsibility to know where rooms are. If the room really needs to know its neighbours pass INeigbourFinder to it.