G enesys : A Novel Evolutionary Program Synthesis Tool with Continuous Optimization

ACM transactions on probabilistic machine learning., 2025. 0 citations.

Abstract

Automatic software generation based on some specification is known as program synthesis . Most existing approaches formulate program synthesis as a search problem with discrete parameters. In this article, we present a novel formulation of program synthesis as a continuous optimization problem using an evolutionary approach, known as Covariance Matrix Adaptation Evolution Strategy. We then propose several mapping schemes to convert the continuous formulation into actual programs and propose different restart policies for the evolutionary approach. This is the first work that demonstrates the feasibility of continuous approach in synthesizing complex programs, not just simple toy programs. We compare our system, Genesys , to several recent program synthesis techniques (in both discrete and continuous domains). We find that Genesys synthesizes more programs within a fixed time budget than those existing schemes. For example, for programs of length 10, Genesys synthesizes 28% more programs than those existing schemes within the same time budget.

Authors

• Shantanu Mandal (Texas A&M University): h-index 3; 19 citations; corresponding author
• Todd A. Anderson (Bodø Science Park (Norway)): h-index 9; 221 citations
• Javier S. Turek (Intel (United States)): h-index 18; 1,096 citations
• Justin Gottschlich (Santa Clara University): h-index 15; 666 citations
• Abdullah Muzahid (Texas A&M University): h-index 11; 418 citations

Topics

Advanced Multi-Objective Optimization Algorithms, Software Testing and Debugging Techniques, Evolutionary Algorithms and Applications, Program synthesis, Computer science

References

• Zohar Manna, Richard Waldinger. Knowledge and reasoning in program synthesis. Artificial Intelligence. 1975;6(2):175-208. doi:10.1016/0004-3702(75)90008-9.
• Susanne Winter, Bernhard Brendel, Andreas Rick, M. Stockheim, Kirsten Schmieder, H. Ermert. Registration of bone surfaces, extracted from CT-datasets, with 3D ultrasound. Biomedizinische Technik/Biomedical Engineering. 2002;47(s1a):57-60. doi:10.1515/bmte.2002.47.s1a.57.
• Nikolaus Hansen. Benchmarking a BI-population CMA-ES on the BBOB-2009 function testbed. 2009;2389-2396. doi:10.1145/1570256.1570333.
• Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, Li Fei-Fei. ImageNet: A large-scale hierarchical image database. 2009 IEEE Conference on Computer Vision and Pattern Recognition. 2009;248-255. doi:10.1109/cvpr.2009.5206848.
• Nikolaus Hansen, Andreas Ostermeier. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation. 2001;9(2):159-195. doi:10.1162/106365601750190398.
• Mark Kramer. Nonlinear principal component analysis using autoassociative neural networks. AIChE Journal. 1991;37(2):233-243. doi:10.1002/aic.690370209.
• Veselin Raychev, Martin Vechev, Eran Yahav. Code completion with statistical language models. 2014;419-428. doi:10.1145/2594291.2594321.
• Armando Solar-Lezama, Liviu Tancau, Rastislav Bodík, Sanjit A. Seshia, Vijay Saraswat. Combinatorial sketching for finite programs. 2006;404-415. doi:10.1145/1168857.1168907.
• Swagatam Das, Ponnuthurai Nagaratnam Suganthan. Differential Evolution: A Survey of the State-of-the-Art. IEEE Transactions on Evolutionary Computation. 2010;15(1):4-31. doi:10.1109/tevc.2010.2059031.
• Eric Schkufza, Rahul Sharma, Alex Aiken. Stochastic superoptimization. 2013;305-316. doi:10.1145/2451116.2451150.
• Swarat Chaudhuri, Armando Solar-Lezama. Smooth interpretation. 2010;279-291. doi:10.1145/1806596.1806629.
• Rafael Gómez-Bombarelli, Jennifer N. Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez-Lengeling, Dennis Sheberla, et al. Automatic Chemical Design Using a Data-Driven Continuous Representation of Molecules. ACS Central Science. 2018;4(2):268-276. doi:10.1021/acscentsci.7b00572.
• Calvin Loncaric, Michael D. Ernst, Emina Torlak. Generalized data structure synthesis. 2018;958-968. doi:10.1145/3180155.3180211.
• Tomasz P. Pawlak, Krzysztof Krawiec. Synthesis of Constraints for Mathematical Programming With One-Class Genetic Programming. IEEE Transactions on Evolutionary Computation. 2018;23(1):117-129. doi:10.1109/tevc.2018.2835565.
• Justin Gottschlich, Armando Solar-Lezama, Nesime Tatbul, Michael Carbin, Martin Rinard, Regina Barzilay, et al. The three pillars of machine programming. 2018;69-80. doi:10.1145/3211346.3211355.
• Daniel Sroka, Tomasz P. Pawlak. One-class constraint acquisition with local search. Proceedings of the Genetic and Evolutionary Computation Conference. 2018;363-370. doi:10.1145/3205455.3205480.
• Erik Hemberg, Jonathan Kelly, Una-May O’Reilly. On domain knowledge and novelty to improve program synthesis performance with grammatical evolution. Proceedings of the Genetic and Evolutionary Computation Conference. 2019;1039-1046. doi:10.1145/3321707.3321865.
• Yu Feng, Ruben Martins, Osbert Bastani, Işıl Dillig. Program synthesis using conflict-driven learning. 2018;420-435. doi:10.1145/3192366.3192382.
• Xujie Si, Mukund Raghothaman, Kihong Heo, Mayur Naik. Synthesizing Datalog Programs using Numerical Relaxation. 2019;6117-6124. doi:10.24963/ijcai.2019/847.
• Marcin Karmelita, Tomasz P. Pawlak. CMA-ES for one-class constraint synthesis. 2020;859-867. doi:10.1145/3377930.3389807.
• Paweł Liskowski, Krzysztof Krawiec, Nihat Engin Toklu, Jerry Swan. Program synthesis as latent continuous optimization. 2020;359-367. doi:10.1145/3377930.3390213.
• Yanju Chen, Chenglong Wang, Osbert Bastani, Işıl Dillig, Yu Feng. Program Synthesis Using Deduction-Guided Reinforcement Learning. Lecture notes in computer science. 2020;587-610. doi:10.1007/978-3-030-53291-8_30.
• Thomas Helmuth, Peter Kelly. PSB2. Proceedings of the Genetic and Evolutionary Computation Conference. 2021;785-794. doi:10.1145/3449639.3459285.
• Yingfei Xiong, Bo Wang. L2S: A Framework for Synthesizing the Most Probable Program under a Specification. ACM Transactions on Software Engineering and Methodology. 2022;31(3):1-45. doi:10.1145/3487570.
• Edward Pantridge, Thomas Helmuth, Lee Spector. Functional code building genetic programming. Proceedings of the Genetic and Evolutionary Computation Conference. 2022;1000-1008. doi:10.1145/3512290.3528866.
• Christoph Anneser, Nesime Tatbul, David Cohen, Zhenggang Xu, P. Senthil Pandian, Nikolay Laptev, et al. AutoSteer: Learned Query Optimization for Any SQL Database. Proceedings of the VLDB Endowment. 2023;16(12):3515-3527. doi:10.14778/3611540.3611544.
• Jeffrey Tao, Natalie Maus, Haydn T. Jones, Yimeng Zeng, Jacob R. Gardner, Ryan Marcus. Learned Offline Query Planning via Bayesian Optimization. Proceedings of the ACM on Management of Data. 2025;3(3):1-29. doi:10.1145/3725316.