Elamur Research⌕
☰
home / papers / 2017 / Program Synthesis

Program Synthesis

Paper · 2017 · Sumit Gulwani, Oleksandr Polozov and Rishabh Singh

Summary

This monograph is a survey and tutorial, not an experimental paper. It addresses program synthesis: automatically building programs from a specification of user intent, such as input-output examples, demonstrations, natural language or logical constraints. The authors organize the field along three dimensions: how intent is expressed, what program space is searched, and which search technique is used. They first review application areas, including data wrangling, graphics, code repair and suggestions, modeling, superoptimization and concurrent programming. They then present shared principles, such as reducing synthesis to second-order problems, oracle-guided loops, syntactic bias and optimization. Next they compare the main search families: enumerative, constraint-based and stochastic, the last including neural methods. A dedicated part covers programming by examples, which is directly relevant to data cleaning and transformation tasks. There are no new datasets or benchmark numbers. The value lies in a unified taxonomy and roadmap. Note: the supplied extract contained only the front matter and the table of contents, so this summary reflects the survey's structure rather than its detailed content.

Key points

  • Appeared in 2017 in volume 4 (issues 1–2, pages 1–119) of the journal Foundations and Trends in Programming Languages, DOI 10.1561/2500000010. Authors are from Microsoft Research and the University of Washington.
  • The survey covers seven application domains, with data wrangling listed first, which makes it useful for data-processing projects.
  • The four general principles are second-order problem reduction, oracle-guided synthesis, syntactic bias and optimization.
  • The search techniques covered are:
    • Enumerative: bidirectional and offline enumeration.
    • Constraint solving: component-based synthesis, solver-aided programming and inductive logic programming.
    • Stochastic: Metropolis-Hastings sampling, genetic programming, machine learning and neural program synthesis.
  • The programming-by-examples chapter covers version space algebra, deduction-based techniques and ambiguity resolution. It closes with a chapter on future work.

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

 Fields, topics and concepts

📚 Shelf 1The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 works

🧭 Topics 1Research subjects and languages the work is about.Code & programming languages · 168 works

Cite

Cite as Sumit Gulwani, Oleksandr Polozov and Rishabh Singh. 2017. Program Synthesis. Foundations and Trends in Programming Languages 4(1-2).

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

@inproceedings{gulwani2017program,
  title = {{Program Synthesis}},
  author = {Sumit Gulwani, Oleksandr Polozov and Rishabh Singh},
  booktitle = {Foundations and Trends in Programming Languages 4(1-2)},
  year = {2017},
  url = {https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf}
}

References

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

  1. Takuya Akiba, Kentaro Imajo, Hiroaki Iwami, Yoichi Iwata, Toshiki Kataoka, Naohiro Takahashi, Michał Moskal, and Nikhil Swamy. Calibrating research in program synthesis using 72,000 hours of programmer time. Microsoft Research, Redmond, WA, USA, Technical Report, 2013. find
  2. Miltiadis Allamanis, Earl T. Barr, Christian Bird, and Charles Sutton. Learning natural coding conventions. In Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, pages 281–293. ACM, 2014. find
  3. Rajeev Alur, Rastislav Bodík, Garvit Juniwal, Milo M. K. Martin, Mukund Raghothaman, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. Syntax-guided synthesis. In Formal Methods in Computer-Aided Design, FMCAD, pages 1–8, 2013. find
  4. Rajeev Alur, Pavol Cerný, and Arjun Radhakrishna. Synthesis through unification. In Proceedings of the 27th International Conference on Computer-Aided Verification (CAV), pages 163–179, 2015. find
  5. Rajeev Alur, Dana Fisman, Rishabh Singh, and Armando Solar-Lezama. Results and analysis of SyGuS-Comp’15. In Proceedings Fourth Workshop on Synthesis, SYNT, pages 3–26, 2015. find
  6. Rajeev Alur, Dana Fisman, Rishabh Singh, and Armando Solar-Lezama. SyGuS-Comp 2016: Results and analysis. In Proceedings of the Fifth Workshop on Synthesis, SYNT@CAV 2016, Toronto, Canada, July 17-18, 2016., pages 178–202, 2016. find
  7. Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. DeepCoder: Learning to write programs. CoRR, abs/1611.01989, 2016. find
  8. Sorav Bansal and Alex Aiken. Automatic generation of peephole superoptimizers. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2006, San Jose, CA, USA, October 21-25, 2006, pages 394–403, 2006. find
  9. Sorav Bansal and Alex Aiken. Binary translation using peephole superoptimizers. In 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2008, December 8-10, 2008, San Diego, California, USA, Proceedings, pages 177–192, 2008. find
  10. Daniel W. Barowy, Sumit Gulwani, Ted Hart, and Benjamin G. Zorn. FlashRelate: extracting relational data from semi-structured spreadsheets using examples. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, Portland, OR, USA, June 15-17, 2015, pages 2… find
  11. Clark Barrett, Pascal Fontaine, and Cesare Tinelli. The SMT-LIB Standard Version 2.6, 2010. find
  12. Gilles Barthe, Juan Manuel Crespo, Sumit Gulwani, César Kunz, and Mark Marron. From relational verification to SIMD loop synthesis. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’13, Shenzhen, China, February 23-27, 2013, pages 123–134, 2013. find
  13. Alan W Biermann. The inference of regular LISP programs from examples. IEEE transactions on Systems, Man, and Cybernetics, 8(8): 585–600, 1978. find
  14. James Bornholt and Emina Torlak. Synthesizing memory models from framework sketches and litmus tests. In Programming Languages Design and Implementation, 2017. find
  15. James Bornholt, Emina Torlak, Dan Grossman, and Luis Ceze. Optimizing synthesis with metasketches. In ACM SIGPLAN Notices, volume 51, pages 775–788. ACM, 2016. find
  16. Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, and Hang Li. Learning to rank: from pairwise approach to listwise approach. In ICML, 2007. References References find
  17. Pavol Cerný, Krishnendu Chatterjee, Thomas A. Henzinger, Arjun Radhakrishna, and Rohit Singh. Quantitative synthesis for concurrent programs. In Computer Aided Verification - 23rd International Conference, CAV 2011, Snowbird, UT, USA, July 14-20, 2011. Proceedings, pages 243–259, 2011. find
  18. Krishnendu Chatterjee, Thomas A. Henzinger, Barbara Jobstmann, and Rohit Singh. Measuring and synthesizing systems in probabilistic environments. J. ACM, 62(1):9:1–9:34, March 2015. ISSN 0004-5411. find
  19. Swarat Chaudhuri, Martin Clochard, and Armando Solar-Lezama. Bridging boolean and quantitative synthesis using smoothed proof search. SIGPLAN Not., 49(1):207–220, January 2014. ISSN 0362-1340. find
  20. Yves Chauvin and David E. Rumelhart. Backpropagation: theory, architectures, and applications. Psychology Press, 1995. find
  21. Salman Cheema, Sarah Buchanan, Sumit Gulwani, and Joseph J. LaViola Jr. A practical framework for constructing structured drawings. In IUI’14 19th International Conference on Intelligent User Interfaces, IUI’14, Haifa, Israel, February 24-27, 2014, pages 311–316, 2014. find
  22. Alvin Cheung, Armando Solar-Lezama, and Samuel Madden. Optimizing database-backed applications with query synthesis. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’13, Seattle, WA, USA, June 16-19, 2013, pages 3–14, 2013. find
  23. Ravi Chugh, Brian Hempel, Mitchell Spradlin, and Jacob Albers. Programmatic and direct manipulation, together at last. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2016, Santa Barbara, CA, USA, June 13-17, 2016, pages 341–354, 2016. find
  24. David Cossock and Tong Zhang. Subset ranking using regression. Learning Theory, 4005:605–619, 2006. find
  25. Allen Cypher, editor. Watch What I Do – Programming by Demonstration. MIT Press, Cambridge, MA, USA, 1993. find
  26. Loris D’Antoni, Roopsha Samanta, and Rishabh Singh. Qlose: Program Repair with Quantitative Objectives. In Computer Aided Verification (CAV). Springer-Verlag, 2016. find
  27. Luc De Raedt. Logical and Relational Learning. Springer Publishing Company, Incorporated, 1st edition, 2010. find
  28. Aditya Desai, Sumit Gulwani, Vineet Hingorani, Nidhi Jain, Amey Karkare, Mark Marron, Sailesh R., and Subhajit Roy. Program synthesis using natural language. In Proceedings of the 38th International Conference on Software Engineering (ICSE), pages 345–356, 2016. find
  29. Joshua Dunfield. A unified system of type refinements. PhD thesis, Air Force Research Laboratory, 2007. find
  30. Kevin Ellis and Sumit Gulwani. Learning to learn programs from examples: Going beyond program structure. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2017. find
  31. Yu Feng, Ruben Martins, Yuepeng Wang, Isil Dillig, and Thomas W. Reps. Component-based synthesis for complex APIs. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, 2017. find
  32. Cormac Flanagan. Hybrid type checking. In ACM Sigplan Notices, volume 41, pages 245–256. ACM, 2006. find
  33. Jonathan Frankle, Peter-Michael Osera, David Walker, and Steve Zdancewic. Example-directed synthesis: a type-theoretic interpretation. In ACM SIGPLAN Notices, volume 51, pages 802–815. ACM, 2016. find
  34. Tim Freeman and Frank Pfenning. Refinement types for ML. In Proceedings of the ACM SIGPLAN 1991 Conference on Programming Language Design and Implementation, PLDI ’91, pages 268–277, New York, NY, USA, 1991. ACM. . find
  35. Yoav Freund, Raj Iyer, Robert E. Schapire, and Yoram Singer. An efficient boosting algorithm for combining preferences. The Journal of machine learning research, 4:933–969, 2003. find
  36. Alexander L. Gaunt, Marc Brockschmidt, Rishabh Singh, Nate Kushman, Pushmeet Kohli, Jonathan Taylor, and Daniel Tarlow. TerpreT: A probabilistic programming language for program induction. CoRR, abs/1608.04428, 2016. find
  37. Khaled Ghédira. Constraint Satisfaction Problems: CSP Formalisms and Techniques. John Wiley & Sons, 2013. find
  38. Patrice Godefroid and Ankur Taly. Automated synthesis of symbolic instruction encodings from I/O samples. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 441–452. ACM, 2012. find
  39. Sally A. Goldman and Michael J. Kearns. On the complexity of teaching. Journal of Computer and System Sciences, 50:303–314, 1992. References References find
  40. Alex Graves, Greg Wayne, and Ivo Danihelka. Neural Turing machines. arXiv preprint arXiv:1410.5401, 2014. find
  41. C. Cordell Green. Application of theorem proving to problem solving. In IJCAI, pages 219–240, 1969. find
  42. Sumit Gulwani. Dimensions in program synthesis. In Proceedings of 10th International Conference on Formal Methods in Computer-Aided Design, FMCAD 2010, Lugano, Switzerland, October 20-23, page 1, 2010. find
  43. Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, January 26-28, 2011, pages 317–330, 2011.
  44. Sumit Gulwani. Programming by examples - and its applications in data wrangling. In Dependable Software Systems Engineering, pages 137–158. 2016. find
  45. Sumit Gulwani and Nebojsa Jojic. Program verification as probabilistic inference. In Proceedings of the 34th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2007, Nice, France, January 17-19, 2007, pages 277–289, 2007. find
  46. Sumit Gulwani and Mark Marron. NLyze: interactive programming by natural language for spreadsheet data analysis and manipulation. In International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22-27, 2014, pages 803–814, 2014. find
  47. Sumit Gulwani, Susmit Jha, Ashish Tiwari, and Ramarathnam Venkatesan. Synthesis of loop-free programs. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2011, San Jose, CA, USA, June 4-8, 2011, pages 62–73, 2011. find
  48. Sumit Gulwani, Vijay Anand Korthikanti, and Ashish Tiwari. Synthesizing geometry constructions. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2011, San Jose, CA, USA, June 4-8, 2011, pages 50–61, 2011. find
  49. Sumit Gulwani, William R. Harris, and Rishabh Singh. Spreadsheet data manipulation using examples. Commun. ACM, 55(8):97–105, 2012. find
  50. Sumit Gulwani, Mikaël Mayer, Filip Niksic, and Ruzica Piskac. StriSynth: Synthesis for live programming. In 37th IEEE/ACM International Conference on Software Engineering, ICSE, pages 701–704, 2015. find
  51. Tihomir Gvero, Viktor Kuncak, Ivan Kuraj, and Ruzica Piskac. Complete completion using types and weights. In ACM SIGPLAN Notices, volume 48, pages 27–38. ACM, 2013. find
  52. William R. Harris and Sumit Gulwani. Spreadsheet table transformations from examples. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2011, San Jose, CA, USA, June 4-8, 2011, pages 317–328, 2011. find
  53. Brian Hempel and Ravi Chugh. Semi-automated SVG programming via direct manipulation. In Proceedings of the 29th Annual Symposium on User Interface Software and Technology, UIST 2016, Tokyo, Japan, October 16-19, 2016, pages 379–390, 2016. find
  54. Ralf Herbrich, Thore Graepel, and Klaus Obermayer. Large margin rank boundaries for ordinal regression. Advances in Neural Information Processing Systems, pages 115–132, 1999. find
  55. Ralf Herbrich, Tom Minka, and Thore Graepel. TrueSkill™: A Bayesian skill rating system. In Advances in neural information processing systems, pages 569–576, 2006. find
  56. John H. Holland. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press, 1975. find
  57. Shachar Itzhaky, Sumit Gulwani, Neil Immerman, and Mooly Sagiv. A simple inductive synthesis methodology and its applications. In Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2010, October 17-21, 2010, Reno/Tahoe,… find
  58. Susmit Jha and Sanjit A. Seshia. A Theory of Formal Synthesis via Inductive Learning. ArXiv e-prints, May 2015. find
  59. Susmit Jha, Sumit Gulwani, Sanjit A. Seshia, and Ashish Tiwari. Oracle-guided component-based program synthesis. In 2010 ACM/IEEE 32nd International Conference on Software Engineering (ICSE), volume 1, pages 215–224. IEEE, 2010. find
  60. Barbara Jobstmann, Andreas Griesmayer, and Roderick Bloem. Program repair as a game. In Computer Aided Verification (CAV), pages 226–238. Springer-Verlag, 2005. find
  61. Colin G. Johnson. Genetic programming with fitness based on model checking. In European Conference on Genetic Programming, pages 114–124. Springer, 2007. References References find
  62. Vladimir Jojic, Sumit Gulwani, and Nebojsa Jojic. Probabilistic inference of programs from input/output examples. Technical Report MSR-TR-2006-103, Microsoft Research, 2006. find
  63. Rajeev Joshi, Greg Nelson, and Keith H. Randall. Denali: A goal-directed superoptimizer. In Proceedings of the 2002 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Berlin, Germany, June 17-19, 2002, pages 304–314, 2002. find
  64. Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. In NIPS, pages 190–198, 2015. find
  65. Garvit Juniwal, Alexandre Donzé, Jeff C. Jensen, and Sanjit A. Seshia. CPSGrader: Synthesizing temporal logic testers for auto-grading an embedded systems laboratory. In EMSOFT, pages 24:1–24:10, 2014. find
  66. Łukasz Kaiser and Ilya Sutskever. Neural GPUs learn algorithms. arXiv preprint arXiv:1511.08228, 2015. find
  67. Susumu Katayama. MagicHaskeller on the Web: Automated programming as a service. In Haskell Symposium, 2013. find
  68. Gal Katz and Doron A. Peled. Genetic programming and model checking: Synthesizing new mutual exclusion algorithms. In Automated Technology for Verification and Analysis, 6th International Symposium, ATVA 2008, Seoul, Korea, October 20-23, 2008. Proceedings, pages 33–47, 2008. find
  69. Ross D. King, Stephen Muggleton, Ashwin Srinivasan, and M.J. Sternberg. Structure-activity relationships derived by machine learning: The use of atoms and their bond connectivities to predict mutagenicity by inductive logic programming. Proceedings of the National Academy of Sciences, 93(1):438–442,… find
  70. A. N. Kolmogorov. Zur deutung der intuitionistischen logik. Math. Zeitschr, 35:58–365, 1932. find
  71. John R. Koza. Hierarchical genetic algorithms operating on populations of computer programs. In Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI), pages 768–774. Morgan Kaufmann Publishers Inc., 1989. find
  72. John R. Koza. Genetic programming - on the programming of computers by means of natural selection. Complex adaptive systems. MIT Press, 1993. find
  73. John R Koza. Genetic programming as a means for programming computers by natural selection. Statistics and Computing, 4(2):87–112, 1994. find
  74. Shriram Krishnamurthi. Educational pearl: Automata via macros. Journal of Functional Programming, 16(03):253–267, 2006. find
  75. Michael Kuperstein, Martin T. Vechev, and Eran Yahav. Automatic inference of memory fences. In Proceedings of 10th International Conference on Formal Methods in Computer-Aided Design, FMCAD 2010, Lugano, Switzerland, October 20-23, pages 111–119, 2010. find
  76. Karol Kurach, Marcin Andrychowicz, and Ilya Sutskever. Neural random-access machines. arXiv preprint arXiv:1511.06392, 2015. find
  77. Tessa A. Lau, Pedro Domingos, and Daniel S. Weld. Version space algebra and its application to programming by demonstration. In Proceedings of the 17th International Conference on Machine Learning (ICML), pages 527–534, 2000. find
  78. Vu Le and Sumit Gulwani. FlashExtract: a framework for data extraction by examples. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, Edinburgh, United Kingdom - June 09 - 11, 2014, page 55, 2014. find
  79. Vu Le, Sumit Gulwani, and Zhendong Su. SmartSynth: synthesizing smartphone automation scripts from natural language. In The 11th Annual International Conference on Mobile Systems, Applications, and Services, MobiSys’13, Taipei, Taiwan, June 25-28, 2013, pages 193–206, 2013. find
  80. Claire Le Goues, ThanhVu Nguyen, Stephanie Forrest, and Westley Weimer. Genprog: A generic method for automatic software repair. IEEE Transactions on Software Engineering, 38(1):54–72, 2012. find
  81. Alan Leung, John Sarracino, and Sorin Lerner. Interactive parser synthesis by example. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, Portland, OR, USA, June 15-17, 2015, pages 565–574, 2015. find
  82. Percy Liang, Michael I. Jordan, and Dan Klein. Learning programs: A hierarchical Bayesian approach. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 639–646, 2010. find
  83. Francesca A. Lisi. Building rules on top of ontologies for the Semantic Web with inductive logic programming. Theory and Practice of Logic Programming, 8(03):271–300, 2008. find
  84. David Mandelin, Lin Xu, Rastislav Bodík, and Doug Kimelman. Jungloid mining: helping to navigate the API jungle. In PLDI, pages 48–61, 2005. find
  85. Zohar Manna and Richard J. Waldinger. Toward automatic program synthesis. Commun. ACM, 14(3):151–165, 1971. References References find
  86. Zohar Manna and Richard J. Waldinger. Knowledge and reasoning in program synthesis. Artif. Intell., 6(2):175–208, 1975. find
  87. Henry Massalin. Superoptimizer - A look at the smallest program. In Proceedings of the Second International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS II), Palo Alto, California, USA, October 5-8, 1987., pages 122–126, 1987. find
  88. Mikaël Mayer, Gustavo Soares, Maxim Grechkin, Vu Le, Mark Marron, Oleksandr Polozov, Rishabh Singh, Ben Zorn, and Sumit Gulwani. User interaction models for disambiguation in programming by example. In 28th ACM User Interface Software and Technology Symposium, pages 291–301. ACM, 2015. find
  89. Aditya Krishna Menon, Omer Tamuz, Sumit Gulwani, Butler W. Lampson, and Adam Kalai. A machine learning framework for programming by example. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, pages 187–195, 2013. find
  90. Alon Mishne, Sharon Shoham, and Eran Yahav. Typestate-based semantic code search over partial programs. In OOPSLA, pages 997–1016, 2012. find
  91. Tom M. Mitchell. Generalization as search. Artificial intelligence, 18(2): 203–226, 1982. find
  92. Stephen Muggleton. Inductive logic programming. New generation computing, 8(4):295–318, 1991. find
  93. Stephen Muggleton. Inverse entailment and Progol. New generation computing, 13(3-4):245–286, 1995. find
  94. Stephen Muggleton and Wray Buntine. Machine invention of first-order predicates by inverting resolution. In Proceedings of the fifth international conference on machine learning, pages 339–352, 1992. find
  95. Stephen Muggleton, Ross D. King, and Michael J.E. Stenberg. Protein secondary structure prediction using logic-based machine learning. Protein Engineering, 5(7):647–657, 1992. find
  96. Stephen Muggleton, Dianhuan Lin, Niels Pahlavi, and Alireza Tamaddoni-Nezhad. Meta-interpretive learning: application to grammatical inference. Machine Learning, 94(1):25–49, 2014. find
  97. Stephen Muggleton, Dianhuan Lin, and Alireza Tamaddoni-Nezhad. Meta-interpretive learning of higher-order dyadic Datalog: Predicate invention revisited. Machine Learning, 100(1):49–73, 2015. find
  98. Arvind Neelakantan, Quoc V. Le, and Ilya Sutskever. Neural programmer: Inducing latent programs with gradient descent. arXiv preprint arXiv:1511.04834, 2015. find
  99. Hoang Duong Thien Nguyen, Dawei Qi, Abhik Roychoudhury, and Satish Chandra. SemFix: program repair via semantic analysis. In 35th International Conference on Software Engineering, ICSE, pages 772–781, 2013. find
  100. Robert P. Nix. Editing by example. In Conference Record of the Eleventh Annual ACM Symposium on Principles of Programming Languages, Salt Lake City, Utah, USA, January 1984, pages 186–195, 1984. find
  101. Aditya V. Nori, Sherjil Ozair, Sriram K. Rajamani, and Deepak Vijay-keerthy. Efficient synthesis of probabilistic programs. In ACM SIGPLAN Notices, volume 50, pages 208–217. ACM, 2015. find
  102. Peter-Michael Osera and Steve Zdancewic. Type-and-example-directed program synthesis. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 619–630. ACM, 2015. find
  103. Pavel Panchekha and Emina Torlak. Automated reasoning for web page layout. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2016, pages 181–194, 2016. find
  104. Pavel Panchekha, Alex Sanchez-Stern, James R. Wilcox, and Zachary Tatlock. Automatically improving accuracy for floating point expressions. ACM SIGPLAN Notices, 50(6):1–11, 2015. find
  105. Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. CoRR, abs/1611.01855, 2016.
  106. Daniel Perelman, Sumit Gulwani, Thomas Ball, and Dan Grossman. Type-directed completion of partial expressions. In ACM SIGPLAN Notices, volume 47, pages 275–286. ACM, 2012. find
  107. Stuart Pernsteiner, Calvin Loncaric, Emina Torlak, Zachary Tatlock, Xi Wang, Michael D. Ernst, and Jonathan Jacky. Investigating Safety of a Radiotherapy Machine Using System Models with Pluggable Checkers, pages 23–41. Springer International Publishing, Cham, 2016. . find
  108. Phitchaya Mangpo Phothilimthana, Tikhon Jelvis, Rohin Shah, Nishant Totla, Sarah Chasins, and Rastislav Bodik. Chlorophyll: Synthesis-aided compiler for low-power spatial architectures. In ACM SIGPLAN Notices, volume 49, pages 396–407. ACM, 2014. References References find
  109. Phitchaya Mangpo Phothilimthana, Aditya Thakur, Rastislav Bodík, and Dinakar Dhurjati. Scaling up superoptimization. In Proceedings of the 21st International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 297–310, 2016. find
  110. Amir Pnueli and Roni Rosner. On the synthesis of a reactive module. In POPL, pages 179–190. ACM, 1989. find
  111. Nadia Polikarpova, Ivan Kuraj, and Armando Solar-Lezama. Program synthesis from polymorphic refinement types. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 522–538. ACM, 2016. find
  112. Nadia Polikarpova, Jean Yang, Shachar Itzhaky, and Armando Solar-Lezama. Type-driven repair for information flow security. arXiv preprint arXiv:1607.03445, 2016. — [arXiv:1607.03445](https://arxiv.org/abs/1607.03445) find
  113. Oleksandr Polozov and Sumit Gulwani. FlashMeta: a framework for inductive program synthesis. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2015, pages 107–126, 2015. find
  114. Veselin Raychev, Martin Vechev, and Eran Yahav. Code completion with statistical language models. In ACM SIGPLAN Notices, volume 49, pages 419–428. ACM, 2014. find
  115. Veselin Raychev, Pavol Bielik, Martin Vechev, and Andreas Krause. Learning programs from noisy data. In ACM SIGPLAN Notices, volume 51, pages 761–774. ACM, 2016. find
  116. Mohammad Raza and Sumit Gulwani. Automated data extraction using predictive program synthesis. In AAAI, 2017. find
  117. Mohammad Raza, Sumit Gulwani, and Natasa Milic-Frayling. Compositional program synthesis from natural language and examples. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI), pages 792–800, 2015. find
  118. Scott Reed and Nando de Freitas. Neural programmer-interpreters. arXiv preprint arXiv:1511.06279, 2015. find
  119. Wolfgang Reisig. Petri nets: an introduction, volume 4. Springer Science & Business Media, 2012. find
  120. Sebastian Riedel, Matko Bošnjak, and Tim Rocktäschel. Programming with a differentiable Forth interpreter. arXiv preprint arXiv:1605.06640, 2016. find
  121. Patrick M. Rondon, Ming Kawaguci, and Ranjit Jhala. Liquid types. In ACM SIGPLAN Notices, volume 43, pages 159–169. ACM, 2008. find
  122. Jose C.A. Santos, Houssam Nassif, David Page, Stephen Muggleton, and Michael J.E. Sternberg. Automated identification of protein-ligand interaction features using inductive logic programming: a hexose binding case study. BMC bioinformatics, 13(1):1, 2012. find
  123. Eric Schkufza, Rahul Sharma, and Alex Aiken. Stochastic superoptimization. In ACM SIGARCH Computer Architecture News, volume 41, pages 305–316. ACM, 2013. find
  124. Eric Schkufza, Rahul Sharma, and Alex Aiken. Stochastic superoptimization. In Architectural Support for Programming Languages and Operating Systems, ASPLOS ’13, pages 305–316, 2013. find
  125. David E. Shaw, William R. Swartout, and C. Cordell Green. Inferring LISP programs from examples. In Proceedings of the 4th International Joint Conference on Artificial Intelligence - Volume 1, pages 260–267. Morgan Kaufmann Publishers Inc., 1975. find
  126. Rishabh Singh and Sumit Gulwani. Synthesizing number transformations from input-output examples. In Computer Aided Verification - 24th International Conference, CAV 2012, pages 634–651, 2012. find
  127. Rishabh Singh and Sumit Gulwani. Learning semantic string transformations from examples. Proceedings of the VLDB Endowment, 5(8): 740–751, 2012. find
  128. Rishabh Singh and Sumit Gulwani. Predicting a correct program in programming by example. In CAV, pages 398–414, 2015. find
  129. Rishabh Singh and Sumit Gulwani. Transforming spreadsheet data types using examples. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 343–356, 2016. find
  130. Rishabh Singh, Sumit Gulwani, and Armando Solar-Lezama. Automatic feedback generation for introductory programming assignments. In Proceedings of Programming Language Design and Implementation (PLDI), pages 15–26, 2013. find
  131. David Canfield Smith. Pygmalion: A Creative Programming Environment. PhD thesis, Stanford University, Stanford, CA, USA, 1975. find
  132. Armando Solar-Lezama. Program synthesis by sketching. ProQuest, 2008. References References find
  133. Saurabh Srivastava, Sumit Gulwani, and Jeffrey S. Foster. From program verification to program synthesis. In Proceedings of the 37th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2010, Madrid, Spain, January 17-23, 2010, pages 313–326, 2010. find
  134. Saurabh Srivastava, Sumit Gulwani, Swarat Chaudhuri, and Jeffrey S. Foster. Path-based inductive synthesis for program inversion. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2011, San Jose, CA, USA, June 4-8, 2011, pages 492–503, 2011. find
  135. Saurabh Srivastava, Sumit Gulwani, and Jeffrey S. Foster. Template-based program verification and program synthesis. International Journal on Software Tools for Technology Transfer (STTT), 15(5-6):497–518, 2013. find
  136. Michael J.E. Sternberg, Alireza Tamaddoni-Nezhad, Victor I. Lesk, Emily Kay, Paul G. Hitchen, Adrian Cootes, Lieke B. van Alphen, Marc P. Lamoureux, Harold C. Jarrell, Christopher J. Rawlings, et al. Gene function hypotheses for the campylobacter jejuni glycome generated by a logic-based approach. J… find
  137. Phillip D. Summers. A methodology for LISP program construction from examples. Journal of the ACM (JACM), 24(1):161–175, 1977. find
  138. Alireza Tamaddoni-Nezhad, Ghazal Afroozi Milani, Alan Raybould, Stephen Muggleton, and David A. Bohan. Construction and validation of food webs using logic-based machine learning and text mining. Advances in Ecological Research, 49:225–289, 2013. find
  139. Emina Torlak and Rastislav Bodik. Growing solver-aided languages with Rosette. In Proceedings of the 2013 ACM international symposium on New ideas, new paradigms, and reflections on programming & software, pages 135–152. ACM, 2013. find
  140. Emina Torlak and Rastislav Bodik. A lightweight symbolic virtual machine for solver-aided host languages. In ACM SIGPLAN Notices, volume 49, pages 530–541. ACM, 2014. find
  141. Abhishek Udupa, Arun Raghavan, Jyotirmoy V. Deshmukh, Sela Mador-Haim, Milo M.K. Martin, and Rajeev Alur. TRANSIT: Specifying protocols with concolic snippets. In Proceedings of the 34th annual ACM SIGPLAN conference on Programming Languages Design and Implementation (PLDI), pages 287–296, 2013. find
  142. Richard Uhler and Nirav Dave. Smten: automatic translation of high-level symbolic computations into SMT queries. In International Conference on Computer Aided Verification, pages 678–683. Springer, 2013. find
  143. Martin T. Vechev, Eran Yahav, and Greta Yorsh. Abstraction-guided synthesis of synchronization. In Proceedings of the 37th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2010, Madrid, Spain, January 17-23, 2010, pages 327–338, 2010. find
  144. Richard J. Waldinger and Richard C. T. Lee. PROW: A step toward automatic program writing. In IJCAI, pages 241–252, 1969. find
  145. Henry S. Warren. Hacker’s delight. Pearson Education, 2013. find
  146. Westley Weimer, ThanhVu Nguyen, Claire Le Goues, and Stephanie Forrest. Automatically finding patches using genetic programming. In 31st International Conference on Software Engineering, ICSE 2009, May 16-24, 2009, Vancouver, Canada, Proceedings, pages 364–374, 2009. find
  147. Konstantin Weitz, Doug Woos, Emina Torlak, Michael D. Ernst, Arvind Krishnamurthy, and Zachary Tatlock. Scalable verification of border gateway protocol configurations with an SMT solver. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languag… find
  148. Fen Xia, Tie-Yan Liu, Jue Wang, Wensheng Zhang, and Hang Li. Listwise approach to learning to rank: theory and algorithm. In ICML, 2008. find
  149. Navid Yaghmazadeh, Christian Klinger, Isil Dillig, and Swarat Chaudhuri. Synthesizing transformations on hierarchically structured data. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2016, Santa Barbara, CA, USA, June 13-17, 2016, pages 508… find
  150. Xiaofeng Yang, Jian Su, Jun Lang, Chew Lim Tan, Ting Liu, and Sheng Li. An entity-mention model for coreference resolution with inductive logic programming. In ACL, pages 843–851, 2008.
  151. Hongyu Zhang, Anuj Jain, Gaurav Khandelwal, Chandrashekhar Kaushik, Scott Ge, and Wenxiang Hu. Bing developer assistant: improving developer productivity by recommending sample code. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pages 956… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/gulwani-2017-program-synthesis/