Evolutionary Program Sketching

详细信息    查看全文

• 关键词：Program synthesis ; Satisfiability modulo theory ; Program sketching ; Genetic programming
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10196
• 期：1
• 页码：3-18
• 丛书名：Genetic Programming
• ISBN：978-3-319-55696-3
• 卷排序：10196

文摘

Program synthesis can be posed as a satisfiability problem and approached with generic SAT solvers. Only short programs can be however synthesized in this way. Program sketching by Solar-Lezama assumes that a human provides a partial program (sketch), and that synthesis takes place only within the uncompleted parts of that program. This allows synthesizing programs that are overall longer, while maintaining manageable computational effort. In this paper, we propose Evolutionary Program Sketching (EPS), in which the role of sketch provider is handed over to genetic programming (GP). A GP algorithm evolves a population of partial programs, which are being completed by a solver while evaluated. We consider several variants of EPS, which vary in program terminals used for completion (constants, variables, or both) and in the way the completion outcomes are propagated to future generations. When applied to a range of benchmarks, EPS outperforms the conventional GP, also when the latter is given similar time budget.