Recursión normal y recursión con cola en Scheme/Racket

Aprovechando que salvo algún trabajo que debo tener hecho para la semana que viene he terminado este curso en la universidad y ya puedo vivir más tranquilo, me ha dado por experimentar con uno de los lenguajes de programación que he aprendido este año y que es sin duda el que más me ha atraído: Scheme, o concretamente el dialecto que hemos estado usando en clase, Racket.

Se dice que Lisp/Scheme son lenguajes de programación de uso principalmente académico, y probablemente sea cierto, pero la forma en la que está hecho Racket, con su gran librería estándar llena de funciones y sus módulos de distinto tipo, incluyendo GUI, redes, servidores web y expresiones regulares hacen que este lenguaje sea conocido fuera de lo estrictamente académico. Por lo que veo en Wikipedia, Racket es el lenguaje de programación bajo el que opera el servidor del sitio web Hacker News y es un lenguaje de script que han usado algunos juegos de Naughty Dog.

Introducción: Langton's Ant

En cualquier caso, ando este fin de semana intentando construir una implementación del autómata celular Langton's Ant (la Hormiga de Langton). En esencia, la hormiga de Langton consiste en un tablero bidimensional de celdas que pueden ser blancas o negras. Una hormiga va moviéndose por el tablero y en función de una serie de reglas va cambiando el color de las celdas entre blanco y negro.

Y uno de los lenguajes de programación que estoy intentando usar para llevar a cabo esto es Racket, simplemente por pura curiosidad. La idea es hacer una interfaz gráfica donde se vea representado el tablero de colores y donde pueda ver a la hormiga y la dirección que lleva.

Un burdo boceto de lo que quiero obtener. Atención a la hormiga, representada como una flecha, en la parte derecha del tablero.

La pregunta es, ¿cómo implementar esto? De forma iterativa es fácil ver que se trata de hacer más o menos lo siguiente:

mientras condicion
  evaluar reglas
  mover hormiga
  cambiar color celda
fmientras

¿Qué es condicion? Veamos. Está determinado que la hormiga de Langton tiene tres modos de conducta, y llegado un momento pasa de un estado a otro. De acuerdo con la información que hay en Wikipedia, no se ha podido demostrar matemáticamente que este cambio de estado sea verdadero siempre, pero en todas las combinaciones probadas hasta el momento ha ocurrido que la hormiga pase entre tres estados:

1. Simple, moviéndose bien y creando hasta estructuras agradables con los colores.
2. Caos, donde empieza a moverse de forma irregular y aleatoria.
3. Emergente, de forma espontánea comienza a avanzar en línea recta hasta salirse de los límites del tablero, dejando tras de sí una estela recta de grosor variable. Por esa estela este modo también es apodado "modo autopista" ya que a veces la estela es bastante gruesa.

Por lo tanto, si la hormiga tarde o temprano abandonará el tablero, puedo hacer que se itere hasta que la hormiga abandone el tablero. Esa será mi condición. Cuando la hormiga se salga de los límites del tablero ya no tiene sentido que continúe evaluando.

El problema es que Racket es un lenguaje funcional, donde la programación iterativa se convierte en recursión. No tengo interés en programar de forma imperativa con Racket ya que para ello hubiese usado desde el principio C o Java, por lo que debo implementar cada paso como una llamada recursiva. He visto simulaciones en YouTube y la hormiga puede dar millones de pasos hasta que abandona el tablero por lo que necesito una función recursiva que soporte ser recurrida miles y miles de veces sin reventar la pila del ordenador que estamos usando. Dada la cantidad de veces que puede iterarse, voy a considerar que lo que tengo es un bucle (casi) infinito por simplificar.

Es por ello que me puse a buscar en Internet cómo se puede implementar un bucle infinito en Scheme. Y el resultado es, que hay dos tipos de recursión: recursión normal y recursión de cola.

Recursión normal

La recursión normal es aquella en la que una función se invoca a sí misma, con la esperanza de obtener un resultado que luego pueda usarse dentro de la misma función para algo. Es decir, la llamada recursiva está en mitad del cuerpo de la recursión. Por ejemplo, en la función factorial se obtiene el factorial de otro número y luego ese valor se usa para otro cálculo, en este caso una multiplicación.

(define (factorial n)

  (if (= n 1) 1

      (* n (factorial (sub1 n)))))

Por dentro, este tipo de recursión trabaja creando nuevos marcos de pila (stack frames) cada vez que se entra en un nuevo ciclo de la recursión; el resultado es que cada llamada sube en la pila. Esto es así hasta que llegamos al caso base, donde se obtiene un valor. A partir de aquí, volvemos a bajar en la pila, entregándole un valor al siguiente frame, y repitiendo esto hasta el final. De este modo, es posible usar esta función en la práctica.

> (factorial 12)

479001600

El problema con la recursión normal está en que, si hay demasiados marcos de pila y se agota la pila, se produce un desbordamiento. No es posible crear más marcos de pila y por lo tanto no se puede continuar en la ejecución. Esto es lo que se conoce como stack overflow. Ocurre cuando, por ejemplo, quitamos el caso base en la función factorial. Se crean nuevos marcos, y más marcos, más marcos, más marcos hasta que la memoria dice ¡basta! y revienta. En DrRacket lanza un mensaje de error preguntando si queremos darle más memoria al programa.

(define (fact-inf n)

  (* n (fact-inf (sub1 n))))

> (fact-inf 12)

Interactions disabled

Recursión de cola

En este caso, la llamada recursiva es lo último que hace la función antes de terminar. No hay ningún tipo de operación que se haga después de la llamada recursiva. Sirva como ejemplo la definición de la función máximo común divisor.

(define (mcd x y)

  (if (= y 0) x

      (mcd y (remainder x y))))

> (mcd 4093 11060)

1

Un compilador que optimice código puede detectar esto y pensar "si lo último que hace esta función es llamarse a sí misma pero luego no necesito hacer nada más, ¿qué sentido tiene que mantenga el viejo marco de pila y cree otro nuevo por encima, si no voy a usar el viejo para nada?".

Y efectivamente, lo que hacen es que en vez de crear un nuevo marco de pila encima del viejo, simplemente reemplazan un marco por otro. De este modo, entre una llamada y la siguiente nunca se asciende en la pila, y por lo tanto, nunca se llega a saturar por culpa de la recursión.

El compilador de Racket optimiza la recursión de cola. De este modo, si quitase el caso base en mi función mcd, hiciese algún apaño al código para que no intente calcular y % 0, e intentase ejecutar este bucle infinito:

(define (mcd-inf x y)

  (mcd-inf y (remainder x (if (= y 0) 1 y))))

> (mcd-inf 4096 11000)

Lo que ocurriría es que esta función estaría llamándose a sí misma todo el rato, consumiendo CPU, claro está, pero sin consumir memoria. Mientras escribo esto la función sigue evaluándose en la ventana de DrRacket pero todavía no devuelve nada, y ya puede acabarse el mundo dentro de tropecientos mil millones de años que por entonces todavía estará mi ordenador ejecutando esta función sin descanso.

De hecho, puedo saber que no consume memoria porque en la parte de abajo de la ventana, no aparece el símbolo de reciclaje que indica que el recolector de basura está intentando hacer cosas, cosa que sí ocurre cuando lanzo la función fact-inf hasta que revienta.

Reciclaje cuando ejecuto fact-inf

Nada de reciclaje cuando ejecuto mcd-inf

Conclusión

Si quiero que mi hormiga pueda avanzar de forma infinita sin que la memoria RAM de mi ordenador pida clemencia y sobre todo sin que el sistema operativo o DrRacket detenga la ejecución del programa, debo usar recursión de cola. De este modo, puedo repetir mi función miles de veces sin que la memoria se resienta.

Habrá código. Al fin y al cabo, esto lo hago sólo por probar, no me llevo nada a cambio. No habrá ningún push hasta que acabe el programa, y tampoco lo voy a hacer hoy mismo porque tengo cosas que hacer, pero cuando termine el programa, lo cargaré en un repositorio de GitHub.

Modificando Unity para tenerle menos manía

Nunca le he tenido mucho aprecio a Unity, a veces de forma justificada y a veces de forma injustificada. Uno de los argumentos que siempre he tenido en su contra es lo mal planteado que está, y lo poco personalizable que es en comparación con otros entornos como XFCE, si bien esto no es nuevo. Es como si se hubiese puesto de moda en muchos entornos de escritorio dejar el sistema poco personalizable, haciendo que los usuarios que quieren tocar cosas tengan que instalar programas especiales, como Unity Tweaks, GNOME Tweaks, Elementary Tweaks, cuando en otros entornos como GNOME 2/MATE o XFCE tienes a tu disposición un ajuste más rico de cómo funciona tu ordenador, especialmente de cómo se ve.

Sin embargo, en un pequeño experimento que hice ayer, recompilé una versión modificada por mí de Unity-2D 5.14 (la versión que se usa en Ubuntu 12.04 LTS) para adaptarla un poco a mis necesidades y tenerle menos manía. Y básicamente, quería compartir los cambios que hice.

Mi cambio ha consistido en modificar el código fuente del panel superior de Unity-2D para que la barra de menús sea siempre visible. No me gusta que el menú sea sólo visible cuando se mantiene el ratón por encima. Me parece más útil poder escanear con el ojo dónde está el menú en el que quiero hacer clic antes de empezar a mover el ratón, para poder mover el ratón justo donde quiero; y no que tal y como está planteado Unity, tengo que mover primero el ratón arriba para ver el susodicho menú.

Ya sé que no es el mejor momento para hablar de menús con la controversia que hay sobre si la barra de menús debe desaparecer o no. Entiendo que en muchas aplicaciones sea un elemento inútil que sólo pone los mismos comandos que hay en la barra de herramientas de forma jerarquizada. Sin embargo, dado el trabajo que hago con el ordenador y las aplicaciones que uso (entornos de desarrollo como Eclipse, edición de vídeo como Kdenlive, edición de imagen como GIMP, edición de audio como Audacity...), que son aplicaciones que se controlan fundamentalmente con la barra de menús, no tener acceso a este elemento sería una gran pérdida de usabilidad a mi punto de vista.

Como una screenshot vale más que mil palabras, he aquí el aspecto final de mi panel de Unity y debajo comento cómo lo he logrado, que es muy simple:

Como se ve, el panel superior ahora se comporta tal que así:

1. Cuando la aplicación tiene tamaño normal (no maximizada), la barra de menús nunca se oculta. El nombre de la aplicación de la izquierda tiene un tamaño variable, es decir, nunca es tapada por el menú, a diferencia de lo que hace Ubuntu por defecto, si no que es el menú el que se desplaza a la derecha.
2. Cuando la aplicación se maximiza, en vez de mostrarse la barra de título de la ventana, se sigue mostrando el nombre de la aplicación, como antes. Es decir, no puedes ver el título de la ventana cuando la aplicación se maximiza. Podría ser una deficiencia, pero tampoco suelo maximizar la mayoría de las ventanas, excepto Chrome quizás, pero Chrome tampoco te muestra el título de la ventana por defecto así que me da igual. Ahora está de moda que los entornos de escritorio te oculten cosas que ellos consideran "redundantes", sea la barra de menús, sean los botones de la ventana (vease las ventanas de GNOME Shell que no tienen botón minimizar ni botón maximizar), sea el menú Inicio (vease Windows 8)... por lo tanto, no creo que nadie tenga valor a decirme que soy un desalmado por "ocultar algo que podría ser importante" cuando ellos no hacen más que ocultar cosas que para mí si son importantes.
3. Cuando se pone el ratón sobre el panel en una aplicación maximizada, se muestran los botones de ventana, como antes. El espacio para mostrar el nombre de la aplicación se reduce y por ende las letras finales se desvanecen. La barra de menús no se mueve ni un píxel.

Este hecho lo recalco en negrita porque me parece importante que la barra de menús no se mueva ni un pixel. Al fin y al cabo, esto es como antes, ¿de qué te sirve que el usuario escanee con el ojo el menú en el que va a hacer clic si cuando pone el ratón encima, se mueve a la derecha o a la izquierda?

Finalmente, comparto el código. Por ahora el cambio sólo funciona en Unity-2D. Tengo que ver cómo integrarlo en Unity, pero por ahora no me parece apetecible ya que estoy usando Ubuntu 12.04, el cual dentro de dos semanas seguramente se actualizará por la siguiente LTS, Ubuntu 14.04, de esperar con una versión nueva de Unity, lo que seguramente hará que tenga que reescribir mi cambio, así que no me merece la pena modificar eso ahora. Esto que hice ayer fue sólo un experimento.

Sólo tengo que modificar el archivo panel/applets/appname/appnameapplet.cpp, que es el archivo encargado de mostrar la parte izquierda del menú. Y concretamente todos los cambios se centran en la función AppNameApplet::updateWidgets(), que es la que se llama cuando se quiere actualizar la apariencia del panel. Aquí está el snippet. Está embebido al final de este post, ya que es un poco largo. Por describir los cambios que hago:

1. Como se ve en la línea 105, la barra de menú ahora es visible siempre, no sólo si la variable showMenu, que se pone a true cuando el ratón se sitúa sobre el widget, está activa (línea 104).
2. En la línea 76, el título negrita que hay a la izquierda ahora muestra siempre el nombre de la aplicación. Antes, si la ventana estaba maximizada se mostraba el título de la ventana (como se determinaba en el IF que hay entre las líneas 66 y 75).
3. El ancho de este título ahora es flexible, como se ve entre las líneas 91 y 95. QFontMetrics es una clase que te puede decir cuántos píxeles mide una cadena de caracteres. Es la que uso para hacer que el ancho de la etiqueta sea lo que vaya a medir el texto que lleva dentro. Antes, si el menú estaba oculto, el ancho era toda la barra de menús, y si el menú estaba visible era un tamaño pequeño para que el menú se quedase siempre a la izquierda; líneas 86 a 90.
4. Anteriormente, si ponías el ratón sobre la barra de menús en una aplicación maximizada, el título de la ventana se ocultaba (línea 97). Pero eso antes no era un problema porque la barra de menús siempre se iba a mostrar a la izquierda. Ahora que se puede desplazar horizontalmente si el título de la aplicación es largo, es necesario meter algo de hueco a su izquierda para que la barra de menús siga en la misma posición. Y como me daba igual lo que fuese, en vez de dejar el espacio en blanco puse otra vez el título de la aplicación, aunque restando el tamaño de los botones de ventana para que no se moviese el menú. Esto lo hago entre las líneas 98 y 101.

Ya digo que no me extrañaría nada que en el Unity que traiga Ubuntu 14.04 las cosas hayan cambiado algo y deba reescribir este código de cero. Lo haré sin problemas. Esto era una prueba de concepto. Habrá a quien no le guste esta forma de usar el menú, y lo entenderé. Pero este cambio es mío, para mí. Esto es parte del software libre. Poder modificar el código para que el software se adapte a tí. ¿O serías capaz de modificar el código fuente de Windows para hacer que se comporte como tu quieras? Creo que no.

Tontunada: conversor ASCII a MinisterioScript (sgsdfgsdfgfg)

Me he levantado curioso y con ganas de hacer algo.

Es posible que hayáis visto ya este vídeo que está circulando últimamente por las redes sociales, especialmente dentro del círculo de quienes estamos metidos en esto de la programación. El vídeo fue subido en 2011 por el Ministerio de Educación y forma parte de una serie de vídeos donde se promueve la formación profesional. En uno de los vídeos se presenta a una persona que supuestamente es programador. Sin embargo, mientras en el anuncio se muestran tomas de él programando, en una de ellas se enfoca a la pantalla y se ve un curioso lenguaje de programación.

Si no lo habéis visto aún, aquí va. La parte interesante está en el segundo 0:17:

Si el gobierno de España quiere mostrarnos la coña que tiene, yo quiero mostrar que puedo tener más coña que ellos aún. Por eso, antes de que se apruebe la ley de seguridad ciudadana y alguien pueda considerar esto "ofensa contra el gobierno", he construido este conversor entre ASCII y MinisterioScript, en 10 minutos.

Está hecho en Python y su funcionamiento, para los curiosos, es el siguiente:

• Podemos convertir un texto de ASCII a MinisterioScript. El conversor toma cada caracter de la cadena que se le proporcione, y lo convierte a un número binario. Después, esos 8 bits los toma en grupos de 2 (por ejemplo, 10110100 lo toma como 10, 11, 01 y 00), y para cada uno de esos pares lo transforma en una letra (por ejemplo, el 00 lo transforma en una s, el 01 en una d... y así).
• Podemos convertir de vuelta un texto en MinisterioScript a ASCII. El funcionamiento es justo a la inversa: va tomando cuatro caracteres del texto y esos cuatro caracteres los convierte en número binario y de ahí a texto en ASCII.

Ni que decir tiene que lo he hecho en 10 minutos así que seguramente tendrá fallos o habrá cosas que se podrían mejorar pero como algo rápido, ha estado bien. Por ejemplo, he probado a convertir "Hola, mundo" a MinisterioScript y queda algo como esto: dsfsdfggdfgsdfsdsfssdfgddgdddfgfdfdsdfgg. Seguramente el tipo del anuncio sabrá lo que quiere decir.

Os dejo el código por aquí, y yo me voy a desayunar algo.

Por qué SumatraPDF le da mil vueltas a Adobe Acrobat

Si hablamos de PDF, inmdiatamente se nos viene a la cabeza Adobe Acrobat. Siendo Adobe el desarrollador del formato PDF, y Adobe Acrobat Reader el primer lector de PDF disponible, es normal que se haya ganado con el paso de los años una reputación en el mercado de lectores de PDF. Sin embargo, es importante darse cuenta de que aunque es el lector de PDF más destacado, no es el único lector de PDF que existe, y que de hecho los hay mejores. ¿Qué me lleva a criticar a Adobe Acrobat Reader o Adobe Reader, ese programa que todo el mundo tiene y que es capaz de leer cualquier PDF? Bueno, pues el rendimiento del programa, algo que francamente valoro mucho más que las características.

Adobe Reader X permite compartir documentos en Acrobat.com, leer en voz alta documentos si el sistema tiene un TTS, anotar, subrayar, marcar… ah, y leer documentos PDF. El problema de tener tantas características es que reducen notablemente el tiempo de carga del programa, porque necesita iniciar todos esos complementos que, no se vosotros, pero yo no he usado nunca, porque yo abro un lector de PDF para leer un PDF, no para decirle a nadie qué estoy leyendo, ni para marcar nada. En cambio, SumatraPDF es un programa que permite leer PDF. Lo que yo quiero. Y mientras que Adobe Reader X tarda 2 segundos en abrir únicamente la pantalla de carga, SumatraPDF tarda también 2 segundos, pero en mostrar la pantalla principal con el documento cargado.

Adobe Reader X necesita más de 200 MB de disco duro para funcionar. ¿Un programa que lee PDF necesita 200 MB? Si echamos un vistazo atrás, con cada versión de Adobe Acrobat los requisitos de disco duro se han incrementado por varias decenas de megabytes. Adobe Acrobat 4.0 ya necesitaba 60 MB de disco duro para instalarse. En cambio SumatraPDF necesita menos de 2 MB de disco duro para funcionar y al no tener tantos archivos instalados hacerlo portable es tan sencillo como copiar el ejecutable SumatraPDF.exe en un pendrive y llevárselo a otro ordenador.

Cuando compré mi portátil nuevo, y lo encendí, una de las primeras pantallas que ví fue “Adobe Reader tiene actualizaciones disponibles para instalar”. La siguiente que vi fue la del desinstalador de Adobe Reader. Hecho eso, instalé SumatraPDF y ahí sigue marcado en el menú Inicio de mi ordenador. No tengo interés en usar Adobe Reader. En mi tableta utilizo Mantano PDF Reader cuando no quiero leer un PDF desde el ordenador, porque sea muy largo o porque me apetezca leer tumbado.

Adobe Acrobat Reader 3.0 (1996). Windows 3.1. 5 MB de disco duro.

Adobe Reader X (2010). Windows 7. 260 MB de disco duro.
Foto obtenida de Wikipedia en inglés.

SumatraPDF 1.9 (2012). Windows 7. 1,74 MB de disco duro.

Modificar las páginas de documentos PDF

En la entrada anterior hablé de cómo instalar y usar PDFCreator para generar documentos PDF de una forma tan sencilla como simplemente mandarlos a imprimir. En la segunda parte de este tutorial explicaré cómo modificar un documento PDF ya creado.