Editing Memoization (section)

===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.)