martes, 29 de junio de 2010

Macros como ligazón semántica

Existen multitud de ocasiones en los cuales hay que sincronizar dos (o más) partes de un mismo programa. Generalmente los lenguajes de programación actuales no permiten expresar este tipo de invariantes fácilmente. Sin embargo, existe un pequeño truco para hacerlo mediante macros.

El problema

Supongamos que tenemos una enumeración

enum E { A, B, C };

Y queremos tener una lista con los nombres de los elementos de la enumeración.

static char *N[] = {"A", "B", "C"};

¿Qué pasa si años después en un ciclo de mantenimiento hay que añadir un nuevo elemento a la enumeración?

enum E { A, D, B, C };

Existe la posibilidad de que nos olvidemos de actualizar la lista de nombres. Nos encontramos con que el elemento D ahora tiene nombre "B". Es un error que se detectará (o no) ejecutando el programa y probándolo.

La solución

Lo que tenemos que hacer es tener una única lista y derivar las otras dos a partir de esta primera. La dificultad reside en que los elementos del lenguaje de programación que estamos usando son muy distintos entre sí: por un lado símbolos y por otro cadenas literales.

La única forma de actuar es mediante un sistema que trabaje indiferentemente sobre ambos tipos de elementos. Ese sistema en muchos lenguajes es el preprocesador de macros.

#define VALORES X(A, "A") X(B, "B") X(C, "C")

Ahora transformamos esos valores definiendo la macro X a lo que queramos (no nos olvidemos de la coma).

#define X(x, y) x,
enum E { VALORES };
#undef X

El preprocesador primero sustituirá VALORES por toda la lista

#define X(x, y) x,
enum E { X(A, "A") X(B, "B") X(C, "C") };
#undef X

Luego verá que aún tiene X por evaluar y lo hará:

#define X(x, y) x,
enum E { A, B, C, };
#undef X

Luego podrá descartar X ya que no se usa.

enum E { A, B, C, };

Casi todos los lenguajes de programación permiten una coma terminal para facilitar la construcción de herramientas que generen código fuente automáticamente. Como en este caso. Esta coma terminal se ignora por lo que al final tenemos lo que queríamos.

enum E { A, B, C };

Conclusiones

Es inmediato ver que si en vez de usar esa definición de X hubiéramos usado otra, tendríamos nuestra lista de nombres.

#define X(x, y) y,
static char *N[] = { VALORES };
#undef X

También es inmediato comprobar que hemos ligado la generación de la enumeración con la generación de la lista. De esta forma, si modificamos nuestros valores, automáticamente se modificarán ambas partes del código.

#define VALORES X(A, "A") X(D, "D") X(B, "B") X(C, "C")

Es justo lo que queríamos: ligar semanticamente dos partes del código de forma automática. Ahora es imposible que nos confundamos dándole a D el nombre "B" como ocurría antes.

Referencias: Walter Bright - The X Macro

viernes, 25 de junio de 2010

Constantes y constantes

Hay un sutil hecho en los lenguajes de programación compilados que, aunque de sobra conocido en el mundo de la creación de compiladores, no lo es tanto por los programadores en general. Es la diferenciación entre constantes estáticas y constantes dinámicas.

Constantes estáticas

Imaginemos que en nuestro lenguaje de programación tenemos definida una función a la que queremos llamar con el argumento 3. Esto podría codificarse de la siguiente forma:

f(3)

El resultado de la compilación de la línea anterior es un código ejecutable que realiza dos acciones:

  • Introducir el valor 3 en los argumentos de llamada
  • Llamar al código de la función cuyo nombre es "f"
  • Tomar el resultado de la llamada como resultado del programa

Es muy sencillo introducir ahora una constante que tenga el valor 3 y llamar a la misma función con esta constante.

const A = 3
f(A)

El resultado de la compilación de este nuevo programa no es más que el mismo código. El compilador, acertadamente, ha sustituido el símbolo "A" por el valor 3 antes de generar el código ejecutable (es lo que se llama propagación de constantes). Esto significa que el programa anterior es completamente equivalente al inicial.

Como todas las transformaciones que hacemos ocurren a la hora de compilar (de hecho el código ejecutable resultante es idéntico en ambos casos) a este tipo de constantes se las llama constantes estáticas.

Plegado de constantes

Imaginemos que ahora queremos realizar la siguiente llamada a la misma función "f".

f(1+2)

El compilador tiene ahora dos opciones. La primera es la generación de código ejecutable directa. Este código ejecutable sería algo como:

  • Introduce el valor 1 en los argumentos de llamada (para la suma)
  • Introduce el valor 2 en los argumentos de llamada (para la suma)
  • Llamar al código de la función suma
  • Introducir el resultado de la llamada en los argumentos de una nueva llamada (para "f")
  • Llamar al código de la función cuyo nombre es "f"
  • Tomar el resultado de la llamada como resultado del programa

La segunda opción que puede tomar el compilador es esforzarse antes de generar el código en resolver las operaciones que se realicen sobre constantes. En este caso primero sumaría 1+2 y obtendría el valor 3 y, luego, generaría el código.

  • Introducir el valor 3 en los argumentos de llamada
  • Llamar al código de la función cuyo nombre es "f"
  • Tomar el resultado de la llamada como resultado del programa

A esta segunda opción se la llama plegado de constantes. El plegado de constantes no es más que ejecutar parte del código en el compilador en vez de en el programa. La razón de esto es muy sencilla. En el compilador se va a ejecutar una única vez mientras que en el programa se va a ejecutar muchas veces (al menos tantas como veces ejecutemos el programa).

De nuevo, como el plegado de constantes se efectúa durante la compilación, se dice que es una operación estática o en tiempo de compilación.

Evaluación de argumentos

Ejecutemos el siguiente código a continuación:

const A = 3
const B = A
f(B)

Nadie duda en este punto que el símbolo "B" estará asignado con el valor 3 ya que "A" se valuaba a 3. ¿Por qué no se asigna al símbolo "B" el valor "A" en vez del valor 3? Ciertamente, existen dos detalles importante:

  1. Lo que hay a la derecha (el argumento) del operador de asignación "=" se evalúa.
  2. Lo que hay a la izquierda (el símbolo) del operador de asignación "=" no se evalúa.

Aquí, cuando hablamos de evaluación, hablamos de evaluación en tiempo de compilación. Si nos fijamos bien, si hacemos f(1+2) también evaluamos el 1+2 antes de generar código. En general, se evalúan los argumentos de las funciones y no se evalúan los argumentos de las macros. De esto ya hablé anteriormente.

Otra vez, estamos hablando de transformaciones estáticas durante el tiempo de compilación.

Reserva de memoria

La diferencia de una constante con una variable es clara. Las variables pueden cambiar de valor durante la ejecución pero este valor es desconocido durante la compilación. Esto significa que hay que guardar una reserva de memoria durante la ejecución para almacenar el valor de la variable.

var A = lee_de_teclado()

El programa anterior generaría un código ejecutable como el que sigue:

  • Llama al código de la función cuyo nombre es "lee_de_teclado"
  • Guarda el resultado en la reserva de memoria para la variable "A"

Lo importante aquí es que no conocemos el valor que va a tener "A" hasta que no ejecutemos el programa y escribamos algo en el teclado. Por tanto, no estamos hablando de operaciones estáticas sino dinámicas que requieren la ejecución del programa.

Sin embargo, ¿qué pasaría si sí conociésemos el valor que va a tener "A" aunque sea una variable?

Constantes dinámicas

La pregunta anterior aparecería en el caso de este pequeño programa:

var A = 3
f(A)

Si el compilador no hiciera nada antes de generar código, el código ejecutable resultante sería:

  • Guarda el valor 3 en la reserva de memoria de la variable "A"
  • Introducir el valor que hay en la reserva de memoria de "A" en los argumentos de llamada
  • Llamar al código de la función cuyo nombre es "f"
  • Tomar el resultado de la llamada como resultado del programa

Obviamente, podríamos reducir el programa a f(3) pero que "A" sea una variable significa que puede ser modificada en tiempo de ejecución. Concretamente es el caso que sigue.

var A = 3
f(A)
A = lee_de_teclado()

Y lo que es peor, la modificación de "A" podría no producirse en la misma hebra. Podría ser concurrente por lo que no sabríamos si entre "var A = 3" y "f(A)" se habría modificado el valor de "A".

La solución a esto es prohibir que "A", aunque sea variable, pueda ser modificada. En nuestro lenguaje podríamos escribirlo así:

var const A = 3
//No permitimos que A se modifique aquí
f(A)

De esta forma se evita el problema anterior y el compilador es libre de optimizar. Debido a que este tipo de constantes requieren reserva de memoria durante la ejecución se denominan constantes dinámicas.

Utilidad de las constantes dinámicas

Entonces, ¿para qué sirve una constante dinámica? Porque si es constante podemos sustituirla y el programa anterior sigue siendo equivalente a f(3). Bien. Existen dos utilidades importantes.

La primera es que las constantes dinámicas están en memoria y podemos obtener su dirección de memoria. Las constantes estáticas sólo están en compilación y se olvidan cuando se genera el código ejecutable.

El que estén en memoria no es trivial, ya que esto nos permite crear objetos en memoria con una estructura compleja. Ejemplo de esto son arreglos o listas. En este tipo de estructuras es fundamental saber las direcciones de memoria ya que se usan punteros en su implementación.

La segunda utilidad está completamente ligada a la característica dinámica. Es posible tener una constante dinámica, cuyo valor el compilador desconoce, pero que sabe que no va a poder ser modificada. El código que sigue es un buen ejemplo de ello.

var const A = lee_de_teclado()
// Por seguro que nadie va a modificar A aquí
f(A)

Esta característica, también llamada inmutabilidad, es fundamental para la programación concurrente.

El origen de la confusión

La mayoría de los lenguajes de programación actuales no hacen una distinción entre estos dos tipos de constantes en el ámbito del compilador (no así en el del preprocesador).

Por ejemplo, en C++, las constantes son dinámicas casi siempre.

static const int A=3;
memset((void*)&A, 0, sizeof(A)); //OK. A es una constante dinámica.

Sin embargo, se pliegan.

sin(A+A); //Genera el mismo código que sin(6).

Existen mecanismos poco intuitivos y claros para forzar el uso de constantes estáticas.

enum {A=3};
memset((void*)&A, 0, sizeof(A)); //ERROR. A es una constante estática.

Por esta razón algunos opinan que haber elegido "const" como palabra clave fue un error y debería haberse usado "immutable". Java no soluciona el problema y usa variables "static final". En cambio, en C# (por fin) hay distinción entre "const" y "readonly".


domingo, 20 de junio de 2010

Caracterización

De vez en cuando hago un breve cambio de tema para despejar de tanta informática teórica. Esta vez voy a hablar de la caracterización de personajes en historias.

La apariencia

La primera forma de caracterizar a un personaje es mediante su apariencia. Primero la apariencia física: la cara y el cuerpo, y luego con la vestimenta: ropas y objetos que lleve.

Está claro que un matón debe tener una cara algo bruta y un cuerpo muy robusto. Sus ropas nos darán información si es un bruto de barrios bajos o un gangster (algo) más refinado. Finalmente, si lleva una pistola o una navaja también nos va a dar un dato muy descriptivo sobre su carácter.

El lugar

No es lo mismo un doctor con bata blanca en un hospital que el mismo doctor en una biblioteca rodeado de manuscritos antiguos. En el primer caso se dedica a la medicina y en el segundo al estudio de documentos. Así pues, el lugar donde aparece es significativo de cómo es el carácter de un personaje.

Otro detalle importante es el lugar que ocupa un personaje respecto a otros personajes. Si son conocidos la distancia será menor (mucho menor si son íntimos). Si son desconocidos o se llevan mal, guardarán las distancias. Esto es lo que se conoce como proxémixa.

La acción

Definir lo que hace un personaje para caracterizarlo es la parte más compleja de todo su desarrollo. Por esta razón se suele subdividir.

El uso del lugar

Es muy interesante dar a entender que un lugar es o no es del agrado de un personaje según sus acciones en él. Supongamos una fábrica procesadora de carne con los cerdos descuartizados y colgando. Un personaje podría estar muy interesado en la carne, viendo si hay o no grasa en los cuartos traseros, pero también podría estar asustado y nervioso mirando a su alrededor. A fin de cuentas, está rodeado de cadáveres.

Usar un lugar es lo más sencillo para exponer ciertas fobias o filias. Alguien con claustrofobia respirará agitadamente cuando se cierren las puertas del ascensor y un juerguista bailará en una discoteca incluso aunque esté vacía y haga un poco el ridículo.

El habla

La acción más obvia y sencilla para un personaje en una historia es hablar. De hecho, existen historias con personajes que no deberían hablar pero hablan (los animales, los edificios, montañas, nubes, etc.)

Un personaje se define con el habla mediante tres aspectos: ¿Cuándo habla? ¿Cómo habla? Y ¿qué dice? Los personajes más silenciosos suelen tener una vida interior más activa, introvertidos. Los charlatanes contactan con los demás y suelen ser más extrovertidos. Si habla con acento o peculiaridades nos indicará si es de una zona o de otra, si su nivel cultural es alto o bajo, si tiene defectos de algún tipo o no. Por otra parte, el tono y ritmo de su discurso puede darnos a entender si está nervioso, tranquilo, aburrido, etc.

Finalmente, el contenido de lo que dice indica parte de su pensamiento.

Breve taxonomía de las acciones

La última frase nos da la pista a la idea de que existen acciones no vistas. El pensamiento es una de ella. Estas acciones se denominan internas. La acción visible es la acción externa.

Por ora parte podría ocurrir que la acción, aunque relativa a un personaje, sea efectuada por otro personaje. Es lo que se denomina la acción lateral y sirve de vínculo entre dos o más personajes. El típico caso es el del amigo que le echa el brazo por encima al otro. No sólo indica que el que realiza la acción es el amigo, el que recibe la acción también lo es. Esto es lo que se llama una acción lateral.

Finalmente, podríamos no narrar una acción aunque exista. Esta es la base para las elipsis.

Reacciones

Existe un tipo especial de acciones que son las que surgen como resultado de otra acción previa. Son las reacciones. Según el grado de efecto que provoque hablaríamos de gestos: una sonrisa ante la aparición de un conocido; posiciones: abrir los brazos cuando el equipo marca un tanto en algún deporte; o movimientos: huir cuando el personaje se encuentra en peligro.

Por todo lo demás, las reacciones son acciones.

Motivación

Finalmente, lo que no se muestra directamente nunca pero es todo lo que se quiere transmitir con las acciones anteriores es el motivo que lleva al personaje a hacer algo. Toda la caracterización surge de este único punto.


miércoles, 16 de junio de 2010

La relación de subsunción

La letra a en el nombre está relacionada con la regla a del lambda cálculo ya que en esta regla también realizábamos un renombramiento de variables.

El conjunto cociente de a-equivalencias

A partir de ahora es fácil definir

[$$ M < N \Leftrightarrow M \le N \wedge M \not\approx N $$]

Y las relaciones simétricas >, =, etc.

Como la a-congruencia es una relación de equivalencia, notaremos [M] por la clase de equivalencia del término M (o clase de congruencia ya que estamos trabajando con congruencias).

Realmente el conjunto cociente T(A,V)/≈ agrupa en una misma clase los términos que son iguales excepto renombramientos de variables.

[$$ \left[ f(x) \right] = \left\{ f(x), f(y), f(z), ...\right\} $$]
[$$ \left[ g(h(1,z),y) \right] = \left\{ g(h(1,x),y), g(h(1,y),x), g(h(1,x),z), ...\right\} $$]

Es importante recordar que un renombramiento de variables no puede fusionar variables y por lo tanto el término g(h(1,x),x) no pertenece a la clase de equivalencia anterior. Esto es así porque no existe ninguna sustitución que pueda obtener el término original g(h(1,z),y) y por tanto no sería a-congruente.

La subsunción inducida

Si ignoramos los renombramientos de variables, la subsunción se convierte en un orden parcial. Esto es obvio ya que la antisimetría nos lleva directamente a la definición de a-congruencia y, dado que estamos trabajando en el conjunto cociente de esta relación, ambas clases de equivalencia van a ser la misma.

Formalmente esto lo haríamos extendiendo la subsunción al conjunto cociente obtenido por a-conversión. Esta nueva relación se denomina subsunción inducida en el conjunto cociente.

[$$ \left( \le, T(A,V)/\approx \right) $$]

Usaremos el mismo símbolo = para ambas relaciones ya que usualmente trabajaremos con la inducida en el conjunto cociente.

Es realmente importante ver que, dado que los términos son finitos, la subsunción inducida es Noetheriana. Es decir, no existe una cadena infinita

[$$ M_1 > M_2 > \cdots $$]

Esto significa que la subsunción inducida forma una semiretículo inferior Noetheriano y, por ciertos teoremas, debe ser también un semiretículo superior y un retículo completo.

El menor elemento del retículo es [x] ya que lo podemos sustituir por cualquier otro elemento y el superior es [O] que no puede ser sustituido más que por él mismo. Esta era una de las razones por las que nos interesaba introducir un elemento indefinido.

Supremo e ínfimo

Siempre que hablamos de retículos podemos aproximarnos a ellos desde dos perspectivas. Desde una relación de orden y desde las operaciones constituyentes de supremo e ínfimo (con las propiedades asociativa, conmutativa y absorción).

En el caso del retículo de la subsunción inducida el supremo (lo notaremos como una unión de conjuntos) es una unificación con variables disjuntas.

[$$ f(x,g(y)) \cup f(g(y), z) = f(g(w), g(v)) $$]

Probablemente explique algo de unificación más adelante. La idea de la unificación es buscar una sustitución que, aplicada a ambos términos, nos proporcione un mismo término final. En el caso especial de usar variables disjuntas, antes de realizar esta unificación hay que renombrar las variables para que sean todas distintas unas a otras.

El ínfimo (que notaremos como la intersección) es la antiunificación.

[$$ f(x,g(y)) \cap f(g(y),z) = f(x,y) $$]

Lo interesante de todas estas ideas es que, a partir de una definición muy simple de términos y sustituciones, obtenemos una estructura algebraica con unas propiedades bastante bien estudiadas como son los retículos completos.

sábado, 12 de junio de 2010

¿Intersectar o intersecar?

Hoy vuelvo a la carga con una sorpresa léxica que he descubierto. Está claro qué es una intersección, sin embargo ¿cuál es el verbo para hacer una intersección? Lo que se suele oír es intersectar. Sin embargo, esta palabra no existe.

La palabra correcta es intersecar. Que sí aparece en el diccionario.

Rebuscando en la etimología, la diferencia se remonta al latín donde aún hay "t" en una versión (intersectĭo) y falta en la otra (ntersecāre). Sea como fuere, debido a mi ignorancia del tema, he de quedarme con la duda.

Curiosamente, buscando en Google, intersectar tiene unas 32000 apariciones mientras que la correcta intersecar sólo 19000.


lunes, 7 de junio de 2010

Suma de señales sinusoidales de la misma frecuencia

Hoy me han preguntado sobre qué pasa cuando se suman señales sinusoidales de la misma frecuencia. La respuesta es que el resultado es otra señal sinusoidal de la misma frecuencia, sea cual sea la fase o amplitud de las originales.
Todo se reduce a una pequeña demostración.
[$$ \sum_{i=1}^N{k_i\cos{(\phi_i+\omega t)}}
$$] [$$ =\sum_{i=1}^N{k_i\frac{e^{\phi_i+\omega t}+e^{-(\phi_i+\omega t)}}{2}}
$$] [$$ =\sum_{i=1}^N{\frac{k_ie^{\phi_i}e^{\omega t}+k_ie^{-\phi_i}e^{-\omega t}}{2}}
$$] [$$ =\frac{(\sum_{i=1}^N{k_ie^{\phi_i})e^{\omega t}+(\sum_{i=1}^N{k_ie^{-\phi_i})e^{-\omega t}}}}{2}
$$] [$$ =\frac{Ke^\phi e^{\omega t}+Ke^{-\phi} e^{-\omega t}}{2}
$$] [$$ =K \cos{(\phi +\omega t)}
$$]
El truco está en el momento en el que transformamos el sumatorio de los coeficientes y las fases en forma compleja a un único valor complejo que, al final, termina siendo la amplitud y fase finales. La única salvedad es que las amplitudes han de ser reales.
Todo esto lleva a la definición de fasor que permite trabajar con señales sinusoidales como si fueran valores complejos.

domingo, 6 de junio de 2010

Formas normales

He descubierto un artículo donde aparecen muy bien explicadas las distintas formas normales del lambda cálculo. El artículo es este y se resume en la siguiente tabla:

Reduce bajo abstracciones

No reduce bajo abstracciones

Reduce argumentos

v ::= λx.v | x v1 … vn

Forma normal (NF)

v ::= λx.e | x v1 … vn

Forma normal débil (WNF)

No reduce argumentos

v ::= λx.v | x e1 … en

Forma normal de cabeza (HNF)

v ::= λx.e | x e1 … en

Forma normal débil de cabeza (WHNF)

He puesto entre paréntesis las iniciales de las formas normales en inglés (Normal Form, Weak Normal Form, Head Normal Form y Weak Head Normal Form).

El grupo sintáctico v es el de los términos que se consideran forma normal. El grupo sintáctico e es el de los términos del lambda cálculo. Éstos se definen así:

e ::= x | λx.e | e1 e2

Estas formas normales se usan luego para definir las propiedades de los términos. Por ejemplo, un término fuertemente normalizable (SF) es un término que, usemos la estrategia de evaluación que usemos, siempre alcanza una forma normal (NF).

Un término tiene forma normal si existe una estrategia de evaluación que llegue a esa forma normal. De hecho, las estrategias de evaluación están enfocadas a llegar a una forma normal en concreto. Las estrategias que siempre llegan a esa forma normal deseada se denominan estrategias normalizantes.

La siguiente tabla define las estrategias de evaluación más usuales según reduzcan los términos exteriores o interiores primero.

Forma normal deseada

Primero términos exteriores

Primero términos interiores

NF

Orden normal (Normalizante)

Orden aplicativo (No normalizante)

WNF

 

Llamada por valor (No normalizante)

WHNF

Llamada por nombre (Normalizante)