Template Metaprogramming XV: Gemini

This is the end. My only reader, the end. After 15 chapters of template metaprogramming you should have learned why staying away from them is a good idea, but if you have been following this series then you should know now when and why they could be useful.

These posts were a compendium of mostly isolated data I found during my travels through the depths of metaprogramming tricks, there are books and people much more capable than me if you want to learn more about this subject (Modern C++ Design by Andrei Alexandrescu comes to mind).

The whole idea of having a cache and a virtual template method was nice, but after seeing the result I decided it was best to have a factory method and an IDL. It may not be so l33t, but whoever has to maintain the code after me will be grateful.

This is the last post on this topic because I feel I have written most, if not everything, I can transmit through this medium but also for an important reason, most likely I won't be working with C++ code so much from now on [1] so there won't be as many chances for me to see the dark, insane, side of this beautiful (in its own way) programming language in a programming language. I know most of you must have barely skimmed through these articles, but I still hope you enjoyed them.

[1] That's right, I'm leaving C++ for the dark side of development, I'll be working with Java from now on. Keep in mind this article may have been written a long time before it's published.

[2] Wow, it was a long time since I used the meta-post category

Redshift: Cool your monitor

I've been trying Redshift the last few days. It's a really cool (pun intended) and simple program. It just sits there all day long, doing nothing. Yeap, it's just one more pointless thing on your ps -ef list, up until noon, when it comes to life: it will adjust your monitor's temperature, gradually, from a cool color to a warmer color.

Say what?

I know what you are thinking. "Why the hell did I eat so much cake?". And probably something like "WTF? Monitor temperature? Mine is running cool, k thx bye" too. The monitor temperature (color temperature, to be more accurate) is the percieved temperature of an object emiting light at the specific wavelength of that color:

So, a blueish color means a higher temperature, and it's the natural ambience light color you see during the day. Towards the night the color temperature begins too cool down towards a more orange color. This is the temperature Redshift changes.

So what?

Fair question. After a couple million years our brains got used to seeing a hot color temperature during the day (do I have any reader that old?) so staring at a blue monitor all day will keep you awake all night long, the theory being that switching its temperature towards a reder color will help you sleep at night.

Does it work?

Probably not, but that doesn't make it any less cool (pun not intended). I think if you fine-tune this app to your sleeping hours it may be of some use, because otherwise you'll get a very dark screen at 5pm (don't you people know the timezone in Argentina is FOOBAR'd).

Quote of the week

It seems making a compile fail is actually quite easy. That’s what I have most experience with.

From "Template metaprogramming", chapter 10 by me

Template Metaprogramming XIV: Marathon

If you remember previous entry, we got our evil device to the point of getting a specific instance using only a type hint. Now we need to put all the code together. I won't add much to the code, you should be able to parse it yourself.

/***********************************************/
struct NIL {
    typedef NIL head;
    typedef NIL tail;
};

template <class H, class T=NIL> struct LST {
    typedef H head;
    typedef T tail;
};
/***********************************************/

/***********************************************/
template <class X, class Y> struct Eq { static const bool result = false; };
template <class X> struct Eq<X, X> { static const bool result = true; };
/***********************************************/

/***********************************************/
template <class Elm, class LST> struct Position {
private:
    typedef typename LST::head H;
    typedef typename LST::tail T;
    static const bool found = Eq<H, Elm>::result;
public:
    static const int result = found? 1 : 1 + Position<Elm, T>::result;
};

template <class Elm> struct Position<Elm, NIL> {
    static const int result = 0;
};
/***********************************************/


/***********************************************/
template <typename LST, int N> struct Nth {
	typedef typename LST::Tail Tail;
	typedef typename Nth<Tail, N-1>::result result;
};

template <typename LST> struct Nth<LST, 0> {
	typedef typename LST::head result;
};
/***********************************************/


/***********************************************/
template <typename Lst> struct Instances {
    typedef typename Lst::head Elm;
    Elm instance;
    Instances<typename Lst::tail> next;
};
template <> struct Instances<NIL> {};
/***********************************************/


/***********************************************/
template <int N, typename TypeLst> struct NthInstance {
    // This one isnt easy...
    
    // This is the next type in the list
    typedef typename TypeLst::tail TypeNext;

    //  * Nth::result is the Nth type in Lst (i.e. char, int, ...)
    typedef typename NthInstance<N-1, TypeNext>::NthInstanceType NthInstanceType;

    //  * typename Nth::result & is a reference to said type and the ret type
    template <typename InstancesLst>
    static NthInstanceType& get(InstancesLst &instances_lst) {
        return NthInstance<N-1, TypeNext>::get(instances_lst.next);
    }
};

// Remember, just for fun we choose a 1-based system (wtf..)
template <typename TypeLst> struct NthInstance<1, TypeLst> {
    typedef typename TypeLst::head NthInstanceType;

    template <typename InstancesLst>
    static NthInstanceType& get(InstancesLst &instances_lst) {
        return instances_lst.instance;
    }
};
/***********************************************/


class Facade {
    typedef LST<int, LST<char, LST<double> > > Lst;
    Instances<Lst> instances;

    public:
    template <typename PK> int find(PK) {
        return Position<PK, Lst>::result;
    }

    template <typename PK>
    // This is a difficult one... it should be parsed like this:
    //  1) Get the desired instance position using Position::result 
    //  2) Get the type @ the desired position with NthInstance::Type
    //  3) Define said type as a return type (with an & at the end, i.e. make
    //      it a reference to the return type)
    typename NthInstance< Position<PK, Lst>::result, Lst >::NthInstanceType&
    get_instance(PK) {
        const int idx_position = Position<PK, Lst>::result;
        typedef typename NthInstance<idx_position, Lst>::NthInstanceType IdxType;
        IdxType &idx = NthInstance<idx_position, Lst>::get( instances );
        return idx;
    }
};

#include <iostream>
int main() {
    Facade f;
    int &a = f.get_instance(1);
    char &b = f.get_instance('a');
    double &c = f.get_instance(1.0);
    a = 42; b = 'n'; c = 4.2;
    std::cout << f.get_instance(1) << "\n";
    std::cout << f.get_instance('a') << "\n";
    std::cout << f.get_instance(1.0) << "\n";
    a = 43; b = 'm'; c = 5.2;
    std::cout << f.get_instance(1) << "\n";
    std::cout << f.get_instance('a') << "\n";
    std::cout << f.get_instance(1.0) << "\n";
    return 0;
}

The only thing missing now is a map, to convert a primitive type to an index type, but that's trivial and so it will be left as an exercise for the reader (?). We just implemented the most evil code in the whole world. Next time, the conclusions.

Sorting by random in bash and mocp random updated

Random is nice. And now you can sort by random your output using sort -R. Why would this be useful? Well, I updated my mocp random script with a oneliner:

mocp -c && find -type d | sort -R | head -n1 | awk '{print """$0"""}'; | xargs mocp -a

C++ linking WTF

It is a commonly accepted fact that a succesfuly compiled application serves as enough proof of its correctness, but common wisdom doesn't say a thing about linking. If you like linker WTF moments, you'll love this snippet. Can you guess why won't it compile?

struct Foo {
    static const int x = 0;
    static const int y = 1;

    int z(bool x){
        return (x)? Foo::x : Foo::y;
    }
};

int main() {
    Foo z;
    std::cout << z.z(true);
    return 0;
}

Well, it does compile (gotcha!) but it just won't link. Yet it seems so simple... let's add some more mistery to this WTF moment, try this change:

    int z(bool x){
        int t = Foo::x;
        return (x)? t : Foo::y;
    }

Holy shit, now it compiles? WTF? Some more strangeness:

    int z(bool){
        return (true)? Foo::x : Foo::y;
    }

And again, now it compiles. WTF? I'll make a final change, this one should give you a clue about why it won't compile. Revert all changes back to the original code but add this two lines after Foo:

const int Foo::x;
const int Foo::y;

Though weird at first, now you should have a clear picture:

• The first case doesn't compiles: x and y are declared in struct Foo, yet the linker doesn't know in which translation unit they should be allocated.
• The second and third cases... well I'm not sure why does this compiles but it's probably because the linker can asume in which translation unit x and y should be allocated. I'm to lazy to check.
• In the last case we explicitly say where should x and y be. According to standard, this is how these two ints should be declared.

So, some linker strangeness. Beware, it's easy to get trapped by this one.

Vim Sexual Care

Vim bestows its users all sort of magical properties, among which now we can count increased sexual performance. I bet you didn't know, but Vim can help you keep your girl happy for days without end. Don't believe me? Check this page.

Template Metaprogramming XIII: Heart of Darkness

Last time we had a virtual template dispatch problem... we got to the point of knowing which was the index of the cache we were searching for, now we need to actually retrieve an instance of that cache. That's a problem. Why? To begin with, there are no instances, only types!

The next logical step would be to create a Map device, to map a list of types to a list of instances... let's see how can we do that, in pseudocode

instances( H|T ) <- [ create_instance(H), instances(T) ]
instances( NIL ) <- NIL

Looks easy. How can we map that to c++?

template <class Lst> struct Instance {
    typedef typename Lst::head Elm;
    Elm instance;
    Instance< typename Lst::tail > next;
};
template <> struct Instance<NIL> {};

#include <iostream>
using std::cout;

int main() {
    typedef LST<int, LST<char, LST<float> > > Lst;
    Instance<Lst> lst;
    lst.instance = 1;
    lst.next.instance = 'a';
    lst.next.next.instance = 3.1;
    std::cout << lst.next.instance << "n";
    return 0;
}

All those next.next.next.instance look ugly. Let's use some more meta-magic to get the Nth instance (why not a [] operator? several reasons, you can't mix non-const ints with templates nicely, there would be problems to define the return type... all those options are workable but it's easier if we do this in another device.

template <typename LST> struct Nth {
	typedef typename LST::tail Tail;
	typedef typename Nth::result result;
};
template <typename LST> struct Nth {
	typedef typename LST::head result;
};

Remember that one from the toolbox? Now we know how to get a specific index position, yet getting the instance is a different problem (the Nth device returns a type, not an instance). We should do something different, the problem is knowing the return type. What's the return type for the Nth instance of the Instances list?

   type <- Nth(TypesLst, Type)
   type var <- NthInstance(InstancesLst, N)

Not so easy, right? This is the translated C++:

template <int N, typename TypeLst> struct NthInstance {
    // This one isnt easy...
    
    // This is the next type in the list
    typedef typename TypeLst::tail TypeNext;

    //  * Nth::result is the Nth type in Lst (i.e. char, int, ...)
    typedef typename NthInstance<N-1, TypeLst>::NthInstanceType NthInstanceType;

    //  * typename Nth::result & is a reference to said type and the ret type
    template <InstancesLst>
    static NthInstanceType& get(InstancesLst &instances_lst) {
        return NthInstance::get(instances_lst.next);
    }
};

// Remember, just for fun we choose a 1-based system (wtf..)
template <typename TypeLst> struct NthInstance<1, TypeLst> {
    typedef typename TypeLst::head NthInstanceType;

    template <InstancesLst>
    static NthInstanceType& get(InstancesLst &instances_lst) {
        return instances_lst.instance;
    }
};

And the code from fetching the instance itself is even more difficult, so I'll leave that for next time.

Date time WTF

Another one to add to my growing list of bad things about Ubuntu. For some reason my clock froze. I only noticed it when it started to be dark outside, for me the time had frozen at about 17pm.

Template Metaprogramming XII: You Really Got a Hold on Me

Remember our virtual template method problem, from the other time? (I know, I said the answer was scheduled for a week after that post, but then I just forgot about it). May be we could avoid the virtual part by keeping a list of all our caches... how would we know which one should we dispatch the message to? Easy, using templates.

Instead of a list let's keep two, for twice the fun. One for the rows cache, another for the PKs. We can use PK to know which ROW Cache should we choose. Let's try to write a pseudo code for it:

ROW get_row(PK id) {
    pos <- Position of PK in pks_lst
    return cache[ pos ].get_row( id )
}

Doesn't look too hard. Building on our previous toolbox, let's use Eq, Position and the definition of a list:

struct NIL {
    typedef NIL head;
    typedef NIL tail;
};

template < class H, class T=NIL> struct LST {
    typedef H head;
    typedef T tail;
};

template <class X, class Y> struct Eq { static const bool result = false; };
template <class X> struct Eq<X, X> { static const bool result = true; };

template <class Elm, class LST> struct Position {
    private:
    typedef typename LST::head H;
    typedef typename LST::tail T;
    static const bool found = Eq<H, Elm>::result;
    public:
    static const int result = found? 1 : 1 + Position<Elm, T>::result;
};

template <class Elm> struct Position<Elm, NIL> {
    static const int result = 0;
};

class Facade {
    typedef LST<int, LST<char, LST<float> > > Lst;

    public:
    template <class PK> int find(PK) {
        return Position< PK, Lst >::result;
    }
};

#include <iostream>
using std::cout;

int main() {
    Facade f;
    std::cout << f.find(1.0) << "\n";
    return 0;
}

Great, now we can find an element on a list of types. The real virtual dispatch for the next entry :D

MySQL upsert, Oracle merge

How many times have you seen this "pattern"?

unsigned int row_count = foo->update();
if (row_count == 0) {
   foo->insert();
}

Wouldn't it be nice if you could write all that in a single line? Say, something like

foo->update_or_insert_if_it_doesnt_exists();

Well, good news, you can! Obviously it's not standard SQL, nothing useful ever is, but even so I think using an upsert (who comes up with those names?) can be quite good for your health.

So, how do you use it? It's easy;

INSERT INTO Table ( col1, col2 )
SELECT 'a', 'b'
ON DUPLICATE KEY UPDATE col1 = 'a', col2 = 'b';

Go on, try it, I'll wait. What? It didn't work? Oh, I forgot, you need to create a unique key so the engine can recognize when there is a duplicate key (say, 'create index unique on col1'). Try it now.

Nice, isn't it? Oracle has its own version of upsert, called merge (at least the name is better) but it itches a little bit when I write about Oracle, so go and check this page instead.

C++ Namespaces and g++

Have you ever tried to leave open a C++ namespace after EOF (that is, openning a namespace in a headerfile but forgetting to close it). It's a little bit like getting your balls caught by the door. The compiler will throw at you an incredible number of seemingly unrelated errors, all of which occur in a different file than the offending header.

Reaching EOF on a C++ file without closing all its namespaces should be ilegal; or at least you should have better error reporting, because right now it's almost impossible to know what's the source of the error (for g++, that is).

Oh my god

An old good Unix console joke goes like this:

% ar m God
ar: God does not exist

Obviously thats a very old and used joke, nowdays we're much more advanced than that:

$ ar m God
$ ar: creating God

Design Patterns: C++ Idiom RAII

Ohh design patterns. I love buzzwords. Who doesn't? To increase my buzzword count I will be writing about a topic most people programming C++ should already know: RAII, resource acquisition is initialization.

Patterns everywhere

Knowing that Gamma et al didn't list all the known patterns in the universe does come as a surprise to some, not sure why though. The twenty some patterns they write about in their now famous book are (arguably, perhaps) some of the most common design patterns, but the list hardly finishes there.

Some patterns only have meaning in a very specific context; a reactor is a nice pattern for handling asynchronous events yet most applications would never need it. Sometimes "the context" means a specific domain in which the application must work, like a web application, a real time application or a distributed application, sometimes the context is the language itself. RAII falls in this last domain, it only makes sense for C++ applications (actually there are others, but thinking what kind of languages would support this idiom is left as an exercise for the reader).

No, really. What is RAII?

If you made it past that long intro you are probably really interested in knowing what RAII is, and don't know how to search it in Wikipedia. OK, I'll explain it the best I can then: RAII means that a resource acquisition is the initialization.

Seriously. That is all the secret there is to RAII. Talking in code:

template
class RAII_Wrapper {
   T *resource;

   public:
      RAII_Wrapper (T *resource)
            : resource(resource)
      {
         resource->open();
      }

      ~RAII_Wrapper ()
      {
         resource->close();
      }
};

An example

Compare that to a visitor pattern. It's just too simple to be of any use, isn't it? Well, contrary to what Java fanboys tend to believe you can do lots of nice things without writing a bazillion lines of code.

int foo() {
	Expensive_Resource x;
	x.open();

	try {
		if (not bar()) {
			x.close();
			return -1;
		}
	} catch (...) {
		x.close();
		throw "up";
	}

	int ret;
	try {
		ret = baz();
	}catch(...) {
		// We don't care, we're closing x anyway
	}

	x.close();
	return ret;
}

Wow... a whole lot of code just for calling bar and baz. And as I wrote that without even compiling I'm sure there are too many hidden bugs, lots of code-paths my simple programmer's mind can't even begin to imagine which will cause my Expensive_Resource to be leaked!

Let's rewrite that using RAII:

void foo() {
	Expensive_Resource x;
	RAII_Wrapper release(&x);

	if (not bar()) return -1;
	return baz();
}

A lot nicer, isn't it? But, what happened to all the try/catch if's and closes there?

Where's the magic?

The magic of RAII lies in how C++ handles exceptions. When we have a built object (can an object be in an unbuilt state?) it means it's constructor has correctly ran. It also means it's destructor will run when it goes out of scope, doesn't mater HOW it goes out of scope.

See how brilant that is? Doesn't matter if a function we're calling throws, or if we need to return before reaching the end of the function: the destructor will be called and thus our Expensive_Resource will be free!

Why is this C++ specific?

This is an easy one: think how would you implement this in Java: right, you can't. Not knowing when is your object going to be destroyed means you can't do anything useful in its destructor, therefore RAII is deeply rooted within the memory management in C++ and it's pretty much a language specific pattern (or is it?). But, is that so good?

Not everything is so great...

You are probably thinking this is the best discovery since ice cream was invented. Well, not so fast, RAII has it's detractors too.

The first problem in RAII, it doesn't have a graceful way of handling resource acquisition failure. If Expensive_Resource is a database, and it's connection fails, we have a throwing constructor.

Even if throwing constructors are acceptable, throwing destructors may even be a worst idea: throwing while an exception is already active is a cause for concern (tip: it'll crash your application, doesn't matter how many try/catch blocks you use, due to stack unwinding issues).

And then, even if we don't care about throwing destructors you have the issue of a release failure: how do you notify the user that a release failure has occurred? And what do you do, should it happen?

So, RAII is a great idea indeed, and it has it's uses, but you should be careful when choosing this C++ specific pattern.

Fuuuuuuuuuuuuuu (Opera)

I hate ubuntu, but I hate windows the most. I hate firefox, but internet explorer makes me want to vomit. I don't like gnome, but kde is uglier. But I love Opera. Well, loved it, I guess version 10.60 will be my last version.

It's been a loyal application which I've been using since its 6.x version. Always fast, with all the functionality I needed (some more too) and none of the bloated BS needed to make FF be a usable (though ugly) browser. It had it's ussual screw-ups, everyone does, but after I updated to version 10.60 it has become unusable.

Its new features include random crashe, making gmail work really slow (or not at all: the fucking scrollbar won't work anymore, and keyboard shortcuts in google reader (j & k, next & prev) are foobar'd. Scrolling on a large webpage eats 100% cpu, the upgrade fucked up my nice dark theme (and changed it back to a hellish abomination which seems to be a time-traveller from 1998), and it has random stupid bugs. And I mean STUPID, like, double click a word and the popup menu won't go away.

Fuck. I always liked you Opera, but it seems it may be time to give chrome a chance.

Template metaprogramming XI: Hidden Agenda

Wow, number eleven already. We're getting more chapters here than Final Fantasy games. I didn't even imagine there was so much to write about such an esoteric language features like templates. I do wonder if anyone will actually read it, but that's a completely different problem.

Enough meta-meta talk: what can we do with all the things we have learned? We can calculate pi and e, we already showed that as an example on one of the first chapters. This chapter I'm going to write about what motivated me to explore the bizarre underworld of template metaprogramming. Some time ago I had to work with a Berkeley DB researching the feasibility of developing a magic cache for (real) DB table. Leaving aside the discussion of whether this is a good idea (the project did have a good reason to be researched) I hit a major roadblock when trying to provide a façade for every table; something like this:

See the problem? To do something like that we'd need a virtual template method, and you can't have that. After seeing that I thought to myself "Hey, I'll use templates!". Then I had two problems, but the damage was done, I couldn't go back. What kind of contorted device could we implement to make such a devious requirement work? I'll leave you to think it, the answers I came up with next week.

Thanks for flying vim

Have you ever used Vim through ssh and saw your xterm title changes to "Thanks for flying vim"? It happens a lot to me, and I usualy notice about an hour later. I'm not sure what's the use of this, I guess it's related to Vim airlines (no, really, check vim-avia.com), but it can be turned off:

When using vim in an xterm it renames the title of that window to "Thanks for flying vim" on exit. Q: How to turn off the message "Thanks for flying vim"? A: :set notitle

-- http://www.vmunix.com/vim/answ.html

The truth about SNMP

Seen @ http://wiki.wireshark.org/SNMP:

After years thinking and reading RFCs and various other documents, today, I finally understood. "Simple" refers to "Network" not to "Management Protocol"! So it is a Management Protocol for Simple Networks not a Simple Protocol for Management of Networks... That explains why it's called "Simple". It was that Simple but it took me years to understand it! -- LuisOntanon

Thank you Luis. That explains a lot.

Opera borks gmail

Ubuntu sucks, but less than windows. Gmail sucks, but less than hotmail. Opera rocks, but it tends to fuck up gmail every once in a while. After a lot of research and having found no help on the interweb I traced the problem to having a lot of tabs open for a lot of time (weeks, not hours).

In Firefox this shouldn't be a problem as having a FF browser open for a week should hog all the memory on its host computer, forcing you to reboot. In Opera, being a little bit better behaved browser, this may actually be a problem.

Luckly the fix is simple: open a Vim editor or take out pencil and paper, make a list of all your open tabs, close opera and using your favourite console type "rm -rf ~/.opera/sessions" (i.e. delete the sessions folder in your .opera dir). Restart Opera and restore your tabs from your backup list. Problem should be gone.

Elvis is alive!

Unix trivia day: in the olden days of the 90's there were a lot of Unix boxes out there named "elvis". Nowdays it's not uncommon to find one, either. Have you ever wondered why are there so many boxes called elvis?

This is related to Solaris' ping command. When you ping $HOST it prints "$HOST is alive" (if it's responding the pings), thus elvis is alive!