I program stuff.

Sunday, March 25, 2007

I was poking around at some programming languages again while thinking about concurency in programming and ran into a discussion on this very thing. Someone there mentioned Erlang as a good language to solve these sorts of problems. I'd never heard of it so I started checking it out. It does indeed have great concurrency support. I was going through their white paper and I found this other great feature that it has that has nothing to do with concurrency.


This program sorts a list using the Quicksort algorithm:
     sort([]) -> [];
     sort([Pivot|T]) ->
          sort([X||X <- T, X < Pivot]) ++
          [Pivot] ++
          sort([X||X <- T, X >= Pivot]).


from "Example 4 - Sort" of the whitepaper.

As it says in there ++ is the infix append operator and this example introduces what they call a list comprehension. Like it says in the whitepaper,


The notation [Expr || Qualifier1, Qualifier2, ...] introduces a list comprehension. Here Expression is an arbitrary expression, and each Qualifier is either a generator or a filter.

For example, the list comprehension

[X || X <- [1,2,a,3,4,b,5,6], integer(X), X > 3].

should be read as:

The list of X such that X is taken from the list [1,2,a,3,4,b,5,6] and X is an integer and X is greater than 3.

Here X <- [1,2,a,3,4,b,5,6] is a generator, and integer(X) and X > 3 are filters. This list comprehension evaluates to [4,5,6].


I was very impressed with this, at one time I was trying to come up with a syntax for this type of expression myself. At that point I'd never seen a language with a compact expression of this idea. I thought SQL where clauses are very close but the rest of the SQL statement is a bit to verbose for this type of case.

Then as I read the example program after understanding this I could clearly see the logic of the Quicksort program and for the first time I understood how the Quicksort algorithm works. I'm a little embarrassed to say but I've never fully understood how a Quicksort algorithm worked before reading the Erlang example. I very clearly remember reading my first introduction to this algorithm back in 1986, or something like that, in a Compute!'s Gazette (a magazine for Commodre computers). I never understood how that Basic implementation worked and from then on I've had some sort of block on my understanding how this algorithm worked. I've come across it may times in may different languages but all the implementations have been cryptic to my eyes. All I could clearly remember is the phrase "divide and conquer", which I think was mentioned in that first Computes!'s Gazette article, but never quite understanding how that helps you sort quickly. This phrase haunting my memory whenever I came across the Quicksort.

Well after about 10 minutes into reading Erlang's whitepaper with no exposure to Erlang before this and once I finished reading their "Example 4 - Sort" the program,


This program sorts a list using the Quicksort algorithm:
     sort([]) -> [];
     sort([Pivot|T]) ->
          sort([X||X <- T, X < Pivot]) ++
          [Pivot] ++
          sort([X||X <- T, X >= Pivot]).


simply blew me away. Suddenly all the pieces fell into place in my mind that had been starting to build in my mind since 1986 till now, 2007, and I suddenly for the first time in 20 years actually understood how Quicksort is implemented. It was here staring me in the face, plainly and succinctly written, which lead me directly to reasoning and logic behind it just like how a great equation compactly and cleanly describes the core of an idea. As a bonus I could see that my work on what they call a list comprehension was not only a good idea but is even a more powerful construction than I originally thought it was. It had helped me understand a difficult concept almost effortlessly.

I suspected before that something like a "list comprehension" is a very common abstraction in algorithms that really should be expressed in a language directly. Coding this sort of construction in C or similar languages is difficult and tiring, especially after you write and debug one for the hundredth time. But now I can see the raw power of using this kind of construction in practice. I think it was probably these details of the implementation of the Quicksort that was getting in my way of understanding the core idea behind the Quicksort itself for all these years. I can see that this language construction is a wonderful tool.

2 comments:

Raoul Duke said...

also, check out Concurrent Clean, or even Haskell, if you liked that.

Mike Nelson said...

Very cool. Clean looks like another cool language. I haven't heard of that one before. Thanks for the tip, Raoul.