En la Corte del Rey Carmesí

King Crimson se formó en Londres, el 30 de noviembre de 1968, y tuvo su primer ensayo el 14 de enero de 1969, hace ya cincuenta años. La banda era heredera de Giles, Giles and Fripp, un grupo que tocaba pop con un estilo excéntrico y de alta complejidad musical. Originalmente eran un trio formado por los hermanos Michael Giles en batería y Peter Giles en bajo, juntas al guitarrista Robert Fripp. Con el tiempo quisieron expandir su sonido e incorporaron en el teclado a Ian McDonald, quien incorporó como letrista a Peter Sinfield.

Fripp quería abandonar el pop y presionó para que Peter Giles abandonara la banda, e invitó a Greg Lake, un viejo amigo, y ex compañero de escuela. Como ambos tocaban guitarra (habían estudiado con el mismo profesor) y tras la partida de Giles, decidieron que Lake tocara el bajo y se hiciera cargo de la voz.

El nombre de la banda es una referencia a Belzebú, príncipe de los demonios[1]. Pero también al hecho que un “rey carmesí” históricamente refiere a un rey cuyo gobierno se caracteriza por el excesivo derramamiento de sangre. Hay que recordar que el primer álbum de la banda debuta en pleno periodo de la guerra de Vietnam.

El principal compositor era McDonald con aportes de Fripp, y las letras de Sinfield. Fripp una vez dijo que incorporar letras a la música de King Crimson era “una imposibilidad funcional”. Trabajaron intensamente, buscando nuevos sonidos y complicadas armonías, hasta que en octubre de 1968 estrenaron “In The Court of the Crimson King”.

El álbum fue un éxito, y la banda partió en tour, principalmente por Estados Unidos. Pero este viaje provocó fisuras en la banda. Michael Giles junto con Ian McDonald abandonaron el grupo en la mitad del tour. De vuelta, y mientras preparaban su segundo álbum, Greg Lake decide partir también para conformar el famoso super trio de rock progresivo “Emerson, Lake & Palmer”.

Fripp invita a Gordon Haskell, otro ex compañero de escuela, para que se incorpore a la banda, reemplazando a Lake. A esas alturas Sinfield estaba a cargo de los sintetizadores.

No fue fácil para Haskell hacerse cargo de las partes vocales de Lake, e incluso pidió bajar el tono de algunas canciones con el fin de poder vocalizarlas adecuadamente. La propuesta fue enérgicamente rechazada por Fripp y ambos se distanciaron. Después Haskell diría *“el arma de King Crimson es el fascismo musical, seco por fascistas, diseñado por fascistas para deshumanizar, para despojar a la humanidad de su dignidad y alma” *[2].

Eventualmente, y después de grabar “Islands”, el cuarto álbum de la banda, Fripp le pide a Sinfield que abandone el grupo. Con esto Robert Fripp se convierte en el cerebro, corazón y alma de King Crimson. 

A pesar de contar siempre con el apoyo de músicos de gran calidad, Fripp se negó sistemáticamente a incorporar sus composiciones, con la idea de mantener el control de la calidad y asegurar que King Crimson ejecutara “el tipo correcto de música”.

Haskell

“Haskell es un compilador que transforma el narcisismo inseguro en superioridad intelectual” - @progmofo en Twitter

De los lenguajes de programación que conozco**, puedo decir que Haskell es uno de los más difíciles de dominar. Probablemente escribir un programa en Haskell es como estar ensayando en una sesión con Robert Fripp. Pero vale la pena, lo mismo que escuchar la música de King Crimson, se los aseguro.

Pero, si no desafías tus gustos, tus convenciones, y todo lo que has aprendido, ¿cómo vas a aprender?. Un colega dijo una vez, “la programación funcional es difícil, pero como todo lo que vale la pena en la vida, es difícil”.

En 1987, en la conferencia de Lenguajes de Programación Funcional y Arquitectura de Computadores, se formó un comité para definir un estándar abierto para consolidar todos los lenguajes funcionales que existían en ese periodo (docenas).

El nombre fue elegido para homenajear a Haskell Curry, un matemático y lógico norteamericano, que trabajó en lógica combinatoria, que sirve de fundamento para un estilo de programación funcional.

La primera versión de Haskell se publicó en 1990 y el trabajo continuó hasta la liberación de Haskell 98, el primer estándar. Con esta definición un equipo en la Universidad de Glasgow trabajó en la implementación de GHC (“El Glorioso Sistema de Compilación para Haskell de Glasgow”). El trabajo fue iniciado por Kevin Hammond, y actualmente es liderado por Simon Peyton Jones y Simon Marlow.

Marlow desde 2013 trabaja en Facebook, y allí ha usado Haskell para implementar y re implementar una serie de herramientas en ese lenguaje. Un ejemplo notable es la máquina de reglas Sigma, que implementa políticas de seguridad a cada interacción que ocurre cuando alguien postea algo en la red social [3].

Héroes

Fripp desbandó a King Crimson en 1974 después de liberar el álbum Red. Después de esto trabajo en diversos proyectos, como músico de sesión y también solista. Colaboró con Brian Eno, David Bowie, David Byrne y Peter Gabriel entre otros, quienes admiraban el estilo de Fripp en la guitarra.

Quizás, de este tiempo, lo más conocido por el público masivo es su participación en el álbun Héroes de David Bowie, de 1977, en donde destaca su guitarra en la canción que le da nombre al trabajo (mi favorita de toda la obra de Bowie). Héroes es una canción representativa de lo que hoy llamamos ara-rock. Está inspirada en la historia de una pareja de amantes separados por el Muro de Berlin.

En 1981 Fripp decidió reformar a King Crimson, llamando de vuelta a Bill Bruford, ex baterista de Yes, y con quien trabajó en el álbum Red. A Bruford se unieron el gran bajista Tony Levin y Adrian Belew (a quien Fripp conoció cuando tocaban para Peter Gabriel). Belew era un cantante y guitarrista que había trabajado con Bowe, Talking Heads y Frank Zappa (con quien empezó su carrera).

Originalmente la banda formada por Fripp, Bruford, Levin y Belew se llamó Discipline, pero los miembros consideraban que era más adecuado asociarla a King Crimson. Para Fripp, el nombre King Crimson ha estado asociado a una “forma de hacer las cosas”, más que a un tipo particular de grupo y músicos.

Disciplina

El primer álbum de esta nueva formación de King Crimson se llamó Discipline. Durante cuatro años trabajaron juntos y expusieron su trabajo en tres álbumes: Discipline, Beat, Thre of a Perfect Pair. Esta quizás es una las formaciones de King Crimson más valoradas por sus fans. Esta vez Fripp se abrió a los aportes de sus compañeros y trabajaron juntos en la escritura y composición. Las letras fueron escritas principalmente por Belew.

Sin Efectos Laterales

Si hay algo que caracteriza a Haskell como lenguaje de programación es su estricta disciplina co respecto a los tipos, y la adherencia a los principios funcionales de inmutabilidad y la falta de efectos laterales.

Ningún programa útil se puede construir sin efectos laterales. Por ejemplo, imprimir en pantalla un simple mensaje implica afectar al entorno. Para cumplir con la estricta disciplina Haskell recurre a un concepto que permite aislar estos efectos laterales, un concepto que viene de la Teoría de Categorías que se llama Monada (Monad).

Veamos el clásico ejemplo:

     Module Main (main) where
     main:: IO()
     main = putStrLen “Hola Mundo”

En este caso al declarar la función main indicamos que su resultado es una IO Monad, es decir, un tipo de datos que aisla un efecto lateral. Es por esto que el compilador nos permite usar la función impura putStrLen[4].

Es esta estricta disciplina la que intimida a muchos programadores, del mismo modo que algunos músicos se sentían intimidados por el liderazgo perfeccionista de Fripp.

Codificación de Huffman en Haskell

A pesar de esa estricta disciplina, en Haskell podemos escribir programas muy concisos. Para resolver el desafío 4 bastaron 91 lineas de código.

Vamos a analizar el proceso de compresión en este artículo, el código fuente completo está en el repositorio en GitHub.

La función compress es la que recibe como parámetros el nombre del archivo que queremos comprimir (input) y deja el resultado en un archivo cuyo nombre viene en el segundo parámetro:

     compress input output = do
       src <- LB.unpack <$> LB.readFile input
       let tree = buildTree $ calcFreq src
       let table = M.fromList $ serializeTree tree
       let lookup chr = fromJust $ M.lookup chr table
       let binaryOut = concat $ map lookup src
       let treeOut = binarizeTree tree
       let outputStream = padRight8 (treeOut ++ binaryOut)
       LB.writeFile output $ LB.pack $ map fromBits (chunksOf 8 outputStream)

Esta función tiene efectos laterales, y eso se desprende del hecho que usa la sentencia do, que siempre en Haskell indica que generaremos un efecto lateral.

Lo primero es obtener todos los bytes del archivo, esto se logra con:

     src <- LB.unpack <$> LB.readFile input

En este caso usamos LB que se declara al principio del programa así:

     import qualified Data.ByteString.Lazy.Char8 as LB

LB tiene todo lo necesario para leer y escribir en archivos de bytes.

LB.unpack desempaca un storing en una secuencia de bytes, LB.readFile lee todo el contenido de un archivo como un string. 

El operador <$> es idéntico a llamar a la función fmap, y en este caso lo que hace es crear un mapeo del string a una lista de bytes.

Luego debemos construir el árbol, esto se hace con:

    let tree = buildTree $ calcFreq src

Notarán que en la primera linea para asignar a src usé el operador <-, pero para asignar a tree usamos let tree =, la razón es que para entrar los valores de una Monad IO se usa <-, pero con funciones puras se usa let, que es lo estándar en Haskell. Con respecto al signo $, es para evitar ambigüedades y está explicado en la nota [4].

La gracia está en la función calcFreq, la que les presento a continuación:

     calcFreq = ((length &&& head) <$>) . group . sort

El operador punto (.) denota la composición de funciones.

En Haskell (f . g) x es equivalente a escribir f (g x).

Entonces calcFreq es una función que devuelve una nueva función compuesta por la aplicación de varias funciones.

Esto debe leerse de derecha a izquierda para entenderse.

La primera función es sort, la que ordena la entrada.

La segunda función es group, que agrupa los elementos ordenados.

Supongamos que nuestro archivo contiene la frase:

 cat's foot iron claw

Entonces sort produce:

  aaccfilnooosttw'

Luego group produce:

  (aa)(cc)(f)(I)(n)(ooo)(s)(tt)(w)

(length &&& head) es lo que se conoce técnicamente como un Arrow, el operador &&& aplica las dos funciones que recibe como parámetros y genera una dupla con los valores obtenidos, entonces

    (length &&& head) (ooo) => (3, o)

La función length calcula el largo de una lista, y head obtiene el primer elemento de esta.

Al hacer <$>, mapeamos cada elemento con el Arrow (length &&& head).

Es decir, al hacer ((length &&& head) <$>) sobre (aa)(cc)(f)(I)(n)(ooo)(s)(tt)(w) obtenemos:

  ((2, a), (2,c),(1,f),(1,l),(1,n),(3,o),(1,s),(2,t),(1,w))

La función buildTree es la siguiente:

     buildTree = htree . S.fromList . map (second Leaf)

Para entender lo que hace esta función debemos introducir el tipo de datos HTree, que se declara así:

     data HTree a = Leaf a | Branch (HTree a) (HTree a)

Explicamos que hace buildTree entonces.

El map (second Leaf) lo que hace es que cada segundo elemento de las duplas de entradas se convierten en hojas:

 ((2, a), (2,c),(1,f),(1,l),(1,n),(3,o),(1,s),(2,t),(1,w))

Quedando así:

 ((2, Leaf a), (2, Leaf c),(1, Leaf f),(1, Leaf l),(1, Leaf n),(3, Leaf o),(1,Leaf s),(2, Leaf t),(1, Leaf w))

La función S.fromList simplemente convierte esta lista en un conjunto, lo que permite operar con la función htree.

La función htree se define así:

     htree ts
       | S.null ts_1 = t1
       | otherwise = htree ts_3
       where
        ((w1, t1), ts_1) = S.deleteFindMin ts
        ((w2, t2), ts2) = S.deleteFindMin ts_1
        ts3 = S.insert (w1 + w2, Branch t1 t2) ts_2

Acá hemos implementado el algoritmo de Huffman. Primero hay que entender lo que hacen las expresiones que vienen después de la sentencia where.

Recordemos que Haskell hace pattern matching, por lo tanto podemos ver que:

     ((w1, t1), ts_1) = S.deleteFindMin ts

Extrae el nodo con el mínimo valor del conjunto. En nuestro ejemplo esto resultaría así:

     ((w1, t1), ts_1) = S.deleteFindMin((2, Leaf a), (2, Leaf c),(1, Leaf f),(1, Leaf l),(1, Leaf n),(3, Leaf o),(1,Leaf s),(2, Leaf t),(1, Leaf w))
     =>
     ((w1, t1), ts_1) = ((1, Leaf f), (2, Leaf a), (2, Leaf c), (1, Leaf l),(1, Leaf n),(3, Leaf o),(1,Leaf s),(2, Leaf t),(1, Leaf w))
     =>
     (w1=1, t1=Leaf f)
     ts_1 = ((2, Leaf a), (2, Leaf c), (1, Leaf l),(1, Leaf n),(3, Leaf o),(1,Leaf s),(2, Leaf t),(1, Leaf w))

La siguiente expressión es:

      ((w2, t2), ts_2) = S.deleteFindMin ts_1

Que en nuestro ejemplo resultaría en:

       ((w2, t2), ts_2) = S.deleteFindMin    ((2, Leaf a), (2, Leaf c), (1, Leaf l),(1, Leaf n),(3, Leaf o),(1,Leaf s),(2, Leaf t),(1, Leaf w))
     =>
     ((w2, t2), ts_2) = ((1, Leaf l),  ((2, Leaf a), (2, Leaf c), (1, Leaf n),(3, Leaf o),(1,Leaf s),(2, Leaf t),(1, Leaf w)))
     => (w2 = 1, t2 = Leaf l)
     ts_2 =  ((2, Leaf a), (2, Leaf c), (1, Leaf n),(3, Leaf o),(1,Leaf s),(2, Leaf t),(1, Leaf w))

La tercera expresión es:

     ts_3 = S.insert (w1 + w2, Branch t1 t2) ts_2

Lo que, en el ejemplo que estamos viendo resultaría en:

           ts_3 = S.insert (1+ 1, Branch (Leaf f) (Leaf l))   ((2, Leaf a), (2, Leaf c), (1, Leaf n),(3, Leaf o),(1,Leaf s),(2, Leaf t),(1, Leaf w))
     => ts_3 = ((2, Branch (Leaf f) (Leaf l)),     (2, Leaf a), (2, Leaf c), (1, Leaf n),(3, Leaf o),(1,Leaf s),(2, Leaf t),(1, Leaf w))

Dadas estas expresiones, podemos entender el cuerpo de la función htree:

     htree ts
     | S.null ts_1 = t1
     | otherwise = htree ts_3 

Esta es una función recursiva. Lo que nos dice que si el conjunto que recibe es vacío entonces toma el elemento t1 (que corresponde a la hoja con el valor mínimo). De lo contrario aplica recursivamente htree al resto del conjunto.

A estas alturas, si es que han llegado hasta acá, me deben estar odiando tanto como Gordon Haskell odiaba a Robert Fripp al salir de King Crimson, pero les pido un poco más de calma.

Lo que hacemos con esta extraña función es simplemente un loop, que va construyendo el árbol desde la lista de frecuencias, de modo que el valor mínimo quede siempre en la raíz. Les sugiero que para entenderlo expandan el ejemplo hasta llegar al final.

Con esto hemos armado nuestro árbol de Huffman.

Volvamos a la función compress, la siguiente expresión es:

    let table = M.fromList $ serializeTree tree

No voy a explicar serializeTree, sólo baste decir que convierte el árbol en una tabla de duplas en que el primer valor es el carácter a comprimir, y el segundo elemento de la dupla es su representación como una lista de ceros y unos.

De ese modo obtenemos la tabla de conversión.

Para poder aplicarla usaremos una función auxiliar que es la que se define en la siguiente expresión:

     let lookup chr = fromJust $ M.lookup chr table

La función lookup recibe un carácter y lo busca en la tabla. La función fromJust es necesaria porque M.lookup retorna una estructura de tipo Just. Este es una construcción estándar para saber si un elemento está o no en un diccionario en Haskell.

Con esto podemos generar la salida comprimida, expresada como una cadena de bits:

     let binaryOut = concat $ map lookup src

Lo que hace esto es mapear cada carácter en una lista de bits, luego junta todas las listas en una sola, que se llama binaryOut.

Debemos capear el árbol también en una secuencia de bits, y para eso llamamos a la función binarizeTree

     let treeOut = binarizeTree tree

Con esto podemos armar nuestra salida, que es una gran lista de bits:

     let outputStream = padRight8 (treeOut ++ binaryOut)

Podría ocurrir que nuestra salida sea algo así

 [1,0,1,1,0,0,0,1,0,1]

Con 10 valores, pero necesitamos que el tamaño de la salida sea un múltiplo de 8, pues los bytes son de ocho. Lo que hace la función padRigh8 es agregar ceros a la derecha hasta alcanzar un largo múltiplo de 8:

     [1,0,1,1,0,0,0,1,0,1,0,0,0,0,0,0]

Esto es necesario porque cuando escribimos finalmente en resultado a un archivo hacemos:

     LB.writeFile output $ LB.pack $ map fromBits (chunksOf 8 outputStream)

La función chunksOf agrupa la salida en lotes de 8 bits.

El resto del programa está en GitHub: [https://github.com/lnds/9d9l/blob/master/desafio4/haskell/src/Main.hs]{auto-link=“true” href=“https://github.com/lnds/9d9l/blob/master/desafio4/haskell/src/Main.hs”}

Radical Action to Unseat the Hold of Monkey Mind

La última encarnación de King Crimson tiene la particularidad de incluir tres baterías. Entre los cuales se incluye a Gavin Harrison, el ex baterista de Porcupine Tree (de quienes hablamos antes cuando resolvimos este problema en Clojure). Robert Fripp colaboró con Porcupine Tree en el álbum Fear of a Blank Planet.

El trabajo de King Crimson hoy en día se aprecia en sus conciertos en vivo, que son esperados con ansiedad por sus admiradores. A pesar de lo que pudo decir Gordon Haskell de la banda, lo cierto es que esta se ha convertido en una agrupación de culto, venerada y admirada por grandes músicos, y es casi obligatorio conocerla por cualquiera que aprecie el rock progresivo.

Pero no es música fácil de seguir, es por esto mismo que he decidido asociar Haskell con King Crimson. Porque no es fácil seguir y aprender, pero si quieres mejorar y profundizar tus conocimientos de programación funciona, es casi obligatorio escribir algo de código en este lenguaje.

Fin al desafío 4

Con este artículo cerramos el desafío cuatro, de nueve, en esta serie. Para finalizar voy a compartir el ranking de este desafío.

Por tiempo de ejecución

(del más rápido al más lento)

#	lenguaje	Tiempo Compresión	Tiempo Descompresión	Total
1	Rust	0.035s	0.050s	0.085s
2	Go	0.089s	0.141s	0.230s
3	Kotlin2	0.200s	0.212s	0.412s
4	Kotlin	0.199s	0.224s	0.423s
5	Scala	0.493s	0.463s	0.956s
6	Scala2	0.529s	0.468s	0.997s
7	Swift	0.723s	1.011s	1.734s
8	Haskell	2.384s	0.809s	3.193s
9	Erlang	2.069s	2.156s	4.225s
10	Clojure	6.973s	4.960s	11.933s
11	F#	3.942s	8.938s	12.880s

Por lineas de código

#	Lenguaje	Lineas
1	Erlang	69
2	Haskell	91
3	Clojure	152
4	F#	197
5	Kotlin	267
6	Scala	280
7	Swift	334
8	Rust	336
9	Go	338

Con esto avanzamos en un proyecto iniciado hace ya tres años (https://www.lnds.net/blog/lnds/2016/1/9/esos-raros-lenguajes-nuevos). Espero este año recuperar el tiempo perdido y terminar de una vez estos 9 desafíos. Los espero.

NOTAS:

[1] Según Fripp la palabra Belzebú viene del árabe B’il Sabab, que quiere decir “el hombre con un propósito”

[2] Tomado de https://news.avclub.com/how-king-crimson-s-musical-fascism-led-to-its-early-d-1798263566

[3] Fighting Spam with Haskell https://code.fb.com/security/fighting-spam-with-haskell/

[4] Una función impura es aquella que tiene efectos laterales.