{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T14:28:23Z","timestamp":1754144903497,"version":"3.41.2"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","funder":[{"DOI":"10.13039\/100019678","name":"Carnegie Mellon Portugal","doi-asserted-by":"publisher","award":["SFRH\/BD\/151467\/2021"],"award-info":[{"award-number":["SFRH\/BD\/151467\/2021"]}],"id":[{"id":"10.13039\/100019678","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":[[2025,6,10]]},"abstract":"<jats:p>We present the first technique to synthesize programs that compose side-effecting functions, pure functions, and control flow, from partial traces containing records of only the side-effecting functions. This technique can be applied to synthesize API composing scripts from logs of calls made to those APIs, or a script from traces of system calls made by a workload, for example. All of the provided traces are positive examples, meaning that they describe desired behavior. Our approach does not require negative examples. Instead, it generalizes over the examples and uses cost metrics to prevent over-generalization. Because the problem is too complex for traditional monolithic program synthesis techniques, we propose a new combination of optimizing rewrites and syntax-guided program synthesis. The resulting program is correct by construction, so its output will always be able to reproduce the input traces.  \nWe evaluate the quality of the programs synthesized when considering various optimization metrics and the synthesizer's efficiency on real-world benchmarks. The results show that our approach can generate useful real-world programs.<\/jats:p>","DOI":"10.1145\/3729316","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"1642-1665","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Program Synthesis from Partial Traces"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1170-5124","authenticated-orcid":false,"given":"Margarida","family":"Ferreira","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"},{"name":"INESC-ID, Lisbon, Portugal"},{"name":"Instituto Superior T\u00e9cnico - University of Lisbon, Lisbon, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3743-7498","authenticated-orcid":false,"given":"Victor","family":"Nicolet","sequence":"additional","affiliation":[{"name":"Amazon, Toronto, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-1534-6968","authenticated-orcid":false,"given":"Joey","family":"Dodds","sequence":"additional","affiliation":[{"name":"Amazon, Portland, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6681-5283","authenticated-orcid":false,"given":"Daniel","family":"Kroening","sequence":"additional","affiliation":[{"name":"Amazon, Seattle, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2013.6679385"},{"key":"e_1_2_2_2_1","unstructured":"Anthropic. 2024. Introducing Claude 3.5 Sonnnet. https:\/\/www.anthropic.com\/news\/claude-3-5-sonnet"},{"key":"e_1_2_2_3_1","unstructured":"AWS. 2023. AWS Automation Runbooks Reference. https:\/\/docs.aws.amazon.com\/systems-manager-automation-runbooks\/latest\/userguide\/automation-runbook-reference.html"},{"key":"e_1_2_2_4_1","unstructured":"AWS. 2023. What is AWS? https:\/\/aws.amazon.com\/what-is-aws\/"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99524-9_24"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984020"},{"key":"e_1_2_2_7_1","unstructured":"Blink. 2023. Blink | The Security Automation Copilot. https:\/\/www.blinkops.com\/"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-57259-3_11"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","unstructured":"Tim Bray. 2017. The JavaScript Object Notation (JSON) Data Interchange Format. RFC 8259. https:\/\/doi.org\/10.17487\/RFC8259 10.17487\/RFC8259","DOI":"10.17487\/RFC8259"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908103"},{"volume-title":"Allen Cypher","year":"2032","key":"e_1_2_2_11_1","unstructured":"1993. Watch what I do: programming by demonstration, Allen Cypher, Daniel C. Halbert, David Kurlander, Henry Lieberman, David Maulsby, Brad A. Myers, and Alan Turransky (Eds.). MIT Press, Cambridge, MA, USA. isbn:0262032139"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523711"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009851"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","unstructured":"Margarida Ferreira Victor Nicolet Joey Dodds and Daniel Kroening. 2025. Program Synthesis from Partial Traces. https:\/\/doi.org\/10.48550\/arXiv.2504.14480 arxiv:2504.14480. 10.48550\/arXiv.2504.14480","DOI":"10.48550\/arXiv.2504.14480"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3646547.3688443"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4842-4330-5_10"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1561\/2500000010"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523450"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371080"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","unstructured":"Sankha Narayan Guria Jeffrey S. Foster and David Van Horn. 2021. RbSyn: Type- and Effect-Guided Program Synthesis. In PLDI. ACM Virtual Canada. 344\u2013358. isbn:9781450383912 https:\/\/doi.org\/10.1145\/3453483.3454048 10.1145\/3453483.3454048","DOI":"10.1145\/3453483.3454048"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/DAC18072.2020.9218613"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512566"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591272"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332165.3347899"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632894"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3689789"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386012"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","unstructured":"Victor Nicolet and Margarida Ferreira. 2025. Program Synthesis From Partial Traces (Software Artifact). https:\/\/doi.org\/10.5281\/zenodo.15047359 10.5281\/zenodo.15047359","DOI":"10.5281\/zenodo.15047359"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","unstructured":"Saswat Padhi Elizabeth Polgreen Mukund Raghothaman Andrew Reynolds and Abhishek Udupa. 2023. The SyGuS Language Standard Version 2.1. https:\/\/doi.org\/10.48550\/arXiv.2312.06001 arxiv:2312.06001. 10.48550\/arXiv.2312.06001","DOI":"10.48550\/arXiv.2312.06001"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2714064.2660228"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451150"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314591"},{"key":"e_1_2_2_34_1","volume-title":"NeurIPS. Curran Associates","author":"Shin Richard","year":"2018","unstructured":"Richard Shin, Illia Polosukhin, and Dawn Song. 2018. Improving Neural Program Synthesis with Inferred Execution Traces. In NeurIPS. Curran Associates, Inc., Montr\u00e9al, Canada. 8931\u20138940. https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/7776e88b0c189539098176589250bcba-Abstract.html"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594340"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)00270-1"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","unstructured":"Qiongwen Xu Michael D. Wong Tanvi Wagle Srinivas Narayana and Anirudh Sivaraman. 2021. Synthesizing safe and efficient kernel extensions for packet processing. In SIGCOMM. ACM Virtal (online). 50\u201364. https:\/\/doi.org\/10.1145\/3452296.3472929 10.1145\/3452296.3472929","DOI":"10.1145\/3452296.3472929"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","unstructured":"Kuat Yessenov Ivan Kuraj and Armando Solar-Lezama. 2017. DemoMatch: API discovery from demonstrations. In PLDI. ACM Barcelona Spain. 64\u201378. https:\/\/doi.org\/10.1145\/3062341.3062386 10.1145\/3062341.3062386","DOI":"10.1145\/3062341.3062386"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729316","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T06:08:17Z","timestamp":1752646097000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729316"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":38,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729316"],"URL":"https:\/\/doi.org\/10.1145\/3729316","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}