Synthesizing Efficient Memoization Algorithms
Open Access
- 16 October 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 7 (OOPSLA2) , 89-115
Abstract
In this paper, we propose an automated approach to finding correct and efficient memoization algorithms from a 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 number of distinct outputs 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 number of different output values of the synthesized function. However, the generated synthesis task is still too complex for existing synthesizers. 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 Leetcode, the National Olympiad in Informatics in Provinces-Junior (a national-wide algorithmic programming contest in China), and previous approaches. Our approach successfully synhesizes 39/42 problems in a reasonable time, outperforming the baselines.Keywords
Funding Information
- National Key Research and Development Program of China (Grant No. 2022YFB450190)
- National Natural Science Foundation of China (Grant No. 62161146003)
This publication has 37 references indexed in Scilit:
- Automatic inversion generates divide-and-conquer parallel programsACM SIGPLAN Notices, 2007
- Combinatorial sketching for finite programsACM SIGARCH Computer Architecture News, 2006
- A discipline of dynamic programming over sequence dataScience of Computer Programming, 2004
- Selective memoizationACM SIGPLAN Notices, 2003
- Prolog Programming Language2003
- Rules and strategies for transforming functional and logic programsACM Computing Surveys, 1996
- Eliminating Redundant Recursive Calls.ACM Transactions on Programming Languages and Systems, 1983
- A Practical Decision Procedure for Arithmetic with Function SymbolsJournal of the ACM, 1979
- The Complexity of Some Problems on Subsequences and SupersequencesJournal of the ACM, 1978
- Longest Increasing and Decreasing SubsequencesCanadian Journal of Mathematics, 1961