Thursday, July 31, 2008

Enjoy Everything You Do

Live the life of a dolphin,
Travel the world without fear,
Whether to the top of a mountain,
Or where the water ain't clear.

Fear not to push the ceiling,
Try to reach for the sky,
Go with the flow if you want to,
Or be left high and dry.

Speak your words with feeling,
Enjoy everything you do.
Play from dawn to the evening,
Is that not everything you do?

Follow the world in its footsteps,
Or make the world follow you.
Do everything with feeling.
Enjoy everything you do.

Bird of Fire

Fly, Fly, Fly little bird in the sky.
You own the heavens - the Earth and the Sky.
Lie, Lie, Lie, asleep in the clouds,
Free from cares, from worldly bounds.
You creature of mirth, of joy abound.

Live, Live, Live, a life full of dreams,
Unchecked by dearth of form or means.
Pray, Pray, Pray for a life full of song,
For finding a rhythm to play along.
You creature of milk, to heavens belong.

Say, Say, Say, the words in your heart,
Bring a smile with a kind remark.
Day, day, day a day in your life,
Opens a door from formless night.
You warrior of words, of shape and light.

Inspired by - To a Skylark by P. B. Shelly

Monday, July 21, 2008

Wordle and SEO


An image is worth a thousand words. This image is a tag cloud
generated by Wordle from the text at
http://www.drkapoorsclinic.com . I don't need to tell you
how such a map is helpful for SEO - do I?

And yes: despite my earlier post on Mac v/s Vista - that *is* a screenshot taken from my laptop running Vista. You might call me a hypocrite, I just call myself a pragmatist - if you can't beat 'em, join 'em. ;-)

Friday, July 18, 2008

Walking through your first template metaprogram in C++

From the Wikipedia article on Metaprogramming:
Metaprogramming is the writing of computer programs that write or manipulate other programs (or themselves) as their data, or that do part of the work at compile time that is otherwise done at run time. In many cases, this allows programmers to get more done in the same amount of time as they would take to write all the code manually.
Unfortunately, metaprogramming is not directly supported by C++ and resources on template metaprogramming are few and far between. I'll try to document my knowledge of metaprogramming as I learn it and hope that it proves useful for one such as myself hunting the web for information.

First, lets get the preliminaries out of the way:
  1. Templates are used to create generic code (but you already know that, don't you?)
    Code like:
    template<typename T> std::string to_string(T const & object) {
    return object.to_string();
    }
    is used to allow the to_string function to be called on all objects that have a to_string() member function.
  2. Template specializations are created to handle certain datatypes in a special manner (or in technospeak - to provide a custom instantiation of generic code)
    So, code like:
    template<> std::string to_string<int>(int I) { std::ostringstream o; o << I; return o.str(); } ensures that calls to to_string that take an int for a parameter will use the second definition of to_string and not the more generic first definition. This allows us to provide a string representation of an int even though it does not have a member function named to_string. Thus, the body of a templated piece of code can be changed completely from its generic counterpart in a template specialization.
  3. The compiler always chooses the most specialized definition of a function. This is somewhat akin to function overloading. So, given a choice between to_string<t> and to_string<int>, it will always choose to_string<int> for an integer parameter.
Well, how does all this help?
It allows us to do a compile time recursion and that's what I'm going to show you.

Look at this piece of code:
template<int N>
struct factorial {
static const long value = N*factorial<N-1>::value;
};

Doesn't that look dandy! Its that same old factorial function again! So, what's new? Firstly, notice that instead of templating the structure via a typename, we have chosen to template it over a compile time constant. So, creating an object of this structure will require code such as:
factorial<5> five_factorial;
But why would you want an empty object? Remember: static structure and class variables do not occupy any space in objects and factorial<N> has only static members. So, what's the use of the static member?
The static member allows us to directly access values that are calculated at compile time. In essence, you can think of it as the return value of the computation. Before we move further into the analysis, let me answer a couple of questions that can arise:
  • Where's the computation taking place?
    • It is taking place at compile time when the template is initialized/instantiated and its being done by the compiler while the templated code is being compiled. Effectively, the compiling process is the runtime for template metaprogramming.
  • Where's the recursion in the code?
    • The instantiation of factorial<N> requires the value of factorial<n-1>::value which is of-course a static member in factorial<N-1>. So, this template is also instatiated and the recursion takes place.

Sharp programmers might have noticed that there is no base case in this piece of code: You're right!
So, here's the base case:
template<>
struct factorial<0> {
static const long value = 1;
};

So, when the compiler tries to instantiate factorial<1> and comes across factorial<0>::value, it will choose this base case and terminate the recursion. Once all the constants have been determined, they are multiplied by the compiler and the result is stored in the resulting executable. So, the value of 5! can be used at runtime without any computation of any sort, all it requires of you is to substitute factorial<5>::value wherever you need it.

A side-effect of this evaluation is that all lower factorial structures are also instantiated. Thus, when you instantiate factorial<5>, you get for free the values of factorial<4>, factorial<3> etc. Also, use of factorial<4> later in the program will not cause additional template instantiations because C++ compilers follow a single template instantiation rule: viz. no template will be instantiated more than once. This allows for a very important optimization: memoization that's right memoization and not memorization (though the two are pretty similar). You can have a look at the Wikipedia entry on memoization for info, but for the impatient, it allows you to code a fibonacci number generator like this:

template<int N>
struct fibonacci_term {
static const int value = fibonacci_term<n-1>::value + fibonacci_term<n-2>::value;
};
template<>
struct fibonacci_term<1> {
static const int value = 1;
};
template<>
struct fibonacci_term<0> {
static const int value = 0;
};

If you had coded an analogous recursive function for evaluation at runtime, you should have been spanked by your computer science/engineering professors because that's the worst way to evaluate the fibonacci series as it has a time complexity of O(2^n) which is exponential in the size of the problem. However, because of the one template instantiation rule, its perfectly alright to do this at compile time. While evaluating fibonacci_term::value , the compiler has already instantiated fibonacci_term and that instantiation is simply looked up from a table, thus saving computation time and making the compile time program linear in time and space complexity.

Meta-programming is not just about compile time computations and tricks like this. Its far greater application lies in the capability of manipulation of the C++ type system. Most metaprogramming techniques are applied to make libraries hide their implementations better and allow you to write simpler, cleaner code without reams of types in angle brackets.

Type manipulation tricks are best left to another blog entry. For now, you can check out:
[1] C++ Template Metaprogramming - Concepts, Tools and Techniques from Boost and beyond
This is a book by the authors of the Boost.MPL (the Boost Meta-Programming Library). The MPL has loads of tools to make metaprogramming easier as well as hacks to work around the deficiencies in various C++ compilers.
[2] The Boost TypeTraits library - This library makes type manipulation a breeze, thanks to the consistent interface and excellent documentation.

Hope you liked it. Comments always welcome.

The files for the examples are listed below. All of them have been compiled and tested using the Visual C++ 2005 compiler and should work with most other compilers. In case you have troubles, let me know.
[1] factorial.cpp
[2] fibonacci.cpp

The commplete source code including makefiles can be found here. A Jamfile is included for those who use Bjam.

Monday, July 14, 2008

I'm Back

Hey all,
Its been ages since I last posted on this blog and its been rather sometime since this blog had been taken off the internet. However, I'm back on the internet after being *really* busy at college and the blog is back online.
Well, in the time my blog was offline, I was completing my second year at college and in the summer vacations was developing a website for my dad and mom's Ultrasound clinic. You can see the final result at their home page: http://www.drkapoorsclinic.com .