Did you know ... Search Documentation:
Pack memo -- prolog/memo.pl
PublicShow source

This module provides the ability to store the results of expensive to run deterministic predicates to save recomputation. The memo table can be volatile (in memory only) and therefore lost when SWI terminates, or stored persistently on disk using the facilities provided by library(persistency).

Suppose you have a predicate expensive/4 which is deterministic with two inputs and two outputs, eg, its PlDoc comment could look like this:

%% expensive(+In1:atom, +In2:int, -Out1:float, -Out2:compound) is det.

Then a volatile memo could be declared with the following directive:

:- volatile_memo expensive( +atom, +int, -float, -compound).

This causes a dynamic predicate expensive/5 to be declared (the extra argument is for metadata about the computation that produced the result). It also causes the definition of the predicate expensive/4 to be renamed to compute_expensive/4, and a new expensive/4 is generated which looks in the memo table (expensive/5) to avoid recomputations.

To declare a persistently memoised predicate, you would use

:- persistent_memo expensive( +atom, +int, -float, -compound).

This causes a persistent predicate expensive/5 to be declared via facilities provided by library(persistency). Otherwise, things look the same externally (there are some internal differences). It is the caller's responsibility to attach a persistent database.

Argument specifiers

Each volatile_memo/1 or persistent_memo/1 directive can contain one or more predicate declarations, where each argument of the predicate declaration term specifies an input or out argument of the predicate to be memoised. The predicate will be treated as semi-deterministic in the sense that it will succeed at most once for each combination of inputs. Each argument specifier must look like one of these:

+ Type
An input of type Type.
+ Name:Type
An input named Name of type Type.
- Type
An output of type Type.
- Name:Type
An output named Name of type Type.

Meta-level interface

Memoised predicates can be accessed at a 'meta-level' using some meta-predicates which you can think of as modal operators.

First of all, each memoised call to the base predicate has some recorded meta-data whose type is metadata, defined below:

metadata    == pair(comp_event,result).
pair(A,B)  ---> A-B.
result     ---> ok ; fail ; ex(any).
comp_event ---> comp(hostname,time,duration)
              ; comp(hostname,duration)
              ; none.
hostname == ground.
time     == float.
duration == float.

Thus, the meta-data can record the computer on which the computation was done, the time it was called (as returned by get_time/1), the duration of the computation in seconds, and whether or not the computation succeeded, failed, or threw an exception. The fact that failures and exception-throwings are recorded means that object level interface (eg expensive/4 in the example above) avoids repeating unsuccessful computation as well as successful ones.

The meta-level browse/1 and browse/2 allow you to access this information. browse(Goal) is a nondeterministic predicate which unifies Goal with all the successful calls in the memo table. browse(Goal,Meta) matches all calls in the memo table including unsuccessful ones.

The meta-level clear_all/1 and clear_all/2 allow you to delete memo table entries. The meta-level memo(Goal) is the same as the object level Goal, failing or throwing an expection depending on what the underlying predicate does, but the meta-level memo(Goal,Meta) catches failures and exceptions, returning the meta-data in Meta.

Finally, the meta-level compute/1 by-passes all the memoisation machinery and calls the original underlying predicate directly. This is useful in cases where you absolutely need any side-effects caused by the original computation. compute/2 is the same except that failures and exceptions are reified as meta-data.

Setting the host name

The meta-data includes the host name of the computer used to do the computations. On a Unix system, this should get picked up from the environment automatically, using getenv('HOSTNAME',Hostname) (see getenv/2) OR, if this fails, by calling the shell command 'hostname'.

TODO:

  • check for duplicate declarations
  • check for missing predicate definitions
 memo_attach(:Spec:filespec, +Options:list) is det
Convenience wrapper for db_attach/2. Attaches a persistent database file. Spec is interpreted by absolute_file_name/3, with a default extension of 'db'.
 volatile_memo(+Spec) is det
Directive to declare memoised predicates. Spec can be a single memo predicate specifier or several comma separated ones, as with dynamic/1 etc, for example,
:- volatile_memo pred1( ArgSpec1, ArgSpec2),
        pred2(ArgSpec3,ArgSpec4,ArgSpec5).

where ArgSpec1 etc are argument specifiers= as defined in the module header comment. It must look like +Type, -Type, +Name:Type or -Name:Type. Name, if given is not used.

 persistent_memo(+Spec) is det
Directive to declare memoised predicates. Spec can be a single memo predicate specifier or several comma separated ones, as with dynamic/1 etc, for example,
:- persistent_memo pred1( ArgSpec1, ArgSpec2),
                   pred2( ArgSpec3, ArgSpec4, ArgSpec5).

where ArgSpec1 etc are argument specifiers= as defined in the module header comment. It must look like +Type, -Type, +Name:Type or -Name:Type. Name, if given is only used for the declaration of the persistent memo table.

 browse(+Goal:callable, ?Meta:metadata) is nondet
 browse(+Goal:callable) is nondet
Looks up previous computations of memoised predicate Goal. browse/1 unifies Goal with all successful computations. browse/2 unifies Goal and Meta with all computations, including failed or exception-throwing computations. browse(Goal) is equivalent to browse(Goal, _-ok).
 clear_all(@Goal:callable, @Meta:metadata) is det
 clear_all(@Goal:callable) is det
Clears all matching entries from the memo tables that unify with Goal. clear_all/2 additionally allows selection on the basis of meta-data. Deletion is NOT undone on backtracking.

Asks for confirmation if more than N entries are to be deleted, where N is determined by the setting memo:confirmation_threshold (see library(settings)). The default is 1. The confirmation message is printed with ansi_format/3 using a style determined by setting memo:confirmation_style, whose default is [bold,fg(red)]. The user must type "yes" and press return continue, otherwise an operation_cancelled is thrown.

 compute(+Goal:callable) is semidet
Calls the original un-memoised predicate without checking or modifying memo-tables.
 compute(+Goal:callable, -Meta:metadata) is det
Calls the original un-memoised predicate without checking or modifying memo-tables. If the underlying predicate fails or throws an exception, Meta is set accordingly.
 recompute_all(+Goal:callable, @Meta:metadata, @Res:result) is semidet
Recomputes all memoised computations matching Goal and Meta. This will recompute all the entries that would have been returned by browse/2. The only extra condition is that Goal cannot be unbound on entry -- only one determinate predicate can be recomputed at a time. The old entry is removed only after the new computation produces a result that unifies with Res. Otherwise, the recomputed version is discarded.
 memo(+Goal:callable, -Meta:metadata) is semidet
 memo(+Goal:callable) is semidet
Calls memoised predicate if it has not been called before with these input arguments, storing the result, or looks up previous matching computations if they exist. Goal must be sufficiently instantiated to satisfy the underlying memoised predicate. memo/1 and memo/2 behave differently if the underlying predicate fails or throws an exception. memo/1 reflects this behaviour, failing or throwing the same exception, even if the computation was not actually repeated but was retrieve from the memo table. memo/2 reifies this behaviour, returing information in Meta.

Note that the types are checked strictly. An Input argument X declared with +T must satisfy must_be(T,X). An output argument declared with a -T may be bound or unbound. If it is bound, the predicate behaves as if it were unbound, followed by a final semi-deterministic unification. (Prior to v0.5.0, outputs had to be unbound.)

 current_mode(-Mode:oneof([memo,browse,compute])) is det
Gets the current memoisation mode.
 call_with_mode(+Mode:oneof([memo,browse,compute]), +Goal:callable) is nondet
Executes an arbitrary Prolog goal with the current memo-evaluation-mode set to Mode. Thus, any calls to memoised predicates result in calls to memo/1, browse/1 or compute/1 respectively.
 memo_property(-Goal, -Prop:memo_property) is nondet
memo_property ---> type(typespec)
                 ; storage(oneof([persistent,volatile]))
                 ; count(natural).                   .

Enumerates memoised and their properties.

 meta_property(+Meta:metadata, -Prop:meta_property) is nondet
True when Prop is a meta-property of a memoised computation, where Meta is the metadata term retrieved from memo/2 or browse/2. Valid properties are:
duration(number)
The duration of the computation in seconds.
time(timestamp)
The time at which the computation was initiated, as returned by get_time/1
host(atom)
The name of host on which the computation was performed.
result(result)
The success/fail status of the result

Undocumented predicates

The following predicates are exported, but not or incorrectly documented.

 memo(Arg1)
 browse(Arg1)
 clear_all(Arg1)
 modally(Arg1)