In the court of the Crimson King

King Crimson was formed in London on November 30, 1968, and held its first rehearsal on January 14, 1969, fifty years ago now. The band was the heir to Giles, Giles and Fripp, a group that played pop with an eccentric style and high musical complexity. Originally they were a trio made up of the brothers Michael Giles on drums and Peter Giles on bass, together with guitarist Robert Fripp. In time they wanted to expand their sound and brought in Ian McDonald on keyboards, who in turn brought in Peter Sinfield as lyricist.

Fripp wanted to leave pop behind and pushed for Peter Giles to quit the band, and he invited Greg Lake, an old friend and former schoolmate. Since both played guitar (they had studied with the same teacher), and after Giles’s departure, they decided Lake would play bass and take over the vocals.

The band’s name is a reference to Beelzebub, prince of demons

. But also to the fact that a “crimson king” historically refers to a king whose reign is marked by excessive bloodshed. Remember that the band’s first album came out right in the middle of the Vietnam War.

The main composer was McDonald, with contributions from Fripp, and the lyrics were Sinfield’s. Fripp once said that adding lyrics to King Crimson’s music was “a functional impossibility”. They worked intensely, searching for new sounds and complicated harmonies, until in October 1969 they released “In The Court of the Crimson King”.

The album was a success, and the band went on tour, mainly across the United States. But that trip opened cracks in the band. Michael Giles and Ian McDonald quit the group in the middle of the tour. Back home, and while they were preparing their second album, Greg Lake decided to leave as well, to form the famous progressive rock supertrio “Emerson, Lake & Palmer”.

Fripp invited Gordon Haskell, another former schoolmate, to join the band, replacing Lake. By then Sinfield was in charge of the synthesizers.

It wasn’t easy for Haskell to take over Lake’s vocal parts, and he even asked to lower the key of some songs so he could sing them properly. The proposal was vigorously rejected by Fripp and the two grew apart. Later Haskell would say *“The King Crimson weapon is musical fascism, made by fascists, designed by fascists to dehumanize, to strip mankind of his dignity and soul.” *

.

Eventually, and after recording “Islands”, the band’s fourth album, Fripp asked Sinfield to leave the group. With that, Robert Fripp became the brain, heart and soul of King Crimson.

Despite always having the backing of top-quality musicians, Fripp systematically refused to include their compositions, with the idea of keeping control over quality and making sure King Crimson played “the right kind of music”.

Haskell

“Haskell is a compiler that transforms insecure narcissism into intellectual superiority” - @progmofo on Twitter

Of the programming languages I know**, I can say that Haskell is one of the hardest to master. Writing a program in Haskell is probably like rehearsing in a session with Robert Fripp. But it is worth it, just like listening to King Crimson’s music, I assure you.

But if you don’t challenge your tastes, your conventions, and everything you have learned, how are you going to learn? A colleague once said, “functional programming is hard, but like everything worthwhile in life, it is hard”.

In 1987, at the conference on Functional Programming Languages and Computer Architecture, a committee was formed to define an open standard to consolidate all the functional languages that existed at the time (dozens of them).

The name was chosen to honor Haskell Curry, an American mathematician and logician who worked on combinatory logic, which serves as the foundation for a style of functional programming.

The first version of Haskell was published in 1990 and the work continued until the release of Haskell 98, the first standard. With that definition a team at the University of Glasgow worked on the implementation of GHC (“The Glorious Glasgow Haskell Compilation System”). The work was started by Kevin Hammond, and it is currently led by Simon Peyton Jones and Simon Marlow.

Marlow has worked at Facebook since 2013, and there he has used Haskell to implement and reimplement a series of tools in that language. A notable example is the Sigma rule engine, which applies security policies to every interaction that takes place when someone posts something on the social network

.

Heroes

Fripp disbanded King Crimson in 1974 after releasing the album Red. After that he worked on various projects, as a session musician and also as a solo artist. He collaborated with Brian Eno, David Bowie, David Byrne and Peter Gabriel among others, who admired Fripp’s style on guitar.

Perhaps the best known thing from this period, for the general public, is his part on David Bowie’s 1977 album Heroes, where his guitar stands out on the song that gives the record its name (my favorite in all of Bowie’s work). Heroes is a song representative of what we now call art rock. It is inspired by the story of a pair of lovers separated by the Berlin Wall.

In 1981 Fripp decided to re-form King Crimson, calling back Bill Bruford, the former Yes drummer, with whom he had worked on the album Red. Bruford was joined by the great bassist Tony Levin and by Adrian Belew (whom Fripp met when they were playing for Peter Gabriel). Belew was a singer and guitarist who had worked with Bowie, Talking Heads and Frank Zappa (with whom he started his career).

Originally the band formed by Fripp, Bruford, Levin and Belew was called Discipline, but the members felt it was more fitting to associate it with King Crimson. For Fripp, the name King Crimson has been associated with a “way of doing things”, more than with a particular kind of group and musicians.

Discipline

The first album by this new King Crimson lineup was called Discipline. For four years they worked together and presented their work in three albums: Discipline, Beat, Three of a Perfect Pair. This is perhaps one of the King Crimson lineups most valued by its fans. This time Fripp opened up to his bandmates’ contributions and they worked together on the writing and composition. The lyrics were written mainly by Belew.

No side effects

If there is one thing that characterizes Haskell as a programming language, it is its strict discipline with respect to types, and its adherence to the functional principles of immutability and the absence of side effects.

No useful program can be built without side effects. For example, printing a simple message on the screen means affecting the environment. To comply with its strict discipline, Haskell resorts to a concept that makes it possible to isolate these side effects, a concept that comes from Category Theory and is called a Monad.

Let’s look at the classic example:

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

In this case, by declaring the function main we state that its result is an IO Monad, that is, a data type that isolates a side effect. That is why the compiler lets us use the impure function putStrLen

.

It is this strict discipline that intimidates many programmers, in the same way that some musicians felt intimidated by Fripp’s perfectionist leadership.

Huffman coding in Haskell

Despite that strict discipline, in Haskell we can write very concise programs. Solving challenge 4 took just 91 lines of code.

We are going to analyze the compression process in this article; the complete source code is in the repository on GitHub.

The function compress is the one that receives as parameters the name of the file we want to compress (input) and leaves the result in a file whose name comes in the second parameter:

     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)

This function has side effects, and that follows from the fact that it uses the do statement, which in Haskell always indicates that we will produce a side effect.

The first thing is to get all the bytes of the file, which is achieved with:

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

In this case we use LB, which is declared at the beginning of the program like this:

     import qualified Data.ByteString.Lazy.Char8 as LB

LB has everything needed to read and write files of bytes.

LB.unpack unpacks a string into a sequence of bytes, LB.readFile reads the entire contents of a file as a string.

The <$> operator is identical to calling the function fmap, and in this case what it does is map the string to a list of bytes.

Next we must build the tree, which is done with:

    let tree = buildTree $ calcFreq src

You will notice that on the first line, to assign to src, I used the <- operator, but to assign to tree we use let tree =. The reason is that to pull out the values of an IO Monad you use <-, but with pure functions you use let, which is the standard in Haskell. As for the $ sign, it is there to avoid ambiguities and is explained in note

.

The trick is in the function calcFreq, which I present below:

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

The dot operator (.) denotes function composition.

In Haskell (f . g) x is equivalent to writing f (g x).

So calcFreq is a function that returns a new function composed of the application of several functions.

This must be read from right to left to be understood.

The first function is sort, which sorts the input.

The second function is group, which groups the sorted elements.

Suppose our file contains the phrase:

 cat's foot iron claw

Then sort produces:

  aaccfilnooosttw'

Then group produces:

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

(length &&& head) is what is technically known as an Arrow; the &&& operator applies the two functions it receives as parameters and generates a pair with the values obtained, so

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

The function length computes the length of a list, and head gets its first element.

By doing <$>, we map each element with the Arrow (length &&& head).

That is, by doing ((length &&& head) <$>) over (aa)(cc)(f)(I)(n)(ooo)(s)(tt)(w) we get:

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

The function buildTree is the following:

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

To understand what this function does we must introduce the data type HTree, which is declared like this:

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

So let’s explain what buildTree does.

What map (second Leaf) does is turn every second element of the input pairs into leaves:

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

Ending up like this:

 ((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))

The function S.fromList simply converts this list into a set, which makes it possible to operate with the function htree.

The function htree is defined like this:

     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

Here we have implemented Huffman’s algorithm. First you have to understand what the expressions that come after the where statement do.

Remember that Haskell does pattern matching, so we can see that:

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

Extracts the node with the minimum value from the set. In our example this would work out like this:

     ((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))

The next expression is:

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

Which in our example would result in:

       ((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))

The third expression is:

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

Which, in the example we are looking at, would result in:

           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))

Given these expressions, we can understand the body of the function htree:

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

This is a recursive function. What it tells us is that if the set it receives is empty then it takes the element t1 (which corresponds to the leaf with the minimum value). Otherwise it recursively applies htree to the rest of the set.

By now, if you have made it this far, you must hate me as much as Gordon Haskell hated Robert Fripp when he left King Crimson, but I ask you for a little more patience.

What we do with this strange function is simply a loop, which builds the tree from the list of frequencies, so that the minimum value always ends up at the root. To understand it, I suggest you expand the example all the way to the end.

With this we have built our Huffman tree.

Let’s go back to the function compress. The next expression is:

    let table = M.fromList $ serializeTree tree

I am not going to explain serializeTree; suffice it to say that it converts the tree into a table of pairs in which the first value is the character to compress, and the second element of the pair is its representation as a list of zeros and ones.

That way we get the conversion table.

To be able to apply it we will use a helper function, which is the one defined in the following expression:

     let lookup chr = fromJust $ M.lookup chr table

The function lookup receives a character and looks it up in the table. The function fromJust is needed because M.lookup returns a structure of type Just. This is a standard construct in Haskell for knowing whether or not an element is in a dictionary.

With this we can generate the compressed output, expressed as a string of bits:

     let binaryOut = concat $ map lookup src

What this does is map each character to a list of bits, then join all the lists into a single one, called binaryOut.

We must also map the tree to a sequence of bits, and for that we call the function binarizeTree

     let treeOut = binarizeTree tree

With this we can assemble our output, which is one big list of bits:

     let outputStream = padRight8 (treeOut ++ binaryOut)

It could happen that our output is something like this

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

With 10 values, but we need the size of the output to be a multiple of 8, since bytes are made of eight. What the function padRigh8 does is add zeros on the right until the length is a multiple of 8:

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

This is necessary because when we finally write the result to a file we do:

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

The function chunksOf groups the output into batches of 8 bits.

The rest of the program is on 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

The latest incarnation of King Crimson has the peculiarity of including three drummers. Among them is Gavin Harrison, the former drummer of Porcupine Tree (whom we talked about before, when we solved this problem in Clojure). Robert Fripp collaborated with Porcupine Tree on the album Fear of a Blank Planet.

King Crimson’s work these days is best appreciated at their live concerts, which their admirers await anxiously. Whatever Gordon Haskell may have said about the band, the truth is that it has become a cult act, revered and admired by great musicians, and knowing it is almost mandatory for anyone who appreciates progressive rock.

But it is not easy music to follow, and that is exactly why I decided to pair Haskell with King Crimson. Because it is not easy to follow and to learn, but if you want to improve and deepen your knowledge of functional programming, writing some code in this language is almost mandatory.

End of challenge 4

With this article we close challenge four, of nine, in this series. To wrap up I am going to share the ranking for this challenge.

By execution time

(from fastest to slowest)

By lines of code

With this we move ahead on a project started three years ago now (https://lnds.net/en/blog/lnds/2016/01/09/those-strange-new-languages/). I hope this year to make up for lost time and finish these 9 challenges once and for all. I’ll be waiting for you.

NOTES:

According to Fripp the word Beelzebub comes from the Arabic B’il Sabab, which means “the man with a purpose”

Taken from https://news.avclub.com/how-king-crimson-s-musical-fascism-led-to-its-early-d-1798263566

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

An impure function is one that has side effects.