24

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();
    }
}
  • This feels like a good case for configuration and the Builder Pattern. – Greg Burghardt Oct 21 '16 at 21:52
  • I also wonder if a room should be decoupled from the layout of a level or stage, so that each room doesn't know about the others. – Greg Burghardt Oct 21 '16 at 21:54
  • 1
    @RockAnthonyJohnson I wouldn't really call that reflexive, but that's not pertinent. Why is that a problem, though? This is extremely common. In fact, it's how almost all data structures are built. Think about a linked list or a binary tree. They're all recursive data structures, and so is your Room example. – gardenhead Oct 22 '16 at 3:03
  • 2
    @RockAnthonyJohnson Immutable data structures are extremely common, at least in functional programming. This is how you define a linked list: type List a = Nil | Cons of a * List a. And a binary tree: type Tree a = Leaf a | Cons of Tree a * Tree a. As you can see, they're both self-referential (recursive). Here's how you'd define your room: type Room = Nil | Open of {name: string, south: Room, east: Room, north: Room, west: Room}. – gardenhead Oct 22 '16 at 3:11
  • 1
    If you're interested, take the time to learn Haskell or OCaml; it'll expand your mind ;) Also keep in mind that there's no clear demarcation between data structures and "business objects". Look at how similar the definition of your Room class and a List are in the Haskell I wrote above. – gardenhead Oct 22 '16 at 3:31
10

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.)

16

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.

  • Keep in mind were talking about immutable objects, so there are no updates. – Rock Anthony Johnson Oct 22 '16 at 2:33
  • 4
    When people talk about updating immutable objects, they mean creating a new object with the updated attributes and referring to that new object in a new scope in lieu of the old object. That gets a bit tedious to say every time, though. – Karl Bielefeldt Oct 22 '16 at 5:51
  • Karl, please forgive me. I'm still a noob at functional principles, hahaa. – Rock Anthony Johnson Oct 22 '16 at 6:19
  • 2
    This is the right answer. Circular dependencies should in general be broken and delegated to a third party. It's much simpler than programming a complex build-and-freeze system of mutable objects that become immutable. – Benjamin Hodgson Oct 22 '16 at 12:28
  • Wish I could give this a few more +1's... Immutable or not, without an "external" repository or index (or whatever), getting all these rooms hooked up properly would be pretty unnecessarily complex. And this doesn't prohibit the Room from appearing to have those relationships; but, they should be getters that simply read from the index. – svidgen Oct 22 '16 at 19:09
12

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.

  • 1
    I've studied directed graphs and fluent builders (and DSLs). I can see how this could build a directed graph but this is the first I've seen the two ideas associated. Is there a book or blog post I've missed? Or does this produce a directed graph simply because that solves the questions problem? – candied_orange Nov 15 '16 at 12:41
  • @CandiedOrange: This is a sketch of what the API might look like. Actually building the immutable directed graph data structure underlying it would take some work, but its not hard. An immutable directed graph is just an immutable set of nodes and an immutable set of (start, end, label) triples, so it can be reduced to a composition of already-solved problems. – Eric Lippert Nov 15 '16 at 14:06
  • Like I said, I have studied both DSLs and directed graphs. I'm trying to figure out if you've read or written something that puts the two together or if you've just brought them together to answer this particular question. If you know of something out there that puts them together I'd love it if you could point me to it. – candied_orange Nov 15 '16 at 14:09
  • @CandiedOrange: Not particularly. I wrote a blog series many years ago on an immutable undirected graph for making a backtracking sudoku solver. And I wrote a blog series more recently about object oriented design problems for mutable data structures in the wizards-and-dungeons domain. – Eric Lippert Nov 15 '16 at 14:46
3

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.

  • +1 for introducing me to a new pattern. First I've ever heard of freeze-thaw. – Rock Anthony Johnson Oct 21 '16 at 23:18
  • a.freeze() could return ImmutableA type. which make it basically builder pattern. – Bryan Chen Oct 25 '16 at 4:30
  • @BryanChen if you do that then b is left holding a reference to the old mutable a. The idea is that a and b should point to immutable versions of each other before you release them to the rest of the system. – candied_orange Oct 25 '16 at 12:25
  • @RockAnthonyJohnson This is also what Eric Lippert called Popsicle immutability. – Spotted Nov 15 '16 at 10:48
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.