Skip to content

A design methodology for reliable software systems

October 21, 2016

A design methodology for reliable software systems Liskov 1972

We’ve come to the end of Liskov’s list. The final paper is by Barbara Liskov herself, on the question of how best to go about designing software systems so that we can have some confidence they will work.

The unfortunate fact is that the standard approach to building systems, involving extensive debugging, has not proved successful in producing reliable software, and there is no reason to suppose it ever will.

So we’re going to need some testing, and for high levels of confidence we’ll need good coverage via:

  • a complete but minimal set of test cases, and
  • a system in which the set of relevant test cases is small, such that it is possible to generate every case

It is the system design which determines how many test cases there are and how easily they can be identified, the problems can be solved most effectively during the design process.”

And with that short introduction, the rest of the paper focuses on the questions of ‘What is a good system design?’ and ‘What process will help to ensure we produce one?’

A good system design is one where complexity is tamed by dividing it into modules (called ‘partitions’ in the paper, because the term module had already become very overloaded). As we’ve looked at previously, just dividing a system into modules isn’t enough though – it matters very much how you make those divisions. In fact,

…the division of a system into modules may introduce additional complexity… if modularity is viewed only as an aid to management, then any ad hoc modularization of the system is acceptable. However, the success of modularity depends directly on how well the modules are chosen.

A good modularity is based on levels of abstraction, and uses structural programming within modules.

Level of abstraction were first defined by Dijktsra. They provide a conceptual framework for achieving a clear and logical design for the system. The entire system is conceived as a hierarchy of levels, the lowest levels being those closest to the machine.

There are two important rules given for levels of abstraction:

  1. Each level has resources which it owns exclusively and which other levels are not permitted to access.
  2. Lower levels are not aware of the existence of higher levels and therefore may not refer to them in any way.

With good modularity, the system is broken into a hierarchy of partitions (modules), with each partition representing one level of abstraction and consisting of one or more functions which share common resources. The connections between partitions are limited as follows:

  • Control connections are limited by the rules about the hierarchy of levels of abstraction
  • Connections in data passed between partitions are limited to the explicit arguments passed from the functions of one partition to the (external) functions of another partition. Implicit interaction on common data may only occur among functions within a partition.
  • The combined activity of the functions in a partition support its abstraction and nothing more.

The definition of connections in the above follows Parnas: “The connections between modules are the assumptions which the modules make about each other.”

We know what good modularity looks like when we see it now. But how do you arrive at good modularity in the first place?

The traditional technique for modularization is to analyze the execution-time flow of the system and organize the system structure around each major sequential task. This technique leads to a structure which has very simple connections in control, but the connections in data tend to be complex.

(See Parnas again).

Select modules to support abstractions or concepts which you find helpful in thinking about the system….

Abstraction is a very valuable aid to ordering complexity. Abstractions are introduced in order to make what the system is doing clearer and more understandable; an abstraction is a conceptual simplification because it expresses what is being done without specifying how it is done.

What kinds of abstractions should we be on the lookout for?

  • Abstractions of resources – modules that map the characteristics of an abstract resource into the real underlying resource or resources
  • Abstractions that hide data storage representations
  • Abstractions that limit information:

According to the third requirement for good modularizatio, the functions comprising a partition support only one abstraction and nothing more. Sometimes it is difficult to see that this restriction is being violated, or to recognize that the possibility for identification of another abstraction exists. One technique for simplification is to limit the amount of information which the functions in the partition need to know (or even have access to).

One way to limit information is to introduce modules at a lower level, on which the higher-level module depends, which hide that knowledge.

  • Abstractions that generalize a function or group of functions. “Separating such groups is a common technique in system implementation and is also useful for error avoidance, minimization of work, and standardization.”
  • Abstractions that encapsulate areas likely to change

The design process proceeds iteratively as follows. First determine an initial set of abstractions which represent the eventual system behaviour in a very general way. Then establish the data and flow of control connections among the partitions.

The second phase occurs concurrently with the first; as abstractions are proposed, their utility and practicality are immediately investigated… A partition has been adequately investigated when its connections with the rest of the system are known and when the designers are confident that they understand exactly what its effect on the system will be. Varying depths of analysis will be necessary to achieve this confidence.

When do you start programming modules? There is a tendency to think of this as the era of the strict waterfall, but that’s not what Liskov proposes:

It is not clear exactly how early structured programming of the system should begin… The best rule is probably to keep trying to write structured programs; failure will indicate that the system abstractions are not yet sufficiently understood and perhaps this exercise will shed some light on where more effort is needed or where other abstractions are required.

Finally, a design can be considered ‘finished’ when the following criteria are met:

  • All major abstractions have been identified and partitions defined for them; the system resources have been distributed among the partitions and their positions in the hierararchy established.
  • The system exists as a structured program… this consists of several components, but no component is likely to be completely defined. Rather each component is likely to use the names of lower-level components which are not yet defined.
  • Sufficient information is available so that a skeleton of a user’s guide to the system could be written. (This was an era of much simpler user interfaces remember).

Programming with Abstract Data Types

October 20, 2016

Programming with Abstract Data Types Liskov & Zilles, ACM SIGPLAN Notices, 1974

This is paper 6/7 from Liskov’s list, and it’s by Barbara Liskov herself. What an enormous impact this paper has had on how we program today. Has there been any single advance in programming languages since this work (42 years ago) which has made such a big impact on mainstream programming? I can’t think of one.

It’s amazing how much is in here, bar inheritance you’ve got pretty much all of the core features of a modern object-oriented language, including strong type checking and support for generic types.

Structured programming attempts to impose a discipline on the programming task so that the resulting programs are ‘well-structured.’ In this discipline, a problem is solved by means of a process of successive decomposition…

You can start out with high-level procedures, and gradually fill-in the details at lower levels of abstraction to complete a program. (Program development by stepwise refinement, Hierarchical program structures). As Liskov notes, when working at a certain level you are concerned with the way a program makes use abstractions provided at lower levels, but not with the details of how they are realized. Higher-level programming languages could provide increasing numbers of abstractions through their built-in types, but could never hope to provide all of the useful abstractions for building programs.

A structured language… contains no preconceived notions about the particular set of useful abstractions, but instead must provide a mechanism whereby the language can be extended to contain the abstractions which the user requires. _A language containing such a mechanism can be viewed as a general-purpose indefinitely-high-level language.

What do we want from an abstraction? A mechanism which allows us to express all relevant details for use of the abstraction, but hides all irrelevant details – the way in which the abstraction is implemented.

An abstract data type defines a class of abstract objects which is completely characterized by the operations available on those objects. This means that an abstract data type can be defined by defining the characterising operations for that type….

When a programmer uses a built-in data type, they make use of a concept or abstraction realized at a lower level of detail – the programming language itself (and its compiler). Likewise, abstract data types are used at one level, and realized at another level – but the lower level is not part of the language itself…

… an abstract data type is realized by writing a special kind of program, called an operation cluster, or cluster for short, which defines the type in terms of the operations which can be performed on it.

I guess operation-cluster-oriented programming was always going to be a bit of a mouthful!

Once you have abstract data types, “most of the abstract operations in a program wil belong to the sets of operations characterising abstract types.” For the remaining operations not associated with an ADT, Liskov and Zilles use the term “functional abstraction.” By programming in terms of ADTs and the operations they expose it is possible to defer the implementation representation decision until a later point. And thus it is possible to program according to one of Dijkstra’s programming principles: build the program one decision at a time.

The new-fangled support for ADTs (and abstract objects) is explained by way of an example – writing a program to convert infix expressions to polish notation. Given modern familiarity with the concepts, I’m going to cut straight to a description of the impressive set of features the language had.

  • The same syntax is used to declare variables of abstract types as to declare variables of built-in types (a very powerful principle)
  • A variable declaration must simply declare the type of the variable, or it may also specify that a new object is to be created at the point of declaration. Object creation is indicated by parentheses following the type name, and any object construction arguments inside the parentheses (a constructor invocation as we would now call it):
    s: stack        // s is of type stack
    s: stack(token) // s is of type stack, 
                    // and initialized to a new stack object
  • The language is strongly typed, you can use an abstract object in only one of three ways: by calling the operations defined for it, by passing it as a parameter to a procedure, and by assigning it to a variable of the corresponding type.
  • You invoke operations on an abstract object using a type_name$operation(args) syntax. The first parameter to such an invocation is always the object to be operated on (the object.operation sugar did not exist at this time). For example: stack$push(s, t)

There are several reasons why the type name is included in the operation call. First, since an operation call may have several parameters of different abstract types, the absence of the type-name may lead to an ambiguity as to which object is actually being operated on. Second, the use of the compound name permits different data types to use the same names for operations without any clash of identifiers existing.

  • Objects may also be created outside of variable declarations simply by following the type name by parentheses: s = stack(t)
  • Operation clusters (classes) are defined in a module supporting independent compilation. A cluster definition contains three parts: the object representation (its internal state), the code used to create objects (constructor), and the operations themselves. Here’s the stack example:
    stack: cluster(element_type: type) 
      is push, pop, top, erasetop, empty:

      rep(type_param :type) = (
        tp : integer;
        e_type: type;
        stk: array[1..] of type_param;

        s : rep(element_type); := 0
        s.e_type := element_type;
       return s;

      push : operation(s : rep, v: s.e_type); := + 1
        s.stk[] := v
      pop : operation(s : rep) returns s.e_type;
  • Type parameters are supported (as seen in the above example)

The rep description defines a new type, denoted by the reserved word rep, which is accessible only within the cluster and describes how objects are viewed there… The optional (“{}”) rep-parameters make it possible to delay specifying some aspects of the type definition until an instance of rep is created.

  • Type checking is extended to incorporate type parameters
  • The language completely hides all implementation details of the abstraction from its user.
  • Program efficiency need not be sacrificed:

We believe it is helpful to associate two structures with a program: its logical structure and its physical structure. The primary business of a programmer is to build a program with a good logical structure — one which is understandable and leads to ease in modification and maintenance. However, a good logical structure does not necessary imply a good physical structure — one which is efficient to execute… We believe it is the business of the compiler to map good logical structure into good physical structure. The fact that the two structures may diverge is acceptable provided that the compiler is verified, and that all programming tools (for example, the debugging aids) are defined to hide the divergence.

And finally, through experimentation with the language, Liskov and Zilles discovered something important about the ability to create new abstractions directly in the programming language:

Of course, program quality is most dependent on good program design. Although a language can never teach a programmer what constitutes a well-designed program, it can guide him or her into thinking about the right things. We believe that abstraction is the key to good design, and we have discovered in our experiments in using the language that it encourages the programmer to consciously search for abstractions, especially data abstractions, and to think vey hard about their use and definition.

Protection in programming languages

October 19, 2016

Protection in programming languages Morris Jr., CACM 1973

This is paper 5/7 on Liskov’s list.

Experienced programmers will attest that hostility is not a necessary precondition for catastrophic interference between programs.

So what can we do to ensure that program modules are appropriately protected and isolated? We still need to allow modules to cooperate and communicate, but ideally we’d like to be able to prove that a given module has various properties without considering the rest of the system. Morris explores a set of mechanisms that provide different kinds of guarantees:

  • Procedures as objects (or as we would say today, “functions as first class citizens”).
  • Local objects (scoping)
  • Memory protection
  • Type-based protections
  • Seals and Trademarks
  • Access keys

Procedures as objects

A procedure already hides details of its implementation from a caller, so why is it necessary that we can also pass procedures as arguments?

…in order to exploit this device to its fullest extent it is useful to make procedures full-fledged objects in the sense that they can be passed as parameters or values of other procedures and assigned to variables. Then, to make a particular object accessible to someone in a restricted way (e.g. read only) we make the object local to a procedure and pass the procedure to them in its stead.

I buy the argument when the procedure offers a limited view on an encapsulated object, but in general if the procedure is just wrapping an object it must give out either a value-object or a reference-object. If it gives a reference object, then we have no more protection than if we passed this directly. If it gives a value-object, then the procedure seems to offer no value over just passing a value-object directly. See ‘Why functional programming matters‘ for some more powerful (imho!) arguments on the value of functions as first-class citizens.

Local objects

It’s desirable to know that an object is local to a particular part of a program – that is, it cannot be accessed by other parts. “Object” here is used to mean for example the address of a variable, not an object as in the OOP sense. To validate such locality we need to check:

  • that it is not passed as a parameter to a procedure not defined within the module
  • that it is not returned as a result of a procedure called from outside the module
  • that it is not assigned to a reference which is not local to the module

Pony and its deny capabilities is a modern theme along these lines.

Memory protection

We’d like to encapsulate a memory reference (e.g. use of a variable) within a module such that only statements inside the module can assign to it or take its contents. Which is very similar to the ‘local objects’ requirement, but I guess implied is the added protection that the memory itself is inaccessible from outside of the module as well.

Given such protection, we can reason about the state of the module using pre-conditions and post-conditions on all of the operations exposed by it.


Now things start to get a bit more interesting…

One of the fundamental ways in which one programmer provides services to another is to implement a representation of a new kind of object…Generally speaking the first programmer writes some subroutines which create, alter, and otherwise deal with the new kinds of objects. These objects are represented by some older kinds.

In 1973 the representations were typically just primitive types with some conventions, for example an “interval” may simply be represented as a pair of integers. Of course this still happens today, especially when programming in a functional style. We hope the recipient of such representations treats them as the module designer intended, but at the same time we open ourselves up to three kinds of ‘mishap’:

  1. Alteration – the state could be changed without the use of the primitive functions provided for the purpose
  2. Discovery – the properties of the data might be explored without using the primitive functions
  3. Impersonation data created outside of the module might be presented to a primitive function expecting it to have certain properties

There are two parties involved in such mishaps: the programmer of the primitive procedures and the user (misuser, actually) of them.

Through the lens of this paper, discovery presents no direct threat, but alteration and impersonation can both expose bugs by invalidating assumed pre-conditions.

Morris’ solution is to allow data to be tagged with a type-tag, “familiar to any implementor of a language with dynamic data types… but being made available to the general user.” Passing data not tagged with the appropriate type-tag should result in a program violation.

These tags have a couple of interesting properties vs static typing:

First, they are ‘cascadable’ : a tagged item may be retained. This feature reflects our belief that representation can be a multilevel affair. Second, they are completely dynamic in the sense that a running program could generate an arbitrarily large number of different type tags. The practical virtues of this generality are not entirely clear (!).

Nowadays we’d probably use domain types.

Seals and Trademarks

A seal provides a way of wrapping an object such that it cannot be seen or tampered with until it is unsealed. A sealed object may safely be passed as a parameter, but its contents cannot be inspected by anyone not in possession of the unseal key. (Morris just uses an integer, ‘which changes every time create_seal is called.’) The seal mechanism provides for authentication (you know its an object you created, if you can unseal it), and access control. Local objects that are sealed remain local even if the seal escapes the module.

Instead of an integer, today I immediately think of digests (it hasn’t been changed), signatures (I created it), and encryption keys (or key-pairs) (it can’t be seen). Though these are more heavyweight constructs than Morris intends I believe.

Trademarks are a more general form of seals that wrap objects in something that testifies to their authenticity (again, implemented using ever-changing serial-numbers in Morris’ world). This is an early nod to the value of signatures:

If the reader doubts the utility of this device, stripped of any access limiting power, we urge him or her to consider how trademarks and other authenticating marks are used in the commercial/bureaucratic sphere. A mark from the Underwriters’ Laboratories attests that a particular device may be used without risk, a fact that a user might discover only by extensive experience. A letter saying “You have been drafted,” is much more likely to be believed if it bears the mark of a draft board….

Morris’ seals and trademarks are lighter-weight constructs than the cryptographic operations I’ve associated them with though. In usage, he seems to envision them as something very similar to type-tags:

We can invent trademarks to attest to these various properties and attach them to objects in any order we like. For example, a complex number represented in the cartesian system might bear four marks: pair, point-in-plane, cartesian, complex. Programs may examine these marks or not as they please: e.g. A routine that prints pairs is unconcerned with all but the pair tag.

Access keys

Now let us example the implications of making the seal operation public and leaving unseal private…. if one puts such a seal on an object and leaves it in a public place, he/she is guaranteed that only the restricted group of programs holding unseal can access it…

Sounds very much like a public/private key pair!

Hierarchical program structures

October 18, 2016

Hierarchical Program Structures Dahl and Hoare, 1972

We continue to work our way through Liskov’s list. ‘Hierarchical program structures’ is actually a book chapter, and is notable for defining a ‘prefix’ mechanism that looks awfully like a form of class inheritance, paving the way for hierarchical program structures (i.e. Class hierarchies). The main takeaway for me is the idea that architectural layers should correspond to conceptual layers, with every entity in a given layer being at the same level of conceptual abstraction.

A programming language provides us with basic concepts and composition rules for constructing and analysing computing processes… data and operations on data seem to be so closely connected in our minds, that it takes elements of both kinds to make up any concept useful for understanding computing processes.

On top of the concepts provided by a programming language, we build higher level concepts. The necessity for this is simply the limits of our own intellect – precise thinking is possible only in terms of a small number of elements at a time. As a consequence,

… The only efficient way to deal with complicated systems is in a hierarchical fashion. The dynamic system is constructed and understood in terms of high level concepts, which are in turn constructed and understood in terms of low-level concepts, and so forth. This must be reflected in the structure of the program which defines the dynamic system; in some way or other the higher level concepts will correspond to program components.

Coming up with a suitable set of concepts is a creative process, often requiring insights that arise during the later stages of construction. Thus software projects tend to be complicated iterative processes involving construction and revision at each stage. A good decomposition of the system enables each component to be programmed independently, and revised with little or no implications for the rest of the system.

Examples of higher-level concepts are given:

  • Procedures can be used to model some concepts, but their reliance on the stack for data storage means that algorithms are the only concepts that can be effectively modelled by them.
  • Classes combine variables and procedures and allow modelling of a wider array of concepts (e.g. A frequency histogram).
  • Coroutines enable two conceptual pieces of a program to operate at the same level (vs. one calling the other). Consider a two-pass compiler: the first pass outputs a long sequence of messages to be consumed as input by the second pass. But it is possible to arrange for the whole translation to be carried out in a single pass with the sequence of messages transmitted piecewise from the first pass to the next.

This suggests that a single coroutine may profitably be regarded as a complete self-contained program whose input and output instructions have been replaced by calls upon those coroutines to produce and consume the data.

It’s interesting to see coroutines right alongside classes as a basic concept modelling tool. They’ve certainly not had such equal billing for most of the intervening 44 years, though perhaps Go is getting closer with its goroutines.

The next concept to be introduced is that of self-referential classes that can be used to build recursive data structures such as binary trees and linked lists. “This is accomplished by declaring attributes of a class to be references to objects of the very same class.”

And finally we arrive at a concept introduced under the heading “program concatenation:”

In the preceding sections we have seen how the class mechanism is capable of modelling certain simple concepts, by specifying data structures and defining operations over them. In this section we develop a method by which more elaborate concepts can be constructed on the basis of simpler ones. This will establish potential hierarchies of concepts, with complex concepts subordinate to the more simple ones in terms of which they are defined…

How do we do that? In 1972, we do it by concatenation. Take two classes A and B, and merge the attributes of both classes and the composition of their actions. Writing ‘X class Y …’ means to take all of the declarations in X and ‘shove them at the front’ of the declaration of Y. In other words, it’s a primitive form of inheritance.

The concept hierarchies formed by this mechanism help to bridge the gap between the problem domain and the general purpose programming language.

Our difficulty in bridging such gaps is the fact that we have to work sequentially on one simple part problem at a time, not always knowing in advance whether they are the right problems. In order to better overcome such difficulties we may build pyramids. Unlike the Egyptian ones ours are either standing on their heads (bottom-up construction) or hanging in the air (top-down construction). The construction principle involved is best called abstraction.

At each layer of the pyramid we concentrate on features common to many phenomena, and we abstract away features too for removed from the conceptual level at which we are working. Thereby, we have a better chance of formulating concepts which are indeed useful at a later stage.

Whether we work top-down or bottom-up (or even a little bit of both and hope to meet-in-the-middle) system construction consists of adding new layers of pyramids until the conceptual gap has finally been bridged. Each such layer will correspond to a conceptual level of understanding.

At the higher conceptual layers, we have what we would now call a domain language:

A well-formed conceptual level (bottom-up) is a set of well-defined inter-related concepts, which may be combined to make more elaborate concepts. It may serve for further construction in a mental platform, raised above ground towards some application area, i.e. as an “application language.” A reconstructed application language may serve to shorten the conceptual gap that has to be bridged for many problems in the area.

Information distribution aspects of design methodology

October 17, 2016

Information distribution aspects of design methodology Parnas, 1971

We’re continuing with Liskov’s listthis week, and today’s paper is another classic from David Parnas in which you can see some of the same thinking as in ‘On the criteria….’ Parnas talks about the modules of a system (for contemporary feel, we could call them ‘microservices’ once more), how we end up with inadvertent tangling / coupling between microservices, and what we can do to prevent that. One of his key recommendations is that information about a microservice be carefully controlled – releasing information about how it works internally outside of the team that are working on it is not just unhelpful, it is positively harmful. Writing in 1971, this information communication was primarily through documentation, and so this is what Parnas discusses. I wonder if in 2016 he would make the claim “making the source code for a microservice available outside of the team working on it is harmful” ??? That would certainly be a statement likely to cause robust debate!

Update: David Parnas himself posted a comment answering my question. Wow! Here’s his reply:

You wrote, “I wonder if in 2016 he would make the claim “making the source code for a microservice available outside of the team working on it is harmful” ??? That would certainly be a statement likely to cause robust debate!” The answer is YES. Papers that I wrote subsequently talk about the need to design and then document interfaces and then give other developers the interface documentation instead of the code. In fact, you can find that in the 1973 papers. The difference is that I have much better techniques for documentation today than I did forty years ago.

David Lorge Parnas


A system has structure: the set of modules (microservices) in the system, and the connections between them.

Many assume that the “connections” are control transfer points, passed parameters, and shared data… Such a definition of “connection” is a highly dangerous oversimplification which results in misleading structure descriptions. The connections between microservices are the assumptions which the microservices make about each other.

Consider a change that needs to be made. “What changes can be made to one microservice without involving change to other services?”

We may make only those changes which do not violate the assumptions made by other microservices about the service being changed.

Making design decisions

During the design and development of a system we make decisions which eliminate some possibilities for system structure. This evolves over time. Three common considerations during the decision process are:

  1. Making sure the system delivers a great experience for its users
  2. Ensuring the system can be delivered as quickly as possible
  3. Making sure the system can easily support future changes

Each of these considerations suggests an optimal partial order for decision making, but those orderings are usually inconsistent!

  • Delivering a great experience suggests using an outside-in approach whereby the external characteristics are decided first (rather than letting them be unnoticed implications of decisions about other aspects of system structure).
  • Delivering the system as quickly as possible requires dividing it early into separate microservices:

Competitive pressures may require the use of large groups to produce a system in a sharply limited period of time. Additional developers speed up a project significantly only after the project has been divided into sub-projects in such a way that separate groups can work with little interaction (i.e. spending significantly less time in inter-group decisions than in intra-group decisions).

The desire to make the division early in the project lifecycle so that the team can ‘get on with it’ encourages a splitting along familiar lines and in agreement with the organisational structure (Conway).

Time pressures encourage groups to make the split before the externals are defined. Consequently, we find some adverse effect on the usability of the product. Haste also makes poor internal structure more likely.

  • When it comes to changeability, Parnas makes an interesting observation: the earlier a decision was made, the more difficult it is likely to be to change it because other parts of the system grow assumptions about it.

These considerations suggest that the early decisions should be those which are the least likely to change; i.e. those based on “universal” truths or reasoning which takes into account little about a particular environment… the possibility of change suggests using the most general information first.

Since the thing that often changes the most is the external characteristics, starting there may make the system harder to change.

Good programmers fight against the system

The crux of Parnas’ argument hinges on this assertion:

A good programmer makes use of the available information given him or her.

Sometimes those uses are obvious: calling a subroutine in another module, or reusing a reference table. Sometimes they are less obvious, for example exploiting knowledge that a list is searched or sorted in a certain order.

Such uses of information have been so costly that we observe a strange reaction. The industry has started to encourage bad programming…. Derogatory names such as “kludger,” “hacker,” and “bit twiddler” are used for the sort of fellow who writes terribly clever programs which cause trouble later on. They are subtly but effectively discouraged by being assigned to work on small independent projects such as application routines (the Siberia of the software world) or hardware diagnostic routines (the coal mines). In both situations the programmer has little opportunity to make use of information about other modules.

(I wonder what the modern Siberia and coal mines would be?)…

Those that remain (the non-bit-twiddlers) are usually poor programmers. While a few refrain from using information because they know it will cause trouble, most refrain because they are not clever enough to notice that the information can be used. Such people also miss opportunities to use facts which should be used. Poor programs result.

A programmer can disastrously increase the connectivity of the system structure by using information he or she possesses about other services.

We must deliberately control information distribution

If you buy Parnas’ argument that if you make information available, good programmers can’t help but make use of it, whether that is in the overall good of the system or not, then an obvious solution presents itself: don’t make information available!

We can avoid many of the problems discussed here by rejecting the notion that design information (or source code?) should be accessible to everyone. Instead we should allow the designers, those who specify the structure, to control the distribution of design information as it is developed.

Say your system depends on an external service, it’s likely that all you know about that service is the documentation for its REST API, or the client SDK built on top. But when you depend on an internal service, you typically know much more…

We should not expect a programmer to decide not to use a piece of information, rather he should not possess information that he should not use.

The last word

I consider the internal restriction of information within development groups to be of far more importance than its restriction from users or competitors. Much of the information in a system document would only harm a competitor if they had it. (They might use it!).

And the modern ‘system document’ is generally the source code, written in a suitably high-level language.

Program development by stepwise refinement

October 14, 2016

Program development by stepwise refinement Wirth, CACM 1971

This is the second of Barbara Liskov’s 7 ‘must-read’ CS papers. Wirth’s main point is that we have a tendency to focus far too much on mastering the syntax and style associated with a particular programming language, and nowhere near enough time on the process by which new programs are designed in the first place.

… active programming consists of the design of new programs, rather than contemplation of old programs… Clearly, programming courses should teach methods of design and construction, and the selected examples should be such that a gradual development can be nicely illustrated.

By far the bulk of the paper though, is dedicated to one worked example of this principle, introducing the idea of stepwise refinement.  The goal is to write a program to solve the eight-queens problem.

Picture credit: Wikipedia

Wirth starts out with a very high level sketch of a solution, and gradually fills in the details to make both a more concrete and a more efficient implementation over time.

In each step, one or several instruction of the given program are decomposed into more detailed instructions. This successive decomposition or refinement of specifications terminates when all instructions are expressed in terms of an underlying computer or programming language, and must therefore be guided by the facilities available on that computer or language.

It’s not just about refinement of the tasks involved in the program; crucially the data and data representations may also need to be refined. “It is natural to refine program and data specifications in parallel.” It’s interesting to think about the task-based decomposition that naturally arises from this method, and contrast it with Parnas’ advice in “On the criteria to be used in decomposing systems into modules“. The stepwise refinement example in this paper though is ‘in the small,’ and really about the stepwise refinement of an algorithm as much as anything.

Reading through the worked example, I’m glad we have higher-level programming languages to work with these days! (The paper uses Algol 60). There are a few too many global variables and pointers for modern tastes.  The thinking process is still valuable though.

A guideline in the process of stepwise refinement should be the principle to decompose decisions as much as possible, to untangle aspects which are only seemingly interdependent, and to defer those decisions which concern details of representation as long as possible.

Here are the steps in Wirth’s refinement:

Up-front thinking…

  1. Start out with a very simple brute force algorithm that tries all possible placements until it finds one that works.
  2. Realise that this would be highly inefficient (about 7 hours on the technology of the day), and thus we need to find a shortcut…
  3. Reduce the number of candidate solutions that must be generated and tried, using a little domain knowledge: in this case, that there must be one queen in every column. This process would find an answer in about 100 seconds on the technology of the day.
  4. Realise that we can do better by being systematic about the way we generate trial solutions via stepwise construction of trial solutions.  That is, we start out by placing a queen in the first column, and then adding a queen in successive columns at each next step. If at any point in this process one or more queens conflict with each other we know there is no point going any further, so instead we can backtrack and try again from there.  This version generates 876 partial solutions before finding a complete one, and takes about 0.09 seconds on the technology of the day.

Development of the program…

Only at this point does Wirth think about moving into code. The first version is expressed in terms of a number of high-level procedures, whose details have yet to be filled in:

The next step is to begin to fill-in the details of those procedures, at which point we can no longer defer any decision about data representation.

A common difficulty in program design lies in the unfortunate fact that at the stage where decisions about data representations have to be made, it often is still difficult to foresee the details of the necessary instructions operating on the data, and often quite impossible to estimate the advantages of one possible representation over another. In general, it is therefore advisable to delay decisions about data representation as long as possible…

(Or as Parnas would advise us, to hide information about data representation from the rest of the program).

With a little thought, Wirth rejects the straightforward 8×8 boolean matrix in favour of an array of columns.  Analysing the efficiency of the resulting structure, Wirth then introduces auxiliary variables that make it more computationally efficient to determine whether or not a given square is safe to place a queen on.

Upon every introduction of auxiliary data, care has to be taken of their correct initialization…

The final version of the program still displays the structure of the version designed in the first step… “other, equally valid solutions can be suggested and be developed by the same process of stepwise refinement.

Wirth concludes with five remarks about the process:

  1. Program construction consists of a sequence of refinement steps
  2. The degree of modularity obtained during the refinement will determine the ease or difficulty with which a program can be adapted to changes or extensions
  3. During stepwise refinement, a notation natural to the problem in hand should be used as long as possible… “the direction in which the notation develops during the process of refinement is determined by the language in which the program must ultimately be specified.”
  4. Each refinement implies a number of design decisions based on a set of design criteria.
  5. Even the small example program in the paper requires quite a lengthy explanation, indicating that careful programming is not a trivial subject!

Among these criteria [for the design decisions] are efficiency, storage economy, clarity, and regularity of structure. Students must be taught to be conscious of the involved decisions and to critically examine and to reject solutions, sometimes even if they are correct as far as the result is concerned; they must learn to weigh the various aspects of design alternatives in the light of these criteria. In particular, they must be taught to revoke earlier decisions and to back up, if necessary, even to the top.

Go to statement considered harmful

October 13, 2016

Go to statement considered harmful Dijkstra, CACM 1968

It sounds like the Heidelberg Laureate Forum this summer was a great event. Johanna Pirker was there and took notes on Barbara Liskov’s talk, including 7 papers that Liskov highlighted as ‘must reads’ for computer scientists.  I’m sure you’ve figured out where this is going… for the next seven days we’ll be covering those papers, starting with the classic ‘Go to statement considered harmful.’

I don’t think we really need to have a serious debate about the merits of goto anymore, but that doesn’t make Dijkstra’s short note any less relevant today. Dijkstra’s argument hinges on the realisation that when the gap between the program as laid out in text and the runtime behaviour of the program becomes too large, we’re heading for trouble. It could perhaps be summarized as “It should be obvious what the program does from looking at it.”

My first remark is that, although the programmer’s activity ends when he has constructed a correct program, the process taking place under control of his program is the true subject  matter of his activity, for it is this process that has to accomplish the desired effect; it is this  process that in its dynamic behavior has to satisfy the desired specifications. Yet, once the  program has been made, the “making’ of the corresponding process is delegated to the machine.

We’re better at understanding static relationships (such as the order of statements in a printout) says Dijkstra, than we are at understanding processes that evolve over time:

For that reason we should do (as wise programmers aware of our limitations) our utmost to shorten the conceptual gap between the static program and the dynamic process, to make the correspondence between the program (spread out in text space) and the process (spread out in time) as trivial as possible.

If you just had a sequence of assignment statements one after the other, then the relationship would be very straightforward indeed – we could say where we ‘are’ in the program at any point during runtime by pointing at the corresponding point in the printout.

When we add procedures and loops things get more complicated. It’s no longer enough to point just at a place in the text, we also need the equivalent of a stack trace to show the nesting of procedures, and a ‘dynamic index’ showing how many iterations have been performed of each loop.

The main point is that the values of these indices are outside programmer’s control; they are  generated (either by the write-up of his program or by the dynamic evolution of the process)  whether he wishes or not. They provide independent coordinates in which to describe the  progress of the process. Why do we need such independent coordinates? The reason is – and this seems to be inherent  to sequential processes – that we can interpret the value of a variable only with respect to the  progress of the process.

The reason go to is harmful therefore, is that it makes it terribly hard to find a meaningful set of coordinates with which to describe the progress of a process.

The go to statement as it stands is just too primitive; it is too much an invitation to make a mess of one’s program.

A salient reminder that sometimes we can be too clever for our own good. If we can’t easily understand what a program does by looking at it, we could be heading for trouble…