The Software Purist |

CAT | Programming

Dec/15

21

Binary Search Part II

A while back (read: years ago), I wrote this post: Software Purist – Binary Search. It wound up being an exercise in algorithm design, along with some interesting points I made about the 80/20 principle and testing. Without looking at what I had done previously, I decided to try to write binary search again. Here’s what I came up with. You should note that this example will use C++11. Here’s the code:

#include <array>
#include <cassert>

using namespace std;

template<class T, class... Tail>
auto make_array(T head, Tail... tail)
  -> std::array<T, 1 + sizeof...(Tail)>
{
	std::array<T, 1 + sizeof...(Tail)> a = { head, tail ... };
	return a;
}

template <class TContainer>
int binarySearch(const TContainer& container,
                 const typename TContainer::value_type& val)
{	
	auto oldBegin = -1;
	auto oldEnd = -1;
	auto begin = 0;
	auto end = container.size() - 1;

	while ((oldBegin != begin || oldEnd != end) && (begin <= end))
	{
		oldBegin = begin;
		oldEnd = end;

 		const auto half = (end - begin + 1) / 2 + begin;
		
		if (container[half] == val)
		{
			return half;
		}
		else if (container[half] < val)
		{
			begin = half + 1;
		}
		else if (container[half] > val)
		{
			end = half - 1;
		}
	}

	return -1;
}

int main()
{
	auto x = make_array(1, 2, 5, 9, 13, 18, 72, 1385);

	assert(binarySearch(x, 0) == -1);
	assert(binarySearch(x, 1) == 0);
	assert(binarySearch(x, 2) == 1);
	assert(binarySearch(x, 3) == -1);
	assert(binarySearch(x, 5) == 2);
	assert(binarySearch(x, 8) == -1);
	assert(binarySearch(x, 9) == 3);
	assert(binarySearch(x, 12) == -1);
	assert(binarySearch(x, 13) == 4);
	assert(binarySearch(x, 15) == -1);
	assert(binarySearch(x, 18) == 5);
	assert(binarySearch(x, 36) == -1);
	assert(binarySearch(x, 72) == 6);
	assert(binarySearch(x, 1000) == -1);
	assert(binarySearch(x, 1385) == 7);
	assert(binarySearch(x, numeric_limits<int>::min()) == -1);
	assert(binarySearch(x, numeric_limits<int>::max()) == -1);
}

It took me a few tries to make it work flawlessly on paper. However, I noticed my test cases were more robust. Obviously, the use of C++11 clouds the issue slightly, as well. I also noted I’m more willing to use int as a data-type now and more likely to use automatic-typing. I’m sure this is due to the influence of other programming languages, like C# and Python. In comparing to the previous, I also noticed better naming, using half rather than newIndex. But, the most striking thing was the fact that my solution was actually different than the previous solution. It encapsulated the same idea, and it’s similar, but not exact. Both solutions work. It’s interesting to see how one’s programming-style evolves ever so slightly (or significantly) over time. It would be hard to say one solution is better than the other.

Going back to the original thought, I still find it amazing that only 10% of programmers get this right. But, as I tried it out on paper, it definitely took me a few goes through my test cases to get it quite right. So, maybe it’s not so far fetched. I think what this is really saying is that 90% of programmers don’t put enough time into unit testing and their test cases. So, let’s discuss that a bit more.

My test cases in this example encompassed all of the following:

  • All values in the array
  • Values not in the array
  • Values not in the array between values that were in the array
  • Negative values
  • Very negative values (checking for underflow)
  • Very large values (checking for overflow)
  • Values less than the minimum value in the array
  • Values larger than the maximum value in the array
  • Zero

If you look at the above, that’s a pretty robust way to approach boundary testing and I encourage you to do the same (where feasible). All of the above can be sources of errors. Also note that sometimes a test case covers multiple conditions, which is great. Just make sure you have a sufficient amount of test cases, to be confident. And then, of course, automate. Normally, one would use a unit test framework, but I wanted to make the code simple enough to run on modern compilers with no additional libraries.

· · ·

Mar/13

20

Dangerous Memory Leak in TR1 shared_ptr class

I encountered a major/dangerous memory leak using std::tr1::shared_ptr. There is an edge case which will not delete the memory nor call the destructors. I’ll demonstrate:

Assume MessageFactory::GetMessage() returns a raw pointer of type IMessage for illustration purposes.


#include "IMessage.h"

...

for (size_t index = 0; index < 100; ++index) { std::tr1::shared_ptr pMessage(MessageFactory::GetMessage());
MessageFactory::ProcessMessage(pMessage.get());
}

This deletes the memory just fine. However, note that this block of code is actually not calling any members, so a forward declaration could also be used. So, instead:


class IMessage;

...

for (size_t index = 0; index < 100; ++index) { std::tr1::shared_ptr pMessage(MessageFactory::GetMessage());
MessageFactory::ProcessMessage(pMessage.get());
}

It actually does not have a definition for the destructor here, so it appears to simply skip over it altogether, and with it, it doesn’t call the destructors of the member variables, thus initiating a chain of some very dangerous leaks.

Conversely, in this same example, if we use boost::shared_ptr instead, it knows it won’t be able to call the destructor, so it fails to compile:


class IMessage;

...

for (size_t index = 0; index < 100; ++index) { boost::shared_ptr pMessage(MessageFactory::GetMessage());
MessageFactory::ProcessMessage(pMessage.get());
}


Error 1 error C2027: use of undefined type 'IMessage' c:\dev\common\3rdparty\boost_1_49_0\boost\checked_delete.hpp 32 SharedPtrLeakTest
Error 2 error C2118: negative subscript c:\dev\common\3rdparty\boost_1_49_0\boost\checked_delete.hpp 32 SharedPtrLeakTest

The ideal solution in this case would’ve been boost::scoped_ptr, which produces the same error messages.

Conclusion: We should not use std::tr1::shared_ptr, as the Microsoft implementation appears to be broken. It should not allow compilation for this invalid case. Please use the boost smart pointers (shared_ptr, scoped_ptr, shared_array, scoped_array, weak_ptr) until further notice instead of std::tr1::shared_ptr.

No tags

Jun/11

19

Conditional Compilation in Java

I wanted to share a trick I learned a while back, that is pretty useful. Personally, I’m not a fan of including code in your executable/bytecode that is never used, because it has the risk of exposing additional implementation, and generally makes for larger DLLs/Jars. One nice thing I can say about C# is that they did not completely remove the idea of conditional compilation. In C#, you can do the following:


#define LETS_DANCE

...

#if LETS_DANCE
// ... do something ...
#endif

However, C#’s conditional compilation is completely restricted to only being able to define a boolean, where the existence of the preprocessor symbol means it exists, and otherwise, it doesn’t. Makes sense. Conditional compilation without all the nasty misuses of them you see in C++ programs. Seems to be the best of both worlds and an obvious leg up on Java, right?

Well, actually not really. Turns out that Java has supported something similar since day one, also. In Java, the equivalent is this:


public static final LETS_DANCE = false;

...

if (LETS_DANCE)
{
// ... do something ...
}
#endif

Why is this guaranteed to work and not include the unreachable code? Turns out there is an important note in Java. Java will not output code that is obviously unreachable. To be obviously unreachable it needs to be known at compile time as a static final constant variable. So, there you go. Definitely a useful thing.

· ·

Dynamic is a new keyword that was introduced in C# 4.0. Thankfully, it hasn’t gotten a ton of press, but I can see it paving the way for all sorts of new types of abuse. By now, you’re probably familiar with my thoughts on the var keyword. Dynamic takes this one step further, by dynamically binding the class type at runtime, and determining if method calls are legal, also at runtime. Here’s an example:


public void MyMethod(dynamic param)
{
param.Call();
}

So, let’s say you pass in an instance of a class which has the method named Call. All is well, Call() will be called, albeit with a performance penalty.

Now, consider what happens if you pass in an instance of a class for which Call() doesn’t exist. It will, instead, throw an exception, which essentially states that Call() doesn’t exist for this type.

So, what’s the problem? Very simple. You’re taking a situation where you can enlist the compiler’s help, and instead pushing it off to runtime, which entails discovering it later than necessary, in some cases, much later. This increases risk and potentially increases the time to fix, since we know that at each stage later that a bug is discovered, the more expensive it is to fix. Problem 2 is that there is absolutely a performance penalty. In a lot of cases, these penalties are no so noticeable, but spread out through an entire application, they can make a serious impact. I have seen poorly written C# applications which made both heavy and improper usage of reflection that easily can operate an order of magnitude slower than well-written one which takes advantage of the type system.

Avoid dynamic in most cases. Use it for cases where it really matters. If you find yourself needing a lot of dynamic behavior, you are more well-suited to using a scripting language like Python or Ruby, where the syntax will be much cleaner and you don’t risk so much paradigm mix, therefore creating more understandable code. Otherwise, if you’re determined to use C#, then use it as the type-safe language that it can be, and don’t treat the type-system as optional, even if Microsoft got overzealous in feature overload.

What’s the solution? Instead, make the method look like this:


public interface ICall
{
void Call();
}

public void MyMethod(ICall param)
{
param.Call();
}

Using generics is also a possible solution. Just remember that when you violate the type system, you are losing the advantages of using a type-safe language.

No tags

Jan/11

24

Var/Auto is Ugly and in Some Cases, Downright Evil.

In this post, I’m going to describe a set of keywords, which effectively serve the same purpose. In C#, there is the var keyword. In C++, there is the auto keyword. Effectively, what they let you do is to automatically inter the type of a variable from the context on the right hand side. Here’s an example, in C#:


var myVar = new MyClass();

and an example in C++:


auto myVar = MyClass();

The problem I have is, while this allows you a tremendous amount of flexibility, in saving redundant typing, it also potentially nullifies some of the benefits of using a language which supports type safety, because you can do some pretty nasty things which destroy the readability and can potentially introduce some subtle bugs. Worse still, tools like Resharper encourage, potentially poor usages of var. Here’s another example of the var problem:


var myVar = new MyClass().DoThis().DoThat().DoSomethingElse().NowGet();

Ok, what’s the type? Don’t know? Me neither. I find this problematic. As such, as I’d like to establish some guidelines for better usage of var/auto, taking some common use cases. I’ll probably switch back and forth with examples from C++ and C#, just to illustrate the point. Here we go:

1) Usage case 1:


var x = new Y();

I consider this usage a minor evil, even though some like it a lot. Here’s my major problem: You have type inference on the wrong side. The point of using a language which supports type safety, is, well, you support the type system and let it help you. If you don’t want that, may I suggest a language that is dynamically typed? It would be nice, if var, instead worked this way:


Y x = new infer-this-type();

As a general rule, we would prefer to infer the type that’s on the right hand side, not the left. This feature is not available in a lot of languages, so for now, I would simply suggest not using var. Go with the old:


Y x = new Y();

2) Usage case 2:


var x = GetY();

Again, with this one, I prefer not to use var, for the same reason as before, with an added caveat. First, of all, you should avoid using var to avoid typing a simple type. Secondly, you can’t even figure out what the type is from reading the code. Not good. On a scale of 1 to evil, I consider this a significant evil.

3) Usage case 3:


for (typename std::vector::const_iterator iter = container.begin(); iter != container.end(); ++iter)
{
...
}

Becomes:


for (auto iter = container.begin(); iter != container.end(); ++iter)
{
...
}

In this case, I can justify using var/auto, so I consider using auto a minor evil. However, C++ has a better mechanism for doing this. It’s called typedef. For example:


typedef typename std::vector::const_iterator MyIter;

for (MyIter iter = container.begin(); iter != container.end(); ++iter)
{
...
}

So, in C++, I have trouble finding ANY usage, where I really like auto. However, in C#, there is no typedef, so I’m fine with usage of var, in the case of complicated nested classes.

Conclusion

Concluding, as you figured, I don’t like the usage of var or auto much. In a lot of cases, it is a minor evil. However, there are some major concerns: Readability and subverting some of the redundant checking that the type system supports. In C#, it is sometimes useful to save a lot of typing, due to the lack of the typedef keyword, while in C++, it is rarely useful. In a future article, I will tackle C#’s dynamic keyword, which I dislike far more than var. Stay tuned.

· · · ·

I was interviewing a candidate recently, and we were talking about some of the programming languages he claimed to know, which was mainly focused around C++ and C#. We started to discuss some of the types of problems he finds easier to solve in each when he said something I found very misleading: “A programming language is really just syntax”. As we talked more, I started to ponder what a shallow understanding of a language this really was. It’s kind of like questioning whether a dollar is a dollar is a dollar. Smart financial people know that the source of the dollar is very important, and so the utter simplification is misleading.

Before I get too far into this, I will note that if you’re using .Net, you can get a lot closer to making the premise of the initial argument, because the .Net languages all can support the same APIs. That wasn’t the case for this individual, as he was using C++, not C++/CLI. With that being said, let’s get into some of the real substantial differences:

1) The standard libraries that the language supports. I find this to be one of the most underrated aspects of working with a language. I think part of the reason is that when you use some languages (C++) there’s a large population of programmers who don’t really make good use of the standard libraries. In my experience, this is often because they sometimes fall into using non-portable APIs, such as Microsoft’s ATL or MFC instead of STL containers, or libraries that may be considered more suitable for an embedded environment. Anyway, I think this is a critical feature, because, again consider the example of C++: Something as commonly used as XML is not standard. This is almost unfathomable for programmers of languages like Java or C#. Meanwhile, the flipside is .Net, which is immense and becomes very difficult for a developer to be proficient in all of it.

2) Third party libraries the language supports. I would consider this almost as important as the standard libraries issue. Unlike the standard libraries, there’s a much better chance that the third party libraries have API interfaces to be used in multiple languages. This will be one of the the top things you would consider when choosing the appropriate language for a task.

3) Language Paradigms: This is another feature which gets underrated at times. Does the language properly support Object-Oriented Programming? Template Meta-Programming? Functional? How easily does it support multi-threading? Again, all of these are critical differences between languages which go well beyond syntax.

4) Static Typing or Dynamic Typing or Both (coughC#cough)? With static typing, you can potentially find a lot of structural errors during compile time and need less code coverage during your unit tests. With dynamic typing, you don’t have these luxuries, but have much better support for rapid development.

5) The tools that are supported for your language.

6) Syntax. I consider this one of the least important differences between languages. It’s very easy for a professional programmer to adjust to a new syntax, assuming it isn’t completely nonsensical.

In the end, I think of this like deciphering any sort of spoken or written language. At the end of the day, if you aren’t able to communicate effectively, then your words are meaningless. This goes far beyond sentence structure. When discussing programming languages, it goes far beyond syntax.

· · · · · · · · ·

May/10

12

Binary Searches and the 80/20 Principle

I recently came across this post: http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/ . I thought this was a very interesting topic, not because a binary search is a particularly interesting algorithm, but because of the realization that only 10% of programmers could get this right on the first try. To test, I did it myself, on paper. I was able to work it out on paper before officially testing it, but I can also see how most people can miss it. It appears to work, according to my tests. Here’s the solution I came up with:

template <class TCollection>
size_t binarySearch(const TCollection& p_collection, const typename TCollection::value_type& p_value)
{
	size_t oldMax = p_collection.size() - 1;
	size_t oldMin = 0;
	size_t newIndex = (oldMax + oldMin) / 2;

	while (oldMin != oldMax)
	{
		if (p_collection[newIndex] > p_value)
		{
			if (oldMax == newIndex)
			{
				break;
			} // end if

			oldMax = newIndex;
			newIndex = (oldMax + oldMin) / 2;
		}
		else if (p_collection[newIndex] < p_value)
		{
			if (oldMin == newIndex)
			{
				break;
			} // end if

			oldMin = newIndex;
			newIndex = (oldMax + oldMin + 1) / 2;
		}
		else
		{
			return newIndex;
		} // end if
	} // end while

	return size_t(-1);
} // end binarySearch

void test()
{
	std::vector<int> collection;
	collection.push_back(1);
	collection.push_back(2);
	collection.push_back(3);
	collection.push_back(5);
	collection.push_back(6);
	collection.push_back(7);
	collection.push_back(9);
	collection.push_back(10);

	assert(binarySearch(collection, 0) == size_t(-1));
	assert(binarySearch(collection, 1) == 0);
	assert(binarySearch(collection, 2) == 1);
	assert(binarySearch(collection, 3) == 2);
	assert(binarySearch(collection, 4) == size_t(-1));
	assert(binarySearch(collection, 5) == 3);
	assert(binarySearch(collection, 6) == 4);
	assert(binarySearch(collection, 7) == 5);
	assert(binarySearch(collection, 8 ) == size_t(-1));
	assert(binarySearch(collection, 9) == 6);
	assert(binarySearch(collection, 10) == 7);
	assert(binarySearch(collection, 11) == size_t(-1));
} // end test

It’s easy to miss it, because there are edge cases, a truncation problem, and multiple termination conditions. I only discovered these cases when I worked through a very small sample set in my head. What worried me about the initial find is that I wasn’t shocked by the result of only 10% of developers getting this right. I think what’s concerning to me is that many people wouldn’t have tested it in isolation, just felt that they had a solution that worked, and moved on. But, then I can’t blame developers for this. I think this is the fault of working in an industry where being thorough isn’t as rewarded as it should be.

The more I work, the more I notice this problem. There is so much focus on short-term goals and results, that it’s easy to cut corners. “You need to finish feature X by COB today.” Well, in order to accomplish this, I notice most people will skip otherwise essential things such as unit testing, and sometimes not even test at all. The design phase is also often skipped, perhaps even more often than testing. When you’re given ambitious or impossible deadlines, it’s natural to skip designing and start coding right away. Worse is that if you do spend time designing and testing the software, you often aren’t rewarded for your efforts; Nobody notices.

Ultimately, what I’m noticing is that a lot of developers remove as much as 50% of the engineering effort, for 80% of the result. While maybe not the 80/20 principle, it’s close enough to feel like it. The problem is that I don’t believe software can follow the 80/20 principle and be effective. That loss of 20% is a lot of bugs… many relatively benign, but I also feel like that remaining 20% also encompasses most of the difficult to reproduce bugs; The bugs we are forced to write off and sometimes never successfully fix. At best, we pull out a roll of duct tape, use enough tape to keep it stable enough to hold together, hoping nobody notices.

As a developer, I can fully admit that when I’ve been pressed with unreasonable schedules, I’ve occasionally responded by cutting corners, just like most people would have handled it. This rarely resulted in a better product. It’s also almost impossible to later go back and rework the foundation when the tower is in danger of toppling over. In other industries, proceeding in this manner would be seen as ludicrous, but in software, it’s accepted. But, it’s unfair to blame developers for this; I blame short-sighted business models and managers who focus mostly on CYOA.

Anyway, coming full circle, I wouldn’t be surprised if there’s a search algorithm in your code base that doesn’t quite work for all cases. If you find a broken search in your code base, let me know and maybe I’ll even post your findings on this website.

· · · · · ·

Dec/09

11

Logging in C++

Hi all. In this edition, I want to discuss a C++ logging system a little bit. I’ve been through the process of developing loggers many times in my career. Each time they get iteratively better, and so I feel this would be an interesting topic to discuss. Now, of course, you could just use a logger from an already existing library, but then there would be no point in this article. So, let’s play along for my sake. 😉

First Approach

Now, obviously, the first thing a logger should do is… log!  So, a basic first step might have our logger looking like this:

class Logger
{
public:
	void log(const std::string& p_output)
	{
		file_ << p_output;
	}
};

Logger& operator<<(Logger& p_logger, const std::string& p_output)
{
	p_logger.log(p_output);
	return p_logger;
}

Simple enough, and effective. However, there are obviously some improvements we could make:

  1. Logging of additional information: file, method name, line.
  2. Scoped logging.
  3. Conditional logging. The point of this would be to log only if a message is important enough to log.
  4. Effect on application performance. Asynchronous logging.
  5. Registering different output sources (Difficulty: Intermediate-Hard. Mostly because it hits up a part of the standard most people avoid. Unfortunately, out of the scope of this article, but can write a follow-up if there’s interest.)

Logging of Additional Information

It’s always very helpful if we can get more information when we’re logging. A log message by itself is often useless, since it may have been called from a variety of different points or the message may be repeated. By providing the right information in the right places, we can help alleviate the first issue and remove any doubt for the second. By putting logging in areas of interest, you might have 5 log messages, which happen to precede the call location where the error message you’re really interested is occurring. Of course, a full stack trace in C++ is more effective, but this, while doable, is way beyond the scope of this article.

The output method might be changed to this:

class Logger
{
public:
	void log(const char* p_pFile, const char* p_pMethod, 
		size_t p_line, const std::string& p_output)
	{
		file_ << p_pFile << ":" << p_pMethod << ":" << p_line << ": " << p_output;
	}
};

// Called like this:
logger.log(__FILE__, __FUNCTION__, __LINE__, ... msg ... );

This is certainly starting to get a bit verbose, but you could potentially cover this with a macro, if i’s a win in this case. Unfortunately, operator<< is eliminated, but there is potential trickery you could get to reuse the solution, but it’s probably fine to not have it in this case. Besides, log() is more readable than << for C++ newbies.

Scoped Logging

This is my favorite and most important feature for any logging system. In C++, it’s useful to log not only when logging of a scope started, but also when it ended. If you can scope the log calls, then information will be shared between the constructor and destructor of this auto log object and the destructor is guaranteed to be called. Here’s an example:

class AutoLogger
{
public:
	AutoLogger(Logger& p_.logger, const char* p_file,
		const char* p_function, size_t p_line, const std::string& p_msg) :
		logger_(p_logger), file_(p_file), function_(p_function),
		line_(p_line), msg_(p_msg)
	{
		logger_.log(file_, function_, line_, msg_);
	}

	~AutoLogger()
	{
		logger_.log(file_, function_, line_, msg_);
	}
};

AutoLogger autoLog(logger, __FILE__, __FUNCTION__, __LINE__, ... msg ...);

... do stuff ...

// destructor automatically called, so it logs at exiting the scope.

This has a lot of benefits. The main thing is the guaranteed and saved typing for executing potentially the same conditions. You also potentially gain the ability to have the scoped version log additional information, such as time deltas, memory deltas, etc… this can even be a weak form of profiling.

Conditional Logging

You could add an optional log type which is a conditional. When provided, it will check the logger’s conditional and see if it’s allowed. If not, it won’t log. This is purely  meant as an efficiency, and preventing log files from getting ridiculously large, while keeping old log messages in tact and not having to change otherwise working code. As an example:

class Logger
{
public:
	void log(const char* p_pFile, const char* p_pMethod, size_t p_line,
		LogCondition p_logCondition, const std::string& p_output)
	{
		if (p_logCondition is allowed)
		{
			file_ << p_pFile << ":" << p_pMethod <<
				":" << p_line << ": " << p_output;
		}
	}
};

// Called like this:
// The following line gets logged
logger.log(__FILE__, __FUNCTION__, __LINE__, MUST_LOG, ... msg ... );

// This one, however, is not logged
logger.log(__FILE__, __FUNCTION__, __LINE__, TRIVIAL, ... msg ... );

Conditional logging holds the advantages that I mentioned above and is very easy to create. Just fill in with the types you need. In this case, I mentioned MUST_LOG and TRIVIAL.

Asynchronous Logging

Now, if we implement what we’ve gone through so far, we’ve got a decent logging system. Unfortunately, put enough logging in place, and your application is slowed down to the speed of the hard disk, at best. This is absolutely unacceptable, of course. So, the obvious solution is to create a thread or pool of threads to handle disk writes to the system. When you make a log call, it actually pushes the “request” on the queue and then allows the logging system to take care of the request when it is free. This prevents your application being slowed down due to logging (if done with care).   Without this, any multithread application would become a single-threaded application which is basically synchronized on files. Now, at this point, you’re probably thinking that we’ve fixed the last major issue. Almost…

Maximum Queue Size

This hit me once when working on a server application. Basically, the story behind it is you almost always won’t be logging a ton of information in your regular application. You only start logging at key points and if things are starting to look “fishy” (e.g.: unexpected value in method Blah::Blah2()). However, on a server application, things scale quickly with load and then are limited based on hardware. Ultimately, a load test with 2000 simulated users worked in a testing environment. However, at around 800 users in a live environment, we started to hit what appeared to be increasing memory leaks, which is never good. To make a long story short, it turned out that the live system was using RAID and the testing environment wasn’t. So, because the hard disk was considerably slower, it hit hard disk write limits much quicker. This issue was easily corrected by providing a maximum queue size. If you’re queueing, say, 10k messages, you then hit a decision path for how you’d like to handle: toss away messages until the queue shrinks to say, 8k, or start having the logger sync with the app. The first solution is easier to code, so we went with that one.

Ultimately, this article discussed writing a basic logger from scratch with example code. Hopefully you found it useful.

· · ·

Dec/09

10

Inheritance vs. Composition

If you’re familiar with Object-Oriented programming, and potentially, UML, these terms may be familiar to you. If not, I will present them below.

Inheritance is a relationship between two classes, where there is a parent-child relationship, in the sense that the parent appears higher on the tree than the children and a parent may have multiple children. However, the relationship follows than the children inherit all the parent’s state and behavior and may also additionally add their own. I’ll demonstrate an example with UML, done with SmartDraw, and some pseudo-code:

class Shape
{
public:
	virtual void draw() = 0;
};

class Circle : public Shape
{
public:
	Circle(const Pos2f& p_pos, float p_radius) :
		pos_(p_pos), radius_(p_radius)
	{
	}

	virtual void draw()
	{
		// perform draw operation based on position and radius
	}

private:
	Pos2f pos_;
	float radius_;
};

class Square : public Shape
{
public:
	Square(const Pos2f& p_topLeftPos, const Dim2f& p_dimensions) :
		topLeftPos_(p_topLeftPos), dimensions_(p_dimensions)
	{
	}

	virtual void draw()
	{
		// perform draw operation based on top-left position, width and height
	}

private:
	Pos2f topLeftPos_;
	Dim2f dimensions_;
};

This relationship makes sense as a class hierarchy because there’s a simple guideline to determine whether a class should be inherited from another. If you can justify that a class “is-a” more specific type of another type, then semantically, it makes sense to inherit, if not it doesn’t. Applying it to this case, a Circle is-a type of Shape. A Square is-a type of Shape. So, therefore, inheritance is appropriate.

This brings up the question, what do we do when inheritance isn’t appropriate? There is also object composition. Object composition basically means that a type or class is “composed” of other types or classes. If you make use of object composition it looks more like this:

Here’s the UML diagram, done with SmartDraw:

class Duck
{
public:
	void quack()
	{
		// logic to quack
	}

	void fly()
	{
		// logic to fly
	}

private:
	Bill duckBill_;
	std::vector<Feather> feathers_;
};

class Bill
{
...
};

class Feather
{
...
};

class Pond
{
...

private:
   Duck* pDuck_;
};

This example demonstrates what it might look like for code that involves a Duck. A duck has-a bill, and has-some feathers. When a relationship between two classes is a has-a relationship, then you should use composition. There are two types of composition, which are demonstrated in the code and diagram above. The more general form of composition implies full ownership, including responsibility for an object’s lifetime. This is true for the bill of a duck and its feathers, for without a instance of a duck object, neither the feathers nor bill exist. (Side note: This is assuming we can’t pluck the feathers of the duck or remove its bill, which would get into a concept called Transfer of Ownership, but that is beyond the scope of this article.) The second type of composition is called aggregation, which implies that while an object has another object, it doesn’t own it. In the example I showed above, the Pond has this sort of relationship with the Duck. An instance of a Pond object may keep a reference (or pointer) to the Duck object while the Duck is in the Pond, but isn’t responsible for managing the lifetime of the Duck object, so it is a aggregation relationship.

Now that I’ve clarified inheritance vs. composition a bit, it brings up some additional questions. In the case of the Duck, a common design problem I’ve seen before is that in the case of a one-to-one relationship, like there is between the Duck and the Bill, you could theoretically derive Duck from the Bill class. The argument I’ve heard is, “This violates the is-a rule, but really what is the big deal? I was going to promote the methods of Bill to be public on Duck anyway? This saves typing.” The problem is semantic understanding. This type of inheritance is generally meant to be a polymorphic relationship. Polymorphism requires a is-a relationship to make sense. Now, there are cases where it makes sense to inherit when there isn’t a is-a relationship, but generally you should avoid it, when it’s obviously wrong. A codebase that violates is-a/has-a rules is much more difficult to understand than one that follows it. Ultimately, it just flows more naturally, and you wind up avoiding some dead ends that code that violates this runs into.

In a future article I will discuss some of the more grey area cases. Hopefully, you found this to be a good introduction.

· · · · · · · · ·

So, one thing you might be wondering is why I titled my blog,The Software Purist. One friend even surmised that it had to do with some clensing program where I would annihilate all the impure programmers. While a humorous suggestion, it wasn’t what I was aiming for. 😉  The long and short of it is that at a previous job, two different managers used to refer to me as a C++ purist, for my take on approaching tackling issues when programming in the C++ language. It was generally meant more as a compliment, because I believe they respected me “sticking to my guns”, so to speak. My general mentality at the time is that all problems can be solved by using well-defined methods, best practices and always maintaining a preference for anything standard or that has the possibility of becoming standard in the future (such as some of the Boost libraries). So, if there was an approach, my general methodology was a question of, “How would Scott Meyers solve this problem?” It’s difficult to get more pure than following Scott Meyer’s advice in Effective C++, at least at the time.

Now that we’ve been through that intro, perhaps some definitions, from my perspective would be useful. There’s two camps of extremes in software development. First, there’s the purists. Purism is about following language standards, following best practices, avoiding legacy features, ignoring language loopholes and using the language as intended by its authors. For example, a purist, in C++, might completely avoid and ignore C++ macros, except when necessary for things, such as header guards. A C++ purist might also prefer to use std::copy instead of memcpy, even if either solution would work, performance was equal, but memcpy is outdated. A C++ purist would use std::string instead of MFC’s CString or Qt’s QString. I know, because I did this and generally stick to this advice, unless it gets in the way.

Pragmatism is exactly the opposite. Pragmatism dictates that the most important thing is getting the job done. If you’re a pragmatist, your goal is generally to get the product out the door. So, if macros streamline your process and make it quicker to code something, this is more important than following a set of recommendations, because you can get your product out the door faster. Likewise, memcpy is a few characters less typing than std::copy and you’re more used to it, so you use it over std::copy, even though iterators are considered “safer” than pointers. Finally, you might use CString, because it gives you direct access to the internal memory, so you don’t have to wrestle through an abstraction and you can use a C-style API if you choose.

Now, these are all fair and valid views. Yes, that’s right. Both views are fair, both are valid. Both are also extreme. We know from many aspects of life, that extremes are generally bad. A temperature of too hot or too cold is uncomfortable. Driving at a speed of too fast or too slow is uncomfortable. And so on… The same holds true for software.  Ultimately, we all evolve as developers. I have a theory that many developers start out as purists and start to migrate towards gaining more pragmatism each year, once they become more seasoned with more business experience. Anyway, as most developers know, it can be a problem to be either too pure or too close to pragmatism.

If you’re too pure, you will probably think every pragmatist’s code is terrible, even to the point of saying that they’re “under-engineering”. I know, because I was there, a long time ago. In some situations, what’s called for is simply getting the job done. Businesses have a need to have a product ship and a product that doesn’t ship is a failure, even if the code was beautiful. Purism often has a large focus on long term goals, which is definitely beneficial. The secret knowledge that purists don’t want to let out is by following purist methodology: 1) The coding becomes very mechanical and repetetive, which is great for developing, because if you can reuse patterns of development, it gets easier and becomes more natural each time. 2) The purist has a keen sense and sensitivity to maintaining the code later and they know if they take a shortcut now, they will be grunting and groaning when they have to look at it later. The truth is that these are really valid points, and in a lot of situations, this is the right approach. Of course, there’s some items that have to be compromised in the name of getting things done. On the flip side…

If you’re too pragmatic, you will probably think every purist is overengineering. Why build a packet class for every packet to the server? You can more easily code it inline, in one large source file, right? The problem with this approach is when you need to maintain it later, such as putting it in a test harness, all of this hardcoded logic becomes a mess to fit in. It’s difficult to extract the 80 out of 200 lines of a large function that you actually want to test, while stubbing out the other 120 — this necessitates refactoring. Both extremes find that refactoring is time consuming. Extreme purists find that in reality, it’s difficult to find time to refactor, so they try to code in such a way to avoid this step. Extreme pragmatists find that it’s difficult to find time to ever refactor, so they just never bother with it and the code is messy forever. Refactoring is one of those concepts that works is good in practice, but unless you get everyone to buy in, it doesn’t happen. Extreme pragmatists often don’t buy into refactoring; they got used to the mess, and have developed a mental map of the shortcuts, so they can often work effectively, despite the challenges. Extreme pragmatism creates a potentially difficult work environment for coworkers when done to extremes, because it becomes a mind field for the uninformed to trip over.

Ultimately, as we know, any sort of extremist views should generally be avoided. There is never always a single answer to any problem. Development has to be done with care and the beauty of the code is imoprtant. However, don’t lose sight of actually shipping the product. There must be a balance. If you feel like you are in the middle and you are accused of either overengineering or underengineering, it’s very possible that the person you’re talking to is an extremist. As for The Software Purist, my general approach now is to stay somewhere in between, but I still lean a bit towards the purist side, because ultimately, I have a high appreciation for the beauty of code.

· · · · · · · · · · · ·

Older posts >>

Theme Design by devolux.nh2.me