8.11 Blackboard Primitives

The predicates described in this section store arbitrary terms in a per-module repository known as the “blackboard”. The main purpose of the blackboard was initially to provide a means for communication between branches executing in parallel, but the blackboard works equally well during sequential execution. The blackboard implements a mapping from keys to values. Keys are restricted to being atoms or small integers, whereas values are arbitrary terms. In contrast to the predicates described in the previous sections, a given key can map to at most a single term.

Each Prolog module maintains its own blackboard, so as to avoid name clashes if different modules happen to use the same keys. The “key” arguments of these predicates are subject to module name expansion, so the module name does not have to be explicitly given unless multiple Prolog modules are supposed to share a single blackboard.

The predicates below implement atomic blackboard actions.

bb_put(:Key, +Term)

A copy of Term is stored under Key. Any previous term stored under the same Key is simply deleted.

bb_get(:Key, ?Term)

If a term is currently stored under Key, a copy of it is unified with Term. Otherwise, bb_get/2 silently fails.

bb_delete(:Key, ?Term)

If a term is currently stored under Key, the term is deleted, and a copy of it is unified with Term. Otherwise, bb_delete/2 silently fails.

bb_update(:Key, ?OldTerm, ?NewTerm)

If a term is currently stored under Key and unifies with OldTerm, the term is replaced by a copy of NewTerm. Otherwise, bb_update/3 silently fails. This predicate provides an atomic swap operation.

The following example illustrates how these primitives may be used to implement a “maxof” predicate that finds the maximum value computed by some nondeterminate goal, which may execute in parallel. We use a single key max. Note the technique of using bb_update/3 in a repeat-fail loop, since other execution branches may be competing for updating the value, and we only want to store a new value if it is greater than the old value.

We assume that Goal does not produce any “false” solutions that would be eliminated by cuts in a sequential execution. Thus, Goal may need to include redundant checks to ensure that its solutions are valid, as discussed above.

     maxof(Value, Goal, _) :-
             bb_put(max, -1),                % initialize max-so-far
             call(Goal),
             update_max(Value),
             fail.
     maxof(_, _, Max) :-
             bb_delete(max, Max),
             Max > 1.
     
     update_max(New):-
             repeat,
               bb_get(max, Old),
               compare(C, Old, New),
               update_max(C, Old, New), !.
     
     update_max(<, Old, New) :- bb_update(max, Old, New).
     update_max(=, _, _).
     update_max(>, _, _).