Simple Design Patterns


Joseph Bergin
Pace University

csis.pace.edu/~bergin
berginf@pace.edu

Introduction

A "pattern" is a solution to a problem in a context. Over the past few years, a movement to develop patterns and "pattern languages" has developed. This work in computer science, and especially in the object-oriented community is based on the work of Christopher Alexander of UC Berkeley, an architect and professor of architecture who has developed such a concept in architecture over the past many years. A pattern language is a set of related patterns that work together in some context.

The design patterns community uses patterns and pattern languages as a means of communicating detailed problem solving knowledge from an expert in one domain to those who might benefit from the knowledge in another domain. To some extent, a pattern is an attempt to establish "best practice" with respect to a problem or class of problems.

One way to think about patterns is to think about the medieval apprentice system. A young person would apprentice to a master who would try to transmit the knowledge of the trade to the novice. The novice would begin by doing relatively simple and straight forward work, but would also often examine the more complex and intricate work of the master. The master would transmit knowledge by showing the novice how a certain thing could be done in the context of solving a certain kind of problem. For example, if the trade were stone carving, the novice would start out with simple patterns, probably marked by the master. The results most likely were fairly blocky with heavy bases. As the novice progressed, more advanced work could be undertaken. Some work was always challenging, even for masters, such as a rider upon a horse, due to the thinness of the legs of horses relative to the strength of stone. Over time, solutions to complex problems were found and refined by masters, who would then transmit the knowledge to novices.

In the educational setting, patterns provide a way for a master (the professor) to show a novice how to solve problems in context. Pattern languages are a formal mechanism for presenting patterns and thus transferring the knowledge. A comprehensive collection of patterns can be compared to an auto repair manual for a 1961 Volkswagen Beetle: solutions to problems in context.

Richard Pattis' book Karel the Robot (Wiley, 1981) was written at a time before the pattern movement began. Nevertheless, the author seems to have been thinking in terms of patterns in many parts of the book. His Stepwise Refinement discussions are one example. Even simpler is his discussion of nested if statements and the transformations that can be done on them. This gives the novice programmer an excellent framework for thinking about if statements as well as the specific topic: nested ifs. In the second edition (1995), Jim Roberts and mark Stehlik carried this a bit farther with their decision map. I tried to carry on in my extensions to Karel the Robot, that resulted in Karel++ (1997).

I think we need to start a conversation about extremely simple design patterns and pattern languages that can be used by novices in learning programming. The purpose is to get educators thinking about these simple patters and how the information we transmit to students can be framed as design patterns. This will have two important benefits. First, it will get educators to formalize what they do, as patterns provide a framework for presentation, discussion, and refinement. Second, students will become familiar with patterns and will be introduced to an important information transfer mechanism. Ideally, students can begin to look at patterns in CS1. They need to look at this information anyway. Patterns simply gives a way to present the information in a regularized format.

There are actually two movements going on, with different goals. One involves the Design Pattern community who have held annual conferences (PLoP Pattern Languages of Programming) conferences sponsored by the ACM. There is a web site (http://hillside.net/patterns/patterns.html) devoted to this work. You can find a nice FAQ there as well as a bibliography and several patterns and pattern languages. The second community is involved in Pedagogical Patterns. The emphasis here is on patterns of instruction. The web site for this is http://www.cs.unca.edu/~manns/oopsla.html. this site contains several contributed patterns. This information will be collected into a book.

What is being proposed here has elements of both existing movements. The Design Patterns community contributes "what to teach" and the Pedagogical Patterns Community speaks to "how to teach it." Both are vital, of course.

First, A Syntax for Presenting Patterns

If we are to transmit knowledge systematically, it helps to have a common expression framework. Once a student is familiar with the framework, they can more quickly and easily absorb the content. The pattern syntax I suggest we start with is very simple. I've selected sixteen elements by scavenging from the book Pattern Languages of Program Design 3, edited by Martin, Riehle, and Buschmann (Addison-Wesley, 1998). I'm not sure that these are the right elements, and some of them clearly overlap with others. To express a pattern in this pattern syntax you just fill in the sixteen elements. Feel free to omit an element if it is not applicable, but you might be better entering TBA (To be announced) rather than omitting an element. You can also reorder the elements as appropriate or supplement this list with other elements. Doing so might eventually cause the pattern syntax itself to evolve.

In any case, here are the sixteen initial elements of the syntactical form with a very brief explanation of each. This is a particularly simple kind of syntax, by the way. Basically you just fill in the blanks under the various titles to get a pattern.

There are two ways that such a pattern structure could be used. First, a pattern could be created from it intended for use by students learning a particular skill. But the same syntax could be used in a different way to transfer teaching techniques between educators. It is necessary to think about who the audience is when writing a pattern. In what follows, I'm not sure that I did a particularly good job of making this distinction. It needs refinement. That is why all patterns have version numbers.

Also, the "author" tag shouldn't be taken too literally. Patterns are not about something new that was created by a certain person. Patterns are about common practice. All the author has done is abstract the practice into a form that permits its analysis and refinement. Also, ideally, once a pattern is submitted by an author, it is analyzed and refined by others. Pattern writing is really a team effort. The author is really just the person who proposes a pattern. This requires more humility than we (professors) often show. In pattern workshops, one technique for analysis of a pattern is to have the author present but not allowed to participate in the discussion of his or her pattern.

If our patterns were intended for more advanced audiences, it would be important to include two additional sections.

In other words, "why is this pattern 'best practice' in this context?" The patterns community considers this to be the essential part of a pattern. I left this out of the syntax as these are intended for novices, but some of this material is discussed in notes in the patterns that I've included here. Maybe they should be included even for novices.


Some Example Patterns

Now that we have a simple pattern syntax, we can try to express some simple design problems in it. I've chosen some here that are simple, but not all equally simple. All can be used in a CS1 course at various points. They are not intended to be profound, but simply to illustrate the possibilities. They are also probably incomplete, but note that most patterns should be expressible in from a few paragraphs to a few pages. Fifteen pages seems to be a common length for the complex patterns in the PLoD3 book mentioned above. Some patterns for novices should be shorter, but not necessarily all, since a novice might need more explanation when the pattern is subtle or has a few parts.

There is a joke in the pattern community that someday someone will try to submit the Linked List Pattern to a PLoP conference. I won't do that, but I do present that pattern here. After all, patterns ain't just for the big kids.

I've assigned all of these patterns version number 1.0. Perhaps that is overstating their level of development. Maybe 0.3beta would be better.


Output Columns of Values (v 1.0)

Author

Joseph Bergin

Intent

To achieve columnar output of a set of values to a page or screen, such as:

	index:	value:
	0		10
	1		25
	2		31
	3		42

Other Names

None known.

Problem

We have a set of data, perhaps with several parts and we want to present it in an easily digestible way.

Motivation

Context

This pattern can be used in which data occurs as a collection of values that must be presented to a human reader. It is also sometimes used to save values in files for later reading by machine. An important element is the similarity of the data values to each other, requiring a systematic means of presentation.

Example

Suppose that we have an array with four elements as above and we wish to display that data along with the index at which we can find each value. The following C++ fragment will achieve this.


	for(int i = 0; i < 4; ++i)
	{	int value = A[i];
		cout << "   " << i << "  " << value << endl;
	}

Required Elements

You need three parts for this pattern. First you need a loop. Second you need an output statement that will print one value in the set on a line by itself, using variable names to stand for the parts of the data that are interesting. Third, you need a way to get the data values themselves: the data generator.

Structure

The loop is written to contain the other two elements. The data generator comes first and the print statement comes last. The loop control is such that all elements of the data set will be covered. Each element in the output statement willl result in a different column. Some of these elements can be variable data, others can be formatting or fixed text.

In the example above, the three parts were made explicit. The first line controls the loop. The second is the data generator (for the array values at least) and the third is the output statement.

Applicability

Consequences

Your output will be easier to read and also easier to generate.

Known Uses

Related Patterns

None yet.

References


Nested If Statements (v 1.0)

Author

Joseph Bergin

Intent

If statements choose among two alternatives. Switch statements choose several alternatives but only along a single scale. Nested if statements can handle more complex situations.

Other Names

None known.

Problem

Two independent choices result in four possibilities if the choices are truly independent, or fewer if there are some linkages. For example, if graphical figures can be rectangular or not, and they can have background patterns or not, then we have four possibilities. This can easily be seen by representing the independent choices as independent axes as in the following figure. A figure like this can be called a "choice figure."

In programming we often have independent choices to make with different processing needed for each of the combinations of choices.

Motivation

Context

Example

Suppose that we have a point in a geometric plane and that we want to print out the quadrant of the point. The point is represented as two values x, and y. The following Java fragment will achieve this, using the usual numbering of the quadrants.


	if(x > = 0)
	{	if(y >= 0)
		{	System.out.println("First");
		}
		else
		{	System.out.println("Second");
		}
	}
	else
	{	if(y >= 0)
		{	System.out.println("Third");
		}
		else
		{	System.out.println("Fourth");
		}
	}

However, if we reverse the inner and outer structures we must proceed differently.


	if(y > = 0)
	{	if(x >= 0)
		{	System.out.println("First");
		}
		else
		{	System.out.println("Third");
		}
	}
	else
	{	if(x >= 0)
		{	System.out.println("Second");
		}
		else
		{	System.out.println("Fourth");
		}
	}

Required Elements

Two if statements, each of which controls some Boolean condition. These two if statements may or may not have else parts.

Variations

If fewer than four distinct kinds of operations need to be done then the nested if structure should be modified. For example, if the processing in one or more combinations is "do nothing" then one or more of the else blocks may be omitted. If two of the combinations have no processing, then we may be able to achieve the desired result without nesting if's at all. However, if there are two cases that require processing and these fall on the diagonal in the choice figure, then we do need nested if statements.

Another variation is when you have more than two independent choices. In this case the number of possibilities expands by powers of two. More than three independent choices (eight possibilities) leads to code which is difficult to read and understand, however, so the use of this pattern for large number of independent choices is discouraged.

If the two decision criteria are truly independent, then the if statements should nest in either order. However it may be that partial dependencies may require that one nesting structure is much better than another.

Structure

In greatest generality, each of the if statements has an else part. In this case the inner test is repeated in both parts of the outer test. Notice that the structure of the inner if is repeated, but the processing provided by the "then" and "else" parts may be different in the two versions.


	// Independent choice pattern, two choices.  
	if(... outer test ... )
	{	if(... inner test ... )
		{	...  both true
		}
		else
		{	... only the first true
		}
	}
	else
	{	if(... inner test ... )
		{	... only the second true
		}
		else
		{	... neither true
		}
	}

Applicability

This pattern applies whenever you have two or more independent choices to be made and the processing depends on the combination of choices.

Consequences

Known Uses

Related Patterns

References

Richard Pattis, Karel the Robot, Chapter 4, Wiley, 1981.

Pattis, Roberts, Stehlik, Karel the Robot, 2ed. Chapter 4, Wiley, 1995


Client Server (v 1.0)

Author

Joseph Bergin

Intent

Object-oriented systems are often viewed as if each object fulfills "roles" in carrying out the overall processing. Two of the most important roles are Client and Server. The Server controls some information needed by its Clients. The client asks the server to perform the service.

Other Names

Problem

In an object-oriented system one component object (the client) requests service of another object by sending a message naming a variable referencing the service provider and the name of the service required along with any parameters. The service provider interprets the service name (a function name) according to its own type and executes one of its methods to fulfill the service. Results of this method invocation are returned to the client.

Since a variable can refer to different objects at different times, the client may not know explicitly which server it is corresponding with since it uses a variable to get access. In an object-oriented system, with polymorphic types, it is not even clear what specific type (class) the server belongs to. Therefore the client does not, in fact, specify which code is to be executed, but only which service is desired.

For this to work two things are required, one structural, and the other logical. First, structurally, all of the possible services must provide the same service interface so that clients may correspond with them. This is usually achieved by having all servers derive from a common base class or all implement a common interface.

Secondly, and more important to the correctness of the program, the fulfillment of the service must be predictable from the clients viewpoint. Each server, no matter what its class, must "do the right thing" to fulfill the service request on behalf of the client in the way that would not be unexpected. Different servers in different classes provides a way to achieve different implementations and a variety of services, but not chaos.

For example, in the real world, when you go to a bank to cash a check, you don't know (or care) what specific procedures the bank uses behind the counter to fulfill the request as long as the results are accurate from an accounting standpoint. In fact, different banks use different procedures, but from the client standpoint they all "seem" the same.

Motivation

Context

Examples

To print a document you make a print request of a print server. To extract an element from an array you make an access request of the array. To save a value in a linked list you make an insert request of the list or an iterator associated with the list.

Required Elements

Two objects are required, one holding access to some information or service and the other desiring access to that information or service.

Structure

A server or class of servers implements a public interface. The interface consists of the services that are provided. The server itself is visible in some scope.

A client within the scope of a server requests service by naming the server and one of its services. Additional information is passed as parameters in the service request. The client usually waits for the service to be performed.

The server receives the request and the parameters and carries out some processing on behalf of the client. The server then returns any generated results to the client.

The client receives the results and continues.

Note that the server may require help in fulfilling a client request and may itself act as client with respect to another object that acts as server to help carry out the original request. This can proceed recursively, but each request finally returns and the object making the request resumes.

Variations

Often there are a number of servers that can serve the same kind of information though they may not be identical or even belong to the same class. For a set of servers to provide a service to a set of clients, the interface of each server must be consistent with that of the others. This is usually achieved using inheritance. All of the servers are derived from a common base class.

Applicability

Consequences

When the entire application is viewed as a collection of interacting clients and servers an appropriate mental model of object-orientation is formed. An application is a web of interactions between independent objects (clients) requesting and receiving services from other objects (server). Each object is autonomous and independent. No object imposes action on another, but only requests service of other objects.

Known Uses

This is the dominant concept in object-oriented programming. Each message can be considered to be a client's request for service. The client code names the server and the service along with parameters as necessary.

Related Patterns

References

The following two patterns work together. As such they form a trivial example of a pattern language. This language could be extended with Stack and Queue patterns also. I am also an advocate that students should see formal design methodologies early on and begin to work with them. CRC (Class-Responsibility-Collaboration) cards are one simple tool that is easy to use as well as powerful. The simpler aspects of the Unified Modeling Language (UML) are also accessible to novices. In the Linked List pattern I've included CRC cards and a Class Diagram in the style of UML. The sequence diagram in the above pattern is also standard.



Link (v 1.0)

Author

Joseph Bergin

Intent

Linking nodes together requries steps be executed in a certain order to maintain consistency of the data structures that contain nodes. Understanding this pattern is fundamental to success with Linked List and other similar patterns.

Other Names

Connect.

Problem

A structure must be maintained using individual Nodes and linkages between them. The nodes are allocated from a free memory store (heap or array). The linkages are pointers, references, or sometimes indices into an array. The linkages of a newly allocated node must be set correctly and in a certain order if errors are to be avoided.

Motivation

Professionals often write code with linked structure. The pattern of assignments needs to become second nature so that it can be done correctly with little effort.

Context

Any situation in which nodes must be connected by pointers or references requires the use of this pattern. Prior to linking we have the following situation:

We require some reference (pointer), P, to the node A. Conceptually, we want to clone the node A to which P refers to achieve the following situation.

We then normally put a new value into either A or its clone. In almost all cases it is the clone that gets the new value.

Example


Required Elements

A linked structure, composed of nodes and references or pointers to nodes, and a reference, P, to some node within the structure. Here we assume that the nodes consist of a value part (value) and a link part (next). Linkage to new nodes is achieved with assignments. The ordering of the assignments is critical.

Structure

Successfully linking requires three steps. They must be done in the following order.

(a) a new node must be obtained.

(b) the link field of the clone must be made to be a copy of that from A.

(c) The link field of A must be made to refer to the new node.

Using C++ code this looks like the following.


	temp = new Node();
	temp->next = P->next;
	P-> next = temp;

We may then insert a new value into either the node to which P refers or the one to which temp refers. This step can be performed at any point after step (a). The two cases are detailed below.

If the new value is to be placed into the newly created node (standard) then we complete the operation with

(a') insert the new value into the newly created node.


	temp->value = ...;

If the new value is to be put into the original node (uncommon), then we must first copy the old value into the new node to complete the clone operation which was left incomplete above.

(a') copy A's value into the node referenced by temp

(b') insert the new value into A.


	temp->value = P->value;
	P->value = ...;

Notes

Novices often incorrectly follow the three steps above with a deletion of temp, thinking that they are done with the variable. They forget that it isn't the variable that is deleted, but the value to which the variable refers that is deleted. In this case that is still the newly created value, which we definitely want preserved, not deleted.

In some languages the linkage code does not all appear together. For example, in C++ a Node constructor might provide steps (a) and (b), in that order. For example


class Node
{	Node(T v, Node* n): value(v), next(n){}
	...
}

The usage is then just


	P->next = new Node(v, P->next);
This matches the pattern as the execution path is to create the new Node (a), initialize it (setting its next field (b)) and then assigning the newly initialized value to the variable (P->next) on the left side of the assignment(c). The steps occur in the correct order.

Variations

If the structure is doubly linked as below, then both links of the new node must be put into place, of course, but the reverse link in the node B must be modified as well so that it points to the newly created node.

(a) create the new node.

(b) set its next link to be a copy of that from A.

(c) set its reverse link to be a reference to A itself (as P is originally).

(d) set A's next link to refer to the new Node.

(e) set B's reverse link to refer to the new Node.


	temp = new Node();
	temp->next = P->next;
	temp->reverse = P;
	P->next = temp;
	P->next->next->reverse = temp;

The operation is then completed by setting values as was done in the case of single linking. Again, the values may be set any time after step (a). Note that the relative orders of steps (d) and (e) are critical to the success of this pattern. Steps (b) and (c) may be reversed, but (b) must also occur before (d).

The suggested pattern of assignments is safe and easy to remember. It has three parts. (1) create the new node (2) fill it in correctly (3) adjust the other links (from A and B) working from left to right.

Applicability

This pattern is used in all sequentially linked structures. Also see Notes, below.

Consequences

Use of this pattern will guarantee that linkage code is sound.

Known Uses

This pattern is used ubiquitously.

Related Patterns

Link List Pattern. Link provides the essential step in the linking process.

Notes

Sometimes the Nodes are more complex, with several links in each node. Each link will have a certain purpose. For example in a Tree structure there are often Left and Right links in each node, pointing to a left and right child node respectively. The Link Pattern can be used for each kind of link individually.

References


Linked List (v 1.0)

Author

Joseph Bergin

Intent

Data needs to be maintained in a sequential order and it must be possible to flexibly and efficiently insert and delete items within the structure to support a wide variety of processing.

Other Names

Sequence. (Properly, sequence is more general than this.)

Problem

Situations often arise in which a set of data must be maintained sequentially. If the situation requires that insertions and deletions be done quickly (small constant time), then the Linked List Pattern may be appropriate. This is especially true if most of the processing can be done in the order in which the elements are maintained.

Motivation

To provide a flexible container structure that provides constant time insertions and deletions anywhere in the structure.

Context

Example

Required Elements

The Linked List Pattern has three parts, usually represented as classes.

(1) Node: A node is the basic building block. It contains a data value and a reference to another node.

(2) List: This is the structure as a whole. Its implementation requires a reference to one or more nodes. Additional information is also sometimes maintained such as the number of values in the sequence

(3) Iterator: This represents an abstract reference to a value within the list. Its implementation uses a reference to one node, or perhaps two adjacent nodes. Occasionally an iterator will also maintain a reference to the list itself as well.

Structure

Linked List has three parts: Node, List, and Iterator. Each is modeled as a class.

CRC cards for the Linked List Pattern follow.

Class: Node

Responsibilities: 
Maintains a data value or a reference to a data value supplied by the user.  
Maintains a reference or "link" to one other node.  This reference may be 
	"empty" or null, or it may be another properly initialized node.  

Can yield its value to a user when needed.  
The value can be changed.
The "next" link can be changed.

Collaborators: List, Iterator 


Class List

Responsibilities:
Maintains the first of a sequence of nodes. 

Collaborators: Node, Iterator

Class: Iterator

Responsibilities:
Provides access to the values stored in an associated list.  
Maintains a single location within the associated list, by referencing a 
	particular Node. 
Can successively refer to each of the elements in the list, starting at the 
	first.  
	
Collaborators: Node, List

The Class Diagram for the Linked List Pattern follows.

This pattern has certain required classes and the classes have a certain required minimal functionality.


	class Node
	{	SomeType value;
		Node * next;
	public:
		...
	}


	class List
	{	Node * first;
	public:
		Iterator newIterator();
		bool empty();
		...
	}

	class Iterator
	{	List * myList;  // Recommended, but optional.
		Node * here;
	public:
		void insert(SomeType v); 
			// Insert v after this location in a new node. 
		void remove(); // Remove the value after (not at) this location. 
		void setValue(SomeType v); // Insert v into this location. 
		SomeType getValue() // Return the value at this location. 
		void advance(); // Set the location one place forward.
		bool atEnd();
		...
	}

Note that the Node structure is recursively defined. A special value is often used to provide a base case for the recursion. In C++, the value NULL is used. The Node class is not normally used publicly, but is actually an implementation type for the List and Iterator types.

Most of the functionality is maintained in the Iterator type, not the List type.


Rationale

The iterator provides the flexibility needed by the structure. To insert an item into a list at other than the head or tail, we need an iterator to the point of insertion. The iterator needs operations that will move it along the list from one node to the next. Abstractly the iterator refers to the location following the one to which it physically points. Notice that many iterators could be maintained simultaneously into the same list structure, making it possible to implement complex algorithms without modifying these structures.

Variations

Linked lists may be singly linked or doubly linked. In the doubly linked pattern, there is an additional link in each node. This "previous" link in a node A refers to the node, B, whose "next" link refers to A. Double linking requires approximately twice the effort and time as single linking, but it adds flexibility to the processing.

Linked lists may also be linked circularly, with the last element connected to the first.

Another variation puts a special "header" and/or a special "trailer" node at the beginning/end of each list. This node does not contain normal data, but is used to simplify testing of position. Such additional nodes can also be used to break the recursive cycle. Sometimes the next field of a trailer node refers to that node itself.

One very important variation does away with the Iterator altogether and provides only access to the head of the list and the rest of the list (its tail). Such lists must necessarily be processed recursively if complex algorithms are to be created. The language LISP is fundamentally based on this idea.

Applicability

Use this pattern when efficiency of insertion and deletion is more important than randomly searching.

Consequences

The linked list structure trades efficiency of insertions and deletions against the possibility of processing the elements in random orders.

Known Uses

Linked lists are used as a fundamental building block for many other structures such as the Stack structure and also in many application domains.

Related Patterns

Link Pattern. This pattern depends on Link. Vector Pattern. Array Pattern. Stack Pattern. Tree Pattern.

Notes

Expert programmers often merge the List and Iterator concepts and represent both as just a reference (pointer) to a Node. While this is marginally more efficient, it holds pitfalls for the novice. Experts don't usually have a problem keeping the various uses distinct. Novices often do. In particular, it is easy to lose the beginning of a list if you confuse a pointer representing the list as a whole, with one representing a location within it. Advancing the latter is fine, but advancing the former is problematical unless you have a copy (or double linking).

If generic programming facilities are provided in the implementation language, it is recommended that the value type stored in the nodes be generic.

References

"Lists with Current Considered Harmful", Joseph Bergin, see: http://csis.pace.edu/~bergin/