Monday, 31 May 2010

Why is Haskell used so little in the industry?

Bugspy asked an interesting question on Stack Overflow recently:
It is a wonderful, very fast, mature and complete language. It exists for a very long time and has a big set of libraries. Yet, it appears not to be widely used. Why ? I suspect it is because it is pretty rough and unforgiving for beginners, and maybe because its lazy execution makes it even harder
Jeff Atwood, cofounder of Stack Overflow, has since closed the question for being subjective and argumentative. Sadly, Marc Gravell chose to edit my answer and delete half of my comments so the discussion no longer makes sense. However, my response will be of interest to anyone considering gambling their own money on Haskell so I shall repeat it here.
The first point of interest is Norman Ramsey's meta-answer which was written from his point of view as an academic. Norman explains why he believes that major institutes have already made "great use" of Haskell:
"Don't tell that to Credit Suisse or Standard Chartered, two banks which have made great use of Haskell. And don't tell Peerium or Galois or any of the other successful startups that use Haskell. Don't tell any Commercial Users of Functional Programming. And especially don't tell their customers!"
Citing Credit Suisse and Standard Chartered is just name-dropping big banks in the hope that it will deceive people into thinking that these institutes are seriously invested in Haskell. They are not. In reality, the number of full-time Haskell developers at Credit Suisse has long since fallen to zero and one diehard fled to Standard Chartered. This is a tiny fraction of a percent of the total development effort at those institutes and does not constitute "great use of Haskell" by any stretch of the imagination.
Citing CUFP is also misleading. CUFP is primarily a Haskell conference attended almost entirely by academics and students, none of whom have customers.
Norman Ramsey goes on to say:
"Industry rewards getting products out quickly, even if the products are barely adequate. Some ways to get things out quickly include...Throw lots of teams at the problem; first one with a successful approach wins."
This is an absurdly-inaccurate caricature of industry. In reality, it is precisely these kinds of comments from key figures of the Haskell community that drive industrialists away.
In the same thread on Stack Overflow, Don Stewart claimed that "Haskell, if anything, is more widely used than most / all FP languages" and later cited the prevalence of Haskell among CUFP delegates as evidence. This could not be further from the truth, of course. Mathematica has millions of users and dozens of commercial libraries. The F# Hub has 21,228 registered members and F# has several commercial libraries (e.g. WebSharper, CoherentPDF, F# for Visualization and F# for Numerics). In contrast, the Haskell-Cafe has only 3,339 subscribers and Haskell has never had any commercial libraries.
Industry is very diverse and it often rewards taking risks with new technologies because that can give you a competitive advantage. We regularly take risks with fringe technologies like OCaml and F#. If you get it right, it really can pay dividends. If you get it wrong, you'll go the way of Red Nucleus (one of the many deceased Haskell startups). We decided to diversify in 2007 and I was challenged with the task of finding other functional programming languages for us to use. I studied Haskell extensively and made the informed decision not to go anywhere near it for the following reasons:
  • Lack of compelling examples. After much searching I found only one program, Power Serious by Doug McIlroy, that I found compelling but it is just an academic curiosity.
  • Lack of genuine success stories. After a bit of digging, I was horrified to discover that almost all of the "success stories" listed on the Haskell in Industry page were fakes. Anygma may ship a product in the future but do not intend to write it in Haskell. Ansemond had a product and are actually a real software company but (according to their blog) there was "no Haskell" in their product. Antiope didn't list any products at all, let alone ones written in Haskell. Bluespec were advertising their product but their customer testimonials were from "Elvis Lives", "Chicken Man", "Painful Eliminations", "Mr. Bigglesworth" and two people from the founders' University. The prominent member of the Haskell community from Credit Suisse told us that his employer was seriously invested in Haskell with over a hundred developers and that he was personally responsible for much of their Haskell development but this turned out to be another deception: Credit Suisse have over a hundred developers using other languages, he had been a large proportion of a tiny number of Haskell developers and Haskell never caught on at Credit Suisse (they are now merely maintaining legacy Haskell code). Erlang Training and Consulting were placed on the Haskell in Industry page as spam. They had apparently never made any use of Haskell whatsoever. Galois are apparently the only self-sustaining company seriously invested in Haskell in the world but their only visible guy is notable only for having listed a PhD on LinkedIn that he hadn't earned and for generating enormous quantities of contentless propaganda such as the analysis of delegates to a Haskell conference above and his analyses of IRC chat. Nokia was a link to a job advert not directly related to Haskell. Openomy was a link to a blog with no products. Many "startups" including Red Nucleus were listed but never saw the light of day. SeeReason Partners, LLC was another company with no products or services at all, let alone Haskell-related ones. One of the "founders" assured us back in 2007 that they would be putting up a real company page but that never happened. This systematic deception of the public by most of the prominent members of the Haskell community was the last nail in Haskell's coffin from our perspective. Regardless of technical merit, the risk of being associated with such people is far too great.
  • User unfriendly. The compiler alone is a nightmare to install (GHC 6.12 just took me 2 days!) and the libraries are even worse (cabal install breaks on about 30% of packages). Trying to put customers through that pain makes about as much business sense as going into private dentistry without anesthetics.
  • Commerce unfriendly. The entire Haskell infrastructure is built on the assumption that software is distributed in source form. Nobody has ever succeeded in selling closed source Haskell libraries to Haskell programmers. So we could only expect to sell source code (an unnecessary risk not imposed by competing languages) or use it in-house. Almost all Haskell users are academics and many, like Norman Ramsey, are vehemently anti-industry.
  • Ill advised. Even Simon Peyton-Jones advised against us trying to use Haskell in industry because they neither wish nor intend to support real users. Haskell is an on-going experimental research project constantly at risk of major breaking changes.
  • Bad science. The Haskell community generate an unprecedented amount of bad science, setting out to draw the conclusion that Haskell is great and using every trick in the book to make that conclusion seem feasible. In many cases, it requires quite some effort to uncover the truth. For example, Saynte published results for "naively" parallelized ray tracers and concluded that Haskell was the easiest language to parallelize efficiently, requiring only a single line change. This deception was perpetrated by starting with a "serial" version that had already been extensively reworked in order to make it amenable to parallelization and then disabling optimizations only for the competitors (and even adding their compile times in one case!) in order to make Haskell appear competitive. Moreover, that reworking could only have been done on the basis of extensive benchmarking and development. Even the academics publishing Haskell research are up to it. For example, in the recent paper Regular Shape-polymorphic parallel arrays Manuel Chakravarty et al. artificially close the gap between Haskell and C by benchmarking only cache ignorant algorithms (that spend all of their time stalled on unnecessary cache misses), incorrectly states that such algorithms are "widely used", describes the one-line change required to parallelize the C code as "considerable additional effort" despite the fact that both the serial and parallel C solutions are substantially more concise than their Haskell counterparts, refused to provide me with their C code so that I could try to verify their findings (until I published this blog post, their code is now here) and cherry picked Haskell's highest performing results as a function of the number of threads (which peaks at an unpredictable number before seeing performance degradation). When I voiced my concerns, Don Stewart abused his moderator status on the forum by deleting my criticisms. To date, these flaws in the paper have not been addressed.
So I decided that we would diversify into F# instead of Haskell. With the benefit of hindsight, that was absolutely the correct decision. Perhaps other people will choose to risk using Haskell in industry but I would strongly advise them to be very cautious about the "information" that will doubtless be bestowed upon them.

Sunday, 30 May 2010

Purely functional Heap Sort in OCaml, F# and Haskell

Here's Markus Mottl's OCaml translation of Okasaki's purely functional leftist heap:

module LeftistHeap (Element : ORDERED) : (HEAP with module Elem = Element) = struct module Elem = Element type heap = E | T of int * Elem.t * heap * heap let rank = function E -> 0 | T (r,_,_,_) -> r let makeT x a b = if rank a >= rank b then T (rank b + 1, x, a, b) else T (rank a + 1, x, b, a) let empty = E let is_empty h = h = E let rec merge h1 h2 = match h1, h2 with | _, E -> h1 | E, _ -> h2 | T (_, x, a1, b1), T (_, y, a2, b2) -> if Elem.leq x y then makeT x a1 (merge b1 h2) else makeT y a2 (merge h1 b2) let insert x h = merge (T (1, x, E, E)) h let find_min = function E -> raise Empty | T (_, x, _, _) -> x let delete_min = function E -> raise Empty | T (_, x, a, b) -> merge a b end

Here's a simple OCaml heapsort based upon the same idea:

type 'a heap = E | T of int * 'a * 'a heap * 'a heap let rank = function E -> 0 | T (r,_,_,_) -> r let t(x, a, b) = let a, b = if rank a > rank b then a, b else b, a in T(rank b + 1, x, a, b) let rec merge = function | h, E | E, h -> h | (T(_, x, a1, b1) as h1), (T(_, y, a2, b2) as h2) -> if x >= y then t(x, a1, merge(b1, h2)) else t(y, a2, merge(h1, b2)) let rec to_list xs = function | E -> xs | T(_, x, a, b) -> to_list (x::xs) (merge(a, b)) let heapsort fold xs = to_list [] (fold (fun h x -> merge(t(x, E, E), h)) E xs)

This takes 0.6s to sort 100k floats on this 2× 2.0GHz E5405 Xeon and it happily sorts millions of elements.

Here's a translation to F#:

type LeftistHeap<'a> = | E | T of int * 'a * LeftistHeap<'a> * LeftistHeap<'a> let rank t = match t with E -> 0 | T (r, _, _, _) -> r let T(x, a, b) = let a, b = if rank a > rank b then a, b else b, a T(rank b, x, a, b) let rec merge h1 h2 = match h1, h2 with | h, E | E, h -> h | T(_, x, a1, b1), T(_, y, _, _) when x >= y -> T(x, a1, merge b1 h2) | T(_, x, _, _), T(_, y, a2, b2) -> T(y, a2, merge h1 b2) let rec toList xs = function | E -> xs | T(_, x, a, b) -> toList (x::xs) <| merge a b let heapSort xs = toList [] (List.fold (fun h x -> merge (T(x, E, E)) h) E xs)

This takes 1.3s and also happily sorts millions of elements.

Here's translation to Haskell:

data Heap a = E | T Int a (Heap a) (Heap a) rank E = 0 rank (T r _ _ _) = r mk x a b = if rank a > rank b then T (rank b + 1) x a b else T (rank a + 1) x b a merge h E = h merge E h = h merge h1@(T _ x a1 b1) h2@(T _ y a2 b2) = if x >= y then mk x a1 (merge b1 h2) else mk y a2 (merge h1 b2) toList xs E = xs toList xs (T _ x a b) = toList (x:xs) $ merge a b heapSort xs = toList [] (foldr (\x -> \h -> merge (mk x E E) h) E xs)

This takes 1.3 second to sort 100k floats but it stack overflows on large inputs.