Come modellare un riferimento circolare tra oggetti immutabili in C #?

22

Nel seguente esempio di codice, abbiamo una classe per oggetti immutabili che rappresenta una stanza. Nord, Sud, Est e Ovest rappresentano le uscite in altre stanze.

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

Quindi vediamo, questa classe è progettata con un riferimento circolare riflessivo. Ma poiché la classe è immutabile, sono bloccata da un problema di "pollo o uovo". Sono certo che i programmatori esperti con esperienza sanno come comportarsi con questo. Come può essere gestito in C #?

Sto cercando di codificare un gioco di avventura basato su testo, ma usando principi di programmazione funzionale solo per motivi di apprendimento. Sono bloccato su questo concetto e posso usare un aiuto !!! Grazie.

AGGIORNAMENTO:

Ecco un'implementazione funzionante basata sulla risposta di Mike Nakis riguardante l'inizializzazione pigra:

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();
    }
}
    
posta Rock Anthony Johnson 21.10.2016 - 23:31
fonte

5 risposte

9

Ovviamente, non puoi farlo usando esattamente il codice che hai postato, perché a un certo punto dovrai costruire un oggetto che deve essere connesso a un altro oggetto che non è stato ancora costruito.

Ci sono due modi in cui posso pensare (che ho usato prima) per fare questo:

Utilizzo di due fasi

Tutti gli oggetti sono costruiti per primi, senza alcuna dipendenza, e una volta che sono stati tutti costruiti, sono connessi. Ciò significa che gli oggetti devono attraversare due fasi della loro vita: una fase mutabile molto breve, seguita da una fase immutabile che dura per tutto il resto della loro vita.

È possibile riscontrare lo stesso identico tipo di problema durante la modellazione dei database relazionali: una tabella ha una chiave esterna che punta a un'altra tabella e l'altra tabella può avere una chiave esterna che punta alla prima tabella. Il modo in cui questo viene gestito nei database relazionali è che i vincoli di chiave esterna possono (e di solito sono) specificati con un'istruzione extra ALTER TABLE ADD FOREIGN KEY che è separata dall'istruzione CREATE TABLE . Quindi, prima crei tutte le tue tabelle, quindi aggiungi i vincoli delle chiavi esterne.

La differenza tra i database relazionali e ciò che si vuole fare è che i database relazionali continuino a consentire dichiarazioni ALTER TABLE ADD/DROP FOREIGN KEY per tutta la durata delle tabelle, mentre probabilmente si imposta un flag "IamImmutable" e si rifiutano qualsiasi ulteriore modifica dopo tutte le dipendenze sono stati realizzati.

Utilizzo dell'inizializzazione pigra

Invece di un riferimento a una dipendenza si passa un delegato che restituirà il riferimento alla dipendenza quando necessario. Una volta che la dipendenza è stata recuperata, il delegato non viene mai più richiamato.

Il delegato di solito assume la forma di un'espressione lambda, quindi apparirà solo leggermente più prolisso rispetto a passare effettivamente le dipendenze ai costruttori.

Il (minuscolo) lato negativo di questa tecnica è che devi sprecare lo spazio di archiviazione necessario per memorizzare i puntatori ai delegati che verranno utilizzati solo durante l'inizializzazione del tuo grafico oggetto.

Puoi anche creare una generica classe "lazy reference" che implementa questo in modo da non doverla implementare nuovamente per ognuno dei tuoi membri.

Ecco una classe simile scritta in Java, puoi facilmente trascriverla in C #

(Il mio Function<T> è come Func<T> delegato di 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 );
    }
}

Questa classe dovrebbe essere thread-safe, e il "double check" è correlato a un'ottimizzazione nel caso di concorrenza. Se non hai intenzione di essere multi-thread, puoi eliminare tutte queste cose. Se decidi di utilizzare questa classe in una configurazione multi-thread, assicurati di leggere l'argomento "double check idiom". (Questa è una lunga discussione oltre lo scopo di questa domanda).

    
risposta data 22.10.2016 - 00:43
fonte
16

Il modello di inizializzazione pigro nella risposta di Mike Nakis funziona bene per un'inizializzazione di una volta tra due oggetti, ma diventa ingombrante per più oggetti correlati tra loro con aggiornamenti frequenti.

È molto più semplice e gestibile mantenere i collegamenti tra le stanze al di fuori degli oggetti room stessi, in qualcosa di simile a ImmutableDictionary<Tuple<int, int>, Room> . In questo modo, invece di creare riferimenti circolari, stai solo aggiungendo un singolo riferimento aggiornabile, facilmente aggiornabile, a questo dizionario.

    
risposta data 22.10.2016 - 04:19
fonte
11

Il modo per farlo in uno stile funzionale è riconoscere quello che stai effettivamente costruendo: un grafico diretto con bordi etichettati.

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

Un dungeon è una struttura di dati che tiene traccia di un mucchio di stanze e cose, e quali sono le relazioni tra loro. Ogni chiamata "with" restituisce un nuovo dungeon immutabile diverso . Le camere non sanno cosa sia a nord ea sud di loro; il libro non sa che è nel petto. Il dungeon conosce quei fatti e quella cosa non ha problemi con i riferimenti circolari perché non ce ne sono.

    
risposta data 14.11.2016 - 23:49
fonte
3

Il pollo e un uovo è giusto. Questo non ha senso in C #:

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

Ma questo:

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

Ma ciò significa che A non è immutabile!

Puoi imbrogliare:

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

Questo nasconde il problema. Certo, A e B hanno uno stato immutabile, ma si riferiscono a qualcosa che non è immutabile. Il che potrebbe facilmente sconfiggere il punto di renderli immutabili. Spero che C sia almeno un thread sicuro di cui hai bisogno.

C'è un modello chiamato freeze-thaw:

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

Ora 'a' è immutabile. 'A' non è che 'a' è. Perché va bene? Fintanto che nient'altro sa di "a" prima che sia congelato, a chi importa?

C'è un metodo thaw () ma non cambia mai 'a'. Crea una copia mutabile di 'a' che può essere aggiornata e poi congelata.

Lo svantaggio di questo approccio è che la classe non impone l'immutabilità. La seguente procedura è. Non puoi dire se è immutabile dal tipo.

Non conosco davvero un modo ideale per risolvere questo problema in c #. Conosco i modi per nascondere i problemi. A volte basta.

Quando non lo è, utilizzo un approccio diverso per evitare del tutto questo problema. Ad esempio: guarda come viene implementato lo schema di stato qui . Penseresti che lo farebbero come riferimento circolare ma non lo fanno. Spingono fuori nuovi oggetti ogni volta che cambia lo stato. A volte è più facile abusare del garbage collector per capire come estrarre le uova dai polli.

    
risposta data 22.10.2016 - 01:10
fonte
1

Alcune persone intelligenti hanno già espresso le loro opinioni su questo, ma penso che non è responsabilità della stanza sapere quali sono i suoi vicini.

Penso che sia responsabilità del palazzo sapere dove sono le stanze. Se la stanza ha davvero bisogno di sapere quali sono i suoi vicini, passa INeigbourFinder.

    
risposta data 15.11.2016 - 01:49
fonte