程序语言顶级会议 PLDI'24 公布论文录用名单，程序设计语言实验室的论文《Superfusion: Eliminating Intermediate Data Structures via Inductive Synthesis》被该会议录用，详情如下。

标题：Superfusion: Eliminating Intermediate Data Structures via Inductive Synthesis

作者：Ruyi Ji, Yuwei Zhao, Nadia Polikarpova, Yingfei Xiong, Zhenjiang Hu

摘要：中间数据结构是函数式编程中导致低效的常见原因。融合（Fusion）尝试通过将相邻的数据遍历合并为一个遍历来消除中间数据结构；然而，现有的融合技术均依赖预先定义的重写规则，在表达能力上存在限制。

在本研究中，我们探索了一种基于归纳程序综合的融合方法。我们将这种方法称为超融合（类比于使用归纳综合进行程序优化的超优化）。超融合从一个带有待消除数据结构注释的参考程序开始，首先生成一个草图，其中操作中间数据结构的程序片段被替换为未知片段；然后，超融合用常数时间表达式填充这些空洞，使得生成的程序与参考程序等价。实现超融合的主要技术挑战在于可扩展性。由于优化后的程序通常复杂，超融合的搜索空间往往很大，远远超出了枚举方法的能力范畴。为了解决这个挑战，我们的想法是首先综合一个辅助函数，该函数描述原始中间数据结构与其压缩版本之间的关系；尽管这个函数不会在最终程序中使用，但它可以将草图填充问题分解为只关于每个未知片段的独立子问题。

我们将超融合实现成了一个名为 SuFu 的工具，并在从相关工作中搜集到的290个任务的数据集上进行了评估。结果显示，SuFu 解决了290个任务中的264个，超过了基于重写的融合系统的能力，并且在各自的程序重构领域中达到了与专门方法相当的性能。