GRCNN: Graph Recognition Convolutional Neural Network for Synthesizing Programs from Flow Charts

Authors: Lin Cheng, Zijiang Yang

Abstract:

Program synthesis is the task to automatically generate programs based on user specification. In this paper, we present a framework that synthesizes programs from flow charts that serve as accurate and intuitive specification. In order doing so, we propose a deep neural network called GRCNN that recognizes graph structure from its image. GRCNN is trained end-to-end, which can predict edge and node information of the flow chart simultaneously. Experiments show that the accuracy rate to synthesize a program is 66.4%, and the accuracy rates to recognize edge and node are 94.1% and 67.9%, respectively. On average, it takes about 60 milliseconds to synthesize a program.

Keywords: program synthesis, flow chart, specification, graph recognition, CNN.

References:

[1] S. Gulwani, “Dimensions in program synthesis,” in Proceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming. ACM, 2010, pp. 13–24.
[2] ——, “Automating string processing in spreadsheets using input-output examples,” ACM Sigplan Notices, vol. 46, no. 1, pp. 317–330, 2011.
[3] Z. Manna and R. Waldinger, “A deductive approach to program synthesis,” ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 2, no. 1, pp. 90–121, 1980.
[4] Y. Feng, R. Martins, J. Van Geffen, I. Dillig, and S. Chaudhuri, “Component-based synthesis of table consolidation and transformation tasks from examples,” in ACM SIGPLAN Notices, vol. 52, no. 6. ACM, 2017, pp. 422–436.
[5] T. A. Lau and D. S. Weld, “Programming by demonstration: An inductive learning formulation,” in International Conference on Intelligent User Interfaces: Proceedings of the 4 th international conference on Intelligent user interfaces, vol. 5, no. 08. Citeseer, 1998, pp. 145–152.
[6] C. Wang, A. Cheung, and R. Bodik, “Synthesizing highly expressive sql queries from input-output examples,” in ACM SIGPLAN Notices, vol. 52, no. 6. ACM, 2017, pp. 452–466.
[7] A. Solar-Lezama and R. Bodik, Program synthesis by sketching. Citeseer, 2008.
[8] L. Cheng, “Sqlsol: An accurate sql query synthesizer,” in International Conference on Formal Engineering Methods. Springer, 2019, pp. 104–120.
[9] M. Balog, A. L. Gaunt, M. Brockschmidt, S. Nowozin, and D. Tarlow, “Deepcoder: Learning to write programs,” arXiv preprint arXiv:1611.01989, 2016.
[10] N. Yaghmazadeh, Y. Wang, I. Dillig, and T. Dillig, “Sqlizer: query synthesis from natural language,” Proceedings of the ACM on Programming Languages, vol. 1, no. OOPSLA, p. 63, 2017.
[11] N. Locascio, K. Narasimhan, E. DeLeon, N. Kushman, and R. Barzilay, “Neural generation of regular expressions from natural language with minimal domain knowledge,” arXiv preprint arXiv:1608.03000, 2016.
[12] S. Ren, K. He, R. Girshick, and J. Sun, “Faster r-cnn: Towards real-time object detection with region proposal networks,” in Advances in neural information processing systems, 2015, pp. 91–99.
[13] S. Zherzdev and A. Gruzdev, “Lprnet: License plate recognition via deep neural networks,” arXiv preprint arXiv:1806.10447, 2018.
[14] G. B. Shelly and M. E. Vermaat, Discovering Computers, Complete: Your Interactive Guide to the Digital World. Cengage Learning, 2011.
[15] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.
[16] R. Girshick, J. Donahue, T. Darrell, and J. Malik, “Rich feature hierarchies for accurate object detection and semantic segmentation,” in Proceedings of the IEEE conference on computer vision and pattern recognition, 2014, pp. 580–587.
[17] M. Jaderberg, K. Simonyan, A. Zisserman et al., “Spatial transformer networks,” in Advances in neural information processing systems, 2015, pp. 2017–2025.
[18] D. M. Etter, Introduction to C. Prentice Hall, 1998.