Previous Up Next

9.5  Stores

A store is an anonymous object which can be used to store information across failures. A typical application is aggregating information across multiple solutions. Note that, if it is not necessary to save information across backtracking, the use of the library(hash) is more appropriate and efficient than the facilities described here.

A store is a hash table which can store arbitrary terms under arbitrary ground keys. Modifications of a store, as well as the entries within it, survive backtracking. The basic operations on stores are entering and looking up information under a key, or retrieving the store contents as a whole.

Stores come in two flavours: anonymous stores are created with store_create/1 and referred to by handle, while named stores are created with a store/ 1 declaration and referred to by their name within a module. If possible, anonymous stores should be preferred because they make it easier to write robust, reentrant code. For example, an anonymous store automatically disappears when the system backtracks over its creation, or when the store handle gets garbage collected. Named stores, on the other hand, must be explicitly destroyed in order to free the associated memory.

Data is entered into a store using store_set/3 and retrieved using store_get/3. It is also possible to retrieve information: either all keys with stored_keys/2, or the full contents of the table with stored_keys_and_values/2. Entries can be deleted via store_delete/2 or store_erase/1.

A typical use of stores is for the implementation of memoization. The following is an implementation of the Fibonacci function, which uses a store to remember previously computed results. It consists of the declaration of a named store, a wrapper predicate fib/2 that handles storage and lookup of results, and the standard recursive definition fib_naive/2:

    :- local store(fib).

    fib(N, F) :-
        ( store_get(fib, N, FN) ->
            F = FN                    % use a stored result
        ;
            fib_naive(N, F),
            store_set(fib, N, F)      % store computed result
        ).

    fib_naive(0, 0).
    fib_naive(1, 1).
    fib_naive(N, F) :-
        N1 is N-1, N2 is N-2,
        fib(N1, F1), fib(N2, F2),
        F is F1 + F2.

Using this definition, large function values can be efficiently computed:

    ?- fib(300, F).
    F = 222232244629420445529739893461909967206666939096499764990979600
    Yes (0.00s cpu)

The next example shows the use of an anonymous store, for computing how many solutions of each kind a goal has. The store is used to maintain counter values, using the solution term as the key to distinguish the different counters:

    solutions_profile(Sol, Goal, Profile) :-
        store_create(Store),
        (
            call(Goal),
            store_inc(Store, Sol),
            fail
        ;
            stored_keys_and_values(Store, Profile)
        ).

Running this code produces for example:

    ?- solutions_profile(X, member(X, [a, b, c, b, a, b]), R).
    X = X
    R = [a - 2, b - 3, c - 1]
    Yes (0.00s cpu)

Previous Up Next