{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:34:02Z","timestamp":1767929642814,"version":"3.49.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["No. SQ2019YFE010068"],"award-info":[{"award-number":["No. SQ2019YFE010068"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["Nos. 61922003, 61672045, 61620106007"],"award-info":[{"award-number":["Nos. 61922003, 61672045, 61620106007"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,11,13]]},"abstract":"<jats:p>Programming by example (PBE) is an important subproblem of program synthesis, and PBE techniques have been applied to many domains. Though many techniques for accelerating PBE systems have been explored, the scalability remains one of the main challenges: There is still a gap between the performances of state-of-the-art synthesizers and the industrial requirement. To further speed up solving PBE tasks, in this paper, we propose a novel PBE framework MaxFlash. MaxFlash uses a model based on structural probability, named topdown prediction models, to guide a search based on dynamic programming, such that the search will focus on subproblems that form probable programs, and avoid improbable programs. Our evaluation shows that MaxFlash achieves \u00d7 4.107\u2212 \u00d7 2080 speed-ups against state-of-the-art solvers on 244 real-world tasks.<\/jats:p>","DOI":"10.1145\/3428292","type":"journal-article","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T23:40:14Z","timestamp":1606261214000},"page":"1-29","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Guiding dynamic programing via structural probability for accelerating programming by example"],"prefix":"10.1145","volume":"4","author":[{"given":"Ruyi","family":"Ji","sequence":"first","affiliation":[{"name":"Peking University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yican","family":"Sun","sequence":"additional","affiliation":[{"name":"Peking University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yingfei","family":"Xiong","sequence":"additional","affiliation":[{"name":"Peking University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenjiang","family":"Hu","sequence":"additional","affiliation":[{"name":"Peking University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290353"},{"key":"e_1_2_2_2_1","volume-title":"SyGuS-Comp 2018: Results and Analysis. CoRR abs\/","author":"Alur Rajeev","year":"1904","unstructured":"Rajeev Alur , Dana Fisman , Saswat Padhi , Rishabh Singh , and Abhishek Udupa . 2019. SyGuS-Comp 2018: Results and Analysis. CoRR abs\/ 1904 .07146 ( 2019 ). arXiv: 1904.07146 https:\/\/2.zoppoz.workers.dev:443\/http\/arxiv.org\/abs\/ 1904.07146 Rajeev Alur, Dana Fisman, Saswat Padhi, Rishabh Singh, and Abhishek Udupa. 2019. SyGuS-Comp 2018: Results and Analysis. CoRR abs\/ 1904.07146 ( 2019 ). arXiv: 1904.07146 https:\/\/2.zoppoz.workers.dev:443\/http\/arxiv.org\/abs\/ 1904.07146"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.229.13"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.260.9"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54577-5_18"},{"key":"e_1_2_2_6_1","volume-title":"5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. https:\/\/2.zoppoz.workers.dev:443\/https\/openreview.net\/forum?id=ByldLrqlx","author":"Balog Matej","year":"2017","unstructured":"Matej Balog , Alexander L. Gaunt , Marc Brockschmidt , Sebastian Nowozin , and Daniel Tarlow . 2017 . DeepCoder: Learning to Write Programs . In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. https:\/\/2.zoppoz.workers.dev:443\/https\/openreview.net\/forum?id=ByldLrqlx Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. 2017. DeepCoder: Learning to Write Programs. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. https:\/\/2.zoppoz.workers.dev:443\/https\/openreview.net\/forum?id=ByldLrqlx"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737952"},{"key":"e_1_2_2_8_1","volume-title":"Proceedings of the 33nd International Conference on Machine Learning, ICML 2016","author":"Bielik Pavol","year":"2016","unstructured":"Pavol Bielik , Veselin Raychev , and Martin T. Vechev . 2016. PHOG: Probabilistic Model for Code . In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016 , New York City, NY, USA , June 19-24, 2016 . 2933-2942. https:\/\/2.zoppoz.workers.dev:443\/http\/proceedings.mlr.press\/v48\/bielik16.html Pavol Bielik, Veselin Raychev, and Martin T. Vechev. 2016. PHOG: Probabilistic Model for Code. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016. 2933-2942. https:\/\/2.zoppoz.workers.dev:443\/http\/proceedings.mlr.press\/v48\/bielik16.html"},{"key":"e_1_2_2_9_1","doi-asserted-by":"crossref","unstructured":"Qiaochu Chen Xinyu Wang Xi Ye Greg Durrett and Isil Dillig. 2020. Multi-Modal Synthesis of Regular Expressions. ( 2020 ).  Qiaochu Chen Xinyu Wang Xi Ye Greg Durrett and Isil Dillig. 2020. Multi-Modal Synthesis of Regular Expressions. ( 2020 ).","DOI":"10.1145\/3385412.3385988"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3338951"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML 2017","author":"Devlin Jacob","year":"2017","unstructured":"Jacob Devlin , Jonathan Uesato , Surya Bhupatiraju , Rishabh Singh , Abdel-rahman Mohamed, and Pushmeet Kohli . 2017 . RobustFill: Neural Program Learning under Noisy I\/O . In Proceedings of the 34th International Conference on Machine Learning, ICML 2017 , Sydney, NSW, Australia , 6-11 August 2017. 990-998. https:\/\/2.zoppoz.workers.dev:443\/http\/proceedings.mlr.press\/v70\/devlin17a.html Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. 2017. RobustFill: Neural Program Learning under Noisy I\/O. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017. 990-998. https:\/\/2.zoppoz.workers.dev:443\/http\/proceedings.mlr.press\/v70\/devlin17a.html"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062351"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90045-P"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926423"},{"key":"e_1_2_2_15_1","volume-title":"6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30-May 3, 2018, Conference Track Proceedings. https:\/\/2.zoppoz.workers.dev:443\/https\/openreview. net\/forum?id=rywDjg-RW","author":"Kalyan Ashwin","year":"2018","unstructured":"Ashwin Kalyan , Abhishek Mohta , Oleksandr Polozov , Dhruv Batra , Prateek Jain , and Sumit Gulwani . 2018 . NeuralGuided Deductive Search for Real-Time Program Synthesis from Examples . In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30-May 3, 2018, Conference Track Proceedings. https:\/\/2.zoppoz.workers.dev:443\/https\/openreview. net\/forum?id=rywDjg-RW Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. 2018. NeuralGuided Deductive Search for Real-Time Program Synthesis from Examples. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30-May 3, 2018, Conference Track Proceedings. https:\/\/2.zoppoz.workers.dev:443\/https\/openreview. net\/forum?id=rywDjg-RW"},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015","author":"Kini Dileep","year":"2015","unstructured":"Dileep Kini and Sumit Gulwani . 2015 . FlashNormalize: Programming by Examples for Text Normalization . In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015 , Buenos Aires, Argentina , July 25-31, 2015. 776-783. https:\/\/2.zoppoz.workers.dev:443\/http\/ijcai.org\/Abstract\/15\/115 Dileep Kini and Sumit Gulwani. 2015. FlashNormalize: Programming by Examples for Text Normalization. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015. 776-783. https:\/\/2.zoppoz.workers.dev:443\/http\/ijcai.org\/Abstract\/15\/115"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(85)90084-0"},{"key":"e_1_2_2_18_1","volume-title":"Doig","author":"Land Ailsa H.","year":"1960","unstructured":"Ailsa H. Land and Alison G . Doig . 1960 . An Automatic Method of Solving Discrete Programming Problems. Econometrica 28 ( 1960 ), 497-520. Ailsa H. Land and Alison G. Doig. 1960. An Automatic Method of Solving Discrete Programming Problems. Econometrica 28 ( 1960 ), 497-520."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594333"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192410"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the 30th International Conference on Machine Learning, ICML 2013","author":"Menon Aditya Krishna","year":"2013","unstructured":"Aditya Krishna Menon , Omer Tamuz , Sumit Gulwani , Butler W. Lampson , and Adam Kalai . 2013 . 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. 187-195. https:\/\/2.zoppoz.workers.dev:443\/http\/proceedings.mlr.press\/v28\/menon13.html Aditya Krishna Menon, Omer Tamuz, Sumit Gulwani, Butler W. Lampson, and Adam Kalai. 2013. 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. 187-195. https:\/\/2.zoppoz.workers.dev:443\/http\/proceedings.mlr.press\/v28\/menon13.html"},{"key":"e_1_2_2_22_1","volume-title":"5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. https:\/\/2.zoppoz.workers.dev:443\/https\/openreview.net\/forum?id=ry2YOrcge","author":"Neelakantan Arvind","year":"2017","unstructured":"Arvind Neelakantan , Quoc V. Le , Mart\u00edn Abadi , Andrew McCallum , and Dario Amodei . 2017 . Learning a Natural Language Interface with Neural Programmer . In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. https:\/\/2.zoppoz.workers.dev:443\/https\/openreview.net\/forum?id=ry2YOrcge Arvind Neelakantan, Quoc V. Le, Mart\u00edn Abadi, Andrew McCallum, and Dario Amodei. 2017. Learning a Natural Language Interface with Neural Programmer. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. https:\/\/2.zoppoz.workers.dev:443\/https\/openreview.net\/forum?id=ry2YOrcge"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276520"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814310"},{"key":"e_1_2_2_25_1","volume-title":"5th Workshop on Synthesis (SYNT).","author":"Polozov Oleksandr","year":"2016","unstructured":"Oleksandr Polozov and Sumit Gulwani . 2016 . Program synthesis in the industrial world: Inductive, incremental, interactive . In 5th Workshop on Synthesis (SYNT). Oleksandr Polozov and Sumit Gulwani. 2016. Program synthesis in the industrial world: Inductive, incremental, interactive. In 5th Workshop on Synthesis (SYNT)."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25543-5_5"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21668-3_12"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-017-0270-2"},{"key":"e_1_2_2_29_1","volume-title":"Inferring LISP Programs From Examples. In Advance Papers of the Fourth International Joint Conference on Artificial Intelligence","author":"Shaw David E.","year":"1975","unstructured":"David E. Shaw , William R. Swartout , and C. Cordell Green . 1975 . Inferring LISP Programs From Examples. In Advance Papers of the Fourth International Joint Conference on Artificial Intelligence , Tbilisi, Georgia, USSR , September 3-8, 1975 . 260-267. https:\/\/2.zoppoz.workers.dev:443\/http\/ijcai.org\/Proceedings\/75\/Papers\/037.pdf David E. Shaw, William R. Swartout, and C. Cordell Green. 1975. Inferring LISP Programs From Examples. In Advance Papers of the Fourth International Joint Conference on Artificial Intelligence, Tbilisi, Georgia, USSR, September 3-8, 1975. 260-267. https:\/\/2.zoppoz.workers.dev:443\/http\/ijcai.org\/Proceedings\/75\/Papers\/037.pdf"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212356"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168907"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062365"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96145-3_22"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158151"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3194810.3194816"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908088"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2013.6693082"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3428292","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/3428292","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:58Z","timestamp":1750197778000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3428292"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":37,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2020,11,13]]}},"alternative-id":["10.1145\/3428292"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/3428292","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,13]]},"assertion":[{"value":"2020-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}