Tipos y árboles en Ocaml

Aunque en Ocaml existen infinitos tipos de datos (partiendo de las combinaciones de los tipos primitivos del lenguaje), puede en un momento resultar útil dar un nombre más práctico a un tipo concreto. Con ese nombre no nos referimos a un dato concreto, sino al conjunto de todos los que pertenezcan a ese tipo. Por ejemplo, en pascal podríamos hacer algo muy simple:
type entero = integer;
Con esto, conseguiríamos poder emplear la palabra «entero» en nuestros programas para referirnos a los números enteros del conjunto «integer«. Puede resultar útil cuando queramos hacer nuestro código más legible. En Ocaml, esto se realiza mediante la expresión «type» y su sintaxis es la siguiente:
# type <nombre_de_tipo> = <nombre_de_constructor> of <esquema_de_tipos>;;
Tambien podemos definir varios constructores de la forma habitual en la sintaxis de Ocaml:
# type <nombre_de_tipo> =
        <nombre_de_constructor_1> of <esquema_de_tipos_1>
      | <nombre_de_constructor_2> of <esquema_de_tipos_2>
      | ...
      | <nombre_de_constructor_n> of <esquema_de_tipos_n>;;

La forma más sencilla es entenderlo con un ejemplo básico. Imaginemos que queremos representar un reloj mediante un par de enteros: el primero es la hora y el segundo los minutos. Algo tal que (00, 00) para representar la medianoche y (12,30) para representar las 12 horas y 30 minutos del mediodía.
Es fácil construir un tipo «reloj».
# type reloj = Hora of int*int;;
Y si queremos crear un reloj, usaremos el constructor «Hora» con el par que nos interese (por cierto, los constructores deben empezar por letra mayúscula):
# Hora (12,30);;
- : reloj = Hora (12, 30)

Quizás para algo tan sencillo no sería demasiado útil definir el tipo «reloj«, ya que a fin de cuentas los pares int*int y, en general cualquier tipo, ya existe en Ocaml sin necesidad de ser definido por el usuario. Pero debemos reflexionar sobre la naturaleza de los programas. Por sí mismo, ningún programa tiene sentido, sólo el que el usuario le otorgue. Yo puedo tener un programa con un montón de celdas numéricas que pueden comunicarse entre sí; aunque el sentido que yo le doy es que es una hoja de cálculo, o una base de datos, etc. Digamos que los tipos definidos por el usuario suponen la capa de información que conecta un programa con el sentido que un usuario vé en el mismo. Están ahí para aportar claridad al código y también para ayudarnos a abstraernos durante el desarrollo.

Esto nos lleva a pensar que los tipos definidos por el usuario son interesantes para trabajar de forma más comprensible con datos brutos. En la asignatura de PD, se ven para poder explicar cómo construir árboles en Ocaml, que no son más que otra forma de estructurar la información. El lenguaje ya «trae» incorporadas algunas estructuras, como las listas o las tuplas, pero no los árboles asi que… ¡¡Construyamos un árbol!!

Árboles
Como sabemos, un árbol puede almacenar cualquier dato, asi que nuestro árbol será un ‘a arbol (se lee alpha arbol). Esto pone sobre aviso al compilador de que nuestro dato es polimórfico, asi que:
# type 'a arbol =
Vayamos con la primera regla. Se trata el caso de que el árbol sea el árbol vacío con lo que no habrá que hacer nada. Simplemente ponemos un constructor vacío y pasamos a la siguiente regla.
# type 'a arbol =
        ArbolVacio
      |

Para el constructor del árbol, tenemos que pensar que se trata de una estructura de naturaleza recursiva. Cada nodo del arbol contiene un dato y de él derivan unos hijos, que a su vez son nodos con dato y más nodos hijos. De modo que, cada nodo es el par que contiene:
(dato, lista de nodos hijos)
En código, representamos el par de tipos con el simbolo *, tal y como lo haría Ocaml.
# type 'a arbol =
        ArbolVacio
      | ArbolNodo of 'a * 'a arbol list;;

Ahora podemos crear árboles vacíos:
# ArbolVacio;;
O árboles con raiz, pero ningún hijo en su lista:
# ArbolNodo ("dato_raiz", []);;
Fíjate que en este caso el tipo del árbol ya cambia para ser un árbol de strings, ya que en su raiz hemos guardado la cadena «dato_raiz». Su lista de hijos es una lista vacía. Si quisiesemos añadir hijos, lo haríamos…
# ArbolNodo ("dato_raiz", [ ArbolNodo("dato_hijo1",[]) ; ArbolNodo("dato_hijo2", []) ] );;
He ahí un árbol con dos hijos. En la lista de cada uno de ellos podríamos añadir aún más nodos.
Llegados a este punto, es fácil saber como dar nombre a un elemento árbol. Solo tenemos que recurrir a un «let» normal y corriente, por ejemplo:
# let a1 = ArbolNodo ("dato_raiz", []);;

Árboles n-arios
En el ejemplo anterior, podríamos añadir hijos a la lista de hijos de un nodo de forma indefinida, porque estos estaban ubicados en una lista. Pero de nuevo nos asalta un problema. ¿Que pasa si queremos ceñirnos exclusivamente a árboles binarios (dos hijos por nodo como máximo)? ¿O a árboles ternarios (tres hijos por nodo como máximo)?
La solución pasa por sustituir la lista de la definición por alguna expresión que fije la cantidad de hijos de un árbol. Podemos pensar de nuevo en que un árbol binario viene dado por una terna en la que la primera componente es el dato de su raiz, la segunda su hijo por la izquierda y la tercera su hijo por la derecha.
(raiz, hijo_izda, hijo_dcha)
Definamos un arbol binario entonces, usando unos constructores con nombres distintos para no machacar los anteriores:
# type 'a arbolbin =
        ArbolbinVacio
      | ArbolbinNodo of 'a * 'a arbolbin * 'a arbolbin;;

¿Que ha cambiado? Además de los nombres, hemos sustituido una lista de elementos ‘a arbol por dos árboles ‘a arbolbin. El primero es el hijo de la izquierda y el segundo el de la derecha, tal y como habíamos razonado antes.
Un árbol ternario (tres hijos) sería simplemente una extensión de esta idea:
# type 'a arbolter =
        ArbolterVacio
      | ArbolterNodo of 'a * 'a arbolter * 'a arbolter * 'a arbolter;;

Por último, en un arbol genérico no sería legal hacer:
# ArbolNodo ("dato_raiz", ArbolVacio);;
porque la segunda componente del par debía ser una lista, y no un elemento ‘a arbol. Sin embargo ahora tenemos definidos el segundo y tercer elemento de la terna como árboles binarios ‘a arbolbin, así que sí podemos recurrir al constructor «ArbolbinVacio«:
# ArbolbinNodo ("dato_raiz", ArbolbinVacio, ArbolbinVacio);;

Por lo tanto, un árbol con dos hijos en el que el hijo de la derecha tenga a su vez otro hijo por la derecha…
# ArbolbinNodo ("raiz", ArbolbinNodo ("hijo_i", ArbolbinVacio, ArbolbinVacio), ArbolbinNodo ("hijo_d", ArbolbinVacio, ArbolbinNodo ("hijo_d_d", ArbolbinVacio, ArbolbinVacio)));;
Esto se correspondería con:

Algunos consejos definiendo árboles
Ya hemos hablado de dar nombres diferentes a los constructores para no machacar otros que hubiera previamente para otros tipos, pero hay otros consejos más. En la asignatura de PD de nuestra facultad, se suelen utilizar palabras en inglés como constructores, por ejemplo:
# type 'a bintree =
        Empty
      | Node of 'a * 'a bintree * 'a bintree;;

Se hace por convención, pero deberían explicarnos que las palabras se puede escojer a nuestro libre albedrío (respetando algunas limitaciones puntuales que no voy a explicar aquí pero que están reflejadas en el manual del lenguaje, como por ejemplo que el nombre comience por una letra mayúscula).
Con los árboles (y en general, con estructuras de datos) lo más normal sería definir un tipo polimórfico (que almacene cualquier dato) como vimos en la explicacion. Pero si queremos limitarlos a tan solo ser usados con, por ejemplo, enteros, bastaría con eliminar el alfa de nuestra definición. Este árbol solo podría guardar números enteros y nada más.
# type inttree =
        Empty
      | Node of int * inttree * inttree;;

Y la otra cosa importante es… ¡¡no liarse con los cierres de paréntesis, corchetes y demás parafernalia!! Así que ya sabes: trabaja con tu editor preferido y siempre que abras uno de ellos, escribe directamente a continuación su cierre. Imagínate un árbol de, pongamos, 5 niveles de altura. ¿Estás dispuesto a buscar cual puede ser el paréntesis que te falla? En serio, vale la pena ser ordenado al escribir código.

Nada más por ahora, aunque espero poder hacer una pequeña entrada sobre cómo trabajar con árboles y definir algunas funciones relacionadas. 🙂

Convertir VRO a AVI en Ubuntu

Personalmente llevaba ya unos días intentando convertir un archivo .VRO de una cámara de vídeo a un archivo .AVI que fuese más manejable. En Windows hubiese sido coser y cantar buscar cualquier herramienta de autoría de DVD, o una herramienta tipo «vro2avi» o algo similar…
Sin embargo no renuncié a hacer esto en Ubuntu con software libre y un poco de paciencia. Para empezar, debemos instalar una herramienta hábil en la conversión de formatos multimedia. En este apartado el rey es ffmpeg. Si no lo tienes instalado, puedes introducir la siguiente orden en una shell:
$ sudo apt-get install ffmpeg
Por defecto soporta multitud de formatos, pero añadiremos una librería para poder codificar audio en mp3:
sudo apt-get install libavcodec-extra-52
Hay otras formas de habilitar la compresión mp3 en ffmpeg, pero ésta me ha parecido idónea.

Vamos allá con el proceso:
Lo básico que necesitamos saber de ffmpeg es que desde la terminal tenemos que indicar el archivo de entrada (con la directiva -i de input), los parámetros y el archivo resultante. Por ejemplo:
$ ffmpeg -i VR_MOVIE.VRO -acodec copy -vcodec copy VR_MOVIE.MPG
Esta orden simplemente cambia los datos de un contenedor VRO a un contenedor MPG. Como se puede deducir de la sintaxis, el audio codificado será una copia del original, lo mismo que con el vídeo. Podemos ahondar un poco más en este apartado añadiendo directivas. Comencemos con el audio:
$ ffmpeg -i VR_MOVIE.VRO -acodec libmp3lame -ac 2 -ar 48000 -ab 128k -vcodec copy VR_MOVIE.MPG
Como se puede ver, solo hemos variado los parámetros de la codificación de audio, y son:
-acodec libmp3lame: indicamos cual es el compresor de audio, en este caso mp3
-ac 2: indicamos el numero de canales del audio. Un solo canal es el tradicional «mono», dos canales es sonido «estéreo» y 5.1 canales es el audio envolvente de, por ejemplo, una pelicula dvd. Como el audio original solo está en estéreo, lo mantenemos así.
-ar 48000: Es el numero de veces que el audio es muestreado por segundo. El ratio del audio original era de 48000, pero otro valor habitual (por ejemplo el de un CD de música) es 44100 hertzios. Es el número de muestras que se toman por segundo para conformar la onda de sonido almacenada en la grabación. Lo mejor es dejarlo como en el original.
-ab 128k: es la calidad con la que el codec mp3 codificará la onda de sonido. Un valor aceptable puede ser 128 kilobytes (de ahí la k tras el número) aunque puede ser insuficiente para un oído bien entrenado. Mucha gente está optando por codificar a 192 kb. Tambien podemos optar por una opción intermedia como es 160k.

Ahora refinemos un poco el vídeo:
$ ffmpeg -i VR_MOVIE.VRO -acodec libmp3lame -ac 2 -ar 48000 -ab 128k -vcodec mpeg4 -qscale 3 -g 300 -deinterlace -aspect 16:9 -s 512x288 -f avi VR_MOVIE.AVI
En este caso los parámetros del video son:
-vcodec mpeg4: es la implementación del estándar MPEG-4 (padre de por ejemplo divx, xvid, etc.). Hay otras opciones como mpeg2video (para MPEG-2, como en un DVD), pero recomiendo MPEG-4 por su buena relación calidad/compresión y su creciente aceptación en reproductores domésticos, teléfonos móviles, etc.
-qscale 3: se trata de la calidad general que se busca en el video. Cuanto más alto es el número, más se comprime y peor se vé. Lo ideal es 3 o 2, reservando el 1 únicamente para casos muy concretos donde se necesite una calidad máxima. Del 3 en adelante, la pérdida de nitidez es apreciable.
-g 300: se trata de una opción bastante avanzada. Agrupará los fotogramas en grupos de 300 para que sea más facil comprimir los que sean similares. En cierto modo, ayuda a mejorar la imagen. No te recomiendo que modifiques este valor a no ser que estés muy seguro.
-deinterlace: desentrelaza las líneas del video, dando a las imagenes un aspecto más suave.
-aspect 16:9: aplica un ratio de aspecto al video. Hay bastantes opciones disponibles, pero las más habituales serían 4:3 (como la televisión cuadrada de toda la vida), 16:9 (el de bastantes películas) y 16:10 (ligeramente más alto que 16:9, pero bastante común tambien). Si el video se reproduce deformado (como en mi caso), prueba a utilizar esta opción, pero omítela si se ve bien.
-s 512×288: sirve para cambiar el tamaño del video. Apenas tiene impacto en el tamaño del archivo, pero si reduces mucho la resolución, se verá bastante peor. Lo ideal es tratar con el original. Un dvd tiene una resolución de 720×576 píxeles, mientras que un blu-ray tiene 1280×720 (HD Ready) ó 1920×1080 (Full HD). Si por ejemplo quiero que el ancho sea de 512 pixeles, debo calcular el alto con una simple regla de tres:
alto_original * nuevo_ancho / ancho_original = nuevo_alto
1080 * 512 / 1920 = 288 píxeles

-f avi: fuerza que el nuevo contenedor sea un archivo avi (fíjate en que tambien hemos cambiado la extensión del archivo de salida).

Volviendo a mi caso, tenía un video grabado con la videocámara de atryx. Añadí alguna opción más como -async 1 para mejorar la sincronización del audio con el vídeo y el resultado fué perfecto.
$ ffmpeg -i VR_MOVIE.VRO -acodec libmp3lame -ac 2 -ar 48000 -ab 128k -async 1 -vcodec mpeg4 -qscale 3 -g 300 -deinterlace -s 720x405 -aspect 16:9 -f avi VIDEO.AVI
Hay otras opciones muy interesantes y la documentación de ffmpeg es excelente para consultar su funcionamiento.

The Decemberists: The King is Dead

Así se titulará el nuevo trabajo de la que es posiblemente mi banda favorita. «The King is Dead» abre el abanico de sonidos rockeros sumergidos en «The Hazards of Love» sin perder ni un ápice del estilo característico del grupo. El álbum sale a la venta el día 18 de enero de 2011 y ya tenemos varias perlas a nuestro alcance. En primer lugar, el que será el single de presentación «Down by the Water» (reminiscencia de los dos anteriores trabajos) pero también las grabaciones de aficcionados que se pueden encontrar en youtube:

Las colaboraciones vuelven a ser de lujo: Peter Buck, guitarrista de REM (con una guitarra de 12 cuerdas) y Gillian Welch, conocida por su actuación en la película O Brother Where Art Thou haciendo gala de una gran voz (a mi personalmente me suena muy country, lo que añade un buen contrapunto a la tesitura de Colin Meloy).

Las nuevas canciones son:
1. Don’t Carry It All
2. Calamity Song
3. Rise to Me ( http://www.youtube.com/watch?v=uoRLoFE4-WA )
4. Rox in the Box
5. January Hymn
6. Down by the Water
7. All Arise!
8. June Hymn ( http://www.youtube.com/watch?v=uZSpIWSB1RA )
9. This is Why We Fight
10. Dear Avery

En youtube hay unas cuantas más disponibles: Calamity Song, Rox in the Box, … ¡¡Quiero que llegue Enero!!

Web del grupo
La noticia en Tanaka Music

Una nueva inquietud: sistemas operativos

Leía hace un par de semanas en El lado del mal una entrevista a Matías Vara, el creador de TORO Kernel.

Se trata de todo un kernel escrito exclusivamente en lenguaje Pascal, que Matías vé como un lenguaje muy apropiado para programar sistemas operativos por la claridad con la que se pueden escribir algoritmos. Como Pascal es el lenguaje con el que nos iniciamos en la programación en nuestra facultad (aunque algunos conozcan otros previamente), sentí curiosidad por el tema y me bajé el codigo fuente del proyecto TORO.
Ahí hay mucho trabajo y horas invertidas, y evidentemente mis conocimientos de Pascal no alcanzan tal grado de comprensión, sobretodo porque tampoco he cursado la asignatura de SO1 todavía. No obstante, he procurado conseguir el libro «Sistemas operativos: diseño e implementación», de Andrew S. Tanenbaum y Albert S. Woodhull.

Incluso trae todo el codigo fuente (impreso y en cd-rom) del kernel Minix, un kernel escrito por el propio Tanenbaum para ilustrar con un ejemplo real (y util) los conocimientos vertidos en el libro. De hecho, el codigo ha evolucionado y hoy en día se ofrece como un SO bastante evolucionado en su sitio web oficial: http://www.minix3.org/
En todo este asunto he encontrado una renovada inquietud por el tema, en el que realmente no me había detenido tanto como en esta ocasión.

Ampliar RAM del EeePC

Hace tres semanas, mi pequeño netbook cumplió dos años y para celebrarlo le he «regalado» una ampliación de memoria RAM. El ordenador venía con 1gb de serie y he cambiado el modulo de memoria original por uno de 2gb, que no le sientan nada mal al ser mi principal ordenador actualmente.
Probablemente la actualización más interesante de todas sea sustituir su disco sólido de 16gb por uno más rápido y grande, como está haciendo bastante gente. De vez en cuando salen algunos modelos de SSD realmente buenos y diseñados para su uso en netbooks. Sin embargo, por menos de 40 € la ampliación de memoria es un caramelo muy apetecible y además la capacidad es mucho más que suficiente para mí, al disponer tambien de un disco externo.
Ahora, tener abierto Netbeans con varias pestañas y al mismo tiempo que Chrome y Evolution no es una tarea tan pesada como antes y el sistema funciona con mayor soltura.

En la imagen se puede ver cómo Ubuntu ha reconocido el cambio sin ningún tipo de problemas y sin tener que tocar nada. Puedes consultar la memoria de tu pc con el comando free.

En youtube se pueden encontrar bastantes videos que explican como sustituir el viejo módulo de memoria, particularmente he visto este:

En cualquier caso, la memoria ram funciona a unos nada fascinantes 533Mhz, por lo que conviene seguir siendo cuidadosos con las aplicaciones que se utilizan. Por ejemplo, ¿porqué no utilizar el editor Abiword en lugar del pesado OpenOffice.org Writer? ¿Chrome en lugar de Firefox? Y mejor aún: ¿Gnumeric en lugar de Calc?
Mantener el sistema a dieta ayudará (y mucho) a que nuestro pc nos brinde unas mejores sensaciones.