Pattern and Variation

(Some odd notes, which should be a longer and more thoughtful piece.)

If I ever write a (very slim) book about programming, I’ll probably call it “Pattern and Variation”, because the vast majority of what it means to effectively convert a problem into a representation using code is: first of all, the identification of pattern, where it exists; and then, the identification of where there needs to be variation from that pattern. That’s a huge amount of what programming is, in a nutshell. The complexity of code is like the complexity of a fractal. It’s only apparent complexity, which arises when simple structures are combined many times over.

Often, the best way to approach a problem is also in that order: pattern, then variation. What’s the same about things, and then what’s different about them. Prolog can be such a good way to illustrate this, precisely because predicates are often defined using a single recursive case (the pattern), and a single base case (the variation), so syntactically the division couldn’t be clearer. For example, here’s the canonical recursive bit of member/2:

member(X, [_|T]) :- member(X, T).

What this does is identify the pattern which serves as the foundation for the algorithm: in order to check whether something is a member of a list, in theory we’ll have to check every item in that list, one by one. It says, in effect: something is a member of a list if (but not only if) it’s a member of the list after we’ve removed the first item. So the pattern involves moving down the list, one item at a time. It might just as well be an iterative moving, but in this case it’s recursive.

And here’s the canonical base case:

member(X, [X|_]).

What this does is identify the variation from the pattern that we’ve set up so far. The variation states that if the thing we’re looking for is the first item in the list we’re searching, then we’ve found it, and have succeeded. (Yes, the base case tends to come first in any clause database, but that’s a procedural wrinkle, not a principle.)

Pattern, then variation. The pattern sets up a strong foundation for the algorithm — a wash of colour which serves as the background, if you like — and then the variation adds necessary detail. Or the pattern defines the scope of the algorithm (to search all of the items in a list, for example), then the variation defines its purpose (to find one particular item). Often, the same pattern applies generally, and only the variation changes. For example, any search of an unordered list must involve the pattern of checking every item, one by one. So the foundation is exactly the same. The variation merely identifies exactly what thing we’re looking for. The first odd number in the list:

member(X, [X|_]) :- number(X), odd(X).

Or the first string that’s a palindrome:

member(X, [X|_]) :- reverse(X, X).

Or any of a million other variations.

I’m not a bad programmer. Not great, but not bad. One of the ways I’m not bad is that I think I can see pattern quite easily, and I think that’s a complete prerequisite for competent software design. More than that: a programmer doesn’t need to merely be able to identify pattern; they need to enjoy pattern, to find it seductive and aesthetically pleasing. This is because code which is entirely pattern-based is a kind of ideal, a perfect model of a perfect solution to a perfect problem. Variations are typically wrinkles in the fabric of the algorithm, to be smoothed out wherever possible. The better the programmer is at seeing pattern, the more he’ll be able to minimise the presence of variation. There should be just enough to get the job done, but absolutely no more than that. Each tiny bit of unavoidable variation from the background pattern should cause the competent programmer — after he’s fought against its unavoidability for a while — almost physical discomfort. It should be an affront to his pattern-identification skills.

There’s another reason why variation should be minimised, and it’s a practical rather than aesthetic one: by their very nature patterns apply generally, and variations apply specifically. The more variation exists, the more specific cases exist, and specific cases: increase the complexity of code; and decrease the efficiency of the code syntax. For example: here’s the complete canonical member/2:

member(X, [X|_]).
member(X, [_|T]) :- member(X, T).

Two clauses, of roughly equal complexity. If we imagine that the list we’re searching is a thousand items long, and that the thing we’re looking for occurs only once, if at all, what happens is that the first clause — the variation — fires only in the single case in which we find what we’re looking for (that’s a maximum of once per search), and the second clause — the pattern — fires every other time (a mean of at least 500 times per search, even assuming that the thing we’re looking for is always in the list). So 50% of the code is used about 99.8% of the time, and 50% is used about 0.2% of the time. That’s an odd imbalance.

Things get worse the more variations there are from the underlying pattern. Imagine we’re looking for either a prime number or a palindrome:

member(X, [X|_]) :- prime(X).
member(X, [X|_]) :- reverse(X, X).
member(X, [_|T]) :- member(X, T).

Now, the pattern, which will still fire something like 99.8% of the time during a search, accounts for only 33.3% of the code. As we add more cases, the general pattern, which applies most of the time, gradually becomes overwhelmed in the code by the specific variations, which hardly ever apply. The result is code complexity, in which problems can arise specifically because the complexity mostly resides in code which hardly ever applies. In general this makes coding mistakes easier to make, and harder to detect.

To be sure, variation is necessary, but pattern is the ideal, and variation a necessary evil which should be resisted at all costs. The first defence against proliferation of variation is, of course, effective identification of pattern in the first place. The more an algorithm can be defined using general patterns — and patterns which are truly representative of the problem — the less variation from those patterns is necessary.

Perhaps you can see where I’m going, and why good programmers are often slightly odd creatures. We love pattern. We see it, and appreciate it. It makes us happy. As for myself, I might joke occasionally about being on the borders of Asperger’s — and only joke about it, because I don’t honestly believe that I am — but I can’t pretend that I don’t have tendencies in that direction. My emotional well-being comes from simplicity, order, pattern. My ability to deal with variation from pattern is a function of how well my need for simplicity, order, pattern is being met. In life as in code.