Relaciones binarias

Estos días he estado algo ocioso y, leyendo algún que otro artículo, me he encontrado otra vez con un orden débil estricto. No sé qué trauma tengo con este tipo de orden que nunca me acuerdo de su definición. Así que me he puesto a hacer un diagrama-póster con las distintas relaciones binarias y cómo se definen unas en otras según se van añadiendo propiedades. Lo que me ha quedado ha sido lo siguiente.
Para ver bien los detalles es mejor usar este pdf.

Selección con el preprocesador

Después de hablar de las macros hace unos días, me he dedicado a investigar algo más sobre cómo funciona el preprocesador de C/C++. Está muy limitado, pero tiene algunas posibilidades.

Usando #if/#endif  es posible seleccionar parte de código, pero no podemos usar #if/#endif dentro de una macro. Es decir algo como esto no funciona

#define SELECCIONA(a,b,c)  #if a \

b \

#else \

c \

#endif

El motivo es que el preprocesador es muy tonto y sus comandos (que empiezan por #) sólo son reconocidos a principio de línea. Debido a que el \ a final de línea significa que se sigue en la siguiente línea como si fuera esta, la macro anterior sería equivalente a

#define SELECCIONA(a,b,c)  #if a b #else c #endif

Por lo que ni el #if ni el #else ni el #endif son reconocidos como comandos de preprocesador.

La solución es algo enrevesada, pero funciona y es usada en boost::preprocesor. Se basa en el concatenador de tokens. Es un operador especial (no es un comando) del preprocesador. Se escribe ##. El resultado de esta concatenación es agrupar dos identificadores en uno.

#define CONCATENA(a,b) a ## b

CONCATENA(hola, adios) //Equivalente a escribir    holaadios

Debido a que el preprocesador vuelve a expandir el resultado de sus macros, es fácil usar el siguiente truco para la selección.

#define IF_TRUE(t,e) t

#define IF_FALSE(t,e) e

#define IF(c,t,e) IF_##c (t, e)

IF(TRUE, bien, mal) //Se expande a IF_TRUE(bien,mal) y se vuelve a expandir a  bien

Ahora podemos combinar este truco con la técnica explicada hace unos días para crear código opcionalmente.

Los estados corrientes de MIDI

MIDI
MIDI (Musical Instrument Digital Interface) es una interfaz multinivel (físico y enlace) ideado en 1982 que transmite información musical entre dispositivos compatibles. La forma de transmisión es mediante una comunicación serie.
La idea principal es que se transmite información musical, no de audio. Los mensajes que se transmiten los dispositivos son del tipo "toca esta nota" y "sube el volumen".
Lo más curioso del protocolo de enlace es que siempre se transmiten bytes, pero los hay de dos tipos.

• Los que tienen a 1 su bit más significativo son los llamados "códigos de estado".
• Los que tienen a 0 su bit más significativo son los datos de esos códigos de estado.

¿Y cómo funciona todo esto? Imaginemos que queremos tocar una nota. El código de estado para enviar una nota es (en binario) 0b10010000. Después hemos de introducir los datos. Dos para tocar una nota: 0b00111100 que indica la nota do central y 0b01010000 que es una velocidad de nota de 80.
La secuencia enviada por el cable sería:

• 0b10010000 Código de estado: tocar nota
• 0b00111100 Nota do central
• 0b01010000 Volumen 80

El uso del bit que distingue entre datos y estados es fundamental si conectamos un cable MIDI en mitad de una transmisión. Inicialmente se ignoran todos los datos hasta llegar al primer estado y a partir de ahí "enganchamos" y empezamos a trabajar.


Comprimiendo datos MIDI
La distinción entre códigos de estado y datos tiene otra función de compresión de la información. Es el llamado "running status" o, en una traducción a vuelapluma, los estados corrientes. Es bien sencillo. Si queremos transmitir dos notas, ¿para qué repetir el código de estado? Se asume el anterior. Entonces, la siguiente secuencia tendría este significado:

• 0b00010011 Dato inesperado: se ignora.
• 0b10010000 Código de estado: tocar nota
• 0b00111100 Nota do central
• 0b01010000 Velocidad 80
• 0b01000000 ¡Repetimos código de estado! Nota mi
• 0b00111100 Velocidad 80
• 0b01000011 ¡Repetimos código de estado! Nota sol
• 0b00111100 Velocidad 80
• 0b10000000 Código de estado: parar nota
• 0b00111001 Nota la
• 0b01000000 Velocidad 64
• 0b10010000 Código de estado: tocar nota
• 0b01001000 Nota do (siguiente octava)
• 0b01010000 Velocidad 80

Más compresión
Finalmente, existe un ligero cambio en el significado de "tocar nota" para comprimir más aún los datos. Debido a que lo más común es tocar nota y parar nota, es posible parar notas usando velocidad cero en "tocar nota". De esta manera se evita enviar el código de estado para parar nota y volverlo a enviar para seguir tocando. El único inconveniente de este sistema es que no puedes decir la velocidad del parado de la nota que se toma por defecto 64.
Con este truco la secuencia de arriba quedaría:

• 0b00010011 Dato inesperado: se ignora.
• 0b10010000 Código de estado: tocar nota
• 0b00111100 Nota do central
• 0b01010000 Velocidad 80
• 0b01000000 ¡Repetimos código de estado! Nota mi
• 0b00111100 Velocidad 80
• 0b01000011 ¡Repetimos código de estado! Nota sol
• 0b00111100 Velocidad 80
• 0b00111001 ¡Repetimos código de estado! Nota la
• 0b00000000 Velocidad 0 = parar nota la
• 0b01001000 ¡Repetimos código de estado! Nota do+
• 0b01010000 Velocidad 80

A lo largo de la transmisión esta pequeña compresión ahorra muchos bytes que, en una línea serie a velocidades de 1982, es una gran diferencia.
Desgraciadamente, estos detalles perduran en el tiempo hasta hoy en día y, de vez en cuando, le da algún que otro quebradero de cabeza a los desarrolladores.

Memento command

El patrón de diseño memento es muy simple y bastante útil. Como todo en la vida, también tiene sus puntos negativos. Por esta razón existe otro patrón de diseño llamado command que soluciona esos problemas.

El patrón de diseño Memento

Supongamos que queremos hacer un sistema de Undo/Redo. Esto significa que, hagamos la acción que hagamos sobre un objeto que llamaré primario, hemos de tener la posibilidad de volver a un estado anterior. (Nota: Llamo acción a una operación que modifica el estado.)

El patrón de diseño memento resuelve este problema y es muy sencillo. Lo que hay que hacer es incluir en el objeto dos operaciones:

• Guarda estado
  
• Recupera estado

Estas operaciones no son acciones en el sentido de modificar el estado, incluso al recuperar el estado lo que hacemos es volver a un estado anterior, no modificar el actual.

La operación que guarda el estado lo que hace es generar un objeto con el estado encapsulado dentro. A este objeto se le llama el objeto memento (recuerdo). Este objeto no tiene operaciones y lo único que se puede hacer con él es pasarlo a "recupera estado". Al recuperar estado no se destruye el memento, sólo se usa para recuperar el estado.

De esta manera:

• Se reifica el estado en un objeto memento. A partir de este momento se puede guardar, ordenar, etiquetar y, en general, gestionar los estados.
• El objeto memento es opaco no necesitamos tener conocimiento de cómo es ese estado por dentro.
• Objetos memento de objetos primarios de distinto tipo deberán tener distinto tipo, de esta forma se mantendría la seguridad del tipado.
• La idea de copiar y restaurar estados es simple y fácil de entender.

Sin embargo, el patrón memento tiene un gran problema. Siempre se guarda todo el estado y este puede ser muy grande. Si quisiéramos tener un sistema de Undo/Redo que recuerde muchos estados anteriores, el problema del almacenamiento de los estados llega a ser costoso en términos de uso de memoria.

Hacia un sistema de estados diferencial

La solución obvia es hacer un sistema de cambio de estados diferencial. En este sistema sólo se guardan los cambios entre dos estados. De hecho, la operación "Undo" suele deshacer únicamente una acción cada vez. ¿Por qué guardar cambios de estado completos cuando sólo es una acción la involucrada?

Ideemos entonces un sistema que por cada acción genere un objeto "minimemento" que indique cómo se deshace esa acción desde el estado actual. Llamaré a estos objetos átomos.

Ahora las dos operaciones del objeto primario serían:

• Obtener el átomo.
  
• Realizar "undo" usando el átomo.

Gráficamente sería así:

He sido cuidadoso en distinguir los objetos que existen en memoria (son los sombreados en azul) y los que existieron pero que ahora no existen (los de relleno blanco).

Este pequeño cambio que hemos hecho conlleva una gran pérdida. Ahora no tenemos objetos memento y si queremos pasar del estado 0 al estado 3 no basta con usar el átomo C. Tenemos que usar los átomos A, B y C en ese orden. De hecho, si intentásemos usar el átomo C sobre el estado 0 tendríamos un resultado inesperado ya que los átomos sólo deshacen una acción. En concreto, el átomo C la acción que va del estado 3 al 2. Por esa razón, deshacerla tiene que ser forzosamente del estado 2 al 3. En definitiva: al usar un sistema diferencial se añade una precondición que no existía en la operación de "recuperar estado" con el patrón memento.

En principio, no pasa nada ya que de todas formas podemos volver a cualquier estado anterior y, con un pequeño cambio, posterior.

Rehaciendo estados

Supongamos que hemos aplicado con éxito los átomos A, B y C de manera que hemos vuelto al estado 3. Como ocurría con el patrón memento, esto no significa que hayamos destruido los átomos A, B y C. De hecho, podríamos usarlos para volver a aplicar las acciones y llegar de nuevo al estado 0.

Esto sólo implicaría tener que añadir una nueva operación de realizar "redo" usando un átomo.

El lector astuto habrá visto que lo que hacen los átomo es reificar las acciones. Es decir, las acciones son objetos ahora (acción=átomo). Esta idea es la que subyace al patrón de diseño command.

Existe realmente un pequeño cambio para llegar al patrón de diseño command. Nosotros venimos del patrón memento y es el objeto primario el que tiene las operaciones "undo" y "redo". En el caso del patrón command estas operaciones están en el propio átomo que guardará internamente una referencia al objeto primario.

Las ideas clave del patrón de diseño command son:

• Las acciones son objetos. Si quieres modificar el objeto primario lo que hay que hacer es crear un objeto acción del tipo adecuado.
  
• Sólo las acciones modifican el objeto primario.
• Las acciones, al ser objetos, pueden anotarse, extenderse, heredarse, etc. Por esa razón pueden hacerse, deshacerse y rehacerse. Si fueran sólo una llamada, sólo podrían hacerse.
  

Chuchería binaria

Me he encontrado con el problema de, dado un número entero, calcular la siguiente potencia de dos. Por ejemplo, del número cinco obtendría ocho. Este problema es muy usual. La restricción de ser potencia de dos aparece en muchos algoritmos. Por ejemplo, en el cálculo de FFT.

Hay un algoritmo bastante curioso para resolver este cálculo. Es el que sigue:

n = n - 1;
n = n | (n >> 1);
n = n | (n >> 2);
n = n | (n >> 4);
n = n | (n >> 8);
n = n | (n >> 16);
...
n = n | (n >> (bitspace / 2));
n = n + 1;

Depende del tamaño de palabra que usemos para almacenar los enteros y no funciona en valores menores o iguales que cero. De todas las maneras, hace lo que tiene que hacer de forma maravillosa.