论文标题
基于分解的综合用于应用类似划分的算法范例
Decomposition-Based Synthesis for Applying Divide-and-Conquer-Like Algorithmic Paradigms
论文作者
论文摘要
提出了算法范式（例如分裂和框）（D＆C）来指导开发人员设计有效的算法，但是仍然很难将算法范式应用于实际任务。为了缓解范式的使用，许多研究工作已致力于自动应用算法范式。但是，大多数现有的问题方法都取决于基于语法的程序转换，因此对原始程序施加了重大限制。 在本文中，我们研究了D＆C的自动应用和几种类似的范式，称为D＆C样算法范式，并旨在消除基于语法的转换中的限制。为了实现此目标，我们提出了一个名为Autolifter的有效合成器，该合成器不依赖于基于语法的转换。具体而言，应用算法范式的主要挑战来自大规模的合成程序，自动化器通过应用两种不取决于输入程序的语法，消除组件消除和可变的消除的语法，将整个问题明显地分为简单的子任务，将整个程序划分为综合综合，从而解决了这一挑战。 我们评估了96个与6种不同算法范式相关的编程任务的自动化器。 Autolifter解决了82/96个任务，平均时间成本为20.17秒，大大优于现有方法。
Algorithmic paradigms such as divide-and-conquer (D&C) are proposed to guide developers in designing efficient algorithms, but it can still be difficult to apply algorithmic paradigms to practical tasks. To ease the usage of paradigms, many research efforts have been devoted to the automatic application of algorithmic paradigms. However, most existing approaches to this problem rely on syntax-based program transformations and thus put significant restrictions on the original program. In this paper, we study the automatic application of D&C and several similar paradigms, denoted as D&C-like algorithmic paradigms, and aim to remove the restrictions from syntax-based transformations. To achieve this goal, we propose an efficient synthesizer, named AutoLifter, which does not depend on syntax-based transformations. Specifically, the main challenge of applying algorithmic paradigms is from the large scale of the synthesized programs, and AutoLifter addresses this challenge by applying two novel decomposition methods that do not depend on the syntax of the input program, component elimination and variable elimination, to soundly divide the whole problem into simpler subtasks, each synthesizing a sub-program of the final program and being tractable with existing synthesizers. We evaluate AutoLifter on 96 programming tasks related to 6 different algorithmic paradigms. AutoLifter solves 82/96 tasks with an average time cost of 20.17 seconds, significantly outperforming existing approaches.
