Identificar referencias mutuas en tipos de datos

En las definiciones de tipos de datos ocurre una referencia mutua cuando la definición de un tipo de dato se refiere a otro tipo de dato que, a su vez, hace referencia al primero, sea directa o indirectamente, formando lo que se conoce como un ciclo de referencia mutua.

En esta entrada se muestran dos ejemplos de identificación de referencias mutuas; uno con referencias directas y otro con indirectas. Para los dos se usan árboles de aridad arbitraria, que son una de las estructuras donde se dan referencias mutuas.

Referencias directas

Miremos esta representación de una jerarquía de archivos de sistema:

(define-struct elt (name data subs))
;; Element is (make-elt String Integer ListOfElement)
;; interp. An element in the file system, with name, and EITHER data or subs.
;;         If data is 0, then subs is considered to be list of sub elements.
;;         If data is not 0, then subs is ignored.

;; ListOfElement is one of:
;;  - empty
;;  - (cons Element ListOfElement)
;; interp. A list of file system Elements

En este caso, la definición del tipo de dato Element se refiere al tipo de dato ListOfElement. Y este último se refiere al tipo de dato Element. Entonces, estas dos referencias forman un ciclo de referencias mutuas como se ve en la Figura 1.

Figura 1.

Figura 1. Diagrama de tipos de referencia mostrando una autoreferencia (SR, por el inglés self-reference) y dos referencias (R), ordinarias a simple vista, que realmente son referencias mutuas (mr, por el inglés mutual reference) que forman un ciclo.

Referencias indirectas

En este caso no todos los ciclos de referencias mutuas son fáciles de encontrar. Las siguientes definiciones de datos son un ejemplo donde ocurren ciclos de referencias mutuas formados tanto por referencias directas como indirectas:

(define-struct woman (name sons daughters))
;; Woman is (make-woman String ListOfMan ListOfWoman)
;; interp. a woman with name, list of her sons, and list of her daughters

(define-struct man (name sons daughters))
;; Man is (make-man String ListOfMan ListOfWoman)
;; interp. a man with name, list of his sons, and list of his daughters

;; ListOfWoman is one of:
;; - empty
;; - (cons Woman ListOfWoman)
;; interp. a list of women

;; ListOfMan is one of:
;; - empty
;; - (cons Man ListOfMan)
;; interp. a list of men

Dibujemos todos los tipos de referencias que se ven a primera vista:

Figura 2.

Figura 2. Referencias (R) y autoreferencias (SR).

  • Woman hace referencia a ListOfMan y a ListOfWoman.
  • Man hace referencia a ListOfMan y a ListOfWoman.
  • ListOfWoman hace referencia a Woman y a sí mismo.
  • ListOfMan hace referencia a Man y a sí mismo.

Hay ciclos de referencias mutuas obvios entre Woman y ListOfWoman, y entre Man y ListOfMan:

Figura 3.

Figura 3. Identificación de referencias directas que forman ciclos de referencias mutuas.

Y resulta que las referencias (R) restantes, que parecen referencias comunes y corrientes, forman, indirectamente, ciclos de referencias mutuas. Para encontrar este tipo de ciclos escondidos, se puede hacer lo siguiente:

  1. Ponga el dedo al inicio de una línea de referencia.
  2. Siga la línea de referencia hasta el final.
  3. Intente llegar al inicio de la referencia siguiendo otras líneas de referencia (de cualquier tipo).

Si puede volver al principio, las aparentes líneas de referencia ordinarias que siguió para lograrlo son realmente referencias mutuas.

Usando los tres pasos anteriores, puede verificar que las referencias que quedan en la Figura 3 son referencias mutuas:

  1. Empiece en Woman.
  2. Siga la referencia a ListOfMan.
  3. Siga la referencia mutua a Man.
  4. Siga la referencia a ListOfWoman.
  5. Siga la referencia mutua a Woman.

Volvió al inicio. Entonces, todas las líneas que siguió para llegar al principio se convierten en referencias mutuas. Finalmente:

  1. Empiece en Man.
  2. Siga la referencia a ListOfWoman.
  3. Siga la referencia mutua a Woman.
  4. Siga la referencia a ListOfMan.
  5. Siga la referencia mutua a Man.

Aquí también, llegó al principio. Entonces el diagrama de referencias debería verse realmente así:

Figura 4.

Figura 4. Aparentes referencias ordinarias convertidas en referencias mutuas.

A la hora de diseñar funciones que operen sobre estos tipos de datos, todas estan referencias deberían poder identificarse también en el código como invocaciones a funciones que operan sobre el tipo de dato referenciado.

Fuentes de consulta

  • Módulo Mutual Reference del curso How To Code: Complex Data, de la University of British Columbia.

✮ Comentar ✮

Información de la entrada:

Autor

sirgazil

Temas