A design pattern is a general recipe for a common problem. Lots of problems in computer science are recurrent to many situations and an effort was created to catalogue the most common and define a simple and efficient recipe to solve the generic case.
As a recipe, it's not really a library or module, but a good practice. Some design patterns could be implemented in a generic way and exposed as an interface to your objects but the cost of being generic not always pay off. Therefore, patterns should be only recipes and you should follow them in your own code, implementing as instructed.
The good thing about patterns is that several good developers already had a similar problem and solved using that technique so you don't have to think too much to solve your problem as well. Also, other developers that see your code will identify the pattern and follow the same recipe when maintaining the code. In addition, pattern concepts often interconnect with each other so the more patterns you follow the easier will be to follow more.
Anti-patterns are the opposite, general recipes often used to solve a specific class of problems and that cause more harm than good. They were also used by several other people in similar cases, they've reached the same solution and thinking it was good enough, implemented. Only later they've found out all the new problems it brought and how bad were their solutions.
So, by understanding the anti-patterns, you know the path not to follow, even if you think that would be a good one. You may have very good reasons but you must remember that past developers also had good reasons and they failed miserably. To follow an anti-pattern you must know all the consequences and assure you won't fall into them, and pray.
There are lots and lots of design patterns and below I'll give only a few examples of the most common ones.
When there is a standard library but its usage is too complex or it could be simplified to your use you can build a facade. Facade pattern is when you write wrappers to simplify the usage of a specific library. This pattern is easily corrupted when you have more facades than libraries, which shows you that you need to review your code.
A facade should be a helper class simplifying only one library or set of functions with related functionality such as network connections, date manipulation, complex structures such as trees, graphs and queues, etc. It cannot be a list of random helper functions nor can it interact directly with your program's data but be completely de-coupled from any other code except the library it must simplify.
As an example, the Boost graph library is very powerful but also very complex. Normally you just need one or two functionalities in your code, so you can write a Facade class called Graph by wrapping the BGL's complexity and providing simple methods to insert, delete and retrieve vertexes and edges to your graph.
If the only type of graph you'll use in your code is the defined below, that's more than enough for you. Otherwise you may choose to increment your Facade or write new facades, one for each specialization, but that must be balanced with the complexity of the library itself, ie. your Facade cannot be more complex than the original library itself for obvious reasons.
// Link and Edge types
struct Link {
std::string value;
};
struct Edge {
long count;
};
// directed weight graph
typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS, Link, Edge > graph_t;
// Vertex and Edge descriptors
typedef boost::graph_traits < graph_t >::vertex_descriptor link_d;
typedef boost::graph_traits < graph_t >::edge_descriptor edge_d;
// Map with all vertexes and links (deduplicate)
typedef std::map < std::string, link_d > link_map_t;
class Graph {
// Graph and map with vertexes
graph_t graph;
link_map_t links;
public:
Graph();
virtual ~Graph();
// Add vertex
link_d addVertex(std::string&);
// Connect two vertexes
void addConnection(std::string, std::string);
// Get vertex
link_d getVertex(std::string&);
// Get edges of vertex
vector<edge_d> getEdges(std::string&);
};
When you have multiple classes of very similar concepts and it's getting out of hand to control them you need a Factory. Whenever you have multiple specializations that overwrite the basic methods, choosing the best specialization might not be easy, so this task might be given to the Factory to choose the best object to return that is a sub-class of the object requested.
For instance, if you are to connect to a server but you can do so over multiple protocols like HTTP, FTP or SSH. For the client, it doesn't matter which transport it'll use as long as it can get the content it's looking for. Normally, protocols are differentiated by the network port it uses so the client could distinguish using that information but sometimes the network port is different (for security or just because there's more than one server in the same machine).
That added complexity is killer to be implemented by the client every single time and to put this code in a new method in the client is not right because you'll need to add the code to every client that'll use the connection object, so this additional complexity could be delegated to a Factory.
class NetworkConnection {
// virtual class
NetworkConnection(server);
virtual ~NetworkConnection();
virtual void connect() = 0;
virtual void getFile(string&, ostream&) = 0;
virtual void disconnect() = 0;
};
class HTTPNetworkConnection : public NetworkConnection {
NetworkConnection(server) { ... }
~NetworkConnection() { ... }
void connect() { ... }
void getFile(string&, ostream&) { ... }
void disconnect() { ... }
};
class NetworkConnectionFactory {
static NetworkConnection* getConnection (server, port) {
if (port == 80)
return new HTTPNetworkConnection(server);
else if (port == 21)
return new FTPNetworkConnection(server);
else if (port == 22)
return new SSHNetworkConnection(server);
else {
// try to connect to the port and find what service is
...
}
}
};
Whether you have a list or a tree or a heap or a queue or a graph, one day or another you'll want to iterate through all its elements to find something or to print all the values or even to change something inside every single node. But all those structures are quite distinct from each other and the way to iterate through the elements each one of them is completely different.
Writing different code for each structure is a killer in your application and also it might not be trivial to understand at the first glance what you're really doing to the structure when you have different ways of navigate through all the elements of the structure, therefore Iterators are an important concept to be used when you want to write only one code for changing the values of the node no matter what structure is underneath.
All C++ STL and most Java containers have iterators and the code is extremely simple to use, but beware with performance, by using iterators too much you may fall in the Golden Hammer anti-pattern (see below), as iterating through all elements of a tree or sorted list is absolutely not the way to find a node. When looking for elements, use the container's specific search capabilities, but when you need to iterate through all elements of the container, use iterators.
Iterators can also be used for inserting elements. You can create an InsertIterator and send new objects to it and it'll automatically insert the element in the container and increment itself to accept a new object again. The insert iterator provides an incremented version where you can write your own inserter yourself and manage small problems during insertion that might happen.
typedef set<MyClass> MyList; MyList list; // Insert iterator: operator '=' inserts it insert_iterator< MyList > inserter (list, list.begin()); *inserter = my_object1; *inserter = my_object2; *inserter = my_object3; *inserter = my_object4; // Iterator: (*it) is the object itself MyList::iterator it; for (it = list.begin(); it != list.end(); ++it) (*it).property = value;
Normally, in object oriented code, we use the constructor to perform the creation of an object but when the structure needed to create is huge and not used often, you can just store the structure locally and initialize the parts you need later. This pattern states that you should only execute a method when you need it and not when you create the object. This is a very important patter for text parsers and in that case it's called Lazy parser.
As an example, I'll show a simple parser:
class MyParser {
dataBlock data;
string info1;
string info2;
string info3;
public:
// Simply store the whole block
MyParser(dataBlock& b) {
block = b;
}
// Parse when you need it
string getInfo1() {
// Not parsed yet, get it
if (!info1) {
// Parse block and get info1
...
info1 = ...;
}
// Now it's cached
return info1;
}
string getInfo2() { same as getInfo1 }
string getInfo3() { same as getInfo1 }
};
When you open an web page in your browser you're connecting hundreds of times on several different web servers at the same time and the result comes in much less than a second. In fact, several people at the same time are accessing the same web page and getting it at more or less the same time too. If web servers were implemented sequentially (one request at a time) you could never scale at that level.
Also, even if you had concurrent execution with threads or processes, just the effort of spawning a new process, connecting to the database (if any), reading data from the disk etc would be killer and the scale would be much less that what we normally see today. Web servers (like Apache) have a pool of processes idly waiting for web browsers or robots to connect to them, with all context already in memory, database connections and everything ready to serve the pages.
Database connection is also another important layer to have a pool. If, for every web page you create a database connection and destroy it at the end, you're wasting valuable resources that could be reused by other instances of the web server. Also, by having a separated pool of database connections you can scale differently the amount of web server and database instances when one side is more often used than the other. Normally, connection pools are often implemented in the enterprise application server layer and you can fine tune the parameters such as minimum and maximum number of processes.
For high performance programming there is also the thread pool, where you avoid the cost of creating and destroying threads to perform complex calculations. All threads in the same pool should be identical, just changing the data source because they're created during initialization time and not on-demand (thus the cost saving), so to have different threads you need separated pools.
In the thread pool you must control the same parameters and make sure that you don't run twice the same thing and that you wait for all threads to execute before continue running the rest of the code (even when the object goes off scope). As this can get quite complex and the generic solution is quite good for most cases, you should search for a good library instead of developing it yourself.
Proxies are heavily used in the internet too, where network connections can take several minutes or not even connect at all. The proxy helps to minimize those costs by pre-fetching and saving previously read data, controlling or restricting access to different resources and even create summaries and statistics in order to optimize further accesses through that channel.
You need a proxy when you have a high demand infra-structure and some expensive resources to crawl for data or when you want to control what objects (or users) can or cannot access. Sometimes you can start predicting where or when your future data will be available and the proxy can help you with the access.
Below is an example of a full-featured proxy object that can help with access control, cache of data and pre-fetching:
class MyExpensiveResource {
public:
dataBlock getData(string pattern) {
// a very expensive data crawl
}
};
class Proxy {
map<string, dataBlock> data;
AccessControl user;
MyExpensiveResource rec;
public:
DataBlock getData (string pattern) {
// First, test access
if (!user.hasAccess(pattern))
throw AccessDeniedException("while fetching 'pattern'");
// If NOT in cache NOR pre-fetched, fetch
if (!data[pattern]) {
// Get the data in cache
data[pattern] = rec.getData(pattern);
// Pre-fetch next (if obvious and not cached yet)
if (!data[pattern+1])
data[pattern+1] = getData(pattern+1);
}
// At the end, return data
return data[pattern];
}
};
Note that, when calling the proxy instead of the original object's method, all subsequent access for the same pattern will be much faster. Also, the access control is embedded in the proxy so you don't have to worry with that in your code. Last, to increase future fetches you can pre-fetch if the access is rather sequential (otherwise pre-fetch makes things much worse) but even sequential access you could fire the pre-fetch in a thread and don't even care if the fetch worked or not.
There are a few concepts considered harmful in programming languages and the two most common are GOTO statements and global variables. Even invariably happening in the lower level of every programming language, they're considered not only unpleasant to the eye but real problems of maintenance and understanding of the code.
In specific, global variables are harmful because virtually every method have access at any time to change their values and the order of execution in complex codes may be unpredictable, leading to bugs not always repeatable or understandable. The other problem is that a function that relies on global variables are not self-contained, you can't always assure the function will work well in another part of the code (when refactoring) nor that removing unused global variables won't actually break in other parts of the code. At last, global variables are easily replaced by local variables of the same name without intention, so you can reach a situation where you can't tell whether you're using a local variable, a global variable or a parameter.
There are some ways of sorting it out and the most used is to pass all parameters a function needs by argument. So, if the database connection is used by all methods of file you pass it to every method:
main() {
db = new DBConnection();
string query = "select * from dual";
prepare(query, db);
ResultSet rs = execute(query, db);
...
}
But even when passing the reference (to avoid copying the same object every type) it still pollutes the method definitions. It does solve the access and multiple copies problems but not all.
A better solution is to use Singletons. A singleton is a Factory that creates only one object. It have a static method getInstance() that will return the object itself, and every time any method calls it, it'll return the same object, so you don't need to make it global (it's a class, or in other words, defined statically and included when you include the header file) and you don't need to pass it as an argument to every method that uses it.
class DBConnection () {
private:
static DBConnection* db;
DBConnection () { } // private constructor, you can't instantiate yourself
public:
static DBConnection* getInstance () {
if (!db)
db = new DBConnection ();
return db;
}
};
void prepare (string query) {
db = DBConnection::getInstance();
...
}
ResultSet execute () {
db = DBConnection::getInstance();
...
}
main() {
string query = "select * from dual";
prepare(query);
ResultSet rs = execute();
...
}
Many real-world situations can be modelled as a set of finite states and finite transitions between states. There are several examples such as machinery automation, natural language, audio and video processing, complex structure navigators, complex text parsers etc. But the number of states tend to be quite high and the traditional implementation, by having a big table with all transactions between any given state (including itself), become impossible to maintain after a certain size.
Therefore a simpler model is required to help bring finite state machines to more complex problems where they could be really effective. One of this models is the State Pattern. The State pattern requires that no other object except the state itself knows about its transitions, thus concentrating the code where it's really necessary (high-cohesion) and avoiding spreading the knowledge of every state to different functions (low-coupling).
As an example, the states below:
A -(a)-> B -(b)-> D \-(c)-> C --(b)--^
In a table, you would need to state all conditions from all states to all states:
State: A B C D cond. a B - - - cond. b - D D - cond. c C - - -
With this, the method for the condition b would have to know about two completely unrelated states B and C and all it's internal idiosyncrasies irrelevant to each other. Instead, if you restrict the code per-state, the transition methods wouldn't have to know the internal structure of more than one object and because they're inside the object they have full access to its members and it increases the cohesion of your code.
class State;
class State {
virtual State* next() = 0;
virtual void run() = 0;
virtual bool isNotLast() = 0;
};
class StateMachine {
// The current state
State* current;
// Initialize with the first state
StateMachine(State* first) : current (first) { }
// Run current and change states until last
void run() {
while (current->isNotLast()) {
current->run();
current = current->next();
}
}
};
class A : public State {
// Do something useful
void run() {
print "I'm state A";
}
// Depending on conditions, change state (or not!)
State* next() {
if (a)
return B();
else if (c)
return C();
else
return this;
}
// This is not the last state
bool isNotLast() {
return false;
}
};
// All other states follow the same logic.
Templates are very used throughout all layers of software, from core libraries to presentation, although they are a bit different in every place. In the presentation layer, templates are used to standardise the look&feel of the interface, where you can only ”fill the blanks” with the dynamic data but it's on the object oriented context that templates gain its true power.
There are two types of OO templates, a simpler one based on virtual classes (sometimes called interfaces) that define the behaviour of a generic object so you can use whatever object you want providing it inherits (and implements) the methods from the virtual class. There is another template concept, widely used in C++ and recently added to Java is the ability to implement methods acting on post-defined objects (ie. you don't even have to inherit from any virtual class).
Lets start with the virtual class. Suppose you're writing a program to match genetic samples against each other. Because you have different materials (DNA or RNA or even protein sequences) and you can match them differently you want to write one program to match them all instead of having several identical small programs doing the same thing. So what you do is to create a virtual class to hold the sequence and write a program to perform matches on it. Than, by creating classes to hold the specific comparisons for DNA, RNA and protein sequences inheriting the structure from the sequence class you can create a list of all those child classes together even though they're all different.
class Sequence {
string sequence;
public:
virtual ~Sequence() { }
// Define what's needed
virtual bool compare(string otherSequence, int startPos, int stopPos);
};
class DNA : public Sequence {
public:
// Constructor
DNA (string seq) {
sequence = seq;
}
// Actually implement
bool compare(string otherSequence, int startPos, int stopPos) {
return (sequence.substr(startPos, stopPos-startPos) == otherSequence.substr(startPos, stopPos - startPos));
}
};
class Protein : public Sequence {
public:
// Constructor
Protein (string seq) {
sequence = seq;
}
// Actually implement
bool compare(string otherSequence, int startPos, int stopPos) {
// Do something different
}
};
int main () {
// Create the list and execute
vector<Sequence> list;
list.push_back(DNA("ACCGTTAGTGCAAC");
list.push_back(Protein("SSWWAHVEMG");
// Use calling the generic method 'compare' on both DNA and Protein
for (int i=0; i<list.size(); ++i)
if (list[i].compare("FOO", i, i+3))
print "Found FOO!\n";
}
Now, you probably noticed the magic list vector<Sequence>. This list is using the powerful concept of templates in C++ (inherited by Java recently). vector is an extremely generic list that can hold whatever you want due to the use of templates. This is the vector definition on GCC's implementation:
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
{
(...)
}
The keyword template means that you're constructing a generic object. The typename is what will later be changed to the type you're calling (in our case Sequence). The class vector as all other containers from STL have iterators (discussed above) and allocators (memory management algorithms), so by calling vector<Sequence> you're using all the default algorithms that fits on most cases pretty well.
A simpler example of templates will be the Summation class. Imagine you're writing a mathematical software and one of the algorithms you need to implement is a summation. Why write summations for integers, double, complex numbers if all of them are identical? Just write one template method that will accept any type and perform the same operation:
// My super-duper generic code
templace<typename type>
type Summation (vector<type> list) {
type sum = 0;
vector<type>::iterator it = list.begin();
while (it != list.end())
sum += (*it++);
return sum;
};
// Using
int main () {
vector<int> intList;
// Fill the list with lots of ints
int intSum = Summation(intList);
vector<double> doubleList;
// Fill the list with lots of doubles
double doubleSum = Summation(doubleList);
vector<complex> complexList;
// Fill the list with lots of complexs
complex complexSum = Summation(complexList);
vector<string> stringList;
// Fill the list with lots of strings
string stringSum = Summation(stringList);
}
Now, the Summation method can handle ALL types tested in main because we can apply the sum operation on all of them (including strings, where the strings are concatenated). As you can see the keyword type is used all over the generic method to define the return value, variables inside the method and even the type of the vector that will be iterated. This means that templates can contain templates and can also create other templates as well.
In this example, our generic code will produce four different results of four different types (three numerical sums and one very long string) and we did that with very little code. It could be even simpler and smaller but that's enough to demonstrate the true power of templates.
In C++, the Standard Template Library defines lots of containers (such as vector) with different behaviours, impose some restrictions (such as algorithm order and guarantees), all of that using templates so you can store in those containers everything that can be stored in memory. Also, because the containers have a standard behaviour (like iterators) you can use the same code on every container that have the same kind of iterator.
Therefore, no matter on which level, templates provide an excellent way of reducing code size, increasing readability and understandability of your code and gives you power to extend previously written software without modifications even if the new objects were never planned beforehand.
With time, anti-pattern became much more than design recipes, but a list of all bad practices in software development, from coding to managing teams, that would affect software quality. I'll tend to keep only in the code level, getting the most common mistakes specifically to bioinformatics area.
A system without any particular order or apparent design is a big ball of mud. Such systems behave randomly or in a non-trivial sequence and have different unpredicted results even for the same input. Structurally, the code is generally a big lump and often mixes scripting style with functional style and object orientation.
Normally the functions were originally helpers and were left floating in the code, the objects were mere structures to hold a bit of data (returned by functions, for instance) where you normally can access everything at any time and change whatever you want during the execution of the program.
Although scripting languages are far more common to show symptoms of muddiness, it's not uncommon to see C or Java programs as a big main function. the big ball of mud can be seen as the exact opposite of modularization and low-coupling.
Design patterns are recipes to follow, copy&paste programming is literally copying the solution and pasting somewhere else where you have a similar problem. It may seem right to “follow the same recipe” but the fact that you're not coding brings lots of problems including unused variables, adverse behaviours and internal structures not directly mapped.
Copy&paste programming is often done when you don't “have time” to code it properly and you have solved that problem already. In this case you can easily adapt the solution to the new reality provided you understand all the odds and ends (what's not necessarily true even for your own programs). But the real problem is when another programmer copy your program (or vice-versa). You can't possibly know all the ends and more specifically all the original coder's decisions and real problems.
Even worse cases will happen when you copy an external code and leave the company. The new developer won't know which was the original code, why you have copied, what was the original problem and what was yours. All information is lost in the copy&paste process, even if you document very well you won't be able to say everything, only what you think is worth saying.
Cowboy coding is very common in bioinformatics. It's when there is no formal definitions of what the program should do, how long will it take to finish, and which safeguards the programmer must take to ensure the minimum decent working conditions for the program, not to say software quality.
Cowboys code at will, at their own pace, in their own logic and expect the others to understand everything they're doing because they do understand. Eventually in the future they won't understand as well but then they'll just rewrite the program and call it a day, as many times as necessary.
Cowboy programming is usually a one-man-show problem and can be quite messy, but when this is encouraged within a team the chaos increases exponentially. Not always one rotten apple will rot the others (they would get rotten anyway) but one cowboy in a team can render all the other developers useless with time.
People are selfish, especially coders. When a programmer learn a new language or technique they tend to apply it to whatever problem that comes first in theirs hands. Sometimes the will is so big and the problem is so unrelated that horrible outcomes can come from this.
The golden hammer is exactly this new tool, which the developer will try desperately to fit wherever he can. The silver bullet is the next step. Whenever the developer has proven the new tool works for a limited problem set, he'll then induce that it also apply for any general problem and will use it.
It's easier to defer golden hammers than silver bullets, as for the later you need to go deeper in the model to prove how limited the solution is, and if you're unlucky, to every new problem that developer wants to use the new tool.
The main argument against design patterns is that you should implement the patterns as modules and interfaces rather than writing recipes and re-writing the same kind of code over and over, but that falls into the Golden Hammer anti-pattern as any pattern will be generic enough to be viable to all problems it solves unless it becomes heavy and slow to predict every single variation.
Hard-coding means writing the values in the code like:
sleep 1
instead of:
sleep secondsToSleep;
But the second example can be hard-coded as well if the secondsToSleep variable is hard-coded itself. Even if you include files containing variables that, at the end, is still hard-coded, it's bad. In scripts it's not so bad, as you can easily change and re-run the script but in compiled programs, for every minor change you have to re-compile the whole code again just to change the number of seconds to sleep.
Hard-coding has also another serious problem, you never know where to look for a certain value. When you're reading the code or fixing a bug and the hard-coded value is right there, it's all right (still bad, but easy to fix in that particular situation), but when you have to open several files just to find out its value it can become a nightmare.
Don't think that putting all values in one single file is the solution, you'll end up with several completely unrelated variables in the same place just for the sake of hard-coding. You must put everything in it's right place. Absolute numbers such as the speed of light in vacuum can even be pre-compiler constants (#define) but the number of seconds to wait for an answer must be in a configuration file that is read in runtime during start-up of the program.
As lava, it keeps going and destroying everything in its path and at the end, solidify and stays there forever. The lava flow is the bunch of unknown code that is carried out long after they stopped being useful just because no one knows what it does.
As stated before, this behaviour stimulates workarounds which stimulates even worse workarounds, just because no one knows exactly if they can remove it or not. After checking it's harmless and asking everyone in the team about it, the best you can do is to remove the unknown code and wait for someone (or some system) to complain. It may seem drastic and against software quality but sometimes such drastic measures are necessary to increase quality.
The other thing to do is to rewrite the whole thing, but remember, you'll introduce new problems as well.
Whenever you want to automate a small task you can create a shell script, even if you're only going to run it this time. It'll be much easier to write a script to call the procedure 10 times instead of calling it yourself and with copy&paste programming you can copy it 10 times and only change the file name (or whatever changes from one to the other).
This script will then stay with the data not in a proper code environment (revision control) but that's ok because you won't need it anymore, right? But as always happens we end up needing to run that once again, and again. The script will be maintained in place, without any reference from outside (that it exists), without any version or release control, and will probably become an important part of the production schedule quite likely ill documented in an email from one member of the team to the other.
As time goes by, new members come in, old go out and as they get used to run that script, no one will think to change it (it could have numerous side effects) and will become part of the team's legacy. Other procedures won't be able to be optimized because any change outside will break all magic buttons you have and you won't want to change them or, more likely, won't be able to in less than a month time.
Premature optimization is the root of all evil we all know that, so this is pretty much a straightforward case. It's quite common to think that optimizing is always important, no matter what you do but early optimizations can lead to serious architecture lock-ups in the future.
The rule of thumb is: stick to standards, optimize the standard if you have performance problems and only if you still have problems, try another standard or do it yourself(TM).
Some call it reinventing the wheel to refer to re-creating code that works but didn't need to be written and reinventing the square wheel to codes that don't work quite well, but to reinvent the broken wheel means that not only the code works poorly but it's a horrible code with lots of bad practices.
It's the sum of all anti-patterns, that's going to some direction that is bad as principle, that anyone knows it's bad, you know the consequences but you still go because its easier or “everyone went that way”. My mum use to ask me: “If he jumps from the bridge, would you go too?” and that question keeps flashing in my head every time I see someone reinventing the broken wheel.