Blog

I added tags support for my blog posts via using the Django tagging library. As you can see each blog post now has any number of tags associated with them.

Overall Django tagging works a lot like Django comments in that you can attach tags to any model in your project.

To implement Django tagging inside my site, I did need to make a slight model change to have a tags field in my blog news item table. Apparently this field is only used for caching and so that it shows up in the Django administration. When you modify your model in Django administration a new text field appears labeled Tags that you can enter in space separated tags for your model.

I made each tag into a link which bring you to all posts on the site about the specified tag. Also you can find a Tags link on the right hand bar which displays the list of tags in use and how many posts each tag has.

The Django tagging framework has many other features which I didn't use, but from what I used it's a great and very easy to use library.

I've implemented comments on this site for all blog posts. I've been wanting to add comments for a long time, especially in case I have errors in any of my postings.

I decided to build off of Django's built in comment framework django.contrib.comments. I was very impressed on how easy it is to integrate and customize. The Django comment framework allows you to attach comments to any model you have. So I didn't need to do any additional database work.

I'm going to attempt to hold off on CAPTCHA for the moment to see how their honeypot feature works. But I expect that I'll have to implement a CAPTCHA system eventually. Basically the honeypot feature is an extra field in the form that's used as a trap. If any data is entered in that field, the comment will be considered spam. Spam robots will typically fill out all fields when attempting to make a form submission.

The sliding and collapsing effects are basically done with a single line of jQuery code.

$("#id-of-div").slideToggle();

You can also optionally pass in a duration or 'fast' and 'slow' keywords to the slideToggle function. Some other cool cross browser things you can do with jQuery are: adding animated effects, Making XML HTTP (AJAX) requests, DOM navigation, DOM manipulation, drag and drop, complex client side operations, and validation.

July 1st 2010 I was happy to receive an email from Microsoft notifying me that I won one of the Microsoft Most Valuable Professional awards. Specifically I was awarded for Visual C++.

From the award website:

The Microsoft MVP Award recognizes exceptional technical community leaders from around the world who voluntarily share their high quality, real world expertise with others. Microsoft MVPs are a highly select group of experts representing technology's best and brightest who share a deep commitment to community and a willingness to help others. Worldwide, there are over 100 million participants in technical communities; of these participants, there are fewer than 4,000 active Microsoft MVPs.

The award is well known and recognized in the tech industry and I'm very honored to have received it.

The award comes with many perks but the recognition and other MVP contacts that you make are invaluable.

It seems that the primary reasons for winning the award was for contributions to stackoverflow (Q&A site for programmers), my blog website, MSDN related forums, and codeproject (Q&A)

In 2003 I purchased a book by O'Reilly on Scalable Vector Graphics (SVG). It was a great book and I had high hopes for what I was learning, but it remains one of the only things I've learnt that I have not had the opportunity to use in a professional setting.

SVG has long been deserving widespread adoption on the web, but the one browser that really matters has not had support for it. Sure you could install 3rd party plug-ins, but native support is needed for widespread adoption. That one browser without support has been Internet Explorer 8 and below.

That is up until now. The MIX 10 conference was held from March 15-17, 2010 and the Internet Explorer team announced that they have support for SVG in version 9. Looks like they're about 10 years late, but better late than never.

Some milestones:

• SVG was initially released late 2001
• Firefox and Camino have had support since 2005.
  
• WebKit which Opera and Safari are based on has had support since 2006.
• Microsoft relases .Net framework 3.0 which has support for XAML

Does SVG pose a thread to Silverlight/XAML?

In 2006 Microsoft would probably of said yes. Today they would say no. I would also say no.

Silverlight and its XAML markup provide a full application description format.

SVG is more of a graphic file format and offers minimal programming support via a script tag typically using Javascript.

That being said, when possible I would prefer to use SVG.

This post will use Fibonacci numbers as a tool to build up to explaining the usefulness of Python generators.

This post will feature both C++ and Python code.

Fibonacci numbers are defined as the sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ....

Or in general:

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2

This can be transferred into a C++ function extremely easily:

size_t Fib(size_t n)
{ 
    //Fib(0) = 0
    if(n == 0)
        return 0;

    //Fib(1) = 1
    if(n == 1)
        return 1;

    //Fib(N) = Fib(N-2) + Fib(N-1)
    return Fib(n-2) + Fib(n-1);
}

But if you want to print the first 6 Fibonacci numbers, you will be recalculating a lot of the values with the above function.

For example: Fib(3) = Fib(2) + Fib(1), but Fib(2) also recalculates Fib(1). The higher the value you want to calculate, the worse off you will be.

So one may be tempted to re-write the above by keeping track of the state in main.

//Not supported for the first 2 elements of Fib
size_t GetNextFib(size_t &pp, size_t &p)
{
    int result = pp + p;
    pp = p;
    p = result;
    return result;
}

int main(int argc, char *argv[])
{
    size_t pp = 0;
    size_t p = 1;
    std::cout << "0 " << "1 ";
    for(size_t i = 0; i <= 4; ++i)
    {
        size_t fibI = GetNextFib(pp, p);            
        std::cout << fibI << " ";
    }   
return 0;
}

But this is very ugly, and it complicates our logic in main, it would be better to not have to worry about state in our main function.

We could return a vector of values and use an iterator to iterate over that set of values, but this requires a lot of memory all at once for a large number of return values.

So back to our old approach, what happens if we wanted to do something else besides print the numbers? We'd have to copy and paste the whole block of code in main and change the output statements to whatever else we wanted to do. And if you copy and paste code, then you should be shot. You don't want to get shot do you?

To solve these problems, and to avoid getting shot, we may re-write this block of code using a callback function. Every time a new Fibonacci number is encountered, we would call the callback function.

void GetFibNumbers(size_t max, void(*FoundNewFibCallback)(size_t))
{    
    if(max-- == 0) return;        
    FoundNewFibCallback(0);        
    if(max-- == 0) return;
    FoundNewFibCallback(1);

    size_t pp = 0;
    size_t p = 1;
    for(;;)
    {
        if(max-- == 0) return;
        int result = pp + p;
        pp = p;
        p = result;
        FoundNewFibCallback(result);
    }
}

void foundNewFib(size_t fibI)
{
    std::cout << fibI << " ";
}

int main(int argc, char *argv[])
{
    GetFibNumbers(6, foundNewFib);  
    return 0;
}

This is clearly an improvement, your logic in main is not as cluttered, and you can do anything you want with the Fibonacci numbers, simply define new callbacks.

But this is still not perfect. What if you wanted to only get the first 2 Fibonacci numbers, and then do something, then get some more, then do something else.

Well we could go on like we have been, and we could start adding state again into main, allowing GetFibNumbers to start from an arbitrary point. But this will further bloat our code, and it already looks too big for a simple task like printing Fibonacci numbers.

We could implement a producer and consumer model via a couple threads. But this complicates the code even more.

Instead let's talk about generators.

Python has a very nice language feature that solves problems like these called generators.

A generator allows you to execute a function, stop at an arbitrary point, and then continue again where you left off. Each time returning a value.

Consider the following code that uses a generator:

def fib():
    pp, p = 0, 1  
    while 1:
        yield pp
        pp, p = p, pp+p

g = fib()
for i in range(6):
    g.next()

Which gives us the results:

0
1
1
2
3
5

The yield statement is used in conjuction with Python generators. It saves the state of the function and returns the yeilded value. The next time you call the next() function on the generator, it will continue where the yield left off.

This is by far more clean than the callback function code. We have cleaner code, smaller code, and not to mention much more functional code (Python allows arbitrarily large integers).

Forward declaring things in C++ is very useful because it dramatically speeds up compilation time. You can forward declare several things in C++ including: struct, class, function, etc...

But can you forward declare an enum in C++?

No you can't.

But why not allow it? If it were allowed you could define your enum type in your header file, and your enum values in your source file. Sounds like it should be allowed right?

Wrong.

In C++ there is no default type for enum like there is in C# (int). In C++ your enum type will be determined by the compiler to be any type that will fit the range of values you have for your enum.

What does that mean?

It means that your enum's underlying type cannot be fully determined until you have all of the values of the enum defined. Which mans you cannot separate the declaration and definition of your enum. And therefore you cannot forward declare an enum in C++.

The ISO C++ standard S7.2.5:

The underlying type of an enumeration is an integral type that can represent all the enumerator values defined in the enumeration. It is implementation-defined which integral type is used as the underlying type for an enumeration except that the underlying type shall not be larger than int unless the value of an enumerator cannot fit in an int or unsigned int. If the enumerator-list is empty, the underlying type is as if the enumeration had a single enumerator with value 0. The value of sizeof() applied to an enumeration type, an object of enumeration type, or an enumerator, is the value of sizeof() applied to the underlying type.

You can determine the size of an enumerated type in C++ by using the sizeof operator. The size of the enumerated type is the size of its underlying type. In this way you can guess which type your compiler is using for your enum.

What if you specify the type of your enum explicitly like this:

enum Color : char { Red=0, Green=1, Blue=2};
assert(sizeof Color == 1);

Can you then forward declare your enum?

No. But why not?

Specifying the type of an enum is not actually part of the current C++ standard. It is a VC++ extension. It will be part of C++0x though.

What are abstract functions?

Abstract functions, are functions who's implementation is not yet specified.

They are useful because:

• They allow you to define an interface without defining an implementation.
  
• A base class may not have a specific default definition for a function, but you know that derived types will.

In C++ both interfaces, and abstract classes are done via pure virtual functions. Pure virtual functions simply say that derived types must override the function. The base type can have a default implementation (that the derived types can use by calling the base function directly) but the base functions typically have no implementation at all.

In C# there are different constructs for interfaces (interface) and undefined base functions (abstract).

This post discusses what pure virtual function call errors are, and how they work across the following languages: C++, C#, and Python.

What is a pure virtual function call error?

Pure virtual function call errors could potentially happen, in a programming language that allows you to create partially implemented classes. Although not all programming languages can have pure virtual function call errors.

Pure virtual function call errors occur when a call is made to a pure virtual function. Since an abstract base type cannot be created in most languages, they will typically occur before a derived type is fully created, or after a derived type is already destroyed. The call is therefore usually called from the base type. Pure virtual function call errors could potentially also occur when using a pointer to call a function of an already deleted object.

Can C++ have pure virtual function errors?

Yes.

Consider the order of construction for the following C++ code:

class Animal
{
public:
  virtual ~Animal() {}
  virtual void Speak() = 0;
  Animal() {}
};

class Dog : public Animal
{
public: 
  virtual void Speak() { }
};

//.... 
Dog leia;

When you create an instance of Dog the following happens:

1. Construct Animal
2. Construct Dog

When the instance of Dog named leia falls out of scope, the following happens on destruction:

1. Destruct Dog
2. Destruct Animal

If you happen to call Speak() in the destructor of Animal, or in the constructor of Animal, then a pure virtual function error will occur. Most C++ compilers will give you a compiling error; however, you can get around this compiling error by calling a function that calls a pure virtual function.

Here is a code sample that will produce a pure virtual function runtime error in g++, Visual Studio 2005, and Visual Studio 2008.

class Animal
{
public:
    virtual ~Animal() {}
    virtual void Speak() = 0;
    void SpeakPlease()
    {
        Speak();
    }
    Animal() 
    {
        SpeakPlease();
    }
};

class Dog : public Animal
{
public: 
    virtual void Speak() { }
};

int main(int argc, char* argv[])
{
    Dog leia;
    return 0;
}

Can C# have pure virtual function errors?

No.

C# allows you to create pure virtual functions by using the abstract keyword on each of your abstract function/methods. And if you have even one abstract function/method in your class you must also use abstract before your class declaration.

C# gets around pure virtual function calls though, but arguably in a worse way.

public abstract class Animal
{
    public Animal()
    {
        Speak();
    }

    ~Animal()
    {
        Speak();
    }

    public abstract void Speak();
}

public class Dog : Animal
{
    public override void Speak()
    {
        Console.WriteLine("Woof!");
    }

    ~Dog()
    {
    }
}

Dog::Speak() will be called in the destructor of Animal even know Dog is already destructed. Obviously this can lead to many problems.

Can Python have pure virtual function errors?

Kind of, and only if you follow certain conventions.

Python can't define abstract functions directly, instead you simply raise an exception of type NotImplemented.

In Python all functions/methods are virtual.

This is to say pure virtual function support is defined in Python simply by convention instead of language constructs.

Therefore unlike C++ and C#, you can create objects of a class that have some of it's functions/methods as abstract. In that sence you can have pure virtual function errors (via NotImplementedError exceptions)

But Python works like C# in the sense that even before the derived type is constructed, it will call into it. The end result is that it throws an exception that can be caught.

class Animal(object):
  def __init__(self):
    print("Constructing animal")    
    self.Speak()
  def Speak(self):
    raise NotImplementedError
  def __del__(self):
    print("Destructing animal")

class Dog(Animal):
  def __init__(self):
    super(Dog, self).__init__()
    print("Constructing Dog")
  def Speak(self):
    print("Woof!")    
  def __del__(self):
    print("Destructing dog")
    super(Dog, self).__del__()

def Test():
  leia = Dog()

Next time you get an error like: "R6025 Pure virtual function call", perhaps you will wonder less about the source of the error.

A common mistake people make in C++ is thinking that arrays and pointers are the same thing. They're not.

char *p = "hello";
char q[] = "hello";

These 2 lines are very different.

The first is a pointer to a string literal. The string literal is in read only memory. Changing p[i] for any index i is undefined.

The second is a char array initialized with 'h', 'e', 'l', 'l', 'o', '\0'. Changing q[i] for any index i in the range 0..5 is fine.

Consequently:

assert(sizeof(p) == sizeof(char*)); 
assert(sizeof(q) != sizeof(char*));
assert(sizeof(q) == 6);

Not only are pointers and arrays 2 different things completely, but you can also have pointers to arrays. Most people think that a char* is a pointer to an array. It's not.

char sz[12];

//This is fine, p points to sz's first element's address
char *p1 = sz;

//Compiling error, Can't convert a pointer to 12 elements to a pointer to a char
char *p2 = &sz;

//This is the correct way to create a pointer to an array
char (*x)[12] = &sz;

//Compiling error, can't convert a pointer to 12 elements to a pointer to 10 elements
char (*y)[10] = &sz;

And of course you can also create references to arrays. But the syntax is just as ugly as the syntax for pointers to arrays.

//r is now a reference to sz
char (&r)[12] = sz;

I've long known about the rope data structure, but it hasn't dawned on me until now in what cases you'd actually want to use it. I also didn't take the time to see how a rope was actually implemented until I looked it up tonight.

Here's an explanation:

The problem with a string data structure is that it's very hard to do insertions into the middle of the string. This means that if you are continually inserting text into the middle of your string, then you will need to re-allocate your buffer a lot of times.

Also to append 2 strings you are forced into copying the 2nd string into the first string's buffer. Assuming the first string's buffer is large enough. If the buffer is not large enough, then the first string will need to re-allocate and copy.

If you have a really really large string, let's say 1GB worth of string data, then a simple insertion of a couple words means you need to move the rest of the characters over and then null terminate. This is an O(N) operation, which means you have to process 1GB worth of data even for any insertion into a 1GB string.

A rope is a special case of a binary tree data structure where each leaf node holds a substring (or an array of characters). Nodes that are not leaf nodes do not hold an array of characters.

A left child that is a leaf is the left part of a string. A right child that is a leaf node is the right part of the string. To get the whole string you process the left child then the right child.

You can concatenate 2 ropes easily by creating a common root node and joining them together.

Example:

RootNode = "Hello"

I want to append " World" so first I create a new rope with a single RootNode....

RootNode = " World"

Then I combine both of those ropes:

RootNode:
 - Left Child: "Hello"
 - Right Child: " World"

Now if we want to make an insertion into the middle of the stirng: "Hello Great World" we simply made a new node and join the leaf node "Hello" with this new node " Great".

RootNode:
  LeftChild:
   - LeftChild: "Hello"
   - RightChild: " Great"
  RightChild: " World"

To get the full string you simply process the tree from the root node, following the left subtree first.

Appending becomes an O(1) operation. Indexing becomes O(logn), and printing everything is just as efficient, other than the rope having a constant factor overhead.

If you are implementing your own rope data structure from scratch you can actually take advantage of the non leaf nodes. They can be used for any type of hierarchical data that would apply to all of its children. For example, perhaps special formatting. Getting a whole item's format would simply involve getting the parent of the nodes all the way up to the root.

You could also do things like make each leaf node a single word. Then you could implement a spell check pretty easily without having to process each node to find the distinct words in each node.

I'm currently reading:

1. Gray Hat Python: Python Programming for hackers and reverse engineers by Justin Seitz
2. C# in depth 2nd edition by John Skeet

I'm about half way through both books. They're both great books so far.