Fundamentals of Software Design

As an introduction to my next post I wrote the text below to explain some basic principles of breaking down a program into more easily handled chunks.  Discussion in software design literature, under such names as separation of concerns, information hiding, modularity, encapsulation, etc, is massive.  However, I have never seen a concise summary so I wrote this.  Unfortunately, my summary was not as brief as I hoped so I split it into this separate post.

This post is an introduction to the my next post on the Layer Anti-Pattern.  I believe it is useful in its own right.

Introduction

Going back to my very first blog post you may recall that I discussed the fundamental problem facing software development (complexity) and the most important approach to tackling it (the principle of divide and conquer) - see Software Design Complexity.  Of course, that is just the start of the story.  The real challenge is to find the best way to divide a problem in order to conquer it.  In general, approaches to this are the subject of just about every book you have read or will read about designing software - ie, the best way to split a problem into smaller and smaller sub-problems which are more easily tackled.  Here I distill the essence of commonly described techniques as well as adding a few approaches of my own.

Modules and Interfaces

First I will clarify my nomenclature.  There are many names given to software components designed to handle specific problems and sub-problems.  I am going to use the word module.

Of course, a large module will use sub-modules to handle it own particular sub-problems.  At the highest level a module may be a program or tool (or even a suite of programs) which is part of a larger system.  At the lowest level a module is a function or procedure.  In C, it is common to have clearly defined modules at the source file level.  In OO languages like C++, Java, and C# the most common type of module is a class, which may or may not correspond to a single source file.

Another important idea is what I will call the interface.  This is simply what a module exposes to the outside world.  By definition, all communications between modules take place through interfaces.  In C and C++ the interfaces to most modules are typically specified in individual header files (typically in a .H file with the same name as the corresponding .C file).

Techniques

SRP

One of the simplest, and most obvious, ideas is that a module should do just one thing.  This idea is ubiquitous in the history of software design.  For example, one of the basic design principles of UNIX is that a tool (or any module) should do just one thing (and do it well).  This is what is commonly discussed when people talk about separation of concerns.  More recently the name SRP (single responsibility principle) has become popular.

Although the idea is simple it is not always easy to recognize when a module is doing more than one thing.  For example, many potentially simple routines are often overwhelmed by ancillary concerns, such as data initialization, data retrieval, data conversion, global state management, error handling, logging, etc.  When queried on why the code is structured that way the designer/developer is unaware of how to separate the concerns or even oblivious to the advantages of doing so.

Further, it is often not possible to separate concerns without access to (or understanding of) the necessary technique or technology.  There have many technologies that have been created for this very reason, such as:

• function pointers: being able to pass around a pointer to code makes many patterns of modularity possible (see my previous posts on IOC and DI)
• object-oriented: sometimes a function pointer is not enough; OO technologies also allow data and code (methods) to be handled as one
• exception handling: allows error handling code to be separated from normal flow of control
• multi-tasking: allows separate processes to run simultaneously with controlled interactions
• aspect-oriented: allows "cross-cutting" concerns to be isolated from the rest of the code
• generics: allows concerns to be separated from the rest of the software in a way that does not reduce performance or sacrifice type-safety

Another good example is from my previous post on Dependency Injection.  It is not obvious that comparison can be separated from sorting which might result in the design of Diagram 2.  Once you realize that the sorting algorithm does not need to know the details of how two elements are compared (only that the elements can be given an ordering) a better separation of concerns can be achieved as in Diagram 3.

DRY

Another basic idea is to eliminate duplicate code, and is often known by the acronym DRY (Don't Repeat Yourself).  It is closely related to SRP since if module boundaries are well chosen then the likelihood of duplicate code is reduced.  Duplicate code is not only a maintenance problem it's also indicative of a poor design in general.

Similarly to SRP there are two problems with DRY: recognizing that two or more pieces of code have commonality; and isolating that commonality.

It can be hard, just inspecting two different pieces of code, to detect any commonality.  For example, the code to sort an array of strings may bear no resemblance to code for sorting a linked list of structures.  The original designer should be aware that both pieces of code are performing a sorting operation and attempt to isolate it into a separate module (or re-use an existing sort module).

Of course, sorting is a fairly obvious operation, but a designer may have much more difficulty finding and separating other pieces of commonality.  Generally, this takes practice and a little lateral thinking but mainly depends on the ability of the designer.

A common pattern when duplicate code is found is to isolate it into a separate module.

Duplicate Code Moved to a New module.

Information Hiding

An important part of the design of modules is the idea that implementation details should be hidden from the outside.  This means designing an interface that does not expose internal details that may need to change.  It also means hiding private methods and data from outside use.

What is Information Hiding?

Some authors consider information hiding to be the principle behind good module design.  I use the term simply to mean hiding details of a module's implementation from the outside world.

A common problem is that an interface will expose details of the module's implementation.  In C++ this is often due to using public data members.  For example, consider a 2-D rectangle class that exposes four numbers: bottom, left, top and right; which are effectively the the coordinates of two corners of the rectangle.  If, for some reason, the implementation needs to be changed to use the bottom, left corner plus height and width it is not possible without changing the interface.  Further, a rectangle like this can only have sides parallel to the axes - what if you wanted to add the ability to rotate?

Another problem is when internal parts of the module are accidentally left visible.  For example, in C it is not unusual for functions internal to a module to be globally visible.  This can cause maintenance problems, such as name conflicts or accidental use of similarly named functions.  Anything that is not hidden effectively becomes part of the interface, since it could potentially be used from another module.  Module-private functions in C should always be declared static to avoid their name being globally visible, in the same way as functions internal to a class in C++ should be declared private.

It should be obvious that using a simple, well-defined interface (that only exposes information on what the module does not how it does it) has many advantages.  It enhances maintainability and portability.  Possibly more importantly, it improves understandability of what the module does, which in turn helps you to understand interactions between modules and verify that the overall design is consistent.

Decoupling

Another piece of software design jargon is coupling which is simply how much modules depend on each other.  The aim is to remove dependencies as much as possible.  This partly depends on information hiding but also relates to how modules themselves are inter-connected.  Decoupling has large benefits for the maintainability of software.  Loosely coupled modules allows changes or improvements in one module to be made easily without affecting (or introducing the possibility of inadvertently affecting) other parts of the code.

If two modules are tightly coupled then there is a lot of interaction between them, which if taken to extremes means they effectively become one module.  When most or all modules are tightly coupled you end up with the Ball of Mud anti-pattern.

For effective decoupling, module interfaces should be as simple as possible, visible and well-defined (see information hiding above).  One indicator of poor decoupling is when a minor change to a system requires changes in multiple places.

However, decoupling goes further than just having good interfaces.  Suppose, we have six well-designed modules that each perform a single function with simple, well-understood interfaces.  If each module depends on every other module then there is a high degree of coupling between the modules.

Tightly Coupled Modules.

A good design will try to organize the modules into a hierarchy so that each module is only dependent on a few other modules and there are no circular dependencies.  A hierarchy make the interactions easier to comprehend.  A graph of the dependencies will be a tree or DAG (directed acyclic graph).  Here is an example:

Loosely Coupled Modules

Encapsulate what Varies

A major purpose of dividing software into modules is to enhance its maintainability.  The are other advantages such as understandability, re-usability, verifiability, etc, but in my opinion maintainability is the most important quality attribute of most software - yes even more important than correctness.  (See my blog Developer Quality Attributes.)

Software Designer's Jargon

Encapsulation, modularity, information hiding, reducing coupling, increasing cohesion, etc are all terms that are used in software design literature to describe the same idea of decomposing a design into modules and reducing the coupling between those modules.  Different people have slightly different interpretations of these terms but the important thing is to understand the ideas, not to be too fussed about the jargon.

Hence it makes sense that, when splitting a design into modules, you should try to isolate the parts of the system that are likely to change.  This is given the software design catchphrase encapsulate what varies.

Flexible Interfaces

Having well-defined interfaces means that modules can be changed more easily, but often enhancements are required that mean the actual interface to a module needs to change.  Just having a simple, well-defined interface is not enough -- it's also important to have flexible interfaces that support forwards (and even backward) compatibility.

I think an example (in C/C++) is in order, to clarify this.  Imagine we have module A that enquires of module B the price of a stock using a function call like this:

     /* moduleB.h */
     extern long moduleb.get_price(const char * stock_code);

     /* moduleA.c */
     price = moduleb.get_price("GOOG");    // get Google's stock price

Now imagine this needs to be enhanced to allow the price of the stock to be obtained at any time in the past.  In C++ we can add a defaulted time parameter like this:

     /* moduleB.h */
     extern long moduleb.get_price(const char * stock_code, time_t time = (time_t)-1);

     /* moduleB.cpp */
     long get_price(const char * stock_code, time_t time)
     {
          if (time == (time_t)-1)
               time = time(NULL);     // default parameter value uses current time
          ...
 
     /* moduleA.cpp */
     price = moduleb.get_price("GOOG");
     ...
     price = moduleb.get_price("MSFT", open_time);

This allows the old module A to work with the new module B without any code changes.  This facility (of C++) is useful but module A stills needs to be rebuilt because the defaulted parameter is added by the compiler at compile-time.

If you try to use the old module A with the new Module B or the old module B with the new module A you will get a link error (for statically linked libraries) or a run-time error if using dynamic libraries.

A more flexible interface would allow optional parameters to be passed at run-time.  This is often accomplished using a text-based interface.

     /* moduleB.h */
     extern long moduleb.get_price(const char * params);

     /* moduleA.c */
     price = moduleb.get_price("code=GOOG");

Now if we enhance module B to accept a time then module A can be enhanced like this:

     /* moduleA.c */
     price = moduleb.get_price("code=GOOG, time=10:00");

If the old module A calls the new module B it behaves exactly as before, for backward compatibility.  That is, if the time parameter is missing the new module B should use the current time.

Also if the new module A calls the old module B then it can also behave sensibly, if it has been designed to be forward compatible.  That is, the original module B should ignore anything it does not understand, such as the time parameter.  Of course, this means that the current stock price will be returned instead of the price at 10:00, but this may be preferable to a run-time error.

Of course, the disadvantage of the above system is that you need extra code to create and parse the text strings.  This is one reason that XML is very popular for decoupling modules.  The main advantage of XML is that the parsing and validation can be done for you by using a DTD or schema.  There are other advantages to using XML such as the plethora of code and tools available and the fact that there are standardised, culture-neutral formats for numbers, dates, etc.

Dual Interfaces

Generally modules are written to only provide one interface to the outside world.

The inspiration for this idea came from the use of the "const" keyword in C+ and C, and const iterators in STL.  It allows you to pass a pointer (or reference) to a function and be sure that the function does not modify the object pointed to.

One technique that I have found useful is to provide two interfaces: one interface is read-only (ie is just used for enquiry) and a separate interface is provided that allows making changes.  When understanding the overall design of a system it is often very useful to know that one module does not affect another even though it may use it.

Using two interfaces in this way can help you to understand the design.  (Having more than two interfaces may indicate that you module violates SRP.)  For example, it is not uncommon to find a container passed to a method and not be sure that the method does not modify the contents of the container.

As a more complete example, consider a simple spreadsheet program that I once implemented using MFC.  MFC use a Document-View architecture which is an example of the Observer Pattern and a simplification of MVC (where the MVC model is called the Document in MFC and the MVC View and Controller are combined into the MFC View class).  Note that this is a good example of decoupling as the model need know nothing of its views - to update the views it simply broadcasts a message to which all attached views subscribe.

In MFC the model or Document is essentially a 2-d array that stores the data of all the cells of the spreadsheet.  The model class provides many methods for modifying the data such as changing the contents of cells, deleting rows or columns etc.  There are also methods that just retrieve information, such as cell contents.

In this design you can have multiple views connected to the same model.  For example, you could have two table views in split windows that show different parts of the model in the normal tabular format of a spreadsheet.  You could also have a other types of view such as a graph view which shows the spreadsheet data as a bar or pie graph.  This is shown in the following UML class diagram.

UML Diagram showing Model-View Associations.

The problem with this diagram is that the table and graph views appear equivalent.  In reality, the table view can make changes to the model, such as editing the contents of a cell, but the graph view only reads the data.  Unfortunately, in a UML class diagram such an association is represented by a dotted arrow and there is no way to differentiate between an association that modifies an object from one that only retrieves information.

Eliminate Unused Code

Unreachable code is code that can never be executed when the software runs.  It is similar to redundant code in that it can be indicative of a poor design -- though it is can be just an oversight.  To find such code a code coverage tool should be used to make sure your tests exercise all the code.  If code is not executed then create tests that cover it; if that is not possible remove the code.

One way I have seen unused code created is through misuse of inheritance.  If derived classes always override a method then there is no point having a base class implementation.  This typically indicates that the classes should be inheriting from an abstract base class (or an interface in C#/Java).

Conclusion

This post has looked at some techniques for deciding how to split a design into modules, how to design interfaces, and how to recognize a design that needs improvement.  Generally, good design requires experience and a readiness to learn new ideas, such as the design patterns discussed in the Design Patterns book that I have mentioned in previous posts.

Most software developers understand the benefits of decomposing a large program into modules.  In reality, the best way to do so is not always obvious and consequently most software still suffers from poor design. In my next post I will look at a common approach which is often used, but is rarely appropriate.  It is perhaps one of the worst design anti-patterns.

Dependency Injection

Last month I explained Inversion of Control (IoC).  A related term is Dependency Injection (DI) which is another technique for assisting modularity and decoupling.  The terms dependency injection and inversion of control often appear together so that some people think they are closely related or even the same thing.  This is not true, but DI is said to be an example of IoC as well as being a way to resolve dependencies in other uses of IoC.

There are many articles on DI on various web pages and blogs, and almost all are misleading or simply wrong.  They often describe design patterns that can use DI (like Strategy, Bridge, Adapter, etc) but do not explain DI.  For example, this article gives a beautiful description of the Bridge Pattern and it's advantages but wrongly calling it dependency injection.

In Brief

In essence, DI separates the mechanism for resolving references into a separate module, which is why it is good for modularity.  Remember the callbacks (and interfaces) that I talked about in the IoC post?  These are just function pointers that can point to any function with the correct signature.  An actual function pointed to is what the code depends upon to get the job done, so is referred to as a dependency.  How the address of a specific function is assigned to a function pointer is what DI is designed for.  A separate module resolves the dependencies and injects them into the other modules that require them.

An example always helps to make things clearer. The example below is in C, as I know that several readers of this blog are very familiar with C.  The fact that it is in C might also help to dispel the fallacy that DI is necessarily an object-oriented technique.

Version One - Original Code

The example is actually based on the first C program I ever wrote, which was an MSDOS program to display a list of files.  One of the features is that it would display the files sorted in different ways (by name, size, time of last modification, etc).  The information for the files was stored in an array of structures like this:

  struct dir_entry
  {
    char name[MAXFN];
    time_t modified;
    long size;
  } entries[MAX_ENTRIES];

Note that I have left out a lot of the code including #includes.  For example, you would need to include stdlib.h, string.h, assert.h, time.h, etc.

The code to display the files looked something like this:

  /* display.c */
  static int compare_file_name(const void *p1, const void *p2)
  {
     struct dir_entry * d1 = (struct dir_entry *)p1;
     struct dir_entry * d2 = (struct dir_entry *)p2;

     return _stricmp(d1->name, d2->name);
  }

  static int compare_modified(const void *p1, const void *p2) { ...
  static int compare_size(const void *p1, const void *p2) { ...
  static int compare_file_extension(const void *p1, const void *p2) { ...

  void display_files()
  {
    /* Get files of current directory into entries[] */
     ...

     /* Sort the files according to user preference */
     enum sort_type how = options_get_sortorder();

     switch (how)
     {
     case SORT_NAME:
          qsort(entries, num_entries, sizeof(struct dir_entry *), &compare_file_name);
          break;
     case SORT_MOD:
          qsort(entries, num_entries, sizeof(struct dir_entry *), &compare_modified);
          break;
     case SORT_SIZE:
          qsort(entries, num_entries, sizeof(struct dir_entry *), &compare_size);
          break;
     case SORT_EXT:
          qsort(entries, num_entries, sizeof(struct dir_entry *), &compare_file_extension);
          break;
     default:
          assert(0);
          break;
     }

     /* Display the files */
     ...
  }

As we saw in the previous blog this is an examples of IoC.  Control of the sorting is inverted by being passed to qsort() (a standard C library function).

This is a reasonable design.  First, it separates the code for sorting the files into a separate (standard) module (ie qsort).  There is also a separate module that handles the user options:

  /* options.h */
  enum sort_type { SORT_NAME, SORT_MOD, SORT_SIZE, SORT_EXT, };

  /* options.c */
  static enum sort_order current_sort_order;

  enum sort_type options_get_sortorder()
  {
    return current_sort_order;
  }

Diagram 1.

However, the above original code did not seem quite right to me  One thing was that the DISPLAY module knows how the sorting is done.  It seemed to me that only the SORT module should know any of the details of the sorting.  For example, if a new sort option was added then the above switch statement would need to be modified, to add a new case, and a new compare function written.

Version Two - Hide Sort Details

My instinct was to create a SORT module that wrapped all details of the sorting.  In fact I am sure that at least one tutor at university advised me that whenever code has to deal with details that are irrelevant to the task, then they should just be pushed down into a lower-level function.  (I later found that this is a simplistic approach but more on that in an upcoming blog post.)

So I created a new version of the code that hid the details of sorting in a separate SORT module.

  /* display.c */
  void display_files()
  {
    /* Get files of current directory into entries[] */
     ...

     /* Sort the files according to user preference */
     sort_files(entries, num_entries);

     /* Display the files */
     ...
  }

  /* sort.c */
  static int compare_file_name(const void *p1, const void *p2) { ...
  static int compare_modified(const void *p1, const void *p2) { ...
  static int compare_size(const void *p1, const void *p2) { ...
  static int compare_file_extension(const void *p1, const void *p2) { ...

  void sort_files(struct dir_entry *entries, size_t num_entries)
  {
     switch (options_get_sortorder())
     {
     case SORT_NAME:
          qsort(entries, num_entries, sizeof(struct dir_entry *), &compare_file_name);
          break;
     case SORT_MOD:
          qsort(entries, num_entries, sizeof(struct dir_entry *), &compare_modified);
          break;
     case SORT_SIZE:
          qsort(entries, num_entries, sizeof(struct dir_entry *), &compare_size);
          break;
     case SORT_EXT:
          qsort(entries, num_entries, sizeof(struct dir_entry *), &compare_file_extension);
          break;
     default:
          assert(0);
          break;
     }
  }

Diagram 2.

This is an attempt to decouple the sorting code from the display code, but is it any better?  It's basically the same as the previous code but has simply pushed the sorting into a subroutine.

In many years of reading (and often writing :) lots of bad code, I have come to dislike this approach.  It results in software that is very hard to decipher as function calls can end up being nested dozens of levels deep.  Moreover, it often means that related pieces of code can become separated resulting in a design that is inefficient and (more importantly) difficult to understand and modify.  It also seems to encourage duplicate code as you often see similar pieces of code all over the place.

Another indicator of a bad design is the number of modules that need to be modified to accommodate a simple change.  If a new sort order option was required then, using the above design, we would have to modify both the OPTIONS module and add a new compare option to the SORT module.

Finally, a principle you should always try to uphold is DRY (don't repeat yourself).  All the calls to qsort() in the above switch statement are almost identical.  Is there a way to eliminate this redundancy?

Version Three - Separating Comparison from Sorting

Looking again at the above code...  Is the  SORT  module the best place for the comparison functions?  Sure sorting needs to know how to call the appropriate comparison function, but this is just a matter of knowing the signature of the function.  A breakthrough was realizing that comparing can, and should, be decoupled from sorting.  This is an example of the strategy pattern - the caller of the strategy only need know the interface, while the concrete strategy (the actual strategy used) can be in a different module.

In the next version of the software I moved the comparison functions to the OPTIONS module.  A pointer to the current comparison function can be obtained from the  OPTIONS module and passed to qsort.  This avoids having the extra sorting layer - now the sorting "module" (ie, qsort) has the single responsibility of performing the sort.

  /* display.c */
  void display_files()
  {
    /* Get files of current directory into entries[] */
     ...

    /* Sort the files according to user preference */
    qsort(entries, num_entries, sizeof(struct dir_entry *), options_sort_strategy());

     /* Display the files */
     ...
  }

  /* options.c */
  typedef int (* PCOMPFUNC)(const void *p1, const void *p2);

  static int compare_file_name(const void *p1, const void *p2) { ...
  static int compare_modified(const void *p1, const void *p2) { ...
  static int compare_size(const void *p1, const void *p2) { ...
  static int compare_file_extension(const void *p1, const void *p2) { ...

  PCOMPFUNC options_sort_strategy()
  {
    switch (current_sort_order)
    {
    case SORT_NAME:
        return &compare_file_name;
    case SORT_MOD:
        return &compare_modified;
    case SORT_SIZE:
        return &compare_size;
    case SORT_EXT:
        return &compare_file_extension;
    default:
        assert(0);
        return &compare_file_name;
     }
  }

Diagram 3.

Now the  OPTIONS module is responsible for determining the sort order.  If new sort options are added only that module needs to change.  However, it is still up to display_files() to call options_sort_strategy() to find out how to sort.  Relieving the DISPLAY  module of this last burden is accomplished with DI.

Version Four - Dependency Injection

Using DI, the  OPTIONS module is given control (using IoC) of setting up the callbacks.  The inject_comparer() function was created to inject the comparer dependency into the  SORT  module.  It is invoked whenever the sorting order changes and sets the default sort order during startup.

  /* config.c */
  static PCOMPFUNC current_file_comparer;

  static void initialize()
  {
    current_file_comparer = find_default_comparer();
    inject_comparer();
  }

  void config_set_comparer(PCOMPFUNC f)
  {
    current_file_comparer = f;
    inject_comparer();
  }

  static void inject_comparer()
  {
    sort_set_comparer(current_file_comparer);
  }

  /* options.c */

    ...
    config_set_comparer(new_comparer);
    ...

  /* sort.c */
  static PCOMPFUNC comparer;

  void sort_set_comparer(PCOMPFUNC f)
  {
    comparer = f;
  }

  void sort_files(struct dir_entry *entries, size_t num_entries)
  {
    qsort(entries, num_entries, sizeof(struct dir_entry *), comparer);
  }

Diagram 4.

The main difference here is that the CONFIG module has control of setting the sort order.  It injects the comparer into the  SORT  module.  The  SORT  module is just a wrapper of qsort that also stores the current comparer.  The concrete comparer functions are no longer part of the display or  SORT  module, but are set up in the config module (eg, at startup, when the user changes the sort order, etc).

The advantage is that the configuration is dynamic.  The  CONFIG  module can even discover or create new comparers at run-time.

Moreover, the existing software does not need to change when a new comparer is added.  This is great for maintainability since it avoids code changes that have to be reviewed, tested, etc, and could potentially introduce new bugs.

Dependency Injection

As we saw above DI is useful when used with the strategy pattern; but, in general, it can be used with any design that uses run-time polymorphism.  The point is that there is a separate module that resolves references at run-time and injects them into the relevant module(s).  These references can be injected as an interface (ie, pointer to a table of function pointers), or anything that allows code to be executed indirectly.  In our C example we simply used a function pointer.


One thing I particularly like about DI is that new modules can be added without changing the existing software.  As long as the new modules can be loaded dynamically then it is just a matter of configuration to inject them into the system.  Maintainability is usually the most important attribute of software and this is the ultimate in maintainability as the existing code does not have to be modified or even rebuilt.

The concept behind DI has been used in a more limited way by Windows software that supported plug-ins.  (I first saw this used in Windows 3.1 more than 20 years ago.)  Plug-ins rely on DLLs that all implement the same interface (ie set of functions).  A plug-in manager is often responsible for discovering the plug-in DLLs (eg, by looking in a certain directory) and injecting them into the relevant parts of the system.

Finally, I should clarify the relationship between Dependency Injection and Inversion of Control.  DI is related to IoC in two ways.  First, it is an example of IoC since it inverts control by passing control of setting up dependencies to the CONFIG module.  It is also often used with other types of IoC in setting up dependencies, since IoC is usually implemented using callbacks (pointers to interfaces or pointers to functions as we saw in the blog last month).

Conclusion

DI is a useful technique for decoupling of modules.  It separates out the responsibility for making connections between other modules.  However, many of the advantages often put forward for DI are not due to DI per se, but to its uses with design patterns such as Strategy, Bridge, Adapter, etc.

The true advantage of DI is that it allows better configuration.  This can go as far as discovering and using new code at run-time (as in the plug-ins we discussed above).  It is very useful for connecting up mock objects for unit tests.  Also by allowing software to be extended without any change to the original code it is great for maintainability.