Wednesday, June 30, 2010

Haskell Libraries: Procedural or Combinatorial

Functional programming is a style of programming that emphasizes the use of functions, especially pure functions. That's boring. It's also not terribly obvious that functional programming, in that sense, is an improvement; going from this:

    int accum = 0, number;
    while (getnumber(&number) != EOF)
        accum += number;
    printf("%d\n", accum);
to this:

    get_accumulated_number(int accum)
        int number;
        if (getnumber(&number) == EOF)
            return accum;
        return get_accumulated_number(accum + number);

    int accum = get_accumulated_number(0);
    printf("%d\n", accum);
is a pretty terrible regression, style-wise. I can't find who to cite this to, but it's been said that tail recursion is the goto of functional programming. So let's forget about using functions instead of loops and try to find a good reason to abandon conventional imperative languages. Here's a better distinction. Imperative programming is a style of programming that emphasizes constructing programs out of sequences of actions for the machine to take. Imperative libraries tend to be collections of re-usable routines that encode commonly-performed sequences of actions; if they take parameters, those parameters tend to be flags controlling conditionals, or pieces of data to be manipulated. If they return results, those results tend to be data calculated produced the machine as it carries out the sub-routines actions. Combinatorial programming is a style of programming that emphasizes constructing programs by composing sub-programs, without limiting how the sub-programs are composed. Combinatorial libraries tend to be collections of re-usable patterns of program composition. The results of their members tend to be sub-programs that can be combined with each other in a variety of ways; their parameters tend to likewise be sub-programs that the function will combine in interesting ways. Combinatorial programming is the style of programming encouraged by the program calculus Global Script. As an example, in the Iron Beach I/O language, which is based on Global Script, the column-sum example might be written as follows:

    for (
        'nums ← parse $ many $ number.parse;
        'total = foldl (+) 0 $ nums;
    ) print $ number.toString total ++ qq{\n}
Note that, unlike both the imperative and functional examples above, this program uses neither recursion nor general looping constructs; instead, combinators such as many and foldl provide special-purpose loops. Haskell advertises itself as a functional programming language. But, as seen above, that's boring. Which style of programming does Haskell encourage, imperative or combinatorial? Do Haskell libraries, and the functions they offer, mostly allow you to re-use canned packages of commands for the machine to carry out? Or do they allow you to compose your own programs in elegant and expressive ways? This is not an idle question: for an academic language, Haskell is a veritable hot-bed of library writing. The standard Haskell package distribution channel, known as Hackage, now has:
  • 2,182 packages, written by
  • 575 separate programmers, uploading
  • 12 new packages per day, with a total of
  • 130,000 downloads per month.
It's time for a reckoning: is all that programming done in a combinatorial style, or is Haskell — in practice — just another conventional language with funny syntax? Over the next week, I will examine the top 15 libraries, by total recent downloads, and attempt to classify the APIs they offer as combinatorial or imperative. My thesis is that Haskell development has, in the last 5-10 years, gone from a primarily combinatorial style to a primarily imperative one; as such, I will attempt to classify each library into one of two categories:
  1. Legacy Haskell: more than 5-10 years old.
  2. Imperative Haskell.
For the record, here are the most popular 15 libraries on Hackage, according to Haskell god Don Stewart: I will examine each of these in turn, primarily looking for evidence against my thesis that Haskell programming has become primarily imperative in nature.