实例编程研究进展与挑战

doi:10.11896/jsjkx.211000225

Abstract

Abstract: Program synthesis means that the computer automatically constructs code that conforms to the specified grammar and user’s given specifications.Programming by examples is a kind of paradigm in program synthesis that takes input and output examples as the specifications.It has high usability and low learning cost.In recent years,it has been successfully implemented in applications such as data wrangling and string transformation,and has great potential for development.There are two main pro-blems to be solved in programming by examples.One is the problem of efficient search in huge program space,and the other is the problem of ambiguity in solutions.To solve the first problem,a method for programming by examples needs to select the appropriate domain-specific language and formulate the search algorithm when specifying the searching strategy.The applied searching algorithm can be classified into a rule-based algorithm and an algorithm based on statistical model.To solve the second problem,a method for programming by examples needs to formulate a sorting strategy.The applied sorting strategy can be classified into a sorting method based on given examples and a sorting method based on user interaction.This paper sorts out related literature on programming by examples in recent years,summarizes the methods and key technical points to solve the above two problems,and finally gives suggestions for future research directions in the field of programming by examples.

Key words: Program synthesis, Programming by examples, Search strategy, Ambiguity

CLC Number:

TP311

YAN Qian-yu, LI Yi, PENG Xin. Research Progress and Challenge of Programming by Examples[J].Computer Science, 2022, 49(11): 1-7.

References

[1]HU X,LI G,LIU F,et al.Program Generation and Code Completion Techniques Based on Deep Learning:Literature Review[J].Journal of Software,2019,30(5):1206-1223.
[2]GULWANI S,POLOZOV O,SINGH R.Program synthesis[J].Foundations and Trends in Programming Languages,2017,4(1/2):1-119.
[3]SUMMERS P D.A methodology for LISP program construction from examples[J].Journal of the ACM(JACM),1977,24(1):161-175.
[4]GKIOKAS A.Imitation learning in artificial intelligence[D].Coventry:University of Warwick,2016.
[5]LÁZARO-GREDILLA M,LIN D,GUNTUPALLI J S,et al.Beyond imitation:Zero-shot task transfer on robots by learning concepts as cognitive programs[J].arXiv:1812.02788,2018.
[6]GULWANI S.Automating string processing in spreadsheetsusing input-output examples[C]//Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages.2011:317-330.
[7]GULWANI S,ESPARZA J,GRUMBERG O.Programming byExamples(and its applications in Data Wrangling)[J].Dependable Software Systems Engineering,2016,45(137):3-15.
[8]BALOG M,GAUNT A L,BROCKSCHMIDT M,et al.Deep-Coder:Learning to Write Programs[C]//International Confe-rence on Learning Representations(ICLR 2017).OpenReview.net,2017.
[9]DEVLIN J,UESATO J,BHUPATIRAJU S,et al.Robustfill:Neural program learning under noisy i/o[C]//International Conference on Machine Learning.PMLR,2017:990-998.
[10]ELLIS K,NYE M,PU Y,et al.Write,execute,assess:program synthesis with a REPL[C]//Proceedings of the 33rd International Conference on Neural Information Processing Systems.2019:9169-9178.
[11]NYE M,HEWITT L,TENENBAUM J,et al.Learning to infer program sketches[C]//International Conference on Machine Learning.PMLR,2019:4861-4870.
[12]HARRIS W R,GULWANI S.Spreadsheet table transforma-tions from examples[C]//Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation.2011:317-328.
[13]WANG C,CHEUNG A,BODIK R.Synthesizing highly expressive SQL queries from input-output examples[C]//Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation.2017:452-466.
[14]DEVLIN J,BUNEL R,SINGH R,et al.Neural program meta-induction[C]//Proceedings of the 31st International Conference on Neural Information Processing Systems.2017:2077-2085.
[15]CHEN X,LIU C,SONG D.Execution-guided neural programsynthesis[C]//International Conference on Learning Representations(ICLR 2018).OpenReview.Net,2018.
[16]BUNEL R,HAUSKNECHT M,DEVLIN J,et al.Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis[C]//International Conference on Learning Representations(ICLR 2018).OpenReview.Net.2018.
[17]ROLIM R,SOARES G,D'ANTONI L,et al.Learning syntactic program transformations from examples[C]//2017 IEEE/ACM 39th International Conference on Software Engineering(ICSE).IEEE,2017:404-415.
[18]LE X B D,CHU D H,LO D,et al.S3:syntax-and semantic-guided repair synthesis via programming by examples[C]//Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering.2017:593-604.
[19]BAVISHI R,YOSHIDA H,PRASAD M R.Phoenix:Automated data-driven synthesis of repairs for static analysis violations[C]//Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering.2019:613-624.
[20]FALLERI J R,MORANDAT F,BLANC X,et al.Fine-grained and accurate source code differencing[C]//Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering.2014:313-324.
[21]FESER J K,CHAUDHURI S,DILLIG I.Synthesizing datastructure transformations from input-output examples[J].ACM SIGPLAN Notices,2015,50(6):229-239.
[22]OSERA P M,ZDANCEWIC S.Type-and-example-directed program synthesis[C]//Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation.2015:619-630.
[23]ALBARGHOUTHI A,GULWANI S,KINCAID Z.Recursiveprogram synthesis[C]//International Conference on Computer Aided Verification.Berlin:Springer,2013:934-950.
[24]ALUR R,BODIK R,JUNIWAL G,et al.Syntax-Guided Synthesis[C]//2013 Formal Methods in Computer-Aided Design(FMCAD).IEEE,2013:1-8.
[25]PELEG H,POLIKARPOVA N.Perfect is the Enemy of Good:Best-Effort Program Synthesis[C]//34th European Conference on Object-Oriented Programming(ECOOP 2020).Schloss Dagstuhl-Leibniz-Zentrum für Informatik,2020:1-30.
[26]LEE W.Combining the top-down propagation and bottom-upenumeration for inductive program synthesis[J].Proceedings of the ACM on Programming Languages,2021,5(POPL):1-28.
[27]SHI K,STEINHARDT J,LIANG P.Frangel:component-based synthesis with control structures[J].Proceedings of the ACM on Programming Languages,2019,3(POPL):1-29.
[28]WANG X,DILLIG I,SINGH R.Synthesis of data completionscripts using finite tree automata[J].Proceedings of the ACM on Programming Languages,2017,1(OOPSLA):1-26.
[29]FENG Y,MARTINS R,VAN GEFFEN J,et al.Component-based synthesis of table consolidation and transformation tasks from examples[J].ACM SIGPLAN Notices,2017,52(6):422-436.
[30]MENON A,TAMUZ O,GULWANI S,et al.A machine lear-ning framework for programming by example[C]//International Conference on Machine Learning.PMLR,2013:187-195.
[31]REED S,DE FREITAS N.Neural programmer-interpreters[J].arXiv:1511.06279,2015.
[32]CHEN X,LIU C,SONG D.Towards Synthesizing Complex Programs From Input-Output Examples[C]//International Confe-rence on Learning Representations(ICLR 2018).OpenReview.Net.2018.
[33]ALUR R,RADHAKRISHNA A,UDUPA A.Scaling enumerative program synthesis via divide and conquer[C]//International Conference on Tools and Algorithms for the Construction and Analysis of Systems.Berlin:Springer,2017:319-336.
[34]LEE W,HEO K,ALUR R,et al.Accelerating search-based program synthesis using learned probabilistic models[C]//39th ACM SIGPLAN Conference on Programming Language Design and Implementation,PLDI 2018.Association for Computing Machinery,2018:436-449.
[35]JI R,SUN Y,XIONG Y,et al.Guiding dynamic programing via structural probability for accelerating programming by example[J].Proceedings of the ACM on Programming Languages,2020,4(OOPSLA):1-29.
[36]BARKE S,PELEG H,POLIKARPOVA N.Just-in-time lear-ning for bottom-up enumerative synthesis[J].Proceedings of the ACM on Programming Languages,2020,4(OOPSLA):1-29.
[37]ODENA A,SHI K,BIEBER D,et al.BUSTLE:Bottom-Up Program Synthesis Through Learning-Guided Exploration[C]//International Conference on Learning Representations.2020.
[38]BAVISHI R,LEMIEUX C,FOX R,et al.AutoPandas:neural-backed generators for program synthesis[J].Proceedings of the ACM on Programming Languages,2019,3(OOPSLA):1-27.
[39]CHEN Y,WANG C,BASTANI O,et al.Program SynthesisUsing Deduction-Guided Reinforcement Learning[C]//International Conference on Computer Aided Verification.Cham:Springer,2020:587-610.
[40]KANT N.Recent advances in neural program synthesis[J].ar-Xiv:1802.02353,2018.
[41]SINGH R,GULWANI S.Predicting a correct program in programming by example[C]//International Conference on Computer Aided Verification.Cham:Springer,2015:398-414.
[42]AN S,SINGH R,MISAILOVIC S,et al.Augmented example-based synthesis using relational perturbation properties[J].Proceedings of the ACM on Programming Languages,2019,4(POPL):1-24.
[43]NARITA M,MAUDET N,LU Y,et al.FlashAttention:Data-centric Interaction for Data Transformation Using Programming-by-Example[C]//Adjunct Publication of the 33rd Annual ACM Symposium on User Interface Software and Technology.2020:65-67.
[44]RAZA M,GULWANI S.Disjunctive program synthesis:A robust approach to programming by example[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2018:1403-1412.
[44]MAYER M,SOARES G,GRECHKIN M,et al.User interaction models for disambiguation in programming by example[C]//Proceedings of the 28th Annual ACM Symposium on User Interface Software & Technology.2015:291-301.
[46]ELLIS K,GULWANI S.Learning to learn programs from ex-amples:going beyond program structure[C]//Proceedings of the 26th International Joint Conference on Artificial Intelligence.2017:1638-1645.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Research Progress and Challenge of Programming by Examples

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 8

Metrics

Comments

Recommended 0

[1]	PAN Heng, LI Jing feng, MA Jun hu. Role Dynamic Adjustment Algorithm for Resisting Insider Threat [J]. Computer Science, 2020, 47(5): 313-318.
[2]	LI Jun, TONG Zhao, WANG Zheng. Approach to Solve TSP with Parallel ACS-2-opt [J]. Computer Science, 2018, 45(11A): 138-142.
[3]	LI Jia, GUO Jian-yi, LIU Yan-chao, YU Zheng-tao, XIAN Yan-tuan and NGUY～N Qing’e. Vietnamese Combinational Ambiguity Disambiguation Based on Weighted Voting Method of Multiple Classifiers [J]. Computer Science, 2018, 45(1): 167-172.
[4]	CHEN Zhi-yan, LI Xiao-jie, ZHU Shu-hua, FU Dan-long and XING Yi-hai. Bi-direction Maximum Matching Method Based on Hash Structural Dictionary [J]. Computer Science, 2015, 42(Z11): 49-54.
[5]	WU Fei, ZHANG Yu-hong and HU Xue-gang. Approach of Cross-domain Word Sentiment Orientation Identification on Reviews [J]. Computer Science, 2015, 42(6): 220-222.
[6]	HU Jing-ming,GUO Dao-sheng and WANG Hui. Carrier Synchronization Algorithm Research for High-order Modulated APSK Signal [J]. Computer Science, 2013, 40(Z6): 239-242.
[7]	GUAN Jing-hua,LIU Da-you. Selected Ensemble of Classifiers for Handling Concept-drifting Data Streams [J]. Computer Science, 2010, 37(1): 205-207.
[8]	. [J]. Computer Science, 2006, 33(7): 204-206.