Dibujando curvas de Bézier cúbicas

He actualizado el tutorial de GIMP sobre la aplicación de efectos de forma radial para incorporarle una animación que cuando publiqué la entrada no había puesto a punto, aunque pensaba que sería una buena adición para explicar cómo actúa el filtro Coord. polares de GIMP. La animación en cuestión es esta:

Está hecha con un programa que escribí en mi lenguaje favorito para hacer pequeñas utilidades cuya velocidad no es crucial, es decir, en PHP. Cuando me puse a pensarlo, me di cuenta de que para hacer la animación que tenía en mente me iban a ser muy útiles las curvas de Bézier cúbicas. Sin embargo, al mirar el listado de funciones de la librería GD, descubrí que no contaba con funciones de dibujado de estas curvas.

Tenía, pues, unas pocas opciones. Una era buscar algún otro módulo PHP capaz de dibujarlas. Resulta que el módulo de ImageMagick lo hacía. Pero usar GD tenía sus ventajas para mí, porque va muy al grano y se puede trabajar con imágenes indexadas (es decir, con paleta), y el ImagickDraw no estaba muy bien documentado. Otra era buscar si alguien más había implementado lo mismo. Encontré unas pocas implementaciones, sí, una de ellas de PEAR que parecía que precisaba mucho aprendizaje para usarla, y otra que resultó tener una calidad muy pobre. La tercera opción era hacerme yo una función para dibujarlas. Finalmente me decanté por esa, aprovechando la ocasión para acometer un reto que tenía pendiente desde hace años. Con algún sistema simple me habría bastado, pero quería resolver el problema de forma definitiva para tener una función que dibujara curvas aplicable a cualquier campo, y que me sirviera de referencia en caso de necesitar reescribirla en otro lenguaje.

Métodos iterativos

Así que estuve investigando los métodos que pude encontrar, para hacerme una idea de por dónde atacar el problema. Sabía de antemano que los métodos recursivos daban mejor resultado que el método iterativo simple.

El método iterativo simple

La forma más sencilla de dibujar curvas de Bézier es utilizar la fórmula directamente, escogiendo un incremento de t adecuado que nos permita recorrer el intervalo [0, 1] de forma uniforme, trazando líneas rectas entre cada punto y el anterior. Además, podemos calcular sólo los coeficientes hasta la mitad usando la igualdad B(P₀, P₁, P₂, P₃, t) = B(P₃, P₂, P₁, P₀, 1 - t). Ya conocía este sistema. El problema principal es que no existe un incremento de t adecuado. Si dibujamos demasiados segmentos, podemos encontrarnos con que la línea se engrosa en algunas zonas de forma muy antiestética. Si no dibujamos suficientes, quedarán a la vista los trazos angulosos de los segmentos rectos con que se dibuja la curva. Lo malo es que en ciertas curvas es fácil que se vean ambos defectos a la vez: trazos angulosos y líneas engrosadas. Así que hay que buscar alternativas.

El método iterativo variable

El problema del método iterativo simple radica en que la distancia entre puntos consecutivos (al aplicar un incremento de t constante) no es uniforme. Este problema se podría salvar recurriendo a la fórmula de la velocidad de la curva, que nos da un indicador de cuán grande será el desplazamiento para un t dado. Para una curva que va de P₀ a P₃ con puntos de control P₁ y P₂, la fórmula es:

V(t) = 3·(1 - t)²·(P₁ - P₀) + 6·t ·(1 - t)·(P₂ - P₁) + 3·t²·(P₃ - P₂)

No he probado este método. A primera vista, parece que tiene el problema de que, si los incrementos no son lo suficientemente pequeños, podrían verse los polígonos de nuevo, así que habría que hacerlos lo bastante pequeños. Hacerlos de un píxel puede presentar problemas cuando los trazos son diagonales. Quizá haciéndolos de 2^½ (1,414213...) píxels, que es la distancia entre dos píxels diagonales, o ligeramente superior para evitar problemas de redondeos, fuera suficiente. Tendría que experimentar. Otra pega es que no veo inmediatamente cómo trasladar velocidad a píxels.

Métodos recursivos

En general, los métodos recursivos se basan en subdividir la curva en múltiples segmentos, utilizando el algoritmo de De Casteljau: Sea B(P₀, P₁, P₂, P₃) una curva de Bézier definida por los puntos P₀, P₁, P₂, P₃. Esta curva se puede dividir de forma exacta en dos segmentos, B₀(P₀, P₀₁, P₀₁₂, P₀₁₂₃) y B₁(P₀₁₂₃, P₁₂₃, P₂₃, P₃). El punto P₀ y el punto P₃ coinciden con los de la curva original, ya que son los extremos del segmento curvo y lógicamente tienen que estar cada uno en una de las curva subdivididas. El punto de subdivisión, P₀₁₂₃, también forma parte de la curva, pues esa es precisamente la ventaja del método de De Casteljau.

P₀₁ es un punto situado en la recta entre P₀ y P₁, a distancia relativa t. Es decir, P₀₁ = (1 - t)·P₀ + t ·P₁. Análogamente obtenemos P₂₃ = (1 - t)·P₂ + t ·P₃. Para obtener los puntos que faltan es preciso calcular un punto extra, P₁₂ = (1 - t)·P₁ + t ·P₂. Ahora, P₀₁₂ = (1 - t)·P₀₁ + t ·P₁₂ y P₁₂₃ = (1 - t)·P₁₂ + t ·P₂₃. Por último, P₀₁₂₃=(1 - t)·P₀₁₂ + t ·P₁₂₃. La figura siguiente ilustra el proceso. Cuando t = ½, nos basta con calcular medias entre los puntos.

Método de subdivisión de una curva de Bézier cúbica en dos, en el punto t=0,3. La curva B(P₀, P₁, P₂, P₃) puede ser dividida en las dos curvas B(P₀, P₀₁, P₀₁₂, P₀₁₂₃) y B(P₀₁₂₃, P₁₂₃, P₂₃, P₃).

Los algoritmos recursivos realizan esta subdivisión, normalmente en el punto t=½, y continúan haciendo lo mismo recursivamente con cada uno de los subsegmentos obtenidos. Difieren en la elección del caso base de la recursión.

Método de la colinealidad

Las subdivisiones recursivas van aproximando cada vez más el segmento dividido a un segmento de recta. Si conseguimos determinar en qué momento es tan parecido a una recta que no es distinguible a simple vista, podremos trazar una recta en su lugar y obtener así una muy buena aproximación.

La curva es más plana cuanto más próximos estén los dos puntos de control a la recta que une los puntos origen y final, así que el cálculo de esa distancia es una buena forma de determinar si son casi colineales. Para evitar una raíz, se puede calcular el cuadrado de la distancia en lugar de la distancia misma. La fórmula del cuadrado de la distancia es:

d(P₁, P₀P₃)² = ((P_x3-P_x0)·(P_y1-P_y0) - (P_y3-P_y0)·(P_x1-P_x0))²/((P_x3-P_x0)² + (P_y3-P_y0)²)

y lo mismo cambiando P₁ por P₂.

Actualización 2011-03-23: Tengo pendiente examinar otra forma de evaluar el «grado de colinealidad», que se me ha ocurrido al releer esta entrada. La idea sería utilizar la ecuación de la recta que pasa por P₀ y P₃, rotándola 90° si el valor absoluto de la pendiente es > 1, para hallar el valor de y que se correspondería con el valor de x del punto a comprobar, hallando entonces la diferencia con la y de dicho punto. Esto podría ser más rápido que el cálculo de la distancia aquí nombrado y probablemente sería igualmente efectivo.

Que sean casi colineales no es condición suficiente para poder aproximar la curva como un segmento de P₀ a P₃. Hay otra condición adicional, y es que tanto P₁ como P₂ estén comprendidos entre P₀ y P₃. Si no se impone esta condición, tanto P₁ como P₂ pueden estar fuera del segmento P₀P₃ y el resultado teórico sería una curva que desde uno de los extremos va temporalmente en dirección contraria al otro extremo, y ese fragmento no sería dibujado. Por ejemplo, si consideramos la curva B((0,0), (-3,0), (10,0), (10,0)), los puntos P₁ y P₂ son colineales con P₀P₃ y, pese a ello, la curva se extiende un poco hacia el lado de abscisas negativas.

En casos como el indicado, la subdivisión podría requerir infinitos pasos para el subsegmento que contiene el pico. Para evitarlo, se puede dar un margen de error: si P₂ y P₃ están ambos dentro de un cuadrado rectángulo de tamaño (|P_x3-P_x0|+ε, |P_y3-P_y0|+&epsilon), se consideran buenos.

Este es el método que escogí finalmente. Los resultados son muy decentes y el algoritmo es aceptablemente rápido. Como parámetros, la distancia al cuadrado que puse para considerar los puntos colineales es 0,125 píxels y el ε que escogí es 0,25 (un cuarto de píxel).

Método de la longitud

La longitud de una curva de Bézier puede ser calculada numéricamente, no hay una fórmula explícita general para la misma. Además de mediante una integral que requiere métodos numéricos clásicos y complicados, hay una forma recursiva de aproximarla que, además, nos da un método para dibujarla.

Sea L₀ la longitud del segmento P₀P₃ y L₁ la suma de las longitudes de los segmentos restantes, concretamente L₁=|P₀P₁| + |P₁P₂| + |P₂P₃|. Entonces, la media de esos valores, (L₁ + L₀) / 2, da una aproximación a la longitud, y L₁ - L₀ da una medida del error. Dicho error decrece en relación 2^-4m donde m es el número de subdivisiones [1].

Se puede entonces dibujar el segmento de forma que si la longitud del subsegmento actual es lo bastante pequeña, se trace dicho subsegmento como recta.

No he probado este método. En realidad es muy similar al anterior, ya que cuando el error es pequeño, significa que los puntos están próximos a ser colineales, lo cual es casi lo mismo que el método anterior. En este no nos salvamos de calcular al menos cuatro raíces cuadradas, por lo cual lo deseché antes de probarlo.

Otros métodos

Descomposición en cuadráticas

En [2] se da una forma de descomponer una curva cúbica en cuatro segmentos de curva cuadrática. No me ha convencido el resultado, pero al menos he creído oportuno dejar una referencia para quien quiera averiguar más. Con este método, queda abierto el problema de cómo dibujar una curva cuadrática de forma eficiente.

Partición de la derivada por octantes

Para terminar, vamos a considerar un método que ha sido utilizado por METAFONT, el programa de diseño tipográfico de D. E. Knuth. Para leer la documentación del programa METAFONT decentemente, necesitaremos la utilidad Weave, capaz de extraer archivos escritos en TeX (el formato de proceso de texto de Knuth) a partir de archivos WEB (que contienen una mezcla del programa en Pascal y la documentación en TeX). El original está aquí: http://mirror.ctan.org/systems/knuth/dist/mf/mf.web. La explicación, junto con el código correspondiente, comienza en la §384.

La idea del método es similar a la de los círculos de Bresenham: se clasifica la derivada de la curva por octantes y se transforma cada uno de los octantes al primero, de manera que la pendiente (el incremento de y por cada incremento unitario de x) no sea superior a la unidad. Con este método se consigue que cada incremento de x vaya asociado a cero o un incremento de y, con lo cual la curva resultante tiene una fineza superior. El precio a pagar por tanto refinamiento es un programa que cuesta mucho entender, además de que cuesta bastantes cálculos. El beneficio es la curva más perfecta posible, igual que la línea de Bresenham es la recta más perfecta posible.

Referencias

[1] http://steve.hollasch.net/cgindex/curves/cbezarclen.html
[2] http://www.timotheegroleau.com/Flash/articles/cubic_bezier_in_flash.htm

Aplicando efectos de forma radial

Hay un filtro para GIMP que puede dar buen resultado aplicado a logos u otros propósitos espectaculares, pero cuya utilidad se ve limitada por la forma en que es aplicado. Estoy hablando de Viento.

El filtro Viento sólo se puede aplicar horizontalmente, hacia la izquierda o hacia la derecha. Esto limita mucho su campo de aplicación, pese a que si pudiera aplicarse de forma radial desde un punto de la imagen hacia los bordes, se podrían conseguir efectos interesantes.

Aquí vamos a ver cómo esquivar esa limitación y aplicar el filtro radialmente. Para ello nos ayudaremos de otro filtro presente en ese mismo menú: Coord. polares.

Hace nada compilé un paquete de Gimp 2.6.8 para Debian Lenny, así que es la versión que vamos a usar en este tutorial. En este caso apenas hay diferencias respecto a la 2.4, pero trataré de explicar las que recuerde.

Primero, dejemos claro el objetivo que perseguimos mediante un par de ejemplos:

Logotipo creado con Archivo > Crear > Logotipos > Calor resplandeciente... (en Gimp 2.4 los logotipos están en el menú Xtns de la ventana de herramientas).

Resultado de aplicar el efecto Viento de forma radial

Peluso

Peluso con efecto viento radial

En el caso del logotipo, para que aparezca el texto bien perfilado he aplicado el efecto solamente a la capa central, ya que la superpuesta ayuda a perfilar; he hecho la prueba de aplanar primero la imagen para aplicar el efecto a todo, pero se emborronaba mucho.

Para ver si el efecto queda aceptable o no, a modo de quickie, bastará con aplicar los pasos cuarto, quinto, sexto, séptimo y noveno (transformación, giro, aplicar efecto, deshacer giro, deshacer transformación), que son los que comprenden la esencia del método. Nos quedará un círculo en pequeño en el centro, pero con suerte bastará para que podamos decidir si vale la pena intentar el método completo o no.

Paso cero: ¿Tiene nuestra capa canal alfa? ¿Lo necesita? ¿Hay que ajustar el color de fondo? ¿Hay que duplicar la capa?

Este tutorial puede aplicarse tanto a capas con canal alfa, como a capas sin él. Al final del proceso, se nos puede haber contaminado la imagen con píxels que no pertenecen a ella, que serán transparentes si hay canal alfa, o del color del fondo si no lo hay. Si tiene alfa, después se puede colocar la imagen original debajo para disimular, pero si se trata de un color plano, basta con asignárselo al color de fondo y nos ahorraremos algún paso. Así que, si no tiene canal alfa, decidamos primero si lo añadimos o no y, en caso de que no, ajustemos el color de fondo. Por ejemplo, si es una capa que contiene un logo en blanco sobre fondo verde homogéneo, se puede ajustar el color de fondo a ese verde y trabajar sin canal alfa. Si lo vamos a hacer con una fotografía, como la de Peluso, lo que mejor resultado proporcione será probablemente duplicar la capa y añadir alfa si no tiene, de manera que la imagen original quede debajo, para que así las partes contaminadas por transparencia dejen a la vista dicha imagen. En cualquier caso, es una buena idea tener una copia de la capa original como referencia, para facilitar el último paso de recorte.

Primer paso: Recentrar

Nuestro primer paso será escoger cuál va a ser el punto central del que van a salir todos los «rayos». En el caso de Peluso, he escogido el punto (284, 276). El filtro Coord. polares toma como centro el de la capa con la que trabaja, así que vamos a ampliar el tamaño de manera que dichos puntos queden en el centro. Si queremos que el centro coincida con el de la imagen, este paso no será necesario. En el caso del logo, he optado por ello y me lo he saltado.

La forma de conseguir el nuevo centro es: averiguar las distancias desde el centro escogido (en coordenadas relativas a la capa) hasta ambos lados de la capa, averiguar la mayor de las dos, y agrandar la capa al doble de dicha distancia, recolocándola de forma que nuestro centro elegido caiga en el centro de la versión agrandada. Esto se hace tanto para la coordenada horizontal como para la vertical. Aquí, «agrandar» no se refiere a escalar, sino a cambiar el tamaño extendiendo el borde. Es la operación que en el Gimp se llama «Tamaño del borde de capa...».

La imagen de Peluso tiene 640×480 píxels. La distancia del centro elegido al borde izquierdo es 284; al borde derecho, es 640-284=356. Por tanto, tenemos que expandir la capa por su lado izquierdo dejando una imagen de 356·2=712 píxels de ancho. Repetimos lo mismo con las coordenadas verticales: la distancia al borde superior es 276 y al borde inferior es 480-276=204 píxels, por lo tanto está más cerca del inferior, luego habrá que expandirlo por debajo hasta que la imagen llegue a 276·2=552 píxels de alto. Es decir, tras redimensionar la capa, ésta ha de quedar pegada a la esquina superior derecha. Así que vamos a Capa > Tamaño del borde de capa, quitamos la cadenita que liga el tamaño vertical y el horizontal e introducimos en Anchura, 712, y en Altura, 552 (píxels, claro). En Desplazamiento, como queremos llevarla a la esquina superior derecha, subimos X al máximo, que es 72, e Y la dejamos a 0. Pulsamos Redimensionar. Ahora el centro de la capa ya es el que queremos.

Segundo paso: Agrandar

Dada la manera en que vamos a usar el filtro Coord. polares, vamos a tropezar con el problema de que la imagen final va a ser más pequeña que la inicial. Concretamente, con forma de un círculo cuyo diámetro es la menor de las dimensiones de la capa. Para compensar este efecto, hemos de agrandarla de antemano de forma que la parte original quede inscrita dentro de dicho círculo.

Resultado de aplicar el filtro Coord. polares y su inverso. Arriba, sin agrandar la capa primero; abajo, agrandándola. Obsérvese que en la de abajo la imagen original queda completa.

Este tamaño extra se aplica incluso si ya la hemos agrandado en el primer paso, y después de hacerlo; así el botón Centrar hará lo que esperamos.

Para saber el radio del círculo dentro del cual estará nuestra capa inscrita, hemos de echar mano del teorema de Pitágoras. Primero, hay que hallar el centro; esto lo hacemos dividiendo los tamaños horizontal y vertical por 2. Con la imagen de Peluso, el horizontal es 356 y el vertical, 276. El punto más alejado de dicho centro es la esquina (todas ellas), así que hay que calcular la distancia a la misma. Aplicamos Pitágoras: (356²+276²)^½ ~= 450,45. Al final del proceso, debido a errores de precisión acumulados se colarán unos pocos píxels indeseados; para compensarlo, añadimos un 1% (el error máximo que he observado no llega a 0,4% pero más vale estar seguros, ya que va a ser una diferencia pequeña). Redondeamos por lo alto para estar más seguros aún. Buscaremos, pues, un círculo de 455 píxels de radio, o sea, 455·2=910 píxels de diámetro, así que agrandamos la capa para que sea un cuadrado capaz de circunscribir dicho círculo, es decir, le damos un tamaño de 910×910. Para ello, vamos de nuevo a Capa > Tamaño del borde de capa, quitamos la cadenita, introducimos Anchura = 910, Altura = 910 y pulsamos el botón Centrar para que nos centre el contenido actual. Si hemos escogido un centro distinto, podemos ver el resultado un poco descentrado al pulsar el botón; eso es normal y no debe preocuparnos, pero nuestro centro sí debe estar en el centro del cuadrado resultante; si no es así, quizá hemos colocado la capa en el cuadrante incorrecto en el paso anterior y hay que volver atrás. Si todo ha ido bien, pulsamos Redimensionar.

Para el logo, de 526×238, los valores son (263²+119²)^½ ~= 288,67, que multiplicado por 2,02 (el doble más el 1%) y redondeado al alza nos da que la capa debe ser de 584×584.

Tercer paso: Extender los bordes

La capa del logo con la que vamos a trabajar no llega hasta los bordes, así que si se contamina un borde con transparencia a causa de los errores de precisión, no pasa nada; en ese caso podemos pasar al paso siguiente. El caso de Peluso es distinto, porque la fotografía sí que llega hasta los bordes. Si no nos preocupa que se haga un poco transparente en los bordes, podemos saltar este paso. Si estamos aplicando el truco descrito en el Paso Cero, dejando una copia de la imagen en la capa inferior, no lo necesitaremos. Si el borde queda mal incluso al usar esa estratagema, podemos probar con el truco aquí descrito.

La intención es extender cada borde a su correspondiente espacio vacío. No conozco ninguna forma que no sea tediosa. La idea es seleccionar la fila de píxels superior (una selección de Ancho×1), copiarla y pegarla en el espacio vacío superior, escalándola sólo verticalmente y moviéndola para cubrir la totalidad del mismo. Para ver lo que hacemos, es preferible haber hecho primero Imagen > Ajustar lienzo a las capas. Cuando hayamos terminado, hacemos lo mismo con la fila de píxels inferior. Después, con la fila de píxels izquierda (una selección de 1×Alto) y por último, con la derecha. Al hacer la izquierda y la derecha, cogeremos también lo que ya hemos extendido al hacer la parte de arriba y la de abajo.

Por ejemplo, así queda Peluso tras este paso:

Peluso con los bordes extendidos de la forma recién descrita.

Cuarto paso: Polares a Cartesianas(*)

Vamos al meollo del asunto. Abrimos el filtro Coord. polares y desmarcamos la casilla «A polares», dejando todo lo demás por defecto (profundidad circular 100%, ángulo de desfase 0, no mapear al revés, sí mapear desde arriba). Obtenemos una versión deformada de la imagen de partida. La transformación interpreta la imagen original como si estuviera en coordenadas polares y representa en el eje X, el ángulo, y en el Y, el radio relativo a la menor de las dos dimensiones de la imagen(*). Es decir, todos los efectos que apliquemos verticalmente se harán sobre el radio. Mmmm, eso se parece a lo que queremos.

Actualización 2-2-2010. Esta animación muestra qué transformación realiza el filtro Coord. Polares al aplicarlo a una imagen habiendo marcado las casillas «Mapear al revés» y «Mapear desde arriba» y con la casilla «A polares» desactivada.

Quinto paso: Rotación de 90° a la izquierda

Pero el efecto Viento no opera en dirección vertical, sino únicamente horizontal, así que antes de aplicarlo, primero rotamos la imagen 90° hacia la izquierda con Capa > Transformar > Rotar 90° en sentido antihorario.

Sexto paso: Aplicar el efecto

Ahora es cuando aplicamos el filtro Viento. Hemos de jugar con los ajustes hasta que consigamos lo que buscamos. En el caso de Peluso, he usado Borde Trasero, Umbral 12 y Fuerza 30, dejando Estilo y Dirección intactos. Con el logo, he usado Borde Delantero, Umbral 10 y Fuerza 100.

Séptimo paso: Rotación de 90° a la derecha

Para poder devolver la imagen a su estado inicial con el efecto aplicado, tenemos que deshacer las transformaciones que hemos acumulado. Primero, la giramos a la derecha 90° con Capa > Transformar > Rotar 90° en sentido horario.

Octavo paso: Ampliar (Antialias primera parte)

El filtro Viento produce unas líneas muy finas, de un píxel de ancho, lo cual causa problemas de aliasing al convertir la imagen de nuevo a polares(*), que sería el paso siguiente si no fuera por ese problema. Según la imagen, podemos tener suerte o no, y no he encontrado otra forma de averiguarlo que el ensayo y error. Con Peluso no lo he necesitado; con el logo, sí.

Para conseguir un antialiasing que palie esa pega, el truco que empleamos es ampliar la imagen en este momento, de tal forma que las líneas que se convertirán de cartesianas a polares(*) sean más gruesas, para que después, al reducir con Sinc una vez convertido, sea la propia interpolación la que consiga el antialias. Así que, si hemos tenido en un intento anterior problemas de aliasing, ahora es el momento de ampliar la capa usando Capa > Escalar capa. Recomiendo un valor que no sea un múltiplo exacto como 200%, porque lo he probado y ha sido un fracaso; en cambio, usando un 121% de ampliación he tenido éxito.

Aquí se ve la diferencia sin antialias y con él:

Comparación entre no usar antialias y usarlo

Noveno paso: Cartesianas a Polares(*)

Abrimos de nuevo Coord. polares y marcamos la casilla «A polares» sin tocar nada más. En la previsualización, veremos ya un anticipo del resultado final. Aceptamos.

Actualización 2-2-2010. Esta animación muestra qué transformación realiza el filtro Coord. Polares al aplicarlo a una imagen habiendo marcado las casillas «Mapear al revés» y «Mapear desde arriba» y con la casilla «A polares» activada.

Décimo paso: Reducción (Antialias segunda parte)

Ahora hay que deshacer la ampliación realizada en el octavo paso, si la hemos hecho. Para ello, podemos usar como tamaño destino el tamaño de la imagen en píxels obtenido en el segundo paso (910×910 para Peluso).

Undécimo y último paso: Recortar

Ya solo falta recortar la capa. Esto puede ser complicado si no tenemos una capa de referencia con el tamaño y la posición originales. Si contamos con ella, podemos seleccionarla, usar Capa > Transparencia > Alfa a selección, y luego elegir la capa procesada y usar Capa > Recortar a la selección. Esta última opción no recuerdo que estuviera en Gimp 2.4, así que a quien lo tenga puede que le toque hacer el recorte artesanalmente.

(*): Yo diría que la caja de selección «A polares» está al revés: que cuando está desmarcada es cuando convierte a coordenadas polares y viceversa, representando en un eje el ángulo y en el otro el radio. Por tanto, la primera transformación sería de cartesianas a polares y la transformación inversa convertiría de polares a cartesianas, y no al revés como indica la casilla. Agradecería opiniones al respecto.

Variaciones

El efecto Viento no es el único que se beneficia de esta técnica, así que hay otras opciones para los pasos quinto a séptimo. Otro efecto que no se puede aplicar radialmente es Desplazamiento, aunque en este caso tiene la opción de aplicarlo tanto horizontal como verticalmente, por lo cual si queremos probarlo podemos omitir el paso de la rotación de 90°. No he encontrado aún una utilidad al resultado. Otro posible uso es el Desenfoque gaussiano, ajustando el radio X a cero. Más efectos curiosos: Pixelizar, Mosaico de cristal, Ondular, Borrar las otras filas... Lo que se le ocurra a cada uno.

Nota final

Después de escribir este tutorial, me he dado cuenta de que alguien ya había escrito uno similar: http://www.gimpusers.com/tutorials/rays-of-light-behind-text.html. Sin embargo, he preferido publicarlo porque proporciona valor añadido al explicar cómo recentrar y cómo ampliar la capa en caso de que no sea un logo sino otro tipo de imagen, y explica un método de antialiasing más sofisticado que el que sugiere el autor de ese otro tutorial. El hecho de que ambos tutoriales consten de once pasos es mera coincidencia.

Lenguajes esotéricos

Este artículo es una reedición, con algunos extras nuevos, del que publiqué en la columna Informática recreativa en la ahora extinta web de Lola Cárdenas El rincón del programador. También fue publicada con mi permiso en programacion.com. Pido disculpas si algunos enlaces no funcionan. También pido disculpas por el uso repetido de la palabra decrementar a lo largo del texto, no reconocida en el DRAE.

---

Ser aficionado a la informática y no saber programar es algo que no casa bien. Un auténtico aficionado sabrá al menos hacer pinitos en algún lenguaje de programación, sea Java, Basic, Pascal, C o cualquier otro. Entre los lenguajes de programación también hay modas; un cierto lenguaje «se lleva» más que otros en ciertos momentos, lo cual es lógico habida cuenta de que la informática evoluciona y con ella las necesidades.

No muchos conocen, sin embargo, la inmensa variedad de lenguajes de programación que hay disponibles. Los nombres que ahora mismo me vienen a la cabeza sin consultar ninguna fuente de información son COBOL, ALGOL, APL, BASIC, RPG, Forth, Fortran, Lisp, PL/I, Logo, C, Pascal, Perl, Python, TCL, Ada, Java, ensamblador... y he omitido deliberadamente nombrar variantes como Visual Basic, RPG III, Scheme (un derivado de Lisp), C++ o Delphi (un Pascal ampliado).

Cuando llegamos al ensamblador, el tema de las variantes se convierte en locura. Cada modelo de microprocesador tiene su propio ensamblador, y existen miles y miles de modelos: Z80, PIC-16, 8051, 8086, 6809, 68000, 6502... A veces, como en el caso del 80x86 de Intel, hay varios, incluso multitud de dialectos: el dialecto oficial de Intel, el dialecto oficial del proyecto GNU (formato AT&T), el dialecto del ensamblador gratuito NASM...

Para liar aún más la madeja existen personas que inventan su propio lenguaje ensamblador, el de un procesador que no existe. El ejemplo más notable quizá sea el de Donald Ervin Knuth, matemático y escritor de una serie de tratados sobre computación famosos en todo el mundo. Existen simuladores de los dos lenguajes ensambladores que ha inventado, que corresponden a los procesadores imaginarios llamados MIX y MMIX.

Ahí no queda todo. Hay gente que no ve razón en que el lenguaje a inventar sea un lenguaje ensamblador; simplemente inventan un lenguaje nuevo. Las razones son muy variadas; está claro por ejemplo que Sun Microsystems tenía razones poderosas para inventar el Java. Pero no todo el mundo necesita razones poderosas; aquí vamos a tratar precisamente sobre los lenguajes de programación que han sido inventados por puro entretenimiento. ¿Hay gente capaz de eso? Sí, y no pocos. Incluso existen intérpretes de la mayoría de esos lenguajes, y en algunos casos hasta compiladores.

Uno de los primeros lenguajes esotéricos (al menos que yo tenga referencia, pues fue creado en 1972), y quizá de los más extendidos, es el INTERCAL. Su diseño se fundamenta en la pretensión de crear un lenguaje totalmente distinto a cualquier otro en todo, aunque sin olvidar desde luego el sentido del humor. En él, tenemos que pedir por favor la ejecución de ciertas sentencias; en lugar del conocido «go to» (ir a) para saltar a otra instrucción, tenemos que escribir «come from» (venir desde) en el lugar de destino, aunque esto es una extensión posterior a la primera especificación. Podemos pedir que se abstenga de ejecutar ciertas sentencias, por ejemplo: PLEASE ABSTAIN FROM CALCULATING evita que se ejecute la orden CALCULATE. Cuando llegamos al capítulo sobre la precedencia de operadores se nos explica que no la hay, porque precisamente el objetivo en el diseño del lenguaje era que no hubiera ningún precedente. Como resultado de esta regla, cuando necesitamos concatenar dos operaciones juntas hay que agrupar los operandos por pares mediante un equivalente a los paréntesis. El nombre completo del lenguaje, según los autores, es «Lenguaje Compilado Carente de Acrónimo Pronunciable», cuya abreviatura es, «por razones obvias», INTERCAL. Podemos ver el aspecto que tiene un programa escrito en INTERCAL en la figura 1. La función de este programa, extraído del manual de INTERCAL, es leer dos enteros de 32 bits, tratándolos como enteros con signo en formato de complemento a dos, y escribir su valor absoluto.

        DO (5) NEXT
    (5) DO FORGET #1
        PLEASE WRITE IN :1
        DO .1 <- 'V":1~'#32768$#0'"$#1'~#3
        DO (1) NEXT
        DO :1 <- "'V":1~'#65535$#0'"$#65535'
                ~'#0$#65535'"$"'V":1~'#0$#65535'"
                $#65535'~'#0$#65535'"
        DO :2 <- #1
        PLEASE DO (4) NEXT
    (4) DO FORGET #1
        DO .1 <- "'V":1~'#65535$#0'"$":2~'#65535
                $#0'"'~'#0$#65535'"$"'V":1~'#0
                $#65535'"$":2~'#65535$#0'"'~'#0$#65535'"
        DO (1) NEXT
        DO :2 <- ":2~'#0$#65535'"
                $"'":2~'#65535$#0'"$#0'~'#32767$#1'"
        DO (4) NEXT
    (2) DO RESUME .1
    (1) PLEASE DO (2) NEXT
        PLEASE FORGET #1
        DO READ OUT :1
        PLEASE DO .1 <- 'V"':1~:1'~#1"$#1'~#3
        DO (3) NEXT
        PLEASE DO (5) NEXT
    (3) DO (2) NEXT
        PLEASE GIVE UP

Figura 1: Programa en lenguaje INTERCAL

Los programas en INTERCAL, desde luego, no son fáciles de escribir. De todas formas no es el lenguaje esotérico en el que más cuesta escribir un programa. Por ejemplo, en lenguaje Piet es imposible escribir un programa: hay que dibujarlo. Vemos en la figura 2 un ejemplo de un programa en lenguaje Piet.

Figura 2: Programa en lenguaje Piet.

El programa de la figura 2 se limita a escribir la conocida frase «Hello, world!» («¡Hola, mundo!»). Hay que reconocer, sin embargo, que hemos hecho abuso del significado de la palabra escribir en este contexto. Diseñar el programa es algo que en Piet no es una tarea demasiado difícil.

Quien busque algo en lo que sea verdaderamente difícil programar, puede intentar usar Malbolge. El nombre procede del Malebolge (el octavo círculo del infierno de Dante), aunque seguramente el nombre fue recortado a causa de una limitación del sistema operativo para el que fue originariamente escrito (MS-DOS), que limita la longitud de los nombres a ocho caracteres. Esta alusión al infierno puede dar una somera idea de la complicación del lenguaje, aunque obtendremos una idea más aproximada conociendo la dificultad que supuso para Andrew Cooke escribir un programa en Malbolge que simplemente escribiera «Hello, world» (digamos que lo hizo por métodos de tipo «ensayo y error», y ni siquiera consiguió uniformidad en las mayúsculas y minúsculas ni signos de puntuación: el programa escribía «HEllO WORld»). En la figura 3 vemos el programa que consiguió la hazaña.

(=<`$9]7<5YXz7wT.3,+O/o'K%$H"'~D|#z@b=`{^Lx8%$Xmrkpohm-kNi;g
sedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543s+O<oLm

Figura 3: Programa en lenguaje Malbolge.

No hay que desesperarse por no entender nada. Esa es justo la intención que el inventor del lenguaje tenía. De hecho, el cripticismo buscado por el autor le resta cierto interés al lenguaje: está deliberadamente encriptado, razón por la cual Cooke propone un «Malbolge normalizado», que es lo que queda después de la fase de desencriptación. No hay que dejarse llevar por la idea, sin embargo, de que esto le reste dificultad al lenguaje. Se puede (si es que se puede) escribir un programa en Malbolge normalizado y después aplicar la fase final de encriptación para obtener un programa válido en Malbolge. La figura 4 muestra el aspecto del programa «Hello world» en Malbolge normalizado.

jpp<jp<pop<<jo*<popp<o*p<pp<pop<pop<jijoj/o<vvjpopoopo<ojo/o
vooooooooooooooooooooooooooooooooooooooooooooooooooo*p<v*<*

Figura 4: Programa en lenguaje Malbolge normalizado.

Aunque resulta algo más legible que antes, sigue siendo complicado de descifrar sin una descripción de qué significa cada símbolo (y aun con ella). En el fichero de la distribución de Malbolge existe una descripción completa del lenguaje.

Pero de entre todos los lenguajes esotéricos hay uno que llama la atención por su exquisita simplicidad y potencia. Se llama Brainfuck, que en inglés suena tan mal como en español su traducción de Jodecerebros, con perdón. Debido a lo ofensivo del nombre, no es tan fácil buscar referencias en WWW usando buscadores ya que hay muchas variaciones del nombre para ocultar su carácter ofensivo: Brainf*ck, Brainf***, Brainfsck, BF... La intención de su creador, Urban Müller, era la de crear un lenguaje para el cual se pudiera escribir el compilador más corto del mundo.

A pesar del nombre, escribir un programa en Brainfuck no es tan difícil como cabe pensar. Está demostrado que es un lenguaje Turing-completo, lo que expresado de forma simple significa que se puede codificar cualquier algoritmo con él. Existen únicamente ocho instrucciones, cada una de las cuales está asociada a un símbolo. Hay un resumen en la tabla 1. Existe un puntero de programa, que representa la posición en la que se está ejecutando actualmente el código, como en cualquier otro lenguaje imperativo (con algunas salvedades), y un puntero de datos, que es una característica propia de Brainfuck y que sirve precisamente para manipular los datos. El puntero de datos apunta a la posición cero de una zona de memoria, inicialimente rellena de ceros. No se considera correcto un programa si intenta aplicar un decremento al puntero de datos cuando éste está en la posición cero. Usualmente se considera que el contenido de cada posición de memoria es un byte sin signo (un número de 0 a 255). Al incrementar uno de estos bytes cuando su valor era 255, generalmente pasa a valer 0. Al aplicarle un decremento cuando su valor era 0, generalmente pasa a valer 255. Decimos «generalmente» porque según la implementación puede haber versiones del lenguaje que adopten otros convenios.

Instrucción	Descripción	Equivalente C
-	Restar 1 al contenido de la celda de memoria actualmente apuntada por el puntero de datos.	--*p;
+	Sumar 1 al contenido de la celda de memoria actualmente apuntada por el puntero de datos.	++*p;
<	Decrementar el puntero de datos en una unidad. Es un error ejecutar esta instrucción cuando el puntero de datos tiene el valor 0.	--p;
>	Incrementar el puntero de datos en una unidad.	++p;
[	Si el contenido de la celda de memoria a la que apunta el puntero de datos es cero, buscar el correspondiente «]» y colocar el puntero de instrucción inmediatamente después. Es posible anidarlos. No se considera un programa válido aquél en el que no hay un balance correcto entre los «[» y los «]».	while(*p){
]	Colocar el puntero de programa en el «[» anterior correspondiente.	}
,	Introducir un carácter desde entrada estándar y colocarlo en la celda apuntada por el valor actual del puntero de datos.	*p=getchar();
.	Escribir el carácter ASCII correspondiente al valor de la celda actual en la salida estándar.	putchar(*p);

Tabla 1: Instrucciones del lenguaje Brainfuck.

Aquellos que sepan C pueden valerse de las equivalencias aproximadas que se dan en la tabla para entender un poco mejor las acciones que cada instrucción realiza. Con tal sencillez estructural, mal puede sorprendernos la facilidad con la que se puede escribir un intérprete, y hasta un compilador de Brainfuck. Pero antes de entrar en detalles respecto al intérprete, analizaremos un poco el lenguaje y veremos algunas construcciones comunes.

Por ejemplo, la secuencia de instrucciones [-] se usa a menudo en los programas Brainfuck, y sirve para poner a cero la celda de memoria actual: equivale en C a la instrucción «while(*p){--*p;}», es decir, mientras la celda de memoria actual sea distinta de cero, decrementarla, lo cual obviamente tiene como efecto ponerla a cero.

Si queremos mover el valor actual una posición a la derecha (aquí entendemos que «izquierda» implica disminuir el puntero de datos y «derecha» aumentarlo), utilizaremos el siguiente programa: [>+<-]. Esto va incrementando el byte de la derecha de la posición inicial y decrementando el actual, hasta que éste es cero. Como resultado, al byte situado a la derecha de la posición inicial se le suma lo que hubiera en dicha posición, que acaba siendo cero. Suponiendo que a la derecha hubiera un cero, habremos acabado moviendo el byte de esa posición un lugar a la derecha. Copiar un valor es un problema más complicado; asumiendo que las dos posiciones situadas a la derecha de la actual sean cero, se procederá de la siguiente forma: primero, usaremos [>+>+<<-], que tendrá el efecto de copiar el valor en la posición actual a la posición de su derecha y a la siguiente más a la derecha, y poner a cero la posición actual; después iremos dos posiciones a la derecha usando >>, tras lo cual usaremos una versión modificada del fragmento mover: [<<+>>-], es decir, mover el byte de la posición p (siendo p la posición del puntero de datos) a la posición p-2. Al terminar, retrocederemos otra vez dos posiciones usando <<, aunque dependiendo de la aplicación que queramos darle este último paso puede ser innecesario.

Si no estamos seguros de si están a cero las dos posiciones de la derecha de la actual, siempre podemos asegurarnos usando el siguiente fragmento: >[-]>[-]<<. Normalmente, sin embargo, no necesitaremos ejecutar este código, ya que estará a cero al comenzar.

Juntando todo esto, nos damos cuenta de que si al empezar tenemos en la posición p el valor a, en la posición p+1 el valor 0 y en la posición p+2 el valor 0, tras ejecutar el siguiente fragmento de código acabaremos teniendo en p el valor a, en p+1 el valor a, y en p+2 el valor 0:

[>+>+<<-]>>[<<+>>-]<<

¿Confuso? Considerando cada parte por separado, se ve claramente que simplemente estamos construyendo fragmentos cada vez más grandes mediante los bloques básicos que anteriormente hemos considerado.

Multiplicar un byte por una constante es sencillo: basta con utilizar el programa de mover, pero en lugar de incrementar una vez la variable de la derecha, la incrementamos tantas veces como haga falta. Por ejemplo, para multiplicar el byte actual por 7 podemos utilizar esto: [>+++++++<-], que deja el resultado a la derecha del byte actual, y éste a cero.

Multiplicar dos bytes entre sí requiere algo más de esfuerzo. La idea es sumar el segundo sobre el byte a su derecha tantas veces como diga el primero. Veamos cómo hacemos esto. Primero fijémonos en que la operación de copiar puede ser usada también para sumar, puesto que si el valor en la posición de la derecha de la actual no es cero, se le sumará el contenido del byte actual. Así pues, si llamamos c a la operación copiar, con este código resolveremos el problema: [>c<-], es decir, ir a la derecha, sumar el byte que hay allí al siguiente, ir a la izquierda, decrementar y continuar hasta que éste sea cero. Si se desea que no se pierda el primer multiplicando, habrá que empezar copiándolo a un lugar seguro.

El código completo queda así:

[>
  [>+>+<<-]
  >>
  [<<+>>-]
  <<
<-]

Veamos ahora un programa simple que imprime la «respuesta a la Gran Pregunta de la Vida, el Universo y Todo lo demás» (según Douglas Adams, escritor y humorista británico fallecido hace pocos años). Dicha respuesta es 42. El siguiente programa calcula el código ASCII del número 4 y lo imprime, y a continuación calcula el código ASCII del número 2 y lo imprime: +++++++[>+++++++<-]>+++.--.. El código ASCII del dígito 4 es 52 = 7×7+3, por tanto primero multiplicamos 7×7, y luego sumamos 3 al resultado y lo imprimimos. Después restamos 2 a lo que quedaba, ya que el código ASCII del dígito 2 es 50 = 52-2. Lo imprimimos, y ya lo tenemos.

Dejamos al cuidado del lector el resto del aprendizaje del lenguaje Brainfuck, para centrarnos en una forma de elaborar un intérprete de dicho lenguaje. Esta es una tarea realmente sencilla, como veremos enseguida; la única parte que presenta alguna complicación (poca, realmente) es llevar el balance de qué «]» corresponde con un «[» y viceversa. Precisamos de dos memorias, compuestas por sendos arrays (o arreglos, según algunos traductores): la de programa y la de datos, llamadas respectivamente mp y md. También necesitaremos dos variables: p y d, que serán los punteros de programa y datos, respectivamente.

He aquí un esquema del algoritmo principal del intérprete:

  Leer el programa en la memoria de programa, mp,
    guardando en la variable pfin la posición siguiente
    a la última usada, que indicará fin de programa.
  Poner a cero todos los elementos de la memoria de datos.
  Hacer p = 0, d = 0.
  Comienzo del bucle (1):
    Si p = pfin, fin de programa: ir a la etiqueta (4).
    Si la instrucción mp[p] es «-», hacer md[d] = md[d] - 1.
    Si la instrucción mp[p] es «+», hacer md[d] = md[d] + 1.
    Si la instrucción mp[p] es «<», hacer d = d - 1.
    Si la instrucción mp[p] es «>», hacer d = d + 1.
    Si la instrucción mp[p] es «,», leer un carácter y guardarlo en md[d].
    Si la instrucción mp[p] es «.», escribir el carácter que hay en md[d].
    Si la instrucción mp[p] es «[» y md[d] es cero, hacer lo siguiente:
      Hacer nivel = 0.
      Comienzo del bucle (2):
        Si mp[p] es «[», hacer nivel = nivel + 1.
        Si mp[p] es «]», hacer nivel = nivel - 1.
        Hacer p = p + 1.
        Si nivel = 0, ir al comienzo del bucle (1).
      Ir al comienzo del bucle (2).
    Si la instrucción mp[p] es «]», hacer lo siguiente:
      Hacer nivel = 1.
      Comienzo del bucle (3):
        Hacer p = p - 1.
        Si mp[p] es «]», hacer nivel = nivel + 1.
        Si mp[p] es «[», hacer nivel = nivel - 1.
        Si nivel = 0, ir al comienzo del bucle (1).
      Ir al comienzo del bucle (3).
    Hacer p = p + 1.
  Ir al comienzo del bucle (1).
  Etiqueta (4): fin de programa.

El intérprete recién descrito asume que los programas son sintácticamente correctos, es decir, que tienen un balance correcto de «[» y «]» y que el programa nunca utiliza la instrucción «<» cuando d = 0, ni la instrucción «>» cuando d está en la última posición disponible de md. También asume que el lenguaje efectúa correctamente el «salto» de 255 a 0 al incrementar, y de 0 a 255 en los decrementos. Si esto no fuera así, habrá que poner condiciones adicionales, convirtiéndose la operación de incrementar en la siguiente:

  Si md[d] = 255, hacer md[d] = 0; si no, hacer md[d] = md[d] + 1.

y la de decrementar, similarmente:

  Si md[d] = 0, hacer md[d] = 255; si no, hacer md[d] = md[d] - 1.

Durante el desarrollo de un programa Brainfuck es fácil equivocarse de forma que no cumpla los requisitos arriba expuestos. Para evitar sorpresas es aconsejable incluir en el intérprete comprobaciones en lugares estratégicos: comprobar antes de decrementar d que éste no es cero, y antes de incrementarlo que no está ya en el límite derecho; en los bucles que buscan el «[» y «]» correspondientes a su pareja, hay que comprobar que no llegamos a p = 0 o a p = pfin sin encontrar la pareja correspondiente, o en caso contrario detener la ejecución. Con esas precauciones el intérprete debería ser seguro frente a cualquier programa Brainfuck por mal construido que esté.

Ya para terminar, una pregunta: ¿cuál es la longitud del programa Brainfuck más corto capaz de escribir una o minúscula (código ASCII 111) dejando el resto de la memoria de datos con ceros?

Intérprete en JavaScript

El siguiente intérprete puede servir para probar código en Brainfuck. Incluye entrada y salida, pero no ejecución paso a paso ni visualización de los datos (véase la sección de enlaces para un depurador de Brainfuck más completo en C).

Programa:
Entrada:
Salida:
Ejecutar:

Enlaces

Por ahora la mayoría de las páginas enlazadas desde aquí están en inglés, ya que el tema parece que todavía no es muy conocido en nuestro país. Esperemos que con el tiempo la situación cambie.

Sobre lenguajes esotéricos en general

El lugar por excelencia donde encontrar información y referencias sobre lenguajes esotéricos es sin duda el Esoteric Languages Wiki:
http://www.esolangs.org/wiki/

Hay un índice de páginas apuntadas a un webring sobre lenguajes esotéricos, que también contiene multitud de referencias:
http://b.webring.com/hub?ring=esolang

Una excelente página dedicada a los lenguajes experimentales, mantenida por Chris Pressey:
Cat's Eye, http://catseye.tc/
Es de destacar la sección dedicada a los lenguajes de programación esotéricos:
http://catseye.tc/projects/eso.html

Eric S. Raymond es el autor de un compilador de INTERCAL, el C-INTERCAL. Su página llamada The Retrocomputing Museum contiene una selección de joyas del esoterismo en programación. Brainfuck tiene ocho instrucciones, pero ¿cuál es el mínimo número de instrucciones que debe tener un lenguaje para ser Turing-completo? ¡Una! Hay en esta página dos ejemplos, que llevan el concepto del RISC un paso más lejos: OISC (One Instruction Set Computing) y URISC (Ultimate RISC).
Otra de las joyas presentes en este museo es el kvikkalkul, un lenguaje pretendidamente utilizado en los submarinos nucleares suecos en la década de 1950, aunque más probablemente sea una broma. El lenguaje sólo soporta números en coma flotante sin parte entera, es decir, menores que 1.
También destacamos el MIXAL, que es el lenguaje ensamblador del procesador MIX de Knuth, mencionado en el texto, y un lenguaje de programación Klingon llamado var'aq. Hay muchas otras perlas que invitamos a descubrir.
http://www.catb.org/esr/retro/

La Enciclopedia de Lenguajes Estúpidos contiene una lista bastante exhaustiva de lenguajes esotéricos, sus características, el nombre de su creador, el año de creación y la página principal. Varios de los enlaces disponibles aquí han sido obtenidos gracias a esa página.
http://www.kraml.at/stupid/

Listas de correo relacionados con lenguajes esotéricos:
Archivo de la lista de correo de Cat's Eye

Selección de lenguajes esotéricos concretos

El lenguaje Whenever, cuyas instrucciones no se ejecutan en un orden preestablecido sino aleatorio:
http://www.dangermouse.net/esoteric/whenever.html

Las instrucciones del lenguaje Wierd son cambios de dirección en cadenas de símbolos. Esta es la especificación del lenguaje:
http://catseye.tc/projects/wierd/doc/wierdspec.txt

El lenguaje Piet mencionado en el texto, cuyas instrucciones son colores:
http://www.dangermouse.net/esoteric/piet.html

Descripción del lenguaje nihilista Sartre, creado por J. Colagioia, otro lenguaje pensado con buen humor. Es bastante llamativa la definición de la instrucción condicional IF.
http://catseye.tc/projects/sartre/doc/sartre.html

Sobre Brainfuck

He aquí un intérprete y depurador de Brainfuck escrito por el autor de este artículo (en inglés), suministrado en forma de código fuente en C. El código debería ser sumamente portable; compila perfectamente con gcc tanto en Windows como en Linux. El intérprete, además, realiza primero una pasada de optimización del código para que se ejecute más rápido. El depurador contiene funciones avanzadas que hasta ahora no he encontrado en ningún programa similar.
brfd101.zip (11.077 bytes)

Una completa guía acerca de los bloques con los que construir programas en Brainfuck:
http://home.planet.nl/~faase009/Ha_bf_intro.html

La demostración formal de que Brainfuck es Turing-completo:
http://home.planet.nl/~faase009/Ha_bf_Turing.html

Un intérprete de Brainfuck disponible en línea, escrito en JavaScript:
http://home.planet.nl/~faase009/Ha_bf_online.html

Propuestas de normalización del Brainfuck:
http://www.muppetlabs.com/~breadbox/bf/standards.html
y otra con cierto sentido del humor:
http://esoteric.sange.fi/ENSI/brainfuck-1.0.txt

Existen numerosos programas escritos en lenguaje Brainfuck; entre ellos destacamos un programa para averiguar si un número es primo, varios intérpretes y compiladores de Brainfuck escritos precisamente en Brainfuck, y un programa para calcular PI, aunque éste último requiere una extensión del lenguaje que permita que cada celda pueda almacenar números de 16 bits en vez de 8.

He aquí una biblioteca de programas escritos en Brainfuck. Destacamos el programa SORT.BF, que lee una entrada, la ordena mediante el método de la burbuja e imprime el resultado.
http://esoteric.sange.fi/brainfuck/bf-source/prog/

Otros enlaces indirectamente relacionados con lenguajes esotéricos

Una colección del programa Hello, World escrito en gran variedad de lenguajes, incluyendo muchos esotéricos, entre ellos BrainFuck e INTERCAL:
http://www.latech.edu/~acm/HelloWorld.shtml

99 Bottles of Beer es una canción popular inglesa y estadounidense, al estilo de la canción popular española cuya letra empieza así: Un elefante se balanceaba sobre la tela de una araña... La versión en inglés requiere contar del 99 al cero durante la canción. Escribir su letra es un ejercicio de programación indudablemente más complicado que el de Hello, World, ya que requiere un bucle finito, una cuenta atrás e imprimir números, y por ello los programas tienden a ser más largos pero a la vez más interesantes. He aquí una página dedicada a los programas que imprimen la letra completa de la canción 99 Bottles of Beer en diferentes lenguajes de programación; destacamos el escrito en A+ ya que es capaz de imprimir las versiones europea y americana. Por supuesto no faltan versiones Brainfuck ni INTERCAL del programa, e incluso una en Malbolge.
http://www.99-bottles-of-beer.net/

Los quines son programas capaces de reproducirse a sí mismos. No tienen, sin embargo, nada que ver con los virus: a diferencia de éstos, el requisito que han de cumplir los quines es que la salida del programa sea su propio código fuente, sin utilizar ningún fichero externo. Pensando un poco sobre el tema vemos enseguida que la tarea no es trivial, y que se parece al problema del huevo o la gallina. Hay ejemplos en muchos lenguajes, entre ellos INTERCAL y Brainfuck.
http://www.nyx.net/~gthompso/quine.htm

Lista exhaustiva de lenguajes de programación, antiguos y modernos:
http://ftp.wustl.edu/doc/misc/lang-list.txt

La Galería de los Descifradores CSS es una página creada para defender que un programa de ordenador puede ser acogido dentro de la ley de libertad de expresión, ya que al parecer un juez estadounidense declaró ilegal un programa escrito en lenguaje C que descifraba los sectores encriptados de los discos DVD, que utilizan un sistema criptográfico denominado CSS. Hay ejemplos en muchos otros lenguajes (entre ellos, cómo no, Brainfuck), y otras muchas formas de expresar el programa original: versiones recitadas del programa en formato MP3, descripciones detalladas del algoritmo paso a paso que pueden ser utilizadas para rehacerlo, y muchas otras divertidas maneras de convertir el algoritmo a formas que sí están claramente protegidas por la libertad de expresión. Dando vueltas a la tuerca, lleva el tema a extremos que rayan el ridículo, como la existencia de números primos ilegales.
http://www.cs.cmu.edu/~dst/DeCSS/Gallery/

Fraccionar archivos usando Reed-Solomon

Hace tiempo que necesitaba una utilidad capaz de dividir un archivo en varias partes. Pero no que hiciera sólo eso, que para eso ya existen muchas (Hacha, por ejemplo), sino una tal que si se pierden algunas partes (con un valor máximo de «algunas» decidido de antemano) todavía se pueda recuperar el archivo original.

El uso que le quería dar es una copia de seguridad distribuida. Se divide el archivo que se quiere guardar en múltiples partes y se suben a diferentes lugares: MediaFire, MegaUpload, FileFactory, 4shared, ADrive... debidamente cifradas de antemano si queremos preservar nuestra intimidad, claro. Si a la hora de recuperar las partes hay alguno de los servicios que ha cerrado, o que ha borrado el archivo, o cuya clave no nos funciona por alguna razón, siempre es posible reconstruir el original usando los demás, suponiendo que el número de bajas no sea excesivo.

La solución obvia es subir el archivo completo a cada uno de los alojamientos remotos. El problema está en el tamaño máximo soportado por cada alojamiento y en el ancho de banda total que hay que usar para subir tantas veces el mismo archivo.

Esto sugiere una pregunta: ¿Es posible obtener, a partir de un archivo dado, n+m archivos, de manera que si de ellas se pierden m partes cualesquiera, se pueda reconstruir el archivo original?

Sí, se puede, y además de forma óptima, es decir, que si el archivo tiene B bytes, el tamaño de cada bloque sería exactamente B/n si B es múltiplo de n. Si no lo es, no importa: nos guardamos la longitud original del archivo y añadimos bytes (por ejemplo, ceros) hasta llegar al siguiente múltiplo de n. Después, tras reconstruirlo, truncamos el archivo por su longitud original.

De hecho, el principio para hacerlo es el que se emplea en el RAID. No me refiero a la marca de insecticida, sino a un sistema genérico para agrupar varios discos (Redundant Array of Inexpensive —o Independent— Disks).

Según la forma de usar los discos, existen varios tipos de RAID, a los que se les asigna números. Algunos de esos tipos contienen información redundante para prevenir fallos de las unidades de disco. Los más básicos son RAID 1, RAID 3 y RAID 6. RAID 1 es el sistema más obvio: todos los discos tienen el mismo contenido. Es como la idea de subir el mismo archivo a todas partes. RAID 3 lo hace mejor: si hay N discos, la capacidad efectiva es N-1, y si se estropea uno, se puede reconstruir a partir de los demás. El sistema que emplea es muy sencillo: cada bit del disco extra es el XOR de todos los demás. Así, si R, S y T son los discos que contienen los datos normales, el disco U contiene R⊕S⊕T. Si se estropea R, se puede recuperar su contenido calculando S⊕T⊕U, ya que puesto que U=R⊕S⊕T, S⊕T⊕U = S⊕T⊕(R⊕S⊕T) = (quitando paréntesis y reordenando) S⊕S⊕T⊕T⊕R = 0⊕0⊕R = R. Lo mismo se aplica al resto de discos.

Sin embargo, no se puede extender el mismo truco a otro disco más y conseguir que si fallan dos discos cualesquiera, ambos se puedan recomponer. El truco del XOR está limitado a un disco fallido como máximo. Esto quiere decir que si falla un disco durante la recomposición de los datos originales (o hasta que se reemplaza el disco fallido), se pierden los datos. Para conseguir tolerancia a dos fallos o más, hace falta recurrir a los códigos Reed-Solomon. Esto es lo que hace el RAID 6.

No es trivial operar con estos códigos; hacen falta algunos conceptos de álgebra lineal y de estructuras algebraicas. Puesto que no encontré ningún programa ya hecho para dividir y recomponer datos, tuve que hacerme uno propio. Lo que sigue es una síntesis de lo que he averiguado durante su elaboración.

Hay un tutorial sobre códigos Reed-Solomon aplicados a sistemas RAID, aquí: [1] (PDF). La descripción de la matriz necesaria para generar los códigos (y su inversa para decodificarlos) es errónea; hay un artículo que la enmienda aquí: [2] (PDF).

Así que tenemos un archivo conceptualmente dividido en n bloques de datos, y queremos generar a partir de ellos un total de n+m bloques de datos, tales que si se pierden cualesquiera m de los n+m bloques, podamos reconstruir los que se han perdido. Para conseguirlo, dividiremos los bloques en palabras, es decir, conjuntos de bits de una longitud fija predeterminada w. El número de bits por palabra w es un valor escogido de tal forma que 2^w sea mayor que el máximo valor de n+m que vamos a emplear. Por ejemplo, si escogemos w=8 (por tanto las palabras son bytes), podremos dividir el archivo original en un máximo de 255 partes contando las que se pueden perder; por ejemplo, n=200, m=55.

Pero para empezar, supongamos que trabajamos en el dominio de los números reales; luego ya veremos cómo hacer lo mismo sólo con enteros de w bits. El problema consiste entonces en encontrar, a partir de una serie de datos d₁, d₂, ..., d_n, una serie de elementos c₁, c₂, ..., c_n+m que tengan la propiedad deseada. Veamos cómo hallarlos.

Dispondremos los datos en forma de una matriz columna, D. Para resolver el problema hemos de encontrar dos matrices A y B. La matriz A debe cumplir esta condición: que el producto AD sea una matriz columna C que contiene los elementos c₁, c₂, ..., c_n+m. La matriz B, por su parte, tiene que cumplir esta condición: si cogemos n elementos distintos cualesquiera de los n+m que tiene C y formamos con ellos una matriz columna C’, entonces BC’=D.

Si tenemos esas dos matrices A y B, el problema estará resuelto: si podemos usar A para calcular C, obtendremos c₁, c₂, ..., c_n+m y por tanto generar los bloques; si podemos usar B para calcular D a partir de cualquier subconjunto de n elementos distintos de C, podemos reconstruir los datos originales.

El problema, pues, radica en cómo construir las matrices A y B. Veamos la forma.

Para poder multiplicarla por D, la matriz A tiene que tener n columnas; para dar como resultado una matriz columna con n+m elementos, tiene que tener n+m filas. La característica que deseamos que tenga A, ya veremos después por qué, es que al tachar m filas cualesquiera, la matriz resultante sea siempre invertible (lo que equivale a requerir que su determinante no sea nulo). ¿Cómo lo conseguimos?

La respuesta viene de la mano de una familia de matrices llamadas matrices de Vandermonde. Estas matrices se construyen como sigue: sean a₁, a₂, ..., a_k escalares arbitrarios; entonces la fila i está compuesta por una sucesión geométrica que comienza en a_i⁰=1:

(Se define 0⁰=1 a este efecto). El determinante de una matriz cuadrada de Vandermonde nunca es cero si ninguno de los escalares está repetido (concretamente, su valor es ∏(a_j - a_i) para todos los posibles pares ordenados a_i, a_j de escalares que intervienen, que no será cero a menos que haya escalares repetidos), así que, si formamos una matriz rectangular de Vandermonde más alta que ancha con todos los escalares distintos, entonces al tachar cualesquiera filas que la hagan cuadrada, el determinante de la matriz resultante no será cero.

De modo que ese es el truco para construir nuestra matriz A: como una matriz de Vandermonde. Usaremos como escalares los números de fila empezando en cero, y se elevarán a los números de columna empezando en cero. La primera fila será pues: 0⁰=1, 0¹=0, 0²=0, ..., 0^n-1=0; la segunda será 1⁰=1, 1¹=1, 1²=1, ..., 1^n-1=1; la tercera será 2⁰=1, 2¹=2, 2²=4, 2³=8, ..., 2^n-1, etcétera. Todas sus submatrices cuadradas de orden n serán entonces invertibles, que es la propiedad que buscábamos.

Ahora veamos cómo construir B para reconstruir los datos originales a partir de C’, que como hemos dicho, es un subconjunto de n elementos de C. Está claro que B tiene que ser una matriz cuadrada de orden n, ya que al multiplicarla por C’, que tiene n elementos, tiene que darnos D, que también tiene n elementos.

Fijemos nuestra atención por un momento en cómo se construye la matriz C. Cada elemento c_i es el producto de la fila i de A por la única columna de D. Construyamos ahora una matriz A’ cuyas filas sean únicamente aquellas filas de A cuyo índice i coincide con el correspondiente de cada elemento c_i en C’. Es decir, construyamos A’ de tal manera que se cumpla la relación A’D=C’.

Entonces ahora es obvio que para hallar D, basta con invertir la matriz A’ puesto que A’^-1A’D=A’^-1C’, luego D=A’^-1C’, por tanto la matriz B buscada es simplemente A’^-1. Sabemos además que A’ es invertible porque la hemos construido así a propósito.

Recapitulando lo que llevamos hasta ahora, se trata de construir un par de matrices A y B tales que al tachar cualesquiera m filas de A, la submatriz resultante siga siendo invertible; para reconstruir los datos a partir de un subconjunto C’ de n bloques de los n+m que hemos generado, construimos A’ como la submatriz de A resultante de dejar únicamente las filas que se corresponden con las presentes en C’, y al invertirla obtenemos B.

Veamos un ejemplo. Tomemos n=3 y m=2. Tenemos tres datos d₁, d₂ y d₃ a partir de los cuales queremos obtener cinco elementos c₁, c₂, c₃, c₄ y c₅. Construimos primero la matriz A y la usamos para obtener los bloques:

Ahora supongamos que sólo tenemos los bloques 1, 3 y 5 y nos faltan los bloques 2 y 4, y queremos reconstruir los datos d₁, d₂ y d₃. Construimos la matriz C’ que consta simplemente de c₁, c₃ y c₅ y construimos también A’, usando las filas 1, 3 y 5 de A, la invertimos y la multiplicamos por C’ para obtener D:

Como cortesía adicional, podemos refinar la matriz A para que cada c_i para i entre 1 y n sea igual a d_i. Para ello, se pueden convertir las n primeras filas de A en una matriz identidad mediante transformaciones elementales, que son unas transformaciones que no afectan a la invertibilidad de la matriz. El algoritmo a aplicar, que también nos sirve para invertir la matriz, se llama algoritmo de Gauss-Jordan. Está explicado en la referencia [2].

Muy bien, muy bonito, pero estamos trabajando con reales de tamaño arbitrario, no con enteros de w bits. ¿Cómo hacemos para que no nos aparezcan números racionales o demasiado grandes?

Los cuerpos de Galois

Un cuerpo finito o de Galois (abreviado GF) es un cuerpo con un número de elementos finito. Hasta aquí, obvio. El más simple es GF(2) que tiene dos elementos, llamémosles 0 y 1. En ese cuerpo, la suma se define igual que en la aritmética en módulo dos (es decir, equivale a la operación XOR) y el producto es el aritmético habitual, que al ser realizado sólo con los elementos 0 y 1, equivale a la operación AND.

Como curiosidad, existen cuerpos de Galois de orden primo y de orden la potencia de un primo, pero no de ningún otro. Por ejemplo, no existen cuerpos de Galois de orden 6, porque 6 no es primo ni es la potencia de un primo, pero sí de orden 9, porque 9 = 3² y 3 es primo. Para construir un cuerpo de Galois de orden primo p (como el caso p = 2 recién nombrado), se puede usar la aritmética en módulo p. Sin embargo, la adición y la multiplicación módulo pⁱ para i > 1 no forman un cuerpo, por lo que hay que emplear otro sistema para construirlo.

Para crear cuerpos de Galois de orden 2^w, se usan como elementos polinomios de grado w con coeficientes en GF(2), es decir, los coeficientes pueden ser sólo 0 y 1, y al operar entre ellos se aplican las reglas de GF(2). La suma es entonces suma de polinomios, pero al ser los coeficientes de GF(2), al sumar o restar dos coeficientes se hace en realidad un XOR entre ellos. El producto es... bueno, el producto es un dolor de muelas. Para calcularlo hay que hallar el producto de los polinomios, módulo un polinomio especial llamado generador, característico del cuerpo con el que estamos trabajando.

Para traducir los polinomios a números enteros, se guarda el coeficiente del término de grado i en el bit i del número. Así, por ejemplo, el polinomio x²+1 en GF(2⁴) se almacena en un entero con el valor binario 0101, es decir, el valor decimal 5. Para sumar (o restar) dos elementos del cuerpo, basta entonces con hacer el XOR bit a bit. En la práctica, para multiplicar de forma eficiente se usan una tabla de logaritmos y una de antilogaritmos, es decir, a*b=antilog(log(a)+log(b)), considerando a=0 y b=0 como casos especiales. La división se traduce igualmente como el antilogaritmo de la resta de logaritmos. (Esa suma y esa resta concretas se hacen en aritmética convencional módulo 2^w-1).

Lo más interesante es que las propiedades de las matrices con las que aquí trabajamos se mantienen cuando operamos en GF(2^w), con tal de que 2^w sea mayor que el número de filas y de columnas de la matriz. Esto nos permite trabajar todo el tiempo con enteros mientras las operaciones las realicemos en el cuerpo. Obsérvese que el RAID 3 equivale a trabajar con w=1 y construir la matriz A de la siguiente forma: las n primeras filas forman una submatriz identidad, y la fila n+1 consiste en todo unos. Aunque en ese caso no se cumple que 2^w > n+m, sí que se cumple que todas las submatrices de orden n de A son invertibles, que es el requisito principal.

El programa

Con todos esos datos ya se puede realizar un programa como el que yo requería. He escogido w=8 porque, además de trabajar con bytes, que es rápido, existe el problema de que el algoritmo de Gauss-Jordan es de orden O(n³) y el almacenamiento de las matrices requiere O(n²). Si hubiera escogido w=16, la matriz requeriría un mínimo de 8 Gb de memoria para almacenarla completa y el algoritmo de Gauss-Jordan prefiero no pensar cuántas operaciones requeriría. Con w=8, la matriz necesita a lo sumo 64 Kb y en el peor caso Gauss-Jordan requiere del orden de 8 millones de operaciones. El inconveniente es que no se puede dividir el archivo en más de 255 partes en total, pero era una solución de compromiso necesaria. De todas formas, para mis propósitos es suficiente. El polinomio generador que he usado es el que viene en el tutorial para w=8, o sea, x⁸ + x⁴ + x³ + x² + 1.

He probado a dividir un archivo de 4,4 Gb en 255 partes de las cuales 8 se podían perder. Lo he reconstruido tras quitar ocho partes elegidas a dedo. El resultado coincidía con el original tal y como se esperaba.

Aún no he decidido la licencia (probablemente será GPL2 o GPL3), y está pendiente de una limpieza para hacerlo presentable. Si hay demanda, tal vez lo haga público. ¿Alguien más quiere el programa?

Referencias

[1] http://www.cs.utk.edu/~plank/plank/papers/CS-96-332.pdf
[2] http://www.cs.utk.edu/~plank/plank/papers/CS-03-504.pdf

Escape del escape del escape

Reproduzco aquí esta entrada que en su día fue publicada en Uno por uno, uno...

---

Existe en muchos sistemas informáticos un medio para escribir caracteres que dentro del contexto en el que se escriben tendrían otro significado. Por ejemplo, en HTML se usa el símbolo & para introducir caracteres o comandos especiales; en las URLs el símbolo usado es el %, en MIME es el signo =, en el prompt de MSDOS era el signo dólar, y el lenguaje C y muchos otros derivados usan la barra invertida (\). Nada que objetar; es un excelente medio para conseguir incluir caracteres que podemos querer usar y la sintaxis del sistema en cuestión nos lo impediría sin ellos. Estos caracteres se suelen llamar «escapes», ya que nos permiten «escapar» de las limitaciones de dicho sistema.

De hecho, en casi todos los casos el propio carácter especial necesita una forma de ser expresado mediante sí mismo: el & se escribe & en HTML, el % se escribe %25 en una URL y el = se escribe =3D en MIME. Algunos han tenido una «feliz» idea: cuando se escribe dos veces el carácter de escape, significa el propio carácter de escape. Así, en el prompt de MSDOS se escribiría $$ para significar un solo símbolo dólar, y en C y similares, se usa \\ para indicar una sola barra invertida.

Pobres de nosotros, quienes tuvieron esa última ocurrencia de duplicar el carácter, no pensaron en las consecuencias. Valga como ejemplo el hecho de que el C, el sh, las expresiones regulares y el PHP emplean todos el mismo convenio de carácter especial (\) y duplicación para obtenerlo (\\).

Supongamos este escenario: tenemos que escribir en PHP una página web para un lugar que aloja archivos fuente en C, que admita que sus usuarios busquen cadenas de texto en dichos archivos con expresiones regulares. Por fastidiar, el PHP donde se va a alojar no tiene compilada la librería de expresiones regulares, así que la solución pasa por invocar el comando 'grep' de la línea de comandos. Algunas búsquedas comunes irán ya codificadas de antemano dentro del código PHP. ¿Cómo habría que escribir en PHP la cadena que buscara, en el código fuente en C, una ruta de un archivo como C:\Dir\Arch.txt?

En el archivo en C, esas cadenas vendrían escritas como "C:\\Dir\\Arch.txt", debido a la duplicación del carácter de escape. Así que eso es lo que tiene que buscar el grep. Pero, como las expresiones regulares también utilizan el mismo carácter de escape, en realidad la línea de comandos del grep debería parecerse a: grep 'C:\\\\Dir\\\\Arch.txt' *.c

Sin embargo, existe alguna incompatibilidad en los caracteres de escape dependiendo del shell (el ash también requiere que se duplique la barra invertida en las cadenas entre apóstrofes, a diferencia del bash; sólo las cadenas entre comillas son compatibles entre sí). De modo que, para asegurar que funcionará tanto en ash como en bash, en lugar de eso habría que prescindir de los apóstrofes y emplear comillas, teniendo que escribir: grep "C:\\\\\\\\Dir\\\\\\\\Arch.txt" *.c

¿Y qué cadena fija escribiríamos en nuestro fuente en PHP?

$cadena = 'grep "C:\\\\\\\\\\\\\\\\Dir\\\\\\\\\\\\\\\\Arch.txt" *.c';

Si todos los sistemas hubieran tenido el convenio de que para generar una barra invertida bastara con un carácter que NO es una barra invertida, la cosa sería mucho más sencilla. Por ejemplo, supongamos que la secuencia \k representara una barra invertida en todos los sistemas implicados en nuestro ejemplo. Entonces, el código fuente en C contendría algo como: "C:\kDir\kArch.txt", por lo que la línea de comandos del grep sería: grep "C:\kkkDir\kkkArch.txt" *.c, y nuestra cadena fija: $cadena = 'grep "C:\kkkkDir\kkkkArch.txt" *.c', lo cual únicamente significa agregar una k en cada nivel, mucho más inocente que la duplicación. Porque, imagínense, si esa cadena tuviera que ir escrita en algo como un generador para esos archivos PHP, quedaría así:

'$cadena = \'grep "C:\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\Dir\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\Arch.txt" *.c\';'

Así que, por favor, si alguna vez necesita escoger un carácter de escape, piénselo dos veces antes de elegir la barra invertida, y tres veces antes de decidir que la duplicación del carácter es una referencia a sí mismo.