Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Best of 2016 Recommended by Editor Recommended by Reviewer Recommended by Reader
SC-Haskell: sequential consistency in languages that minimize mutable shared heap
Vollmer M., Scott R., Musuvathi M., Newton R.  PPoPP 2017 (Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Austin, TX,  Feb 4-8, 2017) 283-298. 2017. Type: Proceedings
Date Reviewed: Aug 11 2017

Concurrency remains a hard problem. Efficient concurrency is even harder. But what if there were a setting where writing correct concurrent programs was significantly easier, at a very modest cost in efficiency? Too good to be true, right?

But this is exactly what the authors show for Haskell and similar languages, which naturally promote minimal use of shared heap mutation. The most fundamental invariant in this setting is sequential consistency (SC), a very natural memory model to program with. The authors modify GHC, the main Haskell compiler, to enforce SC. They then extensively benchmark this in a variety of situations, and convincingly show that their solution not only works, but its overhead is remarkably small.

One sometimes finds, buried behind a technically accurate title, a superb paper. While not a fundamental breakthrough, this paper is nevertheless scholarship at its best: well written, carefully motivated, based on extremely precise (and fully spelled out) theory, implemented in a real setting, and aggressively benchmarked in an adversarial manner (the authors go out of their way to show worst-case results). And as is increasingly standard, the full source is provided. They also go beyond this, proving preloaded virtual machines to allow independent verification. I will use this paper as an exemplar to my graduate students.

Unsurprisingly, such work did uncover a couple of bugs in GHC (as documented in the paper). While the paper says that these would be fixed by GHC 8.2, it turns out that the bug fixes were already implemented in version 8.0.2, as a bit of spelunking in the public bug database reveals.

Any referee depressed with all of the rotten papers they’ve been forced to read can gain a respite by reading this great paper, to remind them that there are excellent papers out there--whether or not they have any particular interest in Haskell or concurrency.

Reviewer:  Jacques Carette Review #: CR145479 (1710-0669)
Bookmark and Share
  Editor Recommended
Featured Reviewer
Haskell (D.3.2 ... )
Concurrency (D.4.1 ... )
Dynamic Storage Management (D.3.3 ... )
Models Of Computation (F.1.1 )
Modes Of Computation (F.1.2 )
Optimization (D.3.4 ... )
Would you recommend this review?
Other reviews under "Haskell": Date
Just do it while compiling!: Fast extensible records in Haskell
Martinez B., Viera M., Pardo A.  PEPM 2013 (Proceedings of the ACM SIGPLAN 2013 Workshop on Partial Evaluation and Program Manipulation, Rome, Italy,  Jan 21, 2013) 77-86, 2013. Type: Proceedings
Jul 2 2013
Haskell: the craft of functional programming (3rd ed.)
Thompson S.,  Addison-Wesley Publishing Company, Harlow, UK, 2011. 528 pp. Type: Book (978-0-201882-95-7)
May 11 2012
Learn you a Haskell for great good!: a beginner’s guide
Lipovača M.,  No Starch Press, San Francisco, CA, 2011. 400 pp. Type: Book (978-1-593272-83-8)
Mar 23 2012

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2017 ThinkLoud, Inc.
Terms of Use
| Privacy Policy