In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls to pure functions and returning the cached result when the same inputs occur again.
Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple mutually recursive descent parsing.
Memoized functions are optimized for speed in exchange for a higher use of computer memory space.
Memoization is heavily used in compilers for functional programming languages, which often use call by name evaluation strategy.
To avoid overhead with calculating argument values, compilers for these languages heavily use auxiliary functions called thunks to compute the argument values, and memoize these functions to avoid repeated calculations.
Applications of automatic memoization have also been formally explored in the study of term rewriting[4] and artificial intelligence.
[5] In programming languages where functions are first-class objects (such as Lua, Python, or Perl[6]), automatic memoization can be implemented by replacing (at run-time) a function with its calculated value once a value has been calculated for a given set of parameters.
When a top-down parser tries to parse an ambiguous input with respect to an ambiguous context-free grammar (CFG), it may need an exponential number of steps (with respect to the length of the input) to try all alternatives of the CFG in order to produce all possible parse trees.
[10][11] In 2002, it was examined in considerable depth by Bryan Ford in the form called packrat parsing.
[12] In 2007, Frost, Hafiz and Callaghan[citation needed] described a top-down parsing algorithm that uses memoization for refraining redundant computations to accommodate any form of ambiguous CFG in polynomial time (Θ(n4) for left-recursive grammars and Θ(n3) for non left-recursive grammars).
[13] Their use of memoization is not only limited to retrieving the previously computed results when a parser is applied to a same input position repeatedly (which is essential for polynomial time requirement); it is specialized to perform the following additional tasks: Frost, Hafiz and Callaghan also described the implementation of the algorithm in PADL’08[citation needed] as a set of higher-order functions (called parser combinators) in Haskell, which enables the construction of directly executable specifications of CFGs as language processors.
The importance of their polynomial algorithm's power to accommodate ‘any form of ambiguous CFG’ with top-down parsing is vital with respect to the syntax and semantics analysis during natural language processing.
This grammar generates one of the following three variations of string: xac, xbc, or xbd (where x here is understood to mean one or more x's.)
In a backtracking scenario with such memoization, the parsing process is as follows: In the above example, one or many descents into X may occur, allowing for strings such as xxxxxxxxxxxxxxxxbd.