Efficient memo-table management strategies (Q582879): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68P05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68N15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C39 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 4131634 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
memo-functions | |||
Property / zbMATH Keywords: memo-functions / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
memo-table | |||
Property / zbMATH Keywords: memo-table / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
dynamic programming | |||
Property / zbMATH Keywords: dynamic programming / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
functional language HOPE | |||
Property / zbMATH Keywords: functional language HOPE / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4091421 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Can programming be liberated from the von Neumann style? / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3929003 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Improving programs by the introduction of recursion / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3919065 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Transformational programming and the paragraph problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Transformation System for Developing Recursive Programs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Eliminating Redundant Recursive Calls. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A synthesis of several sorting algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A system which automatically improves programs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Linearisation: An optimisation for nonlinear functional programs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Elimination of recursive calls using a small table of “randomly” selected function values / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A family of rules for recursion removal / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4144192 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3311639 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An example of hierarchical design and proof / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5657656 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Development of the Algebra of Functional Programs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:56, 20 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient memo-table management strategies |
scientific article |
Statements
Efficient memo-table management strategies (English)
0 references
1990
0 references
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.
0 references
memo-functions
0 references
memo-table
0 references
dynamic programming
0 references
functional language HOPE
0 references
0 references