Previous Up Next

4.4  Storing Information Across Backtracking

In pure logic programming, the complete state of a computation is reset to an earlier state on backtracking. The all-solutions predicates introduced in section 3.7.4 provide a way to collect solutions across backtracking.

The following section presents ECLiPSe’s lower-level primitives for storing information across failures: bags and shelves. Both bags and shelves are referred to by handle, not by name, so they make it easy to write robust, reentrant code. Bags and shelves disappear when the system backtracks over their creation, when the handle gets garbage collected, or when they are destroyed explicitly.

4.4.1  Bags

A bag is an anonymous object which can be used to store information across failures. A typical application is the collection of alternative solutions.

A bag is an unordered collection, referred to by a handle. A bag is created using bag_create/1, terms can be added to a bag using bag_enter/2, and the whole contents of the bag can be retrieved using bag_retrieve/2 or bag_dissolve/2. A simple version of the findall/3 predicate from section 3.7.4 can be implemented like: 

simple_findall(Goal, Solutions) :-
        bag_create(Bag),
        (
            call(Goal),
            bag_enter(Bag, Goal),
            fail
        ;
            bag_dissolve(Bag, Solutions)
        ).

4.4.2  Shelves

A shelf is an anonymous object which can be used to store information across failures. A typical application is counting of solutions, keeping track of the best solution, aggregating information across multiple solutions etc.

A shelf is an object with multiple slots whose contents survive backtracking. The content of each slot can be set and retrieved individually, or the whole shelf can be retrieved as a term. Shelves are referred to by a handle.

A shelf is initialized using shelf_create / 2 or shelf_create / 3. Data is stored in the slots (or the shelf as a whole) with shelf_set / 3 and retrieved with shelf_get / 3.

For example, here is a meta-predicate to count the number of solutions to a goal: 

count_solutions(Goal, Total) :-
    shelf_create(count(0), Shelf),
    (
        call(Goal),
        shelf_get(Shelf, 1, Old),
        New is Old + 1,
        shelf_set(Shelf, 1, New),
        fail
    ;
        shelf_get(Shelf, 1, Total)
    ),
    shelf_abolish(Shelf).
Previous Up Next