Buguntu family album

This is a very cool family album: http://blog.nizarus.org/2010/04/ubuntu-the-family-album

Can't wait to upgrade to 10.04, my current install (9.10) is working like crap.

Template metaprogramming III: Entering Pandemonium

If you are here and you have read the previous two parts then you are crazy. If you haven't then go and read it, then never come back if you value your sanity at all. We saw last time an example of a factorial using template metaprogramming, now it's time for something a little bit more fun. I was thinking on lists, but that's a bit too much for starters: let's do some more math. Now with fractions!

So, how would you express a fraction? The fun part, and you already know this, you have only types (*), there are no variables. Luckly static const int saves the day:

template < int N, int D > struct Frak {
	static const long Num = N;
	static const long Den = D;
};

Woo hoo... how boring, let's do something on those Fraktions, so they don't get bored... like multiplying:

template < int N, typename X > struct ScalarMultiplication {
	static const long Num = N * X::Num;
	static const long Den = N * X::Den;
};

Well that does the job, I guess, but it's ugly. Too ugly... why would we redefine a Fraction when we already have a great definition? Let's try again:

template < int N, typename X > struct ScalarMultiplication {
	typedef Frak< N*X::Num, N*X::Den > result;
};

OK, now you think I'm pulling your leg, but, promise, I'm not. This actually works, and it looks nice! Check out that sexy typedef: you can't have variables, we said, so instead we return types. Frak is a type when binded to two concrete values, so Frak is a type too. Just typedef it to a result and be done with it.

How do we test if it worked? Easy:

int main() {
	typedef Frak< 2, 3 > Two_Thirds;
	typedef ScalarMultiplication< 2, Two_Thirds >::result Four_Sixths;
	std::cout << Four_Sixths::Num << "/" << Four_Sixths::Den << "n";
}

Nice! By now you should have learned how to return new types, which are the result types for template metaprogramming devices. You should have also learnt how to write a device which operates on another template device... congratulations, that's metaprogramming. Next time, something a little bit more interesting.

(*) Boring theory rant: What do I mean you can't have return values so you must use types instead? Let's see: a variable or an attribute are both parts of an object. If I have a variable named height in a class named Person, then each person gets his own height. Even if the numeric value is the same there won't be two shared height attributes. On the other hand static const vars are defining parts of classes, not objects; stupidity could be static const var of Person (only in this case we'd all be equally stupid... this is were the analogy falls apart, I'm sorry).

Knowing the difference between an object and a class defining characteristics, it is clear we can only use static const stuff - it's nonsense talking about template-objects, it's all about template classes.

Ubuntu: Dual screen still FUBAR'd

I'm quite sure I have written about this before but I'm too lazy to search for the article right now. Well, dual screens in Ubuntu still sucks. Much less than ever before, granted, but it still works quite bad. In my specific case the whole desktop is shown, in both monitors (which by itself is a huge improvement over previous versions) but the working area is clipped to the notebook's monitor size. Not nice.

To fix this problem (more like hacking it away, actually) I keep a handy bash script in the top left corner on my desktop:

xrandr --output HDMI-2 --right-of HDMI-1 --mode 1680x1050 --rotate normal

Also, as I have two nice rotable monitors at work it's nice that now Ubuntu supports actually rotating the picture displayed in the monitor (thanks Ubuntu for coming up to speed... with windows 98, that is). Obviously I keep another script for this, as it doesn't really work by default:

xrandr --output HDMI-1 --left-of HDMI-2 --mode 1680x1050 --rotate left
xrandr --output HDMI-2 --left-of HDMI-1 --mode 1680x1050 --rotate normal

Even though I love bashing Ubuntu (and bash) I'm quite confident most, if not all, of this issues will be gone in future versions of the OS.

Template metaprogramming II: Openning the box

We saw last time how to print a factorial using only template metaprogramming, but didn't explain anything about it. I promised to fix that in this article. Starting by the very beginning:

template <int N> struct Factorial {
	static const int result = N * Factorial<N-1>::result;
};

template <> struct Factorial<0> {
	static const int result = 1;
};

int main() {
	std::cout << Factorial<5>::result << "n";
	return 0;
}

Why static const?

Templates get evaluated on compile time, remember? That means all that code actually executes when compiling the source, not when executing the resulting binary (assuming it actually compiles, of course). Having as a constraint the fact that all your code must resolve on compile time means only const vars make sense. Also, as you're working with classes (templates are applied to classes, not objects) only static objects make sense.

That explains the static const thing, what about the Factorial<0>? Well it's obviously an edge case. It describes a specific case of a Factorial. It's a specialization! Why do we need it? Take a look again at the definition of struct Factorial: it's a recursive definition. How do we break from the recursive loop? With a base case, obviously.

If this is starting to remind you of anything then you are crazier than you think, and you already know some Haskel. Indeed, template metaprogramming has some resemblance to Haskel programming: no const "variables", no for-loop (only recursion), base cases (pattern matching), and cryptic error messages which makes you want to jump of a cliff.

A useful trick I learned when working with Haskel (many many years ago) is to declare the problem, instead of thinking it. For our problem the factorial of a number is defined as said number times the factorial of that same number minus one, being the factorial of 0 always 1.

Translating:

// the factorial of a number is defined as said number times
// the factorial of that same number minus one

template <int N> struct Factorial {
	static const int result = N * Factorial<N-1>::result;
};

// being the factorial of 0 always 1.
template <> struct Factorial<0> {
	static const int result = 1;
};

That's good for a first approach... next time something more complex (and less theory, promise).

---

Thanks to Stéphane Michaut for reporting broken code in this page.

Vim tip: Word count

Trying to count words is a common task. Whenever you're writting a report for class, that is. There are some legitimate reasons but they don't matter now: it's a great chance to show off how great Vim is.

First method: Type ggVgY"*p to copy the whole text. Then paste it into word and use word count.

Second method: Type %!wc -w, which executes wc on each line.
Third method: Type g^g (g, CTRL+g) and watch the bottom of your screen.

As ussual, Vim rocks.

Company policy

I liked this one:

Great for a 404.

Template metaprogramming: A slow descent towards utter maddness

There have been some articles dealing with template metaprogramming over here. Things like template <int n>, which look really weird (but behave in an even more bizarre way). This post starts a series of articles following the contrived and tortuous path down insanity lane and into the mouth of the beast. When we are done things like typedef typename should be clearer than i=i++, should you dare to keep on reading.

First things first: Why TF would I...

Instead of explaining why let's start backwards: assume you already want to start learning some template metaprogramming. Yeah, I'm sure there are many legitimate reasons, like job security or job security perhaps, but if you want to learn template metaprogramming the most likely explanation is you are nuts. Plain and simple.

Practical uses? Not really. Yeah, there are some (if you are a boost developer) and lets you write some neat stuff, but in your every day job you are most likely never going to use them. And that is a good thing (tm), for mere mortal programmers tend to like getting their jobs done. Having said that, let's learn some template metaprogramming!

Metawhat?

First, we need to start with a little clarification: using template to parametrize a class, something like std::vector does, is not template metaprogramming. That's just a generic class (Java-pun intended). That is indeed a useful case for templates, but it has little fun in it.

Template metaprogramming is much more fun than mere generic classes. The template processing in C++ is a language on it's own (no, really, like a Turing complete language and everything), though a language with very weird syntax and a very strange "design". Design between quotes because there was no design in its initial stages, template processing is a sub-language organically grown as a side effect of adding partial templates specialization (more on this later), so don't expect a nice language. Here, let me show you an example of another organically grown language: Microsoft's .bat scripting. You can imagine now what kind of beast this is if we are comparing it to bat scripts, right? (Nitpickers note. yup, I do know bat scripting is not a real language as it's not Turing complete. The comparison still stands though).

First step

Enough chatter. Let's start with an empty program and work our way down from there:

template <int N> struct Factorial {
 static const int result = N * Factorial::result;
};

template <> struct Factorial<0> {
 static const int result = 1;
};

int main() {
 std::cout << Factorial<5>::result << "n";
 retrun 0;
}

Whoa. Lots of magic going on there, on the simplest of all template metaprogramming tricks. But I don't feel like explaining it right now, I'm too sleepy, so I will leave that for next post.

Changing default file associations in gnome

It's been a long time since I posted a Linux related tip. Not in the mood I guess... well, this is one which really annoyed me, until I found out how easy it is: I hate some of the default file associations in gnome. Movieplayer, for example, is a horrible choice. Breaking and devolving with each new distro release, I have decided to settle with vlc as my default movie player, yet I couldn't easily change the default file type association. After fiddling around with the thingy in gnome resembling a regedit (ugh) I found out the easy way:

* Right click the file for which you want to change default associations and click properties
* Select "open with" tab
* ...
* Profit!

I hearth Berkeley

error: cannot convert ‘Db**’ to ‘DB**’ for argument ‘1’ to ‘int db_create(DB**, DB_ENV*, u_int32_t)’

Thank you very much, Oracle Berkeley, for having a type named Db and another one named DB, and for never using namespaces. It makes my work a much more interesting challenge (*).

(*) Yeah, I know, Db is for the C++ wrapper and DB is for the plain C API (**). So what, I hate you all anyway.

(**) I'm working on a project with Berekley DB and it has enough WTF moments for a complete blog... I may post some of them, as a catharsis method. (***)

(***) Or because it has some interesting stuff too... who knows. Recursive note FTW (**). I think I have already done that, haven't I?

Fixed string: POD String datatype

We saw in POD types in C++ the difference between a POD and a non-POD type but the question of how to apply this knowledge to persist an std::string-like object remained open. This problem is a specific version of how to persist an object from which you know the size but has internal buffers using the heap instead of using only stack memory.

The best example for this case is, perhaps, a column from a table. You know the upper limit of the string's length but using std::string is clearly much better (easier) than a char[N]. Yet you'd be loosing the ability to persist this object in a generic way (i.e. copying memory instead of knowing the object's internal structure).

Well, there's an easy solution (though more than a solution I'd call it an acceptable trade-off) in which you can create a char[N], a char buffer, with std::string-like behaviour and yet POD-safe (almost POD safe actually, as we'll see now).

What's a POD?

POD datatypes, though informally explained in "POD types in C++" have a formal definition which you can look in Google. For practical terms a POD is a trivial object: no custom constructors, no virtual functions, nada of the fun stuff C++ can give you (or a native type, obviously).

Although this definition gives us quite a hard constraint we can create a quasi POD object (!) that does not conform to the standard definition of POD, yet has all the properties of one. This is the kind of struct we'll be creating. It would crash our program if used in a printf, but resides completly on the stack.

Implementing a POD string

A word of warning: ignore for now the "template " part; that's a template metaprogramming technique which we'll discuss some other day.

template  <int N> struct FixedString {
   mutable char str[N];
   FixedString() { str[0] = 'X'; }
   FixedString(const char* rid){ memcpy(str, rid, sizeof(str)); }
   FixedString(const FixedString &rid){ memcpy(str, rid.str, sizeof(str)); }
   operator const char*() const { return str; }
};

You can see now why I called it a trade-off: it works as we intend it to work but it does have its rough edges (most notably the const char/mutable part). It'll allow you to use a char[N] with some behaviour of an std::string; use it with caution.

POD types in C++

Let's say you have something like this:

typedef int A;
void x(A);

struct B {
   int b;
   B(int b) : b(b) {}
   virtual void x() = 0;
};

Regardless of what does function x do, what's the difference between A and B? Without getting too picky and leaving semantics aside, we may say there is no difference in behaviour. There's however a small gotcha there, which is completely irrelevant for C++ code but can bite you in the ass when interfacing C and C++. Would this work?

{
   A a; B b;

   // Case 1
   A *p = malloc(sizeof(A));
   memcpy(p, &a, sizeof(A));

   // Case 2
   B *p = malloc(sizeof(B));
   memcpy(p, &b, sizeof(B));
}

The answer is perhaps. In most cases it would work, in some cases it won't. C++ uses a vtable to dispatch virtual methods, so if I were to perform a memcpy of an object, then store it on disk and retrieve it afterwards I don't have any guarantees the vtable will still be valid. And that's leaving aside the case of objects having dynamically allocated memory themselves.

Wrapping up, the difference between A and B is simple: A is a POD (Plain Old Datatype, POJO for you Java guys) type, B is not. There are some other things non-POD objects can't do, for example this is invalid:

   B b;
   printf("%i", b);

Not only it's invalid: g++ emits a warning and then crashes on runtime (this is related to the use of vargs in functions with "..." params, but it's not important now).

Knowing what a POD object is, what would you do now if you had to persist (serialize) an std::string-like object? That's a topic for the next post.