{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:24:34Z","timestamp":1787505874894,"version":"build-2736575974"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2022,4,29]],"date-time":"2022-04-29T00:00:00Z","timestamp":1651190400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,4,29]]},"abstract":"<jats:p>While many mainstream languages such as Java, Python, and C# increasingly incorporate functional APIs to simplify programming and improve parallelization\/performance, there are no effective techniques that can be used to automatically translate existing imperative code to functional variants using these APIs. Motivated by this problem, this paper presents a transpilation approach based on inductive program synthesis for modernizing existing code. Our method is based on the observation that the overwhelming majority of source\/target programs in this setting satisfy an assumption that we call trace-compatibility: not only do the programs share syntactically identical low-level expressions, but these expressions also take the same values in corresponding execution traces. Our method leverages this observation to design a new neural-guided synthesis algorithm that (1) uses a novel neural architecture called cognate grammar network (CGN) and (2) leverages a form of concolic execution to prune partial programs based on intermediate values that arise during a computation. We have implemented our approach in a tool called NGST2 and use it to translate imperative Java and Python code to functional variants that use the Stream and functools APIs respectively. Our experiments show that NGST2 significantly outperforms several baselines and that our proposed neural architecture and pruning techniques are vital for achieving good results.<\/jats:p>","DOI":"10.1145\/3527315","type":"journal-article","created":{"date-parts":[[2022,4,29]],"date-time":"2022-04-29T11:42:03Z","timestamp":1651232523000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Automated transpilation of imperative to functional code using neural-guided program synthesis"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2987-6260","authenticated-orcid":false,"given":"Benjamin","family":"Mariano","sequence":"first","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6494-3126","authenticated-orcid":false,"given":"Yanju","family":"Chen","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1000-1229","authenticated-orcid":false,"given":"Yu","family":"Feng","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7061-7298","authenticated-orcid":false,"given":"Greg","family":"Durrett","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8006-1230","authenticated-orcid":false,"given":"I\u015fil","family":"Dillig","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,4,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.7287\/peerj.preprints.1459v1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196891"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39799-8_67"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21668-3_10"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the International Conference on Learning Representations (ICLR). International Conference on Learning Representations (ICLR)","author":"Bahdanau Dzmitry","year":"2015","unstructured":"Dzmitry Bahdanau , Kyunghyun Cho , and Yoshua Bengio . 2015 . Neural Machine Translation by Jointly Learning to Align and Translate . In Proceedings of the International Conference on Learning Representations (ICLR). International Conference on Learning Representations (ICLR) , La Jolla, CA, USA. 1\u201315. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015. Neural Machine Translation by Jointly Learning to Align and Translate. In Proceedings of the International Conference on Learning Representations (ICLR). International Conference on Learning Representations (ICLR), La Jolla, CA, USA. 1\u201315."},{"key":"e_1_2_1_6_1","volume-title":"Deepcoder: Learning to write programs. https:\/\/doi.org\/10.48550\/arXiv.1611.01989 arxiv:1611.01989.","author":"Balog Matej","year":"2016","unstructured":"Matej Balog , Alexander L Gaunt , Marc Brockschmidt , Sebastian Nowozin , and Daniel Tarlow . 2016 . Deepcoder: Learning to write programs. https:\/\/doi.org\/10.48550\/arXiv.1611.01989 arxiv:1611.01989. Matej Balog, Alexander L Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. 2016. Deepcoder: Learning to write programs. https:\/\/doi.org\/10.48550\/arXiv.1611.01989 arxiv:1611.01989."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180219"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454047"},{"key":"e_1_2_1_9_1","unstructured":"Xinyun Chen Chang Liu and Dawn Song. 2018. Tree-to-tree neural networks for program translation. arxiv:1802.03691.  Xinyun Chen Chang Liu and Dawn Song. 2018. Tree-to-tree neural networks for program translation. arxiv:1802.03691."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462180"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/2.4.511"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCL.1994.288389"},{"key":"e_1_2_1_13_1","volume-title":"Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning. https:\/\/doi.org\/10.48550\/arXiv.2006.08381 arxiv:2006.08381.","author":"Ellis Kevin","year":"2020","unstructured":"Kevin Ellis , Catherine Wong , Maxwell Nye , Mathias Sable-Meyer , Luc Cary , Lucas Morales , Luke Hewitt , Armando Solar-Lezama , and Joshua B Tenenbaum . 2020 . Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning. https:\/\/doi.org\/10.48550\/arXiv.2006.08381 arxiv:2006.08381. Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, and Joshua B Tenenbaum. 2020. Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning. https:\/\/doi.org\/10.48550\/arXiv.2006.08381 arxiv:2006.08381."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140587.3062355"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3296979.3192382"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737977"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/P16-1154"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491411.2491461"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1997.9.8.1735"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/103135.103139"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/P16-1002"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980983.2908117"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2020.102476"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Conference on Learning Representations (ICLR). International Conference on Learning Representations (ICLR)","author":"Diederik","unstructured":"Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization . In Proceedings of the International Conference on Learning Representations (ICLR). International Conference on Learning Representations (ICLR) , La Jolla, CA, USA. 1\u201315. Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In Proceedings of the International Conference on Learning Representations (ICLR). International Conference on Learning Representations (ICLR), La Jolla, CA, USA. 1\u201315."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/P18-1249"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.3115\/1557769.1557821"},{"key":"e_1_2_1_27_1","unstructured":"Marie-Anne Lachaux Baptiste Roziere Lowik Chanussot and Guillaume Lample. 2020. Unsupervised translation of programming languages. https:\/\/doi.org\/10.48550\/arXiv.2006.03511 arxiv:2006.03511.  Marie-Anne Lachaux Baptiste Roziere Lowik Chanussot and Guillaume Lample. 2020. Unsupervised translation of programming languages. https:\/\/doi.org\/10.48550\/arXiv.2006.03511 arxiv:2006.03511."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/578"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D15-1166"},{"key":"e_1_2_1_30_1","unstructured":"Benjamin Mariano Yanju Chen Yu Feng Greg Durrett and Isil Dillig. 2022. Automated Transpilation of Imperative to Functional Code using Neural-Guided Program Synthesis (Extended Version). https:\/\/doi.org\/10.48550\/arXiv.2203.09452 arxiv:2203.09452.  Benjamin Mariano Yanju Chen Yu Feng Greg Durrett and Isil Dillig. 2022. Automated Transpilation of Imperative to Functional Code using Neural-Guided Program Synthesis (Extended Version). https:\/\/doi.org\/10.48550\/arXiv.2203.09452 arxiv:2203.09452."},{"key":"e_1_2_1_31_1","volume-title":"Demystifying Loops in Smart Contracts. In 2020 35th IEEE\/ACM International Conference on Automated Software Engineering (ASE). IEEE","author":"Mariano Benjamin","year":"2020","unstructured":"Benjamin Mariano , Yanju Chen , Yu Feng , Shuvendu K Lahiri , and Isil Dillig . 2020 . Demystifying Loops in Smart Contracts. In 2020 35th IEEE\/ACM International Conference on Automated Software Engineering (ASE). IEEE , New York, NY, USA. 262\u2013274. Benjamin Mariano, Yanju Chen, Yu Feng, Shuvendu K Lahiri, and Isil Dillig. 2020. Demystifying Loops in Smart Contracts. In 2020 35th IEEE\/ACM International Conference on Automated Software Engineering (ASE). IEEE, New York, NY, USA. 262\u2013274."},{"key":"e_1_2_1_32_1","unstructured":"Maxwell I Nye Armando Solar-Lezama Joshua B Tenenbaum and Brenden M Lake. 2020. Learning compositional rules via neural program synthesis. https:\/\/doi.org\/10.48550\/arXiv.2003.05562 arxiv:2003.05562.  Maxwell I Nye Armando Solar-Lezama Joshua B Tenenbaum and Brenden M Lake. 2020. Learning compositional rules via neural program synthesis. https:\/\/doi.org\/10.48550\/arXiv.2003.05562 arxiv:2003.05562."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 30th International Conference on Machine Learning, Sanjoy Dasgupta and David McAllester (Eds.) (Proceedings of Machine Learning Research","volume":"1318","author":"Pascanu Razvan","year":"2013","unstructured":"Razvan Pascanu , Tomas Mikolov , and Yoshua Bengio . 2013 . On the difficulty of training recurrent neural networks . In Proceedings of the 30th International Conference on Machine Learning, Sanjoy Dasgupta and David McAllester (Eds.) (Proceedings of Machine Learning Research , Vol. 28). PMLR, Atlanta, Georgia, USA. 1310\u2013 1318 . http:\/\/proceedings.mlr.press\/v28\/pascanu13.html Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. 2013. On the difficulty of training recurrent neural networks. In Proceedings of the 30th International Conference on Machine Learning, Sanjoy Dasgupta and David McAllester (Eds.) (Proceedings of Machine Learning Research, Vol. 28). PMLR, Atlanta, Georgia, USA. 1310\u20131318. http:\/\/proceedings.mlr.press\/v28\/pascanu13.html"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980983.2908093"},{"key":"e_1_2_1_35_1","unstructured":"Maxim Rabinovich Mitchell Stern and Dan Klein. 2017. Abstract syntax networks for code generation and semantic parsing. https:\/\/doi.org\/10.48550\/arXiv.1704.07535 arxiv:1704.07535.  Maxim Rabinovich Mitchell Stern and Dan Klein. 2017. Abstract syntax networks for code generation and semantic parsing. https:\/\/doi.org\/10.48550\/arXiv.1704.07535 arxiv:1704.07535."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660228"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815418"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/P17-1099"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095430.1081750"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980983.2908102"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250754"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2670313"},{"key":"e_1_2_1_43_1","unstructured":"Ilya Sutskever Oriol Vinyals and Quoc V Le. 2014. Sequence to sequence learning with neural networks. https:\/\/doi.org\/10.48550\/arXiv.1409.3215 arxiv:1409.3215.  Ilya Sutskever Oriol Vinyals and Quoc V Le. 2014. Sequence to sequence learning with neural networks. https:\/\/doi.org\/10.48550\/arXiv.1409.3215 arxiv:1409.3215."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509578.2509586"},{"key":"e_1_2_1_45_1","unstructured":"Xi Ye Qiaochu Chen Isil Dillig and Greg Durrett. 2020. Optimal Neural Program Synthesis from Multimodal Specifications. https:\/\/doi.org\/10.48550\/arXiv.2010.01678 arxiv:2010.01678.  Xi Ye Qiaochu Chen Isil Dillig and Greg Durrett. 2020. Optimal Neural Program Synthesis from Multimodal Specifications. https:\/\/doi.org\/10.48550\/arXiv.2010.01678 arxiv:2010.01678."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3527315","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3527315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:18:52Z","timestamp":1750177132000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3527315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,29]]},"references-count":45,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2022,4,29]]}},"alternative-id":["10.1145\/3527315"],"URL":"https:\/\/doi.org\/10.1145\/3527315","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,29]]},"assertion":[{"value":"2022-04-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}