实例编程研究进展与挑战

doi:10.11896/jsjkx.211000225

计算机科学 ›› 2022, Vol. 49 ›› Issue (11): 1-7.doi: 10.11896/jsjkx.211000225

实例编程研究进展与挑战

严倩羽, 李弋, 彭鑫

复旦大学计算机科学技术学院上海 200438
上海市数据科学重点实验室(复旦大学) 上海 200438

收稿日期:2021-10-29 修回日期:2022-02-25 出版日期:2022-11-15 发布日期:2022-11-03
通讯作者: 李弋(liy@fudan.edu.cn)
作者简介:(19212010002@fudan.edu.cn)
基金资助:
上海市科委项目(19511132000)

Research Progress and Challenge of Programming by Examples

YAN Qian-yu, LI Yi, PENG Xin

School of Computer Science,Fudan University,Shanghai 200438,China
Shanghai Key Laboratory of Data Science(Fudan University),Shanghai 200438,China

Received:2021-10-29 Revised:2022-02-25 Online:2022-11-15 Published:2022-11-03
About author:YAN Qian-yu,born in 1997,postgra-duate.Her main research interests include program synthesis and software engineering.
LI Yi,born in 1975,Ph.D,lecturer,is a member of China Computer Federation.His main research interests include robot software,program analysis and computer system architecture.
Supported by:
Science and Technology Commission of Shanghai Municipality(19511132000).

摘要/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

中图分类号:

TP311

严倩羽, 李弋, 彭鑫. 实例编程研究进展与挑战[J]. 计算机科学, 2022, 49(11): 1-7. https://doi.org/10.11896/jsjkx.211000225

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

参考文献

[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

实例编程研究进展与挑战

Research Progress and Challenge of Programming by Examples

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

Metrics

本文评价

推荐阅读 0

[1]	高诗尧, 陈燕俐, 许玉岚. 云环境下基于属性的多关键字可搜索加密方案 Expressive Attribute-based Searchable Encryption Scheme in Cloud Computing 计算机科学, 2022, 49(3): 313-321. https://doi.org/10.11896/jsjkx.201100214
[2]	潘恒, 李景峰, 马君虎. 可抵御内部威胁的角色动态调整算法 Role Dynamic Adjustment Algorithm for Resisting Insider Threat 计算机科学, 2020, 47(5): 313-318. https://doi.org/10.11896/jsjkx.190800051
[3]	郑浩, 于俊洋, 魏上斐. 基于余弦控制因子和迭代局部搜索的蝙蝠优化算法 Bat Optimization Algorithm Based on Cosine Control Factor and Iterative Local Search 计算机科学, 2020, 47(11A): 68-72. https://doi.org/10.11896/jsjkx.200200063
[4]	李俊, 童钊, 王政. 一种并行ACS-2-opt算法处理TSP问题的方法 Approach to Solve TSP with Parallel ACS-2-opt 计算机科学, 2018, 45(11A): 138-142.
[5]	涂宏斌,岳艳艳,周新建,罗锟. 一种基于改进PLSA和案例推理的行为识别算法 Novel Action Recognition via Improved PLSA and CBR 计算机科学, 2017, 44(6): 283-289. https://doi.org/10.11896/j.issn.1002-137X.2017.06.050
[6]	邱武,丁明跃,周华. 基于实时灰度Hough变换的超声图像针状物体检测 Needle Segmentation in US Images Based on Real-time Gray-scale Hough Transformation 计算机科学, 2009, 36(11): 269-272.
[7]	陈静杨小帆曾智. 一种基于基因库和多重搜索策略求解TSP的遗传算法计算机科学, 2006, 33(8): 195-197.
[8]	温万惠刘光远贺一. 基于自适应集中性和多样性搜索策略的多用户检测方法计算机科学, 2005, 32(3): 44-46.
[9]	. Tabu Search集中性和多样性自动平衡下的增强搜索策略计算机科学, 2005, 32(11): 161-163.
[10]	李晓戈杨寿保. 对等网络中搜索策略的研究计算机科学, 2003, 30(9): 94-96.