Research Progress and Challenge of Programming by Examples

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.

Keywords

• program synthesis|programming by examples|search strategy|ambiguity