Jak modelować odwołanie kołowe między niezmiennymi obiektami w C #?

24

W poniższym przykładzie kodu mamy klasę dla niezmiennych obiektów reprezentujących pokój. Północ, południe, wschód i zachód reprezentują wyjścia do innych pomieszczeń.

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

Widzimy więc, że ta klasa została zaprojektowana z refleksyjną referencją kołową. Ale ponieważ klasa jest niezmienna, utknąłem z problemem „kurczaka lub jajka”. Jestem pewien, że doświadczeni programiści funkcjonalni wiedzą, jak sobie z tym poradzić. Jak można to obsłużyć w C #?

Staram się kodować tekstową grę przygodową, ale wykorzystuję funkcjonalne zasady programowania tylko ze względu na naukę. Utknąłem na tej koncepcji i mogę skorzystać z pomocy !!! Dzięki.

AKTUALIZACJA:

Oto działająca implementacja oparta na odpowiedzi Mike'a Nakisa dotyczącej leniwej inicjalizacji:

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
źródło
Wydaje się, że jest to dobry przypadek dla konfiguracji i Wzorca Konstruktora.
Greg Burghardt
Zastanawiam się również, czy pokój powinien być oddzielony od układu poziomu lub sceny, aby każdy pokój nie wiedział o innych.
Greg Burghardt
1
@RockAnthonyJohnson Tak naprawdę nie nazwałbym tego zwrotnym, ale to nie ma znaczenia. Ale dlaczego to jest problem? Jest to niezwykle powszechne. W rzeczywistości tak powstają prawie wszystkie struktury danych. Pomyśl o połączonej liście lub drzewie binarnym. Wszystkie są rekurencyjnymi strukturami danych, podobnie jak twój Roomprzykład.
ogrodnik
2
@RockAnthonyJohnson Niezmienne struktury danych są niezwykle powszechne, przynajmniej w programowaniu funkcjonalnym. W ten sposób można określić połączonej listy: type List a = Nil | Cons of a * List a. I binarne drzewo: type Tree a = Leaf a | Cons of Tree a * Tree a. Jak widać, oba są samoreferencyjne (rekurencyjne). Oto jak chcesz określić swój pokój: type Room = Nil | Open of {name: string, south: Room, east: Room, north: Room, west: Room}.
ogrodnik
1
Jeśli jesteś zainteresowany, poświęć czas na naukę Haskell lub OCaml; rozwinie twój umysł;) Pamiętaj również, że nie ma wyraźnego rozgraniczenia między strukturami danych a „obiektami biznesowymi”. Zobacz, jak podobna jest definicja twojej Roomklasy i a List w Haskell, który napisałem powyżej.
ogrodnik

Odpowiedzi:

10

Oczywiście nie można tego zrobić przy użyciu dokładnie opublikowanego kodu, ponieważ w pewnym momencie konieczne będzie skonstruowanie obiektu, który należy połączyć z innym obiektem, który nie został jeszcze zbudowany.

Są na to dwa sposoby (z których wcześniej korzystałem):

Korzystanie z dwóch faz

Wszystkie obiekty są konstruowane jako pierwsze, bez żadnych zależności, a po ich zbudowaniu zostają połączone. Oznacza to, że obiekty muszą przejść przez dwie fazy swojego życia: bardzo krótką fazę zmienną, po której następuje niezmienna faza, która trwa przez resztę ich życia.

Dokładnie taki sam problem występuje podczas modelowania relacyjnych baz danych: jedna tabela ma klucz obcy wskazujący na inną tabelę, a druga tabela może mieć klucz obcy wskazujący na pierwszą tabelę. W relacyjnych bazach danych jest to obsługiwane w taki sposób, że ograniczenia klucza obcego można (i zwykle są) określać za pomocą dodatkowej ALTER TABLE ADD FOREIGN KEYinstrukcji, która jest niezależna od CREATE TABLEinstrukcji. Najpierw utwórz wszystkie tabele, a następnie dodaj ograniczenia klucza obcego.

Różnica między relacyjnymi bazami danych a tym, co chcesz zrobić, polega na tym, że relacyjne bazy danych nadal zezwalają na ALTER TABLE ADD/DROP FOREIGN KEYinstrukcje przez cały okres istnienia tabel, podczas gdy prawdopodobnie ustawisz flagę „IamImmutable” i odrzucisz dalsze mutacje, gdy wszystkie zależności zostaną spełnione.

Korzystanie z leniwej inicjalizacji

Zamiast odniesienia do zależności przekazujesz delegata, który w razie potrzeby zwróci odwołanie do zależności. Po pobraniu zależności delegat nigdy nie jest wywoływany ponownie.

Delegat zwykle przyjmuje postać wyrażenia lambda, więc będzie wyglądał tylko nieco bardziej gadatliwie niż przekazywanie zależności konstruktorom.

(Mały) minus tej techniki polega na tym, że musisz zmarnować miejsce do przechowywania potrzebne do przechowywania wskaźników dla delegatów, które zostaną wykorzystane tylko podczas inicjalizacji wykresu obiektowego.

Możesz nawet stworzyć ogólną klasę „leniwego odniesienia”, która implementuje to, abyś nie musiał jej ponownie implementować dla każdego członka.

Oto taka klasa napisana w Javie, możesz łatwo transkrybować ją w C #

(Mój Function<T>jest jak Func<T>delegat 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 );
    }
}

Ta klasa ma być bezpieczna dla wątków, a funkcja „podwójnego sprawdzania” jest związana z optymalizacją w przypadku współbieżności. Jeśli nie planujesz być wielowątkowy, możesz usunąć wszystkie te rzeczy. Jeśli zdecydujesz się użyć tej klasy w konfiguracji wielowątkowej, przeczytaj o „idiomie podwójnego sprawdzania”. (To długa dyskusja wykraczająca poza zakres tego pytania).

Mike Nakis
źródło
1
Mike, jesteś genialny. Zaktualizowałem oryginalny post, aby uwzględnić implementację opartą na tym, co napisałeś o leniwej inicjalizacji.
Rock Anthony Johnson
1
Biblioteka .Net udostępnia leniwe odniesienie o trafnej nazwie Lazy <T>. Jak cudownie! Nauczyłem się tego od odpowiedzi na recenzję kodu opublikowaną na codereview.stackexchange.com/questions/145039/…
Rock Anthony Johnson
16

Leniwy wzorzec inicjalizacji w odpowiedzi Mike'a Nakisa działa dobrze w przypadku jednorazowej inicjalizacji między dwoma obiektami, ale staje się niewygodny dla wielu powiązanych ze sobą obiektów z częstymi aktualizacjami.

O wiele prostsze i łatwiejsze do zarządzania jest utrzymywanie połączeń między pokojami na zewnątrz samych obiektów pokojowych, w czymś takim jak ImmutableDictionary<Tuple<int, int>, Room>. W ten sposób zamiast tworzyć cykliczne odwołania, dodajesz do tego słownika jedno, łatwe do aktualizacji, jednokierunkowe odniesienie.

Karl Bielefeldt
źródło
Pamiętaj, że rozmawialiśmy o niezmiennych obiektach, więc nie ma żadnych aktualizacji.
Rock Anthony Johnson
4
Kiedy ludzie mówią o aktualizowaniu niezmiennych obiektów, mają na myśli utworzenie nowego obiektu ze zaktualizowanymi atrybutami i odwołanie się do tego nowego obiektu w nowym zakresie zamiast starego obiektu. Jednak za każdym razem jest to trochę nudne.
Karl Bielefeldt
Karl, proszę wybacz mi. Nadal jestem noobem zasad funkcjonalnych, hahaa.
Rock Anthony Johnson
2
To jest właściwa odpowiedź. Zależności kołowe powinny zasadniczo zostać zerwane i przekazane stronie trzeciej. Jest to o wiele prostsze niż programowanie złożonego systemu budowania i zamrażania obiektów zmiennych, które stają się niezmienne.
Benjamin Hodgson
Chciałbym dać jeszcze kilka + 1 ... Niezmienne lub nie, bez „zewnętrznego” repozytorium lub indeksu (czy cokolwiek innego ), prawidłowe podłączenie wszystkich tych pomieszczeń byłoby dość niepotrzebnie skomplikowane. I to nie zabrania Roomod pojawiające mieć te relacje; ale powinny to być metody pobierające, które po prostu czytają z indeksu.
svidgen
12

Sposobem na zrobienie tego w funkcjonalnym stylu jest rozpoznanie tego, co aktualnie konstruujesz: ukierunkowany wykres z oznaczonymi krawędziami.

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

Loch to struktura danych, która śledzi wiele pokoi i rzeczy oraz jakie są między nimi relacje. Każde połączenie „z” zwraca nowe, inne niezmienne lochy. Pokoje nie wiedzą, co jest na północ i południe od nich; książka nie wie, że jest w skrzyni. Loch zna te fakty, i że sprawa nie ma problemu z odniesieniami kołowymi ponieważ nie ma.

Eric Lippert
źródło
1
Studiowałem ukierunkowane wykresy i płynne konstruktory (i DSL). Widzę, jak to może zbudować ukierunkowany wykres, ale po raz pierwszy widziałem te dwa pomysły. Czy brakuje mi książki lub wpisu na blogu? A może tworzy ukierunkowany wykres po prostu dlatego, że rozwiązuje problem pytań?
candied_orange
@CandiedOrange: jest to szkic tego, jak mógłby wyglądać interfejs API. Właściwie zbudowanie leżącej u jego podstaw niezmiennej ukierunkowanej struktury danych graficznych zajęłoby trochę pracy, ale nie jest trudne. Niezmienny ukierunkowany wykres to po prostu niezmienny zestaw węzłów i niezmienny zestaw potrójnych (początek, koniec, etykieta), dzięki czemu można go zredukować do składu już rozwiązanych problemów.
Eric Lippert,
Tak jak powiedziałem, studiowałem zarówno DSL, jak i ukierunkowane wykresy. Próbuję dowiedzieć się, czy przeczytałeś lub napisałeś coś, co łączy je ze sobą, czy po prostu zebrałeś je, aby odpowiedzieć na to pytanie. Jeśli wiesz o czymś, co je łączy, bardzo bym chciał, gdybyś mógł mi to wskazać.
candied_orange
@CandiedOrange: Nie szczególnie. Wiele lat temu napisałem serię blogów na niezmiennym nieukierowanym grafie do tworzenia solvera sudoku z cofaniem się. Niedawno napisałem serię blogów na temat problemów z projektowaniem obiektowym dla zmiennych struktur danych w domenie wizardów i lochów.
Eric Lippert,
3

Kurczak i jajko mają rację. Nie ma to sensu w języku c #:

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

Ale to powoduje:

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

Ale to oznacza, że ​​A nie jest niezmienne!

Możesz oszukiwać:

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

To ukrywa problem. Pewnie A i B mają niezmienny stan, ale odnoszą się do czegoś, co nie jest niezmienne. Co może z łatwością pokonać punkt, czyniąc je niezmiennymi. Mam nadzieję, że C jest co najmniej tak samo bezpieczne dla wątków, jak potrzebujesz.

Istnieje wzorzec zwany zamrażaniem i rozmrażaniem:

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

Teraz „a” jest niezmienne. „A” nie jest, ale „a” jest. Dlaczego to jest w porządku? Dopóki nic innego nie wie o „a”, zanim się zamrozi, kogo to obchodzi?

Istnieje metoda thaw (), ale nigdy nie zmienia „a”. Tworzy zmienną kopię „a”, którą można aktualizować, a także zamrażać.

Minusem tego podejścia jest to, że klasa nie wymusza niezmienności. Procedura jest następująca. Nie możesz stwierdzić, czy jest niezmienny od tego typu.

Naprawdę nie znam idealnego sposobu rozwiązania tego problemu w c #. Wiem, jak ukryć problemy. Czasami to wystarczy.

Jeśli tak nie jest, stosuję inne podejście, aby całkowicie uniknąć tego problemu. Na przykład: spójrz na sposób implementacji wzorca stanu tutaj . Można by pomyśleć, że zrobiliby to jako okólnik, ale nie robią tego. Wyrzucają nowe obiekty za każdym razem, gdy zmienia się stan. Czasami łatwiej jest nadużyć pojemnika na śmieci niż dowiedzieć się, jak wydobywać jajka z kurcząt.

candied_orange
źródło
+1 za wprowadzenie mnie w nowy wzór. Najpierw słyszałem o zamrażaniu i rozmrażaniu.
Rock Anthony Johnson
a.freeze()może zwrócić ImmutableAtyp. które sprawiają, że jest to w zasadzie wzorzec budowniczego.
Bryan Chen
@BryanChen, jeśli to zrobisz, bzostanie zachowane odniesienie do starej zmiennej a. Chodzi o to, że a i bpowinien wskazywać na niezmiennych wersjami siebie przed zwolnieniem ich z resztą systemu.
candied_orange
@RockAnthonyJohnson To samo Eric Lippert nazwał niezmiennością Popsicle .
Zauważył
1

Niektórzy mądrzy ludzie już wyrazili swoje opinie na ten temat, ale myślę, że to nie jest obowiązkiem pokoju, aby wiedzieć, kim są jego sąsiedzi.

Myślę, że obowiązkiem budynku jest wiedzieć, gdzie są pokoje. Jeśli pokój naprawdę potrzebuje wiedzieć, że sąsiedzi przekazują mu INeigbourFinder.

tymtam
źródło