Learning Semantic String Transformations from Examples

By Rishabh Singh, Sumit Gulwani. 2012

137 citations recorded by the source corpus.

We address the problem of performing semantic transformations on strings, which may represent a variety of data types (or their combination) such as a column in a relational table, time, date, currency, etc. Unlike syntactic transformations, which are based on regular expressions and which interpret a string as a sequence of characters, semantic transformations additionally require exploiting the semantics of the data type represented by the string, which may be encoded as a database of relational tables. Manually performing such transformations on a large collection of strings is error prone and cumbersome, while programmatic solutions are beyond the skill-set of end-users. We present a programming by example technology that allows end-users to automate such repetitive tasks. We describe an expressive transformation language for semantic manipulation that combines table lookup operations and syntactic manipulations. We then present a synthesis algorithm that can learn all transformations in the language that are consistent with the user-provided set of input-output examples. We have implemented this technology as an add-in for the Microsoft Excel Spreadsheet system and have evaluated it successfully over several benchmarks picked from various Excel help-forums.

Subfields: Computer Networks and Communications, Information Systems, Management Science and Operations Research, Code Generation & Program Synthesis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Information Systems

In Management Science and Operations Research

In Code Generation & Program Synthesis

Citations in the corpus

Learning with Latent Language (2017, neutral): “While string editing tasks of the kind shown in Figure 5 are popular in both the programming by demonstration literature (Singh and Gulwani, 2012) and the semantic parsing literature (Kushman and Barzilay, 2013), we are unaware of any datasets that support both learning paradigms at the same time.”
Foofah: Transforming Data By Example (2017, background): “[38] R. Singh and S. Gulwani.”
Bias reformulation for one-shot function induction (2014, background): “The work in this paper is directly inspired by recent advances in Programming Demonstration which use DSLs for various domains of interest (see [6, 17, 21]).”
NLyze: interactive programming by natural language for spreadsheet data analysis and manipulation (2014, background): “It would also be interesting to consider incorporating similarity matching techniques [3, 17] for column names and spread-sheet values and extending the lookup capability of NLyze to search over collections of web tables in addition to a user’s own tables (as in [35]).”
Automated feedback generation for introductory programming assignments (2012, methodology): “Program synthesis has been used recently for many applications such as synthesis of efficient low-level code [29, 38], data structure manipulations [34], inference of efficient synchronization in concurrent programs [42], snippets of excel macros [18, 33], relational data representations [19, 20] an”
Component-based synthesis for complex APIs (2017, background): “As a result, the applicability of component-based synthesis remains limited to domain-specific applications, such as bit-vector, string, or data-structure manipulations [7, 22, 38].”
Predicting a Correct Program in Programming by Example (2015, background): “The Boolean expression predicate (C1 = et∧· · ·∧Ck = et) for a candidate key of size k in the lookup transformation language [25] is another fixed-arity expression of arity k with independent values for the column predicates.”
FlashMeta: a framework for inductive program synthesis (2015, background): “…[22] Text extraction (cid:61) (cid:61) Kini and Gulwani [16] Text normalization = soft Barowy et al. [3] Table normalization = = Singh and Gulwani [33] Semantic text editing = = Harris and Gulwani [8] Table transformation = = Singh and Gulwani [32] Number transformation = = Andersen et al. [2]…”
Program Synthesis Using Natural Language (2015, background): “has included domains for manipulating strings [13, 48], numbers [49], and tables [21].”