A potpourri on static vs dynamic

Static typing is great for more reasons that checking that the program doesn't do (too) crazy things at run-time. On the other hand, dynamic typing let's you (the programmer) do a lot of crazy things that you know will be correct.

The problem with dynamic typing starts popping up as the project grows. This is when static typing starts to be useful, because the compiler keeps you from doing type-unsafe tricks and other black magic.

However, there will always be things -- even in multi-million line projects -- that you brain easily can type-check, but the compiler can't. For instance, interactions between functions within a class or a small source file.

Gradual typing is a typing strategy that might solve such problems.

With gradual typing you can (manually) infer more and more types as the project evolves and more performance, compiler-checked interfaces, etc, is needed.

I find function annotations in python a very interesting start for something that could let python grow into a type-checked language. I've fiddled around with this idea before, however, I'm not skilled enough, nor do I have time enough, to develop a compiler for a full-fledge "static python" language.

Personally I find the research done in the type-checking field very interesting, and even though I'm not formally trained I have played around with different type-checking ideas. One was based on the idea that abstract types are simply a group of concrete types with a common set of behavior; another was an attempt on doing duck-typing at compile-time and inferring interfaces (Java sense of the word).

Compile-time evaluation is another concept that are (distantly) related to static typing that I'm a bit fan of. In a language that have compile-time evaluation, it is possible to for instance generate classes, populate data structures, etc, that will appear to the compiler to be equivalent to manually written classes and data structures.

There are a lot of things to say about gradually moving type-checking to compile-time and execute code at compile-time, but I'll try to end here with the following, slightly confusing, note.

Typing is a fuzzy concept in the sense that static and dynamic all depends on you point of view. If you implement a compiler A that have compile-time evaluation, then you need to implement an dynamically type-checking interpreter which evaluates the code at compile-time (unless, of course, you write a compiler for it... ehm, wait... omg, recursion!). On the other hand, if your writing a just-in-time compiler B you're writing a compiler for the compiler is run at run-time -- if such compiler do typing, is it really static-typing? Is it dynamic typing? I don't know... Making it even more convoluted -- what if compiler A is used as a just-in-time compiler by a virtual machine for a script language -- is it still static-typing?

As always, the world is neither white nor black. In fact, it's not even gray -- it is in some quantum state, being white and black at the same time.

Test the source code, not the assembly

Unit tests are great. Integration tests are great. Regression tests are great. User tests are great. The problem with these kinds of test is that they test the compiled source code -- the assembly -- not the source code itself.

Why is this a problem, you ask? The problem is that the source code, which (should) communicates intention to other programmers is not tested. This aspect of the source code is not tested. It is very hard to test this aspect, though. The only way I know of is Checkstyle (and similar lint tools), and code reviews. The former has the advantage of being possible to automate, the latter has the advantage of being correct (which the former is not :)).

I use correct here in the sense that it actually reflect the opinions of by the target audience -- the programmer. The primary user of source code is the programmer, not the computer. The primary user of the compiled code is the computer (which doesn't have strongs opinions on how structure of the code should by, by the way).

The idea I'm trying to express here is that source code can be functionally perfect in the sense that millions and millions of testcases verify every tiny aspect of the code. Yet the source code will fail miserably on a core review. Testing is not enough if the source code is supposed to live for long.

Is code review the only tool for making sure that source code does not degenerate into a huge ball of spaghetti/mud mixture? Refactoring is often mentioned in discussions like this. However, in my mind this is is a tool for un-mudding the ball into something nicer. It is not a tool for identifying what to refactor.

It kind of sucks, because core review are boring like hell, but what other solution is there to this problem? I would be happy to know of any other than code reviews.

RIP C and LISP

Two very influential profiles in the computer science community and in software engineering has passed away.

On the 12th of October the father of C, Dennis Ritchie passed away; and on the 24th the father of LISP, John McCarthy, passed away. I encourage you to read up on their achievements during their life-time.

Imagine a world without C -- the worlds first really portable language.

Imagine a would without LISP -- the Maxwell's equations of computer science.

std::fstream -- please leave!

During the last half year, there has been several bugs related to C++ file streams, e.g., std::ifstream. Most bugs have been resolved by adding calls to ios::clear to clear the error state of the stream, or similar fixes. Other bugs were fixed by using C FILE instead.

Why, why, why, is file I/O so hard to implement in a reliable way in C++? I haven't done much work with files in C, but the things I've done work well. Same thing with python. Java's file I/O is just a joke (why do I need three classes to read a file?), but at is more reliable than C++.

Think twice before I use std::fstream again. You code might be fine on implementation of the C++ standard library, but will fail on another. Sad.

Dynamic scoping in C++

I've had ideas for dynamic scoping before. There are pros and cons with dynamic scoping, as is explained at the emacs wiki.

Last time I implemented it in Java, this time I'm trying to get something more primitive (compared to the Java implementation) working in C++ (it should be straight-forward to port to C).

The use-case I had in mind when implementing this was how to distribute loggers or hierarchical configurations to every part of an application. In such code is is usually required to pass a Logger or a Configuration around to basically every function. However, with the approach described here, there is no need to pass stuff around like that, instead one uses stack-searching technique.

This little demo demonstrates the idea:

int func1() {
  TaggedInt i1(1);
  printf("i1 = %d\n", findClosestTaggedInt());
}

int func0() {
  printf("i0 = %d\n", findClosestTaggedInt());
  func1();
}

int main() {
  TaggedInt i0(0);
  func0();
}

When run, the following is printed:
i0 = 0
i1 = 1
Ok, what happens here? It's pretty simple. The class TaggedInt is a class that holds two values. A tag and an int. The function findClosestTaggedInt searches backwards through the stack until it finds the tag of a TaggedInt object and returns the corresponding int of that object.

In a real application the int would probably be replaced by something else, like a pointer to a LogConfig object or something similar. Further more, the findClosestTaggedInt would be replaced by findClosestTaggedLogConfig and probably not be used explicitly like in this demo, but rather implicitly in a constructor of some other object such as Logger. For instance:

void func() {

  Logger logger; // findClosestTaggedLogConfig is called by the ctor.

  logger.warning("Something is happening!");

}

int main() {

  LogConfig config(std::cerr); // This is a tagged object.

  func();

}

Now, there is a problem with this approach. Searching through the stack is an expensive operation, and not something you should do often. That implies that findClosetsTaggedXYZ should only be rarely called, or when the program is not in a time-critical phase. However, since findClosestTaggedXYZ is only used when distributing an object throughout the application (not when the object is used) this can usually be done once at application start-up and never again.

To sum up, here's a the rest of the code for running the demo above:
#include <string.h>
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>

static const unsigned TAG_SIZE = 16;
static const char TAG[TAG_SIZE] = "my magic string";

// A tagged int is an magic tag followed by an int. The tag
// *must* be at zero  offset relative to the 'this' pointer.
class TaggedInt {
  char tag[TAG_SIZE + sizeof(void*)];
public:
  int variable;
  TaggedInt(int variable) : variable(variable) {
    // Setup the tag.
    memcpy(tag, TAG, TAG_SIZE);
    TaggedInt* self = this;
    memcpy(&tag[TAG_SIZE], &self, sizeof(self));
  }
};

// Find which direction the stack grows.
int stackDirection() {
  int first;
  int second;
  int diff = intptr_t(&second) - intptr_t(&first);
  return diff > 0 ? 1 : -1;
}

// The maximum number of bytes to search backwards through
// the stack for the  tagged int before giving up.
static const unsigned STACK_SIZE = 1024 * 1024;

// Search backwards through the stack for the first tag.
// Note: this might be possible to optimize by a large factor
// by knowing the  alignment of stack allocated variables.
int findClosestTaggedInt() {
  static const unsigned ALIGMENT = 1;
  int direction = stackDirection();
  char start;
  for (char* ptr = &start; ptr != &start - STACK_SIZE;
       ptr -= direction * ALIGMENT) {
    if (0 == strcmp(TAG, ptr)) {
      TaggedInt* tagged;
      memcpy(&tagged, &ptr[TAG_SIZE], sizeof(tagged));
      return tagged->variable;
    }
  }
  assert(false);
}
With this code you should have a fairly good start for implementing something more useful, such as a distributor of Loggers or Configurations.

One last thing, I would be really interested in hearing from any anyone that figures out how to compute the ALIGMENT constant in findClosestTaggedInt to increase performance while still making sure no tag is missed.

Types are smart, inheritance is plain old code-resue

I've been programming object-oriented languages for at least ten years, yet the paper Inheritance is not subtyping didn't make any sense to me at all the first time I read it. (If you haven't read, I recommend you to do so.) When I started to think about type-checking in my own terms and concepts, and implemented a type-system using those concepts, then I think I got it. I think...

I guess the cause for me not understanding it was that my understanding of types in programming languages was (and still are, but to a lesser degree) very ad-hoc. For instance, in C++ is int a subtype of std::complex<int>. Why isn't it? After all, the set of of non-complex integers is a subset of the set of complex integers, isn't it?

And that's just what type or a variable is -- the set of possible values of that variable. So, why isn't int a subtype of std::complex<int> in C++ then? Well, it's simple: because the type-system doesn't allow it. And why doesn't the type-system allow it? Because subtyping in (most? all?) statically typed OO languages is tied to inheritance. This is the error that crippled the ability to reason about types of so many programmers brains.

The more I read and the more I program, the more I realize that inheritance is just another tool for code-reuse; not so much different from how functions are a tool for code-reuse. It should have been decoupled from the type-system when it was designed though. Instead there should be a separate construct for defining subtype relationship.

But let me get back to what the type of a variable is. If your brain, like mine, has been crippled by C++'s or Java's types-systems, then the phrase "the type of a variable is the set of possible values for that variable" isn't as eye opening as it should be. Consider the following C program:

1  int func(int a) {

2     if (a % 2 == 0) {

3        return a - 2;

4     return a - 1;

5  }

What can we say about the type of a here? The brain-crippled programmer would say something like "it's an int, which it either 16, 32, or 64 bits signed integer, depending on for which the architecture it's compiled." But let's dig deeper...

Let us take the role of a type-system and let's write down as much as we can possible know about a at every line of this program.

1  int func(int a) { // Don't know anything yet.

2     if (a % 2 == 0) { // If true, then a is even.

3        return a - 2; // a is even; a - 2 is even

4     return a - 1; // a is odd; a - 1 is even.

5  }

There are type-system that does precisely this; the type of a variable may change each time the variable is used. The reason for this is that every time a variable is used, there is (potentially) more information about the value of the variable. Thus, following the definition the type of a variable is the set of possible values for that variable, the type of a variable changes as the type-system derives different set of possible values at different parts of the program. For example, at line 1 the type of a is int, and at line 3 the type of a is even int.

Why did I just discuss that? Because I wanted to illustrate how distant the concept subtype and inheritance is. It is unfortunate that these two concepts are blended together in mainstream languages.

What makes the problem even worse is that inheritance is not a guarantee for proper subtyping, as the circle vs. ellipse problem illustrates.

(Please note that I'm not a type-system guy; I have no formal training in this area. This is just my take at the inheritance vs. subtyping problem.)

What OOP's jargons and complexities?

I was introduced to functional programming in an introductory programming course at the university. I had experience with imperative languages and a bit of OO from before. My immediate impression of the functional programming style was simply "this is really peculiar".

However, after a few labs in Scheme, I was stuck. The ideas was clean yet powerful. Everything made sense.

The reason I write about is because I just read Programing: What are OOP's Jargons and Complexities and I recalled those introductory lectures into functional programming. It's a great read if you are interested in how languages and programming styles relate to each other.

Type-checking is compile-time evaluation

I've been thinking a bit about type-checking the last days -- especially how type-checking corresponds to compile-time evaluation (CTE). In C++ templates are often used to implement CTE -- it's a messy way of achieving it but it works.

The idea is a language L where the type-checking is implemented purely by CTE. When a compiler for such language compiles a function f it generates (in addition to compiling the function into executable code) a function fs that type-checks each call to f.

The fact the that type-checking is a function make it possible to do all kinds of fun things, like verifying that an argument is an even integer. All that is needed to do this is to create a function (like fs) that checks whatever one wish to check. For instance, such function can be implemented in L itself (or a subset thereof).

Of course, to be able to type-check this way a lot of type-information needs to be available for the type-checking functions (like fs). For providing that kind of information, the compiler needs to (in addition to compiling) know how various kinds of type-information propagate through the program. For instance, if a is an even integer and b is an odd integer, is a * b even?

It is more less straight-forward to figure out how such type-information propagates through arithmetic functions, like a * b. What complicates things are conditionals, but those can be solved too. The real problem is loops.

And that's were I'm stuck right now -- with loops. Not that I've implemented a full compiler, but I've played around with a instruction set for a stack-based VM and how type-information propagates through those instructions. So far the only compiler is my head, though, but I'm using very mechanical steps to compile.

Anyway, as I said, the problem is loops. Generally, as soon as there is a loop in a program very little type-information can be propagated. However, it is my hope that most practical uses of loops can be expressed in a way such that a reasonable amount of type-information can be propagated through functions containing loops. This might imply that there is a need for other kinds of loops that is traditionally used: for, while, and do-while. Or, that only a certain form of for loops are allowed.

This is where I currently spend my thinking.

Andersson's Law

Proebsting's law states compiler advances double computing power every 18 year --- a pretty depressing fact.

Another depressing fact is that the most used language appeared to the public in 1973 -- almost 40 years ago.

The second most used language is essentially a combination of language features developed in the 70th and 80th -- 30 to 40 years ago. This language appeared in 1995 -- 16 years ago.

The third most used language is 30 years old and is based on a 40 years old language with some added features developed 40 years ago.

And the list goes on... Here is a compilation of the ages of the top 10 most used programming languages:

1. 38 (C)
2. 16 (Java)
3. 28 (C++)
4. 16 (PHP)
5. 16 (JavaScript)
6. 20 (Python)
7. 10 (C#)
8. 24 (Perl)
9. 37 (SQL)
10. 16 (Ruby)

Of course, just because a language is old doesn't mean it bad. Not at all. On the contrary, an old language is proven to be good (in some regard).

What bothers me though, is the "new" languages, e.g., Java, C#, or Ruby, which don't really add any kind of innovation except new syntax and more libraries to learn. Come on, there are tonnes of more interesting problems to solve... There is still no way of automatically parallelize a sequential program for instance.

There seems to be a new law lurking in programming language development... I call it Andersson's Law: Modulo syntax, innovation in new programming languages approaches zero.

And here's the "proof":
Every year there are new programming languages, however, a wast majority of those are merely reiterations of features found in previous languages (except syntax). Thus, the number of unique features per new language approaches zero for each year, that is, innovation approaches zero.

I wish for a green compiler

I like programming languages and I like compilers. I especially like how the less-is-more rule applies to programming languages in the sense that what is not available to the programming, the compiler and the run-time environment can do what ever it want with. For example, a language with pointer arithmetic can not (easily) have a compacting garbage collector, while a language without pointer arithmetic can. This can also be said for what optimizations the compiler can perform.

In a language where the memory layout is implementation defined, the compiler can optimize the memory layout of data structures such that they are ideal for the application. For instance, using run-time profiling information, the compiler can opt for a tree-base map instead of a hash-based map; or select an array of bools instead of a array of ints addressed bit-wise.

However, this requires us programmers to let go of some of our control -- if we want to have the memory layout optimized by the compiler, then the programmer can't have control over it. In theory, the resulting application should be slower, since the programmer usually know more about the application than the compiler. However, in practice I believe the application will perform better, because the programmer rarely take advantage of his/her knowledge for improving performance (it takes to much time and effort).

So, if we accept the fact that programmers are lazy (and compilers aren't), and designed a language with this in mind we would see applications with higher performance. Especially considering that programmers should make it work, make it right, make it fast (in that order) applications rarely reach the make it fast phase.

If you would ask me a few years ago, I wouldn't think that performance is such a big issue -- there is enough computation power in an average computer anyway. But considering that everything is turning into a computer application (I can book laundry slots using my remote control for my TV), it is nothing other that waste to not use that computing power properly.

I use the word waste here in an environmental way. For instance, assume an application that runs on several million computers over 5 year had 25% better cache performance -- how much less energy would that consume? Also, assume that those computers are mostly servers located in huge server rooms -- how much less cooling would be needed? Maybe it would be possible to have fewer computers running in the server room, such that the building containing the computers could be smaller...

Seeing how more and more is driven by software, we should look more into how we use the available computing power. We don't want to waste such incredible resource.

Dumbing it down, intelligently

There are problems that seems to be solvable only by throwing more and more code at it -- we call it the brute force method. It works in most situations, but it rarely produces elegant code that survives bit rotting. The brute force method is actually surprisingly common -- how many times haven't developers solved bugs by adding yet another if-statement?

Luckily, there is another way of solving such problems that result in simple and (potentially) elegant code -- here, I call it the dumb-it-down method. The dumb-it-down method achieves simplicity by solving a similar, more general, problem.

While the brute force method result in masses of code that covers every possible corner case of a very specific problem, the dumb-it-down method results in much less, more general, and simpler code. Let's take an example to clarify what I mean.

Let's assume there is a function has_python() that checks if python is installed on a machine. This function is used for making sure that a certain Python script can be executed. How is such function implemented? It needs to check permissions, check paths, check the python version, etc. There is a lot of intelligence needed to be implemented to make sure that the script can be executed, right? This is the brute force method.

Ok, now let's rewrite the problem slightly. Remember that has_python()'s purpose in life is to make sure that a certain python script can be executed. So, we can just as well write a function that executes the python script and return whether or not it succeeded, right? As it turns out, that function is called exec and is built into the standard C library. No need to write a single line of code!

In the above example we rewrote the problem slightly but kept the intention: execute the script only if it can be executed. This is the pattern; this is the idea behind the dumb-it-down method -- look at what the code tries to do on a more general level and find the a simple (or 'dumb' if you want) way of implementing that.

I think the dump-it-down method is an umbrella term covering many design strategies which aim are to produce simple long-living code. I've previously discussed this here.

It seems like software is in a never-ending spiral of complexity: software needs to grow more complex to manage other complex software. Why is an IDE larger than the operating systems from last decade? Are today's IDEs solving more complex problems than the operating systems did? How can the plug-in APIs of said editor be more complex than the C standard library? Aren't the APIs supposed to make it easy to implement plugins?

I've mentioned it before in this blog, but it needs to be repeated. We software developers, need to start looking at our work (and the result of out work) differently. Our skills are not measured by the complexity of the programs we write, but the simplicity of them (assuming equal functionality).

Forgotten treasures I: Look-up tables

Think fast: how would you convert a bool to a string, "TRUE" or "FALSE", in C? Most of us probably answers "with an if-statement", and when asked to show some code doing it end up with something like:

const char* theString;
if (theBool)theString = "TRUE";
elsetheString = "FALSE";

or some similar code using the conditional operator as follows:

const char* theString = (theBool ? "TRUE" : "FALSE");

But there is at least one more way of doing it, which in some cases gives more readable code. I'm speaking of look-up tables. The code above can be expressed by look-up tables like this:

static const char* options[] = { "FALSE", "TRUE" };
const char* theString = options[theBool];

which is much less code compare to the above if-then-else version. It's slightly more code, though, compared to the conditional operator-version. However, I personally find code using the conditional operator hard to read. I know perfectly well how the conditional operator works, but I still need a few more brain cycles to read such code.

On the other hand, I have no problems at all reading code using look-up tables since code like options[theBool] looks very similar to a normal function call. Of course, there are down-sides to using look-up tables; the most important one is that the result is undefined if you index outside the range of the table.

Another way of using arrays like this is when you need to decode a tree structure. Let's say we have three ints which represents a path in a tree.
   Node root = { "Root", layer1Nodes[node1], 0 };
   Node layer1Nodes[] = { { "L1A", layer1ANodes[node1]  } };

During the last year I've gone from primarily developing Java to write C++, C, and assembler. I have to admit, there are a few idioms that I have rediscovered in this transition to C and assemble. Look-up tables are on such treasure.

Of course, there is now real reason why look-up tables can't be used in, e.g., Java, but it seems like the coding traditions in Java discourage such code. Other languages encourage such  code; for instance lists and dicts are very common in Python as a tool for simplifying expressions. It's a bit funny what different communities value in their code.

The problem with code coverage and why static is good

How can  you automatically determine how well a test-case tests some piece of code? What metric should you use? What instrument should you use to measure it? As I'm sure you know, these questions are not easy to answer. Measuring the quality of testing is not a simple thing to do.

Normal code coverage tools are basically worthless for measuring the quality of the test-cases. All they measure is if a line of code has been executed or not; not if the test case verified the result produced by that line. Tools like Jumble are much better, but much harder to use.

However, code coverage is actually a much better  measurement of test-case quality if you language is very static, declarative, and the code hard to extend. Language like that may sound not sound very useful, but they are. They really are. There are circumstances when you really need their static, declarative and precise semantics. When you design hardware, or software for running on resource limited hardware, then you really need precise semantics with regards to the combinatoric depth, stack usage, the position of code in memory, etc. Higher level language, by their very definition, do not make you worry about those "petty details", which is good unless the "petty details" are what makes you application actually function as it should.

High level languages come with a cost, though. The more dynamic a language gets, the less you know what actually will happen when you run the program. Thus, a test-case exercising the code is further from how the code actually will be run. In fact the more dynamic a language gets, the less you can tell what any piece of code written in that language does; it all depends on how it is run. For example, what does this python function do?

def magic(string, filter):
   return [c.swapcase() for c in string if c in filter]

You cannot say for sure, because it all depends on the types of 'string' and 'filter'. Furthermore, when you see the following code:

print magic("Hello, world", "aeiou")

You cannot say for sure what it means either (even though you know the types of the arguments), because 'magic' might have been redefined to do something entirely different.

Consequently, the value of the test-case is much smaller in dynamic languages; thus, more test-cases are needed. This is nothing new, but it is worth considering before saying "I'm so much more productive in Language X than in Language Y". You didn't forget testing did you?

Separating responsibilities using channels

Imagine the following situation. Three developers that are responsible for three separate (but connected and interacting) subsystem discuss which subsystem that should be responsible for a certain feature.

Developer A: I don't care if Subsystem B or C is responsible for producing Information Y; but Subsystem A needs Information Y to support Feature X.

Developer B: Well, Subsystem B shouldn't be responsible for Information Y because Subsystem B's responsibility is Z and only Z!

Developer C: Subsystem C shouldn't provide Subsystem A with information Y, because Subsystem C should never communicate subsystem A directly!

Feels familiar? It sure does for me.

Basically the problem is that the architecture (which say what subsystems that should interact with each other directly) and the responsibilities (of those subsystem), does not allow the some information (needed by one of those subsystem) to flow as needed.

What is the solution here then? Should poor Developer B be forced to make Subsystem B take on responsibilities beyond Z? Or should Subsystem A and Subsystem C be allowed to communicate directly? Non of these two alternatives are ideal, is there another option?

Of course there are! And I'm sure that you have already figured it out: simply let Subsystem B provide a channel that let's other subsystems provide Subsystem A with information. Subsystem B never knows what information is sent over the channel and Subsystem A never know that the information's source actually is some other subsystem than Subsystem B. In other words, no architectural rule should be broken by introducing a channel.

If you have looked into layered systems, such as communication stacks, this is nothing new. The insight (if there is any for you to get here) should be that any  kind of system can provide a channel without that conflicting with it's other responsibilities. For instance, a system that decompresses files can have a channel that allows other systems to attach meta-data of the decompressed file.

Of course, the channel doesn't have to be a channel in the sense of sending messages back and forth. For instance, a channel can be implemented simply by a std::map<std::string, boost::any>.

A problem that might appear is that the channel is misused and unspecified, informal protocols/contracts starts to grow. But that's a problem that isn't connected to channels, but rather any kind of communication (be it messages, method calls, or file formats).

When all magic goes wrong: std::vector of incomplete type

I have recently been working on an API. I put great effort into separating the implementation from the interface, which in this case means that the header file of the API strictly contains declarations. No executable code at all. This makes it easier to hide implementation details, which is something we should always aim for, especially for APIs.

In C++ there are several ways to hide implementation. One way is to forward declare types and simply use pointers and references to those types in header files. However, when you need to use a type by-value it is not possible to use a forward declared. For example:

class CompleteType { };

class IncompleteType;

class HoldsTheAboveTypes {

  CompleteType value0;     // Ok.

  IncompleteType* pointer; // Ok.

  IncompleteType value1;   // Compilation error!

};

In my experience, there are usually ways to avoid having types by-value that are implementation details. Usually its a matter of thinking hard about the life-time or ownership of an object. However, when I implemented the API mentioned above I ran into a problem that seemed to be unsolvable.

I needed to have a class with a field of type std::vector of an incomplete type, that is:

class StdVectorOfIncompleteType {

  std::vector<IncompleteType> value;

};

This code fails to compile, though, giving some error message about "invalid use of incomplete type" (just as the code above). However, IncompleteType isn't used anywhere! So it should compile, shouldn't it?

(Well, I guess you could argue that it should compile if C++ would be designed properly, but it not so let's not go into that...)

The reason the above code doesn't compile is because the following special methods are automagically generated by the compiler:

• zero-argument constructor
• copy constructor
• destructor
• assignment operator

The default implementations of these special methods are nice to have in most cases. However, in the example with std::vector<IncompleteType> above these default implementation doesn't work at all. It is these default implementation that causes the compilation error, which is very much non-obvious. All (auto-)magic goes wrong.

So to fix the compilation error given above, we simply need to declare these special methods, and provide an implementation to them in a separate .cc-file, where the declaration of IncompleteType is available.

I've been fiddeling with programming for more 15 years (professionally much shorter, though) and I've run into this problem several times before but never tried to understand the cause for it. Today I did.

Design patterns are to software development what McDonald's is to cooking

I remember reading the GoF design patterns book and thinking gosh, this is really good stuff. Now I can write program like a real master! I liked the whole idea so much that I went on reading the xUnit Patterns book, and a few more like Refactoring to Patterns.

Looking back on these books now and what I learned from them, I realize that it's not the patterns described in the books that I value the most. It's the reason for their existents; the motivation for using them. For example, the Factory pattern exists because it's often desirable to separate object construction from domain logic. Why? Because it reduces coupling, which means code are easier to enhance, reuse, extend, and test. So when you understand why a pattern exists, then you know when to use and when not to use it.

The problem is that you don't need to understand why a design pattern is needed in order to use a design pattern in you code. Code with a misused design pattern is worse than code without that pattern. As an example, here is some code taken basically directly from an application I worked with:

Thing t = new ThingFactory().create(arg);

with ThingFactory defined as

class ThingFactory {
  Thing create(int arg) { return new Thing(arg); }
}

This is a prime example of code that misuses a design pattern. Clearly, (s)he who wrote this code did not understanding why and when a Factory should be used, (s)he simply used used a Factory without thinking. Probably because (s)he just read some fancy-named design-pattern book.

This is one big problem I see with design patterns. It makes it easy to write code that looks good and professional, when in fact it's horribly bad and convoluted. The Design Patterns book is the software equivalent to MacDonald's Big Book of Burgers: you need to be a good cook/developer already in order to learn anything that will actually make you burgers/software skills better. A less-than-good cook/developer will only learn how to make burgers/software that look good on the surface.

I recently read Object-Oriented Design Heuristics by Arthur J. Riel, and I must say that this book is much better than the Design Patterns book. First of all, it more than just a dictionary of patterns, it's actually a proper book you can read (without being bored to death). Second, the design rules (what the author calls "heuristics") are much more deep and applicable than design patterns. These rules are like Maxwell's equations for good software design. Understand and apply them, and your software will be well designed.

Let me illustrate with an example how I think Riel is different from GoF. Where GoF say "this is a hammer, use it on nails", Riel says "to attach to wooden objects you can either use hammer+nails or screwdriver+screws, both has pros and cons." Sure GoF is easier to read and you'll learn some fancy word you can say if you running out of buzz-words, but Riel actually makes you understand. Understanding is underrated.


But let's give the GoF book et. al, some slack. To be honest I actually did learn something useful and important from those books, and I couldn't do my daily programming work properly without that knowledge:

• favor composition over inheritance,
• separating construction logic from domain logic, and
• code towards an interface, not an implementation.

To me, these three ideas are the essence of most design pattern that are worth knowing and if you keep those three ideas in you head all the time you won't screw up to much.

Oh, there is actually one more idea you should keep in your head or you will definitely screw up big time (literately).

But of course there is one more important thing about knowing design patterns. It helps you communicating with your colleagues. Design patterns defines a pattern language, so instead of saying "...you know that class that instantiates a bunch of classes an connects them..."you can say "...you know that builder class...". Honestly, for me this language is way more important than the patterns themselves.

Actually, there is one thing that I learned from all those design-patterns books (not including Riel). They taught me something important that I could only have learned from few other places: I learned that if an author tries hard enough, (s)he can write a 500 pages book consisting of some common sense and two or three good ideas repeated over and over again. The xUnit Patterns book is the prime example of this. Don't read it. Read Riel.

Global contracts: mutexes, new/delete, singeltons

I had lunch with a former collegue some time ago. We discussed several things, I would like to write about one idea in particular: global contracts.

A global contract is an agreement that every part of your code needs to adhere to. A good example of a global contract is locks. Locks are used in multi-threaded applications to synchronize threads. The problem is that there is no way to enforce that threads take the locks when they should, nor to release the lock when they should. Application code is free to access memory/object with or with out locks. Correct application code, though, have to take locks, access the memory/object, and the release the lock.

A similar but more common global contract is Singletons. Every part of the application must know how to get the singleton instance, and if the singleton has mutable state every part of the application must also know how to mutate that state correctly.

An even more common global contract is memory management in application without garbage collection. In such applications, the knowledge of how to allocate and deallocate instances of objects are distributed. There are ways to design your application such that the global contract is encapsulated, but in general the detailed knowledge of the contract is spread out all over the application.

Ok, global contracts are bad for the application design, but how do we get rid of them? We can't simply ignore locks or memory management, so how do we handle them? I see the following possibilities:

1. Encapsulate the details of the global contract, or
2. Make the global contract into a local contract.

The first alternative means that you accept that contract is global, but you make sure that it's simple to adhere to it. An example of this is to use smart pointers, or to hide that there is a singleton within a single class, which also holds state, e.g.,

class SingletonHider {

  Singleton singleton = Singleton::instance();

  int intState;

  void changeState(int i) { intState = i; }

  void doit() { singleton.doit(i); }

}

And every time some part of the application needs to use the Singleton class it instantiates a SingletonHider, which holds all the state needed. The precise behavior (or any state that absolutely needs to be global) is handled by the Singleton class.

The second alternative is to make the global contract into a local contract. How is this possible? Well, whether or not a contract is global or local is entirely a question of perspective. If you look a memory management from a operating system's perspective, the details of new and delete are definitely a local contract of that application; it's not a operating system-global contract. So the idea for making global contract local is to implement a class that acts like a overseer of the rest of the code. This class encapsulates all the details of the contract and provides a simple interface. This is exactly what a garbage collector is. Let's take Java's garbage collector as an example:

• it oversees: inspects the running application and determines when a piece of memory is garbage
• simple interface: every piece of memory is allocated by new. The details of where the memory is allocated (constant pool, generation 1, stack, etc) is encapsulated.

I'm sure there are more examples and more ways how to make a global contract local, but the approaches outlined here should give a few ideas the next time you which to refactor away a singleton, or fix new-delete coupling.