Elamur Research⌕
☰
home / papers / 2019 / Learning to Infer Program Sketches

Learning to Infer Program Sketches

Paper · 2019 · Maxwell Nye, Luke Hewitt, Joshua Tenenbaum et al.

Summary

The paper addresses program synthesis from specifications that people find easy to give, namely input-output examples and natural-language descriptions. Earlier neuro-symbolic systems used fixed, hand-designed sketch grammars. In those systems, a neural network predicts a partial program and a symbolic search completes it, but the network cannot adjust how much of the program it fills in. The authors present SketchAdapt. It pairs a recurrent sequence-to-sequence sketch generator with an enumerative synthesizer. A sketch is any valid DSL program in which some subtrees are replaced by a <HOLE> token. Training is self-supervised. In each step a search budget is sampled at random, and the generator learns to favour sketches that the synthesizer can complete within that budget. As a result, the model writes detailed sketches for familiar tasks and leaves more holes for unfamiliar ones. The system was evaluated on list processing, string editing and the AlgoLisp English-to-code dataset. It reached state-of-the-art results on AlgoLisp and generalized better than a pure RNN when training data was scarce or concepts were unseen. This supports combining learned pattern recognition with explicit search.

Key points

  • On AlgoLisp, with a 300-second limit per task and beam size 10, SketchAdapt reached 90.0% test accuracy on the full dataset and 95.8% on the filtered set. The previous systems SAPS and Seq2Tree+Search scored 85.2% and 85.8% on the full dataset.
  • A "Generator only" RNN baseline was nearly as accurate as SketchAdapt on the full data (88.6% test). A "Synthesizer only" baseline reached only 7.3%. With smaller training subsets, SketchAdapt clearly outperformed the RNN baseline.
  • In a held-out-concept test, the models were trained on 8000 programs that never contained the 'odd' lambda (x%2==1). SketchAdapt then solved 29.8% of the 635 'odd' test tasks and 34.4% of the 638 'even' tasks. According to the authors, the RNN baseline largely failed on 'odd'.
  • Using only input-output examples on AlgoLisp gave just 8.3% test accuracy. The natural-language descriptions are therefore essential in this domain.
  • The paper was published at ICML 2019 (PMLR 97) by authors from MIT and the MIT-IBM Watson AI Lab.

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

 Institutions

🎓Massachusetts Institute of TechnologyCambridge · United States274 works · 82,013 citations

 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 Maxwell Nye, Luke Hewitt, Joshua Tenenbaum and Armando Solar-Lezama. 2019. Learning to Infer Program Sketches. arXiv:1902.06349.

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

@misc{nye2019learning,
  title = {{Learning to Infer Program Sketches}},
  author = {Maxwell Nye, Luke Hewitt, Joshua Tenenbaum and Armando Solar-Lezama},
  year = {2019},
  doi = {10.48550/arxiv.1902.06349},
  eprint = {1902.06349},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1902.06349}
}

References

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

  1. Alur, R., Fisman, D., Singh, R., and Solar-Lezama, A. Sygus-comp 2016: Results and analysis. arXiv preprint arXiv:1611.07627, 2016. — [arXiv:1611.07627](https://arxiv.org/abs/1611.07627) find
  2. Balog, M., Gaunt, A. L., Brockschmidt, M., Nowozin, S., and Tarlow, D. Deepcoder: Learning to write programs. arXiv preprint arXiv:1611.01989, 2016. find
  3. Bednarek, J., Piaskowski, K., and Krawiec, K. Ain’t nobody got time for coding: Structure-aware program synthesis from natural language. arXiv preprint arXiv:1810.09717, 2018. — [arXiv:1810.09717](https://arxiv.org/abs/1810.09717) find
  4. Bodik, R., Chandra, S., Galenson, J., Kimelman, D., Tung, N., Barman, S., and Rodarmor, C. Programming with angelic nondeterminism. In ACM Sigplan Notices, volume 45, pp. 339–352. ACM, 2010. find
  5. Bošnjak, M., Rocktäschel, T., Naradowsky, J., and Riedel, S. Programming with a differentiable forth interpreter. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp. 547–556. JMLR. org, 2017.
  6. Bunel, R., Hausknecht, M., Devlin, J., Singh, R., and Kohli, P. Leveraging grammar and reinforcement learning for neural program synthesis. arXiv preprint arXiv:1805.04276, 2018.
  7. Chen, X., Liu, C., and Song, D. Towards synthesizing complex programs from input-output examples. arXiv preprint arXiv:1706.01284, 2017. find
  8. Dechter, E., Malmaud, J., Adams, R. P., and Tenenbaum, J. B. Bootstrap learning via modular concept discovery. In IJCAI, pp. 1302–1309, 2013. find
  9. Devlin, J., Uesato, J., Bhupatiraju, S., Singh, R., Mohamed, A.-r., and Kohli, P. Robustfill: Neural program learning under noisy i/o. arXiv preprint arXiv:1703.07469, 2017. find
  10. Dong, L. and Lapata, M. Coarse-to-fine decoding for neural semantic parsing. arXiv preprint arXiv:1805.04793, 2018. find
  11. Ellis, K., Morales, L., Sablé-Meyer, M., Solar-Lezama, A., and Tenenbaum, J. Learning libraries of subroutines for neurally–guided bayesian program learning. NIPS, 2018. find
  12. Feser, J. K., Chaudhuri, S., and Dillig, I. Synthesizing data structure transformations from input-output examples. In ACM SIGPLAN Notices, volume 50, pp. 229–239. ACM, 2015. find
  13. Gulwani, S. Automating string processing in spreadsheets using input-output examples. In ACM SIGPLAN Notices, volume 46, pp. 317–330. ACM, 2011.
  14. Kalyan, A., Mohta, A., Polozov, O., Batra, D., Jain, P., and Gulwani, S. Neural-guided deductive search for real-time program synthesis from examples. 2018. find
  15. Kingma, D. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
  16. Lake, B. M., Salakhutdinov, R., and Tenenbaum, J. B. Human-level concept learning through probabilistic program induction. Science, 350(6266):1332–1338, 2015. find
  17. Lake, B. M., Ullman, T. D., Tenenbaum, J. B., and Gershman, S. J. Building machines that learn and think like people. Behavioral and Brain Sciences, 40, 2017. find
  18. Le, T. A., Baydin, A. G., and Wood, F. Inference compilation and universal probabilistic programming. arXiv preprint arXiv:1610.09900, 2016. — [arXiv:1610.09900](https://arxiv.org/abs/1610.09900) find
  19. Menon, A., Tamuz, O., Gulwani, S., Lampson, B., and Kalai, A. A machine learning framework for programming by example. In International Conference on Machine Learning, pp. 187–195, 2013. find
  20. Murali, V., Qi, L., Chaudhuri, S., and Jermaine, C. Neural sketch learning for conditional program generation. arXiv preprint arXiv:1703.05698, 2017. find
  21. Parisotto, E., Mohamed, A.-r., Singh, R., Li, L., Zhou, D., and Kohli, P. Neuro-symbolic program synthesis. arXiv preprint arXiv:1611.01855, 2016.
  22. Polosukhin, I. and Skidanov, A. Neural program search: Solving programming tasks from description and examples. arXiv preprint arXiv:1802.04335, 2018. find
  23. Polozov, O. and Gulwani, S. Flashmeta: a framework for inductive program synthesis. In ACM SIGPLAN Notices, volume 50, pp. 107–126. ACM, 2015. find
  24. Schkufza, E., Sharma, R., and Aiken, A. Stochastic program optimization. Communications of the ACM, 59(2):114– 122, 2016. find
  25. Shin, R., Polosukhin, I., and Song, D. Improving neural program synthesis with inferred execution traces. In Advances in Neural Information Processing Systems, pp. 8931–8940, 2018. find
  26. Solar-Lezama, A. Program synthesis by sketching. PhD thesis, University of California, Berkeley, 2008.
  27. Zhang, L., Rosenblatt, G., Fetaya, E., Liao, R., Byrd, W., Might, M., Urtasun, R., and Zemel, R. Neural guided constraint logic programming for program synthesis. In Advances in Neural Information Processing Systems, pp. 1744–1753, 2018. find
  28. Zohar, A. and Wolf, L. Automatic program synthesis of long programs with a learned garbage collector. In Advances in Neural Information Processing Systems, pp. 2098–2107, 2018. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/nye-2019-learning-infer-program-sketches/