Article

Synthesizing number transformations from input-output examples

Authors:

Sumit GulwaniAuthors Info & Claims

CAV'12: Proceedings of the 24th international conference on Computer Aided Verification

Pages 634 - 651

https://doi.org/10.1007/978-3-642-31424-7_44

Published: 07 July 2012 Publication History

Abstract

Numbers are one of the most widely used data type in programming languages. Number transformations like formatting and rounding present a challenge even for experienced programmers as they find it difficult to remember different number format strings supported by different programming languages. These transformations present an even bigger challenge for end-users of spreadsheet systems like Microsoft Excel where providing such custom format strings is beyond their expertise. In our extensive case study of help forums of many programming languages and Excel, we found that both programmers and end-users struggle with these number transformations, but are able to easily express their intent using input-output examples.

In this paper, we present a framework that can learn such number transformations from very few input-output examples. We first describe an expressive number transformation language that can model these transformations, and then present an inductive synthesis algorithm that can learn all expressions in this language that are consistent with a given set of examples. We also present a ranking scheme of these expressions that enables efficient learning of the desired transformation from very few examples. By combining our inductive synthesis algorithm for number transformations with an inductive synthesis algorithm for syntactic string transformations, we are able to obtain an inductive synthesis algorithm for manipulating data types that have numbers as a constituent sub-type such as date, unit, and time. We have implemented our algorithms as an Excel add-in and have evaluated it successfully over several benchmarks obtained from the help forums and the Excel product team.

References

[1]

Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Computers 35(8), 677-691 (1986).

Digital Library

[2]

Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: POPL (1977).

Digital Library

[3]

Cypher, A. (ed.): Watch What I Do - Programming by Demonstration. MIT Press (1993).

Digital Library

[4]

Gualtieri, M.: Deputize end-user developers to deliver business agility and reduce costs. Forrester Report for Application Development and Program Management Professionals (April 2009).

[5]

Gulwani, S.: Dimensions in program synthesis. In: PPDP (2010).

Digital Library

[6]

Gulwani, S.: Automating string processing in spreadsheets using input-output examples. In: POPL (2011).

Digital Library

[7]

Gulwani, S.: Synthesis from examples. In: WAMBSE (Workshop on Advances in Model-Based Software Engineering) Special Issue, Infosys Labs Briefings, vol. 10(2) (2012).

[8]

Gulwani, S., Harris, W.R., Singh, R.: Spreadsheet data manipulation using examples. Communications of the ACM (to appear, 2012).

Digital Library

[9]

Gulwani, S., Jha, S., Tiwari, A., Venkatesan, R.: Synthesis of loop-free programs. In: PLDI (2011).

Digital Library

[10]

Gulwani, S., Korthikanti, V.A., Tiwari, A.: Synthesizing geometry constructions. In: PLDI, pp. 50-61 (2011).

Digital Library

[11]

Gvero, T., Kuncak, V., Piskac, R.: Interactive Synthesis of Code Snippets. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 418-423. Springer, Heidelberg (2011).

Digital Library

[12]

Harris, W.R., Gulwani, S.: Spreadsheet table transformations from examples. In: PLDI, pp. 317-328 (2011).

Digital Library

[13]

Itzhaky, S., Gulwani, S., Immerman, N., Sagiv, M.: A simple inductive synthesis methodology and its applications. In: OOPSLA (2010).

Digital Library

[14]

Jha, S., Gulwani, S., Seshia, S., Tiwari, A.: Oracle-guided component-based program synthesis. In: ICSE (2010).

Digital Library

[15]

Kandel, S., Paepcke, A., Hellerstein, J., Heer, J.: Wrangler: Interactive visual specification of data transformation scripts. In: CHI (2011).

Digital Library

[16]

Lau, T.: Why PBD systems fail: Lessons learned for usable AI. In: CHI Workshop on Usable AI (2008).

[17]

Lau, T., Wolfman, S., Domingos, P., Weld, D.: Programming by demonstration using version space algebra. Machine Learning 53(1-2), 111-156 (2003).

Digital Library

[18]

Miller, R.C., Myers, B.A.: Interactive simultaneous editing of multiple text regions. In: USENIX Annual Technical Conference (2001).

Digital Library

[19]

Perelman, D., Gulwani, S., Ball, T., Grossman, D.: Type-directed completion of partial expressions. In: PLDI (2012).

Digital Library

[20]

Scaffidi, C., Myers, B.A., Shaw, M.: Topes: reusable abstractions for validating data. In: ICSE, pp. 1-10 (2008).

Digital Library

[21]

Singh, R., Gulwani, S.: Learning Semantic String Transformations from Examples. PVLDB 5(8), 740-751 (2012), http://vldb.org/pvldp/vol5/p740_rishabhsingh_vldp2012.pdf

Digital Library

[22]

Singh, R., Gulwani, S.: Synthesizing number transformations from input-output examples. Technical Report MSR-TR-2012-42 (April 2012).

[23]

Singh, R., Gulwani, S., Rajamani, S.: Automatically generating algebra problems. In: AAAI (to appear, 2012).

[24]

Singh, R., Solar-Lezama, A.: Synthesizing data structure manipulations from storyboards. In: SIGSOFT FSE, pp. 289-299 (2011).

Digital Library

[25]

Solar-Lezama, A., Jones, C.G., Bodík, R.: Sketching concurrent data structures. In: PLDI, pp. 136-148 (2008).

Digital Library

[26]

Solar-Lezama, A., Rabbah, R.M., Bodík, R., Ebcioglu, K.: Programming by sketching for bit-streaming programs. In: PLDI, pp. 281-294 (2005).

Digital Library

[27]

Srivastava, S., Gulwani, S., Chaudhuri, S., Foster, J.S.: Path-based inductive synthesis for program inversion. In: PLDI (2011).

Digital Library

Cited By

Zhou XBodik RCheung AWang CJhala RDillig I(2022)Synthesizing analytical SQL queries from computation demonstrationProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523712(168-182)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523712
Wang JSung CRaghothaman MWang C(2021)Data-Driven Synthesis of Provably Sound Side Channel AnalysesProceedings of the 43rd International Conference on Software Engineering10.1109/ICSE43902.2021.00079(810-822)Online publication date: 22-May-2021
https://dl.acm.org/doi/10.1109/ICSE43902.2021.00079
Liu BDong WZhang YWang DLiu JWang SNguyen T(2020)Boosting component-based synthesis with control structure recommendationProceedings of the 1st ACM SIGSOFT International Workshop on Representation Learning for Software Engineering and Program Languages10.1145/3416506.3423579(19-28)Online publication date: 8-Nov-2020
https://dl.acm.org/doi/10.1145/3416506.3423579
Show More Cited By

Recommendations

Spreadsheet table transformations from examples
PLDI '11: Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation

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 ...
Synthesizing data structure transformations from input-output examples
PLDI '15

We present a method for example-guided synthesis of functional programs over recursive data structures. Given a set of input-output examples, our method synthesizes a program in a functional language with higher-order combinators like map and fold. The ...
Learning syntactic program transformations from examples
ICSE '17: Proceedings of the 39th International Conference on Software Engineering

Automatic program transformation tools can be valuable for programmers to help them with refactoring tasks, and for Computer Science students in the form of tutoring systems that suggest repairs to programming assignments. However, manually creating ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CAV'12: Proceedings of the 24th international conference on Computer Aided Verification

July 2012

789 pages

ISBN:9783642314230

Editors:
P. Madhusudan
Dept. of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL
,
Sanjit A. Seshia
Dept. of Electrical Engineering and Computer Science, University of California, Berkeley, Berkeley, CA

Sponsors

NEC Labs: NEC Labs
IBMR: IBM Research
Intel: Intel
Microsoft Research: Microsoft Research

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 07 July 2012

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou XBodik RCheung AWang CJhala RDillig I(2022)Synthesizing analytical SQL queries from computation demonstrationProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523712(168-182)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523712
Wang JSung CRaghothaman MWang C(2021)Data-Driven Synthesis of Provably Sound Side Channel AnalysesProceedings of the 43rd International Conference on Software Engineering10.1109/ICSE43902.2021.00079(810-822)Online publication date: 22-May-2021
https://dl.acm.org/doi/10.1109/ICSE43902.2021.00079
Liu BDong WZhang YWang DLiu JWang SNguyen T(2020)Boosting component-based synthesis with control structure recommendationProceedings of the 1st ACM SIGSOFT International Workshop on Representation Learning for Software Engineering and Program Languages10.1145/3416506.3423579(19-28)Online publication date: 8-Nov-2020
https://dl.acm.org/doi/10.1145/3416506.3423579
Martins RChen JChen YFeng YDillig I(2019)TrinityProceedings of the VLDB Endowment10.14778/3352063.335209812:12(1914-1917)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.14778/3352063.3352098
Miltner AGulwani SLe VLeung ARadhakrishna ASoares GTiwari AUdupa A(2019)On the fly synthesis of edit suggestionsProceedings of the ACM on Programming Languages10.1145/33605693:OOPSLA(1-29)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360569
Fedyukovich GGupta A(2019)Functional Synthesis with ExamplesPrinciples and Practice of Constraint Programming10.1007/978-3-030-30048-7_32(547-564)Online publication date: 30-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-30048-7_32
Varma PRé C(2018)SnubaProceedings of the VLDB Endowment10.14778/3291264.329126812:3(223-236)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.14778/3291264.3291268
Raza MGulwani SSingh SMarkovitch S(2017)Automated data extraction using predictive program synthesisProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298239.3298368(882-890)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3298239.3298368
Ellis KGulwani S(2017)Learning to learn programs from examplesProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3172077.3172115(1638-1645)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3172077.3172115
Leung ALerner SRosu GDi Penta MNguyen T(2017)Parsimony: an IDE for example-guided synthesis of lexers and parsersProceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering10.5555/3155562.3155663(815-825)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.5555/3155562.3155663
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents