Elamur Research⌕
☰
home / papers / 2019 / Write, Execute, Assess: Program Synthesis with a REPL

Write, Execute, Assess: Program Synthesis with a REPL

Paper · 2019 · Kevin Ellis, Maxwell Nye, Yewen Pu et al.

Summary

Program synthesis is difficult because a small syntactic edit can drastically change what a program does, and neural networks struggle to learn this mapping. Ellis et al. address this by letting the synthesizer run its partial code in an interpreter (REPL), so decisions depend on execution results rather than raw syntax. They frame synthesis as a goal-conditioned Markov decision process over sets of partial programs. They train two networks in the spirit of AlphaGo. The first is a policy that proposes the next production rule. The second is a value function that estimates whether the current state can still lead to a correct program. Training starts with imitation on randomly sampled programs and continues with REINFORCE-style fine-tuning. At test time, both networks guide a Sequential Monte Carlo search that samples, executes, reweights and prunes candidate programs. The authors evaluate the method on 2D/3D CSG graphics (inverse CAD) and FlashFill-style string editing. In both domains it finds correct programs faster and more reliably than the alternatives. This suggests that ordinary programmer tools can usefully become components of learned synthesizers.

Key points

  • Core components: a policy π, a value function v (a binary success classifier), and a REPL that executes partial programs. These are combined in an SMC sampler and compared against policy rollouts, beam search and A* (each with and without the value function), and a reimplementation of RobustFill.
  • New benchmark: the authors built a harder string-editing benchmark of 87 problems drawn from 34 templates, covering addresses, dates/times, names and movie reviews. They did this because existing FlashFill-style tests were near ceiling for their model.
  • Efficiency: on string editing, value-guided SMC solved the most tasks, and compared with competing methods it needed about a tenth as many node expansions and ran faster. Adding the value function also improved beam search.
  • Generalization: training programs had at most 30 actions, averaging about 8. At test time, the system often produced programs of 40+ actions, which is more than 350 bits of description length.
  • Scale and future work: the 3D inverse CAD domain has a branching factor above 1.3 million per line of code. Future work targets control flow such as loops and conditionals, possibly via Forth-style stack languages.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksInformation Systems · 1,888 worksComputer Science Applications · 184 works

🧭 Topics 1Research subjects and languages the work is about.Code & programming languages · 194 works

Cite

Cite as Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum and Armando Solar-Lezama. 2019. Write, Execute, Assess: Program Synthesis with a REPL. arXiv:1906.04604.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1906.04604 · arXiv 1906.04604

@misc{ellis2019write,
  title = {{Write, Execute, Assess: Program Synthesis with a REPL}},
  author = {Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum and Armando Solar-Lezama},
  year = {2019},
  doi = {10.48550/arxiv.1906.04604},
  eprint = {1906.04604},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1906.04604}
}

References

23 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016. find
  2. Yaroslav Ganin, Tejas Kulkarni, Igor Babuschkin, SM Eslami, and Oriol Vinyals. Synthesizing programs for images using reinforced adversarial learning. arXiv preprint arXiv:1804.01118, 2018. find
  3. Jürgen Schmidhuber. Optimal ordered problem solver. Machine Learning, 54(3):211–254, 2004. find
  4. Kevin Ellis, Lucas Morales, Mathias Sablé-Meyer, Armando Solar-Lezama, and Josh Tenenbaum. Learning libraries of subroutines for neurally–guided bayesian program induction. In Advances in Neural Information Processing Systems, pages 7805–7815, 2018. find
  5. Matej Balog, Alexander L Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. arXiv preprint arXiv:1611.01989, 2016. find
  6. Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar-Lezama. Learning to infer program sketches. arXiv preprint arXiv:1902.06349, 2019.
  7. Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Josh Tenenbaum. Learning to infer graphics programs from hand-drawn images. In Advances in Neural Information Processing Systems, pages 6059–6068, 2018. find
  8. Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 990–998. JMLR. org, 2017. find
  9. Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. Neural-guided deductive search for real-time program synthesis from examples. arXiv preprint arXiv:1804.01186, 2018. — [arXiv:1804.01186](https://arxiv.org/abs/1804.01186) find
  10. Yonglong Tian, Andrew Luo, Xingyuan Sun, Kevin Ellis, William T Freeman, Joshua B Tenenbaum, and Jiajun Wu. Learning to infer and execute 3d shape programs. arXiv preprint arXiv:1901.02875, 2019. — [arXiv:1901.02875](https://arxiv.org/abs/1901.02875) find
  11. Yewen Pu, Zachery Miranda, Armando Solar-Lezama, and Leslie Kaelbling. Selecting representative examples for program synthesis. In International Conference on Machine Learning, pages 4158–4167, 2018. find
  12. Xinyun Chen, Chang Liu, and Dawn Song. Execution-guided neural program synthesis. 2018. find
  13. Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with a learned garbage collector. In Advances in Neural Information Processing Systems, pages 2094–2103, 2018. find
  14. Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In ACM Sigplan Notices, volume 46, pages 317–330. ACM, 2011.
  15. Arnaud Doucet, Nando De Freitas, and Neil Gordon. An introduction to sequential monte carlo methods. In Sequential Monte Carlo methods in practice, pages 3–14. Springer, 2001. find
  16. Gopal Sharma, Rishabh Goyal, Difan Liu, Evangelos Kalogerakis, and Subhransu Maji. Csgnet: Neural shape parser for constructive solid geometry. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5515–5523, 2018. find
  17. Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pages 2692–2700, 2015. find
  18. Tessa Lau. Programming by demonstration: a machine learning approach. PhD thesis, 2001. find
  19. Rajeev Alur, Dana Fisman, Rishabh Singh, and Armando Solar-Lezama. Sygus-comp 2016: Results and analysis. arXiv preprint arXiv:1611.07627, 2016. — [arXiv:1611.07627](https://arxiv.org/abs/1611.07627) find
  20. Tao Du, Jeevana Priya Inala, Yewen Pu, Andrew Spielberg, Adriana Schulz, Daniela Rus, Armando Solar-Lezama, and Wojciech Matusik. Inversecsg: Automatic conversion of 3d models to csg trees. ACM Trans. Graph., 37(6):213:1–213:16, December 2018. find
  21. Riley Simmons-Edler, Anders Miltner, and Sebastian Seung. Program synthesis through reinforcement learning guided tree search. arXiv preprint arXiv:1806.02932, 2018. — [arXiv:1806.02932](https://arxiv.org/abs/1806.02932) find
  22. Elizabeth D Rather, Donald R Colburn, and Charles H Moore. The evolution of forth. In ACM SIGPLAN Notices, volume 28, pages 177–199. ACM, 1993. find
  23. Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in neural information processing systems, pages 3391–3401, 2017. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/ellis-2019-write-execute-assess-program-synthesis/