Program synthesis using conflict-driven learning
Open accessAbstract
We propose a new conflict-driven program synthesis technique that is capable of learning from past mistakes. Given a spurious program that violates the desired specification, our synthesis algorithm identifies the root cause of the conflict and learns new lemmas that can prevent similar mistakes in the future. Specifically, we introduce the notion of equivalence modulo conflict and show how this idea can be used to learn useful lemmas that allow the synthesizer to prune large parts of the search space. We have implemented a general-purpose CDCL-style program synthesizer called Neo and evaluate it in two different application domains, namely data wrangling in R and functional programming over lists. Our experiments demonstrate the substantial benefits of conflict-driven learning and show that Neo outperforms two state-of-the-art synthesis tools, Morpheus and Deepcoder, that target these respective domains.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Neo inherently requires SMT encoded properties for domain specific functions.
“Neo inherently requires SMT encoded properties for domain specific functions (i.e. its background knowledge).”
From Learning programs by learning from failures (2021) · cites this paper as Feng et al. 2018
Neo synthesises non-recursive programs using SMT encoded properties and a three staged loop.
“Neo (Feng et al. 2018) synthesises non-recursive programs using SMT encoded properties and a three staged loop.”
From Learning programs by learning from failures (2021) · cites this paper as Feng et al. 2018
Neo is not guaranteed to synthesise optimal (textually minimal) programs.
“Neo cannot synthesise recursive programs, nor is it guaranteed to synthesise optimal (textually minimal) programs.”
From Learning programs by learning from failures (2021) · cites this paper as Feng et al. 2018
Neo can fail to detect inconsistency with the examples, in which case no programs get pruned.
“As it typically uses over-approximate properties, Neo can fail to detect inconsistency with the examples, in which case no programs get pruned.”
From Learning programs by learning from failures (2021) · cites this paper as Feng et al. 2018
Neo cannot synthesise recursive programs.
“Neo cannot synthesise recursive programs, nor is it guaranteed to synthesise optimal (textually minimal) programs.”
From Learning programs by learning from failures (2021) · cites this paper as Feng et al. 2018
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Sequence to Sequence Learning with Neural Networks
Sutskever, I., Vinyals, O., & Le, Q. V. (2014) · arXiv · doi:10.48550/arxiv.1409.3215 · Cited by 17,766 · see citing works
de Moura, L., & Bjørner, N. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78800-3_24 · Cited by 6,595 · see citing works
GRASP: a search algorithm for propositional satisfiability
Marques-Silva, J. P., & Sakallah, K. A. (1999) · IEEE Transactions on Computers · doi:10.1109/12.769433 · Cited by 1,378 · see citing works
Automating string processing in spreadsheets using input-output examples
Gulwani, S. (2011) · ACM-SIGACT Symposium on Principles of Programming Languages · doi:10.1145/1926385.1926423 · Cited by 1,039 · see citing works
Combinatorial sketching for finite programs
Solar-Lezama, A., Tancau, L., Bodík, R., Seshia, S., & Saraswat, V. (2006) · ASPLOS XII · doi:10.1145/1168857.1168907 · Cited by 922 · see citing works
Frontiers in Artificial Intelligence and Applications
To, W., Tryfonas, T., & FARTHING, D. W. (2009) · IOS Press eBooks · Cited by 706 · see citing works
Efficient Conflict Driven Learning in a Boolean Satisfiability Solver
Zhang, L., Madigan, C. F., Moskewicz, M. H., & Malik, S. (2001) · Cited by 682 · see citing works
Alur, R., Bodik, R., Juniwal, G., Martin, M. M. K., Raghothaman, M., Seshia, S. A., Singh, R., Solar-Lezama, A., Torlak, E., & Udupa, A. (2013) · 2013 Formal Methods in Computer-Aided Design · doi:10.1109/fmcad.2013.6679385 · Cited by 656 · see citing works
DeepCoder: Learning to Write ProgramsPreprint
Balog, M., Gaunt, A. L., Brockschmidt, M., Nowozin, S., & Tarlow, D. (2016) · International Conference on Learning Representations · doi:10.48550/arxiv.1611.01989 · Cited by 641 · see citing works
Automating string processing in spreadsheets using input-output examples
Gulwani, S. (2011) · ACM SIGPLAN Notices · doi:10.1145/1925844.1926423 · Cited by 581 · see citing works
Code completion with statistical language models
Raychev, V., Vechev, M., & Yahav, E. (2014) · Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/2594291.2594321 · Cited by 555 · see citing works
The Sat4j library, release 2.2
Berre, D. L., & Parrain, A. (2010) · Journal on Satisfiability Boolean Modeling and Computation · doi:10.3233/sat190075 · Cited by 455 · see citing works
Mandelin, D., Xu, L., Bodík, R., & Kimelman, D. (2005) · ACM SIGPLAN Notices · doi:10.1145/1064978.1065018 · Cited by 389 · see citing works
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 365 · see citing works
Conflict-Driven Clause Learning SAT Solvers
Marques-Silva, J. P., Lynce, I., & Sharad, M. (2009) · Frontiers in artificial intelligence and applications · doi:10.3233/978-1-58603-929-5-131 · Cited by 334 · see citing works
DPLL(T): Fast Decision Procedures
Ganzinger, H., Hagen, G. E., Nieuwenhuis, R., Oliveras, A., & Tinelli, C. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27813-9_14 · Cited by 326 · see citing works
Program synthesis by sketching
Bodík, R., & Solar-Lezama, A. (2008) · Cited by 319 · see citing works
SQLizer: query synthesis from natural language
Yaghmazadeh, N., Wang, Y., Dillig, I., & Dillig, T. (2017) · Proceedings of the ACM on Programming Languages · doi:10.1145/3133887 · Cited by 284 · see citing works
Self-citationMandelin, D., Xu, L., Bodík, R., & Kimelman, D. (2005) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/1065010.1065018 · Cited by 261 · see citing works
Synthesizing data structure transformations from input-output examples
Feser, J., Chaudhuri, S., & Dillig, I. (2015) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/2737924.2737977 · Cited by 250 · see citing works
Self-citationSynthesis of loop-free programs
Gulwani, S., Jha, S., Tiwari, A., & Venkatesan, R. (2011) · ACM SIGPLAN Notices · doi:10.1145/1993316.1993506 · Cited by 246 · see citing works
Synthesis of loop-free programs
Gulwani, S., Jha, S., Tiwari, A., & Venkatesan, R. (2011) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/1993498.1993506 · Cited by 201 · see citing works
Program synthesis from polymorphic refinement types
Polikarpova, N., Kuraj, I., & Solar-Lezama, A. (2016) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/2908080.2908093 · Cited by 189 · see citing works
The Sketching Approach to Program Synthesis
Solar-Lezama, A. (2009) · Asian Symposium on Programming Languages and Systems · doi:10.1007/978-3-642-10672-9_3 · Cited by 186 · see citing works
Type-and-example-directed program synthesis
Osera, P.-M., & Zdancewic, S. (2015) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/2737924.2738007 · Cited by 185 · see citing works
Synthesizing highly expressive SQL queries from input-output examples
Wang, C., Cheung, A., & Bodík, R. (2017) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3062341.3062365 · Cited by 178 · see citing works
Programming by sketching for bit-streaming programs
Solar-Lezama, A., Rabbah, R., Bodík, R., & Ebcioğlu, K. (2005) · Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation · doi:10.1145/1065010.1065045 · Cited by 167 · see citing works
Udupa, A., Raghavan, A., Deshmukh, J. V., Mador-Haim, S., Martin, M. M. K., & Rajeev Alur, A. (2013) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/2491956.2462174 · Cited by 158 · see citing works
Albarghouthi, A., Gulwani, S., & Kincaid, Z. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-39799-8_67 · Cited by 147 · see citing works
Complete completion using types and weights
Gvero, T., Kunčak, V., Kuraj, I., & Piskač, R. (2013) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/2491956.2462192 · Cited by 137 · see citing works
Component-based synthesis of table consolidation and transformation tasks from examples
Feng, Y., Martins, R., Geffen, J. V., Dillig, I., & Chaudhuri, S. (2017) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3062341.3062351 · Cited by 131 · see citing works
Self-citationLearning programs from noisy data
Raychev, V., Bielik, P., Vechev, M., & Krause, A. (2016) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/2837614.2837671 · Cited by 125 · see citing works
Component-based synthesis for complex APIs
Feng, Y., Martins, R., Wang, Y., Dillig, I., & Reps, T. (2016) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/3009837.3009851 · Cited by 117 · see citing works
Self-citationA Machine Learning Framework for Programming by Example
Menon, A. K., Tamuz, O., Gulwani, S., Lampson, B., & Kalai, A. T. (2013) · Cited by 112 · see citing works
Singh, R. (2016) · Proceedings of the VLDB Endowment · doi:10.14778/2977797.2977807 · Cited by 87 · see citing works
Program synthesis using abstraction refinement
Wang, X., Dillig, I., & Singh, R. (2017) · Proceedings of the ACM on Programming Languages · doi:10.1145/3158151 · Cited by 84 · see citing works
Self-citationAutomatically synthesizing SQL queries from input-output examples
Zhang, S., & Sun, Y. (2013) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1109/ase.2013.6693082 · Cited by 78 · see citing works
Smith, C., & Albarghouthi, A. (2016) · Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/2908080.2908102 · Cited by 76 · see citing works
Transforming spreadsheet data types using examples
Singh, R., & Gulwani, S. (2016) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/2837614.2837668 · Cited by 54 · see citing works
Synthesizing transformations on hierarchically structured data
Yaghmazadeh, N., Klinger, C., Dillig, I., & Chaudhuri, S. (2016) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/2908080.2908088 · Cited by 46 · see citing works
Self-citationSynthesis of data completion scripts using finite tree automata
Wang, X., Dillig, I., & Singh, R. (2017) · Proceedings of the ACM on Programming Languages · doi:10.1145/3133886 · Cited by 44 · see citing works
Self-citationProgram Synthesis Using Dual Interpretation
Tiwari, A., Gascón, A., & Dutertre, B. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-21401-6_33 · Cited by 28 · see citing works
Program Synthesis using Abstraction RefinementPreprint
Wang, X., Dillig, I., & Singh, R. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.07740 · Cited by 16 · see citing works
Self-citationLook for the Proof to Find the Program: Decorated-Component-Based Program Synthesis
Gascón, A., Tiwari, A., Carmer, B., & Mathur, U. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-63390-9_5 · Cited by 8 · see citing works
Flagged first, then by citations
2 of the 46 references couldn’t be matched to a known paper.
Research works printed but not linked: 7
- Aws Albarghouthi, Sumit Gulwani, and Zachary Kincaid. 2013. Recur- sive Program Synthesis. In Proc. International Conference on Computer Aided Verification. Springer, 934-950.
- Arvind Neelakantan, Quoc V Le, Martin Abadi, Andrew McCallum, and Dario Amodei. 2017. Learning a natural language interface with neural programmer. In Proc. International Conference on Learning Rep- resentations. OpenReview.
- Arvind Neelakantan, Quoc V Le, and Ilya Sutskever. 2016. Neural programmer: Inducing latent programs with gradient descent. In Proc. International Conference on Learning Representations. OpenReview.
- Rishabh Singh. 2016. Blinkfill: Semi-supervised programming by ex- ample for syntactic string transformations. Proceedings of the VLDB Endowment 9, 10 (2016), 816-827.
- Calvin Smith and Aws Albarghouthi. 2016. MapReduce program syn- thesis. In Proc. Conference on Programming Language Design and Im- plementation. ACM, 326-340.
- Abhishek Udupa, Arun Raghavan, Jyotirmoy V Deshmukh, Sela Mador- Haim, Milo MK Martin, and Rajeev Alur. 2013. TRANSIT: specifying protocols with concolic snippets. Proc. Conference on Programming Language Design and Implementation (2013), 287-296.
- Yu Feng, Ruben Martins, Osbert Bastani, and Isil Dillig data. In Proc. Conference on Programming Language Design and Imple- mentation. ACM, 508-521.
Cited by
Sorted by citations
In-IDE Code Generation from Natural Language: Promise and Challenges
Xu, F. F., Vasilescu, B., & Neubig, G. (2022) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/3487569 · Cited by 154 · see citing works
“Besides visual no-code or low-code programming interfaces, there has also been much progress on program synthesis [12, 29, 31, 108], which uses input-output examples, logic sketches, etc.”
Background(2021) · doi:10.1145/3510003.3510203 · Cited by 139 · see citing works
Fuzz testing based data augmentation to improve robustness of deep neural networks
Gao, X. Y., Saha, R. K., Prasad, M. R., & Roychoudhury, A. (2020) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1145/3377811.3380415 · Cited by 129 · see citing works
Learning programs by learning from failures
Cropper, A., & Morel, R. (2021) · Machine Learning · doi:10.1007/s10994-020-05934-z · Cited by 86 · see citing works
“Indeed, PL approaches rarely evaluate the ability of their systems to synthesise solutions that generalise, i.e. they do not measure predictive accuracy (Feser et al. 2015; Polikarpova et al. 2016; Albarghouthi et al. 2017; Feng et al. 2018; Raghothaman et al. 2020).”
BackgroundMethodGenerative Code Modeling with GraphsPreprint
Brockschmidt, M., Allamanis, M., Gaunt, A. L., & Polozov, O. (2018) · International Conference on Learning Representations · doi:10.48550/arxiv.1805.08490 · Cited by 199 · see citing works
Multi-modal synthesis of regular expressions
Chen, Q., Wang, X., Ye, X., Durrett, G., & Dillig, I. (2020) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3385412.3385988 · Cited by 81 · see citing works
Self-citationAutoPandas: neural-backed generators for program synthesis
Bavishi, R., Lemieux, C., Fox, R., Sen, K., & Stoica, I. (2019) · Proceedings of the ACM on Programming Languages · doi:10.1145/3360594 · Cited by 73 · see citing works
Deep Learning Based Program Generation From Requirements Text: Are We There Yet?
Liu, H., Shen, M., Zhu, J., Niu, N., Li, G., & Zhang, L. (2020) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2020.3018481 · Cited by 50 · see citing works
Reconciling enumerative and deductive program synthesis
Huang, K., Qiu, X., Shen, P., & Wang, Y. (2020) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3385412.3386027 · Cited by 46 · see citing works
Synthesizing database programs for schema refactoring
Wang, Y., Dong, J., Shah, R., & Dillig, I. (2019) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3314221.3314588 · Cited by 45 · see citing works
Self-citationMartins, R., Chen, J., Chen, Y., Feng, Y., & Dillig, I. (2019) · Proceedings of the VLDB Endowment · doi:10.14778/3352063.3352098 · Cited by 40 · see citing works
Self-citationResource-guided program synthesis
Knoth, T., Wang, D., Polikarpova, N., & Hoffmann, J. (2019) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3314221.3314602 · Cited by 38 · see citing works
Wang, C., Feng, Y., Bodík, R., Cheung, A., & Dillig, I. (2019) · Proceedings of the ACM on Programming Languages · doi:10.1145/3371117 · Cited by 37 · see citing works
Self-citationCombining the top-down propagation and bottom-up enumeration for inductive program synthesis
Lee, W. (2021) · Proceedings of the ACM on Programming Languages · doi:10.1145/3434335 · Cited by 34 · see citing works
Question selection for interactive program synthesis
Ji, R., Liang, J., Xiong, Y., Zhang, L., & Hu, Z. (2020) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3385412.3386025 · Cited by 33 · see citing works
Program Synthesis Using Deduction-Guided Reinforcement Learning
Chen, Y., Wang, C., Bastani, O., Dillig, I., & Feng, Y. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-53291-8_30 · Cited by 33 · see citing works
Self-citationMaximal multi-layer specification synthesis
Chen, Y., Martins, R., & Feng, Y. (2019) · ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) · doi:10.1145/3338906.3338951 · Cited by 28 · see citing works
Self-citationData Extraction via Semantic Regular Expression Synthesis
Chen, Q., Banerjee, A., Demiralp, Ç., Durrett, G., & Dillig, I. (2023) · Proceedings of the ACM on Programming Languages · doi:10.1145/3622863 · Cited by 27 · see citing works
Self-citationInterpretable Program Synthesis
Zhang, T., Chen, Z., Zhu, Y., Vaithilingam, P., Wang, X., & Glassman, E. L. (2021) · CHI Conference on Human Factors in Computing Systems · doi:10.1145/3411764.3445646 · Cited by 26 · see citing works
Sketch-Driven Regular Expression Generation from Natural Language and Examples
Ye, X., Chen, Q., Wang, X., Dillig, I., & Durrett, G. (2020) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00339 · Cited by 23 · see citing works
Self-citationDemystifying loops in smart contracts
Mariano, B., Chen, Y., Feng, Y., Lahiri, S. K., & Dillig, I. (2020) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1145/3324884.3416626 · Cited by 21 · see citing works
Self-citationUsing active learning to synthesize models of applications that access databases
Shen, J., & Rinard, M. (2019) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3314221.3314591 · Cited by 19 · see citing works
On the Impact of Machine Learning: Architecture without Architects?
Belém, C., Santos, L., & Leitão, A. (2019) · Cited by 19 · see citing works
Relational verification using reinforcement learning
Chen, J., Wei, J., Feng, Y., Bastani, O., & Dillig, I. (2019) · Proceedings of the ACM on Programming Languages · doi:10.1145/3360567 · Cited by 19 · see citing works
Self-citationLooPy: interactive program synthesis with control structures
Ferdowsifard, K., Barke, S., Peleg, H., Lerner, S., & Polikarpova, N. (2021) · Proceedings of the ACM on Programming Languages · doi:10.1145/3485530 · Cited by 18 · see citing works
Ardeshiricham, A., Takashima, Y., Gao, S., & Kastner, R. (2019) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3319535.3354246 · Cited by 17 · see citing works
Optimal Neural Program Synthesis from Multimodal Specifications
Ye, X., Chen, Q., Dillig, I., & Durrett, G. (2021) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2021.findings-emnlp.146 · Cited by 16 · see citing works
Self-citationSynthesis-powered optimization of smart contracts via data type refactoring
Chen, Y., Wang, Y., Goyal, M., Dong, J., Feng, Y., & Dillig, I. (2022) · Proceedings of the ACM on Programming Languages · doi:10.1145/3563308 · Cited by 14 · see citing works
Self-citationBenchmarking Multimodal Regex Synthesis with Complex Structures
Ye, X., Chen, Q., Dillig, I., & Durrett, G. (2020) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/2020.acl-main.541 · Cited by 14 · see citing works
Self-citationFORAY: Towards Effective Attack Synthesis against Deep Logical Vulnerabilities in DeFi Protocols
Wen, H., Liu, H., Song, J., Chen, Y., Guo, W., & Feng, Y. (2024) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3658644.3690293 · Cited by 13 · see citing works
Self-citationExplainable Program Synthesis by Localizing Specifications
Nazari, A., Huang, Y., Samanta, R., Radhakrishna, A., & Raghothaman, M. (2023) · Proceedings of the ACM on Programming Languages · doi:10.1145/3622874 · Cited by 13 · see citing works
Saha, R. K., Ura, A., Mahajan, S., Zhu, C., Li, L., Yang, H., Yoshida, H., Sarfraz Khurshid, D., & Prasad, M. R. (2022) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1145/3510003.3510226 · Cited by 12 · see citing works
Kim, J., D’Antoni, L., & Reps, T. (2023) · Proceedings of the ACM on Programming Languages · doi:10.1145/3571216 · Cited by 12 · see citing works
Modeling black-box components with probabilistic synthesis
Collie, B., Woodruff, J., & O’boyle, M. F. P. (2020) · ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (GPCE) · doi:10.1145/3425898.3426952 · Cited by 12 · see citing works
Programming-by-Demonstration for Long-Horizon Robot Tasks
Patton, N., Rahmani, K., Missula, M., Biswas, J., & Dillig, I. (2024) · Proceedings of the ACM on Programming Languages · doi:10.1145/3632860 · Cited by 12 · see citing works
Self-citationSynthesizing analytical SQL queries from computation demonstration
Zhou, X., Bodík, R., Cheung, A., & Wang, C. (2022) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3519939.3523712 · Cited by 11 · see citing works
Encodings for Enumeration-Based Program Synthesis
Orvalho, P., Terra-Neves, M., Ventura, M., Martins, R., & Manquinho, V. M. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-30048-7_34 · Cited by 11 · see citing works
Self-citationTesting for Race Conditions in Distributed Systems via SMT Solving
Pereira, J. C., Machado, N., & Pinto, J. S. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-50995-8_7 · Cited by 11 · see citing works
Enhanced Enumeration Techniques for Syntax-Guided Synthesis of Bit-Vector Manipulations
Ding, Y., & Qiu, X. (2024) · Proceedings of the ACM on Programming Languages · doi:10.1145/3632913 · Cited by 10 · see citing works
Trials and Tribulations in Synthesizing Operating Systems
Hu, J., Lu, E., Holland, D. A., Kawaguchi, M., Chong, S., & Seltzer, M. (2019) · Workshop on Programming Languages and Operating Systems (PLOS) · doi:10.1145/3365137.3365401 · Cited by 10 · see citing works
Synthesizing data structure refinements from integrity constraints
Pailoor, S., Wang, Y., Wang, X., & Dillig, I. (2021) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3453483.3454063 · Cited by 10 · see citing works
Self-citationThe wonderful wizard of LoC: paying attention to the man behind the curtain of lines-of-code metrics
Alpernas, K., Feldman, Y. M. Y., & Peleg, H. (2020) · ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!) · doi:10.1145/3426428.3426921 · Cited by 9 · see citing works
Scaling Neural Program Synthesis with Distribution-Based Search
Fijalkow, N., Lagarde, G., Matricon, T., Ellis, K., Ohlmann, P., & Potta, A. N. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i6.20616 · Cited by 8 · see citing works
Algebra-Based Reasoning for Loop Synthesis
Humenberger, A., Amrollahi, D., Bjørner, N., & Kovács, L. (2022) · Formal Aspects of Computing · doi:10.1145/3527458 · Cited by 8 · see citing works
RbSyn: type- and effect-guided program synthesis
Guria, S. N., Foster, J. S., & Horn, D. V. (2021) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3453483.3454048 · Cited by 8 · see citing works
FOREST: An Interactive Multi-tree Synthesizer for Regular Expressions
Ferreira, M. A., Terra-Neves, M., Ventura, M., Lynce, I., & Martins, R. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-72016-2_9 · Cited by 8 · see citing works
Self-citationSpecification-guided component-based synthesis from effectful libraries
Mishra, A., & Jagannathan, S. (2022) · Proceedings of the ACM on Programming Languages · doi:10.1145/3563310 · Cited by 7 · see citing works
Active learning for inference and regeneration of computer programs that store and retrieve data
Rinard, M., Shen, J., & Mangalick, V. (2018) · ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!) · doi:10.1145/3276954.3276959 · Cited by 7 · see citing works
DeeperCoder: Code Generation Using Machine Learning
Shim, S. S. Y., Patil, P., Yadav, R. R., Shinde, A., & Devale, V. (2020) · IEEE Annual Computing and Communication Workshop and Conference (CCWC) · doi:10.1109/ccwc47524.2020.9031149 · Cited by 7 · see citing works
Counterfeiting Congestion Control Algorithms
Ferreira, M., Narayan, A., Lynce, I., Martins, R., & Sherry, J. (2021) · ACM Workshop on Hot Topics in Networks (HotNets) · doi:10.1145/3484266.3487381 · Cited by 7 · see citing works
Self-citationInductive Program Synthesis Guided by Observational Program Similarity
Feser, J., Dillig, I., & Solar-Lezama, A. (2023) · Proceedings of the ACM on Programming Languages · doi:10.1145/3622830 · Cited by 6 · see citing works
Self-citationReverse-Engineering Congestion Control Algorithm Behavior
Ferreira, M., Ware, R., Kothari, Y., Lynce, I., Martins, R., Narayan, A., & Sherry, J. (2024) · ACM Internet Measurement Conference (IMC) · doi:10.1145/3646547.3688443 · Cited by 6 · see citing works
Self-citationRamos, D., Pereira, J., Lynce, I., Manquinho, V. M., & Martins, R. (2020) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1145/3324884.3416613 · Cited by 6 · see citing works
Self-citationAbsynthe: Abstract Interpretation-Guided Synthesis
Guria, S. N., Foster, J. S., & Horn, D. V. (2023) · Proceedings of the ACM on Programming Languages · doi:10.1145/3591285 · Cited by 6 · see citing works
Fast and Reliable Program Synthesis via User Interaction
Chen, Y., Wang, C., Wang, X., Bastani, O., & Feng, Y. (2023) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1109/ase56229.2023.00129 · Cited by 6 · see citing works
Self-citationProgram Synthesis Guided Reinforcement Learning for Partially Observed EnvironmentsPreprint
Yang, Y., Inala, J. P., Bastani, O., Pu, Y., Solar-Lezama, A., & Rinard, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.11137 · Cited by 6 · see citing works
Self-citationBrauckmann, A., Jaulmes, L., Magalhães, J. W. D. S., Polgreen, E., & O’boyle, M. F. P. (2025) · Proceedings of the CGO/Proceedings of the ... CGO · doi:10.1145/3696443.3708956 · Cited by 5 · see citing works
A Concurrent Approach to String Transformation Synthesis
Ding, Y., & Qiu, X. (2025) · Proceedings of the ACM on Programming Languages · doi:10.1145/3729336 · Cited by 5 · see citing works
Mobius: Synthesizing Relational Queries with Recursive and Invented Predicates
Thakkar, A., Sands, N., Petrou, G., Rajeev Alur, A., Naik, M., & Raghothaman, M. (2023) · Proceedings of the ACM on Programming Languages · doi:10.1145/3622847 · Cited by 5 · see citing works
Conflict-Driven Synthesis for Layout Engines
Liu, J., Chen, Y., Atkinson, E., Feng, Y., & Bodík, R. (2023) · Proceedings of the ACM on Programming Languages · doi:10.1145/3591246 · Cited by 5 · see citing works
Self-citationActive Learning for Inference and Regeneration of Applications that Access Databases
Shen, J., & Rinard, M. (2020) · ACM Transactions on Programming Languages and Systems · doi:10.1145/3430952 · Cited by 5 · see citing works
Tree traversal synthesis using domain-specific symbolic compilation
Chen, Y., Liu, J., Feng, Y., & Bodík, R. (2022) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3503222.3507751 · Cited by 5 · see citing works
Self-citationRepairing serializability bugs in distributed database programs via automated schema refactoring
Rahmani, K., Nagar, K., Delaware, B., & Jagannathan, S. (2021) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3453483.3454028 · Cited by 5 · see citing works
Data Generation for Neural Programming by ExamplePreprint
Clymo, J., Manukian, H., Fijalkow, N., Gascón, A., & Paige, B. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.02624 · Cited by 5 · see citing works
Learning logic programs by explaining their failures
Morel, R., & Cropper, A. (2023) · Machine Learning · doi:10.1007/s10994-023-06358-1 · Cited by 4 · see citing works
Reinforcement Learning and Data-Generation for Syntax-Guided Synthesis
Parsert, J., & Polgreen, E. (2024) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v38i9.28938 · Cited by 4 · see citing works
Solving System Problems with Machine Learning
Stoica, I. G. (2019) · Studies in Informatics and Control · doi:10.24846/v28i2y201901 · Cited by 4 · see citing works
Gauss: program synthesis by reasoning over graphs
Bavishi, R., Lemieux, C., Sen, K., & Stoica, I. G. (2021) · Proceedings of the ACM on Programming Languages · doi:10.1145/3485511 · Cited by 4 · see citing works
Knowledge Graph Programming with a Human-in-the-Loop
Lou, Y., Uddin, M., Brown, N., & Cafarella, M. (2019) · Workshop on Human-In-the-Loop Data Analytics (HILDA) · doi:10.1145/3328519.3329132 · Cited by 4 · see citing works
Using human-in-the-loop synthesis to author functional reactive programsPreprint
Newcomb, J. L., & Bodík, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.11206 · Cited by 4 · see citing works
Robot Action Selection Learning via Layered Dimension Informed Program SynthesisPreprint
Holtz, J., Guha, A., & Biswas, J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.04133 · Cited by 4 · see citing works
Learning Fitness Functions for Machine ProgrammingPreprint
Mandal, S., Anderson, T. A., Turek, J. S., Gottschlich, J., Zhou, S., & Muzahid, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.08783 · Cited by 4 · see citing works
Lubin, J. P., Ziegler, P., & Chasins, S. (2025) · Proceedings of the ACM on Programming Languages · doi:10.1145/3729264 · Cited by 3 · see citing works
Synthesizing MILP Constraints for Efficient and Robust Optimization
Wang, J., Gupta, A., & Wang, C. (2023) · Proceedings of the ACM on Programming Languages · doi:10.1145/3591298 · Cited by 3 · see citing works
Synthesizing Mutable Configurations: Setting up Systems for Success
Nelson, T., Danas, N., Giannakopoulos, T., & Krishnamurthi, S. (2019) · IEEE/ACM International Conference on Automated Software Engineering Workshops (ASEW) · doi:10.1109/asew.2019.00034 · Cited by 3 · see citing works
Reward-Guided Synthesis of Intelligent Agents with Control Structures
Cui, G., Wang, Y., Qiu, W., & Zhu, H. (2024) · Proceedings of the ACM on Programming Languages · doi:10.1145/3656447 · Cited by 3 · see citing works
General Program Synthesis Using Guided Corpus Generation and Automatic Refactoring
Wild, A., & Porter, B. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-27455-9_7 · Cited by 3 · see citing works
Algebra-Based Synthesis of Loops and Their Invariants (Invited Paper)
Humenberger, A., & Kovács, L. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-67067-2_2 · Cited by 3 · see citing works
SynFuzz: Efficient Concolic Execution via Branch Condition SynthesisPreprint
Han, W., Rahman, M. L., Chen, Y., Song, C., Lee, B., & Shin, I. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.09532 · Cited by 3 · see citing works
Generating Function Names to Improve Comprehension of Synthesized Programs
Nazari, A., Swayamdipta, S., Chattopadhyay, S., & Raghothaman, M. (2024) · IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC) · doi:10.1109/vl/hcc60511.2024.00035 · Cited by 2 · see citing works
Refinement Types for Visualization
Xia, J., Liu, J., Brown, N., Chen, Y., & Feng, Y. (2024) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1145/3691620.3695550 · Cited by 2 · see citing works
Self-citationAn evolutionary framework for automatic and guided discovery of algorithms
Sasanka, R., & Krommydas, K. F. (2020) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/3387902.3394033 · Cited by 2 · see citing works
Synthesizing Queries via Interactive SketchingPreprint
Bastani, O., Zhang, X., & Solar-Lezama, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.12659 · Cited by 2 · see citing works
Self-citationCreating Synthetic Datasets via Evolution for Neural Program SynthesisPreprint
Suh, A., & Timen, Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.10485 · Cited by 2 · see citing works
G enesys : A Novel Evolutionary Program Synthesis Tool with Continuous Optimization
Mandal, S., Anderson, T. A., Turek, J. S., Gottschlich, J., & Muzahid, A. (2025) · ACM transactions on probabilistic machine learning. · doi:10.1145/3776736 · Cited by 1 · see citing works
Automated Repair of OpenID Connect Programs
Rahat, T. A., Chen, Y., Feng, Y., & Tian, Y. (2025) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1109/ase63991.2025.00187 · Cited by 1 · see citing works
Self-citationDefining behaviorizeable relations to enable inference in semi-automatic program synthesis
Krasanakis, E., & Symeonidis, A. L. (2021) · Journal of Logical and Algebraic Methods in Programming · doi:10.1016/j.jlamp.2021.100714 · Cited by 1 · see citing works
Wang, Y., & Li, X. (2021) · IEEE Access · doi:10.1109/access.2021.3079351 · Cited by 1 · see citing works
Type-driven Neural Programming by ExamplePreprint
Grouwstra, K. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.12613 · Cited by 1 · see citing works
FOREST: An Interactive Multi-tree Synthesizer for Regular Expressions
Ferreira, M. (2021) · doi:10.26226/morressier.604907f41a80aac83ca25cef · Cited by 1 · see citing works
Optimal Neural Program Synthesis from Multimodal SpecificationsPreprint
Ye, X., Chen, Q., Dillig, I., & Durrett, G. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.01678 · Cited by 1 · see citing works
Self-citationSupported Programming for Beginning Developers
Gilbert, A. (2019) · doi:10.15368/theses.2019.9
Comparison of Syntactic and Semantic Representations of Programs in Neural EmbeddingsPreprint
Wright, A. P., & Wiklicky, H. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.09201
Enhancing Web App Execution with Automated Reengineering
An, K. (2020) · International World Wide Web Conference (WWW) · doi:10.1145/3366424.3382087
Vasudevan, A., Maniatis, P., & Martins, R. (2020) · ACM SIGOPS Operating Systems Review · doi:10.1145/3421473.3421476
Self-citationLearning Logic Programs by Explaining Failures.Preprint
Morel, R., & Cropper, A. (2021) · arXiv (Cornell University)
Constraint-Driven Learning of Logic Programs
Morel, R. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i18.17860
Visualization question answering using introspective program synthesis
Chen, Y., Yan, X., & Feng, Y. (2022) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3519939.3523709
Self-citationDeepQRE: A QRE System Based on Deep Learning
Zhang, S., & Dou, Q. (2023) · International Conference on Mechatronics and Robotics Engineering (ICMRE) · doi:10.1109/icmre56789.2023.10106580
LGEQRE: Learning Guided Enumerative Synthesis for Query Reverse EngineeringPreprint
Wang, H., Dou, Q., Tang, H., Pan, H., & Zhang, S. (2023) · Research Square · doi:10.21203/rs.3.rs-3320857/v1
- Authors
- Feng, Y., Martins, R., Bastani, O., & Dillig, I.
- Affiliations
- The University of Texas at Austin (US)
- Carnegie Mellon University (US)
- Massachusetts Institute of Technology (US)
- University of Texas at Austin, USA
- Venue
- Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation
- Publisher
- ACM
- Published
- 2018-06-11
- Pages
- 420-435
- ISSN
- 1531-7102 (ISSN-L)
- OpenAlex
- W2964240296
- Cited by
- 111
- References
- 46
- Citations by year
- 2026: 3 · 2025: 11 · 2024: 8 · 2023: 13 · 2022: 10 · 2021: 18 · 2020: 23 · 2019: 22 · 2018: 3
- FWCI
- 6.71
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) (publishedVersion)
- Funders
- National Science Foundation (1453386)
- Defense Advanced Research Projects Agency (8750-14-2-0270)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
- Physical Sciences › Computer Science › Computer Science Applications › Teaching and Learning Programming
- Keywords
- program synthesis, CDCL, learning from mistakes, search space pruning, data wrangling, functional programming
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
