Igualdad de Set

Esta semana hubo una discusión muy interesante en la lista de la materia de la UBA de POO sobre el problema de la igualdad de Set. El problema surgió porque un grupo haciendo un TP compararon Sets y les dió false cuando esperaban que el resultado sea true. Por ejemplo, si evaluamos:

(Set with: 1 with: 2) = (Set with: 1 with: 2)

el resultado es false y no true como se esperaría intuitivamente.
Fácilmente se puede deducir que este comportamiento se debe a que el mensaje #= no está redefinido en Set de tal manera que verifique si su contenido es el mismo, sino que usa la implementación otorgada por Object que define la igualdad como identidad, o sea, dos objetos son iguales si son idénticos, lo que significa que ocupan "la misma posición de memoria".
Hago esta aclaración puesto que la identidad de Smalltalk no es lo mismo que la identidad "filosófica". En Smalltalk pueden existir dos o más objetos que representen el mismo ente de la realidad y que por lo tanto cuando se los compare por identidad devuelvan false, sin embargo en la realidad hay un único ente que posee esa identidad. Por ejemplo:

Date today == Date today

Esta colaboración devuelve false, sin embargo el día de hoy (el ente de la realidad) es único e idéntico a si mismo. Es por este motivo que nunca hay que usar el mensaje #== a menos que explícitamente se necesite verificar si dos objetos ocupan la misma posición de memoria, algo que solo sucede en aquellos modelos relacionados con problema computacionales (por ejemplo frameworks mapeo relacionales, modelos de objetos distribuidos, etc.).
Volviendo al tema de la comparación de conjuntos, luego de varios emails de idas y vueltas en la lista (y un par de errores de mi parte), quedó claro que no se puede fácilmente implementar ese comportamiento y por otro lado tampoco es sencillo darle una semántica clara a esta comparación cuando se están utilizando conjuntos definidos por comprensión (aporte de Daniel Altman que quedó plasmado en la tesis que hizo junto a Hernán Tylin).
Uno de los problemas que surge al implementar el #= en Set es que se debe definir si solo se será true para aquellos casos en que se comparen conjuntos. Algo que yo había pensado es que la comparación debería devolver true si las colecciones comparadas tenían los mismos objetos, más allá de como están implementadas, pero la realidad es que no es sencillo implementarlo así y tampoco tiene sentido semánticamente. Por ejemplo:

(Set with: 1 with: 2) = (OrderedCollection with: 1 with: 1 with: 2)

¿Debería dar true o false?. Cualquier decisión que se tome al respecto es arbitraria. Por lo tanto el #= solo debería devolver true si se comparan conjuntos. Esa es la decisión que tomaron los implementadores de Squeak, donde el #= en Set está definido de la siguiente manera:

= aSet
self == aSet ifTrue: [^ true]. "stop recursion"
(aSet isKindOf: Set) ifFalse: [^ false].
self size = aSet size ifFalse: [^ false].
self do: [:each | (aSet includes: each) ifFalse: [^ false]].
^ true

Fijensé que es necesario que aSet sea instancia de Set o de alguna de sus subclasses. Esto restringe la comparación a que solo devolverá true si se comparan conjuntos. Sin embargo tiene la desventaja de no poder implementar un conjunto fuera de la jerarquía de Set y poder compararlo por igual con un Set puesto que siempre dará falso.
Una vez hecha esta salvedad, surge el problema de cómo implementar el #hash en Set, puesto que al haber implementado el #=, tengo que implementar un algoritmo de hash que cumpla con la condición que dos objetos iguales deben tener el mismo hash. Para la implementación de Object, el hash viene dado utilizando un número que se asigna a cada objeto que se crea y que se almacena en su header (fijensé que no se puede usar la posición de memoria puesto que la misma puede cambiar debido al garbage collector).
La implementación de Squeak es la siguiente:

hash

| hash |

hash := self species hash.
self size <= 10 ifTrue: [self do: [:elem | hash := hash bitXor: elem hash]].
^hash bitXor: self size hash

Podemos observar que se realiza un trade-off entre obtener un buen número y performance. Un buen número estaría dado a partir del hash de los objetos que contiene el conjunto, pero recorrer todo un conjunto puede ser time-consuming y por eso se limita a hacerlo solo en el caso de tener 10 o menos elementos.
Por lo tanto, implementar el #= en Set como uno intuye que debería funcionar no es tan sencillo, tiene sus complicaciones y trade-offs.
Una solución que me propuso Nicolás Kicillof, quién está trabajando en Microsoft en USA, es hacer como hacen ellos en su lenguaje de verificación en donde cada vez que se crea un conjunto, se verifica si el mismo no existe y de existir se devuelve el mismo. O sea, hablando mal y pronto, usan los conjuntos como los símbolos de Smalltalk. Esto implica que los conjuntos son inmutables y por ende tienen que tener un buen algoritmo de búsqueda para asegurarse de no tardar mucho cuando tienen que verificar si ya existe el conjunto (lo cual nos lleva nuevamente al hash...)
Otra solución es la que propone Daniel Altman, la cual crea una nueva manera de ver el problema completamente distinto y que me parece sumamente interesante y acertada. Transcribo lo que Daniel escribió en la lista porque no tiene desperdicio:

"[...] un Set en computación sea distinto del de la matemática, es el dinamismo que hay en el mundo de los objetos, cosa que no ocurre en principio en la matemática.
Es decir, un objeto matemático nunca tiene un estado que cambia.
Basta probar que dos conjuntos tienen los mismos elementos para demostrar que son iguales. Qué pasa en Squeak? Los elementos contenidos en un conjunto cambian a lo largo del tiempo.
Acá entra en juego una consideración bastante importante: es lo mismo hablar de conjuntos como simples “contenedores de elementos” (o sea, básicamente una estructura de datos) que hablar de un conjunto como un ente que tiene una semántica propia?
Para mí, los conjuntos interesantes son los segundos, los que tienen semántica. En ese caso un cambio en el ambiente, o en algún objeto cualquiera, pueden hacer que un elemento pertenezca o deje de pertenecer al conjunto. (por ejemplo, imaginen el conjunto de los objetos que responden true al mensaje #foo).
De ahí se desprende que la manera de comprar la igualdad de conjuntos sería comparar su semántica."

Este comentario quedó a mi entender claramente definido con un ejemplo que escribió más adelante en otro mail:

"Ejemplo: tenes el conjunto de las facturas impagas de una empresa por una
lado, y el conjunto de todas las facturas de la empresa por otro. Esos
conjuntos pueden tener los mismos elementos si nadie pagó ninguna factura,
pero son claramente distintos."

Un concepto muy interesante, ¿no les parece?