Elamur Research⌕
☰
home / papers / 2017 / Neural Attribute Machines for Program Generation

Neural Attribute Machines for Program Generation

Paper · 2017 · Matthew Amodio, Swarat Chaudhuri and Thomas W. Reps

Summary

The authors study how neural networks generate program source code. A recurrent network trained only on examples of correct programs learns the context-sensitive rules of a language poorly. For example, a variable must be declared before it is used, and its type must fit the place where it is used. The authors propose Neural Attribute Machines (NAMs). In this model, an RNN works together with a logical automaton based on an L-attributed grammar. The automaton tracks the structural context while the model builds an abstract syntax tree (AST) top-down and left to right. This context is encoded as a fixed-length vector and appended to the input sequence. The model is also trained with a three-valued loss function. It penalizes three cases differently: a correct prediction, an incorrect but admissible one, and an incorrect and inadmissible one. The experiments used a corpus of C programs that compile. NAMs violate constraints noticeably less often than a plain RNN trained on the same data. The paper concludes that formally known language rules are better built explicitly into training than left for the network to infer from examples on its own.

Key points

  • The AST is converted into a sequence of "nonterminal–production" pairs by depth-first traversal, and moves back up the tree are marked with pop markers. Variable names are replaced with Var1, Var2… in the order in which they appear.
  • Two constraints were tested separately: declared-variable (a variable must be declared before use) and typesafe-variable (variable types must be consistent).
  • NAM with the context vector generates 2.8 times more correct trees than the vanilla RNN. The full NAM (context plus three-valued loss) has a slightly higher NLL because of regularization, but generates best.
  • Mean NLL per token on the test data. Declared-variable: vanilla RNN — 0.253, NAM w/context — 0.188, NAM w/both — 0.208. Typesafe-variable: 1.425 / 0.779 / 0.794, respectively. The baseline model SGWC generalizes poorly: 7.178 on the test set for the type constraint.
  • The closest prior work is Maddison and Tarlow. Future plans: add more C language constraints so that generated programs compile more often, and apply NAMs to other structured sequences, for example proof trees in logic.

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

🎓University of Wisconsin–MadisonMadison · United States60 works · 49,213 citations🎓Rice UniversityHouston · United States15 works · 2,036 citations🎓University of Wisconsin SystemMadison · United States3 works · 202 citations

Also on the byline: GrammaTech.

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksComputational Theory and Mathematics · 496 works

Cite

Cite as Matthew Amodio, Swarat Chaudhuri and Thomas W. Reps. 2017. Neural Attribute Machines for Program Generation. arXiv:1705.09231.

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

@misc{amodio2017neural,
  title = {{Neural Attribute Machines for Program Generation}},
  author = {Matthew Amodio, Swarat Chaudhuri and Thomas W. Reps},
  year = {2017},
  doi = {10.48550/arxiv.1705.09231},
  eprint = {1705.09231},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1705.09231}
}

References

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

  1. Aaron van den Oord, Nal Kalchbrenner, and Koray Kavukcuoglu. Pixel recurrent neural networks. arXiv preprint arXiv:1601.06759, 2016. find
  2. David Ha and Douglas Eck. A neural representation of sketch drawings. arXiv preprint arXiv:1704.03477, 2017. — [arXiv:1704.03477](https://arxiv.org/abs/1704.03477) find
  3. Oriol Vinyals, Alexander Toshev, Samy Bengio, and Dumitru Erhan. Show and tell: A neural image caption generator. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3156–3164, 2015.
  4. Christian Holler, Kim Herzig, and Andreas Zeller. Fuzzing with code fragments. In USENIX Security Symposium, pages 445–458, 2012. find
  5. Abram Hindle, Earl T Barr, Zhendong Su, Mark Gabel, and Premkumar Devanbu. On the naturalness of software. In Software Engineering (ICSE), 2012 34th International Conference on, pages 837–847. IEEE, 2012. find
  6. Veselin Raychev, Martin Vechev, and Eran Yahav. Code completion with statistical language models. In PLDI, 2014. find
  7. D.E. Knuth. Semantics of context-free languages. Mathematical Systems Theory, 2(2):127–145, June 1968. find
  8. D.E. Knuth. Semantics of context-free languages: Correction. Mathematical Systems Theory, 5(1):95–96, March 1971. find
  9. P.M. Lewis, D.J. Rosenkrantz, and R.E. Stearns. Attributed translations. J. Comput. Syst. Sci., 9(3):279–307, December 1974. find
  10. Sophocles Efremidis, Christos H. Papadimitriou, and Martha Sideris. Complexity characterizations of attribute grammar languages. Inf. and Comp., 78(3):178–186, 1988. find
  11. T. Reps and T. Teitelbaum. The Synthesizer Generator: A System for Constructing Language-Based Editors. Springer-Verlag, NY, 1988. find
  12. Lili Mou, Hao Peng, Ge Li, Yan Xu, Lu Zhang, and Zhi Jin. Discriminative neural sentence modeling by tree-based convolution. arXiv preprint arXiv:1504.01106, 2015. find
  13. Bing Shuai, Zhen Zuo, Bing Wang, and Gang Wang. Dag-recurrent neural networks for scene labeling. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3620–3629, 2016. find
  14. Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1735–1780, 1997. find
  15. Horia Margarit and Raghav Subramaniam. A batch-normalized recurrent network for sentiment classification. Advances in Neural Information Processing Systems, 2016. find
  16. Marijn F. Stollenga, Wonmin Byeon, Marcus Liwicki, and Juergen Schmidhuber. Parallel multi-dimensional LSTM, with application to fast biomedical volumetric image segmentation. In Advances in Neural Information Processing Systems, pages 2998–3006, 2015. find
  17. Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pages 3104–3112, 2014.
  18. Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
  19. Nitish Srivastava, Geoffrey E Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1):1929–1958, 2014.
  20. George C. Necula, Scott McPeak, Shree P. Rahul, and Westley Weimer. CIL: Intermediate language and tools for analysis and transformation of C programs. In International Conference on Compiler Construction, pages 213–228. Springer, 2002. find
  21. C.J. Maddison and D. Tarlow. Structured generative models of natural source code. In ICML, 2014. find
  22. Tung Thanh Nguyen, Anh Tuan Nguyen, Hoan Anh Nguyen, and Tien N. Nguyen. A statistical semantic language model for source code. In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2013, pages 532–542, New York, NY, USA, 2013. ACM. find
  23. Anh Tuan Nguyen and Tien N. Nguyen. Graph-based statistical language model for code. In Proceedings of the 37th International Conference on Software Engineering - Volume 1, ICSE ’15, pages 858–868, Piscataway, NJ, USA, 2015. IEEE Press. find
  24. Pavol Bielik, Veselin Raychev, and Martin Vechev. PHOG: Probabilistic model for code. In ICML, pages 19–24, 2016. find
  25. Miltiadis Allamanis and Charles Sutton. Mining idioms from source code. In Proceedings of the 22Nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2014, pages 472–483, New York, NY, USA, 2014. ACM.
  26. Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. arXiv preprint arXiv:1611.01855, 2016.
  27. Vijayaraghavan Murali, Swarat Chaudhuri, and Chris Jermaine. Bayesian sketch learning for program synthesis. arXiv preprint arXiv:1703.05698, 2017. find
  28. Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. arXiv preprint arXiv:1611.01989, 2016. find
  29. J.-F. Raskin and F. Servais. Visibly pushdown transducers. In ICALP, 2008. find
  30. Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to transduce with unbounded memory. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 1828–1836. Curran Associates, Inc., 20… find
  31. Jen-Tzung Chien and Yuan-Chu Ku. Bayesian recurrent neural network for language modeling. IEEE transactions on neural networks and learning systems, 27(2):361–374, 2016. find
  32. Jing Bai and Yan Wu. SAE-RNN deep learning for RGB-D based object recognition. In International Conference on Intelligent Computing, pages 235–240. Springer, 2014. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/amodio-2017-neural-attribute-machines-program-generation/