• entries
    146
  • comments
    436
  • views
    197748

Patterns and Practices

Sign in to follow this  

262 views

Patterns are a funny thing, they crop up throughout development without you ever even noticing. Through the process of analysis, one can discover the myriad of forms that these patterns have taken, and then use that information to generalize the pattern by giving it a name and a definition, with the definition including the problem for which it solves, and the parts that make up the solution to said problem. It is through this process that many of the most common patterns have been found (not invented, as they already existed, it just required the realization of their existence).

Each pattern has a problem domain for which it is applicable, and identifying when a pattern is appropriate for a problem is a tricky business indeed. The only real solution to the problem of knowing when to use a particular pattern is experience.

What are Design Patterns?
According to Christopher Alexander, "Each pattern describes a problem which occurs over and over again in our environment, and then describes the core of the solution to that problem, in such a way that you can use this solution a million times over, without ever doing it the same way twice" [GOF, pg. 3]. Now, according to this definition, a linked list could very well be considered a design pattern. In the context of these journal entries, however, a design pattern is considered to be a bit higher level than your data structures, they shall be considered more of a means of describing a solution to a series of problems involving the interaction of objects in a complex system.

Types of Patterns
So what kinds of patterns are there? Many. Pretty much every field in software development has a set of design patterns that are applicable to that problem domain. Multithreading, high level module interaction, class relationships, method relationships, networking, you name it and it probably has a set of patterns that can be utilized to solve problems that crop up frequently in that field.

Now, some of these patterns are cross-domain in that they appear in more than one field. For instance, multithreading has a pattern that emulates a transaction, it is used to ensure that multiple threads complete a sequence of actions and rolls back on any errors. You also happen to find a similar pattern in enterprise application architecture. This particular pattern (namely the Transaction design pattern) happens to exist in both problem domains, however the problem it solves is the same in both. The only real difference between the two is just in the implementation of the pattern.

Knowing When to Apply a Pattern
As I noted above, the only real way to know is experience. There are some things you can do that will guide you in the right direction, though. First and foremost, refactoring. Through refactoring, most patterns will emerge from software (if it's not hacked together) naturally. This is an interesting point as an implementation strategy, as if the pattern emerges naturally from the code through refactoring, then you have successfully met one of my Software Developer Guidelines (more on this in a bit, yes Oluseyi they are coming [grin]). At another time you will find that you have applied a pattern through design. In this case, while you were designing the module (or modules) you found a solution to a particular problem that worked nicely and that you used again elsewhere to great success (a big hint that you've probably found yourself a pattern). Finally, you may have explicitly used the pattern because you found a problem and noticed that this particular pattern would solve it. The latter case is one that you really do have to be careful of, implementing patterns just to implement patterns is A Bad Thing&tm;.

Software Development Guidelines
From this point forward, I will attempt to always provide a guideline or two that I personally follow in my journal. These guidelines will be indicated by a short sentence followed by a longer explanation at or near the end of the section.

  • Patterns should emerge from code, not be forced out of code.
    Refactoring is the optimal way of ensuring that you don't violate this guideline. If you can refactor to a pattern, then it has emerged from the code. If on the other hand you must force the code to fit a pattern, chances are you have chosen the wrong pattern for your solution.



A Refactoring
A friend of mine asked me to look at a piece of code he had written, and give him some hints for refactoring it. I looked over his code, and noted a good deal of refactoring could be done indeed. Some of it was the usual simplification of code by using the Extract Method refactoring, but one part was a large chunk of duplication. Now, I present his original code here, unmodified mind you, and as you can see, all three of these find methods are almost exactly identical. In fact, if you just go up a single level of abstraction in your thinking, they ARE identical. That's an awful lot of duplicated code to maintain.

const Token * TokenStream::Find ( const char * token, int index )
{
if ( index == -1 )
{
index = (int)currentToken;
}

while ( index < (int)tokenList.size() )
{
if ( !strcmp( tokenList[ index ]->GetToken(), token ) )
{
currentToken = index;
return tokenList[ index ];
}
index++;
}
return 0;
}

const Token * TokenStream::Find ( int type, int index )
{
if ( index == -1 )
{
index = (int)currentToken;
}

while ( index < (int)tokenList.size() )
{
if ( tokenList[ index ]->GetType() == type )
{
currentToken = index;
return tokenList[ index ];
}
index++;
}
return 0;
}

const Token * TokenStream::FindReverse ( const char * token, int index )
{
if ( index == -1 )
{
index = (int)currentToken;
}

while ( index >= 0 )
{
if ( !strcmp( tokenList[ index ]->GetToken(), token ) )
{
currentToken = index;
return tokenList[ index ];
}
index--;
}
return 0;
}

const Token * TokenStream::FindReverse ( int type, int index )
{
if ( index == -1 )
{
index = (int)currentToken;
}

while ( index >= 0 )
{
if ( tokenList[ index ]->GetType() == type )
{
currentToken = index;
return tokenList[ index ];
}
index--;
}
return 0;
}





The first refactoring involved isolating the two types of finds we had, namely the token based find, and the type based find. By passing in an operator to the function, we can abstract out the incrementation, and by passing in the end condition, we can alter the while loop to run until the condition is met.

const Token * Find ( const char * token, int index )
{
DoFind(token, index, tokenList.size(), std::plus<int>());
}

const Token * FindReverse ( const char * token, int index )
{
DoFind(token, index, -1, std::minus<int>());
}

const Token * Find ( int type, int index )
{
DoFind(type, index, tokenList.size(), std::plus<int>());
}

const Token * FindReverse ( int type, int index )
{
DoFind(type, index, -1, std::minus<int>());
}

template<class Op>
const Token* DoFind(char const * const token, int index, int condition, Op op) {
if(index == -1) {
index = currentToken;
}

while(index != condition) {
if ( !strcmp( tokenList[ index ]->GetToken(), token ) ) {
currentToken = index;
return tokenList[ index ];
}
index = op(index, 1);
}

return 0;
}

template<class Op>
const Token* DoFind(int type, int index, int condition, Op op) {
if(index == -1) {
index = currentToken;
}

while(index != condition) {
if ( tokenList[ index ]->GetType()== type ) {
currentToken = index;
return tokenList[ index ];
}
index = op(index, 1);
}

return 0;
}




Even looking at this code you can see duplication. The only difference between the two finds is in what comparison operation they use to determine if a token has been found. We can abstract this by simply providing a functor that does the match.

Token* Find(char const* const token, int index) {
return DoFind(token, CharComp(), index, tokenList.size(), std::plus<int>());
}

Token* Find(int type, int index) {
return DoFind(type, TypeComp(), index, tokenList.size(), std::plus<int>());
}

Token* FindReverse(char const* const token, int index) {
return DoFind(token, CharComp(), index, -1, std::minus<int>());
}

Token* FindReverse(int type, int index) {
return DoFind(type, TypeComp(), index, -1, std::minus<int>());
}

struct TypeComp : std::binary_functionint, bool> {
bool operator()(first_argument_type arg1, second_argument_type arg2) const {
return arg1->GetType() == arg2;
}
};

struct CharComp : std::binary_functionchar const*, bool> {
bool operator()(first_argument_type arg1, second_argument_type arg2) const {
return !std::strcmp(arg1->GetToken(), arg2);
}
};

template<typename T, class Comparer, class Op>
Token* DoFind(T t, Comparer comparer, int index, int condition, Op op) {
if(index = -1)
index = currentToken;

while(index != condition) {
if(comparer(tokenList[index], t)) {
currentToken = index;
return tokenList[index];
}
index = op(index, 1);
}
}




There you have it, now it is much simpler to fix any bugs one might find in the find. In fact, the initial implementation of it that I wrote had a few minor mistakes, based on assumptions I made about his code. After reviewing those assumptions, I was (with only 2 changes) able to fix the mistakes I had made. Versus the 8 I would have had to make with the original code.
Sign in to follow this  


8 Comments


Recommended Comments

Mmmm propgating bug fixes instead of fixing ass loads of copypaste code and then missing one corner case. The joys of a properly designed system.

If I could rate you higher I would. :)

Share this comment


Link to comment
I think it's the duty of everyone who reads and enjoys this journal to leave a comment. Just so that you don't complain about the lack of comments, and keep updating.

Thanks for the information and examples.

Share this comment


Link to comment
So I follow the call of duty!
I have never read any journals before. Boy what have I missed! There's so much knowledge in (some of) them. Two questions:

1) Which journals are a must-read? (Especially on the topic of C++ and design (patterns))
2) Any chance you will write articles about e.g. iterator traits?

Greetings from another Anime-maniac,
Konfusius

Share this comment


Link to comment
I better leave a comment then. I really enjoy and benefit from your journal Washu. Keep it up!

Share this comment


Link to comment
Quote:
1) Which journals are a must-read? (Especially on the topic of C++ and design (patterns))


* SimmerD "Journey to the Ancient Galaxy": Graphics programming, physics and AI so far.
* Ysaneya: Computer graphics
* JohnHattan: A variety of good things.
* Oluseyi: Thought provoking posts.
* Radioactive-Software: Game development in general
* noaktree: Graphics, mostly
* EDI: Game production.
* Raduprv: Indie MMORPG development
* JollyJeffers: DirectX development and shaders.

I might've missed some, but these are the main technical ones.

Quote:
2) Any chance you will write articles about e.g. iterator traits?


Washu usually takes suggestions from the readers. So if you'd like to see something specific, PM him here or catch him on #gamedev.

Share this comment


Link to comment
Quote:
Quote:
2) Any chance you will write articles about e.g. iterator traits?


Washu usually takes suggestions from the readers. So if you'd like to see something specific, PM him here or catch him on #gamedev.
I would have to discuss it with some of the ERB people before I wrote such a set of articles, but I'll think on it.

Share this comment


Link to comment
I did a similar thing when I wrote my raytracer. The ray/aabb code I found had duplication all over the place, i.e. calculations that were done over and over hardcoded where they were needed. For illustration purposes I forgive them, but for my own code I ripped out about 4 functions and called them instead. Alot cleaner and assigning a variable a return value from a named function says alot more than some weird math algorithm, removing unnecessary comments too.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now