{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:32:15Z","timestamp":1767929535680,"version":"3.49.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2019,1,2]],"date-time":"2019-01-02T00:00:00Z","timestamp":1546387200000},"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":[[2019,1,2]]},"abstract":"<jats:p>\n            In component-based program synthesis, the synthesizer generates a program given a library of components (functions). Existing component-based synthesizers have difficulty synthesizing loops and other control structures, and they often require formal specifications of the components, which can be expensive to generate. We present FrAngel, a new approach to component-based synthesis that can synthesize short Java functions with control structures when given a desired signature, a set of input-output examples, and a collection of libraries (without formal specifications). FrAngel aims to discover programs with many distinct behaviors by combining two main ideas. First, it\n            <jats:italic>mines code fragments<\/jats:italic>\n            from partially-successful programs that only pass some of the examples. These extracted fragments are often useful for synthesis due to a property that we call\n            <jats:italic>special-case similarity<\/jats:italic>\n            . Second, FrAngel uses\n            <jats:italic>angelic conditions<\/jats:italic>\n            as placeholders for control structure conditions and optimistically evaluates the resulting program sketches. Angelic conditions decompose the synthesis process: FrAngel first finds promising partial programs and later fills in their missing conditions. We demonstrate that FrAngel can synthesize a variety of interesting programs with combinations of control structures within seconds, significantly outperforming prior state-of-the-art.\n          <\/jats:p>","DOI":"10.1145\/3290386","type":"journal-article","created":{"date-parts":[[2019,1,4]],"date-time":"2019-01-04T13:33:51Z","timestamp":1546608831000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["FrAngel: component-based synthesis with control structures"],"prefix":"10.1145","volume":"3","author":[{"given":"Kensen","family":"Shi","sequence":"first","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Jacob","family":"Steinhardt","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Percy","family":"Liang","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,1,2]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Rajeev Alur Arjun Radhakrishna and Abhishek Udupa. 2017. Scaling Enumerative Program Synthesis via Divide and Conquer. In Tools and Algorithms for the Construction and Analysis of Systems (TACAS).  Rajeev Alur Arjun Radhakrishna and Abhishek Udupa. 2017. Scaling Enumerative Program Synthesis via Divide and Conquer. In Tools and Algorithms for the Construction and Analysis of Systems (TACAS).","DOI":"10.1007\/978-3-662-54577-5_18"},{"key":"e_1_2_2_2_1","volume-title":"International Conference on Learning Representations (ICLR).","author":"Balog Matej","year":"2017"},{"key":"e_1_2_2_3_1","volume-title":"Automatic Discovery of Mutual Exclusion Algorithms. In International Symposium on Distributed Computing (DISC) .","author":"Bar-David Yoah","year":"2003"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442529"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706299.1706339"},{"key":"e_1_2_2_6_1","volume-title":"International Conference on Machine Learning (ICML).","author":"Devlin Jacob","year":"2017"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062351"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009851"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737977"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2568225.2568250"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926423"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993506"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993505"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462192"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Tihomir Gvero Viktor Kuncak and Ruzica Piskac. 2011. Interactive Synthesis of Code Snippets. In Computer Aided Verification (CAV) .   Tihomir Gvero Viktor Kuncak and Ruzica Piskac. 2011. Interactive Synthesis of Code Snippets. In Computer Aided Verification (CAV) .","DOI":"10.1007\/978-3-642-22110-1_33"},{"key":"e_1_2_2_16_1","volume-title":"The Theory of Branching Processes","author":"Harris Theodore E"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993536"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908121"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786805.2786875"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806799.1806833"},{"key":"e_1_2_2_21_1","first-page":"111","article-title":"Systematic Search for Lambda Expressions","volume":"6","author":"Katayama Susumu","year":"2005","journal-title":"Trends in Functional Programming"},{"key":"e_1_2_2_22_1","volume-title":"International Conference on Machine Learning (ICML).","author":"Lau Tessa A","year":"2000"},{"key":"e_1_2_2_23_1","volume-title":"Structured Generative Models of Natural Source Code. In International Conference on Machine Learning (ICML) .","author":"Maddison Chris","year":"2014"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065018"},{"key":"e_1_2_2_25_1","volume-title":"International Conference on Machine Learning (ICML).","author":"Menon Aditya Krishna","year":"2013"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738007"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594297"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/WCRE.2012.51"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594321"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2863701"},{"key":"e_1_2_2_31_1","unstructured":"Kensen Shi Jacob Steinhardt and Percy Liang. 2018. FrAngel Source Code and Experimental Results. https:\/\/www.github. com\/kensens\/FrAngel .  Kensen Shi Jacob Steinhardt and Percy Liang. 2018. FrAngel Source Code and Experimental Results. https:\/\/www.github. com\/kensens\/FrAngel ."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706299.1706337"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2009.5070536"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908088"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3290386","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3290386","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:58:04Z","timestamp":1750208284000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3290386"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,2]]},"references-count":34,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2019,1,2]]}},"alternative-id":["10.1145\/3290386"],"URL":"https:\/\/doi.org\/10.1145\/3290386","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,2]]},"assertion":[{"value":"2019-01-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}