Authors
William Harris & Sumit Gulwani
Abstract
Every day, millions of computer end-users need to perform tasks over large, tabular data, yet lack the programming knowledge to do such tasks automatically.
In this work, we present an automatic technique that takes from a user an example of how the user needs to transform a table of data, and provides to the user a program that implements the transformation described by the example.
In particular, we present a language of programs TableProg that can describe transformations that real users require. We then present an algorithm ProgFromEx that takes an example input and output table, and infers a program in TableProg that implements the transformation described by the example.
When the program is applied to the example input, it reproduces the example output. When the program is applied to another, potentially larger, table with a "similar" layout as the example input table, then the program produces a corresponding table with a layout that is similar to the example output table.
A user can apply ProgFromEx interactively, providing multiple small examples to obtain a program that implements the transformation that the user desires. Moreover, ProgFromEx can help identify "noisy" examples that contain errors.
To evaluate the practicality of TableProg and ProgFromEx, we implemented ProgFromEx as a module for the Microsoft Excel spreadsheet program. We applied the module to automatically implement over 50 table transformations specified by end-users through examples on online Excel help forums.
In seconds, ProgFromEx found programs that satisfied the examples and could be applied to larger input tables. This experience demonstrates that TableProg and ProgFromEx can significantly automate the tasks over tabular data that users need to perform.
Sample
These tables are an example of a common table transformation that a user would like to perform automatically. The tables are from a real Excel help forum thread.
In this paper, we make the following contributions:
- We present a language of programs, TableProg, that can express a rich set of practical transformations over tabular data. TableProg is designed to express table transformations required by real users, but is conceptually simple and is described by a small semantics.
- We present a novel algorithm, ProgFromEx, for inferring TableProg programs from example input and output tables. We show the correctness of ProgFromEx, and analyze its complexity.
- We report our experience using ProgFromEx. We implemented ProgFromEx as a plug-in module for the Microsoft Excel spreadsheet program, and applied the module to automatically infer TableProg programs that implement over 50 transformations specified by examples in online Excel help forums.
Publication
2011, ACM SIGPLAN Notices, Volume 46, Issue 6, June, pages 317-328
Full article
Spreadsheet table transformations from examples
