Efficient memo-table management strategies
A large, automatically detectable class of nonlinear functions is defined and their evaluation graphs are characterized. These results are then used to develop space-efficient implementation of memo-functions. We generate a variant of memo-functions which can be used to linearize the time cost of calls of a nonlinear function to itself whilst executing in bounded space. These memo-functions dynamically garbage collect (or reuse) memo-table entries when it is known that such entries will not be useful again. For each nonlinear function a function called the table- manager function is synthesized by a static analysis of the definition of the nonlinear function. The table-managers delete (or reuse) entries that are guaranteed to be obsolete as a result of any insertion into the memo-tables. In this way they ensure that the size of the tables is minimized. Furthermore, the sizes of the tables for these memo-functions are guaranteed not to exceed a compile-time constant found by the same static analysis which synthesizes the table-managers. The applicability of the method also includes many problems which have been previously solved by applying dynamic programming techniques. An implementation of these memo-functions for the functional language HOPE is also outlined.
- A family of rules for recursion removal
- A synthesis of several sorting algorithms
- A system which automatically improves programs
- A Transformation System for Developing Recursive Programs
- An example of hierarchical design and proof
- Can programming be liberated from the von Neumann style?
- Eliminating Redundant Recursive Calls.
- Elimination of recursive calls using a small table of “randomly” selected function values
- scientific article; zbMATH DE number 3841211 (Why is no real title available?)
- scientific article; zbMATH DE number 3731318 (Why is no real title available?)
- scientific article; zbMATH DE number 3744496 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3573250 (Why is no real title available?)
- scientific article; zbMATH DE number 3388544 (Why is no real title available?)
- Improving programs by the introduction of recursion
- Linearisation: An optimisation for nonlinear functional programs
- On the Development of the Algebra of Functional Programs
- Transformational programming and the paragraph problem
- Memoizing purely functional top-down backtracking language processors
- On sharing, memoization, and polynomial time
- Verified memoization and dynamic programming
- On sharing, memoization, and polynomial time
- Zippy Tabulations of Recursive Functions
- Applicative caching
- Algebraic Transformation Techniques for Functional Languages
- A bounds inference method for vector-based memoization
- Approximation of function evaluation over sequence arguments via specialized data structures
This page was built for publication: Efficient memo-table management strategies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q582879)
