程序语言领域顶级会议OOPSLA’23近日公布论文录用名单，程序设计语言研究室一篇论文《Synthesizing Efficient Memoization Algorithms》被该会议录用。

标题：Synthesizing Efficient Memoization Algorithms

作者：孙奕灿、彭轩宇、熊英飞*

摘要：

在本文中，我们提出了一种自动方法，可以从给定的声明式规约中合成正确、高效的记忆化搜索算法。这个合成问题有两大挑战：(i) 记忆化搜索算法的代码规模过于庞大，传统的程序合成器无法处理；(ii) 我们需要保证记忆化搜索算法的高效性。为解决这一难题，我们通过引入局部目标函数和记忆化分区函数来构造记忆化搜索算法的合成，并将合成任务简化为两个较小的独立程序合成任务。此外，第二个合成任务中的记忆化区分函数的范围也决定了合成后的记忆化搜索算法的效率，我们只需最小化该函数的范围即可。然而，生成的合成任务仍然过于复杂，因为它是一个关系式程序合成任务。因此，我们提出了一种结合演绎法和归纳法的新型合成算法来解决这些任务。为了评估我们的算法，我们从以前的工作、Leetcode 和全国算法编程竞赛中收集了 42 个真实世界的基准。我们的方法在合理的时间内成功合成了 39/42 个问题，表现优于基线算法。