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.

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:

• 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:

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í:

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.