CoChat
Sign Up
PreprintCited by 20Teaching and Learning ProgrammingEvolutionary Algorithms and ApplicationsSoftware Testing and Debugging Techniques

Synthesize, Execute and Debug: Learning to Repair for Neural Program Synthesis

Open access
Gupta, Kavi, Christensen, Peter Ebert, Chen, Xinyun, Song, Dawn·2020·arXiv
DOI 10.48550/arxiv.2007.08095arXiv 2007.08095
Open this paper in CoChat — free accountOpen PDF

Abstract

The use of deep learning techniques has achieved significant progress for program synthesis from input-output examples. However, when the program semantics become more complex, it still remains a challenge to synthesize programs that are consistent with the specification. In this work, we propose SED, a neural program generation framework that incorporates synthesis, execution, and debugging stages. Instead of purely relying on the neural program synthesizer to generate the final program, SED first produces initial programs using the neural program synthesizer component, then utilizes a neural program debugger to iteratively repair the generated programs. The integration of the debugger component enables SED to modify the programs based on the execution results and specification, which resembles the coding process of human programmers. On Karel, a challenging input-output program synthesis benchmark, SED reduces the error rate of the neural program synthesizer itself by a considerable margin, and outperforms the standard beam search for decoding.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2007.08095

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Prior work on code repair has demonstrated that training the repair model on execution traces improves debugging performance.

    “Prior work on code repair has demonstrated that training the repair model on execution traces improves the debugging performance (Wang et al., 2018;Gupta et al., 2020).”

    From Teaching Large Language Models to Self-Debug (2023) · cites this paper as Gupta et al., 2020

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Still being checked.

Research works printed but not linked: 28

  1. [1][1] M. Balog, A. L. Gaunt, M. Brockschmidt, S. Nowozin, and D. Tarlow. Deepcoder: Learning to write programs. In International Conference on Learning Representations , 2017. -
  2. [2][2] R. Bunel, M. Hausknecht, J. Devlin, R. Singh, and P. Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. In International Conference on Learning Representations , 2018. -
  3. [3][3] X. Chen, C. Liu, and D. Song. Execution-guided neural program synthesis. In International Conference on Learning Representations , 2019. -
  4. [4][4] J. Devlin, R. R. Bunel, R. Singh, M. Hausknecht, and P. Kohli. Neural program meta-induction. In Advances in Neural Information Processing Systems , pages 2080-2088, 2017. -
  5. [5][5] J. Devlin, J. Uesato, S. Bhupatiraju, R. Singh, A. rahman Mohamed, and P. Kohli. Robustfill: Neural program learning under noisy i/o. In ICML , 2017. -
  6. [6][6] E. Dinella, H. Dai, Z. Li, M. Naik, L. Song, and K. Wang. Hoppity: Learning graph transformations to detect and fix bugs in programs. In International Conference on Learning Representations , 2020. -
  7. [7][7] K. Ellis, M. I. Nye, Y. Pu, F. Sosa, J. B. Tenenbaum, and A. Solar-Lezama. Write, execute, assess: Program synthesis with a repl. In NeurIPS , 2019. -
  8. [8][8] K. Ellis, D. Ritchie, A. Solar-Lezama, and J. Tenenbaum. Learning to infer graphics programs from hand-drawn images. In Advances in neural information processing systems , pages 60596068, 2018. -
  9. [9][9] C. Fu, H. Chen, H. Liu, X. Chen, Y. Tian, F. Koushanfar, and J. Zhao. Coda: An end-to-end neural program decompiler. In NeurIPS , 2019. -
  10. [10][10] S. Gulwani, W. R. Harris, and R. Singh. Spreadsheet data manipulation using examples. Communications of the ACM , 55(8):97-105, 2012. -
  11. [11][11] R. Gupta, S. Pal, A. Kanade, and S. K. Shevade. Deepfix: Fixing common c language errors by deep learning. In AAAI , 2017. -
  12. [13][13] L. Laich, P. Bielik, and M. Vechev. Guiding program synthesis by learning to generate examples. In International Conference on Learning Representations , 2020. -
  13. [14][14] X.-B. D. Le, D.-H. Chu, D. Lo, C. Le Goues, and W. Visser. S3: syntax-and semantic-guided repair synthesis via programming by examples. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering , pages 593-604, 2017. -
  14. [15][15] C. Le Goues, M. Dewey-Vogt, S. Forrest, and W. Weimer. A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each. In 2012 34th International Conference on Software Engineering (ICSE) , pages 3-13. IEEE, 2012. -
  15. [17][17] Z. Manna and R. J. Waldinger. Toward automatic program synthesis. Communications of the ACM , 14(3):151-165, 1971. -
  16. [18][18] B. Mehne, H. Yoshida, M. R. Prasad, K. Sen, D. Gopinath, and S. Khurshid. Accelerating search-based program repair. In 2018 IEEE 11th International Conference on Software Testing, Verification and Validation (ICST) , pages 227-238. IEEE, 2018. -
  17. [19][19] S. H. Muggleton, D. Lin, N. Pahlavi, and A. Tamaddoni-Nezhad. Meta-interpretive learning: application to grammatical inference. Mach. Learn. , 94(1):25-49, 2014. -
  18. [20][20] E. Parisotto, A.-r. Mohamed, R. Singh, L. Li, D. Zhou, and P. Kohli. Neuro-symbolic program synthesis. In International Conference on Learning Representations , 2017. -
  19. [21][21] R. E. Pattis. Karel the Robot: A Gentle Introduction to the Art of Programming . John Wiley & Sons, Inc., USA, 1st edition, 1981. -
  20. [22][22] E. Schkufza, R. Sharma, and A. Aiken. Stochastic superoptimization. ACMSIGARCHComputer Architecture News , 41(1):305-316, 2013. -
  21. [23][23] E. C. Shin, I. Polosukhin, and D. Song. Improving neural program synthesis with inferred execution traces. In Advances in Neural Information Processing Systems , pages 8917-8926, 2018. -
  22. [24][24] R. Shin, N. Kant, K. Gupta, C. Bender, B. Trabucco, R. Singh, and D. X. Song. Synthetic datasets for neural program synthesis. In International Conference on Learning Representations , 2019. -
  23. [25][25] R. Shin, I. Polosukhin, and D. X. Song. Towards specification-directed program repair. In ICLR Workshop , 2018. -
  24. [27][27] S.-H. Sun, H. Noh, S. Somasundaram, and J. Lim. Neural program synthesis from diverse demonstration videos. In Proceedings of the 35th International Conference on Machine Learning , 2018. -
  25. [28][28] M. Vasic, A. Kanade, P. Maniatis, D. Bieber, and R. Singh. Neural program repair by jointly learning to localize and repair. In International Conference on Learning Representations , 2019. -
  26. [29][29] A. J. Vijayakumar, A. Mohta, O. Polozov, D. Batra, P. Jain, and S. Gulwani. Neural-guided deductive search for real-time program synthesis from examples. In ICLR , 2018. -
  27. [30][30] K. Wang, R. Singh, and Z. Su. Dynamic neural program embedding for program repair. In International Conference on Learning Representations , 2018. -
  28. [31][31] A. Zohar and L. Wolf. Automatic program synthesis of long programs with a learned garbage collector. In NeurIPS , 2018.

Cited by

Sorted by citations

Related

Authors
Gupta, K., Christensen, P. E., Chen, X., & Song, D.
Affiliations
  • University of California, Berkeley (US)
  • Technical University of Denmark (DK)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2020
Volume
33
Pages
17685-17695
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2007.08095
arXiv
2007.08095
OpenAlex
W3102935281
Cited by
18
References
0
Citations by year
2025: 5 · 2024: 3 · 2023: 1 · 2022: 1 · 2021: 8
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
  • neural information processing systems
Topics
  • Physical Sciences › Computer Science › Computer Science Applications › Teaching and Learning Programming
  • Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
  • Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
Keywords
neural program synthesis, program repair, debugging, program execution, specification consistency, error reduction, beam search decoding

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review