array), a real call is made to factorial 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 factorial, a new function object memfact is created as follows: memfact = construct-memoized-functor(factorial) The above example assumes that the function factorial has already been defined before the call to construct-memoized-functor is made. From this point forward, memfact(n) 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