Automatic and transparent memoization
Functions are memoized automatically and transparently. Memoized code can be injected automatically within a program to facilitate efficient and/or expeditious execution thereof, among other things. The memoized code can intercept calls to an original function and return values in accordance with the code. Accordingly, callers of the function need not do anything special and can invoke the function without knowledge of it being memoized.
1. A memoization system, comprising at least one processor and least one computer-readable storage medium storing instructions executable by the at least one processor to implement:
an analysis component configured to perform analysis of program code;
a memo component configured to memoize a function in response to the analysis at least in part via code injection;
a storage component configured to provide functionality pertaining to storing and returning computed function results, and including a generation component configured generate a storage construct to store computed function results, in the form of a hash table accessible by at least one of
a hash function or a key selector specified in code,
a default function if no explicit hash function or key selector is specified in code, or
a function inferred from contextual information; and
a custom component configured to inject functionality in addition to code injected via the code injection, the functionality including
functionality pertaining to creation or detection of cycles in a recursion, and
functionality to insert a dummy value into the storage construct and a called function, scan a result of the called function for occurrences identical to the dummy value, and replace the occurrences with a back link to a root value of a recursive graph corresponding to the called function.
2. The system of claim 1 , further comprising a component configured to remove cached values employed by a memoized function in accordance with a policy.
3. The system of claim 1 , further comprising a component configured to pre-fetch and load one or more values in the storage.
4. The system of claim 1 , further comprising a component configured to remove function memoization.
5. The system of claim 1 , the memoized function including a component configured to identify whether values should be re-computed or retrieved from cache, when available.
6. The system of claim 1 , further comprising an export component configured to persist data of the storage construct to a computer-readable storage medium.
7. The system of claim 1 , further comprising an import component configured to load data from a computer-readable storage medium into the storage construct.
8. The system of claim 1 , the memo component being configured to transform the function into an idempotent function.
9. The system of claim 1 , the analysis component being configured to identify whether memoization is to be turned on or off as a function of at least one of online or offline network connectivity.
10. The system of claim 1 , further comprising a component configured to add logging and/or security functionality.
11. The system of claim 1 , the analysis and memo component forming part of a compiler.
12. A method of computer program interpretation, comprising using at least one processor to execute instructions stored on at least one computer-readable storage medium to perform operations including:
injecting code into a program to memoize a function;
generating a storage construct configured to store results of a computation corresponding to the function;
forming a hash function to access the stored results;
customizing the code by injecting additional functionality pertaining to creating or detecting cycles in a recursion;
overriding the function with the customized code in response to a call to the function;
in response to the overriding, inserting a dummy value into the storage construct and the called function;
accessing the dummy value in the storage construct using at least one of a hash function or a key selector specified in code, a default function if no explicit hash function or key selector is specified in code, or a function inferred from contextual information;
scanning a result of the called function for occurrences identical to the dummy value; and
replacing the occurrences with a back link to a root value of a recursive graph corresponding to the called function.
13. The method of claim 12 , further comprising recording values of previous calls in an instance method field.
14. The method of claim 12 , further comprising computing a unique key to facilitate location of a previously generated value stored in the storage construct as a function of one or more arguments associated with a call to the function.
15. The method of claim 14 , further comprising employing one of a specified, default or inferred key generation function.
16. The method of claim 14 , further comprising returning a previously generated value located in the storage construct.
17. The method of claim 12 , further comprising employing backpatching to detect or create cycles.
18. A computer-readable storage medium storing instructions executable by a computing device to perform the method of claim 12 .