jueves, 26 de agosto de 2010

La maldición del programador

No suelo trabajar de esta forma pero recientemente una persona, un cliente, estableció contacto conmigo para que le hiciera un pequeño programa de control para cámaras de vídeo. Realmente el programa es sencillo pero hay que conocer un protocolo serie. Cuando le di el presupuesto el cliente me dijo que era excesivamente caro y que "se lo pensaría" (ya sabéis lo que significa esto, ¿no?). Las razones que me dio fueron las siguientes:
  1. Me había dado toda la información del protocolo serie para controlar la cámara de vídeo.
  2. Él había sido programador durante años y sabía lo que costaba hacer el programa. Literalmente me dijo "te hago un GUI en unos minutos".
  3. No podía cobrarle la depuración porque no sabía, por anticipado, qué fallos iba a haber en el programa (o si iba a haberlos).
  4. Podía usar los recursos que él tenía en su nave industrial. No necesitaba nada para programar, aparte del ordenador.
  5. El programa era muy pequeño y "en un rato se hacía".
La verdad es que, desde cierto punto de vista inocente, tiene razón en todo lo que me decía. Sin embargo, la realidad es bien distinta.
  1. Después de estudiar y entender el protocolo serie (por cierto, no estándar) que me dio, descubrí que era otro protocolo el que realmente necesitaba ya que había un dispositivo "adaptador inteligente" que traducía de un protocolo a otro. A esta conclusión no llegué de inmediato sino que tuve que estar bastantes horas investigando. Además, esta investigación no fue a vuelapluma. Tuve que recurrir a conocimientos que me ha costado muchos años y esfuerzo tener. Por mucho menos un electricista te cobra un buen monto. Ni que decir tiene que, para poder hacer el presupuesto, tuve que estudiarme este segundo protocolo (por cierto, tampoco estándar).
  2. Yo también hago un GUI, no en minutos, en segundos. Cojo un lápiz y un papel y te dibujo unos cuadraditos que son los botones. Ya está. Claro que quizás él se refería a usar un programa donde pones los botones y con una opción te genera el código. Bueno, "el código" es sólo para poner los botones, nada de la lógica que hay detrás. Porque no querrá nadie que la cámara haga zoom cuando pulses el botón de apagado o que te diga que la cámara está encendida cuando no hay cámara conectada o que intente contactar por un puerto cuando está conectada a otro. Tampoco querrá nadie que no mande los checksums en el protocolo, que no respete la temporización o que ignore las respuestas del dispositivo diciendo que no está preparado para nuevas instrucciones. Y todo eso hay que programarlo y probarlo. Así que no es GUI todo el programa. De hecho, la mayor parte del programa es la lógica de control. Aunque no se vea. Es más, como no se ve, es la realmente difícil de programar y probar.
  3. Jamás he escrito un programa de más de 1000 líneas que no tuviera un fallo. Es verdad que la gran mayoría de fallos son tontos y, o bien los descubre el compilador, o bien los descubres rápidamente al ejecutar. Esto es cierto, pero también tiene una cara negativa: los errores que no descubres rápidamente son los difíciles. Los que ocurren al azar. Los que se detectan haciendo una operación en concreto tras haber hecho cinco antes de una forma dada. Los que no se ven, pero están. Y, en definitiva, los que más calentamientos de cabeza dan. A todo esto hay que añadir, en el caso de este cliente, que cada error que se descubra implica tener que coger el coche, ir a su nave, ver el problema y trabajar en campo. Hasta los fontaneros cobran los desplazamientos, ¿no?
  4. De hecho, no necesito nada para programar. No necesito ni el ordenador, me basta el cerebro. Los grandes programadores, los programadores muertos, escribían sus programas en papel. Concretamente, el papel de la revista en el que lo publicaban. Pero volvamos al mundo real. En un trabajo manual liberas tu mente.  Si estás apretando tuercas y pensando en la vecina del segundo no creo que tu trabajo se vea afectado. Esto no ocurre con la programación. En la programación tienes que pensar el programa. Si dejas de pensar en el programa, no avanzas. Es más, suele ocurrir lo contrario. Suele ocurrir que dejas de programar, te vas, no sé, a comer y ¡sigues pensando en el programa! Estoy viendo la tele ¡trabajando! De paseo, ¡trabajando! En la ducha, ¡trabajando! ¿Cuento o no cuento esas horas de trabajo? Y lo digo en serio porque la ducha es unos de mis momentos más productivos, cuando se me ocurren las mejores ideas de diseño que simplifican un programa drásticamente. ¿Y ahora, qué hacemos?
  5. Esto se relaciona con el punto 2. El famoso "yo fui programador aficionado". Esta frase deja entrever que "y programar es divertido". No te voy a pagar por algo que, si te diviertes, no es trabajo. Bueno, es que hay una diferencia, yo llevo 26 años programando y llega un momento en el cual no te divierte tanto. En el cual, es un trabajo. El problema es que el programador aficionado se pone con el ordenador y se divierte. Se le pasan las horas y cree que ha sido menos tiempo. Así que cuando dice "en un rato se hace" no tiene en cuenta que su visión de la programación está sesgada. Su "rato" fue en realidad de muchas horas. Claro que, con el tiempo, sólo se recuerdan las cosas agradables. Un rato agradable.
Aquí acabo. Siento haber escrito tanto. No puedo decir estas cosas a la cara del cliente. Ya me siento mejor. Ha pasado ya tanto tiempo, décadas, y seguimos a vueltas con lo mismo. ¿Podrá ver el cliente algún día que la programación es un trabajo muy duro, aunque no sea un trabajo físico? ¿Es esta la maldición del programador?

domingo, 22 de agosto de 2010

Divide para sumar

Sigo maravillándome con los trucos para trabajar con los bits individualmente. Después de las últimas entradas escritas, traigo una con algo de trasfondo matemático.

Aritmética modular
La aritmética modular surge cuando trabajamos con los restos (o residuos) de una división con un divisor (o módulo) dado. Así, el residuo de 7 dividido entre (módulo) 3 es uno ya que 7=3·2+1. El teorema de la división nos indica que este valor existe y es único.
Los distintos lenguajes de programación incluyen tanto una operación de división como una operación de obtener el residuo. En la familia del C, se nota con el símbolo %.
Resulta que bajo un módulo dado, las operaciones de suma y multiplicación forman un anillo conmutativo. En todo caso, nos interesa la siguiente identidad

(a·b)%m == [(a%m)·(b%m)]%m

Bits y bytes
Por otra parte, cuando un número se almacena en base dos, cada bit se pondera a una potencia de dos. Esto es básico.


1001 = 1·8 + 0·4 + 0·2 + 1·1 = 9

Pero, ¿qué ocurre si obtengo el residuo de un número así? Probemos a hacer 9%7. El resultado es obviamente 2, pero ¿qué ocurre en las ponderaciones de bits?

9%7 = [1·(8%7) + 0·(4%7) + 0·(2%7) + 1·(1%7)]%7  = [1·1 + 0·4 + 0·2 + 1·1]%7 = 2%7 = 2

Es interesante ver que el bit que está con ponderacion 8 ahora pondera 1. Así que lo que estamos obteniendo es la suma de los dígitos octales módulo siete. Es decir, con números octales es fácil de calcular el resto módulo siete. Ejemplo:

0376252%7  = (3+7+6+2+5+2)%7 = 25%7 = 4

Si en vez de usar 7 usamos otro módulo, estaremos contando los dígitos en la base del siguiente número. En los números decimales tendríamos que usar módulo 9 y lo que obtenemos no es más que el criterio de divisibilidad por nueve: suma cifras y que éstas sean divisibles por nueve.

Divide para sumar
Ahora podemos utilizar este truco para sumar los bytes de un entero.

0xXXYYZZWW % 255 = (0xXX+0xYY+0xZZ+0xWW)%255

Siempre y cuando no llegue la suma a 255, la suma es exacta. Si fuera necesario sumar más de 255, se usarían operaciones AND y desplazamientos.  Se separa el número en dos, se suman dividiéndolos con módulo 65535 y luego se suman los resultados parciales. Algo más tedioso pero que se rentabiliza si de todas las maneras hay que hacer estas operaciones como ocurre en muchos algoritmos que trabajan con bits.

martes, 17 de agosto de 2010

Contando alteraciones

Hoy he inventado un pequeño algoritmo musical. Para entenderlo hay que saber un poquito de teoría musical, pero muy poquito. En concreto hay que saber qué es una escala y qué es una alteración.
Escalas, clases de tono y rotaciones binarias
En la música usual se trabaja con doce clases de tono. Es fácil ver que las teclas de un piano repiten su distribución cada doce (siete blancas y cinco negras). De estas doce clases de tono, una escala es un subconjunto de ellas. Representaremos a este conjunto con doce bits. A cero si no está en el conjunto a uno si está.


Por ejemplo, empezando en un DO, las teclas blancas del piano son 101011010101 y las teclas negras (obviamente) su complementario 010100101010. Aquí tenemos nuestras dos primeras escalas: La escala diatónica mayor natural y la escala pentatónica.
La escala mayor, como la hemos empezado en DO, tiene esa tonalidad y por eso es usual decir que es la es cala de DO mayor. Si por ejemplo quisiéramos la escala de RE mayor, deberíamos empezar por la nota RE que está dos teclas a la derecha (dos semitonos y en nuestra notación dos bits) del DO. Sería algo como 00101011010101.
Entonces tenemos catorce bits, y eso no puede ser porque sólo tenemos doce clases de tono. Lo que ocurre es que las clases de tono son cíclicas y por tanto la operación correcta para pasar de la escala en tonalidad de DO a tonalidad de RE es la rotación y no el desplazamiento de bits. Entonces, en vez de poner 00101011010101, rotamos a 011010110101.
Alteraciones, movimiento de bits y distancia
Ahora bien, las escalas musicales tienen una propiedad que se denomina máxima uniformidad. Esto significa que rotar la escala la cambia poco. De hecho, si comparamos la escala en DO (rotación 0) y la escala en RE (rotación de 2 bits) sólo hemos movido dos unos.
101011010101
011010110101
Mover un 1 en esta representación equivale a realizar una alteración musical. Existen dos tipos de alteraciones: sostenido si movemos el uno a la derecha (como en este ejemplo) o bemol si lo movemos a la izquierda. (Nota: Aquí consideramos que doble bemol son dos bemoles y doble sostenido dos sostendios)
Es sensato pensar en definir una distancia entre estas dos tonalidades de la escala mayor. En este ejemplo la distancia sería de dos sostenidos. Ahora queda el problema de definir el algoritmo que obtenga esta distancia.
El algoritmo
Un detalle importante es que si dos unos coinciden, pueden asumirse como no alterados. Por ejemplo:
01100
00110
Es igual pensar en mover cada 1 un bit a la derecha o pensar que el uno común no se mueve y se mueve el primero dos lugares a la derecha. El resultado es siempre el mismo: dos sostenidos.
La primera intención es usar un XOR (diferencia simétrica), pero hemos de saber si movemos a la izquierda o a la derecha por lo que mantendremos un signo.
01100
00110
0+0-0 //XOR con signo
El + significa que ahí hay un 1 a mover a la derecha y el - que hay un 1 a mover a la izquierda. Ahora hemos de contar el número de unos a mover y luego el número de posiciones a mover.
01100
00110
0+0-0 //XOR con signo
01100 // Número de unos que se mueven en cada bit
01222 // Suma de lo de arriba: Número total de posiciones movidas.
Finalmente, para contar sostenidos y bemoles, es mejor llevar dos acumuladores por separados.
011000110
001101100
0+0-0-0+0 //XOR con signo
011000000 // Número de unos que se mueven A LA DERECHA (sostenidos)
000001100 // Número de unos que se mueven A LA IZQUIERDA (bemoles)
012222222 // Suma de sostenidos.
000001222 // Suma de bemoles
Distancia total: 2 sostenidos + 2 bemoles = 4 alteraciones
Caminos conocidos y desconocidos
Si nos ponemos a calcular las distancias entre escalas encontramos algo conocido: el círculo de quintas. El círculo de quintas nos da la distancia entre dos tonalidades distintas de escalas mayores (o menores).
Existen otras escalas exóticas como la mayor doble armónica o la escala alterada cuya distancia no aparece en el círculo de quintas. En este caso el algoritmo de arriba nos dice que, por ejemplo, entre SOL menor y MI mayor doble armónica la distancia es
101101010110 //SOL menor
100111001101 //MI mayor doble armónica
00+0-00+-0+- //XOR con signo
001100010010 //Movimiento de sostenidos

000000000000 //Movimiento de bemoles (no hay)

001222233344 //Sostenidos 4

Así que hay una distancia de cuatro sostenidos.
La única limitación del algoritmo es el número de bits puestos a uno, que debe ser igual en las escalas a comparar. A fin de cuentas, el algoritmo mide alteraciones, y si no hay un bit a uno, no hay nada que alterar.

viernes, 13 de agosto de 2010

Otra chuchería binaria

Sigo buscando y encontrando algoritmos curiosos para manipular bits. Éste cuenta el número de bits puestos a uno. Es decir, el peso de Hamming. Realmente hay muchísimas variantes y mejoras, pero esta es la más elegante desde mi punto de vista.

int bitcount (unsigned int n) {
   int count = 0 ;
   while (n) {
       count++ ;
       n &= (n - 1) ;  
   }
   return count ; 
}