Purity analysis using white list/black list analysis

摘要

Memoizable functions may be identified by analyzing a function's side effects. The side effects may be evaluated using a white list, black list, or other definition. The side effects may also be classified into conditions which may or may not permit memoization. Side effects that may have de minimus or trivial effects may be ignored in some cases where the accuracy of a function may not be significantly affected when the function may be memoized.

主权项

1. A computer-implemented method of determining whether an impure function of a program is memoizable, the computer-implemented method comprising:
performing a static code analysis of the program which identifies for one or more functions of the program whether a function has a side effect, and if the function has a side effect, classifying the function as impure; for each function classified as impure:
analyzing different sets of input parameters treated as input vectors,clustering the input vectors to create areas of known input vectors for which memoization may be performed and areas of known input vectors for which memoization may not be performed, andfor a given input vector, classifying at least one or more of the impure functions as memoizable or not based at least in part on whether the given input vector is within one of said areas of known input vectors for which memoization may be performed; and storing the one or more impure functions classified as memoizable in a memoization list to facilitate return of cached results for those functions stored on the memoization list so that the cached results are provided without having to re-execute the one or more functions.