{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T18:04:30Z","timestamp":1759773870815,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T00:00:00Z","timestamp":1673222400000},"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":[[2023,1,9]]},"abstract":"<jats:p>\n            We present a new algorithm that synthesizes functional reactive programs from observation data. The key novelty is to iterate between a\n            <jats:italic>functional synthesis<\/jats:italic>\n            step, which attempts to generate a transition function over observed states, and an\n            <jats:italic>automata synthesis<\/jats:italic>\n            step, which adds any additional latent state necessary to fully account for the observations. We develop a functional reactive DSL called Autumn that can express a rich variety of causal dynamics in time-varying, Atari-style grid worlds, and apply our method to synthesize Autumn programs from data. We evaluate our algorithm on a benchmark suite of 30 Autumn programs as well as a third-party corpus of grid-world-style video games. We find that our algorithm synthesizes 27 out of 30 programs in our benchmark suite and 21 out of 27 programs from the third-party corpus, including several programs describing complex latent state transformations, and from input traces containing hundreds of observations. We expect that our approach will provide a template for how to integrate functional and automata synthesis in other induction domains.\n          <\/jats:p>","DOI":"10.1145\/3571249","type":"journal-article","created":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T21:58:14Z","timestamp":1673474294000},"page":"1628-1658","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Combining Functional and Automata Synthesis to Discover Causal Reactive Programs"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8623-8359","authenticated-orcid":false,"given":"Ria","family":"Das","sequence":"first","affiliation":[{"name":"Stanford University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1925-2035","authenticated-orcid":false,"given":"Joshua B.","family":"Tenenbaum","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7604-8252","authenticated-orcid":false,"given":"Armando","family":"Solar-Lezama","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2198-5385","authenticated-orcid":false,"given":"Zenna","family":"Tavares","sequence":"additional","affiliation":[{"name":"Basis, USA \/ Columbia University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,1,11]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96145-3_20"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535860"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.08.007"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1866307.1866355"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523429"},{"key":"#cr-split#-e_1_2_2_7_1.1","unstructured":"Fran\u00e7ois Chollet. 2019. On the Measure of Intelligence. https:\/\/doi.org\/10.48550\/ARXIV.1911.01547 10.48550\/ARXIV.1911.01547"},{"key":"#cr-split#-e_1_2_2_7_1.2","unstructured":"Fran\u00e7ois Chollet. 2019. On the Measure of Intelligence. https:\/\/doi.org\/10.48550\/ARXIV.1911.01547"},{"key":"e_1_2_2_8_1","volume-title":"On the Measure of Intelligence. CoRR, abs\/1911.01547","author":"Chollet Fran\u00e7ois","year":"2019","unstructured":"Fran\u00e7ois Chollet . 2019. On the Measure of Intelligence. CoRR, abs\/1911.01547 ( 2019 ), arXiv:1911.01547. arxiv:1911.01547 Fran\u00e7ois Chollet. 2019. On the Measure of Intelligence. CoRR, abs\/1911.01547 (2019), arXiv:1911.01547. arxiv:1911.01547"},{"key":"e_1_2_2_9_1","volume-title":"Zulu: An Interactive Learning Competition","author":"Combe David","year":"2010","unstructured":"David Combe , Colin de la Higuera , and Jean-Christophe Janodet . 2010 . Zulu: An Interactive Learning Competition . In Finite-State Methods and Natural Language Processing, Anssi Yli-Jyr\u00e4, Andr\u00e1s Kornai, Jacques Sakarovitch, and Bruce Watson (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg . 139\u2013146. isbn:978-3-642-14684-8 David Combe, Colin de la Higuera, and Jean-Christophe Janodet. 2010. Zulu: An Interactive Learning Competition. In Finite-State Methods and Natural Language Processing, Anssi Yli-Jyr\u00e4, Andr\u00e1s Kornai, Jacques Sakarovitch, and Bruce Watson (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 139\u2013146. isbn:978-3-642-14684-8"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462161"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54577-5_10"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275006"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-022-32012-w"},{"key":"e_1_2_2_14_1","volume-title":"Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015","author":"Ellis Kevin","year":"2015","unstructured":"Kevin Ellis , Armando Solar-Lezama , and Joshua B. Tenenbaum . 2015. Unsupervised Learning by Program Synthesis . In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015 , December 7-12, 2015 , Montreal, Quebec, Canada, Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (Eds.). 973\u2013981. https:\/\/proceedings.neurips.cc\/paper\/ 2015\/hash\/b73dfe25b4b8714c029b37a6ad3006fa-Abstract.html Kevin Ellis, Armando Solar-Lezama, and Joshua B. Tenenbaum. 2015. Unsupervised Learning by Program Synthesis. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (Eds.). 973\u2013981. https:\/\/proceedings.neurips.cc\/paper\/2015\/hash\/b73dfe25b4b8714c029b37a6ad3006fa-Abstract.html"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454080"},{"key":"e_1_2_2_16_1","volume-title":"Sergot","author":"Evans Richard","year":"2020","unstructured":"Richard Evans , Jos\u00e9 Hern\u00e1ndez-Orallo , Johannes Welbl , Pushmeet Kohli , and Marek J . Sergot . 2020 . Evaluating the Apperception Engine. ArXiv , abs\/2007.05367 (2020). Richard Evans, Jos\u00e9 Hern\u00e1ndez-Orallo, Johannes Welbl, Pushmeet Kohli, and Marek J. Sergot. 2020. Evaluating the Apperception Engine. ArXiv, abs\/2007.05367 (2020)."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103438"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331545.3342601"},{"key":"e_1_2_2_19_1","volume-title":"Bayesian learning mechanisms, and the theory theory.. Psychological bulletin, 138, 6","author":"Gopnik Alison","year":"2012","unstructured":"Alison Gopnik and Henry M Wellman . 2012. Reconstructing constructivism: causal models , Bayesian learning mechanisms, and the theory theory.. Psychological bulletin, 138, 6 ( 2012 ), 1085. Alison Gopnik and Henry M Wellman. 2012. Reconstructing constructivism: causal models, Bayesian learning mechanisms, and the theory theory.. Psychological bulletin, 138, 6 (2012), 1085."},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Matthew Guzdial Boyang Li and Mark O Riedl. 2017. Game Engine Learning from Video.. In IJCAI. 3707\u20133713. \t\t\t\t  Matthew Guzdial Boyang Li and Mark O Riedl. 2017. Game Engine Learning from Video.. In IJCAI. 3707\u20133713.","DOI":"10.24963\/ijcai.2017\/518"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429125"},{"key":"e_1_2_2_22_1","volume-title":"Marc Ebner, Graham Kendall, Simon M Lucas, Risto Miikkulainen, Tom Schaul, and Tommy Thompson.","author":"Levine John","year":"2013","unstructured":"John Levine , Clare Bates Congdon , Marc Ebner, Graham Kendall, Simon M Lucas, Risto Miikkulainen, Tom Schaul, and Tommy Thompson. 2013 . General video game playing. John Levine, Clare Bates Congdon, Marc Ebner, Graham Kendall, Simon M Lucas, Risto Miikkulainen, Tom Schaul, and Tommy Thompson. 2013. General video game playing."},{"key":"#cr-split#-e_1_2_2_23_1.1","unstructured":"Julie L Newcomb and Rastislav Bodik. 2019. Using human-in-the-loop synthesis to author functional reactive programs. https:\/\/doi.org\/10.48550\/ARXIV.1909.11206 10.48550\/ARXIV.1909.11206"},{"key":"#cr-split#-e_1_2_2_23_1.2","unstructured":"Julie L Newcomb and Rastislav Bodik. 2019. Using human-in-the-loop synthesis to author functional reactive programs. https:\/\/doi.org\/10.48550\/ARXIV.1909.11206"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89597"},{"volume-title":"Fundamental Approaches to Software Engineering","author":"Raffelt Harald","key":"e_1_2_2_25_1","unstructured":"Harald Raffelt and Bernhard Steffen . 2006. LearnLib: A Library for Automata Learning and Experimentation . In Fundamental Approaches to Software Engineering , Luciano Baresi and Reiko Heckel (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg . 377\u2013380. isbn:978-3-540-33094-3 Harald Raffelt and Bernhard Steffen. 2006. LearnLib: A Library for Automata Learning and Experimentation. In Fundamental Approaches to Software Engineering, Luciano Baresi and Reiko Heckel (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 377\u2013380. isbn:978-3-540-33094-3"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-012-0249-7"},{"key":"e_1_2_2_27_1","unstructured":"Megan Tjandrasuwita Jennifer J Sun Ann Kennedy Swarat Chaudhuri and Yisong Yue. 2021. Interpreting expert annotation differences in animal behavior. arXiv preprint arXiv:2106.06114. \t\t\t\t  Megan Tjandrasuwita Jennifer J Sun Ann Kennedy Swarat Chaudhuri and Yisong Yue. 2021. Interpreting expert annotation differences in animal behavior. arXiv preprint arXiv:2106.06114."},{"key":"e_1_2_2_28_1","volume-title":"Tenenbaum","author":"Tsividis Pedro A.","year":"2021","unstructured":"Pedro A. Tsividis , Joao Loula , Jake Burga , Nathan Foss , Andres Campero , Thomas Pouncy , Samuel J. Gershman , and Joshua B . Tenenbaum . 2021 . Human-Level Reinforcement Learning through Theory-Based Modeling, Exploration, and Planning . https:\/\/doi.org\/10.48550\/ARXIV.2107.12544 10.48550\/ARXIV.2107.12544 Pedro A. Tsividis, Joao Loula, Jake Burga, Nathan Foss, Andres Campero, Thomas Pouncy, Samuel J. Gershman, and Joshua B. Tenenbaum. 2021. Human-Level Reinforcement Learning through Theory-Based Modeling, Exploration, and Planning. https:\/\/doi.org\/10.48550\/ARXIV.2107.12544"},{"key":"e_1_2_2_29_1","doi-asserted-by":"crossref","unstructured":"Tomer D Ullman and Joshua B Tenenbaum. 2020. Bayesian models of conceptual development: Learning as building models of the world. Annual Review of Developmental Psychology. \t\t\t\t  Tomer D Ullman and Joshua B Tenenbaum. 2020. Bayesian models of conceptual development: Learning as building models of the world. Annual Review of Developmental Psychology.","DOI":"10.31234\/osf.io\/aq3rp"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2967606"},{"key":"e_1_2_2_31_1","volume-title":"Five ways in which computational modeling can help advance cognitive science: Lessons from artificial grammar learning. Topics in cognitive science, 12, 3","author":"Zuidema Willem","year":"2020","unstructured":"Willem Zuidema , Robert M French , Raquel G Alhama , Kevin Ellis , Timothy J O\u2019Donnell , Tim Sainburg , and Timothy Q Gentner . 2020. Five ways in which computational modeling can help advance cognitive science: Lessons from artificial grammar learning. Topics in cognitive science, 12, 3 ( 2020 ), 925\u2013941. Willem Zuidema, Robert M French, Raquel G Alhama, Kevin Ellis, Timothy J O\u2019Donnell, Tim Sainburg, and Timothy Q Gentner. 2020. Five ways in which computational modeling can help advance cognitive science: Lessons from artificial grammar learning. Topics in cognitive science, 12, 3 (2020), 925\u2013941."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571249","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3571249","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:22Z","timestamp":1750183702000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571249"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,9]]},"references-count":33,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2023,1,9]]}},"alternative-id":["10.1145\/3571249"],"URL":"https:\/\/doi.org\/10.1145\/3571249","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2023,1,9]]},"assertion":[{"value":"2023-01-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}