Memoization - WikiHQ

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs. It works by storing the results of expensive calls to pure functions, so that these results can be returned quickly should the same inputs occur again. It is a type of caching, normally implemented using a hash table, and a typical example of a space–time tradeoff, where the runtime of a program is reduced by increasing its memory usage. Memoization can be implemented in any programming language, though some languages have built-in support that make it easy for the programmer to memoize a function, and others memoize certain functions by default.

Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple mutually recursive descent parsing. In the context of some logic programming languages, memoization is also known as tabling.

Etymology

The term memoization was coined by Donald Michie in 1968 and is derived from the Latin word ('to be remembered'), usually truncated as memo in American English, and thus carries the meaning of 'turning [the results of] a function into something to be remembered'. While memoization might be confused with memorization (because they are etymological cognates), memoization has a specialized meaning in computing.

Overview

A memoized function, when called with a given set of inputs for the first time, stores the inputs along with the computed results. Upon subsequent calls with remembered inputs, the function returns the remembered results rather than recomputing them, thus eliminating the cost of a recomputation. The set of remembered associations may be a fixed-size set controlled by a replacement algorithm or a fixed set, depending on the nature of the function and its use. A function can only be memoized if it is referentially transparent; that is, only if calling the function has exactly the same effect as replacing that function call with its return value. (Special case exceptions to this restriction exist, however.) While related to lookup tables, since memoization often uses such tables in its implementation, memoization populates its cache of results transparently on the fly, rather than needing them to be supplied in advance.

Memoized functions are optimized for speed in exchange for a higher use of computer memory space. The time/space "cost" of algorithms has a specific name in computing: computational complexity. All functions have a computational complexity in time (i.e. they take time to execute) and in space.

Although a space–time tradeoff occurs (i.e., space used is speed gained), this differs from some other optimizations that involve time-space trade-off, such as strength reduction, in that memoization is a run-time rather than compile-time optimization. Moreover, strength reduction potentially replaces a costly operation such as multiplication with a less costly operation such as addition, and the results in savings can be highly machine-dependent (non-portable across machines), whereas memoization is a more machine-independent, cross-platform strategy.

Consider the following pseudocode function to calculate the factorial of n:

function factorial (n is a non-negative integer)

if n is 0 then

return 1 [by the convention that 0! = 1]

else

return factorial(n – 1) times n [recursively invoke factorial

with the parameter 1 less than n]

end if

end function

For every integer n such that <code><var>n</var> ≥ 0</code>, the final result of the function <code>factorial</code> is invariant; if invoked as <code>x = factorial(3)</code>, the result is such that x will always be assigned the value 6. The non-memoized implementation above, given the nature of the recursive algorithm involved, would require n + 1 invocations of <code>factorial</code> to arrive at a result, and each of these invocations, in turn, has an associated cost in the time it takes the function to return the value computed. Depending on the machine, this cost might be the sum of:

The cost to set up the functional call stack frame.
The cost to compare n to 0.
The cost to subtract 1 from n.
The cost to set up the recursive call stack frame. (As above.)
The cost to multiply the result of the recursive call to <code>factorial</code> by n.
The cost to store the return result so that it may be used by the calling context.

In a non-memoized implementation, every top-level call to <code>factorial</code> includes the cumulative cost of steps 2 through 6 proportional to the initial value of n.

A memoized version of the <code>factorial</code> function follows:

function factorial (n is a non-negative integer)

if n is 0 then

return 1 [by the convention that 0! = 1]

else if n is in lookup-table then

return lookup-table-value-for-n

else

let x = factorial(n – 1) times n [recursively invoke factorial

with the parameter 1 less than n]

store x in lookup-table in the nth slot [remember the result of n! for later]

return x

end if

end function

In this particular example, if <code>factorial</code> is first invoked with 5, and then invoked later with any value less than or equal to five, those return values will also have been memoized, since <code>factorial</code> will have been called recursively with the values 5, 4, 3, 2, 1, and 0, and the return values for each of those will have been stored. If it is then called with a number greater than 5, such as 7, only 2 recursive calls will be made (7 and 6), and the value for 5! will have been stored from the previous call. In this way, memoization allows a function to become more time-efficient the more often it is called, thus resulting in eventual overall speed-up.

An extreme example of memoization is the Singleton pattern, specifically the implementation of its getter — a function that creates an object upon the first invocation, caches the instance, and returns the same object on all subsequent invocations.

Other considerations

Functional programming

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.

Automatic memoization

While memoization may be added to functions internally and explicitly by a computer programmer in much the same way the above memoized version of <code>factorial</code> is implemented, referentially transparent functions may also be automatically memoized externally. and artificial intelligence.

In programming languages where functions are first-class objects (such as Lua, Python, or Perl), 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. The function that does this value-for-function-object replacement can generically wrap any referentially transparent function. Consider the following pseudocode (where it is assumed that functions are first-class values):

function memoized-call (F is a function object parameter)

if F has no attached array values then

allocate an associative array called values;

attach values to F;

end if;

if F.values[arguments] is empty then

F.values[arguments] = F(arguments);

end if;

return F.values[arguments];

end function

In order to call an automatically memoized version of <code>factorial</code> using the above strategy, rather than calling <code>factorial</code> directly, code invokes <code>memoized-call(factorial)(n)</code>. Each such call first checks to see if a holder array has been allocated to store results, and if not, attaches that array. If no entry exists at the position <code>values[arguments]</code> (where <code>arguments</code> are used as the key of the associative array), a real call is made to <code>factorial</code> with the supplied arguments. Finally, the entry in the array at the key position is returned to the caller.

The above strategy requires explicit wrapping at each call to a function that is to be memoized. In those languages that allow closures, memoization can be effected implicitly via a functor factory that returns a wrapped memoized function object in a decorator pattern. In pseudocode, this can be expressed as follows:

function construct-memoized-functor (F is a function object parameter)

allocate a function object called memoized-version;

let memoized-version(arguments) be

if self has no attached array values then [self is a reference to this object]

allocate an associative array called values;

attach values to self;

end if;

if self.values[arguments] is empty then

self.values[arguments] = F(arguments);

end if;

return self.values[arguments];

end let;

return memoized-version;

end function

Rather than call <code>factorial</code>, a new function object <code>memfact</code> is created as follows:

memfact = construct-memoized-functor(factorial)

The above example assumes that the function <code>factorial</code> has already been defined before the call to <code>construct-memoized-functor</code> is made. From this point forward, <code>memfact(n)</code> is called whenever the factorial of n is desired. In languages such as Lua, more sophisticated techniques exist which allow a function to be replaced by a new function with the same name, which would permit:

factorial = construct-memoized-functor(factorial)

Essentially, such techniques involve attaching the original function object to the created functor and forwarding calls to the original function being memoized via an alias when a call to the actual function is required (to avoid endless recursion), as illustrated below:

function construct-memoized-functor (F is a function object parameter)

allocate a function object called memoized-version;

let memoized-version(arguments) be

if self has no attached array values then [self is a reference to this object]

allocate an associative array called values;

attach values to self;

allocate a new function object called alias;

attach alias to self; [for later ability to invoke F indirectly]

self.alias = F;

end if;

if self.values[arguments] is empty then

self.values[arguments] = self.alias(arguments); [not a direct call to F]

end if;

return self.values[arguments];

end let;

return memoized-version;

end function

(Note: Some of the steps shown above may be implicitly managed by the implementation language and are provided for illustration.)

Parsers

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. This eventually would require exponential memory space. Memoization was explored as a parsing strategy in 1991 by Peter Norvig, who demonstrated that an algorithm similar to the use of dynamic programming and state-sets in Earley's algorithm (1970), and tables in the CYK algorithm of Cocke, Younger and Kasami, could be generated by introducing automatic memoization to a simple backtracking recursive descent parser to solve the problem of exponential time complexity. Frost showed that basic memoized parser combinators can be used as building blocks to construct complex parsers as executable specifications of CFGs.

Memoization was again explored in the context of parsing in 1995 by Mark Johnson and Jochen Dörre. In 2002, it was examined in considerable depth by Bryan Ford in the form called packrat parsing.

In 2007, Frost, Hafiz and Callaghan 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). Their top-down parsing algorithm also requires polynomial space for potentially exponential ambiguous parse trees by 'compact representation' and 'local ambiguities grouping'. Their compact representation is comparable with Tomita's compact representation of bottom-up parsing. 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:

The memoization process (which could be viewed as a ‘wrapper’ around any parser execution) accommodates an ever-growing direct left-recursive parse by imposing depth restrictions with respect to input length and current input position.
The algorithm's memo-table ‘lookup’ procedure also determines the reusability of a saved result by comparing the saved result's computational context with the parser's current context. This contextual comparison is the key to accommodate indirect (or hidden) left-recursion.
When performing a successful lookup in a memotable, instead of returning the complete result-set, the process only returns the references of the actual result and eventually speeds up the overall computation.
During updating the memotable, the memoization process groups the (potentially exponential) ambiguous results and ensures the polynomial space requirement.

Frost, Hafiz and Callaghan also described the implementation of the algorithm in PADL’08 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. The X-SAIGA site has more about the algorithm and implementation details.

While Norvig increased the power of the parser through memoization, the augmented parser was still as time complex as Earley's algorithm, which demonstrates a case of the use of memoization for something other than speed optimization. Johnson and Dörre

References

External links

; Examples of memoization in various programming languages

groovy.lang.Closure#memoize() – Memoize is an Apache Groovy 1.8 language feature.
Memoize – Memoize is a small library, written by Tim Bradshaw, for performing memoization in Common Lisp.
IncPy – A custom Python interpreter that performs automatic memoization (with no required user annotations)
Dave Herman's Macros for defining memoized procedures in Racket.
Memoize.pm – a Perl module that implements memoized functions.
Java memoization – an example in Java using dynamic proxy classes to create a generic memoization pattern. ( archived version of http://www.onjava.com/pub/a/onjava/2003/08/20/memoization.html ).
memoization.java - A Java memoization library.
C++Memo – A C++ memoization framework.
C-Memo – Generic memoization library for C, implemented using pre-processor function wrapper macros.
Tek271 Memoizer – Open source Java memoizer using annotations and pluggable cache implementations.
memoizable – A Ruby gem that implements memoized methods.
Python memoization – A Python example of memoization.
OCaml memoization – Implemented as a Camlp4 syntax extension.
Memoization in Lua – Two example implementations of a general memoize function in Lua.
Memoization in Mathematica – Memoization and limited memoization in Mathematica.
Memoization in Javascript – Extending the Function prototype in JavaScript ( archived version of http://talideon.com/weblog/2005/07/javascript-memoization.cfm ).
Memoization in Javascript – Examples of memoization in javascript using own caching mechanism and using the YUI library
X-SAIGA – eXecutable SpecificAtIons of GrAmmars. Contains publications related to top-down parsing algorithm that supports left-recursion and ambiguity in polynomial time and space.
Memoization in Scheme – A Scheme example of memoization on a class webpage.
Memoization in Combinatory Logic – A web service to reduce Combinatory Logic while memoizing every step in a database.
MbCache – Cache method results in .NET.

Etymology

Overview

Other considerations

Functional programming

Automatic memoization

Parsers

See also

References

External links