Automating String Processing in Spreadsheets Using Input-Output Examples

Paper · 2011 · Sumit Gulwani

Summary

Many spreadsheet users are not programmers, yet they often need to reformat or extract text such as names, phone numbers and dates. Writing macros or scripts for this is beyond most of them. Gulwani studied Excel help forums and found two things. People usually describe these tasks by showing sample inputs with the outputs they want. Settling the details with a human expert can take several rounds over days. The paper defines a string expression language that concatenates constant strings and substrings. Substring boundaries are found with token-based regular expressions, and the language also supports conditionals (Switch) and loops. A synthesis algorithm based on version-space algebra finds every program in this language that fits the given examples, storing candidate concatenations compactly as DAGs. Extensions rank the candidates, spot likely errors in the user's examples, and ask the user about inputs that could be read in more than one way. The method was built as a Microsoft Excel add-in and answers each interaction round in a fraction of a second. It shows that programming by example can be fast and practical for everyday users.

Key points

The motivation is the more than 500 million spreadsheet users, for whom manipulating text ranks among the programming problems they face most often.
The language's constructors include Concatenate, SubStr, ConstStr, Loop and Switch, and positions are given as CPos(k) or Pos(r1, r2, c).
Response time averages under 0.1 s per interactive round, and the system usually converges within 1–4 rounds of examples.
The system is fully automatic, with no annotations needed from the user. It tolerates noise in the examples and suggests which inputs the user should label next.
The prototype Excel add-in passed what the author calls the "golden test": it synthesized part of its own code.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Institutions

🏢MicrosoftRedmond ·

United States378 works · 161,630 citations

Fields, topics and concepts

📚 Shelves 4Computer Science · 18,614 works Artificial Intelligence · 17,965 works Software · 119 works Computer Science Applications · 131 works

Cite

Cite as Sumit Gulwani. 2011. Automating String Processing in Spreadsheets Using Input-Output Examples. POPL 2011.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{gulwani2011automating,
  title = {{Automating String Processing in Spreadsheets Using Input-Output Examples}},
  author = {Sumit Gulwani},
  booktitle = {POPL 2011},
  year = {2011},
  doi = {10.1145/1925844.1926423},
  url = {https://doi.org/10.1145/1925844.1926423}
}

References

23 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

D. Angluin. Learning regular sets from queries and counterexamples. Inf. Comput., 75(2):87–106, 1987. find
K. Fisher and R. Gruber. PADS: a domain-specific language for processing ad hoc data. In PLDI, pages 295–304, 2005. find
K. Fisher, Y. Mandelbaum, and D. Walker. The next 700 data description languages. In POPL, pages 2–15, 2006. find
K. Fisher, D. Walker, K. Q. Zhu, and P. White. From dirt to shovels: fully automatic tool generation from ad hoc data. In POPL, 2008. find
M. Gualtieri. Deputize end-user developers to deliver business agility and reduce costs. In Forrester Report for Application Development and Program Management Professionals, April 2009. find
S. Gulwani. Dimensions in program synthesis. In PPDP. ACM, 2010. find
S. Gulwani and G. C. Necula. A polynomial-time algorithm for global value numbering. In SAS, pages 212–227, 2004. find
S. Jha, S. Gulwani, S. Seshia, and A. Tiwari. Oracle-guided component-based program synthesis. In ICSE, 2010. find
A. J. Ko, B. A. Myers, and H. H. Aung. Six learning barriers in end-user programming systems. In VL/HCC, pages 199–206, 2004. find
T. Lau. Why PBD systems fail: Lessons learned for usable AI. In CHI 2008 Workshop on Usable AI, Florence, Italy, 2008. find
T. Lau, S. Wolfman, P. Domingos, and D. Weld. Programming by demonstration using version space algebra. Machine Learning, 53(1-2), 2003. find
T. Lau, L. Bergman, V. Castelli, and D. Oblinger. Programming shell scripts by demonstration. In Workshop on SCLAS, AAAI, 2004. find
T. A. Lau, P. Domingos, and D. S. Weld. Version space algebra and its application to programming by demonstration. In ICML, 2000. find
T. A. Lau, P. Domingos, and D. S. Weld. Learning programs from traces using version space algebra. In K-CAP, pages 36–43, 2003. find
R. C. Miller and B. A. Myers. Interactive simultaneous editing of multiple text regions. In USENIX Annual Technical Conference, 2001. find
T. M. Mitchell. Generalization as search. Artif. Intell., 18(2), 1982. find
R. P. Nix. Editing by example. TOPLAS, 7(4):600–621, 1985. find
S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach (2nd Edition). Prentice Hall, 2 edition, December 2002. find
S. Srivastava, S. Gulwani, and J. Foster. From program verification to program synthesis. In POPL, 2010. find
J. M. Vilar. Query learning of subsequential transducers. In Proceedings of the 3rd International Colloquium on Grammatical Inference, 1996. find
J. Walkenbach. Excel 2010 Formulas. John Wiley and Sons, 2010. find
I. H. Witten and D. Mo. TELS: learning text editing tasks from examples. In Watch what I do: programming by demonstration, pages 293–307. MIT Press, Cambridge, MA, USA, 1993. find
Q. Xi and D. Walker. A context-free markup language for semi-structured text. In PLDI, pages 221–232, 2010. find

Updated 2 November 2026

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/gulwani-2011-automating-string-processing-spreadsheets-input/