Elamur Research⌕
☰
home / papers / 2019 / SPoC: Search-based Pseudocode to Code

SPoC: Search-based Pseudocode to Code

Paper · 2019 · Sumith Kulal, Panupong Pasupat, Kartik Chandra et al.

Summary

SPoC addresses the generation of complete, multi-line C++ programs (roughly 10–20 lines) from line-by-line natural-language pseudocode. Programs are judged by whether they pass test cases, not by how closely they match reference code. The system first produces several candidate translations for each pseudocode line. It then searches over combinations of these candidates for a program that compiles and passes the public tests. Most failed attempts turn out to be compiler errors, so the authors use those errors to steer the search toward the line responsible. They propose two ways to do this:

  • a multiclass classifier that reads the error message, the code and the pseudocode, and down-weights the suspect line;
  • prefix-based pruning, which spends extra compilations to find a code prefix that is guaranteed to be faulty and then blacklists it.

The authors also built and released the SPoC dataset. With a budget of 100 compilations, search lifts the success rate from about 25% (top-one translation) to 44.7%. The work shows that combining pseudocode with test cases makes it feasible to synthesize longer programs that actually work.

Key points

  • SPoC dataset: 18,356 accepted C++ solutions to 677 easy problems from codeforces.com, averaging 14.7 lines each. Every line has pseudocode written by 59 vetted Amazon Mechanical Turk workers, and every program comes with public and hidden test cases.
  • Two test splits: TESTP holds out 158 unseen problems (1,820 programs), and TESTW holds out 7 unseen annotators.
  • Why compiler errors matter: they account for 88.7% of failures during search, which motivates error localization. Simply down-weighting the line the compiler reports actually makes results worse.
  • Results: top-one translation succeeds 25.6% of the time (the introduction gives 24.6%), and search with 100 trials reaches 44.7%. With unlimited budget, the top-100 candidate lists cap success at 55.2% on TESTP and 71.4% on TESTW.
  • Multiclass classifier vs. prefix-based pruning:
    • The classifier reduces the number of trials for 15.5% of programs, with a median saving of 26 trials (42%). Because its guesses are never verified, it occasionally causes the search to fail outright.
    • Pruning beats the classifier once the budget exceeds roughly 1,500 compilations.

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

🎓Stanford UniversityStanford · United States506 works · 330,052 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksInformation Systems · 1,730 worksSoftware · 119 worksComputer Science Applications · 131 works

Cite

Cite as Sumith Kulal, Panupong Pasupat, Kartik Chandra, Mina Lee, Oded Padon, Alex Aiken and Percy Liang. 2019. SPoC: Search-based Pseudocode to Code. arXiv:1906.04908.

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

@misc{kulal2019spoc,
  title = {{SPoC: Search-based Pseudocode to Code}},
  author = {Sumith Kulal, Panupong Pasupat, Kartik Chandra, Mina Lee, Oded Padon, Alex Aiken and Percy Liang},
  year = {2019},
  doi = {10.48550/arxiv.1906.04908},
  eprint = {1906.04908},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1906.04908}
}

References

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

  1. M. Allamanis, M. Brockschmidt, and M. Khademi. Learning to represent programs with graphs. In International Conference on Learning Representations (ICLR), 2018.
  2. J. Andreas and D. Klein. Alignment-based compositional semantics for instruction following. In Empirical Methods in Natural Language Processing (EMNLP), 2015. find
  3. S. Bansal and A. Aiken. Automatic generation of peephole superoptimizers. In Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2006. find
  4. J. Berant, A. Chou, R. Frostig, and P. Liang. Semantic parsing on Freebase from question-answer pairs. In Empirical Methods in Natural Language Processing (EMNLP), 2013.
  5. S. Bhatia, P. Kohli, and R. Singh. Neuro-symbolic program corrector for introductory programming assignments. In International Conference on Software Engineering (ICSE), 2018. find
  6. J. Devlin, J. Uesato, S. Bhupatiraju, R. Singh, A. Mohamed, and P. Kohli. Robustfill: Neural program learning under noisy i/o. In International Conference on Machine Learning (ICML), 2017. find
  7. J. Devlin, J. Uesato, R. Singh, and P. Kohli. Semantic code repair using neuro-symbolic transformation networks. arXiv preprint arXiv:1710.11054, 2017. — [arXiv:1710.11054](https://arxiv.org/abs/1710.11054) find
  8. L. Dong and M. Lapata. Coarse-to-fine decoding for neural semantic parsing. In Association for Computational Linguistics (ACL), 2018. find
  9. Y. Feng, R. Martins, Y. Wang, I. Dillig, and T. W. Reps. Component-based synthesis for complex apis. In Principles of Programming Languages (POPL), 2017. find
  10. J. K. Feser, S. Chaudhuri, and I. Dillig. Synthesizing data structure transformations from input-output examples. In Programming Language Design and Implementation (PLDI), 2015. find
  11. S. Gulwani. Automating string processing in spreadsheets using input-output examples. ACM SIGPLAN Notices, 46(1):317–330, 2011.
  12. R. Gupta, S. Pal, A. Kanade, and S. K. Shevade. Deepfix: Fixing common C language errors by deep learning. In Association for the Advancement of Artificial Intelligence (AAAI), 2017. find
  13. B. Hartmann, D. MacDougall, J. Brandt, and S. R. Klemmer. What would other programmers do: suggesting solutions to error messages. In Conference on Human Factors in Computing Systems (CHI), 2010. find
  14. T. Hashimoto, K. Guu, Y. Oren, and P. Liang. A retrieve-and-edit framework for predicting structured outputs. In Advances in Neural Information Processing Systems (NeurIPS), 2018. find
  15. S. A. Hayati, R. Olivier, P. Avvaru, P. Yin, A. Tomasic, and G. Neubig. Retrieval-based neural code generation. In Empirical Methods in Natural Language Processing (EMNLP), 2018. find
  16. S. Iyer, I. Konstas, A. Cheung, and L. S. Zettlemoyer. Mapping language to code in programmatic context. In Empirical Methods in Natural Language Processing (EMNLP), 2018.
  17. M. Iyyer, W. Yih, and M. Chang. Answering complicated question intents expressed in decomposed question sequences. CoRR, 0, 2016. find
  18. S. Jha, S. Gulwani, S. A. Seshia, and A. Tiwari. Oracle-guided component-based program synthesis. In International Conference on Software Engineering (ICSE), 2010. find
  19. G. Klein, Y. Kim, Y. Deng, J. Senellart, and A. M. Rush. Opennmt: Open-source toolkit for neural machine translation. arXiv preprint arXiv:1701.02810, 2017.
  20. P. Liang, M. I. Jordan, and D. Klein. Learning dependency-based compositional semantics. In Association for Computational Linguistics (ACL), pages 590–599, 2011. find
  21. X. V. Lin, C. Wang, L. S. Zettlemoyer, and M. D. Ernst. Nl2bash: A corpus and semantic parser for natural language interface to the linux operating system. In Language Resources and Evaluation Conference (LREC), 2018. find
  22. W. Ling, E. Grefenstette, K. M. Hermann, T. Kočiský, A. Senior, F. Wang, and P. Blunsom. Latent predictor networks for code generation. In Association for Computational Linguistics (ACL), pages 599–609, 2016.
  23. R. Long, P. Pasupat, and P. Liang. Simpler context-dependent logical forms via model projections. In Association for Computational Linguistics (ACL), 2016.
  24. M. Luong, H. Pham, and C. D. Manning. Effective approaches to attention-based neural machine translation. In Empirical Methods in Natural Language Processing (EMNLP), pages 1412–1421, 2015.
  25. V. Marko, K. Aditya, M. Petros, B. David, and S. Rishabh. Neural program repair by jointly learning to localize and repair. In International Conference on Learning Representations (ICLR), 2019. find
  26. H. Massalin. Superoptimizer – a look at the smallest program. In Architectural Support for Programming Languages and Operating Systems (ASPLOS), 1987. find
  27. Y. Oda, H. Fudaba, G. Neubig, H. Hata, S. Sakti, T. Toda, and S. Nakamura. Learning to generate pseudo-code from source code using statistical machine translation. IEEE/ACM International Conference on Automated Software Engineering (ASE), 30:574–584, 2015. find
  28. E. Parisotto, A. Mohamed, R. Singh, L. Li, D. Zhou, and P. Kohli. Neuro-symbolic program synthesis. In International Conference on Learning Representations (ICLR), 2017.
  29. M. Rabinovich, M. Stern, and D. Klein. Abstract syntax networks for code generation and semantic parsing. In Association for Computational Linguistics (ACL), 2017. find
  30. E. Schkufza, R. Sharma, and A. Aiken. Stochastic superoptimization. In Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2013. find
  31. K. Shi, J. Steinhardt, and P. Liang. FrAngel: Component-based synthesis with control structures. In Principles of Programming Languages (POPL), 2019. find
  32. A. Solar-Lezama, L. Tancau, R. Bodik, V. Saraswat, and S. Seshia. Combinatorial sketching for finite programs. In Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2006. find
  33. R. Tate, M. Stepp, Z. Tatlock, and S. Lerner. Equality saturation: a new approach to optimization. In Principles of Programming Languages (POPL), 2009. find
  34. Z. Tu, Z. Lu, Y. Liu, X. Liu, and H. Li. Modeling coverage for neural machine translation. In Association for Computational Linguistics (ACL), 2016.
  35. D. Vadas and J. R. Curran. Programming with unrestricted natural language. In Australasian Language Technology Workshop (ALTA), 2005. find
  36. A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. arXiv preprint arXiv:1706.03762, 2017.
  37. O. Vinyals, M. Fortunato, and N. Jaitly. Pointer networks. In Advances in Neural Information Processing Systems (NeurIPS), pages 2674–2682, 2015. find
  38. N. Yaghmazadeh, C. Klinger, I. Dillig, and S. Chaudhuri. Synthesizing transformations on hierarchically structured data. In Programming Language Design and Implementation (PLDI), 2016. find
  39. N. Yaghmazadeh, Y. Wang, I. Dillig, and T. Dillig. Sqlizer: Query synthesis from natural language. In Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2017. find
  40. P. Yin and G. Neubig. A syntactic neural model for general-purpose code generation. In Association for Computational Linguistics (ACL), pages 440–450, 2017.
  41. M. Zavershynskyi, A. Skidanov, and I. Polosukhin. NAPS: Natural program synthesis dataset. In Workshop on Neural Abstract Machines & Program Induction (NAMPI), 2018. find
  42. M. Zelle and R. J. Mooney. Learning to parse database queries using inductive logic programming. In Association for the Advancement of Artificial Intelligence (AAAI), pages 1050–1055, 1996.
  43. L. S. Zettlemoyer and M. Collins. Online learning of relaxed CCG grammars for parsing to logical form. In Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP/CoNLL), pages 678–687, 2007. find
  44. V. Zhong, C. Xiong, and R. Socher. Seq2SQL: Generating structured queries from natural language using reinforcement learning. arXiv preprint arXiv:1709.00103, 2017.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/kulal-2019-spoc-search-based-pseudocode-code/