OOPSLA23'23, a well-known conference in the field of programming language, recently announced the list of accepted papers. one paper 'Synthesizing Efficient Memoization Algorithms' from our labotorary was accepted. The details of the paper is listed below.

Title: Synthesizing Efficient Memoization Algorithms

Authors: Yican Sun, Xuanyu Peng, Yingfei Xiong

Abstract:

In this paper, we propose an automated approach to finding correct and efficient memoization algorithms from the given declarative specification. This problem has two major challenges: (i) a memoization algorithm is too large to be handled by conventional program synthesizers; (ii) we need to guarantee the efficiency of the memoization algorithm. To address this challenge, we structure the synthesis of memoization algorithms by introducing the local objective function and the memoization partition function, and reduce the synthesis task to two smaller independent program synthesis tasks. Moreover, the range of the function synthesized in the second synthesis task also decides the efficiency of the synthesized memoization algorithm, and we only need to minimize the range of the synthesized function. However, the generated synthesis task is still too complex, since it involves relational synthesis tasks. Thus, we propose a novel synthesis algorithm that combines the deductive and inductive methods to solve these tasks. To evaluate our algorithm, we collect 42 real-world benchmarks from previous work, Leetcode and a national-wide algorithmic programming contest. Our approach successfully synthesizes 39/42 problems in a reasonable time, outperforming the baselines.