Wie modelliere ich einen Zirkelverweis zwischen unveränderlichen Objekten in C #?

24

Im folgenden Codebeispiel haben wir eine Klasse für unveränderliche Objekte, die einen Raum darstellt. Nord, Süd, Ost und West repräsentieren Ausgänge in andere Räume.

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; }
}

Wir sehen also, dass diese Klasse mit einem reflexiven Zirkelbezug entworfen wurde. Aber weil die Klasse unveränderlich ist, habe ich ein Problem mit Hühnern oder Eiern. Ich bin mir sicher, dass erfahrene Funktionsprogrammierer damit umgehen können. Wie kann es in C # gehandhabt werden?

Ich bin bestrebt, ein textbasiertes Abenteuerspiel zu programmieren, aber ich verwende funktionale Programmierprinzipien nur zum Zweck des Lernens. Ich bleibe bei diesem Konzept und kann Hilfe gebrauchen !!! Vielen Dank.

AKTUALISIEREN:

Hier ist eine funktionierende Implementierung, die auf der Antwort von Mike Nakis bezüglich der verzögerten Initialisierung basiert:

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();
    }
}
Rock Anthony Johnson
quelle
Dies scheint ein guter Fall für die Konfiguration und das Builder-Muster zu sein.
Greg Burghardt
Ich frage mich auch, ob ein Raum von der Anordnung einer Ebene oder Bühne entkoppelt werden sollte, damit jeder Raum nichts über die anderen weiß.
Greg Burghardt
1
@RockAnthonyJohnson Ich würde das nicht wirklich reflexiv nennen, aber das ist nicht relevant. Warum ist das aber ein Problem? Dies ist sehr häufig. Tatsächlich werden fast alle Datenstrukturen so aufgebaut. Denken Sie an eine verknüpfte Liste oder einen Binärbaum. Sie sind alle rekursive Datenstrukturen, und so ist Ihr RoomBeispiel.
Gardenhead
2
@RockAnthonyJohnson Unveränderliche Datenstrukturen sind zumindest in der funktionalen Programmierung weit verbreitet. Dies ist , wie Sie eine verkettete Liste definieren: type List a = Nil | Cons of a * List a. Und ein binärer Baum: type Tree a = Leaf a | Cons of Tree a * Tree a. Wie Sie sehen, sind beide selbstreferenziell (rekursiv). Hier ist , wie Sie Ihr Zimmer definieren würde: type Room = Nil | Open of {name: string, south: Room, east: Room, north: Room, west: Room}.
Gardenhead
1
Wenn Sie interessiert sind, nehmen Sie sich Zeit, um Haskell oder OCaml zu lernen. es wird deinen Verstand erweitern;) Denk auch daran, dass es keine klare Abgrenzung zwischen Datenstrukturen und "Geschäftsobjekten" gibt. Schauen Sie sich an, wie ähnlich die Definition Ihrer RoomKlasse und von a List in dem oben von mir geschriebenen Haskell ist.
Gardenhead

Antworten:

10

Natürlich können Sie nicht genau den Code verwenden, den Sie veröffentlicht haben, da Sie irgendwann ein Objekt erstellen müssen, das mit einem anderen Objekt verbunden werden muss, das noch nicht erstellt wurde.

Es gibt zwei Möglichkeiten, die ich mir vorstellen kann (die ich zuvor verwendet habe), um dies zu tun:

Mit zwei Phasen

Alle Objekte werden zuerst ohne Abhängigkeiten konstruiert und sobald sie alle konstruiert wurden, werden sie verbunden. Dies bedeutet, dass die Objekte in ihrem Leben zwei Phasen durchlaufen müssen: eine sehr kurze veränderbare Phase, gefolgt von einer unveränderlichen Phase, die für den Rest ihres Lebens andauert.

Beim Modellieren relationaler Datenbanken können Sie auf genau dieselbe Art von Problem stoßen: Eine Tabelle verfügt über einen Fremdschlüssel, der auf eine andere Tabelle verweist, und die andere Tabelle verfügt möglicherweise über einen Fremdschlüssel, der auf die erste Tabelle verweist. In relationalen Datenbanken wird dies so gehandhabt, dass die Fremdschlüsseleinschränkungen mit einer zusätzlichen ALTER TABLE ADD FOREIGN KEYAnweisung angegeben werden können (und in der Regel sind), die von der CREATE TABLEAnweisung getrennt ist. Sie erstellen also zuerst alle Ihre Tabellen und fügen dann Ihre Fremdschlüsseleinschränkungen hinzu.

Der Unterschied zwischen relationalen Datenbanken und dem, was Sie tun möchten, besteht darin, dass relationale Datenbanken ALTER TABLE ADD/DROP FOREIGN KEYwährend der gesamten Lebensdauer der Tabellen weiterhin Anweisungen zulassen. Wahrscheinlich setzen Sie ein Flag "IamImmutable" und lehnen weitere Mutationen ab, sobald alle Abhängigkeiten erkannt wurden.

Lazy Initialization verwenden

Anstelle eines Verweises auf eine Abhängigkeit übergeben Sie einen Delegaten , der bei Bedarf den Verweis auf die Abhängigkeit zurückgibt. Sobald die Abhängigkeit abgerufen wurde, wird der Delegat nie wieder aufgerufen.

Der Delegat hat normalerweise die Form eines Lambda-Ausdrucks, sodass er nur geringfügig ausführlicher aussieht, als wenn Abhängigkeiten tatsächlich an die Konstruktoren übergeben werden.

Der (winzige) Nachteil dieser Technik ist, dass Sie den Speicherplatz verschwenden müssen, der zum Speichern der Zeiger auf die Stellvertreter erforderlich ist, die nur während der Initialisierung Ihres Objektdiagramms verwendet werden.

Sie können sogar eine generische "Lazy Reference" -Klasse erstellen, die dies implementiert, damit Sie es nicht für jedes einzelne Ihrer Mitglieder erneut implementieren müssen.

Hier ist eine solche Klasse in Java geschrieben, Sie können es leicht in C # transkribieren

(Mein Function<T>ist wie der Func<T>Delegat von 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 );
    }
}

Diese Klasse soll thread-sicher sein, und das "Double Check" -Paket bezieht sich auf eine Optimierung im Fall von Parallelität. Wenn Sie nicht vorhaben, mehrere Threads zu verwenden, können Sie all diese Dinge entfernen. Wenn Sie sich für die Verwendung dieser Klasse in einem Multithread-Setup entscheiden, lesen Sie unbedingt das "double check idiom". (Dies ist eine lange Diskussion, die über den Rahmen dieser Frage hinausgeht.)

Mike Nakis
quelle
1
Mike, du bist brillant. Ich habe den ursprünglichen Beitrag so aktualisiert, dass er eine Implementierung enthält, die auf dem basiert, was Sie über verzögerte Initialisierung gepostet haben.
Rock Anthony Johnson
1
Die .Net-Bibliothek bietet eine Lazy-Referenz mit dem passenden Namen Lazy <T>. Wie wundervoll! Das habe ich aus einer Antwort auf eine Codeüberprüfung
Rock Anthony Johnson
16

Das verzögerte Initialisierungsmuster in der Antwort von Mike Nakis eignet sich gut für eine einmalige Initialisierung zwischen zwei Objekten, wird jedoch für mehrere miteinander verbundene Objekte mit häufigen Aktualisierungen unhandlich.

Es ist viel einfacher und übersichtlicher, die Verknüpfungen zwischen Räumen außerhalb der Raumobjekte selbst in einer Weise wie einer zu halten ImmutableDictionary<Tuple<int, int>, Room>. Auf diese Weise erstellen Sie keine Zirkelverweise, sondern fügen nur einen einzelnen, leicht aktualisierbaren Einwegverweis zu diesem Wörterbuch hinzu.

Karl Bielefeldt
quelle
Denken Sie daran, sprachen über unveränderliche Objekte, so gibt es keine Updates.
Rock Anthony Johnson
4
Wenn von der Aktualisierung unveränderlicher Objekte die Rede ist, bedeutet dies, ein neues Objekt mit den aktualisierten Attributen zu erstellen und anstelle des alten Objekts auf dieses neue Objekt in einem neuen Bereich zu verweisen. Das ist allerdings jedes Mal etwas langweilig.
Karl Bielefeldt
Karl, bitte vergib mir. Ich bin immer noch ein Neuling in Funktionsprinzipien, hahaa.
Rock Anthony Johnson
2
Das ist die richtige Antwort. Zirkuläre Abhängigkeiten sollten im Allgemeinen aufgehoben und an Dritte delegiert werden. Es ist viel einfacher als die Programmierung eines komplexen Build-and-Freeze-Systems aus veränderlichen Objekten, die unveränderlich werden.
Benjamin Hodgson
Ich wünschte, ich könnte dem noch ein paar +1 geben ... Unveränderlich oder nicht, ohne ein "externes" Repository oder einen Index (oder was auch immer ), wäre es ziemlich unnötig komplex, all diese Räume richtig zu verbinden. Und dies nicht verbietet , die Roomaus erscheint diese Beziehungen zu haben; aber sie sollten Getter sein, die einfach aus dem Index lesen.
Svidgen
12

Die Art und Weise, dies in einem funktionalen Stil zu tun, besteht darin, zu erkennen, was Sie tatsächlich konstruieren: ein gerichtetes Diagramm mit beschrifteten Kanten.

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

Ein Dungeon ist eine Datenstruktur, die eine Reihe von Räumen und Dingen sowie die Beziehungen zwischen ihnen aufzeichnet. Jeder „mit“ Aufruf gibt einen neuen, verschiedenen unveränderlichen Kerker. Die Räume wissen nicht, was nördlich und südlich von ihnen ist; Das Buch weiß nicht, dass es in der Truhe ist. Der Dungeon kennt diese Tatsachen, und das Ding hat kein Problem mit Zirkelverweisen, weil es keine gibt.

Eric Lippert
quelle
1
Ich habe gerichtete Graphen und fließende Builder (und DSLs) studiert. Ich kann sehen, wie dies einen gerichteten Graphen erzeugen kann, aber dies ist das erste Mal, dass ich die beiden damit verbundenen Ideen gesehen habe. Gibt es ein Buch oder einen Blogbeitrag, den ich verpasst habe? Oder erzeugt dies einen gerichteten Graphen, nur weil dies das Fragenproblem löst?
candied_orange
@CandiedOrange: Dies ist eine Skizze, wie die API aussehen könnte. Tatsächlich würde das Aufbauen der ihm zugrunde liegenden unveränderlichen gerichteten Graphendatenstruktur einige Arbeit erfordern, aber es ist nicht schwer. Ein unveränderlicher gerichteter Graph ist nur eine unveränderliche Menge von Knoten und eine unveränderliche Menge von (Start-, End-, Bezeichnungs-) Tripeln, sodass er auf eine Zusammensetzung bereits gelöster Probleme reduziert werden kann.
Eric Lippert
Wie gesagt, ich habe sowohl DSLs als auch gerichtete Graphen studiert. Ich versuche herauszufinden, ob Sie etwas gelesen oder geschrieben haben, das die beiden zusammenfügt, oder ob Sie sie gerade zusammengebracht haben, um diese spezielle Frage zu beantworten. Wenn Sie etwas wissen, das sie zusammenbringt, würde ich es lieben, wenn Sie mich darauf hinweisen könnten.
candied_orange
@CandiedOrange: Nicht besonders. Ich habe vor vielen Jahren eine Blogserie über einen unveränderlichen, ungerichteten Graphen geschrieben, um einen Backtracking-Sudoku-Solver zu erstellen. Und ich habe kürzlich eine Blogserie über objektorientierte Entwurfsprobleme für veränderbare Datenstrukturen im Bereich der Assistenten und Dungeons geschrieben.
Eric Lippert
3

Huhn und ein Ei ist richtig. Das macht keinen Sinn in c #:

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

Aber das macht:

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

Aber das heißt, A ist nicht unveränderlich!

Sie können betrügen:

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

Das verbirgt das Problem. Sicher, A und B haben einen unveränderlichen Zustand, aber sie beziehen sich auf etwas, das nicht unveränderlich ist. Welches leicht den Punkt besiegen könnte, sie unveränderlich zu machen. Ich hoffe C ist mindestens so threadsicher, wie Sie es brauchen.

Es gibt ein Muster namens Einfrieren-Auftauen:

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

Jetzt ist 'a' unveränderlich. 'A' ist nicht aber 'a' ist. Warum ist das ok Solange nichts anderes über 'a' weiß, bevor es eingefroren ist, wen interessiert das?

Es gibt eine thaw () -Methode, die jedoch niemals 'a' ändert. Es erstellt eine veränderbare Kopie von 'a', die aktualisiert und dann auch eingefroren werden kann.

Der Nachteil dieses Ansatzes ist, dass die Klasse keine Unveränderlichkeit erzwingt. Folgendes Verfahren ist. Sie können nicht sagen, ob es vom Typ unerschütterlich ist.

Ich kenne keinen idealen Weg, um dieses Problem in c # zu lösen. Ich kenne Möglichkeiten, die Probleme zu verbergen. Manchmal ist das genug.

Wenn dies nicht der Fall ist, benutze ich einen anderen Ansatz, um dieses Problem insgesamt zu vermeiden. Zum Beispiel: schauen, wie die Zustandsmuster implementiert sind hier . Sie würden denken, dass sie das als Zirkelverweis tun würden, aber sie tun es nicht. Sie drehen jedes Mal, wenn sich der Zustand ändert, neue Objekte auf. Manchmal ist es einfacher, den Müllmann zu missbrauchen, als herauszufinden, wie man Eier aus Hühnern holt.

kandierte_orange
quelle
+1 für die Einführung in ein neues Muster. Zuerst habe ich von Einfrieren-Auftauen gehört.
Rock Anthony Johnson
a.freeze()könnte ImmutableATyp zurückgeben. was es im Grunde Builder-Muster machen.
Bryan Chen
@BryanChen Wenn Sie das tun, bbleibt ein Verweis auf die alte veränderbare a. Die Idee ist, dass a und bsollte auf unveränderliche Versionen von einander verweisen, bevor Sie sie für den Rest des Systems freigeben.
candied_orange
@RockAnthonyJohnson Dies ist auch, was Eric Lippert Popsicle Unveränderlichkeit nannte .
Gesichtet
1

Einige kluge Leute haben bereits ihre Meinung dazu geäußert, aber ich denke nur, dass es nicht die Verantwortung des Raumes ist, zu wissen, was seine Nachbarn sind.

Ich denke, es liegt in der Verantwortung des Gebäudes, zu wissen, wo sich Räume befinden. Wenn der Raum wirklich wissen muss, welche Nachbarn er hat, geben Sie INeigbourFinder an ihn weiter.

tymtam
quelle