Specifications: the Good, the Bad, and the Ugly

One can define a prime number as an integer greater than 1 that has no divisors other than 1 and itself. This is a declarative definition: it says what a prime number is rather than how to get one. One can also appeal to the Sieve of Eratosthenes. This would be a procedural definition. It is the opposite of declarative and it only tells how to get prime numbers.

In Software Engineering it is considered bad form to specify a function by pseudocode or by a reference implementation; a proper specification is supposed to be declarative. This blanket preference for the declarative assumes that such specifications are always better: easier to understand and to write. This is indeed the case with prime numbers, but not always. In the case of the Reef Knot, the Bowline, or any other kind of knot, a declarative definition, though perhaps possible, is likely to be less useful than being shown how to make one, which is procedural. Here I consider an example where it is easy to compare the merits of the Good (declarative), the Bad (procedural), and an even less respectable third approach.

Example: Scoring in "Mastermind"

Consider the game of Mastermind (trademark of Parker Bros.). In this game there are two players, the "Codemaker" and the "Codebreaker", each on opposite sides of a board that is specific to this game. On the Codemaker side there are n slots in which code pegs are placed by the Codemaker. Each of these are in one of m colours (red, green, blue, ...). The code pegs are concealed by a shield from the Codebreaker.

The Codebreaker tries to replicate the code on his side of the board. Each of these attempts takes the form of a probe, a sequence of n code pegs. On the Codebreaker's side there is room for several of such probes. For each probe the Codemaker determines a score, which indicates how close the probe is to the code. The score consists of a set of "key pegs", each of which is black or white. We are here concerned with specifying the scoring function, a function that maps a pair consisting of a code and a probe to the appropriate set of key pegs.

Suppose now that I want to write a program to compute the score from a given code and a given probe. Proper Software Engineering requires me to write a specification first so as to make it easier to write the program. Below you find a C program, which I find easy to write and to read. I have also made an attempt to write a declarative specification, which I find to be neither easy to write nor to read. This does not, of course prove that the Software Engineering method is wrong: I may just be singularly inept at writing specifications. All I can say is that the one shown below is the best I could come up with.

What is the basis of both of the program and of the specification? All we have to go on are the directions to prospective players given by Parker Bros., the manufacturer of the game:

Black key pegs are placed by the Codemaker in any of the key peg holes for every code peg placed by the Codebreaker which has the colour and is in exactly the same position as one of the code pegs behind the shield.
White key pegs are placed by the Codemaker in any of the key peg holes when any hidden code peg behind the shield matches the Codebreaker's code pegs in colour only but not in position.

Consider the following situation:

     Codemaker     B  Y  G  B
     Codebreaker   Y  W  Y  Y

Here the Codebreaker has three yellow (Y) code pegs, all of which "match the Codemaker's code pegs in colour only, but not in position". Or is it only one?

The Parker Bros. are apparently aware of the difficulty, but have given up on trying to formulate an adequate description, because they add, rather lamely,

Example: If one red code peg is behind the shield and the Codebreaker places two red code pegs in the [sic] position, ONE white key peg is used.

The rule as formulated by Parker Bros has a declarative flavour. I will try harder than they have done in attempting to give an adequate declarative description. For comparison, I will also give procedural descriptions, in English as well as in the C programming language. All of these will be more complex and harder to read than the inadequate one by Parker Bros.

Finally, I will address the phenomenon that the customers of Parker Bros have no trouble in scoring. This is remarkable: Parker Bros does not tell them, so how do they know? Why do I think I know? Although it is not in the given description, we all seem to agree, and I bet Parker Bros also agrees.

That's a mystery.

A procedural description in C

typedef enum{white, green, yellow, red, black, blue} colour;
typedef enum{false, true} bool;
typedef struct{int blacks; int whites;} score;

score scoreFn(colour code[], colour probe[], int n) {
  score s = {0, 0};
  bool cc[n];  // characteristic function for subset of code[]
  bool pp[n];  // characteristic function for subset of probe[]
  for(int i=0; i < n; i++) {
    if (code[i] == probe[i]) {
      s.blacks++;
      cc[i] = pp[i] = false;
      // this pair is counted; remove it
    }
    else cc[i] = pp[i] = true;
    // check this pair later for white scoring peg
  }
  for(int i=0; i < n; i++) {
    for(int j=0; j < n; j++) {
      if (cc[i] == true && pp[j] == true
          // both pegs present
          && code[i] == probe[j]) {
        s.whites++;
        cc[i] = pp[j] = false;
        // remove both pegs
      }
    }
  }
  return s;
}

A declarative specification

Given are sequences c and p of n colours. To specify scoring is to specify the functions b(c,p) and w(c,p) giving the numbers of black and white scoring pegs, respectively.

A strong match between c and p is a pair [c_i, p_i] such that c_i = p_i.

Two pairs [c_i, p_j] and [c_k, p_l] are disjoint iff i and k are not equal and j and l are not equal.

A weak match between c and p is a pair [c_i, p_j] such that it is disjoint from any strong pair and such that c_i = p_j.

b(c,p) is the number of strong matches between c and p.

Lemma: All maximal sets of mutually disjoint weak matches have the same size.

w(c,p) is the size of a maximal set of mutually disjoint weak matches.

An informal procedural description

If we don't have hang-ups about the need for declarative specifications and if we don't need to instruct a computer in the skill of scoring, then we can just say:

For each location where the code and probe have a peg of the same colour, remove both, and place a black scoring peg.
For each code peg and probe peg that have the same colour, remove both, and place a white scoring peg.

This works because it is procedural: it appeals to a state, and this state changes as a result of the prescribed actions. The action of removing pegs avoids the ambiguity in the directions given by the Parker Bros.

On the role of examples

Parker Bros relied on an example to supplement their attempt at a declarative specification. It is unlikely that this single example nails down all possible completions of the incomplete specification. Yet it seems to be enough for everyone to complete the specification and to arrive at the same completion. How is this possible? Is it perhaps so that we, as a species, have an innate sense of what is simplest, or most natural, and that this example was enough for all our brains to latch onto this? If this is so, then perhaps examples are all we need. It is the contention of Machine Learning that programs can be written on the basis of examples only, and automatically so. Maybe we can use examples instead of a definition rather than as a redundant supplement to an attempt at a self-sufficient definition.

It may be objected that examples can never be more than a hand-waving substitute for rules, justified only in situations where those whose job it is to emit the knowledge are too stupid to write rules or where those who need to absorb the knowledge are too stupid to understand them. It may be that examples can unambiguously determine the simplest function that is exemplified by the given examples.

I can imagine that we order all descriptions compatible with a given set of examples and find that the one with least Kolmogorov complexity is much simpler than the next simplest. Then we take this as the one that is defined by the examples. I can also imagine that our brains are so wired that we jump to the conclusion that this is the intended description.

Conclusions

For the concept of Prime Number, a declarative definition is easiest to give. In the case of a knot, a procedural one is easiest. The scoring function for the game of Master Mind is easier to define procedurally than declaratively, at least in my experience. In practice an incomplete declarative definition supplemented by an incomplete set of examples has been found satisfactory. This makes one wonder whether a function that is the least complex generalization of a set of examples would also work.