Mamma Mia, here I go again
Discover more from La Naturaleza del Software
Mamma Mia, here I go again
Suecia, el país de Volvo, Electrolux, H&M, Ericsson, el Bluetooth y por supuesto, ABBA.
En los setenta, ABBA era la banda que más vendía discos en todo el planeta. El mito dice que ABBA representaba una importante porción del PIB sueco, algo muy improbable, porque Suecia en esa época ya era un país muy próspero.
Agnetta, Bjorn, Benny y Anni-Frid saltaron a la fama mundial en 1974, tras ganar el festival de Eurovision. con el super éxito Waterloo. En este video pueden ver su presentación en Eurovision, con un estilo muy glam, que era lo que estaba de moda en esa época:
Abba en Eurovision 1974
La belleza de Agnetta y Frida, es lo que más recuerdo de mi niñez sobre este grupo, porque mi padre era fan de ABBA, así que escuchábamos sus canciones casi todo el tiempo. Siendo más adolescente traté de alejarme de ese tipo de música, pero ya era tarde. A pesar de mi resistencia, el virus de ABBA invadió mi ADN musical y dejó su marca para siempre.
Hasta que en 2008, junto con mi familia, vimos la película “Mamma Mia!”, esas melodías habían estado fuera de nuestra casa. Pero volvieron y nos atraparon, como un placer culpable, debo confesar que me he vuelto mi padre, y de vez en cuando disfruto escuchando las viejas canciones de ABBA.
Pero este post no es para contar la historia del cuarteto, que es muy conocida. No, ésta es la historia de otro producto sueco, y principalmente de un inglés que ayudó a crearlo. Un hombre que nació el mismo año que Agnetta Fälsktog, y que a los diecisiete años, mientras la bella cantante entraba en los charts musicales de su país, decide aprender a programar, y de paso adquiere una pasión por este oficio que nunca abandonó. Y aunque tardó en obtener el reconocimiento que merecía, su historia debe ser contada en este blog, puesto que es uno de mis héroes personales.
Waterloo
At Waterloo Napoleon did surrender
Oh yeah, and I have met my destiny in quite a similar way
Joe Armstrong nació en Inglaterra, en 1950. Mientras Agnetta Fälsktog alcanzaba las listas de popularidad de su país, con un éxito tras sólo un año de carrera, nuestro héroe luchaba con las tarjetas perforadas y el lenguaje FORTRAN para aprender a programar el computador de su instituto.
Al ingresar a la universidad, sin embargo, decide estudiar física y seguir un doctorado en esa materia, y no en informática, curiosamente.
Armstrong cuenta que durante la universidad tomó varios cursos que requerían programación, pero que desarrolló una habilidad especial para depurar programas, así que ayudaba a otras personas a corregir los errores en su código. La tarifa estaba expresadas en cervezas, habían problemas de dos, tres cervezas, o más. Muchas veces su trabajo consistía en simplificar el código de sus “clientes”, una de las cosas que más le llamaba la atención es que las personas codificaban de la manera más complicada posible, y esa era la causa de varios de sus errores.
Su supervisor de tesis le había dicho en varias ocasiones: “no deberías estar haciendo un doctorado en física, tu amas las computadoras”, pero Armstrong se negaba, “tengo que finalizar esto que estoy haciendo”, insistía. Pero a la larga resultó que su profesor tenía toda la razón.
Pero en medio de sus estudios Armstrong sufre el primero de los muchos percances de su carrera. T[iene que abandonar sus estudios de doctorado por razones económicas. Atrás quedan sus sueños de estudiar la física de altas energías. Necesitaba dinero,ganarse la vida y quizás ahorrar algo para poder retomar su carrera.
Super Trouper
I was sick and tired of everything
When I called you last night from Glasgow
En ese tiempo, al visitar la biblioteca de su universidad encuentra unos enormes volúmenes titulados “Machine Intelligence”, que venían del departamento del mismo nombre de la universidad de Edimburgo, editados por Donald Michie y Jane Hayes Michie.
Armstrong escribe una carta a Michie, quien era uno de los pioneros en Inteligencia Artificial en el Reino Unido, explicándole su experiencia programando y le pregunta por la posibilidad de aplicar en algún trabajo como programador en su departamento.
La carta debe haber sido muy convincente, porque Michie lo llama: “estaré en Londres el próximo martes, ¿podemos encontrarnos? Tomaré un tren a Edimburgo, ¿puede venir a la estación?"1.
Armstrong fue a la estación, se encuentra con Michie quien responde “Hmmm! Bien, no podemos hacer la entrevista acá, así que, ¡busquemos un pub!”. Y en un Pub cerca de la estación de trenes tuvieron su entrevista de trabajo. A los pocos días le llegó una carta de Michie, “hay un trabajo como asistente de investigación, acá en Edimburgo, ¿por qué no postulas?"1.
En este punto de la historia hay algo interesante, Donald Michie fue amigo personal de Alan Turing y trabajaron juntos en Bletchey Park, durante la Segunda Guerra Mundial, así que Armstrong tuvo la rara oportunidad de usar un escritorio de Turing y estar rodeado de varios de sus papers originales. En 1975 Michie era el chairman del Turing Trust, un archivo de la obra de Turing y posteriormente fundó el Instituto Turing, un laboratorio de inteligencia artificial, en Glasgow.
Sin embargo, los fondos para el grupo de IA en Edimburgo, empezaron a disminuir, y Armstrong debe buscar nuevamente trabajo. Es así como encuentra trabajo como programador físico en la EISCAT, una organización internacional científica fundada en 1975, con sede en Suecia.
Eventualmente, Armstrong ingresa a la Swedish Space Corporation, como desarrollador del sistema operativo para el primer satélite sueco, el Viking.
Alrededor de 1984, se mueve al laboratorio de investigación de Ericsson.
Take a chance on me
Take a chance on me
If you need me, let me know, gonna be around
Al principio Armstrong se dedicó a crear un pequeño lenguaje basado en Prolog. La labor en el laboratorio era construir software que eventualmente los ingenieros de Ericsson pudieran usar. Junto con Robert Virding acompañaron a un grupo de empleados de Ericsson que querían un nuevo lenguaje para programar aplicaciones de telefonía. Era un intercambio de conocimiento, Virding y Armstrong les enseñarían sobre programación y a cambio recibirían conocimientos sobre telefonía.
El producto de esos meses de intercambio se tradujo en un proyecto de dos años, cuyo fruto sería el lenguaje de programación Erlang y la OTP (Open Telecom Platform).
Mientras Armstrong escribía el compilador en Prolog, Virding diseñaba y programaba las bibliotecas y framework. Cuando llegó el momento de escribir la máquina virtual para el lenguaje, Armstrong se enfrentó por primera vez al lenguaje C. Al revisar su trabajo, Mike Williams, otro colega del laboratorio, le comentó que era el peor C que había visto en su vida, así que decidió hacerse cargo personalmente de la máquina virtual. Armstrong quedó liberado para dedicarse a terminar el diseño del lenguaje y su compilador. De ese modo empezaron el proceso de bootstrap, en que el compilador pudo ser escrito totalmente en Erlang, liberándose del pasado en Prolog.1
El nombre Erlang hace referencia al matemático danés Agner Krarup Erlang, autor de la teoría de colas y de gran parte de la teoría original en redes de telefonía (como la fórmula del tráfico de Erlang). Erlang también funciona como el acrónimo de Ericsson Language, aunque la comunidad opensource que lo soporta actualmente trata de no vincularlo a Ericsson.
El mayor logro de Erlang es el sistema AXD301. En 1995 el sucesor del sistema de packet switching para redes telefónicas, llamado AXE-N había colapsado totalmente ante las nuevas demandas y fue reemplazado por la serie AXD, desarrollada totalmente en Erlang2.
El AXD301, con más de dos millones de lineas de código, es un sistema que logró un 99.9999999% de confiabilidad.
Así como lo leen, 99.9999999% (esos son nueve nueves), esto quiere decir que en este sistema se tiene 0,3 segundos de indisponibilidad en todo el año. Esta cifra fue medida en British Telecom durante un periodo de ocho meses. Lo que expresa esta cifra es el uptime del servicio en su totalidad, no de sus partes.
¿Cómo lograron esto? Gracias a dos características esenciales: no compartir estado y contar con un sofisticado modelo de recuperación de errores.
Erlang es un lenguaje funcional, que permite construir sistemas altamente distribuidos, y que incorpora el modelo de actores para implementar concurrencia y distribución. Cuenta con OTP, Open Telecom Platform, un completo framework, que incluye bibliotecas, módulos y estándares, que es la base de gran parte de los sistemas construidos con este lenguaje. Erlang es prácticamente inseparable de este framework.
The Winner take it all
I don’t want to talk
About the things we’ve gone through
I’ve played all my cards
And that’s what you’ve done too
Nothing more to say
No more ace to play
A pesar del éxito probado de Erlang, los ejecutivos de Ericsson toman una extraña decisión y en 1998 deciden imponer una restricción y la prohibición de usar Erlang para el desarrollo de productos internos, el argumento expuesto es que preferían que no se desarrollara en lenguajes propietarios. La prohibición hace que Armstrong y otros ingenieros dejen Ericsson. La implementación se libera como Open source a fines del mismo año.
Eventualmente, en 2003 la prohibición es levantada y Armstrong es recontratado por Ericsson3. Aunque Ericsson no ha establecido ninguna política oficial con respecto al lenguaje, es por esta razón que la comunidad open source del programa prefiere ignorar la referencia a Ericsson en el nombre del lenguaje.
Antes de volver a Ericsson, Armstrong documenta su trabajo en el desarrollo de Erlang en una tesis de doctorado que presenta al Instituto Real de Tecnología de Estocolmo.
Su tesis, titulada “Making reliable distributed systems in the presence of software errors”2 está disponible en internet http://erlang.org/download/armstrong\_thesis\_2003.pdf.
Así, a los cincuenta y tres años Joe Armstrong obtiene por fin su doctorado, no en física como aspiraba de joven, pero sí en tecnologías de información, donde hizo un gran aporte.
Este hecho es una gran inspiración, al menos para mi, quizás inconscientemente decidí emularlo al volver a la universidad a los cincuenta años.
Tal como nos muestra la vida de Armstrong, nada es definitivo en la vida, y no todo sigue el camino que esperamos, a veces la ruta al reconocimiento tiene extraños recovecos.
Dancing Queens
Looking out for a place to go
Where they play the right music
Getting in the swing
You come to look for a king
Anybody could be that guy
El mundo de la tecnología volvió a escuchar de Erlang en febrero de 2014, tras la adquisición de WhatsApp por parte de Facebook.Fundada en 2009, por Brian Acton y Jan Koum, la aplicación revolucionó el mundo de la mensajería instantánea.
WhatsApp se volvió en el epítome de la startup unicornio, era la reina del mundo de las aplicaciones de mensajería en diciembre de 2013. Con más de 400 millones de usuarios, era evidente que los grandes de la tecnología estaban detrás de la empresa. La venta por más de diecinueve mil millones de dólares a Facebook dejó a todos estupefactos. Una compañía con apenas 50 empleados adquiría una de las valoraciones más altas de la historia de la tecnología.
Al analizar la tecnología detrás de este producto, la prensa y muchos aficionados a la tecnología se enteraron de la existencia de Erlang. Para una aplicación como esta, un sistema de alta escalabilidad, concurrencia y distribución, las características de diseño de Erlang resultan más que adecuadas4.
Voulez Vous
And here we go again, we know the start, we know the end
Masters of the scene
Para mi, Joe Armstrong es una de esas personas cuya vida encuentro inspiradoras. Entre las cosas que más me identifican con él está lo que dice en la entrevista con Siebel en su libro Coders At Work1.
“Los programadores realmente buenos pasan mucho tiempo programando. Nunca he visto a un buen programador que no pase gran parte de su tiempo programando. Si yo no programo por dos o tres días, necesito hacerlo. Y te vuelves mejor y más rápido en ello. El efecto lateral de escribir todas esas cosas es que cuando tienes que resolver problemas ordinario, lo puedes hacer muy rápido."
“He aprendido nuevos lenguajes de programación, pero no con la meta de ser un mejor programador. Con la meta de ser un mejor diseñador de lenguajes, quizás."
“Me gusta descubrir como funcionan las cosas. Y una buena prueba de eso es implementarlas por ti mismo. Para mi, programar no se trata de tipear código en una máquina. Programar es entender.”
Codificación de Huffman en Erlang
Erlang permite escribir código muy conciso, y para este ejercicio, que es parte de mi serie sobre esos extraños lenguajes nuevos, la compresión de Huffman, apenas necesité de 70 líneas efectivas de código, lo que muestra la expresividad de este lenguaje.
Esta es la esencia del programa:
-module (huffman).
-compile({no_auto_import,[size/1]}).
-export ([main/0, main/1]).
-import(filename, [absname/1]).
-define(USAGE, "uso: huffman [c|d] archivo_entrada archivo_salida\n").
main() -> io:format(?USAGE).
main([Opt,Entrada,Salida]) when Opt =:= 'c' -> comprimir(Entrada, Salida);
main([Opt,Entrada,Salida]) when Opt =:= 'd' -> descomprimir(Entrada, Salida);
main([_]) -> io:format(?USAGE).
comprimir(Entrada, Salida) ->
{ok, Binary} = file:read_file(Entrada),
Bytes = binary_to_list(Binary),
{Dump, Tree} = encode(Bytes),
DTree = tree_as_bits(Tree),
PS = (8 - ((bit_size(DTree) + bit_size(Dump)) rem 8)) rem 8,
PDump = <<DTree:(bit_size(DTree))/bitstring, Dump:(bit_size(Dump))/bitstring, 0:PS>>,
ok = file:write_file(Salida, PDump).
descomprimir(Entrada, Salida) ->
{ok, Binary} = file:read_file(Entrada),
{Tree, Code} = read_tree(Binary),
Dump = decode(Code, Tree),
ok = file:write_file(Salida, Dump).
Al ser un lenguaje creado para resolver problemas de telecomunicaciones, el soporte para construir protocolos es superior a muchos lenguajes. En particular, la manipulación de datos binarios es uno de los atributos interesantes de Erlang y que aproveché fuertemente para resolver este problema.
En Erlang existe una estructura de datos que corresponde a una cadena de bits. De este modo, es posible generar el stream de bits necesario para la compresión de Huffman, veamos cómo.
Primero, cuando tenemos el árbol del código de huffman, debemos almacenarlo como una secuencia de bits, para construir esa secuencia usamos este código:
tree_as_bits({L,R}) ->
BL = tree_as_bits(L),
BR = tree_as_bits(R),
<<0:1, BL/bitstring, BR/bitstring>>;
tree_as_bits(Symbol) ->
<<1:1, Symbol>>.
Recordemos que nuestro árbol puede tener nodos internos (que tienen dos hijos) o tener hojas, que sólo contienen el símbolo.
Dado esto el patrón {L,R} representa a un nodo, en ese caso, L es la rama izquierda y R la rama derecha. Lo que hace esto es recursivamente crear la representación binaria para L y R dejándolas en BL y BR, respectivamente, luego devuelve el bitstring <<0:1, BL/bitstring, BR/bitstring>>, con esto decimos que se devuelve una secuencia de bits, donde el primer bit es 0, el :1 indica que es un string de 1 bit de ancho, seguido de los bistrings BL y BR.
En el segundo caso, Symbol es la hoja que contiene sólo el símbolo que queremos almacenar (un byte), entonces devolvemos <<1:1, Symbol>>, es decir un bit en 1, seguido de los 8 bits que representan al símbolo.
Lo inverso, también se resuelve recursivamente del siguiente modo:
read_tree(<<1:1, Rest/bitstring>>) -> read_leaf(Rest);
read_tree(<<0:1, Rest/bitstring>>) -> read_node(Rest).
read_leaf(<<Sym:8, Rest/bitstring>>) -> {{Sym,-1}, Rest}.
read_node(Bits) ->
{L, Rest1} = read_tree(Bits),
{R, Rest2} = read_tree(Rest1),
{{L,R}, Rest2}.
En este caso estamos leyendo una secuencia de bits, si encontramos un 1 entonces leemos una hoja (read_leaf) en el resto de los bits (Rest). Si encontramos un 0, leemos un nodo en el resto de los bits (Rest).
La función read_leaf lee el símbolo desde los primeros 8 bits del bitstring y devuelve el símbolo como un nodo con un valor de frecuencia -1 {Sym, -1} junto con el resto de bits. Recordemos que para descomprimir no nos interesa la frecuencia de los símbolos, pero es necesario que mantengamos esta forma para que nuestro código que decodifica reconozca cuando está leyendo el símbolo.
La función read_node es recursiva, lee primero el nodo izquierdo y luego el derecho y devuelve un nodo compuesto más el resto de los bits.
Un último aspecto, muy relevante, con el cual me topé fue lo siguiente. En el archivo comprimido guardamos el árbol como una secuencia de bits, y luego una secuencia de bits que representan la información comprimida.
Entonces, la función de decodificación debe leer esta secuencia de bits recorriéndola guiado por el árbol, es decir, si hay un 1 recorre el árbol derecho hasta llegar a una hoja, si hay un cero recorre el árbol izquierdo hasta llegar la hoja. Una vez que llegas a la hoja, el símbolo que contenga es el símbolo decodificado. Ahora bien, mi primera versión usaba bitstring para hacer esto, pero esto resultó ser extremadamente lento. Esto se debe a que los bitstring son una estructura de datos bastante compleja y la naturaleza recusiva del algoritmo requiere una estructura de datos más liviana con la cual trabajar.
Es por esto que la versión definitiva del decodificado quedá así:
% decode a binary using Tree
decode(Code, Tree) ->
L = [X || <<X:1>> <= Code],
decode(L, Tree, Tree, []).
decode([], _, _, Result) ->
lists:reverse(Result);
decode([1|Rest], {_, R={_,_}}, Tree, Result) ->
decode(Rest, R, Tree, Result);
decode([0|Rest], {L={_,_}, _}, Tree, Result) ->
decode(Rest, L, Tree, Result);
decode(L, {Sym, -1}, Tree, Result) ->
decode(L, Tree, Tree, [Sym|Result]).
La función decode/2 (que recibe los bits y el árbol, transforma el bitstring en una lista de valores 0 ó 1. Esta lista es la que se pasa a la función decode/4 (que recibe una lista de 0 y 1, el nodo a visitar, el árbol entero y una lista que contiene los símbolos decodificados.
El código completo se encuentra, como siempre, en mi repositorio Github, en esta dirección: https://github.com/lnds/9d9l/tree/master/desafio4/erlang
Terminemos este post entonces, con uno de los mayores éxitos de ABBA y quizás una de las mejores canciones del Pop de todos los tiempos, Dancing Queen:
Notas
Coders at work: Reflections on the Craft of Programming. Autor Peter Seibel. ↩︎
Tesis de Armstrong, de 2003, “Making reliable distributed systems in the presence of software errors”: http://erlang.org/download/armstrong_thesis_2003.pdf ↩︎
Inside Erlang, the Rare Programming Language behind WhatsApp’s success ↩︎