Best Haskell Papers of 2009

As the year closed I reminisced on all the Haskell related papers I read in 2009. Some of them lifted my understanding to exciting new heights, while some others seemed impractical or overly tedious. The thought came upon me to present a list of the best of the best with the hope that these excellent papers might inspire and motivate others as they have me.

Naturally, many will reject such a subjective list. I concede that the list is heavily influenced by my own interests and lack of prerequisite knowledge in some cases. However, I’d argue that it isn’t entirely useless. First, I’d expect several of these papers to be well respected by experts in their respective fields. In this way, my list does shadow the objective truth. Second, my rare occupation as a commercial Haskell contractor makes my personal viewpoints of particular interest.

So, without further ado, the list.

The List

#7 Experience Report: Haskell in the “Real World” - Curt J. Sampson [abstract][pdf]

This paper showcases the decision of a software business to use functional programming without any prior experience with the paradigm. The business’s choice of Haskell for a programming language was outlined as well as the benefits they enjoyed. What struck me in particular were the problems and disadvantages the programming team encountered. It was refreshing to see my own experiences with these issues put so clearly. I point business associates primarily to this paper for an introduction to using Haskell commercially.

#6 Algebra of programming in Agda: Dependent types for relational program derivation - Shin-Cheng Mu et al.[abstract][pdf]

Agda, a dependently typed programming language with a syntax similar to Haskell, is fueling a lot of research this year. After reading many papers such as this one, I can’t help but think that the future lies in dependent types.

This paper presents an unorthodox approach to writing programs called relational program derivation. One starts by encoding a proposition, for example “the algorithm x sorts all lists”, and then deriving a program that the proposition is true for, like quicksort. The authors created an algebra for encoding these derivations in Agda. By using Agda, the derived programs include a computer verified proof of correctness.

I think it is going to take a while before the programming community, myself included, becomes fully aware of the implications of this paper.

#5 Fun with Type Functions - Oleg Kiselyov, Simon Peyton Jones, Chung-chieh Shan [link][pdf]

Reaching a limitation of the type checker is a common cause of ire for Haskell programmers. Type families, a new feature of ghc, removes a sizable amount of these limitations. Superseding an earlier compiler extension, functional dependencies, type families opens up many new areas of generic programming as well. One of the most interesting examples from the paper is a simple type-safe implementation of printf and scanf.

Note that the final version of this paper has not been published yet.

#4 Commercial uses: Going functional on exotic trades - Simon Frankau et al.[abstract][pdf]

Where the #7 spot paper expounds on the implications of switching to Haskell, this paper gives an in depth detail of a commercial domain specific embedded language (DSEL) using Haskell. The explanations within were atypically clear and well referenced. After studying this paper I felt confidant in using Haskell as a host language for DSEL’s.

For someone new to DSEL’s, this paper is great first read. In my opinion, DSEL’s are one of the most lucrative uses of Haskell commercially.

#3 Safe Functional Reactive Programming through Dependent types - Neil Sculthorpe, Henrik Nilsson [abstract][pdf]

This paper contributed two important findings to the field of functional reactive programming (FRP). First, it presented several obvious defects in current FRP implementations. Those who’ve programed with FRP in any depth are painfully aware of how easy it is to accidentally create programs that loop or leak memory at run-time. Sculthorpe and Nilsson pinpoint the exact cause of these issues.

The second major contribution is an FRP implementation that they proved does not have these problems. The aforementioned proof is computer verified. Can you guess how they did it? If you guessed that they used Agda, you’d be right! Amazing stuff.

#2 Typeclassopedia - Brent Yorgey [pdf]

Brent Yorgey’s Typeclassopedia, published in the Monad.Reader is the most comprehensive tutorial on the basic Haskell type classes (like Monoids, Monads, etc.) thus far. It stands out in both its accessibility to all levels of Haskell developers and its vast coverage. The paper can be used both as a tutorial and a reference. For more in-depth studies, lots of useful references are also included.

This paper is a great contribution to the Haskell community and will surely become a classic.

#1 Finally Tagless, Partially Evaluated - Jacques Carette, Oleg Kiselyov and Chung-Chieh Shan [abstract][pdf]

The essence of this paper is so simple, it bears repeating right here

varZ env = fst env
varS vp env = vp $ snd env
b b env = b
lam a env = \x -> a (x,env)
app a b env = (a env) (b env)

What you’re looking at is a simple implementation of a typed embedded language using Haskell98 as a host for both the language and the type checking. Prior to this paper, embedded language designers took advantage of Haskell98’s syntax, but not its type system.

The problem the authors so elegantly solve using Haskell98 was a main motivation behind the complex generalized algebraic data type (GADT) extensions to Haskell. Perhaps this extension isn’t necessary after all.

They further describe how to extend this simple interpreter to various efficient compilers and interpreters without modification of the original embedded language. Although the paper primarily uses OCaml, they provide equivalent Haskell code on their website.

I’m looking forward to seeing more complex embedded languages built on the ideas of this paper. It wins first prize for elegance, utility, and cleverness.

Notes

Runner-ups

The Arrow Calculus (Technical Report) - Sam Lindley, Philip Wadler, and Jeremy Yallop [link]. This paper describes a new syntax for arrows that more closely resembles the lambda calculus. It remains to be seen if this syntax is easier to use than our current proc syntax.

Push-pull functional reactive programming - Conal Elliott [link]. This paper is a theoretically elegant refactoring of FRP using standard type classes. Had I not directly encountered the subtle, and serious, bugs of this implementation in a commercial setting, it probably would have made the list.

Denotational Semantics - David Schmidt [link]. This is a book written in 1982 that I read last year. It is just as relevant today as it was back then. An excellent exposition of denotational semantics. My programming has substantially changed for the better since that read. It was regretfully disqualified for the medium and date of publication.

Where I hear about these papers

Journal of Functional Programming. I purchased a paper subscription.

The Monad.Reader. A must-read, freely available Haskell journal.

Haskell Weekly News. A weekly summary of community activity. A great place to discover powerful blog posts or pre-releases of journal articles.

Proceedings of ICFP (International Conference of Functional Programming) and affiliated SIGPLANs. I have access to these from the ACM website because I’m an alumnus of the University of Rochester. It took me a long time to get through the great quantity of papers available here, but it was very worthwhile.

Apology

I apologize for all mistakes and especially all my omissions. I am certain there are papers that would have made the list had I only read or understood them. I invite my readers to point out their favorites in the comments below.

Thanks to all who contribute to this field and give me countless hours of enjoyable reading and pondering.

See a short note on a blog post that I really wanted to be on this list.

Comments (9)

[...] wanted to squeeze this blog post into my Best Haskell Papers of 2009 article, but it unfortunately was written in late 2008. For your enjoyment, here is the entry [...]

ArthurJanuary 19th, 2010 at 4:23 am

The first link (the paper) was an awfully fun read…

“With the above criteria in mind, we looked at some of the more pop- ular free functional language implementations available. Our abil- ity to compare these was limited: we simply didn’t know enough about functional languages in general, and had no extensive experi- ence with any functional language implementation.”

I’ve tried to build multi-month small scale projects in Scala, OCaml and Haskell. My experience with Scala was that it was simply too verbose. I tried doing a web-app in Java, and found it maddeningly verbose. Scala was an improvement (compared to Java), but the Eclipse plugin wasn’t very mature and the syntax was still too verbose. I didn’t get too far with Scala because I felt that I was simply wasting too much time typing. If I were stuck on the JVM, it’d be a solid option, but then there’s Clojure.

OCaml was pretty powerful but ultimately too baroque. I spent nearly a year and a half trying to write a purely functional CAD program in it before giving up and using the OO component of the language. The OO system turned out to be clean, well thought out and aptly suited for conventional application programming, but no one wants to team up and write an staid old platform app these days.

Academic debates about type systems aside, Haskell’s typeclasses are more powerful than the ML system’s functors. Writing explicitly tail-recursive functions was also a pain. I think OCaml’s day may yet still come, if we’d be able to get it working on a mobile platform, because it’s (IMO) the best statically-typed hybrid functional/OO language out there.

My current preference right now is towards Haskell. The library support is fantastic, laziness is darn awful handy (space leaks be damned), and I can actually find other hackers doing stuff with the language (who helped me quite a bit when I was starting out). Sure, it took about a month to pick it up despite having done ML beforehand, but that’s a small price to pay for the joy of having a community, and of writing code with a plethora of pre-written toys (e.g. applicative functors, libraries for SMTP, the kitchen sink).

solrizeJanuary 26th, 2010 at 4:57 am

I think Ben Lippmeier’s PhD thesis about Disciple should be included. Its first chapter is one of the most clearheaded criticisms of Haskell that I’ve seen. The rest is about how to fix it. I’m in chapter 2 now.

Reference: Type Inference and Optimisation for an Impure World Ben Lippmeier PhD Thesis, Australian National University, Submitted June 2009. http://cs.anu.edu.au/people/Ben.Lippmeier/project/thesis/thesis-lippmeier-sub.pdf

solrizeJanuary 26th, 2010 at 5:00 am

I should also have said, the rest of the Haskell literature doesn’t discuss type-and-effect systems very much so I basically didn’t know anything about them. But Disciple is based on one and the thesis is explaining it pretty well so far, so I’m learning a lot.

David SankelJanuary 26th, 2010 at 11:47 am

@solrize: Thanks for that pointer. I’m looking forward to giving that thesis a read.

Linktipps Februar 2010 :: BlackflashJanuary 27th, 2010 at 11:53 am

<

p>[...] die Problematik von NOSQL vs. SQL beleuchtet. Vor allem das Fazit sollte man sich zu Herzen nehmen.Best Haskell Papers of 2009: Eine zugegebenerma

Rohan HartFebruary 10th, 2010 at 4:59 pm

Finally Tagless, Partially Evaluated is great, but was first published in 2007 (http://okmij.org/ftp/Computation/tagless-typed.html#tagless-final I’ve not checked to see whether there are any significant differences between the APLAS and JFP versions

TomApril 28th, 2011 at 9:36 pm

I’m not finished yet reading your entire list. But so far I think you have made all the papers in this list in a good order. I’ll let you know my opinion when I’m done reading all of them.

DaleMay 9th, 2011 at 12:12 am

Thank you for making the list. At last, I have something to do for this weekend. I’m sure that these papers are good reading.

Leave a comment

Your comment