Software Development

Structural contingency (part one)

Order, in mathematics, matters.

Take two functions, f and g, and compose them, thus applying them to an argument as either f(g(x)) or g(f(x)). In general, it cannot be assumed that f(g(x)) = g(f(x)). If f(x) = 2x and g(x) = x 2, for example, then f(g(3)) = 18 but g(f(3)) = 36. The order in which the functions apply matters. Mathematics often supplying multiple ways of expressing an idea, this f(g(x)) can also be written using the compositional operator o meaning, “Applied after,” such that f(g(x)) = f o g (x).

A function defined purely in terms of the composition of other functions is itself a composed function. In Java a composed method might look like this:

public void recoverFromException() {
	View view = registry.get(View.class)
	view.endWaiting();
    }

If we wish to view a method entirely from the perspective of how it orders the invoking of other methods then, stripping away the clutter of variable and assignment, we can “model” this method with an “order equation”:

recoverFromException = endWaiting o get

Such a composition stems from the necessary relationship of the invocations involved, get() supplying the argument to endWaiting(). The explicitness of syntactic ordering demands that get() be invoked before endWaiting(), otherwise the program will not compile. But what of seemingly unrelated method invocations? Consider the following:

public void clearViewCache(View view) {
	view.clearPositionCache();
	view.clearImageCache();
    }

This method expresses a weaker syntactic ordering requirement than the previous because it is not a composed method but defined in terms of two method invocations neither of which supplies necessary argument to the other. A method whose invocation order lacks necessary explicitness is called a contingent method. Unlike the previous method, which admitted no re-ordering, this contingent method apparently could have been written as:

public void clearViewCache(View view) {
	view.clearImageCache();
	view.clearPositionCache();
    }

This, of course, may not be the case. Taking no arguments and supplying no return values, both method invocations wallow in side-effects, so the second invocation may harvest information altered by the first such that a re-ordering will cause an error. Whether the apparent lack of necessary order implies a stealth order to be respected or an invitation to shuffle at will is moot; the point remains that the method itself offers no syntactic evidence either way and in doing so suggests orderlessness where composition does not. This suggestion may be wrong but it exists nonetheless. Contingency raises questions that composition avoids entirely.

Programmers value intent. Kent Beck’s Extreme Programming Explained, for example, claims that the very essence of simple code is that it, “Reveals its intent.” Robert C. Martin goes further asserting that, even more than mere programming, “Architecture is about intent.” Increasing constraint generally correlates with increasing intent because with increasing constraint comes a reduced number of alternatives and thus fewer opportunities for ambiguity and misinterpretation. Given that composition constrains ordering more than than contingency, composed methods show more intent than contingent methods and so enjoy, on this narrow dimension alone, superiority.

Some notation may help. Just as the o operator signifies composition, let us say that the \ operator signifies contingency. Thus the second snippet can be written as:

clearViewCache = clearPositionCache \ clearImageCache

And this, by definition, is equal to:

clearViewCache = clearImageCache \ clearPositionCache

How might a programmer use this triviality to clarify intent? One way is to minimise the number of contingent methods and maximize the number of composed methods. Here, alas, the universe laughs at the programmer because of some unfortunate combinatorial rules; loosely:

Composition + composition = composition.
Contingency + contingency = contingency.
Composition + contingency = contingency.

That is, f o g o h constitutes a composed method but f o (g \ h) is a contingent method even though it contains a compositional operator. Once blighted by order ambiguity, no method escapes contingency. Nevertheless, it seems a shame to cloak even partial intent under a cloth of confusion. A method, let us therefore further say, formed exclusively around either the composition or contingency operator – for example, the invocation sequence k \ m \ p \ s or the sequence k o m o p o s – we shall call an, “Order-simple,” method, whereas one boasting both compositional and contingency operators we shall call, “Order-compound.” Maximising intent thus becomes smashing order-compound methods into order-simple shards.

Consider:

a = f \(g o h)

If we introduce a composed method, j, such that j = g o h then the above order-compound reduces to the two order-simple methods:

a = f \ j
j = g o h

As figure 1 shows, this reduction comes at the cost of both extra methods and depth, but whereas the original method’s contingency muddled its overall invocation order at least one of the new methods explicitly intends the order it articulates. Part of the program has been saved from contingency even if the overall contingency remains.

Figure 1: Order-compound contingency reduction, before (left) and after (right).
Figure 1: Order-compound contingency reduction, before (left) and after (right).

 
No guarantee exists, sadly, that an order-compound method may decompose into set of order-simple methods. The invocation of a multi-argument method inherently involves contingency as methods do not dictate the order of evaluation of functional arguments. (Indeed the \ operator is little more than the comma separating the arguments of a function.) Two questions then arise. Given a successful reduction, is the set of order-simple methods to which an order-compound method decomposes unique?

Properties

Some properties of contingency:

  1. f o (g \ h) = f(g, h)
  2. Commutativity:
    f \ g = g \ f
  3. Associativity:
    (f \ g) \ h = f \ (g \ h)
  4. Composition right-distributes over contingency:
    (f \ g) o h = (f o h) \ (g o h)

Others exist, to be investigated in a later post.

The composed order-simple

Let us examine some real production code. FitNesse supplies all the following snippets, the first being from class PageDriver.

private NodeList getMatchingTags(NodeFilter filter) throws Exception {
    String html = examiner.html();
    Parser parser = new Parser(new Lexer(new Page(html)));
    NodeList list = parser.parse(null);
    NodeList matches = list.extractAllNodesThatMatch(filter, true);
    return matches;
  }

Modeling this as its essential method invocations yields the equation:

getMatchingTags = extractAllNodesThatMatch o parse o new Parser o new Lexer o new Page o html

This presents a perfect, order-simple, composed method, with each method invocation depending on the previous. In expressing an order that brooks no tampering, the programmer helps clarify the method’s intent by unburdening the programmer’s mind of potential alternatives. Being order-simple, PageDriver offers no order-compoundness to reduce.

The contingent order-simple

public void close() throws IOException {
    super.close();
    removeStopTestLink();
    publishAndAddLog();
    maybeMakeErrorNavigatorVisible();
    finishWritingOutput();
  }

This method within class TestHtmlFormatter presents order-simple contingency whose equation is:

close = close /  removeStopTestLink / publishAndAddLog / maybeMakeErrorNavigatorVisible / finishWritingOutput

Again, being order-simple, TestHtmlFormatter stands irreducible but, unlike the previous example, this hardly speaks well of the method’s design. The programmer’s intent has left no trace on the syntax employed, dissolving entirely to hazy semantics. Still, at least the method is order-simple rather than order-compound: concentrating contingency into such pure order-implicitness at least singles out targets for the intent-revealing refactorings to which order-compound reductions point. To repeat, order-compound reductions do not reduce overall system contingency per se – they refactor the method under study but not those invoked by the method under study. Instead, reductions act as refineries, pumping the sludge of contingency into metal barrels for later detoxification.

The order-compound

The MultiUserAuthenticator constructor presents a minimalist example of order-compoundenss:

public MultiUserAuthenticator(String passwdFile) throws IOException {
    PasswordFile passwords = new PasswordFile(passwdFile);
    users = passwords.getPasswordMap();
    cipher = passwords.getCipher();
  }

Clearly an order-compound contingent method, this can be modeled by:

MultiUserAuthenticator = (getPasswordMap \ getCipher) o new PasswordFile

Performing an order-compound reduction involves refactoring a method to minimise the size of order-compound methods of which it is constructed. The most obvious reduction to perform on the above extracts a new method f = getPasswordMap \ getCipher, thus producing two equations:

MultiUserAuthenticator = f o new PasswordFile
f = getPasswordMap \ getCipher

This eliminates all order-compoundenss, yielding a composed method and an order-simple contingent method, hence completing the reduction. The resulting source code will look something like:

public MultiUserAuthenticator(String passwdFile) throws IOException {
    PasswordFile passwords = new PasswordFile(passwdFile);
    f(passwords);
  }

  private f(PasswordFile passwords) throws IOException {
    users = passwords.getPasswordMap();
    cipher = passwords.getCipher();
  }

(A better name for method f() possibly exists.)

Again, this reduction incurs the cost of increased depth. Other reductions present themselves, however. Given rule (4) above, the original model of the constructor could have been written as:

MultiUserAuthenticator = (getPasswordMap o new PasswordFile) \ (getCipher o new PasswordFile)

This reduces to three order-simple equations:

MultiUserAuthenticator = f \ g
f = getPasswordMap o new PasswordFile
g = getCipher o new PasswordFile

Such a formulation, however, suffers from many draw-backs, such as the calling of the PasswordFile constructor twice; if this were a computationally expensive piece of code then performance alone might render this second formulation untenable. The reduction nevertheless answers our question. Is the set of order-simple methods to which an order-compound method decomposes unique? No.

The normalization problem

The processTestFile() method of PageHistory illuminates some interesting difficulties:

void processTestFile(TestResultRecord record) throws ParseException {
    Date date = record.getDate();
    addTestResult(record, date);
    countResult(record);
    setMinMaxDate(date);
    setMaxAssertions(record);
    pageFiles.put(date, record.getFile());
  }

The previous example introduced duplication of method invocation as means to explore a different order arrangement. The order equation for processTestFile(), however, cannot be expressed without duplication. In the minimum case, its seems getDate() appears twice:

processTestFile = put o (getDate \ getFile) \ setMaxAssertions \ (setMinMaxDate o getDate) \ countResult \ (addTestResult o getDate)
= put o (getDate \ getFile) \ setMaxAssertions \ countResult \ ((setMinMaxDate \ addTestResult) o getDate)

Where a one-to-one correspondence exists between method invocation in source code and its appearance in an order equation, we say that the method under study is in normal form. This processTestFile() is not in normal form and so, while still reducible, the performance of its duplicated invocations may prove impractical.

For completeness’s sake, if we introduce a = put o (getDate \ getFile) and b = (setMinMaxDate \ addTestResult), then we get:

processTestFile = a \ setMaxAssertions \ countResult \ (b o getDate)

Finally, we introduce c = b o getDate we get:

processTestFile = a \ setMaxAssertions \ countResult \ c

This is now an order-simple contingent method, with the remaining order-compoundness sequestered into the a() method, though with getDate() called from both a() and c().

Summary

Programmers view absolutes with suspicion.

The weakest of the Tulegatan principles, the principle of contingency barely holds its head above the choppy waters of style guidelines. This perhaps does not surprise given the target of its attentions: not concrete ripple effect but amorphous intent. The principle states that contingency should be minimized, advocating not the alarmist eradication of the semantic ordering of method invocation but the bolstering of semantic ordering with syntactic constraint.

Curiously, despite its weakness, the principle of contingency leads to marked code structure. While the novice struggles to balance order-simplicity with increased code depth, the warrior versed in the blade of order-compound reduction produces refactorings of rare acuity.

Martin’s SOLID principles, developed for classes, often find application at method-level, with many programmers calling for the method, too, to adhere to the principle of single responsibility. “Single responsibility,” of course, means different things to different people, but some would argue that a composed method adheres to this principle more than an order-simple contingent method does, and both vastly out-adhere order-compound methods. As such, contingency provides an objective gradient along which this subjective principle might be evaluated.

The next part of this post will investigate fallen eliminations, naturally arising order-layering and compaction.

Reference: Structural contingency (part one) from our JCG partner Edmund Kirwan at the A blog about software. blog.

Edmund Kirwan

Edmund is a programmer with a telecoms company in Stockholm where he is currently working on a large-scale network simulator. In his spare time he thinks far too much about program-structure.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments
Back to top button