Posts for 2010 May

Template metaprogramming VII: The Enemy Within

Post by Nico Brailovsky @ 2010-05-27 | Permalink | Leave a comment

Remember where were we last time? We had this code to define a list:

struct NIL {
    typedef NIL Head;
    typedef NIL Tail;
};
template <typename H, typename T=NIL> struct Lst {
    typedef H Head;
    typedef T Tail;
};
template <int N> struct Int{ static const int result = N; };
typedef Lst< Int<1>, Lst< Int<2>, Lst< Int<3> > > > OneTwoThree;

Now, to increase our template-foo, let's practice some basic operations. The same operations you would implement to practice your skill any other functional language. If I remember correctly these where useful when learning Haskel: getting a list's lenght, getting the Nth element, appending and preppending elements... that sort of stuff.

Let's start with the most basic: getting the length of a list. We don't really have a for loop so using recursion is the only way. It gets easier if we think again on our definition of list: "think of a list as tuple, two elements, the first (called head) will be the first element of the list and the second element as another list or a NIL object". Whit this definition of a list, then it's length turns to be 1 (the head) + the length of the remaining list (the tail), with a special case for the length of a NIL object which should always be 0. In template-speak:

template <typename LST> struct Length {
    typedef typename LST::Tail Tail;
    static const unsigned int tail_length = Length< Tail >::result;
    static const unsigned int result = 1 + tail_length;
};
template <> struct Length <NIL> {
    static const unsigned int result = 0;
};

I know. You are thinking "wait, what?". Well, even for this basic case we need to use some esoteric language features:

Obviously, you can write it this way too:

template <typename LST> struct Length {
    static const unsigned int result = 1 + Length< typename LST::Tail >::result;
};
template <> struct Length  {
    static const unsigned int result = 0;
};

The rest of the "basic" list-operations are quite similar, but I'll leave that for another post.

Thank you Stéphane Michaut for pointing out typos and bugs in the code listings

Deleting > Writing

Post by Nico Brailovsky @ 2010-05-25 | Permalink | Leave a comment

Perfection is finally attained not when there is no longer anything to add but when there is no longer anything to take away, when a body has been stripped down to its nakedness.

Antoine de Saint-Exupery

Level up!

Post by Nico Brailovsky @ 2010-05-23 | Permalink | Leave a comment

Today it’s been 756864000 seconds of uptime since I was promoted from Release Candidate to V1.0. Hope none of you remember I made this same post 31536000 seconds ago.

Template metaprogramming VI: The Spider Webb

Post by Nico Brailovsky @ 2010-05-20 | Permalink | Leave a comment

We have been building our template meta-foo for five chapters now, and I think we are ready to move on to more advanced topics. We will be borrowing a lot more from functional languages from now on, so you may want to actually start practicing some template metaprogramming to keep advancing.

In our previous entries we worked with basic building blocks, making it quite easy to keep in mind the whole "program flow". Now it won't be so easy anymore, as we'll be using real metaprogramming (i.e. templates operating on templates) so a lot more thought will be needed for each program.

Another point to keep in mind, you don't have a debugger here. All the magic occurs at compile time so there is no gdb to step through your program to find a logic flaw. There's a little trick to check if you are too far off from the target but, mainly, you'll have to think for yourself.

Let's start with any functional programming course basics: lists. We have to think, first, how can a list make any sense when you only have types and no values. It means you can have a list like "int, char, void**, Foo", and not something like "1, 2, 3". Or, can you? There's a way to trick the compiler into creating a type from a integral value:

template <int N> struct Int {
    static const int value = N;
};

Voila! Now you can create a list of numbers. For our next trick, let's implement the list itself. No pointer magic, think of a functional definition of a list. Come on, I'll wait... ready? OK, a list is a tuple T of two values, in which the first element, called head, is the first element of the list and the second element, called tail, is either a list or the NULL element.

Quite a mouthful... let's go over that definition again:

// A list is a tuple T of two values
List: [ ..., ... ]
// in which the first element, called head, is the first element of the list
List: [ Head, ... ]
// and the second element, called tail,
List: [ Head, Tail]
// is either a list or the NULL element
List: [ Head, Tail]
Tail: List | Nil

So, as an example, a list of numbers could be expressed as:

    List( 1, List( 2, List( 3, NIL ) ) )

Closing up... how would you define this list in C++? Easy:

template <typename H, typename T> LST {
    typedef H Head;
    typedef T Tail;
};

We need here a NIL type to use as a list ending element. We could also use a default template type, so we won't have to write the last NIL to end a list definition. Thus we have now:

struct NIL {
    typedef NIL Head;
    typedef NIL Tail;
};
template <typename H, typename T> struct LST {
    typedef H Head;
    typedef T Tail;
};

Nice. You should remember the following rules:

  1. We can use template to define a template class, defining a new type based on a number instead of another type ;)
  2. We can't "store" a value in a type... unless we store it as a static value, that is.
  3. Using a convention for defining result holding variable names is very useful, as there are no interfaces and more than once we'll be using a result from an unknown class

With that said, let's translate the list (1, 2, 3) to Tmpl C++

template <int N> Int{ static const int result = N; };
typedef Lst< Int<1>, Lst< Int<2>, Lst< Int<3> > > > OneTwoThree;

Not so bad to start with. Next time we'll be doing something a little bit more useful with this list.

One last note, initializing a static const int in the definition of the class may be non portable (some compilers seem to have trouble with it). An enum may be used instead.

Dealing with Office on Linux

Post by Nico Brailovsky @ 2010-05-18 | Permalink | Leave a comment

Seen @ bash.org:

< adamkuj> are there any good open source tools for working with Access DB's (mdb files)? <@Dopey> rm Comment: #evilgeeks

True, so true... It's been said a thousand times, but I kinda like ranting... like it or not Office files are a majority out there. If you work with Linux, using it in a real enterprise environment, sooner or later you'll run into someone using a propietary Office format. You'll also run into someone who doesn't know that you need OOO to open those weird odf files. You may need to produce an adecuately formated document sometime, and LaTeX may not be an option.

Deal with it. Install a VM, or Wine, and a copy of MS Office. Resistance is futile.

Template metaprogramming V: Face to face

Post by Nico Brailovsky @ 2010-05-12 | Permalink | Leave a comment

By now we have learned the basics for a nice template metaprogramming toolkit:

Unfortunately that's all you need for a Turing complete language, meaning now we have the power, bwahahaha! Mph, I'm sorry, back on topic, it means we can now create a fully functional and useful template metaprogramming device... for approximating e, nonetheless. Oh, you think that's not useful? Well though luck, that's all you get for now:

template <int N, int D> struct Frak {
    static const long Num = N;
    static const long Den = D;
};
template <class X, int N> struct ScalarMultiplication {
    static const long Num = N * X::Num;
    static const long Den = N * X::Den;
    typedef Frak<Num, Den> result;
};
template < class X1, class Y1 > struct SameBase {
    typedef typename ScalarMultiplication< X1, Y1::Den >::result X;
    typedef typename ScalarMultiplication< Y1, X1::Den >::result Y;
};
template <int X, int Y> struct MCD {
    static const long result = MCD<Y, X % Y>::result;
};
template <int X> struct MCD<X, 0> {
    static const long result = X;
};
template <class F> struct Simpl {
    static const long mcd = MCD<F::Num, F::Den>::result;
    static const long new_num = F::Num / mcd;
    static const long new_den = F::Den / mcd;
    typedef Frak< new_num, new_den > result;
};
template < class F1, class F2 > struct Sum {
    typedef SameBase<F1, F2> B;
    static const long Num = B::X::Num + B::Y::Num;
    static const long Den = B::Y::Den; // == B::X::Den
    typedef typename Simpl< Frak<Num, Den> >::result result;
};
template <int N> struct Fact {
    static const long result = N * Fact<N-1>::result;
};
template <> struct Fact<0> {
    static const long result = 1;
};
template <int N> struct E {
    // e = S(1/n!) = 1/0! + 1/1! + 1/2! + ...
    static const long Den = Fact<N>::result;
    typedef Frak< 1, Den > term;
    typedef typename E<N-1>::result next_term;
    typedef typename Sum< term, next_term >::result result;
};
template <> struct E<0> {
    typedef Frak<1, 1> result;
};
int main() {
    cout << (1.0 * E<8>::result::Num /  E<8>::result::Den) << endl;
    return 0;
}

Looking nice, isn't it? You should have all what's needed to understand what's going on there. Even more, almost everything has been explained in previous articles, with the exception of EqBase. But that's left as an exersice for the reader because the writer is too lazy.

If you think any part of the code requires clarification ask in the comments. Next, a long overdue topic: lists using template metaprogramming. Guaranteed to blow your mind into little pieces!

Random WTFs

Post by Nico Brailovsky @ 2010-05-10 | Permalink | Leave a comment

Random WTF 1

Note: Use dapper instead of edgy to use Ubuntu Dapper

Thank you captian obvious.

Random WTF 2

I've been working with a big-co supplied ACS server, but it's IE only. WTF!? Aren't ACS all XMLy so they can work everywhere? I hate you all.

Template metaprogramming IV: Nightmares to come

Post by Nico Brailovsky @ 2010-05-06 | Permalink | Leave a comment

By now you should have noticed the warnings were not in vain: we are exploring a bizarre side of C++ here, a side many people prefer to, wisely, ignore. Luckily it probably is too late for you, there is no way back. Only a long spiraling way down into the arms of despair and cryptic compiler error messages... mwahahahaha. But now, let's see where we are.

In previous entries we learned how to return values, how to define recursive devices and how to provide a partial specialization. Let's see know how can we use partial specialization and complex return type definitions for some more fun template metaprogramming tricks. We had a fraction and a ScalarMultiplication operation for Frak:

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

Let's try to add an operation to simplify a Fraction. Simplify< Frak<2, 4> > should return 1/2. Mph... simplifying a fraction means dividing it by the MCD. A quick trip to Wikipedia reveals a nice recursive way to implement an MCD device:

template <int X, int Y>   struct MCD {
static const long result = MCD<Y, X % Y>::result;
};
template <int X> struct MCD<X, 0> {
static const long result = X;
};

I won't get into much detail as the link explains it a lot better than whatever I could try, but do take a look at the definition of MCD: that's a partial specialization. No magic there. Back to our simplifying device, we now have all the parts for it. Going back to it's definition we can see that simple(fraction) = fraction / mcd(fraction). Then:

template <class F> struct Simpl {
static const long mcd = MCD<F::Num, F::Den>::result;
static const long new_num = F::Num / mcd;
static const long new_den = F::Den / mcd;
typedef Frak< new_num, new_den > New_Frak;
typedef typename New_Frak::result result;
};

Quite a mouthful, but a lot simpler than what you think as there is a lot of unnecessary code there. Until new_num and new_den, no surprises. Typedeffing a Frak is not new, either. typedef typename is something new: typename tells the compiler you're referring to a name inside a template class, otherwise it'd try to refer to a static variable inside said class (*). Knowing what each thing does we can simplify it:

template <class F> struct Simpl {
static const long mcd = MCD<F::Num, F::Den>::result;
typedef typename Frak< F::Num / mcd, F::Den / mcd >::result New_Frak;
};

It is a matter of style really. In this case I'd rather use the second one because it matches better its colloquial definition, but if you think the first one is more readable go with it... it doesn't really matter though, no one will ever even try to read this kind of code if you intend to use it in a real application.

Next time: a "useful" (**) and complete template metaprogramming device, using the complete toolset we've been learning in this crazy templating series.

(*) Think of it this way:

struct Foo {
   typedef int Bar;
   Bar bar;
};

In a template you don't know if Bar is a typename or varname because there's no access to the specific template definition. As a rule of thumb, if the compiler complains then add typenames.

(**) Results may vary according to your definition of useful.

Ubuntu: Sound still FUBAR'd

Post by Nico Brailovsky @ 2010-05-04 | Permalink | Leave a comment

Remember my problems with dual screen support in Ubuntu? Well, I still love bashing Ubuntu, and the sound system in Linux is certainly a topic to rant a lot. Making the sound work fine in Ubuntu is an odyssey in pain and frustration, unless it works fine out of the box. And even if it does, it may still have it's kirks. Lots of them.

In my case the sound starts in mute. I know it's a problem with pulse (which is a WTF in itself) and alsa, I don't really care what's the problem though, I just want to play my mp3s collection without having to carefully turn the knobs up to eleven in alsamixer.

After trying a lot of the "solutions" found on the internets I've decided the best thing to do, short of switching back to windows me, is adding the following to my "fix_ubuntu_fuckups.sh" start script, which already contains my dual-screen pseudofix:

amixer -c0 -- sset Master playback -0dB unmute
amixer -c0 -- sset Headphone playback 0dB unmute
amixer -c0 -- sset Front playback 0dB unmute
amixer -c0 -- sset PCM playback -16dB unmute

This sets alsamixer to normal volume levels. As for the real fix, I'll wait till the next Ubuntu version. I wonder which sound subsystem will they chose next time.

I'm a pirate!

Post by Nico Brailovsky @ 2010-05-02 | Permalink | Leave a comment

Original: ./blog_img/img_lost.png

-- src