Semantic Invariants

—Andy Hunt

01/01/1998
Published in Toolshed Newsletters

Welcome to the Toolshed Technologies Newsletter! In this issue we’ll talk about my favorite phrase of the month: semantic invariants.

Abstraction

The dictionary tells us that an abstraction is “disassociated from any specific instance”, “expressing a quality apart from an object”.

The key to computer science is abstraction: the ability to sift through the rubble and noise of nearly infinite variations and generalize concepts and principles. This is the case whether you are a user, or writing code, doing requirements analysis, or design. When implementing, you are writing in a high level language that abstracts the physical machine. In requirements analysis and design, you are looking at abstracting the physical world and business practices that exist to seek a higher-level understanding.

Seeking commonality at the right levels is easier said than done of course, but how do you go beyond the buzzwords and really alter how you think about things? Here a couple of random thoughts that may help.

Constraints

Let’s suppose you want to model a very simple transaction, for example, purchasing a hamburger at a fast food establishment. Suppose you have an interface (or abstract class) for “Buying a Burger”. The constraints on such a transaction might be expressed as:

Pre-condition to “Buying A Burger”:

The customer has sufficient money in local currency to purchase a burger.
Customer may request options on the burger, any of: cheese, lettuce, or tomato.

Post-condition to “Buying A Burger”:

Customer will receive a burger with the requested option(s).

Invariant for Burgers:

All burgers are made of a beef and kangaroo mixture, and come on a 1.5” diameter roll.
All burgers are flame-broiled.
All burgers weigh 0.08oz before cooking.

You can’t get a fried burger here. If you request a burger with ketchup the supplier is under no obligation to give it to you. If you request a cheese-burger and have the money, you are guaranteed to receive it.

So here we have the pre and post conditions that define “Buying A Burger”. What defines a burger? Everything can be described in terms of certain properties, some properties can vary among instances, some can not. Books may have differing number of pages, but they all have covers and spines (ok, I have a 1979 Unix V7 manual that doesn’t have a cover, but bear with me…). Invariant properties (properties that can’t vary) define what must always be true about something. The formal expression of pre-conditions, post-conditions, and invariants are a powerful way to design software.

Semantic Invariants

There’s an interesting article in the February 1998 issue of Unix Review by Jim Waldo of Sun Microsystems. He describes an argument amongst object oriented practitioners: should a FilePath (a path and name to a given file) be a subclass of String?

I must admit that when I first read it, I thought “sure, sounds reasonable”. File names and paths are generally held as Strings, you could add a few special methods to get the basename() and dirname() components to parse the string, etc. But as Mr. Waldo goes on to point it, these two concepts are really not at all related. The gist of his argument is based on an analysis of the “semantic invariants” of the two proposed classes.

For a given String class, you as programmer make certain assumptions about its behavior. You assume that if you concatenated two strings together, that the result would be a string equal to sum of the lengths of both the original strings:

if: 
    String a = "foo"; // Length is 3 
    String b = "bar"; // Length is 3 
 
then: 
    length(a+b) == 6 // should be true. 

You also implicitly assume other mundane things, like if you converted a the string to lower case, that it would be different from the string in upper case:

if: 
    String a = "FOO"; 
    String b = a.toLowerCase() 
 
then: 
    a.equals(b) // should be false. 

There are hidden assumptions throughout our programming day, things we as programmers take for granted. Many a nasty surprise turns up when the hidden assumption is no longer valid. (For an excellent discussion of the consequences, see The Lessons of Ariane , a classic $500 million mistake.)

In the case of the String vs. filename argument, the two invariants informally expressed above for a String DO NOT HOLD for a filename! Suppose: (Windows users pretend you see 's instead of /’s).

If: 
    FilePath a = "/usr/toolshed/projects/foo/"; 
    FilePath b = "../.." 
 
Then: 
    a+b == "/usr/toolshed/projects"! NOT "/usr/toolshed/projects/foo/../.." 
    length(a+b) is not what you think it is!  

In the second case, on a MSDOS filesystem both “FOO” and “foo” refer to the same file, and the programmer may be in for a potentially nasty surprise!

Mr. Waldo’s article points out the importance of thinking about the meaning of a class – its semantics. Yes, a file name is something that can be represented as a string. But it IS not a string. It IS a named entity used by the operating system to locate a data file on some secondary store.

So the phrase of the month is Semantic Invariants: What is the meaning behind those immutable properties that define a class?

Summary

Determining the Semantic Invariants as part of Analysis and early Detailed Design can be a valuable tool in clarifying your thoughts on class responsibilities and the partitioning of functionality.

I hope this helps, or at least raises more questions:

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of idea.—John Ciardi

Keep up to date with my low-volume newsletter and don't miss another article or fresh idea:

Your subscription could not be saved. Please try again.

Your subscription has been successful.