Programmatically Speaking

A potpourri on static vs dynamic

2011-12-11T04:13:00.001-08:00

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

2011-11-23T08:42:00.001-08:00

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

2011-11-04T09:18:00.000-07:00

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!

2011-10-20T02:17:00.000-07:00

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++

2011-09-10T00:49:00.000-07:00

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

2011-09-04T15:11:00.000-07:00

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?

2011-08-31T13:55:00.000-07:00

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

2011-08-17T14:46:00.000-07:00

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

2011-07-28T13:05:00.000-07:00

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:

38 (C)
16 (Java)
28 (C++)
16 (PHP)
16 (JavaScript)
20 (Python)
10 (C#)
24 (Perl)
37 (SQL)
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

2011-06-26T12:59:00.000-07:00

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

2011-05-21T05:43:00.000-07:00

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

2011-05-14T02:55:00.000-07:00

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

2011-04-29T13:48:00.000-07:00

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

2011-04-16T09:39:00.000-07:00

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

2011-01-12T14:33:00.000-08:00

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

2011-01-09T14:48:00.000-08:00

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

2011-01-06T07:15:00.000-08:00

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:

Encapsulate the details of the global contract, or
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.

Integrating invisible tools with the shell

2010-11-21T15:19:00.000-08:00

I've been working on a build system called Mim for some time. It has some interesting features, the most interesting being that files/artifacts are implicitly built when they are read. In other words, there is never a file on disk that is out of date.

That's pretty neat, but what happens if a file cannot be built for some reason? What happens it there is a syntax error in a .c file, for instance? Since Mim runs in the background, how should such errors be reported? Simply writing them to a log file might suffice, but the experience for the end-user is not very nice. Imagine having to open a file every time a file fails to compile... Horrible!

This is not a unique problem for Mim. All tools that runs in the background have problem with reporting errors, and most solve this by writing to a log. However, for Mim I chose a totally other way of doing it.

Most shell utilities, e.g. cat, uses functions in the standard library for printing, open files, etc, but more importantly (for this post) for reporting errors. The error function is used to report errors.

That means that we can control how errors are printed, by LD_PRELOADing a .so-file with another implementation of the error function. This is what I did to implement error reporting for Mim.

This is how Mim works now; if you try to open a file that Mim cannot build because of a build error (e.g., compile error), you'll get the following printed to the console:

$ cat generated-file.txt

cat: Mim: error 512 when building artifact
which is much better than the old error message which just was a generic message indicating that the file could not be opened.

But there is still room for improvement! It's nice to get a error message that says that the file couldn't be built, but it would be even nicer if the message told us why the artifact couldn't be built. I haven't implemented that yet, but I'm working on it. I imagine something like this:

$ cat generated-file.txt

cat: Mim: error 512 when building artifact generated-file.txt, because:
input-file.cc failed to build, because:
input-file.cc:53: Syntax error.
$ emacs input-file.cc

That will require some more work though as I said, but it's definitely possible and it's technically not hard.

The firge, the door and the fire alarm

2010-09-04T00:41:00.000-07:00

Today when I prepared breakfast I realized that the fridge wasn't properly closed. It had been a small opening the whole night. That's not particularly good.

But what's worse is that the fridge did not make any noise indicating that the door was open. In fact, it did the opposite: it turned off the only indication there was that the door wasn't properly closed -- it turned of the light inside the fridge. If that light wasn't turned off it would be easier to spot that the door was open.

Turning the light off would not be a big problem if there was some way the fridge alarmed when the door was open. Let's say making a noise when it had been open for more than 1 minute.

I'm sure that it's a feature that the fridge turns off the light by it self when it has been on for too long. But I can't the use-case when it would be a useful. There must be a timer somewhere that turns off the light. That timer should instead trigger an alarm.

Actually there is an noise-making-device in the fridge. But that only used when the temperature in the fridge is above a certain temperature. That noise-making-devices should be triggered by that timer. Why didn't it?

I don't know.

Recently I've noticed more and more weird design choices in everyday things. Like having the handle of a door be shaped as a pipe when you should push the door, and having the handle be shaped like a flat surface when you should pull the door (think about it, a surface is easy to push and a pipe is easy to pull).

Even worse, I've experienced that fire alarms sounds very very much like the break-in alarm.

Mim: the build system you always wanted

2010-09-03T07:31:00.000-07:00

The word mim means any of the following:

an incorrect way of writing 1999 in roman numbers (as in "we gonna party like it's 1999"),
the Madame Mim from the Disney movie Sword in the Stone,
Swedish for "mime" meaning "imitating"
a figure in Norse mythology renowned for his wisdom
an acronym for "Mim Isn't Make"

it's also the name of the build system I've been thinking and working of for a while. This post is about what Mim is now and what it can become. Text in red describes stuff that isn't implemented yet, text in yellow is things that are kind-of implemented, and text in black describes implemented features. First, I'll describe how Mim is different from other build systems and why it's better.

Problem
The problems with traditional build system are:

make sure the dependencies are correct and built in the right order (think: make depend && make && make install),
be sure of that every built file you see is up to date,
hard understand how a software project is built (what are the artifacts? where are they stored? what are the dependencies?),
hard to understand which variables a build have (e.g., make DEBUG=1)

Solution
The solution to these problem is (of course) Mim. With Mim you clearly see all artifact the build system produces, how they are built, and when they need to be built. In fact, you can see the artifacts, e.g., by doing ls, before they are built. In other words, using your normal command line tools you can browse the project file tree to find the artifact you need (to run, to view, to copy, etc.) without building anything. Sounds like magic? Keep reading...

When when you found the program you need to get built you simple execute it. No need to issue any command yourself to build it. The program will be automatically built for you and then executed. Similarly, if you have a tool that generates a text file as part of the build, you can do emacs file.txt. The file will be automatically generated and then opened in emacs.

If you need to get more information about a file you can do mim ls filename. You'll get something like this written to the console:


-r-xr-xr-x you users filename (g++ filename.cc -o filename)

that is, you can easily discover to the access rights, the owner, the group, and how the file is built, of any artifact simply by locating it in the file system.

This is especially powerful when you work with project of which source code generation is part of the building process. Understanding what files are generated, how they are generated, can be very hard. With Mim, however, this is very easy, because every file (generated or not) looks the same to you when you browse the file tree. Additionally, you can ask Mim for additional information about a certain artifact file, e.g., get the command for building the file by doing mim cmd file.

Furthermore, getting the dependencies right when the build involves several steps (generating .d files, generating source code, generating .d files for the generated code, compiling the source code, linking the source code against libraries (which themselves has to be built, including its generated source code)) is also very very hard. And understanding it a few month later is even harder. Mim solves all these problems.

Let's take an example. Let's assume we have a directory called hello with a file hello.cc contaning an implementation of Hello, World. There is also a file called Mimfile that tells Mim how to build this program. Doing mim ls in hello gives you:

greeting.txt
hello.cc     codegen -lang en greeting.txt -o hello.cc
hello-en     g++ hello.cc -o hello-en
Mimfile

which tells you that there is only one physical file, greetings.txt, in this directory (except the obligatory Mimfile) and two artifact files, hello.cc and hello-en, of which the latter is an executable. You can also see that there is some code generation involved by looking at the command line for hello.cc. You can tell all this by issuing one simple command, mim ls, without building anything at all.

Let's say you wish to take a peek at the hello.cc file. All you need to do then is to do cat hello.cc. No need to worry that the code you see is out of date because Mim makes sure it's up to date before it's opened.

Being lazy
Being lazy is a good attribute; as long as you're not too lazy. Being lazy in the context of a build system means that you only rebuild a file if is inputs have changed. How do Mim achieve this?

Mim woks by intercepting all read and write accesses to the file system. This means that Mim has perfect knowledge of 1) which files are read when a given artifact if built, and 2) which files that have been updated since the artifact was last built. This means that artifacts are only rebuilt when needed.

This information makes it possible for Mim to easily construct a graph dependencies and what needs to be built. This implies that Mim start building the leaves of the graph as early as possible to reduce the build time.

Instant messaging

In large project there is usually variables that controls how the project is built. Mim supports such variables in a nice way. To list the variables simply do mim conf, you'll get something like this printed to the console:

lang      en   en|fr|swe  Controls in which language "Hello, World" is printed.
debug     off  on|off     Compile with or without debug information.
optimize  0    1|2|3      Optimization level as defined by gcc:s -O flag.

The first column is the the name of the variable, second column is its current value, third is its possible value, and last column is a textual description of it.

Changing the value of the variable lang to swe is done by doing mim conf lang=swe. Setting a variable have instant effect. For example, if a variable affects which files are built, you can see the updated list of files immediately by doing ls without building anything. Example:

$ ls hello*
hello.cc  hello-en
$ mim lang=swe
$ ls
hello.cc  hello-swe

That is, by changing the variable lang from en to swe we get an artifact file called hello-swe instead of hello-en like we got before.

To aid discoverability even more, you can do mim ls hello* lang==* to list all files matching hello* for all values of lang. For the hello example this outputs:

hello-en   lang=en   g++ hello.cc -o hello-en
hello-fr   lang=fr   g++ hello.cc -o hello-fr
hello-swe  lang=swe  g++ hello.cc -o hello-swe

All these features helps you in learning how an a project is built, how to use its build system, how to change it, how those changes affect the build system, and more.

The Tracker
Since Mim intercepts all accesses to the file system, it can help you when you do potentially bad things, for example, if you delete a file that is needed to build an artifact. Mim also updates your Mimfiles automatically when you do non-destructive changes to your source tree. For instance, when you rename an input file to gcc as the following example illustrates this:

$ mim ls hello*
hello.cc  codegen -lang en greeting.txt -o hello.cc
hello-en  g++ hello.cc -o hello-en
$ mv hello.cc hi.cc
$ mim ls hello*
hi.cc     codegen -lang en greeting.txt -o hi.cc
hello-en  g++ hi.cc -o hello-en

Mim can do this automatic update of Mimfiles correctly in many cases, but it's impossible to get it right every time since that would require deep knowledge of all possible build tools (e.g., gcc, ld, m4, etc). However, Mim makes certain (reasonable) assumption on how the build tools behave, and as long as the build tools' conform to these assumptions Mim gets it right most of the time. Anyway, to check that Mim got it right, you simple build of application so this isn't a big problem in practice.

Getting general

Mim is built around the concepts of events and actions triggered by event. So far we have implicitly discussed the event open artifact for reading and the action was update artifact. The possible events that can trigger actions are:

open physical of artifact file for reading (before-read),
closing a physical or artifact file after write (after-write),
deleting physical or artifact file or directory (delete-file),
creating a physical file or directory (create-file), and
moving a physical or artifact file (move-file).

Since arbitrary commands can be executed as the result of an event, you can do what ever you heart desire when a file is moved, delete, created, etc. However, actions that interact with Mim would be hard to implement ourself and are thus built into Mim:

update an artifact (without reading the artifact file)
log to the Mim log (e.g., an error message)
reject event (e.g., reject opening a file).

The reject event action is useful, e.g., if you need to verify the consistency of a save file: if the file is consistent it cannot be saved.

Playing nice
So far so good. But what about integrating with other non-miming tools like, say, make. Since all Mim does to build an artifact files is to execute a command line in the shell, Mim can easily be used as a front-end to make. Here is an example of doing mim ls in a directory of a project that does just that:

main.cc
hello     make hello
Makefile
Mimfile

Furthermore, any program can use Mim for building files, because all the program need to do to build a file is to (try to) open it for reading. Mim will then kick in and build the file, without the other program ever nothing anything special. This is very powerful, because every program you have on you computer, cat, emacs, Mozilla, etc, can build any file using Mim.

Saving the environment
Do you have ./configure && make && sudo make install aliased to nike on you system? If you do you're not using Mim.

One reason to use autoconf (i.e., the ./configure script above) is to find the paths to all the necessary tools, libraries, headers, etc, needed to build your project. With autoconf this involves generating Makefiles that are specifically targeted at your system. The problem with autoconf and the generated Makefiles is that you have to be a genius to understand what the heck is going on.

So what do Mim do instead? Easy, you have an artifact file for each tool, library, header, etc, that is needed by your build. Those artifacts are configured (e.g., using autoconf) to link to a specific file on your system. These tools (or, ) are normally placed in a directory called ext (for "external"); thus, to list the dependencies to external tools simply do find ext or ls -R ext. Every file listed is an external dependency. Example:


$ cd my-project/ext
$ ls -R *
ext/bin:
g++  ld  python

ext/include:
3rdparty.h

ext/lib:
3rdparty.so

In this example we have configured the ext directory to contain a compiler, linker, and a python interpreter. So, when we need to compile a .cc file we have the following command line in the Mimfile ext/bin/g++ file.cc. The first time this command line is executed, the artifacts (ext/bin/g++, etc) are not yet configured, so Mim launches the configuration tool (autoconf). After that, the artifacts in the ext directory point to the correct files on the local system and can be executed easily.

A way of thinking of this is that Mim creates a virtual environment (directory structure) that is ideal(ized) for you specific project. All the tools and libraries you need are right there in the ext directory.

Deep understanding
Mim really, really, understands mimfiles. If a mimfile is updated, artifacts potentially need to be rebuilt. However, Mim will only rebuild artifact which command lines has changed or if their dependencies' command lines are changed. Have you ever experienced that your entire project needs to be rebuilt just because you added an a comment to a makefile? That will never happen with Mim.

Mim has even support for refactoring mimfiles via your filesystem! In the hidden directory .mimfile the artifact files' mimfile-data is represented as files. So, if you want to change the name of an artifact file simply do mv .mimfile/old-name .mimfile/new-name; to create a new artifact file that is identical to an existing one do cp .mimfile/original .mimfile/copy; to delete an entry from the mimfile do rm .mimfile/remove-me. Finally, to edit the command line for an artifact you simply edit the corresponding file under .mimfile, e.g., echo 'gcc input-file.c -o %output' > .mimfile/file-to-be-edited.

As mentioned earlier, Mim also has variables that can be used to configure how your project is built. These variables are also represented as files under the directory .mimvars. Here you can easily browse the variables using ls, find, grep, etc, or even your graphical file browser. The get the current value of a variable, simply do cat .mimvars/the-variable and to set the value do something like echo 'new value' > .mimvars/the-variable.

When thing go wrong

Ok, so Mim is nice, I think I've communicated that by now. But sometimes the world is very very unnice. Sometimes the world don't want to compile your code. Then you need to either 1) fix the world, or 2) fix your code. To my experience the latter is slightly easer than the former, although your mileage may vary.

To fix your code you need to know what the compiler complains about, but how do you do this when the files is compiled behind the scenes? Simply do mim log errors to print the error messages to the console, fix the error, and run the program again.

Doing mim log error after every build error gets annoying very fast. Thus there is a variant, mim log errors -f, that is useful when you wish to get continuous feedback. Given the -f flag Mim will run in the background and print the error message to the console as soon as they appear. So, assuming hello.cc contains an error, trying to execute hello will print the flowing:

$ mim errors -f
$ ./hello
hello/hello.cc: In function ‘int main()’:
hello/hello.cc:3: error: ‘printf’ was not declared in this scope

which is is just what gcc outputs, thus, any tool that parses the output from gcc will understand the error output from Mim as well. This is of course also applicable for other tools like make.

Summing up
I've described the ideas behind Mim, its current state, and possible future features (that, by that way should be very reasonable to implement :)). You can find Mim here. You'll need Intel Threading Building Blocks and Lua 5.1. I've developed using Ubuntu and also compiled it on Suse 11.2. The instructions for how to build Mim itself is currently horribly missing, so please contact me if you like to try Mim out.

DSL: Domain Specific Logging

2010-07-09T11:30:00.000-07:00

A few years ago, I was asked to to design a logging framework for our new Product X 2.0. Yeah, I know, "design a logging framework?". That's what I thought too. So I didn't really do much design; all I did was to say "let's use java.util.logging", and then I was done designing. Well kind of anyway...

I started to think back on my first impression of the logging framework in Product X 1.0. I remembered that I had a hard time understanding how it was (supposed) to be used from a developer's point-of-view. That is, when faced with a situation where I had to log, I could not easily answer:

to which severity category does the entry belong (FINEST, FINER, FINE, INFO, WARNING, SEVERE, ERROR, etc)
what data should be provided in the entry and how it should be formatted, and
how log entries normally is expressed textually (common phrases, and other conventions used).

In other words, it was too general (i.e., complex) with too much freedom to define your own logging levels, priorities, etc.

That's why I proposed to make logging easier, thus, the logging framework in Product X 2.0 has very few severity levels. This is implemented by simply wrapping a java.util.logging.Logger in a new class that only has the most necessary methods.

This simplification reduced the code noise in the logger interface, which made it a lot easier to choose log-level when writing a new log message in the source. This had an important implication (that we originally didn't think of): given that a certain message had to be logged, we (the developers) agreed more on which level that message should be logged. No more, "oh, this is a log message written by Robert -- he always use high log level for unimportant messages".

Of course, you could still here comments like "oh, this log message is written by John -- he always use ':' instead of '=' when printing variables". This isn't much of an issue if an somewhat intelligent being is reading the logs, e.g., a human. However, if the logs are read by a computer program, this can be a big problem -- this was the case for Product X 2.0.

This variable-printing business could be solved quite easily; we simply added a method to the logger class (MyLogger) called MyLogger variable(final String name, final Object value) that logged a variable. Example:

logger.variable("result", compResult).low("Computation completed.");

which would result in the following log message:


2008-apr-12 11:49:30 LOW: Compuation completed. [result = 37289.32];

When I did this, I began to think differently about log messages. It put me into a new mind-set -- the pattern matching mind-set. Patterns in log messages started to appear almost everywhere. Actually, most of our logs followed one of the following patterns:

Started X
Completed X
Trying to X
Failed to X
Succeeded to X

Here is an example:

try {
  myLogger.tryingTo("connect to remote host").variable(
                    "address", remoteAddress).low();
  // Code for connecting.
  myLogger.succeededTo("connect to remote host").variable(
                       "address", remoteAddress).low();
} catch (final IOException e) {
  myLogger.failedTo("connect to remote host").cause(e).medium();
}

To take this even further, it is possible to only allow certain combinations of succeededTo, tryingTo, cause, etc, by declaring them in different interfaces. Let's assume that it should only be possible to use cause if the failedTo method have been called. Here's the code for doing that:


interface MyLogger {
  // ... other logging methods.
  CauseLogger failedTo(String msg);
}

interface CauseLogger {
  LevelChooser cause(Throwable cause);
  LevelChooser cause(String message);
}

interface LevelChooser {
  void low();
  void medium();
  void high();
}

This is essentially what's called fluent interfaces. It complicates the design of the logging framework, but also makes it impossible to misuse it. Good or bad? It's a matter of taste, I think, but it's a good design strategy to have up your sleeve.

The only design pattern is small solutions

2010-06-17T11:34:00.000-07:00

I just saw this TED talk (which you need to see too!). It's essentially about how we prefer big complex solutions to any problem we face. Why? Because it makes us feel smart and important. As my head is filled software thoughts, I started to think how this it relates to software design. We software developers really!, really!, really!, like big solutions to small problems: "Oh, you got a program that needs to store some data? You better get yourself a dedicated database machine, a persistence layer, and define a XML schema for communication data format."

We don't need big solutions to small problems. Big solutions are easy to find. Big solutions need man-hours but no understanding. We need small solution to big problems. Small solutions are hard to find. Small solutions need insight into the actual problem we're solving. The actual problem is what's left when we remove all accidental complexity, marketing buzz-words, etc, and think clearly about the original problem.

Small solutions are orthogonal to each other; big solutions are not, they interact in non-obvious ways. Thus, big solutions creates more problems, or as the american journalist Eric Sevareid, said:

The chief cause of problems is solutions

which is more true in software development than in most other areas. Implement small solutions to problems and your future self will thank you. Implement big solutions and you fall for the sirens' calls of the marketeers, or your own wishes to do seemingly cool stuff while looking smart doing it. Do you really need a DSL? A database? Web interface? Reflection? Operator overloading? Meta-programming? Code generation? Ruby? SOAP?

Thinking small have big impact.

If it hurts do it more often

2010-06-14T09:33:00.000-07:00

As a kid, most of what you did was related to learning. Some call it "playing" or "being curious", but whatever you call it, it's learning in one form or another. And learning hurts. A lot.

So you start going to school to make learning not hurt so much. As a 7-8 year-old you enjoy school, because it makes learning much easier. Also, you can play with your class mates, like say, play soccer. Oh, by the way, playing soccer makes you run faster longer, gives you better balance, gives you better feeling of how flying objects behaves (like a ball), better timing your own movements to others (like your team mates). It also makes you better winning and loosing (you aren't a bad looser, are you? How about a bad winner?), and it makes you better at focusing on a particular task, and making other (your team mates) focusing on the same task as you. It's all learning.

As you grow older you become more comfortable with most things you do because you know them. When you finally leave school to start working as a programmer you lost all will to do things that hurts... because you lost your will to learn (in comparison to how much you wanted to learn stuff as a kid). You lost your will to discover new things.

Stupidity hurts

So, when stated with a problem that forces you to do something you don't know or something you really don't like, you stall. Stall, stall, stall, because you don't want to do it. You want to do something fun. Something you know how to do. Something that makes you feel secure and comfortable. Something that makes you feel less stupid!

Yes, you are stupid. I'm stupid. We are all stupid. No one know everything, so everyone is stupid at something. And we will remain stupid at those things unless we learn how to do them better. But... Ouch! Remember? Learning hurts! So we think to yourselfs "Ooh, I don't want to do that!", or put slightly different "I may get hurt doing that! I'd rather stay stupid!". Imagine if you thought that way as a 8-year-old kid in school... or at the playground, or at the soccer field. We wouldn't get many marathon runners or Nobel prize winners that way, would we?

The cure

It's really easy: dare to be stupid. Dare to ask stupid questions. After a while, you'll notice that you start to ask really hard questions, and before you know it you'll ask questions no one (you know) have answers to. And then, as it happens, people will ask you instead. If they dare to of course (hint: they should).

In fact, I think that people will be more likely to ask you (stupid) questions because they'll seen or heard (of) you ask (stupid) questions. And you know what, people do as other people do. Especially like people they look up to, and since you know so much (from asking stupid questions) they look up to you. Isn't that neat?

The workplace

If you have colleagues who don't mind potentially looking stupid by asking a question, you've work at a good company, I think. But I'm not really someone who read or thinks about this a lot, so I may be wrong. There may be effect here that I'm clueless about. Anyway, my feelings are that I'd be more at home at a company like that than a company that encourages silence and really intelligent questions only. But I'm just me. You are you, and you may feel entirely different about this.

Features are social processes

2010-06-10T12:53:00.000-07:00

For a while now I've been thinking about how human languages evolve compared to how computer languages are designed and how that relates to the features of the respective languages. In this post I will ramble at bit about how the meaning of software related terms is defined. I'll also discuss hard and soft features in programming languages and how the community surrounding the language affects, and is affected by, those features.

This is mostly a bunch of ideas and observations that I'm trying to put into words to 1) make me understand them better, and 2) make sure I don't forget them. If you expect a scientific survey, then I'm sorry to disappoint you. Maybe, though, you'll find food for your own thought and ideas.

What's a language?

As I see it, languages (be it the human or programming kind) are mutual agreement between the communicating parts of what a statement means. If everyone have a different opinion of what the following statement means, then it effectively doesn't have any meaning at all since we can't use it to communicate with anyone:

You need wood from a forrest to create a fire.

or in computer-speak:

Fire fire = new Fire(forrest.getWood());

On the other hand, when we agree upon what this phrase mean, then we can do all kinds of things: discuss its correctness, use it in another context, abstract it to cover more and general cases, write a compiler for it, etc.

For example, the common breed of C compiler accepts a lot of code most C programmers won't. It's the users of the C language that defines the subset of allowed-by-the-compiler-C that is acceptable for us to use. In other words, the C standard can say all it wants; its the C users who in the end defines the (practical) C language. It a bit like if physics would say "Our universe have 11 dimensions. Go use all of them!", but all known users of the universe are three-dimensional beings, thus, the accepted subset of the universe is three-dimensional. Sorry to break it to you, physics, but that's how it is.

Language features are all about what the community around the language make of the language. In a way, language features are just as much a technical aspect of the language as a social aspect of it. Example: is a language feature that's not accepted by the community really a feature, or is it just useless language complexity? More extreme example: a language without users but with extremely powerful features; effectively, does that language have any features at all?

I would also say that anyone aiming to develop a successful programming language (without the backing of a *caugh* Sun huge *caugh* Microsoft corporation) needs to have equally good eye for the technical aspect as well as the social aspect. (S)he needs to understand the social processes involved for getting a community of users who agree (hopefully with the language designer) on how the language should be used. (I think python is good example of such community, by the way).

What about software?

Developing software is also a social process. For example, you get requirements from your customer, you discuss the requirements in order to understand them, and you implement them. Implementing requirement are also a social process: you design the code by discussing it with your colleagues. And what words do you use for doing that?

You use words like object, generic, sort, inheritance, stack, tree, operation, method, message, reuse, client, algorithm, allocation, port, framework, mapping, service, channel, process, decoupled, assumption, resource, provider, input, interface... I could go on forever, but the point is that none of these words really mean anything if we humans don't agree on what they mean. The computer, framework, or programming language has no opinion on what "decouple the client's mapping algorithm from the port allocation" means, but programmers do. It's important it means that same to all programmers involved.

Soft and hard

How does this relate to programming language features? I think there two different kinds of features: hard features that was (deliberately) designed into the language, and soft features that are concepts and idioms that have evolved from using the language.

Hard features are concrete. You can make a list of hard features by reading the language specification. Soft features, on the other hand, are not. They are embedded in the community and to enumerate them you need to vibe with it for a while. Hard features are taught in classes and in books; soft features are learned by hacking, hacking, living and breathing, and some more hacking.

Example: C++ templates. Originally intended to provide better type-safety when writing generic code, like std::vector. The C++ community has then discovered that templates can be used for much, much more (like Boost.Spirit). There are a lot of template code written to implement various kinds of abstract features, e.g., compile-time if, compile-time strings, domain specific languages, etc. The hard feature is "write type-safe generic code". The soft features are "compile-time if", "embedded DSL", and even "it's hard, but you can evaluate everything at compile-time".

The D language took these soft features of C++ templates (e.g., compile-time if, embedded DSL) and integrated them into the core language. Thus, enabled more programmers to use them, because of easier syntax, error messages, compiler support, documentation, etc.

So when a C++ programmer talks about enabling or disabling some piece of code (s)he needs to think about some abstract concept like the enable-if template, while a D programming just thinks "static if". In fact, I don't think the D programmer even thinks "static if" because it's so natural to them, just as the more common "dynamic if" is so natural to all of us. The D programmer probably thinks in entirely other abstract concepts because his/her mind is free from the horrible details of C++ templates meta-programming.

You may argue that our mind is very good at abstracting and that this isn't a problem in practice, but I don't think that's true at all. Example: very few C++ programmer have every done something like an template computing the sinus of an angle, so when they're told to optimize a piece of code doing trigonometry what they'll do is to use some kind of table look-up. A D programmer, on the other hand, will simply slap together a sinus function that can be evaluated statically by the compiler because compile-time evaluation is nothing magic to her/him. (In fact, in D 2.0 match function will automatically be evaluated at compile-time if their arguments are constants).

What I'm saying here is that compile-time evaluation is a (hard) language feature of D but not of C++ (where it is an soft feature). Sure, you can in theory do compile-time evaluation of everything you need in C++ (templates are Turing complete), but not in practice because it's so hard that you actively avoid it. Thus, in most programmers conscious mind, C++ does not have compile-time evaluation. Similarly, you can do object-oriented programming in C, but you probably don't because it's hard and littered with horrible details. Thus, C is in most programmers mind not a object-oriented language. It's possible to do structured programing in Commodore BASIC, but most of us don't think of it like that. Got my point yet? Good.

Ok, so what?

By now you are probably thinking "that's all very interesting, but how is this useful?". Well, I did say that this post was a rambling, didn't I? :)

Seriously though, I don't really think any of this will make you a better software developer, but I think it could be useful if you are developing an tool and there's a community of users around it. Be sure to note what kinds of words the users uses, what features they ignore, what idioms they invent, etc. Integrate the words and idioms into the tool and it's documentation to make the experience for a new user of the application more consistent.

Design for optimizability

2010-06-09T16:30:00.000-07:00

Only optimize when you found a bottleneck by measuring. That's what we all have been taught, right? It's a good rule. But is it really right? What if you're designing a performance critical application? Should you really be ignorant about performance until you measured and found a bottleneck?

I say: don't optimize, but plan for optimizability. I think Dwight D. Eisenhower said it best, though

Plans are nothing; planning is everything.

And now a disclaimer. I am not encouraging over-design in this post. Neither am I proposing that you should analyze every silly detail of your application domain before you start coding. I encourage you to start hacking on you application without worrying about performance, because you know (if you follow the tips that follows and use your brain) that you can optimize it later. Knowing that you can rewrite that slow and memory-hungry Ruby script into a snappy C program (that don't use any heap memory at all) makes it so much easier to sleep at night. Believe me.

Ok, now let's get going!

Caring about planning

Planning for optimizability means that you make sure that:

seams are placed to allow optimizing,
system-wide concerns are encapsulated,
it's possible to do design lowering later on,
algorithmic decisions are delayed,
intelligence can be moved from data to code to data,
it's possible to move run-time aspects to compile-time,
you know your tools.

We will now go through the first three of these bullets one by one and discuss them in detail. I will discuss the remaining four in a later post.

Seams and optimization borders

A seams in software design is a some-what vaguely defined concept. If two components of a software design are loosely coupled, we say that there is a seam between them. In other words, seams separate the design into parts that can vary independently of each other. Inheritance and dependency injection is often used to achieve this in object-oriented systems; function pointers play a similar role in procedural programming.

Since planning for optimizability means that we wish to make it easy to replace slow code with faster, we thus should place seams in the design such that they surround potentially slow code. This implies that design seams also are optimization borders; borders over which optimizations cannot easily be done without affecting other parts of the system.

This doesn't mean that it's impossible to optimize over optimization borders, just that other parts of the system will be affected by it. Thus, optimizing over optimization boarders is harder than optimizing within them. Let's take an example.

Assume that we iterate over a a large list in a performance critical part of our application:

void Foo::iterateOverLargeList(std::list<Thing> l) {
 for (int i = 0; i < l.size(); i++)
   l[i].doEasyCalculation();
}

Where should we place the design seams in this code? Or, more concretely, how do we use virtual functions to enable us to optimize this piece of code as much as possible without affecting the surrounding code? As I see it, we have the following alternatives:

make Thing::doEasyCalculation virtual,
make Foo::iterateOverLargeList virtual, or
encapsulate std::list<Thing> in a new class ThingList, move iterateOverLargeList to ThingList, and make it virtual.

Of these three alternatives 3) gives us the most freedom to increase the performance of the loop, because it allows us to do not only optimize how we iterate, but also change the underlying data structure. For instance, changing from std::list (a linked list) to std::vector (essentially a linear array) will make the access pattern linear, thus the (L1, L2, L3) cache can do a better job.

However, 3) is also the option that is the hardest to refactor to, because we have to change every part of the application that uses the std::list<Thing> list. So, if our application is large, this may involve a lot of refactoring work. Thus, if we choose 3) early in the development we don't have to refactor so much later. In other words, early understanding of the domain, the application's use-cases, and the application design, is important for us when designing for optimizability.

This example touches on another important tool when designing for optimizability: encapsulation. We will now discuss this in greater detail.

Concerning encapsulation

One of the worst kind of optimizations you can do is to optimize something that affect the entire system, e.g., the data flow. A global property like is a system-wide concern and having the system's performance depend on such property is very very bad. We need to encapsulate these global properties to make sure that there are design seams that enable us to optimize them when we need to.

This means that we need to design our code such that if we need to optimize something, that something is encapsulated into a single class (or few classes). This does not mean that we should encapsulate every little petty detail, though. It does mean, however, that we need to put a bit more effort in understanding our application, and then think about its design, data flow, etc. This is actually something we should do anyway even if we're not designing for optimizability, because understand the current design of the application make it easier to improve it.

When we got a firm understanding of the application and how it will be used, then we can identify the system-wide concerns, and only then can we start to encapsulate them to make them possible to optimize in the future.

Avoid memory copying

Reading data from memory is one of the most costly thing a modern CPU can do. If the data is in (L1) cache reading memory is fast (3-5 cycles or so), but if the data needs to be read from main memory it takes 100 times longer. That's right: 500 cycles to read a single bit of data. Writing data to main memory is also very costly operation, thus, copying is extremely costly operation.

With this in mind, it may be tempting to return a pointer to a shared data buffer instead of returning a copy of that data. For example:

class Thingie {
 int* stuff;
 // constructor that initializes 'stuff'.
 int* getStuff() { return stuff; }
};

This may look efficient since there is no memory copying going on. However, this design is horrible with regard to encapsulation. For instance, what if we need to modify the returned data in some other part of the program without affecting the Thing instance? In that case we need to make a copy and modify the copied data. But what if that copied data is returned just like the int* stuff above? And what if it needs to be modified in some other part of the program? Then we need to make another copy!

In situations like this, you need to take a step back and look at the data flow through your application and then try to optimize it to minimize the number of copies. This is not an easy task, so we really wish to avoid doing it, or at least make it easier for us to do. Is there some way to design our application (with little extra effort) from the start to make optimizations like this possible (without huge redesigns)?

In the example above, the system-wide concern is how the int* stuff data is passed around in the application and how to make sure that it is not copied unnecessarily.

Let's rewrite this example a bit into:

class Thingie2 {
 MyBuffer stuff;
 // constructor that initializes 'stuff'.
 MyBuffer getStuff() { return stuff; }
};

Since the data now is encapsulated in MyBuffer (and the entire application uses MyBuffer to refer the the data), we can now implement a lot of optimizations that affect the data-flow of the application. For instance, we can implement copy-on-write semantics and reference counting; this would be extremely hard to do without using MyBuffer to encapsulate the data-flow, which is a system-wide concern.

Design lowering

The term instruction lowering is an optimization technique used in compilers to generate more efficient code. For example, the C code a = 16 * b; can be implemented (in pseudo-assembler) by a multiplying operation A = MULT(16, B) but also by a simpler and faster shift operation A = SHL(4, B).

With the term design lowering I mean a similar concept: reimplementing the design in a simpler and faster language or platform, or using faster language constructs or data structures. Examples of such design lowering include:

rewrite Python code in C,
replace reflection-heavy Java code with simpler non-reflection code,
using a simple array instead of a hash map or a linked list,
using the memory layout of C structs as data format instead of XML in files, over network, etc
use hardware acceleration like graphics cards.

Design lowering can easily increase the performance 10-100 times or even much more. Lets take an example of this.

A story of left and right

Imagine two small program left and right; left generates data and sends it to right, which sums the received data. Here is the first version of this pair of programs implemented in Python:

--- left.py ---
a = { "first":[1, 123], "middle":[1, 2, 456], "last":[1, 2, 3, 789] }
for i in xrange(0, 1000000):
 print a

--- right.py ---
import sys
total = 0
for line in sys.stdin:
 a = eval(line)
 total = total + sum(a["first"]) + sum(a["middle"]) + sum(a["last"])
 print total

Translating this Python code into C++ idioms this becomes:

--- left.cc ---
struct Data {
 Data() {
   first[0] = 1; first[1] = 123;
   middle[0] = 1; middle[1] = 2; middle[2] = 456;
   last[0] = 1; last[1] = 2; last[2] = 3; last[3] = 789;
 }
 int first[2];
 int middle[3];
 int last[4];
};

int main() {
 Data data;
 for (size_t a = 0; a < 1000000; a++) {
   for (size_t b = 0; b < sizeof(Data); b++)
     putchar(reinterpret_cast<char*>(&data)[b]);
 }
}

--- right.cc ---
struct Data {
 int first[2];
 int middle[3];
 int last[4];
};

int main() {
 Data data;
 long total = 0;
 for (size_t a = 0; a < 1000000; a++) {
   for (size_t b = 0; b < sizeof(Data); b++)
     reinterpret_cast<char*>(&data)[b] = getchar();
   total += data.first[0] + data.first[1] + data.middle[0] + data.middle[1] +
   data.middle[2] + data.last[0] + data.last[1] + data.last[2] + data.last[3];
 }
 printf("%ld\n", total);
}

And running them we get:

$ time ./left.py | ./right.py
1378000000

real 1m3.284s
user 1m14.057s
sys 0m0.256s
$ g++ -O2 right.cc -o right && g++ -O2 left.cc -o left && time ./left | ./right
1378000000

real 0m0.763s
user 0m1.292s
sys 0m0.088s
$ echo 74.067/1.292 | bc
57

Thus, the C++ version of these little programs are 57 times faster than the equivalent Python code. But this is not the neat thing... Let's get back to discussing design lowering.

Where to do design lowering

The neat thing is that you can implement left and right in Python without worrying about performance because they are easily design lowered to C++. I can say this because left and right comes in pair; if you redesign one side you also redesign the other. In other words, the details of the implementations are free to change in ways to make them execute more efficient. Thus, it's easy to do design lowering.

However, this would not be the case if left sent data to an unknown part via a predefined protocol. If this was so, then reimplementing left in C++ would probably be considerably harder. In other words, design lowering left would be less feasible. It would still be possible to do, though.

In summary, design lowering can be used as a plan for optimizability when the design can vary in ways that make it feasible to implement faster in another language (or data structure, etc). How the design can vary depends on many things, though, thus design lowering is not always easy to do without first refactoring the design.

As before, design lowering is not something you get for free, though: you need to ha good understanding of how/where the application will be used. When you understand your application, you're more likely to make correct assumptions of what parts of that can be design lowered and which parts that can't.

Conclusions

Just like optimizing, designing for optimizability requires us to understand the problem. We cannot escape it: to do something good, we need to know what "good" is, and to know what "good" is we need to understand the domain. Beware of over-analyzing though: concentrate on system-wide concerns that are likely to affect performance, and know how the design can vary to enable design lowering. Also, make sure that design seams don't hinder optimizability.

There are still much more to discuss on this topic, so stay tuned!

LLVM talks

2010-05-29T06:20:00.000-07:00

A few very interesting presentations of LLVM from the LLVM developer's meeting 2009.

Find parent pid given a pid

2010-05-26T08:04:00.000-07:00

A few days ago I needed to get the parent process id (pid) of a given pid on Linux. There are shell commands for that, .e.g, ps -o ppid= p the-pid, but I needed to get the pid programmatically from C.

For some reason the getppid function can only return the parent pid of the current process, not any process. I searched the web after an alternative solution but I found nothing.

So I took a peek at the source for the ps command, which revealed that there is a function called get_proc_stats defined in proc/readproc.h that (among other things) returns the parent pid of a given pid. You need to do install libproc-dev to get this function. You can then do:

#include <proc/readproc.h>
void printppid(pid_t pid) {
proc_t process_info;
get_proc_stats(pid, &process_info);
printf("Parent of pid=%d is pid=%d\n", pid, process_info.ppid);
}

and compile it with gcc the-file.c -lproc. I hope you find this useful.

A story of being humble with confidence

2010-05-16T04:12:00.000-07:00

I just read a post over at SKORKS, a blog I read every now and then. He writes a bit about The Art Of Unix Programming, which got me reminded of when I first heard of that book. I then remembered reading The Art of Humble Confidence and I felt that I really had to write something along those lines. Here goes.

It was 2006 and I was working with a handful experienced colleagues on a project trying to radically increase the usefulness two large applications by making them work together. This was an extremely interesting time for me and they taught me a lot that I today value very highly.

One day one of my colleagues who was sitting next door to my office knocked gently on my open door to get my attention. He said, "Sorry, am I interrupting you? Do you have a moment?" He was humble as always, speaking slowly and silently to make sure that I wouldn't be anxious about what he'd say next.

"Do you remember what we talked about before?" Even though I wasn't really sure to what he was referring I replied "sure", thinking that I'd get what he means when he starts to talk about it.

While he slowly pulled up a chair and sat down next to me he said, "did you consider what we said about the MessageReceiver class?" I now realized that he was referring to our discussion over a coffee they day before. I nodded, remembering that he didn't really liked how I designed some part of the system we were working on.

Though I couldn't really understand his argument from yesterday I had redesigned it anyway to be more in line with his suggestions. Making a poor design made me feel a bit bad and not understanding why it was bad made me feel worse. But I didn't want to ask him explaining it (again) because I didn't want to look (more) stupid. That would be even worse. Or so I thought.

I guess he realized my anxiety about not properly understanding his design, because he next said "I did a pretty crappy job explaining why that class needed to be changed, right?" He smiling and chuckled, "I was always better at instructing computers than people." We laughed.

"Anyway", he said, "I read this book a bit yesterday and I think chapter 10 explains what I mean much better than I ever can." He handed me the book and said "you can borrow it if you like." He laughed again and added "but not for too long. I need to read it soon again since you ask so incredibly interesting and hard questions." He got up from the chair and said "let's go and get some coffee." He smiled and added "I'm 'starving'".

I grabbed my cup and we walked over to our colleagues offices and asked them to joined us. As we walked to the coffee machine I felt like I was in the greatest group of developers there was. Everyone was working for our mutual goal while having fun, learning, and teaching at the same time.

My colleague had basically just asked me questions, yet managed to tell me something. Yes, he evened managed to tell me what to do. But more importantly, he taught me that you will never know everything and that working in software is a constant process of learning.

My worst mistakes (since two days)

2010-05-11T05:19:00.000-07:00

I just spent two days on writing, testing, rewriting, testing, debugging, etc, a piece of code only to find the error to be five misplaces pixels. Learn from my mistake: never use i and j as index in nested loops.

What made this problem worse than it should have needed to be was that the erroneous code was in a test-case. Learn from my mistake: never write complex control flow in your test code.

What made it take longer than it should have take for me to find this mistake was that I didn't assert my assumptions. Learn from my mistake: always assert, never assume anything of any piece of code when you're chasing weird behavior.

Threading is not a model

2010-05-07T11:19:00.001-07:00

I just saw the Threading is not a model talk by Joe Gregori from PyCon 2010, which I found very interesting. It has some history about programming language development, and some discussion about design of every-day physical stuff and every-day programming language stuff. I especially find the idea of sufficient irritation very funny and interesting. :)

The main part of the talk is about different ways of implementing concurrency, mainly CSP (Communicating Sequential Processes) and Actors. Interesting stuff presented by a good speaker.

Must-know tricks for safer macros

2010-05-07T07:29:00.000-07:00

Almost every developer knows to stay away from (C-style) macros unless it's absolutely necessary to use them, or that is saves a lot! of code to use them. And when they do use them, they make sure to write them properly. I won't go into the details of the traditional ways of writing good macros (as in "harder to misuse, but still possible") because there are several pages like that already (see the links above). Instead, I'll discuss an entirely different way of making macros more safe.

Why macros are hard

Let's describe the problems with macros with an example. This simple macro definition multiplies the provided argument with it self to yield the square of the input:

#define SQUARE(x) x * x

Looks simple right? Too bad, because its not that simple. For example, what happens when the following code is evaluated:

int a = 2;
int b = SQUARE(a + 1);

I tell you what happens: all hell breaks loose! The above code is expanded into:

int a = 2;
int b = a + 1 * a + 1;

thus, b will equal 2 + 1 * 2 + 1 = 5. Not quite what we expected by looking at the code SQUARE(a + 1), right? All in all, macros looks simple and harmless enough, but are not simple at to get right. And definitely not harmless, on the contrary, it's extremely easy to get bitten horribly bad. We are now going to discuss how to make macros a bit more safe to work with.

Making them softer: check your typing

Types are an important part of the C language and even more so of C++ with all its classes, templates, and function overloading. Macros, though, are simple text substitution without knowledge of types, so macros fits very badly in the normal type-centric C/C++ world we are used to work with.

For example, you give a function the wrong types as argument. What do you get? A type error. No code is emitted by the compiler. This is good. On the other hand, if you give a macro the wrong types as argument, what do you get? If you're lucky some kind of error; maybe a syntax error, maybe a semantic error. If you're unlucky, though, you won't get any error at all. The compiler will just silently emit ill-behaving code into the .o-file. This is extremely bad because we're fooled into believing our code works as we expects it to.

Luckily, there is a way of making macros more safe in this regard. Let's take simple, yet illustrative example: a macro called ZERO that takes one argument, which is a variable, and sets it to 0. The first version looks like this:

#define ZERO(variable) variable = 0;

and is intended to be used inside a function like this:

void func() {
int i;
ZERO(i);
// more code here...
}

Simple but not safe enough for our tastes. For example, this macro can be called as ZERO(var0 += var1) and it will produce code the compiler accepts, but that code does not have the behavior the macro was intended to have. The macro will expand this code to var0 += var1 = 0, which (I think) is equivalent to var1 = 0; var0 += 0. Whatever the expanded code does, its not what we intended ZERO to do. In fact, ZERO was never designed to handle this kind of argument and should thus reject it with a compilation error. We will now discuss how to reject such invalid argument. Here goes...

Halt! Identify yourself!

To make sure that the compiler emits an error when the ZERO macro is given a non-variable as argument, we rewrite it to:

#define ZERO(variable) \
{ enum variable { }; } \
variable = 0;

That is, an enumeration is declared with the same name as argument inside a new scope. This makes sure that the argument is a valid identifier and not just any expression, since an expression can't be used as a name for an enumeration. For example, the previously problematic code, ZERO(var0 += var1), will expand to:

{ enum var0 += var1 { }; } var0 += var1 = 0;

which clearly won't compile. On the other hand given correct argument, e.g., the code ZERO(var0), we get

{ enum var0 { }; } var0 = 0;

which compiles and behaves as we expect ZERO to behave. Neat! Even neater, the compiler won't emit any code (in the resulting .o-file) for the extra "type-checking code" we added, because all it does is to declare a type, and that type is never used in our program. Awesomeness!

So we now have a pattern for making sure that a macro argument is a variable: declare a enumeration (or a class or struct) inside a new scope with the same name as the variable. We can encapsulate this pattern in a macro VARIABLE and rewrite ZERO using it

#define VARIABLE(v) { enum v { }; }

#define ZERO(variable) \
VARIABLE(variable) \
variable = 0;

Note that with a bit of imagination, the definition of ZERO can be read as the signature (VARIABLE(variable)) followed by the macro body (variable = 0;), making macros look more like function definitions that we are familiar with. This wraps up our discussion about variables as macro argument. But read on, there's more!

Constants

Let's assume that we wish to generalize ZERO into another macro called ASSIGN that sets the provided variable to any constant integer expression not just zero. For example, 1, 2, and 39 + 3 are valid arguments, but i + 2, 1.0, and f() are not because those are not constant integers. One way of defining such macro is as follows:

#define ASSIGN(variable, value) \
VARIABLE(variable) \
variable = value;

that is, we simply added an argument value that variable is assigned to. Simple, but as usual with macros, very easy to misuse. For example ASSIGN(myVar, myVar + 1) will assign myVar to a non-constant value, which is precisely what we didn't want ASSIGN to do.

To solve this problem, we recall that an enumerator (a member of an enumeration) can be assign a constant integer value inside the enumeration declaration. This is exactly the kind of values we wish ASSIGN to accepts, thus, we rewrite it into the following code:

#define ASSIGN(variable, value) \
VARIABLE(variable) \
{ enum { E = value }; } \
variable = value;

This version of ASSIGN only accepts variables names for its first argument and constant integers for its second argument. Note, that the constant can be a constant expression, so things like ASSIGN(var0, 1 + C * D) will work as long as C and D are static const int's. If we extract the pattern for checking that an argument is a constant integer int CONST_INT, we get the following two definitions:

#define CONST_INT(v) { enum { E = v }; }
#define ASSIGN(variable, value) \
VARIABLE(variable) CONST_INT(value) \
variable = value;

As for the final version of ZERO, the definition of ASSIGN can be read as the signature of ASSIGN followed by the body of it.

Types

Now we will modify ASSIGN into DECLARE; a macro that declares a variable of some type, which is provided as argument to DECLARE. Similar to ASSIGN, DECLARE initializes the variable to the provided constant integer expression. Our first implementation of such macro is:

#define DECLARE(type, variable, value) \
VARIABLE(variable) CONST_INT(value) \
type variable = value;

However, the compiler will accept code like DECLARE(int i =, j, 0) (assuming j is delcared variable and i is not). So following our habit from previous examples, we wish to make it a bit safer by making sure the type argument actually is a type, e.g., int, MyClass, or MyTemplate<MyClass>. We do this by having the macro using type as a template argument, as follows:

template<typename TYPE> class TypeChecker { };
#define DECLARE(type, variable, value) \
VARIABLE(variable) CONST_INT(value) \
{ class Dummy : TypeChecker<type> { }; } \
type variable = value;

This definition is much more safe from misuse than the previous; code like DECLARE(int i =, j, 0)won't compile. If we extract the argument-checking code into a separate macro, TYPE, we get:

template<typename TYPE> class TypeChecker { };
#define TYPE(t) { class Dummy : TypeChecker<t> { }; }
#define DECLARE(type, variable, value) \
TYPE(type) VARIABLE(variable) CONST_INT(value) \
type variable> = value;

As before, note that we can read this definition as two parts: first the macro signature and then the macro body. Compiler enforced documentation FTW!

Everyone's unique

To not make this post too long, I'll stop giving background and reasons for the rest of the type-checking macros I'll present from now on. I'll just briefly describe what they do.

The following macro makes sure that a list of identifiers only contains unique identifiers:

#define UNIQUE(is...) { enum { is }; }

Note that this macro requires that the compiler supports macro varargs. It used as UNIQUE(name1, name2, name3), or UNIQUE(name1, name2, name1) where former is ok, but the latter will emit an error.

Comparison

These macros compares constant integer expressions in various ways. The basic idea here is that the size of an array must not be negative and that the boolean value true is converted into 1 in a integer context and false is converted to 0. We use this to implement the macro IS_TRUE as follows:

#define IS_TRUE(a) { struct _ { int d0[!(a)]; int d1[-!(a)]; }; }

Many comparison macros are then trivially implemented using IS_TRUE, for example:

#define LESS_THAN(a, b) IS_TRUE(a < b)
#define EQUAL(a, b) IS_TRUE(a == b)
#define SMALL_TYPE(t) IS_TRUE(sizeof(t) < 8)

You may ask yourself why such macro is needed. Shouldn't templates be used here instead? I agree, but there are some of us who is (un-)lucky enough to use C and not C++...

Let's get general

The general idea we've used so far is to have two parts of the macro. One part that implements the desired (visible) behavior, and another part that works like type-checking code. The type-checking code is implemented by having short trivial side-effect free pieces of code that only will compile under the assumptions you make on the argument. For example, the argument is a variable, or the argument is a constant integer expression.

Of course, it may still be possible to fool the "type-checking" code, but its much less likely to happen indeliberately, which is the most important cases to find.

Descriptive error message?

In short: no. The error messages got from any of these type-checking macros are extremely non-descriptive. However, any error message, even weird and non-descriptive ones, is still better than no error message at all and ill-behaving binary code.

The sum of all fears

Does the approach described here solve all problems with macros? No, it does not. It does however, make it less of an issue. It is possible to write macros that are type-safe and behaves in a good way (by which I mean: either compiles into correct code or does not compile at all). However, I'm pretty sure that are uses for macros that cannot be covered with this approach.

Despite this, I highly recommend to use this idea when you write macros. It will make the macro better in most way possible, e.g., safer and better documented. Compiler-enforced documentation, even! Just like type declarations in all your other C/C++ code. Neat, don't you think?

Beautiful Dependency Injection in C++

2010-05-02T05:56:00.000-07:00

Dependency injection is a very nice way of making classes testable and more reusable. An instance of a class Foo that a class NeedsFoo depends on are simply injected into NeedsFoo's constructor. That is, the client of NeedsFoo (the code instantiating it) controls how Foo instances are created, thus, NeedsFoo is more decoupled from the rest of the system. Why? Because any object that is a Foo can be used with NeedsFoo: subclasses of Foo, instances shared other objects, or a Foo created in a special way (e.g., a singelton or proxy to a remote object). Compare this to the traditional non-dependency injection way, where Foo is instantiated by NeedsFoo, thus making it impossible for the client to control what kind of instance of Foo that is used by NeedsFoo.

Object life-time management complicated

Dependency injection is straight forward to do (correctly) in languages with automatic memory management like Java and Python, but it's much harder to get right in languages like C++ which forces you to manage memory manually. Of course, it possible to do simply delete the injected object in NeedsFoo's destructor; like:

class NeedsFoo {
Foo* foo;
public:
NeedsFoo(Foo* foo) : foo(foo) { }
~NeedsFoo() { delete foo; }
// Methods using foo that needs to be tested.
};

However, this is far from an optimal solution because now all objects given to any instance of NeedsFoo must be heap allocated because we delete them in the destructor. So even when NeedsFoo is stack allocated (e.g., for performance reasons), its Foo object must be heap allocated. Besides being hard to get right, heap allocation is extremely costly compared to stack allocation. So if we want performance we're screwed, and since we're using C++ I assume that performance is important. If it's not, we could just as well use some other language.

Another reason, arguably more important, for that doing delete in the destructor is bad! bad! bad! is that the injected object cannot be easily share with some other part of the application: who knows when (and if) the object should be deleted...? NeedsFoo don't know it, that's for sure.

How do we fix this? Well, we could simply remove the delete from the destructor:

class NeedsFoo {
Foo* foo;
public:
NeedsFoo(Foo* foo) : foo(foo) { }
// Methods using foo that needs to be tested.
};

Easy to test, right? Yes. Easy to use in production code? Well, kind of. Easy to use correctly in production code? Definitely not!

Why? Because, as said before, C++ lacks garbage collection thus the injected object needs
to be managed manually somehow. For example using referenced counting pointers, or making sure that foo are has the same life time as the NeedsFoo instance. We will focus on the latter for the remaining of this post. But first a short discussion why it is common that the injected objects (e.g., a Foo instance) should be destroyed at the same time as the object they are injected into (e.g., a NeedsFoo instance).

Let them here on be joined and never parted

Dependency injection is used a lot to make code more testable. However, in my experience it is often the case that if it wasn't for testing, dependency injection wouldn't be needed because its always the same kind if objects that are injected (e.g., the Foo instance is always instantiated the same way for all NeedsFoo instances). In a way using dependency injection is a kind of over-design: the code is more generic than it needs to be, thus, more complex that it needs to be.

Despite this, we still do dependency injection and we still consider it part of a good design. Why? Because, as said, it makes the code testable. We consider testable code to be more important than simple design. I can accept that for languages with garbage collector, but when you do the memory management manually the design get much! much! much! more complex. Not good, not good. Infact it's terrible. The reason it's terrible is that memory management is a program global problem that isn't easy to encapsulate.

For example, if I call malloc in my code and pass the pointer to a function defined in a library, how do I know if that memory is deallocated by the library? I can't. Not without manually inspecting the source code of the library. How about using smart pointers? Doesn't help much. The library is most probably a C library. Crap.

So, how can we do dependency injection to simplify testing while keeping memory management simple? This is what we will discuss now, my friend. Let's go!

Object life-time management simplified

One way making sure that a bunch of objects is created and destroyed at the same time is to stuff them into a class:

class Concrete : public NeedsFoo {
Foo foo;
public:
Concrete() : NeedsFoo(&foo) { }
};

Here, an instance (actually an instance of a sub-type) of NeedsFoo is created and injected with a Foo object. Since both object are held in a Concrete instance, the NeedsFoo and the Foo instances will be destroyed at the same time. Sweetness!

This approach works well under the assumption we never need to inject a subclass of Foo to NeedsFoo. (Well, of course it's still possible to inject a subclass to NeedsFoo, but if we do that we are back to square one since we need to manage those objects' lifetime manually; Concrete is only usable for Foo objects not subtypes of Foo).

So, for classes that injected with the same kind of instances, this approach solves the memory management problem. Goody-goody!

Lies, damn lies, and untested source code

Wait, what's that? Do you the cries? Breaking news! Lies on the Internet! Read all about it! It sad, but true. And I'm a bit ashamed to tell the truth.. but here goes.

In the code for Concrete above, the injected object Foo is not constructed when it's injected into NeedsFoo's constructor. Why? Because the constructor of base classes are called before the constructor of derived classes. In other words, NeedsFoo's constructor is called before Concrete's, thus, before Foo's constructor. Similarly, when NeedsFoo's destructor is called, Foo has already been destroyed. Why? Because NeedsFoo's destructor is called after Concrete's.

So what does this mean for us? Is everything we done here useless? Fortunately, it is not that bad. All we need to do is make sure Foo isn't used in the constructor or destructor of NeedsFoo. More precisely, we must not in any way touch the memory where Foo will be/was constructed. In fact this is good rule in any case, because constructors shouldn't do any work any way. Constructors should ideally just initialize the class' members. Destructors shouldn't do any work either (except for destroying object, closing sockets, etc., of course).

Making it testable (my favourite pass-time)

Let's take a step back before we continue and look at the piece we have. Note that NeedsFoo uses Foo which is a concrete class, not an interface. Thus, there is no way to inject an object that does not share any implementation with Foo (e.g., because Foo's constructor is called even for derived classes). But this is precisly what we need for testing! Crap! How to solve this? Templates to the rescue!

I know what you think: what a stupid template-loving masochistic guy. Yeah, you're half-right. I'm a guy. But not a template-loving masochistic one. Just a guy, who actually, do think templates can be put to good use (as in: std::vector). However, templates can also be used in way they weren't designed for (as in: most of Boost). There are better ways of doing so-called "template meta-programming"(affectionately called so by the Boost guys; disgustedly called so by sane people[1]). The D language is a good example of this. Check out this talk by the inventor of D, Walter Bright, about how meta-programming should be done.

Anyway, if we use templates we get:

template<class TFOO>
class NeedsFoo {
TFOO foo;
public:
NeedsFoo(TFOO foo) : foo(foo) { }
// Methods using foo that needs to be tested.
};

and the derived class that manages the injected objects life-time becomes:

class Concrete : public NeedsFoo<Foo*> {
Foo foo;
public:
Concrete() : NeedsFoo<Foo*>(&foo) { }
};

So, now we have a class that contains the code with interesting behavior (NeedsFoo) and a class that contains the construction and life-time management of the injected objects (Concrete). Furthermore, NeedsFoo can be instantiate with any kind of class that looks like a Foo class, e.g., a stub implementation of Foo. This means that the interesting code can be tested easily because of dependency injection, while still being easy to instantiate and pass around.

Also, note that the template part of the class is never visible in the production source code. That is, all other parts of the production code uses Concrete, not NeedsFoo. Furthermore, the implementation of NeedsFoo does not need to be given in the header file as is traditional for template classes. The reason is that we know all possible types TFOO will refer to. Thus, the build-time will no increase significantly using this approach compared to a initial code we had.

Another important thing to note is that this style of dependency injection is in some ways more powerful than the Java-style dito, because NeedsFoo can actually instantiate the template parameter class TFOO itself. Of course, it requires TFOO to a have a matching constructor, though. In Java, you would need to write a factory to achieve something roughly equivalent.

Pros and Cons

There are several things to consider with the code we started with and what we ended up with. First of all, the code for NeedsFoo has become more complex. This is bad, but I would argue that the test-cases for the production code will be much simpler. Thus, the total complexity (of production code + test-cases) is less for the templated code, than for the code we started with. This is good.

Second, the production code we ended up with is more generic yet maintains a its original simple interface. I say this because the main implementation (NeedsFoo) is now a template, thus, any class that looks like Foo can be used instead of Foo. Yet the interface is simple, since the most common case (when Foo is used) is still simple because of the Concrete helper-class. This is good.

Third, the performance of the templated code should be the same as the original code, because there are no unnecessary virtual calls. Virtual methods are traditionally used for making a class testable, but we managed to avoid those here. Instead we use templates, which means that methods calls can be statically bound to a concrete method implementation. Thus, the compiler can do a better job at optimizing the code. This is good.

The major drawback with this approach is that the error messages emitted by the compiler usually gets harder to read. This is common for templated code though, since the error messages contain a bunch of references to template and the types of the template parameters (here FOO). For someone who is a bit familiar with the compiler's error messages this should be very hard to figure out what the error messages mean, though. However, compared to a non-templated solution, the error messages are much harder to understand for someone not used to them.

I recommend you to try this way of doing dependency injection in C++. I'm not saying its the best way of doing under all circumstances, but I am sying its good card to have in your sleeve. A card that may come handy sometime.

[1] The Boost guys have my fullest respect for what they are doing. It is a really impressive project that has helped me more time than I can count. But that doesn't change the fact that what they are doing is insane.

Best TED-talk ever

2010-05-01T13:37:00.000-07:00

TED is an extremely good place to find interesting (short) talks about various topics. You can literally spend days there watching really high quality presentations ranging from musical performances to science talks. Today, though, I saw something that bets every other TED-talks I've ever seen before.

It was short and witty, it was science and humor, and it was refreshingly different. And best of all, you actually learnt something useful! Stop wasting your time here. Get over there and see it now!

Lambda the Ultimate Joker

2010-04-24T01:30:00.000-07:00

From Lambda the Ultimate Weblog:

All people are lazy, but very eager when evaluated.

Funny stuff for all us language nerds. :)

Testing generated code

2010-04-18T09:55:00.000-07:00

I started to write this post roughly one and a half years ago. I never finished writing it until now for whatever reason. Here's the post.

<one and a half years ago>
At work I'm currently devloping a little tool that generates Java code for decoding messages (deeply nested data structures) received over a network. To be more precise, the tool generates code that wraps a third-party library, which provides generic access to the messages' data structures. Slightly amusing is that the library consists of generated Java code.

The third-party library is... clumpsy to use, to say the least. Its basic problem is that is so generic/general that it's feels like programming in assembler when using it. Ok, I'm exaggerating a bit, but you get the point: its API is so general it fits no one.

There are several reasons for hiding a library like this:

simplifynig the API such that it fits your purpose;
removing messy boilerplate code that's hard to read, understand, and test;
less code to write, debug, and maintain;
introducing logging, range checks, improved exception handling, Javadoc, etc, is cheap;
removing the direct dependency to the third-party library; and
you get a warm fuzzy feeling knowing that 3 lines of trivial DSL code corresponds to something like 60-80 lines of messy Java code.

I'm developing the code generator using Ruby, which have had its pros and cons. The good thing with Ruby is that is easy to prototype things and ou can do fairly complex stuff really easy.

On the bad side is that I reqularly get confused about what types go where. This isn't to much of a problem from a bug point-of-view since test-cases catches the mistakes I make, but it's a bit of an annoyance if you're used to developing Java with Eclipse like I am. The Ruby IDE I'm using (Eclipse RDT) is not nearly as nice as Eclipse JDT, which is natural since an IDE for a dynamic language has less information available for refactorings, content assist, etc.

I've discovered that a functional style is really the way to go when writing code generators, especially when there are no requirements on performance. This is a nice fit, beacuse Ruby encurage a functional programming style -- or rather, it encurage me.

What keeps biting me when it come to code generators is how to test them. Sure, the intermediate steps are fairly easy to test, that is, while things are still objects and not just a chunk of characters. But how is the output tested?

Usually I test the output (the generated code) by matching it against a few regual expressions or similar, but this isn't a very good solutions as the test-cases are hard to read. Also, if an assertion fails the error message isn't very informative (e.g., <true> was not <false>). Furthermore, test-cases like these are still just an approximation how the code really should look like. For example, I've found no general and simple way of testing that all used classes (and no other classes) are imported. So, it is possible that a bug such as:
import tv.muppets.DanishChef;
wouldn't be found by my test-cases, even though the resulting code wouldn't even compile (do'h! The chef's from Sweden not Denmark!).

Ok, this could be fixed by having some test-cases that actually compiles the output by invoking a Java compiler. Not very beautiful but still possible. Even better, the generated-and-compiled code could be tested with a few hand-written test-cases. These test-cases would test the generated code, alright, but would not document the code at all (since "the code" here means the uby code that genreated the executed Java code). This problem, I'm sad to say, I think is impossible to solve with reasonable effort.

This approach is good and covers a lot of pitfalls. However, it misses one important aspect: generated documentation. The code generator I wrote generated Javadoc for all the methods and classes, but how should such documentation be tested? The generated documentation is definitely an important part of the output since it's basically the only human-readable part of it (in other words, the generated code that implements methods are really hard to read and understand).

Another approach is to simply compared the output with the output from a previous "Golden Run" that is known to be good. The problem here is, of course, to know what is 'good'. Also, when the Golden Run needs to be updated, the entire output of the (potential) new Golden Run has to be manually inspected to be sure it really is good/a Golden Run. The good thing with a "Golden Run" is that documentation in the generated code is also tested and not only the generated code.

The approach I'm using is to have a lot of simple test-cases that exercises the entire code generator (from input to output). Each of these test-cases verifies a certain aspect of the generated code, for instance:

number of methods;
number of public methods;
name of the methods;
a bunch of key code sequences exists in method implementations (e.g., foo.doIt(), new Bar(beer), baz.ooka(boom), etc);
for a certain method the code looks exactly like a certain string (e.g., return (Property) ((SomethingImpl) s).propertyOf(obj););
name of the class;
name of the implemented interfaces;
number of imports;
that used classes are imported;
key frases exist in Javadoc.

In addition to these test-cases, there is are test-cases that simply generates a lot of Java classes and compiles them. The test-cases pass if everything compiles. Finially, some of these generated classes are tested using hand-written JUnit test-cases. For me, this approach worked good and I didn't experience any problems (meaning more problem than normally) with testing the generated code. For the generated documentation, however, there were much more bugs. These bugs didn't get fixed either because it wasn't high priority to fix them. Too bad.
</one and a half years ago>

Looking back at this story now, I would have done things differently. First of all I would not use Ruby. Creating (internal) DSLs with Ruby is really easy and most of the time turn out really nice. I've tried doing similar things with Python, Java and C++, but the syntax of these languages just isn't as forgiving as Ruby's. However, the internal DSL I created for this tool never used the power of Ruby, so it just be an external DSL instead. An external DSL could just as well be implemented in some other language than Ruby.

Second, I would consider just generating helper methods instead of entire classes and packages of classes. So instead of doing:
void setValueFrom(Message m) {
this.value = new GeneratedMessageWrapper(m).fieldA().fieldB().value();
}
you would do
void setValueFrom(Message m) {
this.value = getValue(m);
}
@MessageDecoder("Message.fieldA.fieldB.value")
int getValue(Message m) {
}
where the code for the getValue method would be generated and inserted into the file when the class is built. This way, much less code would be needed to be generated, no DSL would be needed (annotations are used instead), and things like name collisions would not be such a big problem as it was (believe it or not).

At any rate, writing this tool was a really valuable experience for meany reasons that I wouldn't wish to have undone. Considering how good (meaning how much code it saved us from writing) it was a sucess. On the other hand, considering how much time we spent on getting it to work it was a huge failure. As it turns out, this tool has been replaced with a much simpler variant written entierly in Java. Although simpler, it gives the user much more value, though, so its arguable much better then that stuff I wrote 1,5 years ago. My mistake.

Happy two year!

2010-03-31T23:38:00.000-07:00

One year ago this blog celebrated its first birthday. And today, one year later, it celebrates its second birthday! Gasp! Oh, arithmitic, you gotta love it.

During the last year I've written about some crazy stuff, some testing stuff, a lot of compiler stuff, a few things about learning, and even a joke!

I hope some of these posts have been useful for you and that you continue to stop by every now and then to read some of them. Now I'm looking forward to another year of crazy, and (I hope) few useful, ideas and hacks.

Designing (your)Self

2010-03-30T09:41:00.000-07:00

I just saw a very interesting lecture by Davig Unger. Its main focus is the programming language Self, which is a prototyped-based object-oriented language. He also talks about other things: getting the right people to work with you, some of his guiding principles, and even a few comments on getting to know yourself.

David Ungar received the Dahl-Nygaard Senior Prize in 2009 for his work in the field of object-orientation, most notably for Self. He currenlty works at IBM Research.

Commodore 64 Live!

2010-03-15T10:32:00.000-07:00

Do you remember those old arcade machines where, when no one played them, the "computer" would play the games? Kind of like a demonstration of the game instead showing some fancy graphics. I came across the übergeeky page C64 Longplays a few days ago and I feel that I must do my small part to spread the word through the world.

It's basic like those computer-played arcade machines, with the difference that it's actually someone who plays through the entire game. Didn't you solve the third level of Boulder Dash or did you think no one ever cared to finish Ghostbusters? Everything is on C64 Longplays for you to watch.

I personally liked the video of Yie Ar Kung Fu... some fights was really close... the energy bar was down to the last pixel!

The most important skill

2010-03-05T11:51:00.000-08:00

As a software developer you need to have large skill set: knowing the right tools, languages, frameworks, platforms, and so on. To complicate things you need to keep every piece of knowledge updated since the field of computing is changing so rapidly. But what is the most important skill among all these? I argue that it's not knowledge of some key technology that make you more than an average programmer, nor is it how many fixed point combinators you dreamt up, how many open-source project you've started, or how fast you type. If non of these, what is the most important skill?

First let me note that with developer I do not mean someone like Alice who write shell one-liners for her husband Bob to search his photo collection of dogs with hats. I don't mean teenanger Charlie who uses barbed wire and duct tape to hack together scripts to play suitably random mp3s to match his parents' photo slide show from their vacation last summer. What I mean is someone who write code that other developers will maintain, test, read, enhance, etc. In essens I mean developers that work with other developers either directly or through their code.

So, the important part here is work with other developers, which leads me to the heart of this post: the most important skill for a developer is communication. Err, I'm sorry, let me correct that: the most important skill for every developer is effective communication. By communication I mean source code and comments, documentation and specifications, power-point presentations and white-board explanations, mail and phone calls, and so on. I could continue, but I think you've got the point.

A small disclaimer before we continue. I assume that the ones you communicate with want to understand what you say or write. If that's not the case then you have an entierly different problem, and I don't think much in this post can help you. Sorry. Ok, that's that, let's continue.

I've met many very technically skilled developers that, when I tell them I don't understand what you mean, literally repeated what they just said (only louder). Is this good communication? I don't think so. I've also got mails from otherwise good programmers which basically required mind reading ability in order to be understood. Even worse, the mails were sent to 10-50 people, meaning (10 to 50) * (mail length) / (reading speed) * (average speed reduction factor due to lack of mind reading ability) man-hours was spent reading that mail. Effective communication? No.

I think there are two kinds of communication: one-way and two-way. Explaning some intricate technical detail to you pair-programming collaegue is a two-way communication since you (should) instantly realize if you collaegue understands you (by her facial expressions and body language). Phone calls are also two-way since the vocal intonation (should) indicate directly to you whether or not your explanation is good enough.

On the other hand, I consider mail to be a one-way communication (especially if sent to many people) since you don't get any indications when you write the mail if it will be understood or not when received. The same is true for documentation, specifications, code comments and source code. All these kinds of communication is one-way since it takes long time until you get any feedback on if your colleagues understand it or not.

So, how to become a better developer? How to communicate more effectively? For two-way communication I suggest to practice. For one-way communication I suggest... practice, as well actually. That is. Move along, nothing more to see here. Hit the back-button on you favourite browser.

Just kidding. Well, kind of any way. I do think that practice is the one thing will make any noticable difference, so my suggestion is to try to explain whatever technical work you're currently doing to your aunt Mathilda who lives in that small red cottage and knits hats all day long. Oh, it's impossible you say? Your aunt has never heard of numerical stability? She thinks monte carlo simulations has something to do with SimCity? That's doesn't mean you can't make her understand the ideas behind your work. It only means that you have to try harder to explain and simplify it using her language and concepts! Remember that the whole idea with this exercise is to make you better at explaning to other people, not make your aunt capable of challenging the next Turing award winner. To be blunt, she is just an exercise tool. A excerise tool that makes extremely good blueberry pies, though. Yum.

In fact, you could do this exercise by explaning anything. For instance, describe the story of the last book you read, a news article, or the story behind the best photo you ever took. But remember, you're not just telling the story, you're explaning what happend. You should "listen" (with your ears and eyes) to your audience to make sure they understand every word you say.

Some simple concrete tips:

Be clear about the background. Just because you remember the context, does not mean every one else do. Start the explanation by giving the relevant context. If you have discussed it before with the audience, refer to that. If you haven't, start by giving a hand-waving overview of the problem.
Use you hands. If you talk about many different objects, place them on different places in the air and "hold" the object you talk about by making a fist on that spot. Much less confusing for those who listen to you. Also, if you need to move your arms around to refer to different objects, you will probably speak more slowly which is also makes it easier to take in everything you say.
Pop the stack explicitly. Often in a discussion you need to get back to something you talked about earlier. In that case, say "as I said before" before you start talking about it to indicate to your audience that you pop the conversation stack. If you just change the subject people could get a bit confused and miss some parts of your explanation.
Be utterly clear when something is important. Say "this is the key point", or "this is important". Use short sentences. Repeat yourself. Use short sentences and repeat yourself. Make a pause to let your audience take in what you just said and let them think about it. Use some uncommon phrase or a silly name when explaning this key point that you can use later on to refer to it.
Speak clearly or stay quiet. If you don't know what to say, don't mumble something incomprehensible. Just shut up. Scratch your head a bit if you feel akward to let the audience know that you're thinking about what to say. People won't mind anyway, unless you do it twice every minute. They will probably thank you for the moment of mental relief. In fact, you can make pauses like this work for your advantage. (Read the bullet above one more time if you don't understand why. (You still don't get it? I'm refering to the 6th sentence, silly.))

That it for this post. But what about the one-way communications? How to improve those? I'll get back to that in my next post on this subject. Until then, if you have any other tips please let me know by leaving a comment!

And oh, before I forget, say hello to aunt Mathilda for me!

How browsers work

2010-03-05T08:33:00.000-08:00

A former colleague sent me this very sweet explanation of how browsers work today. Can you say awww?

Talks by Herb Sutter

2010-02-25T09:20:00.000-08:00

I wish to recommend two very good talk by Herb Sutter; Machine Architecture: Things Your Programming Language Never Told You and Concur ad C++ Futures.

Unskilled and unaware of it

2010-02-19T07:21:00.000-08:00

I just read the Unskilled and unaware of it post at Successful Software. It's a good post that (should) make you think about how good you consider yourself in various fields such as software development and driving.

I find it a bit funny that there are some skills that you probably don't overestimate your own skill level. Have you ever heard of someone saying he/she is a great gardener when in fact every flower they touch die?

Update: See Dunning-Kruger effect on Wikipedia.

Detecting function inlining

2010-01-25T10:33:00.000-08:00

By definition, compiler optimizations should only affect the performance of the application. The behavior of the optimized code should be the same as the non-optimized code. If this is the case, how is it possible to detect whether a function has been inlined or not? Dear reader, read on (that's what readers do, right?).

Before we continue, let's take a step back and ask ourselves why it would ever be useful to detect function inlining. Let's take an example. Imagine the following code is part of a large application developed at company where we pair program. The function createObject() allocates an object on the stack (that is, it's a local variable) and returns a pointer to it:

int function() {
Object* o = createObject();
return o->field;
}

although it's bad practice to return a pointer to a local variable, function works and does precisely what you'd expect: it creates an object and returns one of its fields. As developers with good taste, we decide to clean up the code a bit by introducing a getter for field:

int function() {
Object* o = createObject();
return o->getField();
}

We compile the code and run the tests. There is a green light. Everything is good. We commit the code to the repository.

Not so fast! After a while the automated build system indicates a whole lot of failing tests. What happend?

Here's what happend: since we introduced a function call to getField we changed how the stack looks when reading the field field. And since the object is stack allocated, the object is overwritten by the call to getField. Good team players as we are, we do not want to have failing builds for long, so we revert our last check-in and start to inspect the problem closer.

We quickly determine that the only failing builds were the non-release builds, that is, those builds that failed were those that did not optimize the code. We stare into the air and ask ourselves... why?

At this point one of us remembers a blog he had read the night before about function inlining. He explains "if the call to createObject is inlined into function, then the object is allocated as a local variable in function instead of in createObject. This means that when getField is called, the object is not overwritten. It's not overwritten because its allocated in a different place on the stack. In a different stack frame, to more precise."

The other developer thinks about this for a few seconds and replies "ok, then let's just allocate the object on the heap instead of the stack". Before the blog-reading developer can say "memory leak" he adds "and, of course, delete it when we're done with it".

After a few minutes of coding and half an hour of waiting for the compiler to finish, we have a working solution that works on both optimized builds and on non-optimized builds. We commit the code and leave for the day.

When we get back the morning after, we have an angry mail in out inbox. Apparently our little fix made the performance of the application degrade horrendously -- we had placed a call to new inside an extremely tight loop. Doh! Stupid us. A better solution is needed. In order to understand the problem properly the pair programmers summarize:

For optimized builds the function is inlined, thus stack allocation work fine. With stack allocation the performance of the application is acceptable.
On non-optimized builds the function is not inlined, thus stack allocation does not work and we have to resort to heap allocation. However, heap allocation is not acceptable for performance.

When the problem is so clearly stated, the blog-reading developer exclaims "let's allocate on the stack if the function is inlined, and allocate on the heap otherwise!"

Ok, now let's leave those two developers, I think they can handle it by themselves now. I'm now going to explain how to do the trick the blog-reading developer suggested.

For every function that is called there is a stack frame which contains the function's local variables. Every stack frame has an address, which can be accessed via a register called EBP (extended base pointer, I think). This register can be read using the following code:

void* stack_frame() {
register void* ebp asm("ebp");
return ebp;
}

This function returns the pointer to the stack frame that is created when entering the function. So, as you can see, it's really simple to get the pointer to the current stack frame. Let's make another function and provide it with the pointer the stack frame of its caller:

bool is_inlined(void* callers_ebp) {
register void* my_ebp asm("ebp");
return my_ebp == callers_ebp;
}

This function is kind of magic because it will return true if its inlined and false otherwise. Using this we can write a function that allocates on the stack if the function is inlined, and allocates on the heap otherwise:

Object* createObject(void* callers_ebp) {
register void* my_ebp asm("ebp");
if (my_ebp == callers_ebp)
return &Object();
else
return new Object();
}

Pretty sweet.

Note that the EBP register is not used when compiling with -O2 or -O3 unless you use -fno-omit-frame-pointer. It should be possible to do the same trick without EPB by using the ESP register instead, but I haven't tested that.

(Disclaimer: I'm not suggesting that this is a good way for solving the problem the two developers in the story faced. What I do say it that in those rare circumstances when the behavior of a function need to change when its inlined, then this is one way to do it.)

Faster and optimization friendly: speculative stack allocation

2010-01-24T13:11:00.000-08:00

I've have had an idea for a memory allocation algorithm for some time. It's based on the idea behind escape analysis. Escape analysis analyzes the source code and determines the dynamic scope of an allocated object. For example, in the following Java code:

void printNumber(int i) {
System.out.print(new Formatter(i).hex());
}

escape analysis can help improve performance by determining that the instance of Formatter cannot escape the stack frame it was allocated in. Thus, the Formatter instance can be allocated on the stack instead, which (greatly) improves performance. Since Java 6u14 there has been experimental escape analysis in the JVM.

For languages such as C++, which rely on static compilation and optimization, escape analysis make it possible to do even more optimization. Consider the following C++ code:

int two() {
Cons second(2, NULL);
Cons first(1, &first);
return first.cdr()->car();
}

which creates a linked list of cons cells (1 (2 NULL)) and returns the first value of the second cons cell. That is, the function returns 2. GCC (and most other compilers as well (I will use the name GCC in this post meaning your favourite C++ compiler)) will gladly optimize this to simply return 2, it doesn't even bother to create the Cons objects at all (unless there are some kind of side-effect in the Cons constructor, like printing). Furthermore, since GCC now knows that this function simply returns 2, GCC can replace all calls to two with the value 2. Thus, the overall performance will increase even more.

However, what if we cannot allocate the Cons cell on the stack... what if we must allocate on the heap. What kind of code will GCC generate then? I'll spare you the list of assembler code here, but let me tell you it isn't pretty. Its a far cry from the assembler equivalent of return 2;. Also, allocating on the heap is an extremely costly operation in comparison to stack allocation. So, not only is heap allocation expensive, it also stops GCC from performing any kind of smart optimizations.

So what has escape analysis to do with the idea I have for memory allocation? The idea is to perform escape analysis at run-time instead of at compile-time. That is, determine at run-time if an object is reachable from outside its stack frame; and if it is move it to the heap.

This boils down to insert checks at certain places in the source code, e.g., when returning a pointer from a function. These check determines if the object (which is returned) will be reachable from a stack frame with longer lifespan than the stack frame in which the object was allocated.

Now, inserting checks at certain places may not sound like a very good idea, but the application I'm thinking of for this right now is not manually written code; it's generated code. A proper implementation of this idea would only (explicitly) allocate object on the stack and then (implicitly) move object to the heap when needed. Thus the code for allocating an object always looks the same; it does not depend on the lifetime of the allocated object. Code that look the same is easier to generate, so this is a good thing for code generators. Furthermore, extra checks that I mentioned above should be easily generated by a code generator since those checks also always look the same. Pretty neat.

Another thing that is important to note is that the algorithm uses data that is only available at run-time when deciding if an object should be moved to the heap or not. This means that this algorithm is independent on the complexity of the code or knowledge of data. On the other hand, normal (static) escape analysis may fail if the code is very complex, e.g., a lot of execution paths that depends on statically unknown data.

There is one more thing with this approach that is important: it plays well with GCCs optimizations. Since every object is stack allocated (until the run-time system notices that it needs to be moved to the heap), optimization like the one discussed above for function two can be done by GCC. That's pretty neat as well.

I've implemented a prototype of this idea here. It's not at all well-tested and I haven't tried it on any other machine than my laptop, so there are probably a lot of problems with it. The idea, however, I think is not entirely insane and could be useful.

Your decompiler is my compiler

2010-01-15T09:58:00.000-08:00

Last night while brushing my teeth I thought about a recent project I've worked with, namely compiling Java to native code. The basic idea is the same as my other project compiling python statically: translate the byte code into C/C++ and then use any C/C++ compiler to compile it to native code.

There is a neat tool called javap that prints a bunch of interesting stuff of a Java class: the byte code of all its methods, and the type of its fields, among other things. I simply translated the sequence of byte code into something gcc could compile, and I got a primitive Java compiler that compiles to native code. Well, right now it only supports a small subset of Java... and it probably will stay that way too. :) I have a good habit of starting many project and a bad habit of never finishing them.

As I've discussed before Java and C++ are textually quite similar, for instance is the following code Java or C++?
if (var >= 0) return new ArrayList<String>(“hello”);
(I intended it to be Java, but the only reason for it to be more Java-ish than C++-ish is the name of the types: ArrayList instead of list and String instead of string.)
As you probably know, there are several decompilers for Java. Just google it and you'll find some. What these decompiler do is to print the Java code that behave exactly as the original byte code. No surprise there; that's what decompilers do!

Since Java and C++ are such similar languages textually, much more similar than Java and C or Java and Ada, its pretty straight-forward to turn a Java decompiler into a bytecode-to-C++ compiler. What I just said may sound like it turns the decompiler inside-out, but the only difference are (comparatively) small changes to the textual output.

Of course, such compiler will not support any of Java's good stuff, such as reflection, but that's not the point here. The point is that it's possible to make a compiler for Java by hacking an existing decompiler, and doing so is fairly easy because of the reuse of a C++ compiler.

Total awesomeness.

Print sucks, tuples rocks: disassembling Python

2010-01-06T12:04:00.000-08:00

I recently worked on compiling Python by translating it to C++. I did this using the dis module, which prints the bytecode of a Python function. Note the word prints. There is no (simple) way of getting the bytecode of a function in a list or similar; just having it printed to the console.

At first I parsed the textual output that dis gives, but this turned out to not work for more complex stuff. Basically, the textual output did not contain all the information I needed (printing repr(obj) throws away information for some values). What to do?

Well, luckily Python is distributed with the source code of dis, so it was easy to create a copy of the function that disassembles Python functions into bytecode and rewrite it a bit. Essentially, instead of calling print, everything is stuffed into a list. Thus, you'll get a list of tuples instead of a textual output to the screen. Each tuple holds the source code line, the byte code line, the opcode and the argument to the opcode, making it easy to access them programmatically. If you would like to see the source look here (the first 60 lines).

More importantly though, this patch does not just makes the dis module a bit easier to use. As I said earlier, the textual output of dis throws away certain important information. Howerver, this patch retains the actual values instead of converting them to strings using repr. This is really important for me because it makes it possible to translate certain code which otherwise would have been impossible. More precisely, it makes it possible to translate lambdas, list comprehensions, etc, from Python to C++. The reason is that instead of getting repr(function_object) I now get function_object itself. Awesomeness!

Oh, did I mention that Python rocks?

Of banks and doorbells

2010-01-06T09:19:00.000-08:00

This is an amusing kafkaesque story form real life by Niel Fraser at Google.

History of Microsoft

2010-01-05T07:59:00.000-08:00

I just saw a few episodes of web show The History of Microsoft on Channel 9, which I thought was quite interesting. Channel 9 is web site by Microsoft so I assume that the show focuses on the good parts, but it's still a good watch.

Statically typed and compiled Python

2010-01-03T04:37:00.000-08:00

It was a while since I wrote something here. In spring last year, that is 2009, I started on a really fun project: writing a compiler for a language I invented myself (previously mentioned here). Ok, the "compiler" only compiled to C++-code, but still...

The language is called Fit and is a compiled (of course :)) statically-typed prototype-based language. It's heavily inspired by Java and Ruby, has first-class functions, generators, list literals, and string interpolation, among other things. All these things aren't supported completely by the compiler; there is only a rudimentary (by which I mean buggy) implementation.

I worked alot on this project. Many late nights. Four hours of sleep before getting up to work wasn't unusual. Naturally I got really tired and when the compiler was able to compile a decent subset of the language I originally imagined, I stopped working on it. It just wasn't fun anymore.

I learnt alot from this project. Writing parsers, writing efficient C++ code, optimization tricks, how to implement closures, and... oh yeah, I learnt Python. Why? The compiler is written in Python.

Here's the funny part: after working on Fit and its compiler for a while, I realized that the language I was trying to create essentially was a statically typed Python with braces. And after writing Python for a few weeks I was ready to throw away the braces. What's left is a statically typed Python (take a look at Boo if this kind of language sounds interesting). The rest of this post is about creating a compiler for a statically typed Python with minimal effort.

I actually tried writing a parser for such a language, but I failed miserably so I dropped the idea. However, I have recently realized that it is not necessary to write a parser to create a statically typed Python. Here's why: in Python 3 it is possible to annotate functions to indicate the types of the arguments. Example:

def plus(i: int, j: int) -> int:

__return i + j

These annotations provide the type information needed to convert Python to C++ code, which then can be statically type-checked and compiled. The first step for this is to get the signature for the C++ function. The following code returns the C++ function signature corresponding to a given Python function:

def signature(func):

__import inspect

__spec = inspect.getfullargspec(func)

__c_args = [spec.annotations[arg].__name__ + " " + arg for arg in spec.args]

__return_type = spec.annotations['return'].__name__

__return return_type + " " + func.__name__ + "(" + ", ".join(c_args) + ")"

For example, calling signature(plus) will result in the string int plus(int i, int j), which of course is the signature of plus in C-speak.

Ok, so how is this useful you may wonder. We need to convert the body of a function not just its signature. Well, here's where another great Python module comes into action, namely dis, which returns the bytecode of a Python function. For example, when called with plus as argument, dis get us:

1 0 LOAD_FAST 0 (i)

3 LOAD_FAST 1 (j)

6 BINARY_ADD

7 RETURN_VALUE

I won't go into details here, but it fairly easy to translate this bytecode sequence into C++ code. I've written a translator that supports only a few bytecodes (LOAD_FAST, LOAD_CONST, STORE_FAST, BINARY_ADD, BINARY_MULTIPLY, and RETURN_VALUE) and with limited support for types. On the other hand, I only spent a few hours on it. That's the "minimal effort" I was talking about earlier. :) The following Python code is small example of what the translator currently supports:

def testing(i: int, j: str) -> int:

__text = "hello"

__dog = 9.9

__donald = i

__goofy = dog

__donald = donald + 100

__daisy = donald * 4 + donald

__return daisy * 223

And this is the corresponding C++ code:

int testing(int i, str j) {

__str text = "hello";

__float dog = 9.9;

__int donald = i;

__float goofy = dog;

__donald = (donald + 100);

__int daisy = ((donald * 4) + donald);

__return (daisy * 223);

}

As you can see in this example, the C++ code matches the Python code quite well. Also, note that local variables are declared and typed automatically. Awesome! The best part is that the whole translator is only 100 lines of Python! Of course it doesn't support all bytecodes and does not have proper type inference but it definitely works as a proof-of-concept. As I said, I only spent a few hours on the translator.

So, assuming this translator ever gets finished, what could it be used for? Anything, I would say. As a general purpose compiled language just like C++ or Java (if you consider that compiled), or as a replacement for normal Python when performance or memory consumption is an issue. I also find it really neat that you have an interpreted language and a compiled language in one; the same language can be used to hack together a small prototype and to write a large well-specified application. In other words, you can stay in the same language and simply "refactor" your hacky prototype into a not-so-hacky application. I find this a very attractive idea.

State of the art C compiler optimization tricks

2009-11-09T12:25:00.000-08:00

I found this via Lambda the Ultimate: State of the art C compiler optimization tricks. It's a good read, though I would really like to see the presentation rather than just reading the slides. Also, is this really 'state of the art'? Sure, some of the optimizations the compiler does is pretty impressive, but some are... well... not. Is common subexpression elimination really state of the art? Seems like 1970-ish to me...

alias norris=sudo

2009-10-29T11:53:00.001-07:00

Joke of the day. :)

Lecture from MIT: Cache oblivious algorithm

2009-10-22T09:51:00.000-07:00

I just watched a lecture about cache oblivious algorithm from MIT's course Introduction to Algorithms. It's really nice that things like this is free on the net. I found it via Good coders code, great reuse. Check it out!

Code generation: C++ vs. Java

2009-08-30T05:13:00.000-07:00

Code generation can be very useful by reducing the amount of code that is needed to be written, tested, debugged, maintained, etc. But if you develop the code generation yourself, code generation can be a nightmare. Getting the code generator right can be very hard, especialley so if the generator needs to support more than one target language (the output language).

The last code generator I wrote was for a private project. I've always wanted to design and implement my own programming language, and this spring I finally started to implement a compiler (actually it was source-to-source translator that outputted C++ code) for my language, which I call Fit. This was the first translator/code generator I've written that generates C++ code.

I'm not a big fan of C++, I think it's a too complex language that forces you to think about low-level implementation details. Thus, since my brain is limited, I have less brain-cycles to think about the high-level design of the application.

So why did I choose to translate Fit to C++ if C++ is so hard? Well, my other alternaive was Java, but since I already had written a couple of generator for Java I thought that a generator for C++ would be a fun experience.

Actually it was a really nice experience! Having access to all the low level details (e.g., pointer arithmitics and goto) and the high-level constructs (e.g., operator overloading) made it relatively easy to translate Fit to C++. When implementing the Fit-to-C++ translator I really saw the difference in power between C++ and Java.

Java, although a good language, is not a powerful language. In Java you can do certain very easy, but as soon you need to do things the language wasn't designed for you will have a bad experience. Ever tried to write bit manipulations in Java? It's not fun I tell you. In C++ at least you have the option to implement it using operator overloading and templates to make is less of a burden. I Java, that option is not available.

To take a concrete example from the Fit compiler/translator: yield is translated to (efficient) C++ using a switch and a goto. I'm not sure how to implement it in Java, but I guess you would have to do some work-around using a do-while construct.

So what am I'm saying? Is C++ a good language? Well, no it's not good if a human being writes it, but it is actually good if a code generator writes it. All the low-level stuff actually simplifies the generator.

Everything you ever need to know about concurrent programming

2009-08-13T08:36:00.000-07:00

I usually don't link to other blogs without adding some of my thought on the topic, but this time I make an exception. Herb Sutter has written 25+ articles in Dr. Dobb's Journal, all about different aspects of cuncurrent programming. Check them out. They are a good read even if you're not really into concurrency.

Give me a smarter compiler! How? Here's how!

2009-06-07T05:25:00.000-07:00

In dark ages writing code and compiling code was two separate processes. As we get better languages and faster hardware and compilers, writing code and compiling code becomes more and more integrated. For instance, when programming Java in Eclipse the source is compiled in the background every time the file is saved. Very nice because it gives fast feedback!

This means that since the code is compiled so often there usually only a small difference between the previous compiled version of the code and the current. This got me thinking: would it be possible to improve the error messages from the compiler by comparing the current code with the previously compiled code?

Let's take an example. Assume that there is an interface I with a method void m(int) that is implemented by a class C. The code compiles without errors. Then you change the signature of m in C to void m(long), which breaks the code of course. In this case the compiler could give an error message something like "Changing C.m(int) to C.m(long) makes non-abstract class C abstract, because I.m(int) is no longer implemented" instead of the error message given by today's compilers which is something like "Non-abstract class C is missing implementation for I.m(int)".

For this small example it may seem like a small improvement, but I think that if the compiler has access to the latest working code, then it can help in several way. Better error messages is only one improvement. Other improvements could be to give warnings when the semantics of the code has changed in an uncommon way. Let's take an example of this.

Let's say an instance of the java.lang.Thread class is created and its void start() method is called. During refactoring, the call to start is removed by mistake. The compiles knows that its a common pattern to instantiate a java.lang.Thread and then call start on it, thus, the compiler gives a warning indicating the (potential) problem. For instance something like: "Thread is created but not started because the call to Thread.start() has be removed between the two latest version of the code." It's almost like having a conversation with the compiler.

Another nice thing with this kind of warning is that it only appears when the code has changed. In other words, it is the difference between two consecutive versions of the code that triggers the warning, not the individual versions.

If the programmers intent is that the thread should not be started, then the warning can be ignored and the next time the code is compiled the compiler will not warn about the "missing" call to Thread.start(), because from the compiler's perspective the call is not missing anymore.

This idea can of course be useful for static code analyzers, such as FindBugs, as well.

The missing level of testing for software reuse

2009-06-02T09:18:00.000-07:00

I've noticed a pattern. For software projects that start doing unit testing, unit testing is often paired with (manual) system testing only. Here's the pattern I've notices a few times:

Project members think unit testing and (traditional manual) system testing is good enough.
Project members want the simplicity of unit testing for system testing.
Project members try to automate system testing, but realize its hard or impossible to come close to the simplicty of unit tests.
Project members realize there is a missing level of testing between unit testing and system testing.

Here project members means developers, architects, testers, managers, etc.

The funny thing with this is that the missing level of testing often has been mentioned in discussions several time before in the project, but said to be impossible to implement because there is not time to do it. However, after being bitten by bugs found late in the project work on it is finally started.

This missing level of testing tests such a large part of the application that it can be run indepenently. However, hardware and OS depenent parts are stubbed, configuration is (thus) simplified, user interaction is replaced with test-case input and assertions, and so on. There are several names for this level of testing: subsystem testing, multi-component testing, module testing, etc.

There is a important difference between unit tests and system tests: unit tests live inside the code, while system tests live outside the code. When you write a unit test you write the code in parallel, you rewrite to code to make it testable, you refactor the test code and the production code at the same time. System tests, on the other hand, is often written in a completely other language (if automatic at all).

This missing level of testing I'm talking about here also lives inside the code. Those tests are also refactored when the production code are, for instance. This is important. Being inside the code means these tests are easy to run, update, and write. Being inside the code is the thing that make this level of testing work.

Essentially, these tests are unit tests in many aspects except that they test much larger chunks than a 'unit' (which is often said to be a single class).

If done well, I think there is an interesting side-effect of this level of testing: it's easier to adapt larger chunks of code to work under different environments or assumptions (this can be seen for unit-tested classes. but for smaller chunks). If unit testing encourage interfaces and dependency injection, then this level of testing encourage a similar mind-set on larger chunks of code. For instance, configuration could be done in such as way that it easy to configure the application to use some kind of stub (e.g., saying PROTOCOL_TO_USE=TCP instead of USE_TCP=TRUE, because then it's simple to add a stub protocol)

Seeing how much code is written that essentially reimplements existing application just because some small part of the application does not meet some requirement, this style of testing (if it improves reuseability, as I think it does) can be worth doing for more reasons than quality.

Is testability what we should really aim at if we wish to make our code reusable? If so, then we need to test code in chunks that we think is valuble for reuse. In other words, the levels of testing we have defines the chunks of code that can be (easily) reused.

Using Office as an IDE (was: Making word documents machine-readable)

2009-05-11T13:19:00.000-07:00

Ok, I admit it: this is a bit crazy. :) I think this is a very good quote:

Get your data structures correct first, and the rest of the program will write itself.
David Jones

especially in the context of this post.

That enough fluff, now let's get to the stuff.

Let's assume that you get some kind of specification in a simple computer readable format, e.g., comma-seperated-values or XML. There are several things that you can do when provided with such specification:

generate code, e.g., interfaces or test-cases
automatically check you code (e.g., the states of a finite state machine handles the events they should and no more)
automatic formal analysis of the specification (e.g., the finite state machine does not have any unreachable states)
make sure the user documentation contains all parts of the documentation (e.g., a chapter for each foo and bar specified).

Nice, stuff. But what if you get the specification in a less computer friendly format like MS Word format? Luckily, OpenOffice can read Word files and convert those to an easier format like HTML or plain text format (this should be possible to do via command line according to this, although I haven't tried it). OpenOffice can also do similar thing with Excel files.

Ok, now you've got the Word or Excel file converted to plain text, now it's time to write that anayzer, code generator, or whatever you need. Code on!

Actually, when thinking about this I realized that a very cool thing to do would be to trigger the convert-to-text-and-generate-code process when the Word/Excel document is saved. This way, whoever is updating the Word/Excel file will immediately know if the document is consistent (if the process analyzed its content) or if the tests passed (of the process generated test-cases). Would that be awesome?

In some sense, this is using MS Office (or OpenOffice for that matter) like an IDE. Sound like madness to me, but perhaps its useful someone. Although I have to say that writing some document in MS Office, saving it, and a few seconds later getting an indication saying "document analysis result: 1 warning: no test-case for feature 'Foo is sent to Bar'." would be really cool. Or when saving an Excel file getting an indication saying "Data in cell (5, 4) made test-case 'Foo can hold configured number of Bar:s' fail."... that would be awesome.
Why? Dunno, it just would. :)

Java-compatible syntax for C++

2009-05-04T11:33:00.000-07:00

Since I first realized how much more productive you are in Java compared to C++, it has bugged me that the syntactic difference is so small. Take this code as an example:


class A {
public void a() { }
}

Is that C++ or Java? (Hint: add ":" and ";" and it becomes another language). The difference is syntactically tiny, but huge when you think of all the things you get from Eclipse when using Java.

So, this the idea: express C++ with a syntax that is compatible with Java. This Java-compatible syntax (JCS from now on), of course, requires a program to translate it to C++, but it will make it possible to use a number of tools currently only available for Java. Refactoring and code browser (which is reliable), for example.

Yeah, I hear you, "you can't express advanced-feature-X and meta-programming-feature-Y using a JCS". You're right; macros and advanced template-programming is far beyond the reach of a JCS, but that's not my point. My point is that the majority of C++ code could easily be expressed with a JCS. If 95% of your code could be refactored or browsed using Eclipse, thats much better than if 0% of your code could be refactored properly.

Actually, I think that the alot of the C++ language is an example of not keeping the corner-cases in the corner. Simple things like writing a script to list all defined functions in a source file is (in the general case) impossible because macros can possibly redefine the language... (thus all #include:ed header files has to be parsed, thus the entire build system with all its makefiles has to be known to the scrip.).

I know Bjarne Stroustrup had reasons for doing this (backwards compatability with C), but I think this was more of marketing reason than a technical reason. His new language could have been compatible with C (being able to call it, and be called from it, etc) without the new language having to be a syntactial superset of C. Anyway, back to JSC for C++.

Friends and colleagues have told me that the new CDT for Eclipse gives you refactoring, code completion, and browsing, but it works poorly from my experience. Perhaps I've failed to configure Eclipse correctly, or I'm using a crappy indexer to index my C++ code... but I can't refactor my C++ code the way I can with Java code. (Compare the number of available refactorings in Eclipse for Java and C++ if you like to have an objective measurement).

I've implemented a prototype that proves that it is possible to create a JCS that covers the most common part of C++. It works by traversing the Java AST (abstact syntax tree) and translates relevant nodes to its C++ representation. Example:


class A extends B implements C {
public int foo(@unsigned int[] a, boolean b) {
  if (b) return a[1];
  return 0;
}
}

translates to


class A : public B, public C {
public: virtual int foo(unsigned int* a, bool b) {
  if (b) return a[1];
  return 0;
}
};

There are very much that's not covered with this prototype, and it's probably riddled with bugs... but it fulfills its purpose perfectly: proving that expressing C++ using a JCS is possible. The prototype is available here.

I'd love to make a real-world worthy implementation of this idea, but I'm afraid it will take up my entire spare-time... I have other things to think about! :)

Unit testing makes manually managed memory simple

2009-04-22T10:19:00.000-07:00

I recently started working on a project that does test-first development in C++. I have mostly done TDD in Java, but I've done a lot of C++ before that so neither the language nor methodology is new to me. However, after two-three years of unit testing in Java and a few scripting languages, I have (luckily) learned a few things. So this time around I hope to avoid one of the problems I had earlier with C++: the problem with ownership of newed objects, that is, which object owns another dynamically allocated object?.

When I was rewriting some classes to be testable I, as you usually do, introduced interfaces, used factories, injected dependencies, etc. In one case I rewrote the class under test (CUT) to use a factory instead of calling new directly. This made it easy to test that the CUT allocated an object correctly. But how to test that the CUT deletes that allocated object?

Well, it was quite simple: simply add a method to the factory called destroy that takes one argument which is the object to be destroyed. The method destroy is used to tell the factory I'm done with this object, do what ever you like with it... delete it it you want to. The destroy method corresponds to the make method, which of course allocates an object.

This is probably not some great new discovery I've made; most of you who have done test-first development in languages with manual memory management have probably already done this kind of thing. This was a new thought for me, though.

I also realized how clear the ownership of the object (created by the factory) had become. It was obvious from reading the production code and/or test-case that it was the factory that owned the object; all it did was to lend the object to some other class until destroy was called. This was an insight for me.

The fact that the factory owns the objects it creates means that it is trivial to replace the memory allocation scheme used by the factory. Only the factory is needed to be changed, e.g., if there is a need for pooling objects. Awesomeness.

I guess there are cases when this approach is not possible to use, but in cases where it is I think its a good pattern to use.

Movable proxy: a design pattern for hiding dirty secrets

2009-04-08T10:34:00.000-07:00

The Proxy design pattern is a useful pattern. For my style of programming it's quite common, although I seldom actually name the proxy-class SomethingProxy. Instead I try to come up with a name for its actual role or responsibility. An example of this kind of proxy could be the services provided by a package in some Java code. All classes of the package is package private (default visibility) except for one, which is the proxy towards the package (there are of course a bunch of public interfaces).

Traditionally, though, a proxy is an object used to accessing something complex in a easier way. For instance a proxy for sending messages to, or retrieving the state of, a remote process. At work, where I'm working with a distributed Java application, we have a bunch of such proxies for accessing the various distributed subsystems/processes. All these proxies have some protocol for talking to the remote subsystem, e.g., homebrew protocol N, standard protocol M, etc.

This is all good, except for the fact that both the client subsystem and the server subsystem need to share a dirty secret: which protocol that is used to communicate. A sane design will hide this dirty secret inside some class (e.g., a proxy!), such that the bulk of the code doesn't need to know the secret. But still, some part of the client subsystem must know it, otherwise it cannot establish a connection to the server.

Or does it?

Wouldn't it be great if it was possible for the client to ask the server for the proxy instance? That is instead of doing:


final Proxy forTalkingToServer = new ServerProxy();

the client does:


final Proxy forTalkingToServer = server.proxyForTalkingToServer();

Ok, that sound like a nice idea. But wait, how is the proxyForTalkingToServer() method implemented? Doesn't the implementation of that method need to communicate with the server? Well, yes. But this bootstrap problem is easily solved by having a standardized protocol for sending java objects between different Java systems, e.g., RMI.

The sequence is something like this:


      Client                      Server
      ------                      ------
        |    Proxy request [RMI]    |
        |-------------------------->|
        |                           |
        |    Proxy confirm [RMI]    |
        |<--------------------------|
        |                           |
+------------------+                |
| client has proxy |                |
+------------------+                |
        |                           |
        |    Whatever request [?]   |
        |-------------------------->|
        |                           |
        |    Whatever confirm [?]   |
        |<--------------------------|

Where Proxy request is what happens when the proxyForTalkingToServer() method is called, and Proxy confirm is the methods' return value, that is, the proxy the client should use for talking with the server. The Whatever request and Whatever confirm messages are messages sent using some protocol (symbolized by [?]) that the server decided to use.

In addition to having the client completely unaware of the actual protocol used for communicating with the server, the proxy can be pass around (using, e.g., RMI) the entire distributed system and it will still be possible to access the server using the proxy. It is also possible to update the protocol without updating the clients, or to let the proxy instance implement multiple interfaces (one new-and-improved and one legacy for backwards compatibility). It is also great for testability/debugging: you can easily replace a troublesome protocol with a simpler variant.

Neat.

Happy new year!

2009-04-01T10:42:00.001-07:00

One year ago I wrote my first post for this blog! I've been writing about Java and testing, published a few small programming project, and screamed in frustration.

There have also been some (slightly) philosophical posts, seemingly trivial ideas, my old sweatheart Lisp, and my views on OO. I have also faced one of my many fears and helped you making your faviourite IDE a bit better.

At late, I've even had some insights and publishing one of my coolest ideas (with a crappy implementation) :)

Code generation using reflection

2009-03-23T10:51:00.000-07:00

A couple of month ago, in late November I think, I got an idea when I was riding my bike home from work: using code generation to optimize code that normally relies on reflection. (To understand this post, you should at least now the basics basics of dynamic proxies. Check this out if you don't.)

A common pattern for me is to have an interface and generating the class(es) that implements it at runtime using a Dynamic Proxy. The behavior of the class defined by code that is parameterize by annotations on the interface. Example:


interface CommandLineArguments {

@ArgumentName({"c", "config"})

String configFileName();

@Argument({"x", "max")

String maxValue();

@Argument({"n", "min"})

String minValue();
}

The annotations on the methods in the interface defines what they should do simply by giving the name of the corresponding command line switch. Extremely terse, readable, and flexible code. If you ask me, this (annotated interfaces + dynamic proxies) is one of the best thing in the Java language.

The code that actually gets executed when the methods in the interface is called often rely heavily on reflection. Reflection, as everyone know who have ever used it, is very powerful but can also be very slow. Is there some way to make it a bit faster? Yes, there certainly is: code generation.

Lets take a simple but realistic example: for any interface, create a wrapper that print the name of the method and delegates to some other class that implements the same interface. The code for doing this look something like this:


import java.lang.reflect.InvocationHandler;

class InvocationPrinter implements InvocationHandler {

private Object delegateTo;

InvocationPrinter(Object delegateTo) {

this.delegateTo = delegateTo;

Object invoke(Object proxy, Method method, Object[] args) throws Throwable {

System.out.println(method.getName() + " called.");

return method.invoke(delegateTo, args);

}
}

This is a general but, unfortunately, slow. It is trivial to speed up, but this requires us to hand-write every method for every interface we wish to use this way. Another way, which gives the same speed-up, is to generate the same code dynamically. Literally the same code (except for indentation and such). Then using Javassist, this code can be compiled to a class at run-time, resulting in bytecode with the same performance as your hand-written code.

I have prototyped this approach for generating code by providing wrapper classes that looks and behaves just like java.lang.reflect.Method, java.lang.reflect.Constructor, etc, except that they also stores how they were used. For example, the class (called BIMethod) that corresponds to java.lang.reflect.Method stores the arguments used when invoking it and the returned object. By doing this you can write normal Java code that uses reflection (via these provided wrappers), but also generate (at run-time) the Java code that implements the same functionality. In fact, since the wrappers keep track of returned values, and created object (via Constructor.newInstance) it is possible to do fairly complex stuff like:


void doSomeReflectionStuff(Object[] args) {

DummyInterface obj = null;

 for (final BIConstructor c : factory.constructors(Dummy.class)) {

try {

obj = (DummyInterface) c.newInstance(args[1], args[2]);

break;

} catch (final Exception e) {

final BIMethod someMethod = getSomeMethod();

return someMethod.invoke(obj, 0, args[0]);
}

That is, you reflectively invoke an object created using reflection. In addition, a constructor matching the arguments (the Object[] args) is found automatically by checking if the constructor threw an exception of not. The generated Java code for this will look something like this:


Dummy variable0 = new Dummy(arg1, arg2);
return variable0.theChosenMethod(0, arg0);

If you wish to take a peek at the prototype, just go ahead. Be aware, though, that is is probably the least tested stuff I'll written in quite a while... there a probably heaps of bugs... :) Despite this, I think it's worth taking a look at if you need to get more performance out of your reflection-based code. Please contact me if you have any questions or ideas.

It's 2009 and you can't read a forwarded mail

2009-03-20T07:59:00.000-07:00

The other day, a college sent me a mail that I simply forwarded from Outlook to my Gmail. Today, when I finally had time to read it I opened it in Gmail. What do you think the mail contains? Nothing, except an attached file called smime.p7m. This file contains the encrypted mail, apparently, so I can't read it.

Oh, please! Come on! Why is a simple thing like this so hard?! Really... seriously, I'm failing to forwardning an e-mail...? Are we really making progress?

Yeah, I know that I should have forwarded it without encryption. But why is this something I need to know about? The mail client should tell me that the receiver won't be able to read the mail... It's freaking 2009! Not 1979!

Who knows... in 3009, perhaps we humans have evolved enough to have figured out and understand this whole send plain stupid text to another person-thingie. It's apparently too advanced to grasp for the current generation of humans.

(I have high hopes for the next-gen humans, though... No, really. I do!)

Contracts? Test-driven? Insight!

2009-03-14T06:48:00.000-07:00

The other day I pair-programmed with a new guy at work. He showed my a class and its tests he and another guy had written a few week earlier. I don't recall exactly what the class did, but it was quite simple, hence the tests was short and simple. Overall well written tests if you ask me.

As we looked at the tests we had the following conversation, which afterwards gave me an new insight to an idea I've had a long while: tests are contracts.
He: Most of these tests are for testing that the class logs correctly...
Me: Yes, is that a problem?
He: Well, I know TDD says that you need to write a failing test before you're allowed to write any production code. But isn't testing logging a bit over-kill?
Me: I understand what you mean. What kind of logging is this? Why does the class need to log?
He: We needed it to understand the code. For debugging.
Me: Is the logging needed now? Is there some script that parses these logs, for example?
He: No, it's not needed any more.
Me: In that case I'd say that these tests isn't needed.

I could go even further and say that those tests shouldn't be written at all and should be removed. I actually think that tests like these are more confusing then anything else. I'm not saying those two guys who wrote these tests did anything wrong; they were doing TDD and was doing TDD right. What I'm saying is that, in my opinion, TDD isn't ideal.

Yeah, I hear you're cries: What?! Heresy! Calm down. I'll try to explain.

My opinion is that a class' tests should define what the class has to fulfill to be considered correct. To be precise, with 'correct' I mean 'what makes all things that depend on the class behave correctly'. (I realize that this is an recursive definition of 'correct', but you're a human being so you can handle it. :))

Recall that my pair-programming partner said that the logging wasn't needed any more. This means that we could remove the part of the code that logs and the class would still be correct according to the definition above. However, the class would not pass its tests because of the tests that tests the logging. This means that the class is over-specified. This is bad. The solution? Ditch the logging tests!

And so my fellow pair-programmer did.

I often say that test-methods should be named shouldFoo since it makes you focus on the behavior that is tested instead of the part that is tested (the tested method for example). I'm thinking of extending this tip to nameing test-methods as shouldFooBecauseBar. If this convention was followed, the the test-methods that tests the logging whould be named shouldLogBecauseWeNeedItforDebugging. That name sound a bit silly, doesn't it? That because it is silly to test it!

As I said, a class' tests defines what the class has to fulfill to be correct. In other words, the tests is the contract that the class must fulfill. Having tests that define contracts is much better, I think, than having tests for every little piece of functionality a class have (i.e., TDD). One reason is that it makes it easier to understand how you can change the class without breaking anything.

Now don't get me wrong, TDD is great, really great. But is it perfect? Of course not, that would be very naive to think (not to mention boring: Nothing more to do here, we've find the ideal solution! Now, let's drink tea all day!).

Is contracts ideal? Probably not. It contracts better? Yes, I think so.

Pythonic parsing and keeping corner-cases in the corners

2009-03-07T04:40:00.000-08:00

I've been fiddeling with Python for a while, especially a nice library called Pyparsing. I have posted some stuff about parsers before, and I have tried ANTL for a private project for parsing and translating Java code. Anyway, Pyparsing has to be the most intuitive and easy to use parser library I have used.

In my opinion, a common problem with many libraries, programming languages, etc., is that they are not opted for the most common, simple, cases. Rather, they make the most common cases just as hard as the most weird corner-cases you can possibly think of. Take this Java code for reading an entire file into a String:


FileInputStream fstream = new FileInputStream("filename.txt");
DataInputStream in = new DataInputStream(fstream);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String strLine;
StringBuffer content = new StringBuffer();
while ((strLine = br.readLine()) != null)   {
content.append(strLine);
}
in.close();
return content.toString();

Why, oh why, do I have to write all this code when all I want is (in Python):


return open('filename.txt', 'r').read()

or (in Perl):


open FILE, "filename.txt";
$string = <file>;

The Java API for opening and reading files seems to be focused on covering all possible use-cases. Covering all use-cases is of course a good thing, but not on the expense of common simple cases. It is trivial for me to add a few convenience methods/classes to cover the common cases. But why aren't these methods/classes in the API from the beginning?

There are several other examples of this screw-the-common-cases-and-make-the-api-super-generic-mentality. Reflection in Java throws a gazillion exceptions, for example, and in most cases you don't need to know what went wrong, only that it did go wrong.

So, anyway, let's get back to the Pyparsing library. As I said, it is very easy to use and the common cases are straight-forward to implement. For example, there are helper classes/methods for parsing a string while ignoring up-/downcase, for matching one (and only one) of a set of grammar rules, etc. In addition to this the +, ^, | operators, etc, are overloaded so a grammar rule normally looks something like this:


greet = Word( alphas ) + "," + Word( alphas ) + "!"

Awesomeness.

So, what is this post all about? Pyparsing or bad libraries? Both. There are so many bad libraries out there that aren't ment to be used by human programmers. That is, the most simple things in the library are hard to use just becase the harders things are har to use. Pyparsing, on the other hand, is a joy to use. I was suprised how often I thought oh, it would be nice to have such-and-such helper function now and after looking in the Pyparsing documentation though yey, there it is!

One factory to bring them all, and at run-time bind them

2008-11-09T05:39:00.000-08:00

Most of us know that to call new makes code hard to test because the piece of code calling new is statically bound to another class. In other words, there is no way to isolate the class under test such that its interactions with other classes can be tested. There is of course a solution to this: factories and/or dependency injection (with or without a framework).

I personly prefer to manually inject the needed dependencies, and seldomly use DI frameworks such as Guice. Why? Well, call my old fashioned, but I find it easier to read and understand non-DI framework code. So this leaves me with writing factories.

I don't know about you, but I find it boring to write these lousy factories (also, how can they be tested?). All they do is calling new; should there be some better way of doing it? Of course there should, and in fact, there are (for some definition of "better" :)). I've implemented a generic factory that can be used to instantiate most classes.

The factory uses some reflection magic and does a fair amount of work at run-time instad of compile-time. Actually, the factory is on the edge of being a primitive DI framework. :) As I usually do in my post I cut to the chase and give a few code examples:


final Factory factory = Factory.of(ConcreteClass.class, AnotherConcreteClass.class);

This creates a new factory that can create two concrete classes. Let's say that these classes implement the interfaces Interface and AnotherInterface respectiveley. To get an instance of the Interface the factory is called like this:


final Interface instance = factory.create(Interface.class);

When the create method is called, the factory finds the class that implements the provided interface (in this case this is the ConcreteClass class). Then the factory instantiates that class and returns the instance. This means that

the factory can be used for creating different kinds of objects as long as they implement different interfaces,
the client of the factory is unaware of the concrete class implementing the interface, and
the same Factory class can be used in test-cases testing the client code (the difference is only how the factory instance is created).

I illustrait the last bullet with an example, This code is part of a test-case testing a class which use the factory to create an Interface instance:
final Factory stubbedFactory = Factory.of(Stub.class);
where, of course, Stub implements Interface (compare to the example above where the factory is created using ConcreteClass and AnotherConcreteClass).

Ok, so far so good. But how to instantiate a class that need some parameters to be instantiated, i.e., only has a non-default constructor? Parameters that the factory needs in order to create objects are provided by calling the using method:
final DependencyUser user = factory.using(new Dependency()).create(DependencyUser.class);
Here, the concrete class implementing DependencyUser is instantiated with the Dependency instance as argument to the class' constructor. Any number of parameters can be given to the using method as long as they have different (run-time) type. The factory will use those parameters that are needed for instantiating the class that the client requests.

The using method returns a new Factory instance that "know about" the parameters provided to using (and any parameters known by the factory instance which using was called on). This may sound a bit strange, but it makes it possible to add parameters as they become available in the program flow. For instance, it's quite common that some parameters are only know when the factory is used. Example:
// Outside client code. An instance of 'Two' is not available. final Factory factory = Factory.of(ClassUsingOneAndTwo.class).using(new One()); // Inside client code. An instance of 'Two' is now available. final OneAndTwoUser user = factory.using(two).create(OneAndTwoUser.class);
(ClassUsingOneAndTwo is a class implementing the OneAndTwoUser interface and its constructor takes an One instance and a Two instance).

That is! That's the mostly simple, almost generic, factory I hacked together... pardon me ...developed this afternoon. The source is available here. There is also a few test-cases in that Eclipse project.

JUnit 4.5 in Eclipse 3.4

2008-10-23T09:05:00.000-07:00

I was quite disappointed when I realized that Eclipse 3.4 (Ganymede) still uses JUnit 4.3. JUnit 4.4 was released last summer so it shouldn't be rocket science to it a part of Ganymede, which was released this summer. Well, I guess it all comes down to lack of time and resources. Of course, it could also be because of compatabilty issues between JUnit versions, or something similar.

Luckely, it quite easy to use a newer version of JUnit in Eclipse. By simply adding the new JUnit JAR to the classpath of an Eclipse project and removing the JUnit 4 Library (that is, the entry in 'Java Build Path' with an icon that looks like a pile of books), the project will run the test-case with the new JUnit. Of course, your other projects will still use JUnit 4.3. We have done this at work with JUnit 4.5 and it works really good.

I recommend you to do this, since there are some really nice features in JUnit 4.5; the possibility do distinguish between assumptions and assertions, and better descriptions of failed assertions, for instance.

Don't Repeat Yourself - what does 'repeat' really mean?

2008-10-17T07:38:00.000-07:00

It is not uncommon to have some kind of script (e.g., a .sh-script) to start an application. For example, a start script for an Java application could check that the correct version of the JRE is installed, set up the classpath, and then start the application by executing java -cp [classpath] [mainclass].

In a case like this, the start script contains some information that is already embedded in the source code, e.g., the name of the class containing the static void main(String[]) method. Is this a violation of the DRY principle? I certainly think so.

However, you could argue that source code is filled with this kind of violation (refering to something by its textual name) since classes/types are referred to by name everywhere, for example when instantiating a new object in most OO languages. I don't consider this to be a violation of DRY, though.

Why? Because with modern IDEs classes can be renamed/moved and all references to the class will be updated. Thus, effectively, there is no repetition (since you don't manually handle it). So, no violation of the DRY principle.

However, if the application uses reflection, or something similar, then the IDE can't safely handle it. Consequently, you have to handle these repetions manually with IDE support. In other words, the DRY principle is violated.

The impact of these violations can be minimzed by having a good test-suit. This way, if you fail to update the code correctly the tests will tell you so. Reflection-heavy code is not different than any other code in this sense.

Ok, so let's get back to the original example: the start script and the reference to the main class of the application. This is a violation of the DRY principle since the IDE does not update the script's references to classes. But not only that, in most cases it does not have any test-cases. This is very bad, because you'll get no indication that something has gone wrong. (You could argue that you shouldn't rename the main class, but that's beside the point I'm making).

So, how to fix this? Simple. Either

unit test the start-script (run it, or use some kind of pattern matching), or
generate the test-script by a well-tested generator.

All executable parts of the application it should be possible to test; but how about the non-executable parts? How about documentation, e.g., user guides? I don't have a good answer to this besides generate what can be generated but this is hard in practice. If you have a good soluation, please let me know...

A run-time equivalent to JUnit's @Ignore

2008-10-13T08:36:00.000-07:00

It's been some time since I wrote about things that annoy me. Now it's time again. The pain-in-the-lower-back this time is: why isn't there a (good) way to ignore a JUnit test-case based on a piece of information that only awailable at run-time? In short: dynamically ignore a test-case.
I think a "good way" to solve this should fulfill the following:

a dynamically ignore test-case should marked as "ignored" in the JUnit test-run,
possible search for dynamically ignored test-cases in the IDE.

There is a very simple way to ignore a test-case base on run-time information:
@Test public void testIt() { if (shouldIgnore()) return; // ... the rest of the test-case. }
However, this solution does not fulfill the above requirements at all. Something better is needed.

JUnit uses a org.junit.runner.Runner to run test-cases. Since JUnit 4.0 it's possible to define which such Runner that should be used to run a set of test-cases. The @RunWith annotation does just this. Here is an example:@RunWith(MyRunner.class) public final class MyTest { // ... some test-cases. }
There are several ways @RunWith can make you testing filled days easier; for a real-world example you need to look no further than to JMock. I have implemented a Runner that makes it possible to do:
@RunWith(RuntimeIgnoreable.class) public final class MyTest { @Test public void perhapsIgnored() { ignoreIf(perhapsTrue()) // ... the rest of the test-case. } }
Neat, ey? I think so at least. What's even neater is that the RuntimeIgnoreable class and the ignoreIf method was embaressingly straight-forward to implement. You can browse the code, or look at the individuals files:

Oh, one final note: this was develop for JUnit 4.3. If you are using any other JUnit version, the you prbably need to make some minor changes to the code.

Update: I just realize that JUnit Extensions does this (among aother things)...

Performance gain of memoization in Ruby

2008-09-18T09:22:00.000-07:00

I and a some friends at work are developing a code generator that simplifies how we use a third-party library. Basically, the problems with the library are:

Hard to write code: we wish to express "get X.Y.Z", but the library force us to write "get Y from X by doing actions A and B, check that the result is a Y, cast it to a Y and then get Z by doing C actions and D". You get the point...
Hard to read code: given the code to "get X.Y.Z" is extremely hard to understand that it X.Y.Z that it returns. Self-documenting code is basically impossible to achieve here. We have tried, and fia
The library has no interfaces what-so-ever, making it very hard to our own code.

We've developed the code generator without any effort to make it fast (making it correct is hard enought). However, there have been a few instances where we simply "had to" optimize, because our test-cases started to take minutes to complete. Not good at all.

The first optimization we did was to write the parse tree of a file (which rarely changes) to disk by marshalling the Ruby objects. This made the parse phase go from 2-4 minutes to instantaneous. It was quite simple to implement, too. Very good! Actuallt, we didn't even use a profiler for this because it was to utterly obvious that it was the parse phase that was the bottleneck.

For the second optimization, though, we used a profiler. We found that a single method was responsible for around 90% of the used CPU time and that is was called alot. What to do?

Well, lucky us, we had been very careful to not have any state in our classes. That is, the code generator is purely functional (well, almost) . This made it possible for us to cache the result of the method the first time it was called, and use the cached value for all consecutive calls. (This only took one additional line of code, by the way.) We ran our test-suit and it passed. Great!

We ran the profiler again. The performance gain was 25 fold. Good stuff.

For me, this illustraits the age old truth that you should only optimize when you know you need to optimze and what/where to optimize. But it also shows how easy it is to optimize functional code, especially if there is a good test-suit making sure you don't mess anything up.

Thoughts on naming methods and classes

2008-09-13T05:24:00.000-07:00

This may seem like a trivial thing to discuss, but I actually think is quite important because the name of a method or class can change how you think about a particualr piece of code. For me, there are at least two ways of naming a method:

What it does, e.g., donaldDuck = ducks.findByName("Donald"). This is probably the name you come up with when you realize that you need the particular method ("How do I ...? Ah, I need to find the duck named 'Donald'. Then I can ...").
what it returns or how it will be used, e.g., donaldDuck = ducks.named("Donald"). I usually come up with this type of names when I think about the contexts the method will be called from. That is, how the code will look when you read it.

Let's take a concrete example to illustrait. Assume that we have a class Bag representing a set of objects. This class have a constructor taking a single Class argument that is the type of the objects the Bag contains. Thus, to get your self a new fancy bag you do:

final Bag<Apple> appleBag = new Bag<Apple>(Apple.class);

"Yuck", you think to your self, "that's a lot of code just to get one lousy bag". To remedy this, you decide to write a static factory method in the Bag class. How should should you name this method?

What it does: static <T> Bag<T> newBag(final Class<T> contentType)
How/where it will be used: static <T> Bag<T> of(final Class<T> contentType)

Now, to put this into context:
01 void Bag<Appple> chooseStylishBag() { 02 if (isOutOfStule(oldBag)) 03 return Bag.of(Apples.class); 04 return oldBag; 05 }

I think line 03 reads very nice. It's short and to the point, and does not expose implementation deatils, etc.

All is good with that bag buissness -- or at least so you though. However, after a few days a fellow programmer says that (s)he does not like the name of the method because it is not clear that it create a new empty bag. You respond 'well, you could just read the documentation for the of method'. You have't even completed that sentence before your colleague replies 'good code should not need documentation! It should be self-documented!'. (S)he is of course right. What to do?

Let's go back and rewrite the chooseStylishBag method such that it is clear that it returns an empty Bag.
01 void Bag<Apple>> chooseStylishBag() { 02 if (isOutOfStule(oldBag)) 03 return EmptyBag.of(Apples.class); 04 return oldBag; 05 }
That is, we've moved the of factory method to a separate factory class that is called EmptyBag. Your angry colleague does not complain any more. All is calm again.

Greatest pair-programming tool ever?

2008-08-26T12:57:00.000-07:00

This has to be one of the greatest thing for pair-programmers since large wide-screen monitors. I haven't tried it yet though, so perhaps I'm wrong. :) Seems like a really really nice plug-in for Eclipse, though.

Checked exceptions exposes implementation?

2008-08-25T11:29:00.000-07:00

I've read and heard the phrase Checked exceptions are evil! They expose implementation details! a couple of time (last time was an entartaining read for several other reasons...). I really don't understand this statement (hey, you, explain to me please).

How can the EncodingException part of the code below expose implementation details when void encode() does not? The first say I can fail to encode, the latter say I can encode. What's the difference?


 interface Encoder {
     void encode(Object o) throws EncodingException;
 }

For me, checked exceptions are vital to enforce proper error handling. But this can (probably) only be achieved if the exceptions fits the problem domain. For instance, throwing an IOException in the interface above would be really really bad because it exposes details of the Encoder, e.g., that is uses the network, or whatever. On the other hand, the only thing EncodingException exposes is that an Encoder can fail to encode the provided object. That's not an implementation detail, I think, that's the Encoder being honest and not hiding it flaws.

One of the most important lesson I've learnt from using exceptions is the importance of doing try-catch-wrap-throw. For example, if an implementation of Encoder uses a method that throws IOException then the proper way of handling such exception is to catch it, wrap it in a EncodingException and throw it to the client of the Encoder. This cleans up ugly interfaces that throws many exceptions, resulting in clear description (with semantics, yeay!) of what can go wrong when a method is called. Exceptions that fits the problem domain is the key.

A couple of times I've let domain exceptions inherit from each other to define that, for example, a RangeException is a ConfigurationException. This seemed like a good idea to me at the time, however, it seldom helped the design (it didn't make it worse either, though). In fact, the only time I find it useful is when you need to distinguish between thrown exceptions in one place but handle them in the same way in a nother place. For example (where LeftException and RightException inherits from BaseException):


interface Something {
   void doIt() throws LeftException, RightException;
}

class HandlesExceptionsSeparately {
   void method(Something s) {
       try {
           s.doIt()
       } catch(LeftException e) {
           // handle it
       } catch (RightException e) {
           // handle in another way) {
       }
   }
}

class HandlesExceptionsTogether {
   void method(Something s) {
       try {
           s.doIt()
       } catch(BaseException e) {
           // handles both
       }
   }
}

But as I said, this is not very common for me. Although if you are developing a library and wish the user to have the ability to handle the different error-cases separetely, then could be useful.

Well, these are some of my thoughts on checked exceptions. In summary: I think they're good stuff if done well. :)

Fear and Loathing in Parse Vegas

2008-08-03T03:14:00.001-07:00

Martin Fowler writes about parser fear and I have to say "guilty as charged". I've done a few DSL but all have be so simple that I could hand-write a parser using regular expressions and other string manipulations. To be honest, the resulting parser would probably be easier to understand, maintain, etc, if it was developed using a proper grammar and a parser generator. Despite (knowing) this, I kept writing those convoluted hand-written parsers.

I did the compiler class at the university and I'm intressted in most things programming langage related, e.g., compilers and parsers. Despite this I never actually done a parser (with proper grammar) by my self. Why? I had parser fear.

Fowler writes:

So why is there an unreasonable fear of writing parsers for DSLs? I think it boils down to two main reasons.
You didn't do the compiler class at university and therefore think parsers are scary.
You did do the compiler class at university and are therefore convinced that parsers are scary.

I think the last bullet explains why I never did a proper-grammar-parser by my self.

However, the last time I had to write a parser I (finally) realized that a proper-grammar-parser was a better idea than trying to hand-write something convoluted. The parser should be implemented in Ruby, so I googled (is that a verb now?) and found a generic recursive decent parser -- all I had to do was to write the grammar, which was straight forward.

There were several resons that finally made me take the step to use a proper parser:

The language was complex enough to make my old approach unsuitable
The parser was really easy to integrate with my other Ruby code
No separate step for generating the parser (i.e. short turn-around time, and less complexity because there is no code generation)

In essense: it was easy to use and test. That was the cure for my (irrational) anxiety towards parsers.

Lessons from a debugger

2008-07-03T12:13:00.000-07:00

A few days ago I got undefined method `some_method' for nil:NilClass when I executed a test-case I've just had written for a quite well-tested class. The test-case tested input that the class hadn't been designed to handled, but now I needed the class to handle it.

Knowing that there was a suit of test-cases making sure I didn't break anything, I just added return if (!thing) (where thing is the object the some_method was called on) and run the suit again. And gues what? All test-passed -- including the one I just written that didn't pass. I wrote another one testing a similar scenario and it also passed. I was satisfied.

Why did I add that nil-check? Well, the error appeared deep in a recursive call-chain, and I simply guessed that the recursion should be stopped if thing was nil. I didn't know -- I just guessed.

The point is that I didn't have to know, because if I was wrong any of the class test or multi-class tests would tell me I was. This is all good right? Well, it's not all good. Why? I'll tell you in a moment.

But first, think about a hard problem that you solved by putting in more effort than usual -- persuading someone to test more, parsing a proprietary file format, writing C++ or reading Perl -- any hard problem will do. I'm pretty sure you learnt something really valueable from that experience (even though it didn't feel that way while solving it...). I'm sure we learn a lot from solving any problem by putting in more effort than ususal.

Now, back to my story about the nil fix that made the test-case pass. What did I learn from fixing it by adding a line that I simply guessed should be there? Zip, nothing, ingenting. Of course, this shows that well-tested code is a Good Thing, but this isn't news to anyone. (By the way, note that a Good Thing isn't trademarked, registered, closed-sourced, or anything like that. Its free to use and I encurage you to do so as often as possible. :) Of course, any improvements you make to a Good Thing have to be shared with the community.)

On the other hand, what would I have to do if the class was poorly tested? I would have to understand what the code did by reading, test/run it by hand, debug it, etc, before I added the nil-check. Then I would have to repeate the process to make sure everything worked as before. What would the outcome of all this work be? Probably the same nil-check as before, but I would also understand the code much better. Also, I might picked up some good design ideas, learnt to use the tools better, etc.

Now, I'm not saying that poorly tested code is good. What I am saying is that working with poorly tested code that forces you to fire up the debugger and step through the program will make you debug programs better. I'm saying that working with deep inheritage hiearchies will make you realize that inheritance isn't always a good thing. I'm also saying that reading code with a lot a mutable instance variables and class variables will make you appreciate (and use) 'final' or 'const' more.

To take this a bit further, I think you actually get worse at debugging if you developing in an environment where the code is well-tested, because you never have to debug anything. This is true for me, at least.

I've completely stopped using the debugger. I write test-cases that narrow down the problematic code instead. This combined with a few print-outs is all I need. I think this is easier, and more valuable in the long-run because my efforts are mirrored in a few test-cases that document that there was a bug that was fixed. Would I simply had fired up the debugger and found (and fixed) the problem, there would be no (exectubale) documentation of the bug-fix.

So, one way of becoming a better developer is, I think, to improving quality of untested code because it'll forces you to reason about the program and it's control flow based on scarce information (e.g., logs and stack-traces) among other things. On the other hand, working with well-tested code is much easier: write a test, make the change you have to make to the production code and run all tests. Do they still pass? Great! Code is ready to be checked-in. Good for the project's progress. What have you learnt? Nothing! Bad for you. In some sense.

The Blub paradox

2008-06-25T10:07:00.000-07:00

Yesterday I read someting interesting concerning how programming languages are compared:

«[T]o explain this point I'm going to use a hypothetical language called Blub. Blub falls right in the middle of the abtractness continuum. It is not the most powerful language, but it is more powerful than Cobol or machine language.

And in fact, our hypothetical Blub programmer wouldn't use either of them. Of course he wouldn't program in machine language. That's what compilers are for. And as for Cobol, he doesn't know how anyone can get anything done with it. It doesn't even have x (Blub feature of your choice).

As long as our hypothetical Blub programmer is looking down the power continuum, he knows he's looking down. Languages less powerful than Blub are obviously less powerful, because they're missing some feature he's used to. But when our hypothetical Blub programmer looks in the other direction, up the power continuum, he doesn't realize he's looking up. What he sees are merely weird languages. He probably considers them about equivalent in power to Blub, but with all this other hairy stuff thrown in as well. Blub is good enough for him, because he thinks in Blub.

When we switch to the point of view of a programmer using any of the languages higher up the power continuum, however, we find that he in turn looks down upon Blub. How can you get anything done in Blub? It doesn't even have y.

By induction, the only programmers in a position to see all the differences in power between the various languages are those who understand the most powerful one. (This is probably what Eric Raymond meant about Lisp making you a better programmer.) You can't trust the opinions of the others, because of the Blub paradox: they're satisfied with whatever language they happen to use, because it dictates the way they think about programs.»

Check this out to read more about how to evaluate programming languages.

LISP's mapcar for Java: onAll-collect

2008-06-04T08:39:00.000-07:00

I've been working on a project were I need to iterate over a set of objects, get some property from all objects in the collection, and store that property in a new collection. This wouldn't be much if an issue if I did it in LISP or Ruby or some think similar... but this is done in Java with th the java.util.Collection framework. The Collection framework is nice and all, but when I have to write:

List<SomeProperty> allProperties(List<SomeClass> objects) {
  List<SomeProperty> properties = new ArrayList<SomeProperty>();
  for (SomeClass c : objects)
    properties.add(c.getProperty());
  return properties;
}

when all I really wish to say is:

(defun all-propreties (objects)
  (mapcar get-property objects))

I get a bit sad. Sure computer technology is progressing, but are computer languages? LISP appeared in the late 50-ies and Java in the mid 90-ties, but looking at the code above I can't really tell that there is almost 40 years between these two languages. Crazy...

Anyway, to make me a bit happier I started to think about how the Java code above could be improved to make it a little bit more terse. What I came up with was this:

List<SomeProperty> allProperties(Bag<SomeClass> objects) {
  return objects.collect(objects.onAll().getProperty());
}

which I honestly think is pretty neat. Then again, I'm just an ape-descended life form who are so amazingly primitive that I still think digital watches are a pretty neat idea too.

How does this work? Well, first of all the objects variable is not the same type in the two Java examples above. In the latter example, it is a class that I've implemented specially to deal with the scenario described. This class, which is called Bag<T>, has a method onAll(T) that returns an dynamic proxy implementing the T interface. That is, in the example above the objects.onAll() returns an instance of the SomeProperty interface.

This dynamic proxy handles every method call it receives by calling that method on each object in the Bag. Also, if the called method is non-void, then it returns whatever the last object in the Bag returned. This means that bag.onAll().someMethod() behaves just as thing.someMethod() if bag contains just the thing objects. This is a Good Thing in my book. :)

How about the Bag.collect method?, you ask. Funny you should ask that. I was just getting to that, I reply. Cut to the chase already!, you say. Cool it, I say, or there won't be any desert!.

(Ok, I'm getting a bit carried away.)

The Bag.collect simply returns the set of return values got when last calling a method on the onAll-object. Ehm, it a bit hard explain with words... but I think you understand. If you don't, look at the code and test-cases. :)

Note that the onAll method returns an object that can be used for more than what's described above. Whenever you need to treat a set of objects as if they were one object, for instance the Observer pattern, the onAll-object simplifies alot.

What makes a class?

2008-05-20T11:21:00.000-07:00

A few days ago, when I was "merrily" washing my dishes, I started to think about what makes a class necessary. That is, how we could identify code that should be placed in a class. I came up with a few obvious cases, and some less obivous. Obvious:

a new domain entity is needed,
to simplify testing,
remove conditional logic and special cases,
remove duplicated code,
move private private methods of a class to a new class; and
split a class that has multiple responsibilities.

Yeah, I know, ob-vio-us... But as I said, when I joyfully made my forks and spoons clean and shiny, I found a couple of cases that are commonly ignored or missed (at least by me, until now):

there are recurring patterns in variable names and variable type, e.g., java.nio.ByteBuffer payload = ... indicates that there is a need for a Payload class,
circular dependencies between classes can be solved by introducing a new class, e.g., if Alice and Bob has references to each other for exchanging messages, then a Channel should be introduced that they both will use to send and receive messages;
an exception exposing implementation details should be replaced with a new exception mathing the abstraction level of the class/method throwing the exception,

A comment on classes that solves circular dependencies: it is possible to solve this kind of dependency by simply introducing an interface (e.g., Alice and Bob could implement a MessageReceiver interface), but this misses the point a wish to make. By introducing a new class instead of an interface, domain logic can be placed where it is more suitable (e.g., the Channel can take care of serializing the messages passes between Alice and Bob).

Anyway, these are a few ways we can use classes to simplify code by introducing additional classes. There are probably a lot more... :)

Oh, by the way: some exceptions in the packages java.... miss a SomeException(String description, Throwable cause) constructor. Why is this? It makes catch-wrap-rethrow really hard. This is very important for hiding imlementation details.

Furthermore, why are there no proper hiearchy for (example for) the exceptions thrown by the reflection mechanism? I hate to catch four-five exceptions every time I do something with reflection... NoSuchMethodException, SecurityException, NoSuchFieldException, InvocationTargetException?! Come on! Why can't I just catch ReflectionException and get it over with? Also, give me multi-catch so that I can catch more than one Exception in each catch-block. Please!

Well, who ever said Java was perfect? Or even close to perfect...

Do not write tests for your code!

2008-05-07T07:34:00.000-07:00

I am of the opinion that developers should not write test for their own code. The reason is that the tests just test that the production code does what it does -- not necessarily that it does the right thing. That is, the tests just "mirrors" the production code. In fact, the test can actually test the wrong thing entirely!

On the other hand, if someone else writes the tests, then he/she does not know any details about the implementation, thus the tests do not mirror the production code.

Of course, there are problems with this... how does the tester know what the code is supposed to do? Good documentation? The trouble is that the documentation will (probably) describe what the code does, not what it is supposed to do. Why? Because it (probably) written after the code. Also, to use an understatement: documentation is boring.

The point I'm trying to make is that it is very hard to express what a piece of code is supposed to do when that code is already written. Unless, of course, there are a few test-cases for that piece of code. To my experience, test-cases describe what code is supposed to do very accurately.

Ok, I think you get where I'm going with this so I'm just going to cut to the chase. I hope you are of the opinion, like me, that developers should not write test for their own code. They should, however, write code passing their tests.

The Zen of regular expressions

2008-04-28T07:52:00.000-07:00

I'm a proud owner, and sometimes wearer, of this (scroll down to Regular Expressions Shirt). On my way home from work today I started to think about whether I really know regular expressions. Sure, I can write expressions that match fairly complex patterns... but do I really know them? I came to the conclusion that I know regexp in the same sense as most seven-year-olds (i.e., first graders) can read and write: they know letter and short words, but not much more.

The funny thing is that if I had been asked this question a few years ago I would have answered of course I know regexps without much thought. Does that mean that I know less about regular expression now than I did then? No, I know more. I now know enough to know that I don't know them.

The Zen of regular expressions:

The first step towards knowing regular expressions is to realize you do not know them.

Since I'm just starting to reach this first step, I cannot tell what the next step will be... or how many steps there are. :)

Boring stuff you have to implement: Configuration, part 2

2008-04-21T08:23:00.000-07:00

A while ago I wrote a post where I proposed an easy way of specifying the configuration of an application. The idea is basically to define a configuration parameter by annotating a methods with information that describes the parameter. Of course, the value of the parameter is retrieved by calling the annotated method. My previous post contains an example.

To implement this easy-configuration-thingie I use dynamic proxies. If you haven't heard of dynamic proxies you have missed one of Javas powerful facilities for metaprogramming. Under the circumstances (e.g., static type-checking) I think it's pretty easy to use too.

The basic idea behind dynamic proxies is quite simple: let all calls to methods of an interface be delegated to another method. This method is called invoke and is declared in java.lang.reflect.InvocationHandler.

As you may suspect, the invoke method receives the all arguements given to the method defined in the interface (i.e., the method that delegated to invoke). It also receives an arguments that describes which method that was called; this is an java.lang.reflect.Method object, which among other things, contains the method's annotations.

Back to the original topic: configuration. How can all this annotation stuff and proxy fluff be used to define and read configuration?

Well, as the example in my earlier post shows, the interface that defines the configuration is annotated with the name and the type of the configuration parameter. Since the method's annotations are available to the invoke method, invoke can use the parameter name to look up its value (in a hashmap, or similarly) and return it. It's as simple as that!

I've made a simple implementation of this availble here (follow the instructions on Google Code if you wish to check-out the entire Eclipse project).
Note that some more development is needed before this code is useful, since it does not
read any configuration from file (only default values can be read).

In general, I tend to think that annotations simply are additional arguments to the annotated method (although a bit harder to use than ordinary arguments). This way of looking at annotations is even more suitable when used together with dynamic proxies, I think.

You probably already have thought of this, but there are several other ways of using annotations + dynamic proxies: I've used it to parse binary messages and command line arguments (before I know about JewelCLI), and I guess you can come up with several other examples...

Oups, sorry.

2008-04-17T11:39:00.000-07:00

While updating my blog (I realized that I misspelled 'programmatically') I accidentily changed the address (on www.javablogs.com) to my other blog (in swedish), which does not discuss Java. My apologies to www.javablogs.com.

Inheritance is overrated

2008-04-16T11:46:00.000-07:00

I like the object-oriented way of developing software -- especially if there is some functional flawor in it. In most language it is fairly easy to at least emulate a functional programming language by simply changing the way you think about the problem and the solution.

When I think in an functional way about a problem I have to solve using an object-oriented language, objects become collections of related functions (with this I mean pure function, i.e., they have no side effects). That is, I think about the program as lambdas that is passed around, rather than instances of classes. This may sound like a trivial and superficial difference but it is not.

I have found that if I solve a problem in a functional way, the components of the solution (functions, classes, etc) are less coupled than if I solve it in an object-oriented way. Why is this?

One reason it that an object A is provided with objects B..Z that A needs for doing whatever it needs to do. That is, A only relies on that it gets something that it useful for its purposes, instead on relying on a particular implementation. Another reason is that classes' methods are often pure functions, which decreases coupling because classes does not depend on the state of another class or in which order methods are called.

Enough rambling. Now to the point. The first reason basically says that a functional mind-set results in an structure of has-a relations between objects, instead of the "object-oriented way" is-a. With "is-a" I mean class-inheritance (the extends keyword in Java), which is the strongest way of coupling two classes and the most difficult to reuse, refactor, and understand -- at least for me.

On the other hand, I find interface-inheritance (the implements keyword in Java) very useful and I rely on it dayly.

If find it a bit funny that during the years I have used object-oriented languages, I have not once used inheritance... without regretting it. I'm getting better and better, of course, and during the last year I haven't used inheritance at all... and I'm not regretting it.

Maybe it just me, but I find inheritance overrated.

Making deactivated logging 100 times faster

2008-04-12T08:28:00.000-07:00

I think the java.util.logging is a nice logging framework: it's easy to do simple things yet it is not limited. You can easily tweak it using custom filters, formatters, and handlers. One thing I do not like with it, however, is its performance.

The problem with logging
I have no problem with the performance of java.lang.logging when the logging is activated. It's the performance when logging is deactivated that is an issue for me. The problem, as I see it, is that when


  logger.info("someting: " + something.toString());

is executed, the argument to info is created (by concatinating two string, which is computationally heavy) despite logging being deactivated. This means that a string will be created and then directly thrown away without being used. To make things even worse, there is even a greater performance penalty if the toString method of something is computionally heavy.

This is not problem with java.util.logging per se, but rather a problem with the Java language. Don't get me wrong -- I like Java -- but in certain areas Java is simply too limited/limiting. I see at least three way of solving the problem described above:

introducing some kind of macros to the language,
using aspect-oriented programming, or
performing string concatination lazily.

Personly, I think that the common variant of macros (the C/C++-kind) it a Bad Thing. On the other hand, the other variant of macros (the Lisp-kind) does not fit nicely in the Java languange because those kinds of macros operate on the AST (this is perfectly ok in Lisp because Lisp does not have any syntax -- you're actually creating the AST when you write the program).

The second solution to the problem is aspect-oriented programming. To be honest, I don't know enough about that to be able to discuss it here. With the limited knowledge I do have, however, I think that it should be possible to instrument the piece of code above such that you get the following sematic:


  if (logger.logsAtLevel(Level.INFO) {
    logger.info("someting: " + something.toString());
  }

The third solution -- performing string concatination lazily -- is the solution I will discuss for the rest of this post. I'm assuming that the methods used to create the log message, e.g., the toString method, are are pure functions, i.e., has no side-effect. This is a perfectly legitimate assumption because deactivated logging should have no side effect as it is.

Lazy string concatination
Ok, so how can we make string concatination in Java lazy? In C++ we could have overloaded the operator +, but this is not possible in Java. One hacker-ish solution would be to implement new String and StringBuilder classes (which the compiler uses to implement string concatination) which performs concatination lazily, but this not trivial... (I have actually tried... (and failed)). Instead, we can implement a thin wrapper around java.util.logging.Logger with the following methods:


  MyLogger log(Object msg);
  MyLogger log(Object msg1, Object msg2);
  MyLogger log(Object msg1, Object msg2, Object msg3);
  // ... and so on.
  void info(Object msg);
  // ... and all the the other levels.

which is used like this:


  myLogger.log("Received message: ", msg, " from ").info(msgProvider);

which is the equivalent of


  logger.info("Received message: " + msg + " from " + msgProvider);

when using a java.util.logging.Logger. The log methods is simply implemented by storing the references to the objects given as arguments. The info method is implemented by calling toString on its argument and the argument given to log if the logging is actived, otherwise it does nothing.

I (kind of) have implemented such class; the difference is that instead of wrapping a java.util.logging.Logger my class uses a java.util.logging.Handler directly. The interface of this class, which I named Ln4j (pun definitely intended), is the same as MyLogger above, however.

Performance measuments
So, what kinds of performance numbers can we expect? <disclamer>I'm definitely no expert in measuring performance, but I have tried my best to create fair benchmarks.</disclamer> These are the benchmarks:

logging single constant string,
concatinating two constant string and log the result,
concatinating a constant string and a variable string and log the result,
concatinating six short (4 characters) variable strings,
concatinating six long (40 characters) variable strings,
concatinating a constant string and an int and log the result,
concatinating a constant string and a List<double> (of length 8) and log the result.

I ran these benchmars with and without the -server switch to the JVM and with logging activated and with logging deactivated. This is the result.

In summary: with logging activated ln4j performs a bit faster than java.util.logging. However, since ln4j is quite simple (e.g., it has no log levels) this small performance advantage would probably disapper if ln4j implemented all functionality provided by java.util.logging.Logger.
When running the benchmarks with logging deactivated, there is usually considerable performance gains (no, the post title is no exaggeration). Of course, exact numbers depend on what is logged. When logging a single constant ln4j is actually somewhat slower. However, in the benchmark that logs a list, ln4j is 600-700 times faster than java.util.logging. That optimzation for ya!

I hope this post was informative and that you have learned something from reading it. I learned a lot when experimenting with lazy string concatination; let's hope it will native in Java 8. :)

Oh, I almost forgot, here and here are the source used in the benchmarks.