11.3. Evolution of the development of the cryptanalysis system

Integration

Now that the key abstractions of the problem domain have been identified, we can proceed to joining them into a working application. We will implement and test vertical slices of the system, and then work through the mechanisms one after another.

Integrating the top-level objects. Figure 11-7 shows the object diagram of our system at the very top level, which corresponds fully to the structure of the blackboard given in Figure 11-1. The physical content of the blackboard objects in the collection theBlackboard and of the knowledge sources in the collection theKnowledgeSources is shown in accordance with the description of the nesting of the classes.

An instance of the class Cryptographer has appeared on the diagram. It aggregates the blackboard objects, the knowledge sources and the controller. As a result our program can have several instances of this class, and consequently several blackboards functioning in parallel.

Figure 11-7. Object diagram of the cryptanalysis system.

Two main operations should be defined for this class:

• reset - Restart the blackboard.
• decipher - Begin deciphering the cryptogram.

The constructor of this class must create the dependencies between the blackboard and the knowledge sources, as well as between the knowledge sources and the controller. The reset method is extremely simple: its purpose is to return these connections and objects to their initial state.

The method decipher takes a string - the cryptogram. Now the high-level functions of our application become extremely simple, as is usually the case in object-oriented systems:

char* solveProblem(char* ciphertext)
{

Cryptographer theCryptographer;
return theCryptographer.decipher(ciphertext);

}

The method decipher turns out to be somewhat more complicated. First of all, by means of the operation assertProblem the task is placed on the blackboard. After that the knowledge sources are activated. And finally, a cyclic process begins in which the knowledge sources turn to the controller with more and more assumptions and assertions until either a solution to the problem is found or the process reaches a dead end. Interaction diagrams or object diagrams could be used for illustration, but the C++ code does not look too complicated either:

theBlackboard.assertProblem();
theKnowledgeSources.reset();
while (!theController.isSolved || !theController.unableToProceed())

theController.processNextHint();

if (theBlackboard.isSolved())

return theBlackboard.retrieveSolution();

Now we had best supplement the algorithm with the appropriate architectural interfaces. Although at the moment its capability is minimal, implementing it as a vertical slice of the system architecture allows us to test the key system decisions.

Let us look at two operations defined in the class decipher, namely assertProblem and retrieveSolution. The first of them is interesting in that it creates the structure of the blackboard. Let us describe our algorithm as follows:

strip all leading and trailing blanks from the string
if the resulting string is empty return
create a sentence object
add the sentence to the blackboard
create a word object (the leftmost one)
add the word to the blackboard
add the word to the sentence
for each character of the string from left to right

if the character is a blank

make the current word the previous one
create a word object
add the word to the blackboard
add the word to the sentence

else

create a "cipher letter" object
add the letter to the blackboard
add the letter to the word

In Chapter 6 it was already mentioned that the aim of design is to create a sketch of the implementation. This notation represents a sufficiently detailed algorithm, so that there is no need to show its full implementation in C++.

The operation retrieveSolution is very simple: it returns the string currently recorded on the blackboard. By invoking this operation before the function isSolved has returned the value True, partial solutions can be obtained.

Implementing the assumption mechanism. So, we now know how to set and retrieve the values of blackboard objects. Now we need a mechanism for putting forward statements about these objects. This mechanism is interesting because of its dynamic nature. In the search for a solution, assumptions are continually created and retracted, and this is precisely what sets the whole process in motion.

Figure 11-8 shows a scenario of putting forward assumptions. A knowledge source reports the assumptions it has to the blackboard, which applies them to the alphabet and notifies the remaining sources.

In the simplest case, in order to retract an assumption, we simply run this mechanism in the opposite direction. For example, to retract an assumption about a letter, we remove from its collection all assumptions up to and including the incorrect one.

Figure 11-8. Putting forward assumptions.

One can act more subtly. Suppose we have assumed that a one-letter word corresponds to I (a vowel is needed). Further, an assumption has been made that some two-letter combination is NN (consonants are needed). If the first assumption turns out to be erroneous, the second may well be retained. With such an approach the class Assumption must be supplemented with one more method that records the connection of assumptions with one another (interdependence). The implementation of this behavior can be deferred to a later time, since it has little effect on the architecture.

Adding the knowledge sources

Now that the key abstractions of the blackboard and the mechanisms for putting forward and checking assumptions have been defined, it is necessary to implement the inference engine (the class InferenceEngine) that binds all the knowledge sources into a single whole. It was mentioned earlier that the inference engine must implement one main operation, namely the carrying out of a rule, evaluateRules. We will not dwell on this in detail, since the implementation does not affect the design decisions.

Having satisfied ourselves that the inference engine works correctly, we can introduce the knowledge sources into the system one after another. The advisability of precisely such a process is explained by two reasons:

• It is difficult to determine in advance which rules are essential for each of the knowledge sources without testing the system on a concrete problem.
• Debugging the knowledge base is substantially simplified when the rules are added one after another.

Implementing the knowledge sources is a matter of knowledge engineering. To build a particular knowledge source, consultation with experts (for example, cryptographers) is required. In analyzing the knowledge sources it may turn out that some rules are useless, others are too specialized or excessively generalized, and some are clearly lacking. After the analysis a source's rules may be modified. Sometimes the creation of a new knowledge source is required.

In the course of implementing the knowledge sources, rules and/or behavior common to several sources may come to light. For example, the knowledge source about word structure and the knowledge source about sentence structure may contain common rules concerning the possible ordering of certain linguistic structures. In both cases the essence of the rule is one and the same, and therefore it makes sense to introduce a new mixin class StructureKnowledgeSource reflecting knowledge about structure, into which this common behavior is placed.

Such a change in the class structure underlines the fact that the process of handling rules is determined not only by the knowledge sources, but also by the nature of the blackboard objects. For example, one of the knowledge sources may implement forward chaining of reasoning with respect to some objects and backward chaining with respect to others. In addition, different knowledge sources may operate differently on one and the same object.