We present a new algorithm that synthesizes functional reactive programs from observation data. The key novelty is to iterate between a functional synthesis step, which attempts to generate a transition function over observed states, and an automata synthesis 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.

@article{paperbot2063,
  title = {Combining Functional and Automata Synthesis to Discover Causal Reactive Programs},
  author = {Ria Das and Joshua B. Tenenbaum and Armando Solar-Lezama and Zenna Tavares},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {7},
  number = {POPL},
  year = {2023},
  doi = {10.1145/3571249}
}