实例编程研究进展与挑战  

Research Progress and Challenge of Programming by Examples

作　　者：严倩羽 李弋 彭鑫[1,2] 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)

机构地区：[1]复旦大学计算机科学技术学院,上海200438 [2]上海市数据科学重点实验室(复旦大学),上海200438

出　　处：《计算机科学》2022年第11期1-7,共7页Computer Science

基　　金：上海市科委项目(19511132000)。

摘　　要：程序合成指计算机自动地构造符合指定语法和用户给定规约的代码。实例编程是程序合成中一类以输入输出实例为规约形式的范式,它易用性高、学习成本低。近年来,该技术已经在数据处理、字符串变换等领域得到成功应用,具有很大的发展潜力。实例编程主要待解决的问题有两点:一是庞大程序空间中高效搜索的问题,二是程序合成解的歧义性问题。为解决第一个问题,实例编程方法在指定搜索策略时,需选取适当的领域特定语言,制定搜索算法,所应用的算法可分类为基于规则的算法和基于统计模型的算法。为解决第二个问题,实例编程方法需制定排序策略,所应用的排序策略可分类为基于给定实例的排序方法和基于用户交互的排序方法。文中对近年来的实例编程相关文献进行了整理,针对解决以上两个问题的方法、关键技术点进行了总结归纳,最后对实例编程领域未来的研究方向给出了建议。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.

关 键 词：程序合成 实例编程 搜索策略 歧义性 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]