Lecture
The architecture of the blackboard
Now we have everything we need to set about solving the problem at hand using the blackboard metaphor. This is a classic example of reuse "in the large": we are reapplying a proven architectural pattern as the basis of the design. The blackboard method presupposes the following top-level objects: the blackboard, several knowledge sources, and a controller. All that remains is to define the classes and objects of the problem domain that specialize these general abstractions.
Blackboard objects. The objects on the blackboard form a hierarchy that reflects the hierarchical nature of the various levels of abstraction of the knowledge sources. Thus, we have the following three classes:
The knowledge sources must make use of shared information about the assumptions made in the course of solving the problem, and so the following class is included among the blackboard objects:
Finally, the knowledge sources make assumptions about the relationship between the letters of the real and the cipher alphabets, so we introduce the following class:
Is there anything in common among these five classes? The answer is unambiguously yes: they all correspond to objects on the blackboard and in this respect differ substantially from other objects, for example, the knowledge sources and the controller. Therefore the following superclass is introduced for all of the objects listed above:
class BlackboardObject ...
From the standpoint of external behavior, let us define two operations for this class:
Why did we define these two operations on objects of the class BlackboardObject rather than on the blackboard itself? This is similar to the situation in which an object must draw itself in some window. The "litmus" test in such cases is the question: "Does the object itself have enough knowledge and skill to carry out such operations?". Blackboard objects are in fact the ones that best understand how to properly appear on the blackboard or remove themselves from it (of course, they need the help of the blackboard itself in doing so). We established earlier that objects interacting with the blackboard must by their very nature join in the problem-solving process on their own initiative.
Dependencies and affirmations. Sentences, words, and letters are also linked by a certain commonality: for all of them there are corresponding knowledge sources. A particular knowledge source, for its part, may take an interest in one or more such objects (depend on them), and therefore a sentence, a word, and a cipher letter must maintain a connection with the knowledge sources, so that when an assumption is made about the object the appropriate knowledge sources are notified. This resembles the dependency mechanism of the Smalltalk language mentioned in Chapter 4. To implement this mechanism, let us introduce the following mixin class:
class Dependent {
public:
Dependent();
Dependent(const Dependent&);
virtual ~Dependent();
...
protected
UnboundedCollection<KnowledgeSource*> references;
};
We have run a little ahead of ourselves and hinted at a possible implementation of the class in order to show the connection with the library of foundation classes described in Chapter 9. One internal element is defined in the class - a collection of pointers to knowledge sources [In Chapter 9 we noted that unbounded structures require a memory manager. For simplicity we omit this template argument everywhere in this chapter. Of course, a complete implementation must be consistent with the mechanisms of the development environment].
Let us define the following operations for this class:
The last operation is a passive iterator: when it is called, the action that must be performed on all the dependent objects in the collection is passed as a parameter.
Dependency can be mixed into other classes. For example, a cipher letter is a blackboard object on which others depend, and so we can combine these two abstractions to obtain the behavior we need. Such use of mixins encourages reuse and the separation of concepts in our architecture.
Cipher letters and alphabets have one more property in common: assumptions may be made about objects of these classes. Recall that an assumption (Assumption) is one of the objects on the blackboard (BlackboardObject). Thus, some knowledge source may allow that the letter K in the cipher corresponds to the letter P of the original text. As the problem is solved, it may become absolutely certain that G means J. For this reason one more class is introduced:
class Affirmation ...
This class is responsible for statements (assumptions or assertions) about the object associated with it. We use this class not as a mixin, but for aggregation. A letter, for example, is not an assumption, but it may have an assumption about itself.
In our system assumptions are permitted only with respect to individual letters and alphabets. One may, for example, assume that some cipher letter corresponds to some letter of the alphabet. An alphabet consists of a set of letters about which assumptions are made. By defining Affirmation as an independent class, we express in it the similar behavior of these two classes, which are not related by inheritance.
Let us define the following set of operations for instances of this class:
From the preceding discussion it is clear that we must clearly distinguish two roles of statements: temporary assumptions about correspondences between cipher and plaintext letters, and finally proven correspondences - assertions. As the cryptogram is deciphered, a great many different assumptions about the correspondence of cipher and plaintext letters may be made, but in the end final correspondences are found for the whole alphabet. To reflect these roles, let us refine the previously identified class Assumption in the subclass Assertion (assertion). Instances of both classes are managed by objects of the class Affirmation and may be placed on the blackboard. To support the operations make and retract introduced earlier, we need to define the following selectors:
Now we can define the class Assumption. Since this abstraction is of a purely structural nature, its state can be made public:
class Assumption : public BlackboardObject
{
public:
...
BlackboardObject* target;
KnowledgeSource* creator;
String<char> reason;
char plainLetter;
char cipherLetter;
};
Note that we have reused one more class of the environment described in Chapter 9, namely the parameterized class String.
The class Assumption is a blackboard object, since information about the assumptions that have been made is used by all the knowledge sources. The individual members of the class express the following of its properties:
The necessity of each of the properties listed is to a large degree explained by the nature of assumptions: a knowledge source forms a conjectured correspondence "letter of the original text - cipher letter" on the basis of some reasons (usually, some rule). The purpose of the first property, target is less obvious. It is needed for backtracking. If an assumption that has been made turns out not to be confirmed, then we must restore the state of the blackboard objects that made use of the assumption, and they in turn must notify the knowledge sources that their meaning has changed.
Next we define the subclass Assertion:
class Assertion : public Assumption ...
Common to the classes Assumption and Assertion is the following selector:
For all assumptions that have been made, the value of the predicate isRetractable is true, whereas for assertions it is false. An assertion that has been made can no longer be either changed or retracted.
Figure 11-2. Dependency and statement classes.
Figure 11-2 shows a diagram that explains the relationship between the dependency and statement classes. Pay particular attention to the roles that the abstractions mentioned play in the various associations. For example, the class KnowledgeSource in one aspect is the creator (creator) of an assumption, while in another it references (referencer) a cipher letter. Differences in the interaction protocols follow naturally from the differences in roles.
Designing the blackboard objects. Let us complete the design by adding, besides the alphabet class, classes for the sentence (Sentence), the word (Word) and the cipher letter (cipherLetter). A sentence is simply a blackboard object (upon which other objects depend) that contains a list of words. On this basis we write:
class Sentence : public BlackboardObject, virtual public Dependent {
public:
...
protected:
List<Word*> words;
};
The superclass Dependent is declared virtual, since we expect that there will be subclasses of sentence that will also want to inherit from Dependent. In that case the members of the class Dependent will be shared by all such subclasses.
In addition to the operations register and resign (defined in the superclass BlackboardObject) and the four operations inherited from the class Dependent, we add two more operations specific to the sentence:
The initial value of value coincides with the text of the cryptogram. When isSolved becomes true, value will return the original deciphered text.
A word is a blackboard object and a source of dependency. It consists of letters. For the convenience of the knowledge sources, pointers to the whole sentence, as well as to the previous and next words in the sentence, have been introduced into the word class. The declaration of the class Word looks like this:
class Word : public BlackboardObject, virtual public Dependent {
public:
...
Sentence& sentence() const;
Word* previous() const;
Word* next() const;
protected:
List<CipherLetter*> letters;
};
Just as for the sentence, two additional operations are introduced into the word class:
Now we can define the class cipherLetter (cipher letter). Cipher letters are blackboard objects and give rise to dependencies. In addition, they have a value (a letter as it is written in the cipher, for example, н) and a collection of possible assumptions and assertions about its mapping to letters of the plaintext. To organize the collection we use the class Affirmation. We describe the letter class as follows:
class CipherLetter : public BlackboardObject, virtual public Dependent {
public:
...
char value() const;
int isSolved() const;
...
protected:
char letter;
Affirmation affirmations;
};
Note that the same pair of selectors has been added to this class as well, by analogy with the word and sentence classes. For the clients of this object we must provide protected operations for accessing the assumptions and assertions.
The object affirmations included in this class contains a collection of assumptions and assertions in the order in which they were put forward. The last element of the collection contains the current assumption or assertion. The point of storing the sequence in which the problem was solved lies in the possibility of the knowledge sources learning from their own mistakes. For this reason, two additional selectors have been introduced into the class Affirmation:
Having refined the behavior of the class, we can make the right decisions about its implementation. In particular, we will need to introduce the following protected object into the class:
UnboundedOrderedCollection<Assumption*> statements;
This object too has been borrowed by us from the foundation class library of Chapter 9.
Now let us turn to the class Alphabet (alphabet). It holds data about the plaintext and cipher alphabets, as well as about the mapping between them. This information is necessary so that the knowledge sources can learn about the mappings already discovered between cipher letters and plaintext letters and those that still remain to be found. For example, if it has already been proven that the letter с in the cipher corresponds to the letter и of the plaintext, then this mapping is recorded in the alphabet and the knowledge sources will no longer make other assumptions concerning the letter м of the plaintext. For processing efficiency it is useful to be able to obtain data about the correspondence of cipher and plaintext letters in two ways: by cipher letter and by plaintext letter. We define the class Alphabet as follows:
class Alphabet : public BlackboardObject {
public:
char plaintext(char) const;
char ciphertext(char) const;
int isBound(char) const;
};
Just as in the class CipherLetter, in the class Alphabet it is necessary to include a protected object affirmations and to define operations for accessing its state.
Finally, let us define the class Blackboard, which is a collection of instances of the class Blackboardobject and its subclasses:
class Blackboard : public DynamicCollection<BlackboardObject*> ...
Since the blackboard is a kind of collection (the inheritance test), we prefer to form this class by inheritance rather than by including an instance of the class DynamicCollectlon. The operations of adding to and removing from the collection are inherited from the class Collection, while the following five operations, specific to the blackboard, are introduced by us:
The second operation establishes a dependency between the blackboard and the knowledge source. Figure 11-3 gives the resulting diagram of the classes associated with Blackboard. It primarily reflects the inheritance relationships. The using relationships (for example, between Assumption and the blackboard) have been omitted for simplicity.
Figure 11-3. Class diagram of the blackboard.
Note that the class Blackboard both instantiates from the template DynamicCollection and inherits from it. In addition, the use of the class Dependent as a mixin becomes clear. By not tying this class rigidly to the Blackboard hierarchy, we increase the chances of its subsequent reuse.
Designing the knowledge sources
In the previous section we identified thirteen knowledge sources relevant to the problem being solved. Now we can proceed to designing the class structures for them (as was done for the blackboard) and generalizing them into more abstract classes.
Designing the specialized knowledge sources. Suppose that there is an abstract class KnowledgeSource (by analogy with the class BlackboardObject). Before defining all thirteen sources as subclasses of a single common superclass, we should see whether they group together in some way. Indeed, such groups can be found: some knowledge sources operate on the whole sentence, others on words, fragments of words, or individual letters. Let us reflect this fact in the following definitions:
class SentenceKnowledgeSource : public KnowledgeSource ...
class WordKnowledgeSource : public KnowledgeSource ...
class LetterKnowledgeSource : public KnowledgeSource ...
For each of these abstract classes we will subsequently define specialized subclasses. For the class SentenceKnowledgeSource they will look as follows:
class SentenceStructureKnowledgeSource : public SentenceKnowledgeSource ...
class SolvedKnowledgeSource : public SentenceKnowledgeSource ...
Similarly, the subclasses of the class WordKnowledgeSource are defined thus:
class WordStructureKnowledgeSource : public WordKnowledgeSource ...
class SmallWordKnowledgeSource : public WordKnowledgeSource ...
class PatternMatchingKnowledgeSource : public WordKnowledgeSource ...
The last class requires some explanation. It was mentioned earlier that its purpose is to find words by pattern. To describe a pattern we can use the regular expression notation adopted, in particular, in the grep utility of the UNIX system:
Using such notation, we can pass an object of this class the pattern ?E~{A E I O U} so that it searches its dictionary for a three-letter word beginning with some letter, followed by E, and then any letter other than a vowel.
Since pattern matching is a technique useful both for this system as a whole and in other domains, it makes sense to factor the corresponding class out as an independent abstraction. It is therefore not surprising that we will make use of a class from our library (see Chapter 9). As a result our class for pattern matching will look as follows:
class PatternMatchingKnowledgeSource : public WordKnowledgeSource {
public:
...
protected:
static BoundedCollection<Word*> words;
REPatternMatching patternMatcher;
};
All instances of this class share a common dictionary, but each of them can have its own agent for comparing against patterns.
At this stage of design the implementation details of this class are not essential for us, so we will not dwell on them in detail.
Let us now define the subclasses of the class StringKnowledgeSource as follows:
class CommonPrefixKnowledgeSource : public StringKnowledgeSource ...
class CommonSuffixKnowledgeSource : public StringKnowledgeSource ...
class DoubleLetterKnowledgeSource : public StringKnowledgeSource ...
class LegalStringKnowledgeSource : public StringKnowledgeSource ...
Finally, let us define the subclasses of the class LetterKnowledgeSource:
class DirectSubstitutionKnowledgeSource : public LetterKnowledgeSource ...
class VowelKnowledgeSource : public LetterKnowledgeSource ...
class ConsonantKnowledgeSource : public LetterKnowledgeSource ...
class LetterFrequencyKnowledgeSource : public LetterKnowledgeSource ...
What the knowledge sources have in common. Analysis has shown that only two operations are defined for all the specialized classes mentioned:
The reason for this simplified interface lies in the relative autonomy of the knowledge: we point to the blackboard object of interest and give the source the command to apply its rules, taking into account the global state of the blackboard. In carrying out its rules, each of the knowledge sources may perform the following actions:
All these actions are common to all knowledge sources. The listed operations form an inference mechanism. Let us define an inference engine (InferenceEngine) as an object that carries out known rules in order either to find new rules (forward chaining of reasoning) or to prove some hypothesis (backward chaining of reasoning). On this basis we introduce the following class:
class InferenceEngine {
public:
InferenceEngine(<DynamicSet<Rules*>);
...
};
The constructor of the class creates an instance of the object and populates it with rules. Only one operation is made visible to the knowledge sources in this class:
Now about how the knowledge sources cooperate: each specialized source defines its own rules and delegates responsibility for carrying them out to the class InferenceEngine. More precisely, the operation KnowledgeSource::evaluate invokes the method InferenceEngine::evaluate, which leads to the performance of one of the four operations mentioned above. Figure 11-4 shows a scenario of such an interaction:
Figure 11-4. Interactions with a knowledge source.
What is a rule? By way of illustration we give (in Lisp format) a rule concerning knowledge about commonly used suffixes:
((* I ? ?)
(* I N G)
(* I E S)
(* I E D))
This rule means that the given pattern *I?? (the condition - antecedent) may be matched by the suffixes ING, IES and IED (the conclusion - consequent). In C++ the following class can be defined to represent rules:
class Rule {
public:
...
int bind(String<char>& antecedent, String<char>& consequent);
int remove(Strlng<char>& antecedent);
int remove(String<char>t antecedent, String<char>& conseiruent);
int hasConflict(const String<char>& antecedent) const;
protected:
String<char> antecedent;
List<String<char>> consequents;
};
The meaning of the operations given is entirely clear from their names. Here we have reused certain classes from Chapter 9.
From the standpoint of the structure of this class it can be asserted that knowledge sources are a kind of inference engine. In addition, they are associated with blackboard objects, since that is where they find application for their efforts. Finally, each knowledge source is connected to the controller and sends it its considerations. The controller, in turn, can activate the knowledge sources.
Let us express all of this as follows:
class KnowledgeSource : public InferenceEngine, public Dependent {
public:
KnowledgeSource(Blackboard*, Controller*);
void reset();
void evaluate();
protected:
Blackboard* blackboard;
Controller* controller;
UnboundedOrderedCollection<Assumption*> pastAssumptions;
};
A protected data member pastAssumptions has been introduced into this class, allowing the entire history of assumptions to be preserved for the purposes of self-learning.
Instances of the class Blackboard serve to store blackboard objects. For similar reasons, a class KnowledgeSources is also needed, encompassing all the knowledge sources relevant to the problem being solved:
class KnowledgeSources : public DynamicCollection<KnowledgeSource*> ...
One of the properties of this class is that when an instance of it is created, the 13 specialized knowledge sources are created as well. Three operations are defined for objects of this class:
Figure 11-5. Class diagram of the knowledge sources.
Figure 11-5 shows the structure of the knowledge source classes created in the course of design.
Designing the controller
Let us examine in more detail the interaction of the controller with the individual knowledge sources. In the course of the step-by-step deciphering of the cryptogram, individual knowledge sources discover useful information and report it to the controller. On the other hand, it may be discovered that information passed on earlier turned out to be false and must be removed. Since all the knowledge sources have equal rights, the controller must poll them all, choose the one whose information seems most useful, and permit it to make changes by invoking its operation evaluate.
How does the controller determine which of the knowledge sources should be activated? Several reasonable rules can be proposed:
The controller acts as the agent responsible for the interaction of the knowledge sources.
The controller must be in an association relationship with the knowledge sources through the class KnowledgeSources. In addition, it must have as one of its properties a collection of hints ordered by priority. In this way the controller can easily select for activation the knowledge source with the most interesting hint.
After analyzing the class in isolation, we propose introducing the following operations for the class controller:
All these decisions can be described as follows:
class Controller {
public:
...
void reset();
void connect(Knowledgesource&);
void addHint(KnowledgeSource&);
void removeHint(KnowledgeSource&);
void processNextHint();
int isSolved() const;
int unableToProceed() const;
};
The controller is in a certain sense driven by the knowledge sources, and therefore a finite state machine scheme is best suited to describing its behavior.
Consider the state transition diagram in Figure 11-6. From it one can see that the controller may be in one of five main states: initializing (Initializing), selecting (Selecting), evaluating (Evaluating), stuck (Stuck) and solved (Solved). Of greatest interest to us is the behavior of the controller in the transition from selecting to evaluating. In the state selecting the controller goes from creating a strategy (CreatingStrategy) to processing a hint (ProcessingHint) and, in the end, selects a knowledge source (SelectingKS).
Figure 11-6. The controller as a finite state machine.
Having given one of the sources the opportunity to speak, the controller moves to the state Evaluating, where it first of all changes the state of the blackboard. This causes a transition to the state Connecting when a knowledge source is added, or to Backtracking if an assumption has not been borne out and must be backed out, notifying at the same time all the dependent knowledge sources.
The end point of our mechanism's work is solved (the problem has been solved) or stuck (a dead-end situation).
Comments