Editing Memoization (section)

==Other considerations==
===Functional programming===
{{main|Thunk#Functional programming}}
{{expand section|date=April 2014}}
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 [[thunk]]s 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''.<ref name="Norvig1991" /> The techniques employed by [[Peter Norvig]] have application not only in [[Common Lisp]] (the language in which his paper demonstrated automatic memoization), but also in various other [[programming language]]s. Applications of automatic memoization have also been formally explored in the study of [[term rewriting]]<ref name="Hoffman1992">{{cite book |last=Hoffman |first=Berthold |chapter=Term Rewriting with Sharing and Memoïzation |title=Algebraic and Logic Programming: Third International Conference, Proceedings, Volterra, Italy, 2–4 September 1992 |series=Lecture Notes in Computer Science |editor-first=H. |editor-last=Kirchner |editor2-first=G. |editor2-last=Levi |pages=128–142 |year=1992 |volume=632 |location=Berlin |publisher=Springer |isbn=978-3-540-55873-6 |doi=10.1007/BFb0013824 }}</ref> and [[artificial intelligence]].<ref name="MayfieldEtAl1995">{{cite book |last1=Mayfield |first1=James |first2=T. |last2=Finin |first3=M. |last3=Hall |display-authors=1 |chapter-url=http://ebiquity.umbc.edu/get/a/publication/799.pdf |chapter=Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems |title=Proceedings of the Eleventh IEEE Conference on Artificial Intelligence for Applications (CAIA '95) |pages=87–93 |year=1995 |doi=10.1109/CAIA.1995.378786 |hdl=11603/12722 |isbn=0-8186-7070-3 |s2cid=8963326 }}</ref>

In programming languages where functions are [[first-class object]]s (such as [[Lua (programming language)|Lua]], [[Python (programming language)|Python]], or [[Perl]]<ref name="perl-firstclass">{{cite web|title=Bricolage: Memoization|url=http://perl.plover.com/MiniMemoize/memoize.html}}</ref>), 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):
<!-- don't remove trailing whitespace from blank lines within the block -->
 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
<!-- don't remove trailing whitespace from blank lines within the block -->
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 [[closure (computer science)|closure]]s, memoization can be effected ''implicitly'' via a [[function object|functor]] factory that returns a wrapped memoized function object in a [[decorator pattern]]. In pseudocode, this can be expressed as follows:
<!-- don't remove trailing whitespace from blank lines within the block -->
 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 (computer science)|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
<!-- don't remove trailing whitespace from blank lines within the block -->
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:
<!-- don't remove trailing whitespace from blank lines within the block -->
 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
<!-- don't remove trailing whitespace from blank lines within the block -->
(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 parsing|top-down parser]] tries to parse an [[syntactic ambiguity|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 parser|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.<ref name="Norvig1991"/> The basic idea in Norvig's approach is that when a parser is applied to the input, the result is stored in a memotable for subsequent reuse if the same parser is ever reapplied to the same input.

Richard Frost and Barbara Szydlowski also used memoization to reduce the exponential time complexity of [[parser combinator]]s, describing the result as a memoizing purely functional top-down backtracking language processor.<ref name="Frost1996">{{cite journal |last1=Frost |first1=Richard |last2=Szydlowski |first2=Barbara |title=Memoizing Purely Functional Top-Down Backtracking Language Processors |journal=Sci. Comput. Program. |year=1996 |volume=27 |issue=3 |pages=263–288 |doi=10.1016/0167-6423(96)00014-7 |doi-access=free }}</ref> Frost showed that basic memoized parser combinators can be used as building blocks to construct complex parsers as executable specifications of CFGs.<ref name="Frost1994">{{cite journal |last=Frost |first=Richard |title=Using Memoization to Achieve Polynomial Complexity of Purely Functional Executable Specifications of Non-Deterministic Top-Down Parsers |journal=SIGPLAN Notices |year=1994 |volume=29 |issue=4 |pages=23–30 |doi=10.1145/181761.181764 |s2cid=10616505 }}</ref><ref name="Frost2003">{{cite book |last=Frost |first=Richard |year=2003 |chapter=Monadic Memoization towards Correctness-Preserving Reduction of Search |title=Canadian Conference on AI 2003 |series=Lecture Notes in Computer Science |volume=2671 |pages=66–80 |isbn=978-3-540-40300-5 |doi=10.1007/3-540-44886-1_8 }}</ref> 

Memoization was again explored in the context of parsing in 1995 by Mark Johnson<!-- note:don't wikify name: not same MarkJ --> and Jochen Dörre.<ref name="Johnson1995">{{cite journal |last=Johnson |first=Mark |arxiv=cmp-lg/9504016 |title=Memoization of Top-Down Parsing |journal=Computational Linguistics |volume=21 |issue=3 |pages=405–417 |year=1995 |bibcode=1995cmp.lg....4016J }}</ref><ref name="Johnson&Dorre">{{cite book |last1=Johnson |first1=Mark |last2=Dörre |first2=Jochen |name-list-style=amp |arxiv=cmp-lg/9504028 |chapter=Memoization of Coroutined Constraints |title=Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics |location=Cambridge, Massachusetts |year=1995 }}</ref> In 2002, it was examined in considerable depth by Bryan Ford in the form called [[Packrat parser|packrat parsing]].<ref name="Ford2002">{{cite thesis |last=Ford |first=Bryan |title=Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking |type=Master’s thesis |publisher=Massachusetts Institute of Technology |year=2002 |hdl=1721.1/87310 }}</ref>

In 2007, Frost, Hafiz and Callaghan{{citation needed|date=December 2017}} described a top-down parsing algorithm that uses memoization for refraining redundant computations to accommodate any form of ambiguous CFG in [[polynomial]] time ([[Big O notation|Θ]](n<sup>4</sup>) for [[left recursion|left-recursive]] grammars and Θ(n<sup>3</sup>) 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]].<ref name="Tomita1985">{{cite book |author-link=Masaru Tomita |last=Tomita |first=Masaru |title=Efficient Parsing for Natural Language |publisher=Kluwer |location=Boston |year=1985 |isbn=0-89838-202-5 }}</ref> 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{{citation needed|date=December 2017}} as a set of [[higher-order function]]s (called [[parser combinators]]) in [[Haskell (programming language)|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 [http://www.cs.uwindsor.ca/~hafiz/proHome.html 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<ref name="Johnson&Dorre"/> demonstrate another such non-speed related application of memoization: the use of memoization to delay linguistic constraint resolution to a point in a parse where sufficient information has been accumulated to resolve those constraints. By contrast, in the speed optimization application of memoization, Ford demonstrated that memoization could guarantee that [[parsing expression grammar]]s could parse in [[Big O notation|linear]] time even those [[Formal language|languages]] that resulted in worst-case backtracking behavior.<ref name="Ford2002"/>

Consider the following [[Formal grammar|grammar]]:

 S → (A '''c''') | (B '''d''')
 A → X ('''a'''|'''b''')
 B → X '''b'''
 X → '''x''' [X]

(Notation note: In the above example, the [[Formal grammar#The syntax of grammars|production]] S → (A '''c''') | (B '''d''') reads: "An ''S'' is either an ''A'' followed by a '''c''' or a ''B'' followed by a '''d'''." The production X → '''x''' [X] reads "An ''X'' is an '''x''' followed by an optional ''X''.")

This grammar generates one of the following three variations of [[String (computer science)|string]]: ''xac'', ''xbc'', or ''xbd'' (where ''x'' here is understood to mean ''one or more ''x''<nowiki>'</nowiki>s''.) Next, consider how this grammar, used as a parse specification, might effect<!--to carry out, not "affect"--> a top-down, left-right parse of the string ''xxxxxbd'':

:The rule ''A'' will recognize ''xxxxxb'' (by first descending into ''X'' to recognize one ''x'', and again descending into ''X'' until all the ''x''<nowiki>'</nowiki>s are consumed, and then recognizing the ''b''), and then return to ''S'', and fail to recognize a ''c''. The next clause of ''S'' will then descend into B, which in turn '''again descends into ''X''''' and recognizes the ''x''<nowiki>'</nowiki>s by means of many recursive calls to ''X'', and then a ''b'', and returns to ''S'' and finally recognizes a ''d''.

The key concept here is inherent in the phrase '''again descends into ''X'''''. The process of looking forward, failing, backing up, and then retrying the next alternative is known in parsing as backtracking, and it is primarily backtracking that presents opportunities for memoization in parsing. Consider a function <code>RuleAcceptsSomeInput(Rule, Position, Input)</code>, where the parameters are as follows:

* <code>Rule</code> is the name of the rule under consideration.
* <code>Position</code> is the offset currently under consideration in the input.
* <code>Input</code> is the input under consideration.

Let the return value of the function <code>RuleAcceptsSomeInput</code> be the length of the input accepted by <code>Rule</code>, or 0 if that rule does not accept any input at that offset in the string. In a backtracking scenario with such memoization, the parsing process is as follows:

: When the rule ''A'' descends into ''X'' at offset 0, it memoizes the length 5 against that position and the rule ''X''. After having failed at ''d'', ''B'' then, rather than descending again into ''X'', queries the position 0 against rule ''X'' in the memoization engine, and is returned a length of 5, thus saving having to actually descend again into ''X'', and carries on ''as if'' it had descended into ''X'' as many times as before.

In the above example, one or ''many'' descents into ''X'' may occur, allowing for strings such as ''xxxxxxxxxxxxxxxxbd''. In fact, there may be ''any number'' of ''x''<nowiki>'</nowiki>s before the ''b''. While the call to S must recursively descend into X as many times as there are ''x''<nowiki>'</nowiki>s, ''B'' will never have to descend into X at all, since the return value of <code>RuleAcceptsSomeInput(''X'', 0, ''xxxxxxxxxxxxxxxxbd'')</code> will be 16 (in this particular case).

Those parsers that make use of [[syntactic predicate]]s are also able to memoize the results of predicate parses, as well, thereby reducing such constructions as:

 S → (A)? A
 A → /* some rule */

to one descent into ''A''.

If a parser builds a [[parse tree]] during a parse, it must memoize not only the ''length'' of the input that matches at some offset against a given rule, but also must store the sub-tree that is generated by that rule at that offset in the input, since subsequent calls to the rule by the parser will not actually descend and rebuild that tree. For the same reason, memoized parser algorithms that generate calls to external code (sometimes called a [[semantic action routine]]) when a rule matches must use some scheme to ensure that such rules are invoked in a predictable order.

Since, for any given backtracking or syntactic predicate capable parser not every grammar will ''need'' backtracking or predicate checks, the overhead of storing each rule's parse results against every offset in the input (and storing the parse tree if the parsing process does that implicitly) may actually ''slow down'' a parser. This effect can be mitigated by explicit selection of those rules the parser will memoize.<ref name="AcarEtAl2003">{{cite book |last1=Acar |first1=Umut A. |first2=Guy E. |last2=Blelloch |first3=Robert |last3=Harper |display-authors=1 |chapter=Selective Memoization |title=Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 15–17 January 2003 |journal=ACM SIGPLAN Notices |location=New Orleans, Louisiana |pages=14–25 |year=2003 |volume=38 |doi=10.1145/640128.604133 |arxiv=1106.0447 }}</ref>