Automating string processing in spreadsheets using input-output examples
The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
Abstract
We describe the design of a string programming/expression language that supports restricted forms of regular expressions, conditionals and loops. The language is expressive enough to represent a wide variety of string manipulation tasks that end-users struggle with. We describe an algorithm based on several novel concepts for synthesizing a desired program in this language from input-output examples. The synthesis algorithm is very efficient taking a fraction of a second for various benchmark examples. The synthesis algorithm is interactive and has several desirable features: it can rank multiple solutions and has fast convergence, it can detect noise in the user input, and it supports an active interaction model wherein the user is prompted to provide outputs on inputs that may have multiple computational interpretations. The algorithm has been implemented as an interactive add-in for Microsoft Excel spreadsheet system. The prototype tool has met the golden test - it has synthesized part of itself, and has been used to solve problems beyond author's imagination.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Artificial intelligence: a modern approach
(1995) · Choice Reviews Online · doi:10.5860/choice.33-1577 · Cited by 21,974
Learning regular sets from queries and counterexamples
Angluin, D. (1987) · Information and Computation · doi:10.1016/0890-5401(87)90052-6 · Cited by 2,114
Mitchell, T. M. (1982) · Artificial Intelligence · doi:10.1016/0004-3702(82)90040-6 · Cited by 1,412
Watch what I do: programming by demonstration
Cypher, A., Halbert, D. C., Kurlander, D., Lieberman, H. A., Maulsby, D., Myers, B. A., & Turransky, A. (1993) · Medical Entomology and Zoology · Cited by 1,027
Six Learning Barriers in End-User Programming Systems
Ko, A. J., Myers, B. A., & Aung, H. H. (2004) · 2004 IEEE Symposium on Visual Languages - Human Centric Computing · doi:10.1109/vlhcc.2004.47 · Cited by 549
Oracle-guided component-based program synthesis
Jha, S., Gulwani, S., Seshia, S. A., & Tiwari, A. (2010) · Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering - Volume 1 · doi:10.1145/1806799.1806833 · Cited by 510
Self-citationFrom program verification to program synthesis
Srivastava, S., Gulwani, S., & Foster, J. S. (2010) · Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/1706299.1706337 · Cited by 267
Self-citationDimensions in program synthesis
Gulwani, S. (2010) · Proceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming · doi:10.1145/1836089.1836091 · Cited by 238
Self-citationProgramming by Demonstration Using Version Space Algebra
Lau, T., Wolfman, S. A., Domingos, P., & Weld, D. S. (2003) · Machine Learning · doi:10.1023/a:1025671410623 · Cited by 178
PADS: a domain-specific language for processing ad hoc data
Fisher, K. S., & Gruber, R. E. (2005) · ACM SIGPLAN Notices · doi:10.1145/1064978.1065046 · Cited by 132
Research works printed but not linked: 7
- Gualtieri M., 2009, Forrester Report for Application Development and Program Management Professionals
- Lau T., 2008, CHI 2008 Workshop on Usable AI
- Lau T., 2004, Workshop on SCLAS, AAAI
- Lau T. A., 2000, ICML
- Miller R. C., 2001, USENIX Annual Technical Conference
- 10.5555/645516.658243 · doi:10.5555/645516.658243
- Walkenbach J., 2010, John Wiley and Sons
Cited by
Items 701–767 of 767
Heer, J., Hellerstein, J. M., & Kandel, S. (2019) · Springer eBooks · doi:10.1007/978-3-319-77525-8_9
Machine Learning for Programming Language Processing
Alon, U. (2021) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.6730560
Heer, J., Hellerstein, J. M., & Kandel, S. (2012) · Springer eBooks · doi:10.1007/978-3-319-63962-8_9-2
Program Generation from Diverse Video DemonstrationsPreprint
Manchin, A., Sherrah, J., Wu, Q. M., & van den Hengel, A. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2302.00178
Select-Them-Repair-Them: Automatically Optimize Pseudocode-to-Code Data
Yu, Q., & Gu, N. (2023) · IEEE International Conference on Big Data Analytics (ICBDA) · doi:10.1109/icbda57405.2023.10104712
Multi-Intent Detection in User Provided Annotations for Programming by Examples SystemsPreprint
Kumar, N. A., Gupta, N., Guttula, S., & Patel, H. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2307.03966
Han, J. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2311.03753
Urrutia, L. Z., Liventsev, V., Febres, J., & Sterling, R. (2023) · Research Square · doi:10.21203/rs.3.rs-3735947/v1
EmFORE: Learning Email Folder Classification Rules by Demonstration
Singh, M. P., Verbruggen, G., Cambronero, J., Le, V., & Gulwani, S. (2024) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v38i21.30581
Self-citationImproving Web Automation Tools through UI Context and Demonstration
Krosnick, R. (2024) · Deep Blue (University of Michigan) · doi:10.7302/22949
Exploring Data Preparation Modules by Examples
Belhajjame, K., Barhamgi, M., & Camacho, D. (2024) · Lecture notes in computer science · doi:10.1007/978-981-97-4982-9_5
WebTableX: Efficiently Discovering Web Table Transformations Through Sampling
Tehrani, S. O., Nobari, A. D., & Rafiei, D. (2025) · International World Wide Web Conference (WWW) · doi:10.1145/3701716.3715600
Contextual State Pattern Determination-Based Heuristic Program Synthesis
Pan, H., Dou, Q., Wang, H., & Zhang, S. (2025) · Communications in computer and information science · doi:10.1007/978-981-96-7175-5_13
Program Synthesis for Geometric Modeling
Pascual, R., Gall, P. L., Belhaouari, H., & Arnould, A. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-04848-6_9
Tang, X., Wong, S., He, Z., Yang, Y., & Chen, Y. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2507.11470
Recursive self-models and minimal phenomenal experiencePreprint
Deane, G., & Demekas, D. (2025) · PsyArXiv (OSF Preprints) · doi:10.31234/osf.io/u8y6f_v1
Analysis of Error Sources in LLM-based Hypothesis Search for Few-Shot Rule InductionPreprint
Parab, A., Lu, H., Wu, Y. N., & Gulwani, S. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2509.01016
Self-citationMetaJoin: Adaptive Join Selections for Heterogeneous TablesPreprint
Wang, N., & Galhotra, S. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2512.02444
Genetic Programming Techniques in Engineering Applications
Lorenzo, A. D. (2014) · OpenstarTs (Univeristy of Trieste https://www.units.it/)
Sergey, I. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-21037-2
Accelerated Programming for Data Analysis and Processing
Le, T. K. T. (2025) · heiDOK (Heidelberg University) · doi:10.11588/heidok.00035971
Το πρόβλημα της σύνθεσης προγραμμάτων
Tsivra, A. (2024) · DSpace - NTUA (National Technical University of Athens) · doi:10.26240/heal.ntua.26631
Program Synthesis for Quantum Applications
Deng, H. (2025) · University Libraries (University of Maryland) · doi:10.13016/1iuj-bwm1
Basha, M. (2025) · cIRcle (University of British Columbia) · doi:10.14288/1.0444836
Καθαρισμός δεδομένων: επισκόπηση και εφαρμογή σε πραγματικά δεδομένα
Τσικάκης, Δ., & Μπαλαμώτη, Α. (2023) · Institutional Repository Hellanicus · doi:10.26215/heal.uoa.6508
Synthesis of Provable Recursive Functions
Wagner, E. M. (2024) · reposiTUm (TU Wien) · doi:10.34726/hss.2024.120500
Aktives Dialogmanagement für eine natürlichsprachliche Benutzerschnittstelle
Wachtel, A. (2024) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000169813
Explainable Methods for Information Extraction
Vacareanu, R., & Vacareanu, R. (2024) · UA Campus Repository (The University of Arizona)
Designing interactive visualizations by demonstration
Zong, J. (2020) · DSpace@MIT (Massachusetts Institute of Technology)
Programmasynthese voor het Automatisch Transformeren van Data
Verbruggen, G. (2023) · Lirias
Distributed Coordination and Computation Synthesis
Houshmand, F. (2023) · eScholarship (California Digital Library)
Human-Centered Program Synthesis
Ferdowsifard, K. (2024) · eScholarship (California Digital Library)
Synthesis and Repair for Functional Programming: A Type- and Test-Driven Approach
Gissurarson, M. P. (2024) · Chalmers Research (Chalmers University of Technology)
Synthetic generation of programs using Neural Networks
Ferrús Ferri, C. M. (2021) · Repositorio Institucional de la Universidad de Alicante (Universidad de Alicante)
Conditional Graph Generative Models for Code and Texture Generation
KC, D. R., & KC, D. R. (2024) · UA Campus Repository (The University of Arizona)
IRE: A Framework For Inductive Reverse Engineering
(2019) · Arizona State University Library Digital Repository (Arizona State University)
Next Generation Black-Box Web Application Vulnerability Analysis Framework
(2017) · Arizona State University Library Digital Repository (Arizona State University)
Type-Directed Program Synthesis for Complex APIs
Guo, Z. (2024) · eScholarship (California Digital Library)
Program Synthesis over Noisy Data
Handa, S. (2022) · DSpace@MIT (Massachusetts Institute of Technology)
Enhancing Software Engineering Tasks with Intelligent Assistant Tools
Dakhel, A. M. (2023) · PolyPublie (École Polytechnique de Montréal)
Uniform Projection of Program Space Geometry for Genetic Improvement of Software
Craine, B., & Porter, B. (2025) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/3712256.3726393
Tensor program optimization through program synthesis
Brauckmann, A. (2025) · ERA · doi:10.7488/era/6825
Bayesian Program Learning by Decompiling Amortized KnowledgePreprint
Palmarini, A. B., Lucas, C. G., & Siddharth, N. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2306.07856
Debugging into Existence with Program Synthesis
Frankel, G., Segal, S., & Peleg, H. (2025) · IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC) · doi:10.1109/vl-hcc65237.2025.00021
BatCoder: Self-Supervised Bidirectional Code-Documentation Learning via Back-TranslationPreprint
Xu, J., Lu, Y., Huang, Z., Lv, C., Wang, X., Li, S., Xu, Z., Guo, Z., Wang, Z., Tian, M., et al. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2602.02554
MagicCopy: Bring my data along with me beyond boundaries of appsPreprint
Vaithilingam, P., Glassman, E. L., Riche, N. H., Ramos, G., Inala, J. P., & Wang, C. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2604.04307
Domain agnostic techniques for scaling up program synthesis
Matricon, T. (2024) · theses.fr (ABES) · doi:10.70675/c6818c13z66a7z4489zb542za75798a64fc4
Automatic String Data Validation with Pattern Discovery
Han, Z., Lin, X., Di, P., Xiao, C., Onizuka, M., Liu, J., Mao, R., & Qin, J. (2026) · Lecture notes in computer science · doi:10.1007/978-981-92-0369-7_38
BAT: Target-Instance-Free Data Preparation Synthesis via LLM-Driven Tree Search
Ge, C., Liu, Y. H., Tang, Y., Zhu, Y., Tu, Y., & Gao, Y. (2026) · Proceedings of the ACM on Management of Data · doi:10.1145/3802020
Learning Mental Models From Unreliable EvidencePreprint
Qin, J., Gao, Z., Piriyakulkij, W. T., Radovanovic, M., Sommerville, J. A., Ellis, K., & Kryven, M. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2605.24528
Program lifting for acceleration
Magalhães, J. W. D. S. (2026) · ERA · doi:10.7488/era/7291
A Benchmark and Framework for Evaluating Next Action Predictions in SpreadsheetsPreprint
Agrawal, T., Le, V., Gulwani, S., & Verbruggen, G. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2606.13802
Self-citationAn Empirical Comparison of Cost Functions in Inductive Logic Programming
Hocquette, C., & Cropper, A. (2026) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.21950
Repairing Regex-Dependent String-Manipulation Programs
Chida, N., & Terauchi, T. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-32519-8_14
Zenkner, J., Sesterhenn, T., Grams, T., & Bartelt, C. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2608.03461
(2024) · OAPEN (The OAPEN Foundation)
GUIDE: Designer-in-the-loop Authoring of Conformant Generative User InterfacesPreprint
Lee, H., Wang, Z., Moy, A., Nagubandi, S., & Wu, J. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2609.21285
namefill: Synthesizing DNS Naming Conventions
Sommers, J., Kranig, C., Wung, W.-S., Barford, P., Crovella, M. E., & Pauley, E. (2026) · ACM Internet Measurement Conference (IMC) · doi:10.1145/3777912.3839791
Towards eliminating expert creative help in automated reasoning
Murali, A. (2024) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign)
Smart Contract Synthesis via Multi-modal Specifications
Chen, T., Chen, H., Xiang, H., & Wang, Y. (2026) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1145/3832783.3837430
A Survey of Code-to-Code Translation: From Statistical Rule-Based Systems to LLM Agents
Zhang, Z., Wen, S., Yan, Z., Zhu, B., Shen, C., & Guo, H. (2026) · Algorithms · doi:10.3390/a19100857
From Abstraction to Action: DSLs for Natural Language Abstraction Interpretation and ExecutionPreprint
Lisha, A., & Tsarfaty, R. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.28311
ValiAssist: Scaling LLM-generated Programming Feedback Validation by DemonstrationPreprint
Tang, X., Abulikemu, R., Gao, P., & Chen, Y. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.27248
Work Agents: Systems, Capabilities, and OptimizationPreprint
Xu, Z., Du, E., Gao, M., Yang, C., Shen, J., Chen, Z., Yao, Z., Guo, Y., Lu, Y., Huang, J., et al. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.35845
From Specification to Kernel Commit: Verified Code Generation on Real-World Systems
Sun, H., Li, Z., Li, C., & Su, Z. (2026) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3845814.3850060
Metadata
- Authors
- Gulwani, S.
- Affiliations
- Microsoft (United States) (US)
- Corresponding author
- Gulwani, Sumit
- ORCID
- Gulwani, Sumit
- Venue
- ACM SIGPLAN Notices
- Published
- 2011-01-26
- Volume
- 46
- Issue
- 1
- Pages
- 317-330
- ISSN
- 0362-1340 (ISSN-L)
- 1558-1160
- OpenAlex
- W2132525863
- Cited by
- 581
- References
- 23
- Citations by year
- 2026: 10 · 2025: 19 · 2024: 26 · 2023: 35 · 2022: 29 · 2021: 60 · 2020: 74 · 2019: 56 · 2018: 54 · 2017: 55 · 2016: 39 · 2015: 36 · 2014: 38 · 2013: 19 · 2012: 20
- FWCI
- 92.00
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- ACM SIGPLAN Notices (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Software › Spreadsheets and End-User Computing
- Physical Sciences › Computer Science › Software › Logic, programming, and type systems
- Physical Sciences › Computer Science › Computer Science Applications › Teaching and Learning Programming
- Keywords
- string processing, spreadsheet programming, program synthesis, input-output examples, regular expressions, interactive synthesis, Excel add-in, noise detection
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.