small medium large xlarge

Semantic Invariants

Abstraction is the key

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”: 1) The customer has sufficient money in local currency to purchase a burger. 2) Customer may request options on the burger, any of: cheese, lettuce, or tomato. Post-condition to “Buying A Burger”: 1) Customer will receive a burger with the requested option(s). Invariant for Burgers: 1) All burgers are made of a beef and kangaroo mixture, and come on a 1.5" diameter roll. 2) All burgers are flame-broiled. 3) 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 postconditions 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.

Thinking about 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