Origami: (un)folding the abstraction of recursion schemes for program synthesis

使用遗传编程进行程序合成，寻找满足输入规范的正确程序，通常以输入输出示例的形式提供。一个特别的挑战是如何有效地处理循环和递归，避免永远不会终止的程序。一个有用的抽象可以缓解这个问题，就是使用递归方案来概括数据的生成和消费的组合。递归方案非常强大，因为它们允许构建可以总结数据、创建序列和执行高级计算的程序。使用递归方案编写程序的主要优点是，程序由定义明确的模板组成，只需要合成少数几个部分。在本文中，我们对使用折叠和展开模板进行程序合成的好处进行了初步研究，并概述了一些初步实验结果。为了突出这种方法的优缺点，我们使用递归方案手动解决了整个GPSB基准测试，突出了应该与其他实现相比合成的部分。我们注意到，一旦选择了递归方案，合成过程就可以简化，因为模板中缺失的每个部分都可以简化为更简单的函数，这些函数又受到它们自己的输入和输出类型的限制。

论文试图解决使用遗传编程进行程序合成时，如何有效处理循环和递归问题的挑战？

使用递归方案作为程序合成的抽象，以避免程序无限循环的问题，并且可以构建能够总结数据、创建序列和执行高级计算的程序模板。使用递归方案编写程序的主要优势是，程序由明确定义的模板组成，只需要综合一些需要合成的部分。

论文通过手动解决GPSB基准测试来突出使用递归方案进行程序合成的优势和缺点，并概述了一些初步实验结果。一旦选择了递归方案，合成过程就可以简化，因为模板的每个缺失部分都可以简化为更简单的函数，这些函数受它们自己的输入和输出类型的限制。

最近的相关研究包括使用遗传编程进行程序合成的其他方法，如基于类型的程序合成和程序合成中的搜索空间约束等。