Research Highlights from PLDI 2015

Last week I attended the 36th annual ACM SIGPLAN conference on Programming Language Design and Implementation (PLDI) in Portland, Oregon. While the entire technical program was excellent, a few papers stood out to me as particularly exciting examples of how programming language design can solve challenging problems for programmers and non-programmers alike. I should stress that this is by no means an exhaustive list of great work from this year’s conference — go check out the technical program! (Be sure to check out my research group’s paper, “Exploring and Enforcing Security Guarantees via Program Dependence Graphs”.) As a neat feature this year, all papers from PLDI 2015 will be freely available for one year on the ACM digital library.

Automatically Improving Accuracy for Floating Point Expressions

Pavel Panchekha, Alex Sanchez-Stern, James R. Wilcox, and Zachary Tatlock

Floating-point arithmetic is an incredibly important domain of programming with applications from science and engineering to writing video games. Unfortunately, while floating point is a convenient approximation to real arithmetic, it is far from perfect, and worse still, incredibly difficult to understand and debug — writing good floating point programs requires a deep understanding of both numerical methods and how floating point works. To solve this problem, Panchekha et al built Herbie, a tool that automatically synthesizes fast and accurate floating point programs. Herbie incorporates domain specific knowledge about numerical methods that allow even novice programmers to write good floating-point code.

FlashRelate: Extracting Relational Data from Semi-Structured Spreadsheets Using Examples

Dan Barowy, Sumit Gulwani, Ted Hart, and Benjamin Zorn

As Dan pointed out in his talk, spreadsheets are one of the most pervasive computing models in the world, with hundreds of millions of users. Because most of those spreadsheets are really programs, spreadsheets are one of the most widely used programming languages in the world! Unfortunately, as a programming language, they provide pretty bare-bones support for the types of complex, database-like operations users want from them. As a result, users end up encoding their high-dimensional data into spreadsheets using complex, ad-hoc data formats. This has the unfortunate result that if the data ends up in the wrong format for a particular computation, reformatting it can be extremely tedious and error-prone. FlashRelate is a synthesis tool that allows users to extract relational data from spreadsheets by supplying input/output examples using an interactive user interface. Not only does FlashRelate solve an incredibly common and high-impact problem, its also an impressive piece of software. Dan and his co-authors took home the best artifact award! I’m looking forward to the tool being available on the web for my own use.

Lightweight, Flexible Object-Oriented Generics

Yizhou Zhang, Andrew Myers, Barbara Liskov, Guido Salvaneschi, and Matt Loring

One of the on-going debates in my research group is the relative merits of object-oriented programming with generics (à la Java) and functional programming with type classes (à la Haskell). Well, now we can have our cake and eat it, too. Yizhou and his co-authors introduce Genus, a Java-like programming language with a new model-based generic programming model. Generic programming in Genus is based on first-class “models” that capture how different types witness type constraints. Similar to type classes, it is possible to retroactively add support for a type constraint to an existing type. Unlike type classes, a type may satisfy the same type constraints in multiple different ways using different models. Another neat feature I often wish for in Java is the ability to have static methods associated with a generic type. The paper describes a slew of additional features including automatic structural constraint satisfaction, multi-methods, model inheritance and enrichment, and existential quantification. Another great project that I’m looking forward to downloading and using myself.

Finding Counterexamples from Parsing Conflicts

Chinawat Isradisaikul and Andrew Myers

While I was pleased to see parser generators beating parser combinators and other hand-coded options in a recent poll of ways to write parsers, certainly one area that parser generators have never excelled is in outputting good error messages. Oh, the dreaded shift/reduce conflict… I think the results of this project speak for themselves. Chin and Andrew’s tool turns something like this:

state 13

    1 exp: exp . PLUS exp
    1    | exp PLUS exp .

    PLUS   shift, and go to state 4

    PLUS      [reduce using rule 1 (exp)]
    $default  reduce using rule 1 (exp)

into this:

Warning : *** Shift/Reduce conflict found in state #13
  between reduction on expr ::= expr PLUS expr •
  and shift on         expr ::= expr • PLUS expr
  under symbol PLUS
  Ambiguity detected for nonterminal expr
  Example: expr PLUS expr • PLUS expr
  Derivation using reduction:
    expr ::= [expr ::= [expr PLUS expr •] PLUS expr]
  Derivation using shift:
    expr ::= [expr PLUS expr ::= [expr • PLUS expr]]

I actually first encountered this work when I got a suprisingly awesome error message when writing a parser using the Polyglot compiler framework. I fully expect this to be the new standard for parser generators to follow.