martes, 27 de mayo de 2008

Ejemplos de buena implementación

En la materia de POO, uno de los ejercicios que tienen que hacer es implementar un modelo de medidas y otro un autómata finito determinístico y no determinístico. Son ejercicios muy interesantes y que dan buenos ejemplos de problemas de modelado e implementación.
A continuación transcribo alguna de las cosas que les comenté por mail a los alumnos y que me parecen interesantes en general:

1) En el ejercicio de las medidas, la implementación del mensaje #*, que se puede utilizar para hacer cosas como: "diezMetros * 5" o "diezMetros * dosMetros", no utiliza polimorfismo sino un "if" para solucionar el problema de multiplicar por un número o por una medida. Por ejemplo:

Measure>>* aMeasure

^aMeasure class = self class
ifTrue: [ ... multiplicación de medidas, en muchos casos puesto el código acá directamente en vez de factorizarlo en un mensaje ]
ifFalse: [ ... multiplicación por un número ]

Esta solución adolece de varios problemas:
a) Restringe la solución a multiplicar medidas y cualquier otra cosa, asumiendo siempre que la otra cosa va a ser un número, lo cual está implícito y por lo tanto puede generar errores en la evolución del modelo. Para evitar este problema de evolución, una correcta solución sería:

^aMeasure class = self class
ifTrue: [ ... multiplicación de medidas, en muchos casos puesto el código acá directamente en vez de factorizarlo en un mensaje ]
ifFalse: [ (aMeasure isKindOf: Number)
ifTrue: [ ... multiplicación por un numero ]
ifFalse: [ Exception!!! -> El modelo no está preparado para multiplicar por cualquier otra cosa ]

b) La opción anterior, por supuesto que sigue estando distante de una buena solución, por el motivo que comente en el punto a (que restringe la multiplicación a lo que conocemos ahora que se puede multiplicar), pero también porque queda claro si nos fijamos con cuidado que el colaborador externo aMeasure no es un buen nombre, porque si es una medida, cómo puede ser un Number?. Esto tiene mal olor. Es este caso puede ser interpretado como que falta una abstracción que permita "juntar" el concepto de medida y de número en algo más abstracto, que en el caso de VisualWorks se llama ArithmeticValue. Por lo tanto, Measure debería subclasificar ArithmeticValue (igual que Number) y el colaborado externo se debería llamar "anArithmeticValue" en vez de aMeasure

c) Para no restringir la multiplicación a medidas y números, hay que utilizar la técnica que se denomina "double dispacth". La idea de esta técnica es que las decisiones la tomen los objetos enviándose mensajes en vez de los programadores por medio de un "if". La solución correcta para este caso sería:

Measure>>* anArithmeticValue

^anAritmeticValue multiplyMeasure: self

Measure>>multiplyMeasure: aMeasure

"En este caso estoy seguro que aMeasure es instancia de Measure, puesto que el mensaje lo envió una Measure"
^... (multiplicación de medidas)

Number>>multiplyMeasure: aMeasure

"Soy un número y me piden multplicar aMeasure por mi"
^Measure amount: aMeasure amount * self unit: aMeasure unit (o algo así)

Esta solución erradica el if y está preparada para el día de mañana si alguien observa que se puede multiplicar una medida por algo que no sea ni una medida ni un número... algo quizá medio difícil de ver en primera instancia, pero la puerta queda abierta para esa posibilidad (algún loco le gustaría poder multiplicar por un punto por ejemplo. Para el caso de VisualWorks no parece loco hacerlo puesto que Point subclasifica ArithmeticValue como también lo hace Complex)
Fijense que también el código queda automáticamente factorizado y en el caso de querer multiplicar por algo que no tiene sentido, por ejemplo un punto, automáticamente se genera un doesNotUnderstand y no hay que explícitamente manejar ese caso en el código, los objetos se encargan.

2) Otro ejemplo de código que tiene mal olor es este que pongo a continuación y tiene que ver con la creación de una función no determinística de un atómata finito:

funcionNoDeterministica
| dictionary |
dictionary := Dictionary new.
dictionary
add: (Association key: #(1 'a') value: (Set new add:7;add:6 ));
add: (Association key: #(7 'a') value: (Set new add:3 ));
add: (Association key: #(3 'b') value: (Set new add:5 ));
add: (Association key: #(6 'b') value: (Set new add:2));
add: (Association key: #(6 'a') value: (Set new add:4));
add: (Association key: #(4 'b') value: (Set new add:2; add:5)).

^TransitionFunction dictionary: dictionary.

Si lo analizamos un poco, veremos que:
a) Nombre "dictionary" no agrega valor, no representa su rol en el contexto. En esta caso es difícil pensar un mejor nombre y creo que tiene que ver con el problema de usar un diccionario para representar las transiciones, pero esto es solo una suposición.
b) Se utiliza el mensaje #add: en vez de #at:put:
c) No queda claro qué representa la key ni el value. Por qué se usa como key un Array? y el value? Parecería por el código que se espera que el value sea un Set, pero qué termina siendo?... observen bien el código.... termina siendo un número puesto que el mensaje #add: devuelve el colaborador externo, no el receptor del mensaje. Esto demuestra además que los test realizado no son buenos, no cubren todos los casos.
d) No sería más claro tener algo así:

| transitions |

transitions := OrderedCollection new
add: (Transition from: 1 to: 7 by: $a);
add: (Transition from: 1 to: 6 by: $a);
add: (Transition from: 7 to: 3 by: $a);
....
yourself.

^TransitionFunction with: transitions

jueves, 15 de mayo de 2008

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?

jueves, 8 de mayo de 2008

Ventajas del código autodocumentado

Este año hay un grupo muy activo en POO lo cual es muy bueno porque preguntan y hacen cosas más allá de lo que comúnmente sucede en esta materia.
Por ejemplo, el otro día en la lista de POO un alumno preguntó como hacer una búsqueda de algún String particular en los métodos. Pareciera que en VisualWorks no hay manera de hacerlo directamente usando las herramientas de desarrollo que ofrece, pero como esto es Smalltalk no cuesta nada escribir un conjunto de colaboraciones para hacerlo. Así se los propuse y, debido a que es un grupo muy interesante, generaron una solución.
La solución que generaron fue:

| resultado aBuscar bloque |

resultado := OrderedCollection new.
aBuscar := (Dialog request: 'Texto a buscar:' initialAnswer: '' windowLabel: 'Buscar' for: nil).
bloque := [:class :selector :aString | | method |
method := class compiledMethodAt: selector.
( method allLiterals anySatisfy: [:lit | lit isString and: [aString match: lit]])
ifTrue: [ resultado add: method definition]
].
Object allSubclasses do: [:class | class selectors do: [:sel | bloque value: class value: sel value: aBuscar ]].

RefactoringBrowser
openListBrowserOn: resultado
label: 'Resultados de búsqueda'
initialSelection: nil

Me parece interesante analizar los errores que posee dicho fragmento de código y como se puede escribir de otra manera para que sea más simple de entender. Como errores podríamos enumerar:
1) No tiene en cuenta el caso de presionar Cancel cuando se pregunta por el string. En dicho caso buscará el String ''
2) No tiene en cuenta aquellas clases que no tienen superclase que no sea Object
3) No busca el string en Object puesto que hace Object allSubclasses en vez de Object withAllSubclasses

Respecto a como está escrito, los nombre de las variables que usaron no están muy buenos. Dichos nombres deberían ser más explicativos, por ejemplo "resultado" no dice mucho sobre el objeto que referencia.
El objeto "bloque", también es un poco confuso, no solo por el nombre sino por como termina participando en las colaboraciones. Me imagino que la intención fue refactorizar el código puesto que de estar escribiendo esto en una clase ese "bloque" estaría representado por un método. Ahora, de ser así, seguramente ese método no se activaría al enviar el mensaje #bloque, lo que demuestra que "bloque" no es un buen nombre para dicho objeto.
Mi propuesta para resolver este problema es:

| methods stringToLookFor |

methods := OrderedCollection new.
stringToLookFor := Dialog request: 'Texto a buscar:' initialAnswer: '' windowLabel: 'Buscar' for: nil.
stringToLookFor isEmpty ifTrue: [^self].

Class rootsOfTheWorld do: [ :aRootClass |
aRootClass withAllSubclasses do: [ :aClass | | methodContainingStringToLookFor |
methodContainingStringToLookFor := aClass methodDictionary values select: [ :aMethod |
aMethod allLiterals anySatisfy: [ :aLiteral | aLiteral isString and: [ stringToLookFor match: aLiteral ]]].
methods addAll: methodContainingStringToLookFor ]].

RefactoringBrowser
openListBrowserOn: (methods collect: [ :aMethod | aMethod definition ])
label: 'Resultados de búsqueda'
initialSelection: nil

Esta solución resuelve los errores del script anterior. Creo que es un poco más fácil de leer, pero el hecho de tener tantos bloques anidados complica bastante su lectura. Para hacer un poco más entendible el script, utilizo la variable methodContainingStringToLookFor para explicar qué hace el conjunto de colaboraciones "aClass methodDictionary values select: ...". De esta manera no es necesario leer toda las colaboraciones para entender qué resulta al evaluarlas.
Sin embargo, la mejor solución sería modelar esto en una clase (olvidarnos del script...), puesto que al hacerlo se podría refactorizar bastante y hacer que el código quede más "autodocumentado".
De hacerlo, obtendríamos algo así:
...>>methodsContaining: aString

^Class rootsOfTheWorld inject: OrderedCollection new into: [ :methods :aRootClass |
methods addAll: (self methodsContaining: aString inAll: aRootClass withAllSubclasses).
methods]

...>>methodsContaining: aString inAll: aCollectionOfClasses

^aCollectionOfClasses inject: OrderedCollection new into: [:methods :aClass |
methods addAll: (self methodsContaining: aString in: aClass) ]

..>>methodsContaining: aString in: aClass

"Lamentablemente VisualWorks no define le mensaje #methods en Behavior, por eso trabajo con el methodDictionary. Esto rompe el encapsulamiento pero es una solución de compromiso para no modificar Behavior"
^aClass methodDictionary values select: [ :aMethod | self does: aMethod includes: aString ]

...>>does: aMethod includes: aString

^aMethod allLiterals anySatisfy: [ :aLiteral | aLiteral isString and: [ aString match: aLiteral ]].

Creo que así queda mucho más lindo y fácil de entender. Fijensé como desaparece la necesidad de definir la variable methodContainingStringToLookFor debido a que fue reemplazada por el envío de un mensaje, #methodsContaining:inAll: , que a mi gusto además transmite mejor la intención de qué están haciendo los objetos.
Fijensé también que los métodos #methodsContaining:in: y #does:includes: podrían haber sido implementados en Behavior y CompiledCode respectivamente, de tal manera que quedasen como #methodsContainingString: e #includesString:
Me parece interesante este caso como ejemplo de cómo se puede mejorar la legibilidad del código y de cómo así y todo en algo tan sencillo pueden haber varios errores.

miércoles, 7 de mayo de 2008

Programming as a Threory Building

Debido al curso que estoy dando en la UCA, volví a reeler el paper de Peter Naur que se llama "Programming as a Theory Building".

Es interesante que cuando uno relee lecturas, le impresionan partes distintas a las lecturas anteriores. Eso me pasó esta vez, donde lo que más me impresionó fue esta parte donde habla del "status" del programador: (si quieren leer todo el artículo, vayan a http://www.zafar.se/bkz/Articles/NaurProgrammingTheory)

"More generally, much current discussion of programming seems to assume that programming is similar to industrial production, the programmer being regarded as a component of that production, a component that has to be controlled by rules of procedure and which can be replaced easily. Another related view is that human beings perform best if they act like machines, by following rules, with a consequent stress on formal modes of expression, which make it possible to formulate certain arguments in terms of rules of formal manipulation. Such views agree well with the notion, seemingly common among persons working with computers, that the human mind works like a computer. At the level of industrial management these views support treating programmers as workers of fairly low responsibility, and only brief education.

On the Theory Building View the primary result of the programming activity is the theory held by the programmers. Since this theory by its very nature is part of the mental possession of each programmer, it follows that the notion of the programmer as an easily replaceable component in the program production activity has to be abandoned. Instead the programmer must be regarded as a responsible developer and manager of the activity in which the computer is a part. In order to fill this position he or she must be given a permanent position, of a status similar to that of other professionals, such as engineers and lawyers, whose active contributions as employers of enterprises rest on their intellectual proficiency.

The raising of the status of programmers suggested by the Theory Building View will have to be supported by a corresponding reorientation of the programmer education. While skills such as the mastery of notations, data representations, and data processes, remain important, the primary emphasis would have to turn in the direction of furthering the understanding and talent for theory formation. To what extent this can be taught at all must remain an open question. The most hopeful approach would be to have the student work on concrete problems under guidance, in an active and constructive environment."

viernes, 2 de mayo de 2008

Ejercicio de Distancia

El otro día hicimos en la facultad, durante POO, un ejercicio que me ha dado muy buenos resultados. El ejercicio consiste en modelar medidas de distancia, o sea un modelo capaz de expresar cosas como "3 metros", "5 centimetros + 10 metros", etc.
Es increíble como un tema que parece tan sencillo genera tantos modelos distintos, tantas ideas distintas sobre como resolverlo y ofrece una gran cantidad de temas para hablar y discutir.
También es interesante porque es un tema que se puede ampliar a medidas de cualquier tipo, como volumen, velocidad, tiempo, riqueza, etc. y por lo tanto como ejercicio siguiente deben hacerlo.
Lo que implemente este año a diferencia de los anteriores, es que para el modelo de medidas genéricas ellos tienen que escribir los test usando TDD, mientras que en el de distancias nosotros les proveemos los test y ellos solo los tienen que hacer andar.
Aún así, dándole los test, los diseños son distintos.... da para pensar no?