Stepping Stones to Inductive Synthesis of Low-Level Looping Programs
Stepping Stones to Inductive Synthesis of Low-Level Looping Programs
复制标题
低级循环程序归纳综合的垫脚石
DOI：
10.1609/aaai.v33i01.33012362
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Christopher D. Rosin
中科院分区：
文献类型：
--
作者：
Christopher D. Rosin
来自输入/输出示例的归纳程序合成可以提供从头开始自动创建程序的机会，而无需预先假定解决方案的算法形式。对于带有循环的通用程序的归纳（与无循环程序或特定领域语言的综合相反），最先进的技术处于介绍性编程作业的水平。如果没有重要的特定问题背景知识，大多数需要算法精妙的问题（例如快速排序）仍然无法解决。一个关键的挑战是识别可用于指导搜索正确的循环程序的线索。我们提出了 MAKESPEARE，一种简单的延迟接受爬山方法，它从输入/输出示例合成低级循环程序。在搜索过程中，延迟接受会绕过小的收益来识别显着改进的垫脚石程序，这些程序往往会泛化并实现进一步的进展。该方法在一组已建立的基准上表现良好，并在之前未解决的“Collatz Numbers”程序综合问题上取得了成功。其他基准包括快速排序整数数组的问题，其中我们观察到梳状排序（一种根据经验快速的希尔排序变体）的出现。 MAKESPEARE 还针对 TIS100 汇编语言编程游戏中的一个谜题合成了创纪录的程序。
Inductive program synthesis, from input/output examples, can provide an opportunity to automatically create programs from scratch without presupposing the algorithmic form of the solution. For induction of general programs with loops (as opposed to loop-free programs, or synthesis for domain-specific languages), the state of the art is at the level of introductory programming assignments. Most problems that require algorithmic subtlety, such as fast sorting, have remained out of reach without the benefit of significant problem-specific background knowledge. A key challenge is to identify cues that are available to guide search towards correct looping programs. We present MAKESPEARE, a simple delayed-acceptance hillclimbing method that synthesizes low-level looping programs from input/output examples. During search, delayed acceptance bypasses small gains to identify significantly-improved stepping stone programs that tend to generalize and enable further progress. The method performs well on a set of established benchmarks, and succeeds on the previously unsolved “Collatz Numbers” program synthesis problem. Additional benchmarks include the problem of rapidly sorting integer arrays, in which we observe the emergence of comb sort (a Shell sort variant that is empirically fast). MAKESPEARE has also synthesized a record-setting program on one of the puzzles from the TIS100 assembly language programming game.
DOI：
10.1007/978-3-662-44923-3
发表时间：
2014-09
期刊：
--
影响因子：
--
作者：
Gerson Zaverucha;V. S. Costa;A. Paes
通讯作者：
Gerson Zaverucha;V. S. Costa;A. Paes