¿Cómo modelar una referencia circular entre objetos inmutables en C #?

24

En el siguiente ejemplo de código, tenemos una clase para objetos inmutables que representa una habitación. Norte, Sur, Este y Oeste representan salidas a otras habitaciones.

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

Así vemos, esta clase está diseñada con una referencia circular reflexiva. Pero debido a que la clase es inmutable, estoy atrapado con un problema de 'pollo o huevo'. Estoy seguro de que los programadores funcionales experimentados saben cómo lidiar con esto. ¿Cómo se puede manejar en C #?

Estoy tratando de codificar un juego de aventuras basado en texto, pero usando principios de programación funcionales solo por el simple hecho de aprender. ¡Estoy atrapado en este concepto y puedo usar algo de ayuda! Gracias.

ACTUALIZAR:

Aquí hay una implementación funcional basada en la respuesta de Mike Nakis con respecto a la inicialización diferida:

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
fuente
Esto se siente como un buen caso para la configuración y el Patrón del generador.
Greg Burghardt
También me pregunto si una habitación debe estar desacoplada del diseño de un nivel o escenario, para que cada habitación no sepa de las demás.
Greg Burghardt
1
@RockAnthonyJohnson Realmente no llamaría eso reflexivo, pero eso no es pertinente. ¿Por qué es eso un problema? Esto es extremadamente común. De hecho, así es como se construyen casi todas las estructuras de datos. Piense en una lista vinculada o un árbol binario. Todas son estructuras de datos recursivas, y tu Roomejemplo también.
cabeza de jardín
2
@RockAnthonyJohnson Las estructuras de datos inmutables son extremadamente comunes, al menos en la programación funcional. Así es como se define una lista enlazada: type List a = Nil | Cons of a * List a. Y un árbol binario: type Tree a = Leaf a | Cons of Tree a * Tree a. Como puede ver, ambos son autorreferenciales (recursivos). Aquí te mostramos cómo definir su habitación: type Room = Nil | Open of {name: string, south: Room, east: Room, north: Room, west: Room}.
cabeza de jardín
1
Si está interesado, tómese el tiempo para aprender Haskell u OCaml; expandirá su mente;) También tenga en cuenta que no hay una demarcación clara entre las estructuras de datos y los "objetos comerciales". Mira cuán similares son la definición de tu Roomclase y a List en el Haskell que escribí anteriormente.
cabeza de jardín

Respuestas:

10

Obviamente, no puede hacerlo utilizando exactamente el código que publicó, porque en algún momento necesitará construir un objeto que necesite estar conectado a otro objeto que aún no se ha construido.

Hay dos maneras en que puedo pensar (que he usado antes) para hacer esto:

Usando dos fases

Todos los objetos se construyen primero, sin dependencias, y una vez que se han construido, se conectan. Esto significa que los objetos necesitan pasar por dos fases en su vida: una fase mutable muy corta, seguida de una fase inmutable que dura todo el resto de su vida.

Puede encontrar exactamente el mismo tipo de problema al modelar bases de datos relacionales: una tabla tiene una clave externa que apunta a otra tabla, y la otra tabla puede tener una clave externa que apunta a la primera tabla. La forma en que esto se maneja en las bases de datos relacionales es que las restricciones de clave externa pueden (y generalmente son) especificadas con una ALTER TABLE ADD FOREIGN KEYdeclaración adicional que es independiente de la CREATE TABLEdeclaración. Entonces, primero crea todas sus tablas, luego agrega sus restricciones de clave externa.

La diferencia entre las bases de datos relacionales y lo que desea hacer es que las bases de datos relacionales continúan permitiendo ALTER TABLE ADD/DROP FOREIGN KEYdeclaraciones durante toda la vida útil de las tablas, mientras que probablemente establecerá un indicador 'IamImmutable' y rechazará cualquier otra mutación una vez que se hayan realizado todas las dependencias.

Usando la inicialización perezosa

En lugar de una referencia a una dependencia, pasa un delegado que devolverá la referencia a la dependencia cuando sea necesario. Una vez que se ha recuperado la dependencia, nunca se vuelve a invocar al delegado.

El delegado generalmente tomará la forma de una expresión lambda, por lo que se verá solo un poco más detallado que pasar las dependencias a los constructores.

La desventaja (pequeña) de esta técnica es que debe desperdiciar el espacio de almacenamiento necesario para almacenar los punteros a los delegados que solo se utilizarán durante la inicialización de su gráfico de objetos.

Incluso puede crear una clase genérica de "referencia diferida" que implemente esto para que no tenga que volver a implementarla para cada uno de sus miembros.

Aquí hay una clase escrita en Java, puede transcribirla fácilmente en C #

(Mi Function<T>es como el Func<T>delegado de 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 );
    }
}

Se supone que esta clase es segura para subprocesos, y el material de "doble verificación" está relacionado con una optimización en el caso de concurrencia. Si no planea ser multihilo, puede quitar todo eso. Si decide utilizar esta clase en una configuración de subprocesos múltiples, asegúrese de leer sobre el "idioma de verificación doble". (Esta es una larga discusión más allá del alcance de esta pregunta).

Mike Nakis
fuente
1
Mike, eres brillante. He actualizado la publicación original para incluir una implementación basada en lo que publicaste sobre la inicialización diferida.
Rock Anthony Johnson el
1
La biblioteca .Net proporciona una referencia perezosa, acertadamente denominada Lazy <T>. ¡Qué maravilloso! Aprendí esto de una respuesta a una revisión de código que publiqué
Rock Anthony Johnson
16

El patrón de inicialización perezosa en la respuesta de Mike Nakis funciona bien para una inicialización única entre dos objetos, pero se vuelve difícil de manejar para múltiples objetos interrelacionados con actualizaciones frecuentes.

Es mucho más simple y manejable mantener los enlaces entre las habitaciones fuera de los objetos de la habitación, en algo así como un ImmutableDictionary<Tuple<int, int>, Room>. De esa manera, en lugar de crear referencias circulares, solo está agregando una referencia unidireccional, fácil de actualizar, a este diccionario.

Karl Bielefeldt
fuente
Tenga en cuenta que estamos hablando de objetos inmutables, por lo que no hay actualizaciones.
Rock Anthony Johnson el
44
Cuando las personas hablan de actualizar objetos inmutables, se refieren a crear un nuevo objeto con los atributos actualizados y a referirse a ese nuevo objeto en un nuevo alcance en lugar del antiguo objeto. Sin embargo, eso se vuelve un poco tedioso cada vez.
Karl Bielefeldt
Karl, por favor perdóname. Todavía soy un novato en los principios funcionales, jaja.
Rock Anthony Johnson
2
Esta es la respuesta correcta. En general, las dependencias circulares deben romperse y delegarse a un tercero. Es mucho más simple que programar un complejo sistema de compilación y congelación de objetos mutables que se vuelven inmutables.
Benjamin Hodgson
Ojalá pudiera darle algunos +1 más ... Inmutables o no, sin un repositorio o índice "externo" (o lo que sea ), conseguir que todas estas salas se conecten correctamente sería innecesariamente complejo. Y esto no prohíbe la Roomde aparecer tener esas relaciones; pero, deberían ser captadores que simplemente leen del índice.
svidgen
12

La forma de hacer esto en un estilo funcional es reconocer lo que realmente está construyendo: un gráfico dirigido con bordes etiquetados.

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

Una mazmorra es una estructura de datos que realiza un seguimiento de un montón de habitaciones y cosas, y cuáles son las relaciones entre ellas. Cada llamada "con" devuelve una nueva mazmorra inmutable diferente . Las habitaciones no saben qué hay al norte y al sur de ellas; el libro no sabe que está en el cofre. El calabozo conoce esos hechos, y esa cosa no tiene problemas con las referencias circulares porque no hay ninguno.

Eric Lippert
fuente
1
He estudiado gráficos dirigidos y constructores fluidos (y DSL). Puedo ver cómo esto podría construir un gráfico dirigido, pero esta es la primera vez que veo las dos ideas asociadas. ¿Hay algún libro o publicación de blog que me haya perdido? ¿O esto produce un gráfico dirigido simplemente porque resuelve el problema de las preguntas?
candied_orange
@CandiedOrange: este es un boceto de cómo se vería la API. En realidad, construir la estructura de datos del gráfico dirigido inmutable subyacente requeriría algo de trabajo, pero no es difícil. Un gráfico dirigido inmutable es solo un conjunto inmutable de nodos y un conjunto inmutable de (inicio, final, etiqueta) se triplica, por lo que puede reducirse a una composición de problemas ya resueltos.
Eric Lippert
Como dije, he estudiado DSL y gráficos dirigidos. Estoy tratando de averiguar si has leído o escrito algo que reúne a los dos o si los has reunido para responder a esta pregunta en particular. Si sabes de algo que los une, me encantaría que pudieras señalarme.
candied_orange
@CandiedOrange: No particularmente. Hace muchos años escribí una serie de blogs sobre un gráfico inmutable no dirigido para hacer un solucionador de sudoku de seguimiento. Y escribí una serie de blogs más recientemente sobre problemas de diseño orientado a objetos para estructuras de datos mutables en el dominio de magos y mazmorras.
Eric Lippert
3

Pollo y un huevo están bien. Esto no tiene sentido en c #:

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

Pero esto hace:

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

¡Pero eso significa que A no es inmutable!

Puedes hacer trampa:

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

Eso esconde el problema. Claro, A y B tienen un estado inmutable, pero se refieren a algo que no es inmutable. Lo que fácilmente podría vencer el punto de hacerlos inmutables. Espero que C sea al menos tan seguro como lo necesite.

Hay un patrón llamado freeze-thaw:

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

Ahora 'a' es inmutable. 'A' no es pero 'a' es. ¿Por qué está bien eso? Mientras nada más sepa sobre 'a' antes de que se congele, ¿a quién le importa?

Hay un método thaw () pero nunca cambia 'a'. Hace una copia mutable de 'a' que puede actualizarse y luego congelarse también.

La desventaja de este enfoque es que la clase no impone la inmutabilidad. El siguiente procedimiento es. No se puede saber si es inmutable del tipo.

Realmente no conozco una forma ideal de resolver este problema en C #. Sé maneras de ocultar los problemas. A veces es suficiente.

Cuando no es así, uso un enfoque diferente para evitar este problema por completo. Por ejemplo: mire cómo se implementa el patrón de estado aquí . Uno pensaría que lo harían como referencia circular, pero no lo hacen. Producen nuevos objetos cada vez que cambia el estado. A veces es más fácil abusar del recolector de basura que descubrir cómo sacar huevos de las gallinas.

naranja confitada
fuente
+1 por presentarme un nuevo patrón. Primero, he oído hablar de congelación-descongelación.
Rock Anthony Johnson el
a.freeze()podría devolver el ImmutableAtipo. que lo hacen básicamente un patrón de construcción.
Bryan Chen el
@BryanChen si haces eso, entonces bqueda una referencia a la antigua mutable a. La idea es eso a y bdebe apuntar a versiones inmutables el uno del otro antes de lanzarlos al resto del sistema.
candied_orange
@RockAnthonyJohnson Esto también es lo que Eric Lippert llamó inmutabilidad Popsicle .
Visto el
1

Algunas personas inteligentes ya expresaron sus opiniones sobre esto, pero creo que no es responsabilidad de la sala saber cuáles son sus vecinos.

Creo que es responsabilidad del edificio saber dónde están las habitaciones. Si la sala realmente necesita conocer a sus vecinos, pase INeigbourFinder.

tymtam
fuente