[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Program synthesis algorithm based on context consistency heuristic

  • Original Article
  • Published:
International Journal of Machine Learning and Cybernetics Aims and scope Submit manuscript

Abstract

Programming-by-example (PBE) is a program synthesis technique that automatically synthesizes computer programs from input–output (I/O) examples. There are many approaches to program synthesis, and one of the most commonly used solutions is to perform a search over the space of programs. In this paper, we present a novel program synthesis algorithm based on context consistency heuristic (PSACC) that differs from previous heuristic methods. We consider the input–output example as a state and develop a deep neural network-based predictor called DHFnet. DHFnet has the ability to map the current state to the first two instructions of the program which achieves the current state. By considering the current state and its subsequent state obtained by executing the corresponding instruction, we design a context consistency-based search algorithm. Our search algorithm enables a more reasonable and efficient selection of instructions in the program, by judging whether the instructions maintain the context consistency between the current state and its subsequent state. Furthermore, under the same experimental and testing environments, PSACC successfully enhances the success rate of program synthesis by 2–5%, and reduces the synthesis time compared to the baseline method. PSACC also exhibits better synthesis efficiency in terms of comprehensive performance compared to existing program synthesis methods.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Data availability

The data that support the findings of this study are available from the corresponding author but restrictions apply to the availability of these data, which were used under licence for the current study, and so are not publicly available. Data are however available from the authors upon reasonable request and with permission of the corresponding author.

References

  1. Nye M, Hewitt L, Tenenbaum J, Solar-Lezama A (2019) Learning to infer program sketches. In: International Conference on Machine Learning, pp. 4861–4870. PMLR

  2. Fijalkow N, Lagarde G, Matricon T, Ellis K, Ohlmann P, Potta AN (2022) Scaling neural program synthesis with distribution-based search. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, pp. 6623–6630

  3. Le H, Wang Y, Gotmare AD, Savarese S, Hoi SCH (2022) Coderl: Mastering code generation through pretrained models and deep reinforcement learning. Adv Neural Inf Process Syst 35:21314–21328

    Google Scholar 

  4. Cellucci C (2017) Is mathematics problem solving or theorem proving? Found Sci 22(1):183–199

    Article  MathSciNet  Google Scholar 

  5. Waldinger RJ, Lee RC (1969) Prow: A step toward automatic program writing. In: Proceedings of the 1st International Joint Conference on Artificial Intelligence, pp. 241–252

  6. Manna Z, Waldinger RJ (1971) Toward automatic program synthesis. Commun ACM 14(3):151–165

    Article  Google Scholar 

  7. Alur R, Černỳ P, Madhusudan P, Nam W (2005) Synthesis of interface specifications for java classes. In: Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 98–109

  8. Solar Lezama A (2008) Program synthesis by sketching. Technical Report UCB/EECS-2008-176, EECS Department, University of California, Berkeley. http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-176.html

  9. Quirk C, Mooney R, Galley M (2015) Language to code: Learning semantic parsers for if-this-then-that recipes. In: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 878–888

  10. Gu X, Zhang H, Kim S (2018) Deep code search. In: Proceedings of the 40th International Conference on Software Engineering, pp. 933–944

  11. Juravsky J, Guo Y, Fidler S, Peng XB (2022) Padl: Language-directed physics-based character control. In: SIGGRAPH Asia 2022 Conference Papers, pp. 1–9

  12. Gu X, Zhang H, Zhang D, Kim S (2016) Deep api learning. In: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp. 631–642

  13. Chen X, Liu C, Shin R, Song D, Chen M (2016) Latent attention for if-then program synthesis. In: Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 4581–4589

  14. Zhang L, Rosenblatt G, Fetaya E, Liao R, Byrd W, Might M, Urtasun R, Zemel R (2018) Neural guided constraint logic programming for program synthesis. Adv Neural Inf Process Syst 31

  15. Laich L, Bielik P, Vechev M (2019) Guiding program synthesis by learning to generate examples. In: International Conference on learning representations

  16. Reed SE, Freitas N (2015) Neural programmer-interpreters. CoRR abs/1511.06279

  17. Li C, Tarlow D, Gaunt AL, Brockschmidt M, Kushman N (2016) Neural program lattices. In: International Conference on learning representations

  18. Cai J, Shin R, Song D (2017) Making neural programming architectures generalize via recursion. In: International Conference on learning representations . https://openreview.net/forum?id=BkbY4psgg

  19. Parisotto E, Mohamed A-r, Singh R, Li L, Zhou D, Kohli P (2017) Neuro-symbolic program synthesis. In: International Conference on Learning Representations. https://openreview.net/forum?id=rJ0JwFcex

  20. Balog M, Gaunt A, Brockschmidt M, Nowozin S, Tarlow D (2017) Deepcoder: Learning to write programs. In: Proceedings of ICLR’17. https://www.microsoft.com/en-us/research/publication/deepcoder-learning-write-programs/

  21. Zohar A, Wolf L (2018) Automatic program synthesis of long programs with a learned garbage collector. Adv Neural Inf Process syst 31

  22. Shrivastava D, Larochelle H, Tarlow D (2021) Learning to combine per-example solutions for neural program synthesis. Adv Neural Inf Process Syst 34:6102–6114

    Google Scholar 

  23. Huang G, Liu Z, Van Der Maaten L, Weinberger KQ (2017) Densely connected convolutional networks. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4700–4708

  24. Klambauer G, Unterthiner T, Mayr A, Hochreiter S (2017) Self-normalizing neural networks. Adv Neural Inf Process Syst 30

  25. Kingma DP, Ba J (2015) Adam: a method for stochastic optimization. In: Bengio, Y., LeCun, Y. (eds.) 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings. http://arxiv.org/abs/1412.6980

  26. Jaccard P (1912) The distribution of the flora in the alpine zone. 1. New Phytologist 11(2):37–50

    Article  Google Scholar 

  27. Zhang W (1998) Complete anytime beam search. In: AAAI/IAAI, pp. 425–430

  28. Devlin J, Uesato J, Bhupatiraju S, Singh R, Mohamed A-r, Kohli P (2017) Robustfill: Neural program learning under noisy i/o. In: International Conference on Machine Learning, pp. 990–998 . PMLR

Download references

Author information

Authors and Affiliations

  1. College of Computer Science and Technology, Shandong Technology and Business University, 191 Binhai Middle Road, Yantai, 264005, Shandong, China

    Quansheng Dou, Huanling Tang & Ping Jiang

  2. College of Information and Electronic Engineering, Shandong Technology and Business University, 191 Binhai Middle Road, Yantai, 264005, Shandong, China

    Hao Pan & Huixian Wang

  3. School of Computer Science and Technology, Kashi University, 29 Xueyuan Road, Kashi, 844006, Xinjiang, China

    Quansheng Dou

Authors
  1. Quansheng Dou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hao Pan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Huanling Tang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ping Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Huixian Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Quansheng Dou.

Ethics declarations

Conflict of interest

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this paper.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dou, Q., Pan, H., Tang, H. et al. Program synthesis algorithm based on context consistency heuristic. Int. J. Mach. Learn. & Cyber. 15, 559–571 (2024). https://doi.org/10.1007/s13042-023-01925-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13042-023-01925-3

Keywords

Search

Navigation