Elamur Research⌕
☰
home / papers / 2016 / Neuro-Symbolic Program Synthesis

Neuro-Symbolic Program Synthesis

Paper · 2016 · Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh et al.

Summary

Neural program-induction models usually learn an opaque mapping. They are expensive to train and need a separate model for every task. This paper instead addresses program synthesis: from a few input-output examples, it produces an explicit program in a domain-specific language (DSL) that reproduces them. A single model serves many tasks, and no hand-crafted search heuristics are needed.

The method has two neural parts. An encoder compresses the example set into a vector. Besides a plain bidirectional LSTM encoder, the authors propose a cross correlation I/O network that correlates LSTM representations of inputs and outputs. The Recursive-Reverse-Recursive Neural Network (R3NN) then builds a parse tree of the DSL grammar step by step. At each step it chooses which non-terminal to expand and which rule to apply, and every node's representation reflects the whole partial tree. Training data comes from randomly sampled programs, rule-generated inputs and the outputs obtained by running those programs.

On FlashFill-style regex string transformations, the system finds correct programs even for tasks unseen in training. This suggests that learned synthesis can be both interpretable and general.

Key points

  • The DSL is a large subset of the FlashFill language (Microsoft Excel 2013) without conditionals. It is built from Concat, ConstStr, SubStr and position logic, and uses 8 predefined regex token classes.
  • R3NN encodes a partial program tree in two passes: a recursive pass up to the root, then a reverse-recursive pass back down to every node.
  • With a single sample, the system solves 63% of tasks not seen during training. This rises to 94% when 100 program samples are drawn.
  • It solves 38% of 238 real-world FlashFill benchmarks.
  • Two I/O encoders were compared: an LSTM-concatenation encoder and the cross correlation encoder.

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

🏢MicrosoftRedmond · United States378 works · 161,630 citations🎓University of TorontoToronto · Canada110 works · 179,061 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksComputational Theory and Mathematics · 321 worksComputer Science Applications · 131 works

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

Cite

Cite as Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou and Pushmeet Kohli. 2016. Neuro-Symbolic Program Synthesis. arXiv:1611.01855.

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

@misc{parisotto2016neuro,
  title = {{Neuro-Symbolic Program Synthesis}},
  author = {Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou and Pushmeet Kohli},
  year = {2016},
  doi = {10.48550/arxiv.1611.01855},
  eprint = {1611.01855},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1611.01855}
}

References

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

  1. Alur, Rajeev, Bodı́k, Rastislav, Dallal, Eric, Fisman, Dana, Garg, Pranav, Juniwal, Garvit, Kress-Gazit, Hadas, Madhusudan, P., Martin, Milo M. K., Raghothaman, Mukund, Saha, Shamwaditya, Seshia, Sanjit A., Singh, Rishabh, Solar-Lezama, Armando, Torlak, Emina, and Udupa, Abhishek. Syntax-guided synt… find
  2. Bielik, Pavol, Raychev, Veselin, and Vechev, Martin T. PHOG: probabilistic model for code. In ICML, pp. 2933–2942, 2016. find
  3. Biermann, Alan W. The inference of regular lisp programs from examples. IEEE transactions on Systems, Man, and Cybernetics, 8(8):585–600, 1978. find
  4. Bunel, Rudy, Desmaison, Alban, Kohli, Pushmeet, Torr, Philip H. S., and Kumar, M. Pawan. Adaptive neural compilation. CoRR, abs/1605.07969, 2016. URL http://arxiv.org/abs/1605.07969. — [arXiv:1605.07969](https://arxiv.org/abs/1605.07969) ↗
  5. Gaunt, Alexander L, Brockschmidt, Marc, Singh, Rishabh, Kushman, Nate, Kohli, Pushmeet, Taylor, Jonathan, and Tarlow, Daniel. Terpret: A probabilistic programming language for program induction. arXiv preprint arXiv:1608.04428, 2016. find
  6. Graves, Alex, Wayne, Greg, and Danihelka, Ivo. arXiv:1410.5401, 2014. find
  7. Gulwani, Sumit. Automating string processing in spreadsheets using input-output examples. In POPL, pp. 317–330, 2011.
  8. Gulwani, Sumit, Jha, Susmit, Tiwari, Ashish, and Venkatesan, Ramarathnam. Synthesis of loop-free programs. In PLDI, pp. 62–73, 2011. find
  9. Gulwani, Sumit, Harris, William, and Singh, Rishabh. Spreadsheet data manipulation using examples. Communications of the ACM, Aug 2012. find
  10. Hindle, Abram, Barr, Earl T., Gabel, Mark, Su, Zhendong, and Devanbu, Premkumar T. On the naturalness of software. Commun. ACM, 59(5):122–131, 2016. find
  11. Irsoy, Orzan and Cardie, Claire. Bidirectional recursive neural networks for token-level labeling with structure. In NIPS Deep Learning Workshop, 2013. find
  12. Neural turing machines. arXiv preprint Joulin, Armand and Mikolov, Tomas. Inferring algorithmic patterns with stack-augmented recurrent nets. In NIPS, pp. 190–198, 2015. find
  13. Kurach, Karol, Andrychowicz, Marcin, and Sutskever, Ilya. Neural random-access machines. arXiv preprint arXiv:1511.06392, 2015. find
  14. Le, Phong and Zuidema, Willem. The inside-outside recursive neural network model for dependency parsing. In EMNLP, pp. 729–739, 2014. find
  15. Liang, Percy, Jordan, Michael I., and Klein, Dan. Learning programs: A hierarchical Bayesian approach. In ICML, pp. 639–646, 2010. find
  16. Maddison, Chris J and Tarlow, Daniel. Structured generative models of natural source code. In ICML, pp. 649–657, 2014. find
  17. Menon, Aditya Krishna, Tamuz, Omer, Gulwani, Sumit, Lampson, Butler W., and Kalai, Adam. A machine learning framework for programming by example. In ICML, pp. 187–195, 2013. find
  18. Neelakantan, Arvind, Le, Quoc V, and Sutskever, Ilya. Neural programmer: Inducing latent programs with gradient descent. arXiv preprint arXiv:1511.04834, 2015. find
  19. Paulus, Romain, Socher, Richard, and Manning, Christopher D. Global belief recursive neural networks. pp. 2888–2896, 2014. find
  20. Raychev, Veselin, Vechev, Martin T., and Krause, Andreas. Predicting program properties from ”big code”. In POPL, pp. 111–124, 2015. find
  21. Reed, Scott and de Freitas, Nando. arXiv:1511.06279, 2015. find
  22. Riedel, Sebastian, Bosnjak, Matko, and Rocktäschel, Tim. Programming with a differentiable forth interpreter. CoRR, abs/1605.06640, 2016. URL http://arxiv.org/abs/1605.06640. ↗
  23. Schkufza, Eric, Sharma, Rahul, and Aiken, Alex. Stochastic superoptimization. In ASPLOS, pp. 305–316, 2013. find
  24. Singh, Rishabh and Solar-Lezama, Armando. Synthesizing data structure manipulations from storyboards. In SIGSOFT FSE, pp. 289–299, 2011. find
  25. Singh, Rishabh, Gulwani, Sumit, and Solar-Lezama, Armando. Automated feedback generation for introductory programming assignments. In PLDI, pp. 15–26, 2013. find
  26. Solar-Lezama, Armando. Program Synthesis By Sketching. PhD thesis, EECS Dept., UC Berkeley, 2008. find
  27. Solar-Lezama, Armando, Rabbah, Rodric, Bodik, Rastislav, and Ebcioglu, Kemal. Programming by sketching for bit-streaming programs. In PLDI, 2005. find
  28. Summers, Phillip D. A methodology for lisp program construction from examples. Journal of the ACM (JACM), 24(1):161–175, 1977. find
  29. Udupa, Abhishek, Raghavan, Arun, Deshmukh, Jyotirmoy V., Mador-Haim, Sela, Martin, Milo M. K., and Alur, Rajeev. TRANSIT: specifying protocols with concolic snippets. In PLDI, pp. 287–296, 2013. find
  30. Vinyals, Oriol, Kaiser, Lukasz, Koo, Terry, Petrov, Slav, Sutskever, Ilya, and Hinton, Geoffrey. Grammar as a foreign language. In ICLR, 2015. find
  31. Neural programmer-interpreters. arXiv preprint JConcat(f 1 , · · · , f n )K v JConstStr(s)K v JSubStr(v, p l , p r )K v JConstPos(k)K v J(r, k, Start)K v J(r, k, End)K v Figure 7: The semantics of the DSL for string transformations. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/parisotto-2016-neuro-symbolic-program-synthesis/