{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:07:52Z","timestamp":1784200072000,"version":"3.55.0"},"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. We evaluate the quality of the programs synthesized when considering various optimization metrics and the synthesizer\u2019s 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"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3743-7498","authenticated-orcid":false,"given":"Victor","family":"Nicolet","sequence":"additional","affiliation":[{"name":"Amazon, Toronto, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-1534-6968","authenticated-orcid":false,"given":"Joey","family":"Dodds","sequence":"additional","affiliation":[{"name":"Amazon, Portland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6681-5283","authenticated-orcid":false,"given":"Daniel","family":"Kroening","sequence":"additional","affiliation":[{"name":"Amazon, Seattle, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2013.6679385"},{"key":"e_1_3_2_3_1","unstructured":"Anthropic. 2024. Introducing Claude 3.5 Sonnnet. https:\/\/www.anthropic.com\/news\/claude-3-5-sonnet."},{"key":"e_1_3_2_4_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_3_2_5_1","unstructured":"AWS. 2023. What is AWS? https:\/\/aws.amazon.com\/what-is-aws\/."},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99524-9_24"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984020"},{"key":"e_1_3_2_8_1","unstructured":"Blink. 2023. Blink | The Security Automation Copilot. https:\/\/www.blinkops.com\/."},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-57259-3_11"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","unstructured":"Tim Bray. 2017. The JavaScript Object Notation (JSON) Data Interchange Format. RFC 8259. doi:https:\/\/doi.org\/10.17487\/RFC8259","DOI":"10.17487\/RFC8259"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908103"},{"key":"e_1_3_2_12_1","volume-title":"Watch what I do: programming by demonstration","author":"Cypher Allen","year":"1993","unstructured":"Allen Cypher, Daniel C. Halbert, David Kurlander, Henry Lieberman, David Maulsby, Brad A. Myers, and Alan Turransky(Eds.). 1993. Watch what I do: programming by demonstration. MIT Press, Cambridge, MA, USA."},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523711"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009851"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","unstructured":"Margarida Ferreira Victor Nicolet Joey Dodds and Daniel Kroening. 2025. Program Synthesis from Partial Traces. doi:https:\/\/doi.org\/10.48550\/arXiv.2504.14480 arXiv:2504.14480 [cs.PL]","DOI":"10.48550\/arXiv.2504.14480"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3646547.3688443"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4842-4330-5_10"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","unstructured":"Sumit Gulwani Oleksandr Polozov and Rishabh Singh. 2017. Program Synthesis Found. Trends Program. Lang. 4 1\u20132. (2017) 1-119. doi:https:\/\/doi.org\/10.1561\/2500000010","DOI":"10.1561\/2500000010"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523450"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371080"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454048"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/DAC18072.2020.9218613"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512566"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591272"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332165.3347899"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632894"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3689789"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386012"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.15047359"},{"key":"e_1_3_2_31_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.. doi:https:\/\/doi.org\/10.48550\/arXiv.2312.06001 arXiv:2312.06001 [cs.PL]","DOI":"10.48550\/arXiv.2312.06001"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2714064.2660228"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451150"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314591"},{"key":"e_1_3_2_35_1","first-page":"8931","volume-title":"NeurIPS","author":"Shin Richard","year":"2018","unstructured":"Richard Shin, Illia Polosukhin, and Dawn Song. 2018. Improving Neural Program Synthesis with Inferred Execution Traces. InNeurIPS. Curran Associates, Inc., Montr\u00e9al, Canada, 8931\u20138940. . https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/7776e88b0c189539098176589250bcba-Abstract.html"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594340"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)00270-1"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452296.3472929"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","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":[[2026,7,16]],"date-time":"2026-07-16T10:08:47Z","timestamp":1784196527000},"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":[{"value":"2475-1421","type":"electronic"}],"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"}}]}}