BLOG@CACM
Computing Applications

Mental Self-Check

Posted
Bertrand Meyer

Some people in insane asylums think those outside are the ones who are crazy; the rest of the world disagrees.

If you are just inside or just outside, it is difficult to adjudicate the question.

Programming with Eiffel and Design by Contract is the privilege of a minority, who think that the rest of the world is crazy. I, for example, have no idea how it is even possible to program otherwise and keep one’s sanity; but maybe I am the insane one. This article might serve as a mental self-check.

In short: using a powerful static type system and Design by Contract radically changes the nature of software development, which becomes a much more predictable and enjoyable endeavor, worthy of being called “software engineering”.

Let me take an example from a program I am writing now. I have several data structures, fairly complex. They serve to represent a multigraph, which is like a directed graph but with labeled edges and the possibility of having any number of edges (not just zero or one), with different labels, between two given nodes. The figure below shows a multigraph; the nodes represent people and houses, and the edges represent relations between them, for example that a person is another person’s boss or a house is a person’s residence.

 

A multigraph

 

Assume that we have a way to represent each node by a unique integer; a simplified view of the above example looks like this, showing the node numbers (26 and 57, arbitrary examples) and the tag (abbreviated from spouse to s) for only one edge:

 

A multigraph (partial view)

A data structure that represents this concept is a “triple table”: an array of triples, each containing a node identifier x, a tag t, and another node y. A typical triple table could be this one:

 

See how the highlighted triple in triple_table represents the highlighted edge in the graphical illustration of the multigraph. The triple_table is declared as follows:

triple_table: HASH_SET [TRIPLE]

where HASH_SET (a variant of HASH_TABLE) is a library class and TRIPLE a class (not from the library, but written for this application) describing objects with three components: source, tag and target. A HASH_SET is an implementation of sets where each element, here each triple, serves as its own key.

These type declarations already help us a lot towards getting things right. For example, to find out if there is a triple with specific values in the table, you will use the test

             triple_table.has (create {TRIPLE}.make (a_source, a_tag, a_target)

Everything here needs to have a specific type. The first compilation attempt will kill many errors in the bud simply as type errors.

Why anyone would use a dynamically typed language (for anything beyond a 10-line script) and deprive himself or herself of this marvelous bug-killing mechanism passes my understanding. But I have to remember I am inside the asylum.

It turns out that my program needs to access the structure in many different ways. A common technique in the design of efficient algorithms is to trade some space for time by providing several, possibly redundant, representations of the same information. Here it is convenient to have another data structure, triples_from, such that triples_from [i] is the list of entries in triple_table representing edges starting with i. Here is triples_from [26] for the example: