Sunday, June 12, 2005

Haskell takes it up a notch

I think exotic programming languages are the best way to explore the core ideas of information science. Haskell is so god damn expressive, it's amazing. Here is the definition of the "increment" function:

inc = add 1

That's so fucking organic. How can that idea be encoded any more elegantly?
The trick with Haskell is that their language is designed firstly as a really clear system of notation, a higher level syntax for a system of rigorous mathematics developed in the study of algorithms and semantics. Haskell is a veneer over the lambda calculus and type theories, converting the greek letters from the theory into something that is easier to type. C is a veneer over the system's operating instructions, the mechanical arrangement of electrical impulses that results in the computation. C created a useful shorthand for the tasks that assembly code programmers found themselves doing often. Instead of writing branch statements and pushing to the stack, they wrote for loops. But their code was still very much linear, a cleaned up revision of the very linear programming model of machine instructions. And that indicates the difference between Haskell and C. Haskell is built to express meaning concisely and naturally. C is built to tell the computer what to do. But more and more of that "telling the computer what to do" is becoming redundant and unnecessary. The "higher level" languages need to be divided into two categories. "Mid level" languages are those that rely on sequencing imperatives, and are really just veneers over common patterns in assembly programming. True high level languages are expressive, and completely abstract away the technical details of how the computation occurs. The creator is left to deal just with the idea, and assume his computer will support him.

Look at this definition for quicksort:

quicksort [ ] = [ ]
quicksort (first:rest) = quicksort elsLessThanFirst ++ [first] ++ quicksort elsGreaterThanOrEqFirst
                elsLessThanFirst = [ y | y <- rest, y < first]
                elsGreaterThanOrEqFirst = [ y | y <- rest, y >= first]

That says that the quicksort of an empty list is an empty list. The quicksort of the first and rest of the list is the quicksort of every element in the rest of the list that is less than the first concatenated with the list of just the first concatenated with the quicksort of elements in the rest of the list that are greater than or equal to the first.

I think the code expresses that much more clearly. In fact, Haskell programs can be compiled as documentation in the LaTeX format. The programs serve as executable documentation of programs. Hmm... deathly elegant idea eh? Just look at the quicksort in C:

qsort( a, lo, hi ) int a[], hi, lo;
int h, l, p, t;

if (lo < hi) {
l = lo;
h = hi;
p = a[hi];

do {
while ((l < h) && (a[l] <= p))
l = l+1;
while ((h > l) && (a[h] >= p))
h = h-1;
if (l < h) {
t = a[l];
a[l] = a[h];
a[h] = t;
} while (l < h);

t = a[l];
a[l] = a[hi];
a[hi] = t;

qsort( a, lo, l-1 );
qsort( a, l+1, hi );

Tell me which one you'd rather be using on a hard problem. And even adding layers of shit, as in Java, you still don't avoid the barrier to abstraction enforced by that view of programming.