Friday, March 18, 2011

dumb_ptr, a smart_ptr conversion class in C++ (only for programmers)

Everyone reading this who is not a programmer, 
STOP READING NOW!!
Seriously this post will make no sense to you, do something you will enjoy like going swimming. For those who are programmers this may interest you.

I have been using a lot of different boost smart pointers lately, as well as normal pointers. I have noticed that as you develop you tend to realise that you have to switch pointer types and memory management mechanism because you overlooks some circular dependency or some othe small annoying thing. When this happens and you change your pointer type you have to either go and change a whole bunch of you method signatures to take the new pointer type, or at each call site you have to convert between pointer types. You also have a problem if you have the same function but want it to take multiple pointer types.

I was wondering if there already existed a generic way to deal with this, i.e. write methods that are agnostic of the pointer type you pass to it?
The obvious answer is write all your simple methods (methods that don't manipulate ownership of the pointer and don't return it to anything) to take raw pointers (T*) or references (T&) as parameters. But this still means that you have to write code at each call site to extract the raw pointer, and if you change the type of smart pointers you are using then you have to change code at every call site. That's a hassle, I like to avoid hassles.

You could also overload your methods for different pointer types, but thats a huge waste of time and makes the more code difficult to read. Another way is to use a template style solution with some type inference, but this would cause some significant bloat in the compiled code and is likely to start throwing strange unsolvable template errors.

My idea was to write a new class any_ptr<T> with conversion constructors from all the major pointer types, say, T*, shared_ptr<T>, auto_ptr<T>, scoped_ptr<T>  and weak_ptr<T>and then have it expose the * and -> operators. In this way it could be used in any function that does not return the pointer outside of the function and could be called with any combination of common pointer types.

The class ended up being really simple, here it is:

template<typename T>
class dumb_ptr {
 public:
  dumb_ptr(const dumb_ptr<T> & dm_ptr) : raw_ptr(dm_ptr.raw_ptr) { }  
  dumb_ptr(T* raw_ptr) : raw_ptr(raw_ptr) { }  
  dumb_ptr(const boost::shared_ptr<T> & sh_ptr) : raw_ptr(sh_ptr.get()) { }  
  dumb_ptr(const boost::weak_ptr<T> & wk_ptr) : raw_ptr(wk_ptr.lock().get()) { }  
  dumb_ptr(const boost::scoped_ptr<T> & sc_ptr) : raw_ptr(sc_ptr.get()) { }  
  dumb_ptr(const std::auto_ptr<T> & au_ptr) : raw_ptr(au_ptr.get()) { }  
  T& operator*() { return *raw_ptr; }
  T * operator->() { return raw_ptr; }
  operator T*() { return raw_ptr; }
 private:
  dumb_ptr() { } 
  dumb_ptr<T> operator=(const dumb_ptr<T> & x) { }
  T* raw_ptr;
};

It can convert from the common smart pointers automatically and can be treated as a raw T* pointer, further it can be converted automatically to a T*. The default constructor and the assignment operator (=) have been hidden to deter people from using it for anything other than function arguments. When used as a function argument the following can be done.

void some_fn(dumb_ptr<A> ptr) {
  B = ptr->b;
  A a = *ptr;
  A* raw = ptr;
  ptr==raw;
  ptr+1;
}

Which is pretty much everything you would want to do with a pointer. It has the exact same semantics as a raw pointer T*. But now it can be used with any smart pointer as the parameter without having to repeat the conversion code (.get,.lock) at each call site. Also if you change your smart pointers you don't have to go around fixing each call site.

So I think this is a pretty neat solution. The idea and most of the content for this post come from a Stackoverflow question I asked, where I presented this idea and asked if anyone saw any major problems with it. The answering parties didn't think much of it, but I think they missed the point (No offence intended) . The point is that it should be less of a hassle to program, even in languages like C++.

Well that's it, I hope someone finds it useful

Sunday, March 13, 2011

Counting your way out of hell

Today I have some riddles and games for you. The game is called counting your way out of hell and involves a simple a little story. You have died and been banished to hell for the many transgressions you have committed during your life (such as this or this). In any case Satan (played by Tom Waits) offers you a way out. He proposes a challenge (said in a classic Waitsian drawl):

I'm gonna think of a number, it's gonna be positive whole number like 1,2,3 or 57823. It can be as big as I want. Now you have to guess what it is, but you have as many guesses as you want.
So you think to yourself, this is a pretty sweet deal. Since you have been damned for all eternity you have time for quite a few guesses. So how do you do it?

So this is an easy one. I'm sure you've figured it out. So you start at 1, and the 2, 3, 4 and so on. And you know that eventually you are gonna get there. It may take a long time but eventually you'll get there, and you do. The Devil is marginally impressed and stroking his pointy beard proposes a slightly more difficult challenge:

So now I'm gonna think of another number, this time it can be positive or negative. Same rules, you get as many guess as you want.
This one's a bit more difficult. If you try your original strategy and Old Nick guesses a negative number you are never gonna get there. But with just a simple modification you figure it out. If you follow every positive guess with a negative one then you get there, something like 1,-1,2,-2,3,-3 and so on. Once again whatever the number is you are guaranteed to eventually guess it.

Satan grins, knowing that he has just been warming you up. He gives his final challenge:

This time I'm going to think of a fraction. It can be any positive fraction, proper or improper (i.e. 14 or 73). You get as many guesses as you want. If you guess the right number then you get go to back to your life.
Now this one is tricky, and it takes a bit of thought. Think about it for a few minutes.

There are a couple of (wrong) ways you could try this. You could try every simple fraction with a numerator of 1, something like 11, 12, 13, 14 and so on. But then if the Devil guesses 23 you are never gonna guess it and you'll be spending all of eternity in the fiery abyss. Similarly if you pick any other single Numerator (the top number in a fraction) or Denominator (the bottom number in a fraction) and try all of possibilities. However, there is a way.

Imagine the fractions on a grid, with the one axis being all the denominators and the other being all the numerators, such as the one shown below. Then all you have to do is count them off on each diagonal starting at the top left corner. Below is a little animation of this system for numerators and denominators between 1 and 9. Click the "Go!" Button to start it.

Denominators
N
u
m
e
r
a
t
o
r
s

It should be clear that if you continued this pattern for long enough you would eventually reach any fraction. Realising this you eventually guess the correct fraction (and really no matter how long it takes you it's a lot shorter than eternity). Reluctantly the Devil has to let you go, strangely the Devil seems bound by verbal contracts just like everyone else. And that's how you count your way out of hell.

Mathematically this is all possible because Natural Numbers, Integers and Rational Numbers(Fractions) are all Countable. What this essentially means is that you can create a system (a bijection technically) that can assign a Natural Number (1,2,3,etc.) to each and every Integer and Rational Number. With Integers it was pretty obvious how to do it but with the Rational Numbers the system explained above is called a Cantor Pairing, after the Mathematician Georg Cantor.

Countability is an important concept when we want to talk about the size of infinitely large sets. There are an infinite amount of Natural Numbers and Real Numbers, but in some sense we feel that there should be "more" Real Numbers than Natural Numbers. To define this idea we use the idea of countability. In some sense we say that the infinite amount of Natural Numbers is the same as the infinite amount of Integers and is also the same as the infinite amount of Rational Numbers - they are all countable. However, we can prove that the Real Numbers are not countable (which I will not show here, but has a simple elegant proof you can look up here), they are uncountable and strictly larger than than a countable set. The fact that Rational Numbers are countable is surprising since in between 0 and 1 there are infinitely many Rational Numbers, yet despite that we consider the set of all Natural Numbers and the set of all Rational Numbers to be the same size.

Cantor's pairing function can be seen as a way of encoding two numbers into one number, which you can see if you consider a fraction ab to just be a pair of numbers (a,b). The function can easily be extended to encode any amount of numbers, for example (a,b,c). It can even be used to encode tuples where you don't know the length by first encoding the length of the tuple and then encoding the the tuple in a single number and then taking the cantor pairing of those. The consequence of this is that a surprisingly large amount of sets turn out to be countable. For example:

  • Rational Numbers
  • Polynomials
  • Algebraic numbers
  • All polygons with integers length sides (I'm guessing on this but it seems obvious)
  • All Computer programs
Because we can number all these things we can use them much more easily in proofs, and we sometimes make very surprising relations between one and the other.

Monday, February 28, 2011

Thought Factory - A friend's new blog

A friend of mine, Camaren, has started a blog, Thought Factory, that those interested in
"Thoughts on the new millenium; people, politics,economics, environment and technology. What kind of world do we live in and where is it leading to?"
should check out. The posts a well thought out and offer more analysis than the usual blogger fair of just splurging out whatever you have seen on the news. The latest posts have followed the middle east obviously and offer a good review of whats been happening as well as contextualizing some of the events more broadly.

Post-Oedipul remembrance

Today I was reminded by the Daily Maverick how swift we are to re-imagine our past to appease our consciences. Talking about Libya in this case they point that its about as hard to find a person that supported the Gaddafi regime as it is to find a person that voted for the National Party government during apartheid. The great re-visioning of personal histories that acts as the precursor to greater rewriting of the past has begun in earnest all through the middle east. We've seen this many times before, an obvious example being the claims of ignorance of the Nazi population with regard to the holocaust. Soon it will true that everyone was secretly working against Gaddafi, and those that supported him were only doing so out of fear. Perhaps this reinvention of the past is a requirement to move on, a type of survivalist double-think that we need to live with what many people should feel as overwhelming guilt. This sort of thinking is no stranger to South Africa.

I have no desire to see anger fester, and I hope that their will be a swift reconciliation of the middle east with out to many Salem style witch hunts. But still the inevitable and willful destruction of the truth bothers me. I am reminded of a great line from The unbearable lightness of being (actually i stole this line form the movie, but i am sure its the same). It is not exactly relevant but touches on somethign I am feeling. It is the protagonist Tomas talking about the former Czech leaders:
"I've been thinking about Oedipus. Good King Oedipus. When Oedipus realized that he had killed his father- unknowingly, unknowingly killed his father - and was sleeping with his mother and that because of his crime plagues were ravaging his city, he couldn't bear the sight of what he'd done.He plucked out his own eyes and left.He did not feel innocent.He felt he had to punish himself.
But our leaders, unlike Oedipus, they felt they were innocent. And when the atrocities of the Stalinist period became known,they cried,"We didn't know! We weren't aware of what was going on. Our conscience is clear". 
But the important difference is they stayed in power. And they should have plucked their eyes out. All I'm saying is that morality has changed since Oedipus." 

Tuesday, February 15, 2011

The Barnsley fern

So I am getting into my masters again. Which means I have lots of time to distract myself with pointless side projects. Hence we are delving again into the wonderful world of fractals. This time the fractals is called the Barnsley Fern. It's also a very famous fractal (as far as fractals can be famous. I don't think its famous like Tom Cruise. But how could a lowly mathematical object compete with the crown prince of Scientology).

The fractal, unsurprisingly, looks like a fern plant, or rather a leaf of a fern. Like many fractals it is made up of smaller versions of itself that have been scaled and rotated. It is also an infinitely complex object. If you had the computational power then in theory you could zoom into any part of it and find infinitely many copies of itself.

So here it is. It is set to keep drawing in more detail. To start it from scratch again click the redraw button.

This fractal was discovered by Michael Barnsley who was really into fractals. It is an example of a Iterated Function System(IFS). The interesting thing about it (which you can see in the animation) is that it is drawn one point at a time, and that how this point moves around is randomly chosen. But never the less it always draws the same picture. The Wikipedia article has a reasonably detailed explanation of how it is constructed (which really is simple). Check it out if you are interested.

Saturday, December 18, 2010

Mumbai rising

Mumbai is massive. That's really the best way to describe it. Its spans endlessly in seemingly all directions. Getting your bearings seems impossible. The scale of the place compounded with the traffic mean that getting from one side of town to the other can easily take 2 or 3 hours. And the traffic, it almost defies description. I know that the traffic in India is renowned, but it really lives up to its reputation. A South African driving here would break down crying in about the first city block, thank fully I had a driver (thank you Paramin) and so had the luxury of being a fairly passive observer. The roads are a constant melee. It does not matter the time of day or night, there is a gridlock. Trucks and Buses vie for position with auto-rickshaws and scooters. The auto-rickshaws flock down the roads like huge beetles, they are really something to see.

What appeared to me at first to be complete chaos I later realised was the only workable system for traffic of this nature. The rule seems to be, take any opportunity you have (no matter how slight), but be constantly conscious that everyone else is trying to do the same. Thus if some one else has gotten there first you give up and let them through, its kind of like having right of way being set as whoever has there nose in front first. The maneuvers are death defying. Three lane roads can easily have five lanes of vehicles on them, all of different and varying size. To make a three point turn in the middle of this traffic is a completely valid maneuver. If construction barriers are too close to your car its fine to stick your hand out and push them away. But its strangely nonthreatening, perhaps I don't so easily, but the system just seems to flow. This stop start bump and bash seems to have a logic and life of its own.

The motorbikes are incredible. Families of three (or even four) jet down the road, all on a little Hero Honda 125cc. They weave through traffic with a reckless abandon, deftly avoiding certain collisions with buses and cars. The roads are full of pretty young women straddling the back of a bike holding onto their boyfriends or husbands in front, and older women behind there husbands. These women sit side saddle because they are wearing Saree's, and modesty (I think) stops them from holding onto the rider in front, so instead they just hold onto the seat they are on. No matter how sharp the turn or sudden a maneuver they never seem to to be anything but perfectly upright on the bike. It is like there is some invisible gravity that makes sure they just float along in perfect unison with the bike beneath then. It is an almost eerie sight.

The skyline is impressive. In all directions there are towering constructions of new residential towers or massive office blocks, all 50+ stories high. From my previous apartments (I am now in New Delhi) window I could see 10 of these huge towers within a few blocks, some are still being built but none of them are more than 3 years old. It is as if the city can no longer grow out (since it is on a peninsula) and the continual massive growth of the Indian economy is driving it up out of the ground.

The most striking thing about Mumbai though is the is the tangible sense of ambition. It electrifies the air, along with the scramble to survive. All the young men walk around in collared shirts, good pants and (ironically) leather shoes. They look like fields or accountants (though most of them I think work in call centers). It is so important to them to look successful and to constantly work to improve their position in life. Where western advertisers try to sell the idea of "cool", here they try to sell the idea of "success". You can see it on TV, on billboards and in the shops. The driving ambition permeates everything. Perhaps this is what America used to feel like when everyone started striving towards the American dream? In any case it is a monumentally powerful force, with a huge, young, educated workforce this ambitious it is no wonder that India grows year on year. It is an almost humbling realisation.

I wonder what Mumbai will look like in 20 years? it has the potential to become a beautiful city, right now the private spaces are exquisitely maintained but almost all the public spaces a dirty and broken. The obvious wealth of the city juxtaposed against the dirt and poverty is not strange for a person coming from South Africa, but is far more immediate a contrast. But perhaps the rising wealth will uplift the public areas, clean the streets, repaint the disastrously dirty old walls of old apartments (which are very nice inside). Right now Mumbai needs a bit of photo-shopping, but its electric will to succeed is irrepressible. This cannot but be one of the cities of the future.