Index
Memoize
This functor provides memoization of functions.

NOTE: Memoize2: accessing memoized values is slow -- it can be far
slower than recomputing the memoized values! Efficiency of
memo-functions lookup is only linear time (!) and depends on the
number of results already cached (i.e. lookup is not performed in
constant time as perhaps expected, because currently there exists
no constant time implementation of RecordC.reflectHasFeature). It
may still be sufficiently efficient in a CSP when used for avoiding
redundant propagators, but you may want to compare the performance
with and without memoization...

Functor

Import

Export

Define

proc{Memoize Fn ClearP MemoFn}
Expects a unary function Fn (expecting a list of values and returning a value) and returns the corresponding memoized function MemoFn (ie. a function which caches the result for specific arguments and returns this pre-computed value again when called with the same arguments instead of computing the value again, see 'Norvig. Paradigms of Aritificial Intelligence Programming, 1992' for details). Additionally, the nullary proc ClearP is returned: calling ClearP clears the cache for MemoFn.

The identity of the memoized function arguments is checked with a function GetID. This function can be set with SetGetID, and must return a unique key (a name, atom or an integer) for every unique function argument. Also, the memoized function arguments must be values for which their unique key can be computed. GetID defaults to fun {$ X} {X getID($)} end, that is, per default a memoized function must expect a list of score objects with a unique determined ID or a free ID.
In case the ID retured by GetID is a free variable, then this variable is set to a unique integer. The minimum integer ID can be specified with SetMinID.

The definition of the original function is not changed (in contrast to the Lisp implementation of Norvig) and thus recursive functions are not well memoized. Only the top-level call of the recursive function would get memoized but internally the function would call the original unmemoized version. Note that memoization is usually most effectful at recursive functions, whereas the present Memoize is useful only under very specific circumstances.

Memoize performs stateful operations and is therefore not applicable in a CSP. For CSP use Memoize2 instead.

Memo-functions are not thread save. In case the result for a particular set of arguments is not yet cached and the function is called with the same args (args with the same keys) in parallel, the cache will be set twice (in case of inconsistent values, an exception will be raised). Similarily, setting the ID of a value is not thread-save either.
TODO: these operations could be made thread-save by locking multiple sub-operations within the functor MultiDict.

Lookup with Memoize is far more efficient than Memoize2. Still, you better check whether memoization is really more efficient than recomputing...
proc{ClearAll }
Clears the cache of all memoized functions.


proc{Memoize2 Fn MemoFn}
Like Memoize, but completely stateless. Functions memoized with Memoize2 are not cleared with ClearAll (in contrast to functions created with Memoize), but for functions local to CSPs this is not necessary.
Memoize2 is intended for locally use in CSP where its use can avoid re-applying redundant propagators.
Efficiency of memo-functions lookup is only linear time (!) and depends on the number of results already cached (i.e. lookup is not performed in constant time as perhaps expected, because currently there exists no constant time implementation of RecordC.reflectHasFeature).

BUG: setting IDs automatically does presently _not_ work from inside a local space (i.e. during search): implicitly called function MakeID is stateful operation.
Workaround for now: set IDs of score objects manually (the method getID returns the ID of an object, which is free, by default).
proc{SetGetID Fn}
Sets the function which accesses the unique ID of an argument to a memoization function. This must be a name, atom or an integer. Alternatively, the value returned by Fn may be a free variable. In that case, this variable gets implicitly bound to a unique integer (see SetMinID).
The default GetIdFn is fun {$ X} {X getID($)} end.
NOTE: the use of SetGetID is not thread-safe. SetGetID performs a stateful operation and may overwrite the key expected by a concurrent computation. Workaround: create a unique Memo module with Module.link for each key needed.
proc{SetMinID Min}
A memo-function created by Memoize recognises values by their ID. In case this ID is a free variable, it is determined to a unique integer.
SetMinId sets the minimum ID. This allows to avoid conflicts of automatically created IDs with IDs created by hand. The default min ID is 0.
Please note that SetMinID should only be called once before calling any memoized function (otherwise ID conflicts may happen and multiple objects may be assigned the same ID). If it is called multiple times, the new setting is ignored in case it is less than the next automatic ID in order to avoid conflicts.

End