Ruby : Tetris

If you've heard what Ruby on Rails has done for Web Development you may be interested in Shattered. It's like Ruby on Rails for games development. It's only at version 0.3.2 at the moment, early days but it looks promising already. I'm investigating it with a view of using it as a rapid prototyping tool for more avant-garde game designs.

Everything you need to know can be found on the Shattered Weblog which has some very useful links in the top right hand corner.

I've written a simple tetris game using it to limber up :) I'm currently in the process of writing a little tutorial on the Shattered Wiki to help people out. I found it quite hard to get going at first due to the lack of examples and documentation. Saying that though, if you're prepared to look through the Shattered sources and reference documentation it's not too hard to find out what's going on and it shows some very nice likke Ruby tricks as well.

Check it out

Ruby : Pretty Code

I've been through many beginners tutorials for Ruby and I must say I really like this language. I think it's going to be very useful. The Pragmatic Programmers - Dave Thomas and Andy Hunt - give some good advice to learning a new language ... they say you must ask the question, "How will I know when I'm done?". I decided that my first "bout" of learning would be concluded when I had written my own program to prettify the text files I write for this blog! Usually I have to search and replace certain characters, manually add html tags for line breaks and code snippets, ensure that any preformatted line doesn't exceed 62 characters ... in short, a bit of a chore.



So here's the Ruby blog prettifier ... and of course, this blog post is the first to have been run through it! :)

class String

def subAfter str, ext
    self[0..self.index(str)-1]+"."+ext
end

end

$column = 62
filename = ARGV[0].to_s

puts "Processing "+filename+"...\n"

File.open(filename, "r") do |file|

    outFile = File.new(filename.subAfter(".","htm"), "w")

    code = false;
    
    file.each_line do |line|
    
        if line.chomp == "@@@"

            if code
                outFile.puts "</pre></tt></blockquote>"
            else
                outFile.puts "<blockquote><pre><tt>"    
            end

            code = !code;
            
        else
        
            if code
            
                long = line
                line = ""

                while long.length > $column

                    space = long[0..$column].rindex(" ")
                    
                    if space == nil
                        space = $column
                    end
                    
                    line += long[0..space]+"\n"
                    long =  long[space+1..-1]
               
                end

                line += long
                   
            
                line.gsub!(/</,"<")
                line.gsub!(/>/,">")
            else
                line.gsub!(/\n\r|\n|\r/, "<br>") 
            end

            outFile.puts line
    
        end
        
    end
    
    outFile.close()

# This is a really long comment which I've added to show you 
how the code prettifier neatly looks for the last space before 
col 80 and splits the line :) 
#_This_is_another_really_long_comment_which_I've_added_to_show_
you_how_the_code_prettifier_simply_cuts_the_line_if_there_are_n
o_spaces!

end

Ruby : to_eng Integer class extension

Here's the "English Number" method implemented in a more useful form; as an extension to the Integer class. It now works with negative numbers to. The usage is simple.

puts 0.to_eng(0) # arg is 0 for British, 1 for American
puts 12.to_eng(1)
puts -54.to_eng(1)
puts (10**600).to_eng(0)

# extend the Integer class with a "to english" method

class Integer

def to_eng scale

  number = self.abs

  if number == 0
    return 'zero'
  end

  # ... code removed see previous post

      if write > 0
      
        exps = write.to_eng(scale)

        # ...
        
      end
# ...

  if self<0
    numString = "Minus " + numString
  end

  #  Now we just return "numString"...
  numString

end

end

Ruby : English Numbers

Well, it's been almost a month since my last post and what a busy month it's been! I started to write an article about a wrapper I had written for C++ iostreams that automatically closes them on scope exit until I found out that they do that anyway!! Talk about redundant levels of abstraction!

I've also found myself over-using templates recently, I mean they're fun to use but they tend to obfusticate code and generate hard-to-read compiler errors. I had this realisation after discovering Ruby - one of the easiest, most concise and powerful "scripting" languages I've ever had the pleasure to use. Check it out www.rubycentral.com. I've been following a great article called Learn To Program (Ruby), a precursor to the book by the same name.

On Chapter 8 there's a nifty English Number Program example that takes any positive integer and returns the english name of that number. It's quite limited and only works properly between 0-999. The author sets an exersize to make it work for thousands and millions and asks, how high can you go? My answer? Is that British Scale or American Scale? Either? Ok, well, in either case I can go as high as 10^600, which is the largest number-word below googolplex which is too large to include anyway :)


Here's my first Ruby program (based on the original example), enjoy ... for an example of conciseness see the code I wrote to sort the array of name/exponent pairs by exponent ...

def englishNumber number, scale
  if number < 0  #  No negative numbers.
    return 'Please enter a number that isn\'t negative.'
  end
  if number == 0
    return 'zero'
  end

  # check scale:
  
  if scale<0 or scale>1
    return 'scale out of range'
  end  
  
  # valid scales: 
  # 0) British (long scale) 
  # 1) American (short scale)
  
  numString = ''  #  This is the string we will return.
  
  onesPlace = ['one',  'two',  'three', 'four',     
               'five', 'six',  'seven', 'eight',  'nine']
  tensPlace = ['ten',  'twenty', 'thirty', 'forty',  'fifty',
               'sixty',   'seventy',   'eighty',   'ninety']
  teenagers = ['eleven',  'twelve',    'thirteen', 'fourteen', 
               'fifteen', 'sixteen', 'seventeen', 'eighteen', 
               'nineteen']
  
  # short scale words
  
  expTens = [['b'],['tr'],['quadr'],['quint'],['sext'],
             ['sept'],['oct'],['non'],['dec'],['undec'],
             ['duodec'],['tredec'],['quattuordec'],['quindec'],
             ['sexdec'],['septendec'],
             ['octodec'],['novemdec'],['vigint']]
  
  # add short scale exponents and append "illion"'s!

  exp = 9
  
  expTens.each do |expTen|
  
    expTen[0] = expTen[0] + 'illion';
    expTen.push(exp)
    exp = exp + 3
  
  end
      
  if scale == 0 # British (long scale) 
                # not using uncommon "milliard" (10**9)
  
    # convert exponents to long scale
    
    expTens.each do |expTen|

        expTen[1] = (expTen[1] - 3) * 2    
    
    end
    
  end
 
  # add words and exponents common to both scales
  
  expTens = [ ['hundred', 2], ['thousand', 3], ['million', 6] ] 
            + expTens
  expTens = expTens + [ ['googol', 100], ['centillion', 600] ]

  # rational.rb says googolplex i.e. 10**(10**100) => Infinity
 
  # unfortunatly now after the possible conversion to British 
  # long scale the expTens array is not in order. A googol's 
  # exponent is 100 which means it should be between 
  # sexdecillion and septendecillion.

  # let's simply sort the array every time in case other such 
  # ordering errors occur

  expTens.sort! { |x, y| x[1]<=>y[1] } # how easy was that! :)
 
  left  = number

  # handle hundreds and above

  expTens.reverse.each do |expTen|

      value = 10**expTen[1]
      write = left/value
      left  = left - write*value
      
      if write > 0
      
        exps = englishNumber(write, scale)
        numString = numString + exps + ' ' + expTen[0]

        if left > 0

          if left < 100
            numString = numString + ' and '
          elsif
            numString = numString + ', '
          end
          
        end
        
      end
    
  end

  # handle teens
  
  write = left/10          #  How many tens left to write out?
  left  = left - write*10  #  Subtract off those tens.
  
  if write > 0
    if ((write == 1) and (left > 0))
      #  Since we can't write "tenty-two" instead of "twelve",
      #  we have to make a special exception for these.
      numString = numString + teenagers[left-1]
      #  The "-1" is because teenagers[3] is 'fourteen', 
      #  not 'thirteen'.
      
      #  Since we took care of the digit in the ones place
      #  already, we have nothing left to write.
      left = 0
    else
      numString = numString + tensPlace[write-1]
      #  The "-1" is because tensPlace[3] is 'forty', 
      #  not 'thirty'.
    end
    
    if left > 0
      #  So we don't write 'sixtyfour'...
      numString = numString + '-'
    end
  end
  
  # handle ones
  
  write = left  #  How many ones left to write out?
  left  = 0     #  Subtract off those ones.
  
  if write > 0
    numString = numString + onesPlace[write-1]
    #  The "-1" is because onesPlace[3] is 'four', not 'three'.
  end
  
  #  Now we just return "numString"...
  numString
end

def formatEnglishNumber value, scale
 value.to_s+" = "+englishNumber( value, scale)
end

def formatEnglishNumberExp exp, scale
 "10**"+exp.to_s+" = "+englishNumber(10**exp, scale)
end

scale = -1;
while scale<0 or scale>1
    puts "Use 0) British Long Scale 1) American Short Scale?"
    scale = gets.chomp.to_i
end

puts "Some Numbers:"
puts
puts formatEnglishNumber(  0, scale)
puts formatEnglishNumber(  9, scale)
puts formatEnglishNumber( 10, scale)
puts formatEnglishNumber( 11, scale)
puts formatEnglishNumber( 17, scale)
puts formatEnglishNumber( 32, scale)
puts formatEnglishNumber( 88, scale)
puts formatEnglishNumber( 99, scale)
puts formatEnglishNumber(100, scale)
puts formatEnglishNumber(101, scale)
puts formatEnglishNumber(234, scale)
puts formatEnglishNumber(1000, scale)
puts formatEnglishNumber(3211, scale)
puts formatEnglishNumber(10000, scale)
puts formatEnglishNumber(100000, scale)
puts formatEnglishNumber(999999, scale)

puts
puts "Let's test the scale: "
puts

scalemax = 64;
if scale == 0
    scalemax = 121
end

scalemax.times do |exp|
    puts formatEnglishNumberExp(exp, scale)
end

puts
puts "Some bigger numbers!"
puts
puts formatEnglishNumber(100098765432134, scale)
puts formatEnglishNumber(2348723948732948723, scale)
puts formatEnglishNumber(2342342324100098765432134, scale)
puts formatEnglishNumber(124523598054213453230980329480, scale)
puts formatEnglishNumberExp(100, scale)
puts formatEnglishNumberExp(600, scale)
# googolplex is too big!!
#puts formatEnglishNumberExp(10**100, scale) 

puts
puts "Press Enter To Quit"
gets

C# : Localization and Web Services

I've recently moved house, what hard work that is! We're pretty much back to normal now so hopefully I will be blogging about some more coding topics that I've found interesting. I've recently been developing a small WinForms application in C#. It needed to be localized for a number of languages and I was pleasantly surprised at how easy this was.

If you set the "Localizable" property of your main form or custom control to true you can then set the language. Any changes made for each selected language (the pull-down contains all that are available through the OS) are writting to a seperate .resx file for that language, so for example, Form1.resx is the default language UI and Form1.fr.resx is the French version. Subsequent language resx's only contain the changes from the default file. The beauty of the entire UI resource file being customizable and not just a string table is that you can change the layout of controls to accomodate longer strings etc.

One annoying thing I did encounter was that if you edit the .resx file by hand in the VS .NET editor (you'll have to Show All Files in the Solution Explorer first) then any additions you make (i.e. for Dialog Messages etc.) will be overwritten by the IDE if you make changes in that.


It's also very, very easy to consume a Web Service in VS .NET. It's simply a matter of adding a "Web Reference" to the project in the Solution Explorer, you enter the URL and it is automatically wrapped in a namespace/class for the language you are developing in. It can then be simply instantiated and used. I actually wrote a COM object in pure C++ that uses a web service and is in turn used by a C# application and through script!


Cross-language development is fun when things are decoupled like this but I find that developing software using Managed C++ with a combination of pure C++ APIs and Managed Types can be a bit of a headache. The Garbage Collector obviously doesn't let managed types own un-managed ones etc. so you have to do your own memory management on them. When all's said and done, if I'm using .NET I'd rather program in C# .. a language specifically designed and fit for purpose rather than Managed C++ which has been (very ingeniously) hacked to work for the .NET runtime.

C++ : Meta Programming : Fibonacci and Phi

In this blog I explore the relationship between the Fibonacci sequence and the Golden Ratio Phi. I write a meta program to calculate the Fibonacci sequence at compile time and use the last two elements in the sequence to calculate Phi.


Fibonacci Sequence:

 1 1 2 3 5 8 13 21 34 ...

  N    N   + N
   i =  i-1   i-2
   

The following expression tends towards Phi as i increases:

 N  /  N
  i     i-1

Another definition of Phi:

Phi * Phi = Phi + 1

Which rearranged proves that Phi is 1 + it's reciprocal, hinting at a much simpler algorithm to calculate it than the one we have here based on this equation:

Phi = 1 + 1/Phi

This could be expressed as a recursive function and we can start with any number, except 0 or -1, to tend towards Phi, 1 will do though.

The following link explores the interesting mathematical properties of Phi


http://www.mcs.surrey.ac.uk/Personal/R.Knott/
Fibonacci/phi.html#simpledef


Now time for some code, here's a runtime recursive function that calculates the last two numbers in the Fibonacci sequence for any given index in the sequence i:

#define DO_OUTPUT

typedef unsigned long long ulong;
typedef std::pair<ulong, ulong> tuple;

// Fibonacci
// Run-time Recursive Function
void GetFibonacciTupleImpl(unsigned int i, tuple &result)
{
    if(i>0)
    {       
        result.second += result.first;
        result.first = result.second - result.first;
#ifdef DO_OUTPUT
        std::cerr << result.second << " ";
#endif                                
        if(result.second>result.first) // wrapping guard
            GetFibonacciTupleImpl(i-1, result);
        else  // store recursive level
           result.first = result.second = i;
        
    }
}

void GetFibonacciTuple(unsigned int i, tuple &result)
{
    result.first = 1;
    result.second = 1;
#ifdef DO_OUTPUT
    std::cerr << "1 1 ";
#endif
    GetFibonacciTupleImpl(i, result);
#ifdef DO_OUTPUT
    if(result.first==result.second && result.second>1)
        std::cerr << "\nwrapping occured at i=" 
                  << (i-result.first+2) << "\n";
#endif
}

Here's a meta-programming solution for the exact same thing, only all calculated at compile-time!

template<int I>
struct Fibonacci
{
    enum { value = Fibonacci<I-1>::value +
                   Fibonacci<I-2>::value };
};

template<>
struct Fibonacci<1>
{
    enum { value = 1 };
};


template<>
struct Fibonacci<0>
{
    enum { value = 1 };
};

template<int I, typename T>
struct FibonacciTuple
{
    enum {
        first = Fibonacci<I-1>::value,
        second= Fibonacci<I>::value
    };
    
    // run time part as not integral ...
    static const T getRatio()
    {
         return (T)second / (T)first;
    }
};

Now this only works up to a point. If you try to compile Golden::FibonacciTuple<47,double>::getRatio() under g++ 3.4.4 you get a compiler error: Integer Overflow in Expression. Also the results are only correct up to Golden::FibonacciTuple<45,double>::getRatio(). Initially I surmised this was due to some compiler recursion-stack related problem but after I'd actaully read the compiler output! I realised the error occured on the line where the enum value is evaluated (using the + operator). If it were a compiler stack-depth problem then something like this migth have alleviated the problem:

template<ulong I>
struct Fibonacci
{
   ...
};

but the error lies with the face that it looks like the compiler uses a signed integer to store enum values. Why signed? Well the runtime version uses an unsigned int to store the Fibonacci sequence value and it breaks down after 90 recursions! (i.e. twice as many).

Of course this is only a bit of fun and isn't the most efficient way of calculating Phi. Initially I thought perhaps I could write a way of statically storing the value of Phi in a program without defining it as a literal value, i.e.

static const float Phi = 1.618....;

However, firstly there's the enum problem and secondly (and this is a related problem) we can only use integral values at compile-time. This is illustrated by the following meta program:

// Cannot get Phi using the reciprocal method
// since only integral numbers are used in enums!

template<int I>
struct Phi
{
    enum { value = 1 + 1/Phi<I-1>::value };
};

template<>
struct Phi<0>
{
    enum { value = 1 };
};

This is a flawed implementation of the reciprocal method of calculating Phi as mentioned above. This obviously requires less work than the Fibonacci method but isn't quite as interesting from a mathematical point of view.

In conclusion then, as well as exploring the fascinating relationship between the Fibonacci Sequence and Phi, we've found out about some limitations of what we can and can't do a compile-time and managed to deduce the g++ 3.4.4 uses an int to store an enum values!

C++ : Exploring Sorting Part IV

Let's start with the full code for the promised generic quicksort implementation that is my attempt at an "exercise for the reader" from an Alexandrescu article mentioned previously

template<class Iter>
void sort(Iter left, Iter right)
{
    // make larger to invoke insertion sort sooner
    enum { threshold = 56 }; 
    while(right-left>1)
    {
        // do insertion sort on range
        if(right-left<=threshold) 
        {
            Bannister::insertionSort(left, right);
            return; // done sorting range
        }
        else // do quicksort on range
        {
            const std::pair<Iter,Iter> pivot = 
                Bannister::partition(
                    left, right, 
                    *Bannister::selectRandomPivot(
                        left, right));
            if (left < pivot.first)
              Bannister::sort(left, pivot.first);
            if (right > pivot.second)
              left = pivot.second;
            else
              break;
        }
    }
}

Quite different from the original C code I posted in my last blog! I'm sure you could have made that function generic using the same method as shown with the bubblesort, it's not worth going into detail again. The above algorithm uses a quicksort for arrays over 56 elements long, otherwise it uses an insertion sort which is another fast method. It's a matter of testing to get the best speed benefits, something I have as yet to write a test framework for. Now to explain the quicksort part of the algorithm. The selecting of a pivot value and partitioning of the array passed to the sort function is deferred to two functions for clarity and to make it easier to tinker with the algorithm. The sort function itself has been partially converted to an iterative solution to try and alleviate the speed costs of recursion.

The pivot value is chosen randomly to help prevent the "worst-case scenario" of always choosing the lowest number around which to partition the array, which is always the case when sorting an array which is already ordered using the first value as the pivot. Another speed increase is achieved by uses Alexandrescus "fit pivot" technique which is based on the more well-known "fat-pivot". The "fat pivot" algorithm partitions the array into 3, not 2, sub arrays. The 3rd contains all occurences of the pivot value and places this in the middle of the other two (which contain values lower and values higher than the pivot respectively). This reduces the number of partitioning steps needed when there are long runs of equal numbers. However there is an overhead cost in doing the partitioning. The "fit pivot" algorithm will simply apply the normal "two partition" algorithm to an array but carry on moving the right pointer to the left and vice versa until numbers are found which are not equal to the pivot value. This way, if there is a run of pivot-equal numbers in the middle of the array, it will be kept there, not passed to the quicksort again and the resulting two partitions will be smaller, increasing the speed in those situations at no extra cost. Here are the two functions (including a more standard selectFirstPivot).

template<class Iter>
Iter selectFirstPivot(Iter left, Iter right)
{
    return left;
}

template<class Iter>
Iter selectRandomPivot(Iter left, Iter right)
{
    long int index = Bannister::rand(0, right-left);
    return left + index;
}

template<class I0, class I1, class T>
std::pair<I1,I0> partition(
    I0 left, I1 right, T pivot)
{
  --right;
  while (left < right)
  {
    while ((*right >= pivot) && (left < right))
      --right;
    if (left != right)
    {
      *left = *right;
      ++left;
    }
    while ((*left <= pivot) && (left < right))
      ++left;
    if (left != right)
    {
      *right = *left;
      --right;
    }
  }
  *left = pivot;
  // all numbers in-between will be equal
  return std::make_pair(right, left+1); 
}

Note, I've put my functions in a namespace called "Bannister" (rubbish name I know, it's named after Roger Bannister, the first man to run the 4 minute mile). Here's the insertion sort algorithm.

template<class Iter, class T>
void insertionSort(Iter left, Iter right, T) 
// T unused, only type is needed
{
  Iter i, j;
  T index;

  for (i=left+1; i != right; ++i)
  {
    index = *i;
    j = i;
    while ((j > left) && (*(j-1) > index))
    {
      *j = *(j-1);
      --j;
    }
    *j = index;
  }
}

template<class Iter>
void insertionSort(Iter left, Iter right)
{
    // dereference left to deduce type of iterator
    Bannister::insertionSort(left, right, *left); 
}

And finally I'll include the fast pseudo-random function I found to calculate the random pivot.

// Park-Miller "minimal standard" 31 bit 
// pseudo-random number generator
// implemented with David G. Carta's 
// optimisation: with 32 bit math and
// without division..

long unsigned int rand31()
{
    static long unsigned int seed = 16807;
    long unsigned int hi, lo;

    lo = 16807 * (seed & 0xFFFF);
    hi = 16807 * (seed >> 16);

    lo += (hi & 0x7FFF) << 16;
    lo += hi >> 15;

    if(lo>0x7FFFFFFF) lo -= 0x7FFFFFFF;

    return (seed=(long)lo);
}

long int rand(long int lo, long int hi)
{
    return (long int)(rand31() % (hi-lo)) + lo;  
}

I should include some examples of using these functions as well ... (I really am letting the code speak for itself in this blog)... disclaimer: really bad test harness with no error-checking!!

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <limits>
#include <vector>
// previous code goes in here...
#include "sort.h"

template<class Iter>
void output(Iter left, Iter right)
{
    for(Iter it=left; it!=right; ++it)
        std::cerr << *it << " ";
    std::cerr << std::endl;
}

template<class Iter>
Iter find_unsorted(Iter left, Iter right)
{
    for(Iter it=left+1; it!=right; ++it)
    {
        if(*it<*(it-1))
        {
            return it;
        }
    }
    return right;
}

int unit(void)
{
    const int size = 12;
    int arr[] = {4, 0, 5, 7, 2, 2, 2, 2, 2, 1, 78, 4};
    float arf[] = {4.2f, 0.1f, 5.3f, 7.8f, 8.02f, 
                   2.3f, 45.9f, 2.1f, 2.1f, 1.2f, 
                   78.0f, 4.2f};
    int arr[] = {0, 7, 1, 8, 2, 9, 
                   3, 10, 4, 11, 5, 6};
    typedef std::vector<char> char_array_t;
    char_array_t arc;
    arc.push_back('k');
    arc.push_back('c');
    arc.push_back('e');
    arc.push_back('f');
    arc.push_back('b');
    arc.push_back('g');
    arc.push_back('i');
    arc.push_back('h');
    arc.push_back('l');
    arc.push_back('d');
    arc.push_back('j');
    arc.push_back('a');
    
    output(arr, arr+size);
    bubbleSortT<int*>(arr, size);
    Bannister::sort(arr, arr+size);
    output(arr, arr+size);
        
    output(arf, arf+size);
    Bannister::insertionSort(arf, arf+size);
    Bannister::sort(arf, arf+size);
    output(arf, arf+size);

    output(arc.begin(), arc.end());
    Bannister::sort(arc.begin(), arc.end());
    Bannister::insertionSort(arc.begin(), arc.end());
    output(arc.begin(), arc.end());

    return 1;
}

int main(int argc, char **argv)
{
    if(argc==1)
    {
        return unit();
    }
  
    typedef std::vector<char> char_array_t;
    char_array_t arc;

    // Kilobytes of characters to sort
    const int mem_size_bytes = 1024 * atoi(argv[1]); 
    for(int i=0; i<mem_size_bytes; ++i)
    {
        arc.push_back(Bannister::rand('A', 'Z'));
    }
       
    switch(argv[2][0])
    {
    case 'b':
        std::cerr << "bubble sorting array...\n";
        bubbleSort(arc.begin(), arc.end());
        break;
    case 'q':
        std::cerr << "Bannister::sorting array... "
        "(hybrid quicksort/insertion sort "
        "with random fit pivot)\n";
        Bannister::sort(arc.begin(), arc.end());
        break;
    case 'i':
        std::cerr << "insertion sorting array...\n";
        Bannister::insertionSort(
                   arc.begin(), arc.end());
        break;
    case 's':
        std::cerr << "std::sorting array...\n";
        std::sort(arc.begin(), arc.end());
        break;
    default:
        break;
    }
    
    char_array_t::iterator it = 
           find_unsorted(
               arc.begin(), arc.end());
    if(it!=arc.end())
    {
       std::cerr << "Unsorted! Error!\n" << std::endl;
       output(it-10, it+10);
       //output(arc.begin(), arc.end());
    }

    return 1;
}

Now I propose an exercise for the reader... write some proper test code to automatically time and compare the results using different sorting methods.

Some simple timing tests I've done (using >time ./sort.exe on the bash command line under Cygwin) show that the Banniser::sort is many times quicker than a bubble sort or even an insertion sort with large arrays. It doesn't hold a candle to std::sort though. I suspect the std::sort implementation uses some really good platform-specific tricks, maybe implementing some inner loops in assembly. Anyone who could attempt modifying this code to go even faster is more than welcome!

Haskell : Getting Started

Here are a couple of links for anyone who wants to get started using Haskell. These are both interpreter implementations of the language but are good for getting started.

http://haskell.org/hugs/

Hugs 98 is a functional programming system based on Haskell 98, the de facto standard for non-strict functional programming languages. Hugs 98 provides an almost complete implementation of Haskell 98.

http://www-users.cs.york.ac.uk/~ndm/projects/winhugs.php

WinHugs is the Windows user interface to Hugs. In addition to all of the Hugs features, it includes type browsers and heirarchical constraint views. WinHugs should run on any version of Windows since 95, i.e. 95/98/ME/NT/2K/XP.

Haskell : QuickSort in 2 Lines

As an aside to the series of blogs on sorting and in an effort to ensure you that this is not a C++ only blog here's how you can express the quick sort algorithm in haskell

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x]
               ++ qsort (filter (>= x) xs)

Compare this to the C example below! Haskell is a high-level, functional programming language. It is definitely worth a closer look, even if you don't use it to develop anything it will offer a different mindset that may help you approach and solve problems from a different angle.

Programming Quote of the Month

"The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds castles in the air, from air, creating by exertion of the imagination. Few media of creation are so flexible, so easy to polish and rework, so readily capable of realizing grand conceptual structures."

- Frederick P. Brooks, "The Mythical Man-Month: Essays on Software Engineering, Anniversary Edition (2nd Edition)" by Frederick P. Brooks , ISBN: 0201835959,
page: 7-8

www.softwarequotes.com

C++ : Exploring Sorting part III

I promised to talk about faster sorting algorithms and one of the fastest is the appropriately named quicksort. The algorithm was devised by British computer scientist in 1962! (I told you sorting was an age-old problem). His name is Charles Antony Richard Hoare his original paper is entitled C. A. R. Hoare. "Quicksort," Computer Journal, 1962, 5, p.p. 10-15. and is apparently still the most cited paper on the subject.

Anyway, I read an interesting article on searching (of which sorting is part of the solution) by Alexandrescu and the subject of this and the next blog is basically the good old "exercise for the reader" which I've done. I'm not going to claim that mine is the best or fastest implementation. In fact it performs alot slower the std::sort but there's always room for improvement and it's a good learning exercise. I have yet to completely finish tinkering with it so any suggestions would be welcome. I'd like to remove all recursion and make as many other speed improvements as possible. I also need to write a better testing framework with some proper profiling of the function. But anyway... here's the original quicksort algorithm expressed as a simple, non-generic function in C taken from Michael Lamont whose knowledge base pages have lots of nicely expressed C implementations of sorting algorithms with explanations and metrics

void quickSort(int numbers[], int array_size)
{
  q_sort(numbers, 0, array_size - 1);
}


void q_sort(int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}

In part III we'll take this, make it generic as we did with the bubbleSort in Part II and use the ideas put forward by Alexandrescu to improve it's speed even further.

C++ : Exploring Sorting part II

In order to make our bubble sort function more generic (an thereby more useful) we could give it a function signature something along these lines:

template<class T>
void bubbleSort(T numbers[], size_t size);

This would mean we could call the function with an array of any type and the compiler would deduct the type to instantiate the function using the first parameter i.e.

float f[4] = {1.1f,0.2f,-2.3f,0.3f};
int i[4] = {6,3,1,5};
char *s = "zyxw"; // nicer syntax than...
//char s[4] = {'z','y','x','w'};

bubbleSort(f,4); // uses float
bubbleSort(i,4); // uses int
bubbleSort(s,4); // uses char 

With the wonders of (take a deep breath) explicit template function argument specification we can do this now too...

bubbleSort<double*>(f,4); uses double

Even though we're using a float array the function is explicitly instantiated using the type double. This would compile fine but obviously yield a runtime error in this specific case because we'd be performing pointer arithmetic (i.e using the array) with a double type which is twice as big as the float parameter. But hang on a second... why does it even compile? You may have noticed something amiss here... we've used double* here explictly but when we don't specify the type i.e. bubbleSort(f,4) shouldn't the type of f be float and not float*? If this were true then our function would be written by the compiler thus:

// not what we get
void bubbleSort(float *numbers[], size_t size);
// this IS what we get!
void bubbleSort(float numbers[], size_t size); 

The reason for this, and the reason why all the above code examples work is because when the compiler does type deduction it performs a number of type conversions on the actual type passed. If you want more details on this here's an excellent article by Angelika Langer on Function Template Arguments. I learnt alot reading this article. Jump to the section entitled "Implicit Type Conversions Involved in Template Argument Deduction" if you are just interested in what we've been talking about here, but I heartily recommend you read the whole thing. Anyway, I've got off the beaten track again, it's time to finish making our poor old, slow bubbleSort generic... aren't we done? No. It may work in it's current state for all POD (Plain Old Data) types but try this:

std::vector<int> array;
array.push_back(6);
array.push_back(3);
array.push_back(1);
array.push_back(5);

bubbleSort(array, array.size());

...and you'll quickly see it doesn't work for STL containers. You could always compile it and see why but put simply it's because we are asking the compiler to instantiate something along these lines:

void bubbleSort(std::vector<int> numbers[], size_t size);

Which is obviously ludicrous! Anyway, when we want to iterate though an STL container we don't pass the containers to algorithms but the containers iterator. I.e. std::swap(array.begin(), array.end());.

The iterator is an abstract concept, by that I mean that anything that behaves like an iterator is an iterator, including simple arrays. The reason why simple arrays are iterators too is because iterators are implemented using operator overloading of ++, --, [] among others (and depending on the type of iterator) to use the same syntax as pointer arithmetic. This gives us a clue as to how we can write our fully generic bubbleSort function. If we pass "pointers" to the start and end we can use pointer arithmetic inside the function body and it should work with both simple arrays and STL containers. One thing to note is that STL ranges are defined with a closed start and an open end. This means the begin() of an iterator points to the first element whilst the end() actually points to the element directly after the last element. This is something we need to be aware of when writing the function, luckily for us it is a really good design decision and greatly simplifies a lot of things for us! Anyway, I don't want to stray from the path of this blog anymore so perhaps we'll discuss STL ranges later, here's the final implementation of bubbleSort...

template<class Iter, class T>
void bubbleSort(Iter left, Iter right, T)
{
    bool swap = true;
    while(swap)
    {
        swap = false;
        for(Iter it = left + 1; it!=right; ++it)
        {
            if(*it<*(it-1))
            {
                T tmp = *it;
                *it = *(it-1);
                *(it-1) = tmp;
                swap = true;
            }
        }
    }
}

However we can't use this function in exactly the same way as we use std::sort, it has 3 arguments! The first two specify the range we want to sort and the 3rd passes the type used in the container of the iterator! We need this to store our temporary variable T tmp = *it. Notice that there is no parameter variable specified as we only need to use the type. This makes the usage of this function pretty ugly:

//dereference first element to pass type of container
bubbleSort(array.begin(),array.end(),*array.begin());

No worries we can use explicit function template argument specification! (I hear you cry ... erm), well no we can't. We'd have to specify all the template arguments which would make the function quite tedious to use. A better solution is to write a simple function overload to call the above for us:

template<class Iter>
void bubbleSort(Iter left, Iter right)
{
    bubbleSort(left, right, *left);
}

This is a neat trick we can use to quite clearly derive the container type of an iterator in a lot of situations.

To conclude this part we now have a more useful generic version of our algorithm which can by used for simple arrays and STL containers. The point of this blog has been to demonstrate how it's possible to convert an algorithm into a more useful, generic form. We'll look at some faster sorting algorithms in part III...

C++ : Exploring Sorting part I

Sorting is a fundamental requirement in many programs and libraries. As such it has been throughly explored by many people since the dawn of computers and there are many efficient algorithms and implementations available. This doesn't stop us pulling them apart, finding out all about them and seeing if we can't do better though! This is the first in a series of blogs on the subject where I want to go from looking at sorting algorithms to developing our own generic (of course!) sorting function.


I'll leave you with the good, old (and very, very slow) bubble sort ... we'll make it generic in part II...

void bubbleSort(int numbers[], size_t size)
{
    bool swap = true;
    while(swap)
    {
        swap = false;
        for(int i = 1; i<size; ++i)
        {
            if(numbers[i]<numbers[i-1])
            {
                int tmp = numbers[i];
                numbers[i] = numbers[i-1];
                numbers[i-1] = tmp;
                swap = true;
            }
        }
    }
}

Retro Gaming : What's Knanshon?

Remember Xenon II : Megablast? At the start of every level you bought power ups and upgrades from this guy. One of them was called "Super Knanshon Power" which gave you every power-up and upgrade for the first 10 seconds. Not sure if it was spelt like this but it makes an excellent unique username for sure! :)

C++ : A response to functors

I received an interesting and detailed response to my posts on the uses of std::for_each from my friend Jun. Before we dive in I'd like to point out that I find it interesting that there seems to be an infinite number of ways of solving the same problem in C++! If you've ever used C# you'll know that the for(object in IEnumerable) syntax is part of the language. However this is a very different language despite the syntatical similarities and it doesn't do to pit one language against another ... they all have their uses.

Soapbox time over, let's get on with it!

Jun writes...

The thing I don't like about functors (function objects) is that they can clutter the code and they obscure the flow of the logic. Originally it is clear what you want - I only have to look at what you say is the ugly code (void B::Update()).

But I don't agree that the code has become easier to read or understand (i.e. maintain) toward the end of your article.

At the start it is clear that B has a container which is used to steer its controls.


In the end this simple piece of code is stretched out over a class A_UpdateHandler (it's Update function), B::Init() function and of course the B::Update() function. Undoubtfully the Init(), Update() and the A_UpdateHandler will end up apart from each other in the source file and it will become quite tricky for others (including yourself in a couple of months time) to piece out the flow of the code.

What happens when elements are added to or removed from m_APCollection after Init() has been called?


The design in the end is a workaround for the fact that C++ doesn't support Lambda calculus. If you look at it - the original Update() function is clear, but to be able to use std::for_each you had to create a functor and use a std::bind2nd with a std::mem_fun_ref which makes the end result more complex than what you originally started with.

I can imagine that if someone else would have to make a change to this code and allow for changes to be made to m_APCollection at runtime - (s)he could be in for a bind.


Everything in C++ is solvable by introducing an extra layer of indirection. But by doing so, simple things can be lost in the translation.

If you would use pseudo code to describe your algorithm it would be something like:

for a in m_APCollection do
    control = GetControlByName ( a.GetName( ) )
    if ( control ) then
        graphic.doSomething( control.GetCurrentValue( ) 
                             > a.GetThreshhold( ) )
    end
end

Now wouldn't it be nice to be able to stick as close to this as possible?

You definitely have to read FOREACH Redux by Niebler!
check this out:

BOOST_FOREACH ( char c, "Hello World" )
{
    std::cout << ch;
}

or even

BOOST_FOREACH ( A *a, m_APCollection )
{
    std::string const &name=a->GetName( );
    Control *control = GetControlByName( name ); 
    // can return NULL
    if ( control )
    {
        bool value = control->GetCurrentValue( ) 
                     > a->GetThreshold( );
        graphic.doSomething( value );
    }
}

Sticks pretty close to what you originally intended? Then in turn it
is not that different from what you considered to be ugly code


Now I am curious if there is a way to force std::for_each in without having to write a wrapper and having to use "bind" and "mem_fun_ref".


How about this sneaky way to get access to that private function(compiles with the .NET C++ compiler - I haven't checked with GNU or others). No need to make changes to the interface and this is the update function:

void B::Update( )
{
    Graphic const &graphic = GetGraphic( );
    DoSomethingWithA functor(graphic, *this, 
                             &B::GetControlByName);
    std::for_each(mAPCollection.begin( ), 
                  mAPCollection.end( ), functor);
}

(*disclaimer - I am not promoting this and any loss or
damage resulting from this code is your own responsibility!


Jun


So I agree with all of what is said here and have taken it on board. My main mistake in this case was the desire to use a tool that was unsuited to the task in hand. Having said that I learnt a lot so it is always recommended to try these things out! I actually managed to use a more straight forward functor without the pointer to a private member function hack to solve a similar problem after this and I think it made for much better code. Of the two solutions offered the BOOST_FOREACH is the most robust and readable. The Niebler article is well worth a read. Many good generic tricks are introduced in an interesting context and I learnt a lot. Especially the ScopeGuard trick from Alexandrescu ... but that's a topic for another post. The full code for Jun's own solution is shown below and I think you'll agree too that it is more readable and hence easier to maintain. The intention is clear and as it says in The Pragmatic Programmer "Program close to the Problem Domain".

#ifndef __B__H
#define __B__H

#include 
#include 

class A
{
public:
    std::string const& GetName() const;
    int GetThreshold() const;
};

struct Control { int GetCurrentValue() const { return 11; } };
struct Graphic { void DoSomething(bool) const {} };

class B
{
public:
    void Update();
private:
    Control const* GetControlByName(
                   std::string const &name) const;
    Graphic const& GetGraphic() const;

    std::vector mAPCollection;
};

#endif // __B__H

// b.cpp
#include "b.h"
#include 

using namespace std;

string const& A::GetName() const
{
    static string const name("Knanshon");
    return name;
}

int A::GetThreshold() const { return 42; }

//--------------------------------------

namespace
{

    class DoSomethingWithA
    {
        Graphic const &mGraphic;
        B &mB;
        typedef Control const* (B::*GetCtrl)
                               (std::string const&) const;
        GetCtrl  mFoo;
    public:
        DoSomethingWithA(Graphic const &graphic, B &b, 
                         GetCtrl foo)
            : mGraphic(graphic)
            , mB(b)
            , mFoo(foo)
        {
        }

        void operator()(A *a)
        {
            string const &name=a->GetName();
            Control const *ctrl=(mB.*mFoo)(name); 
            // can return NULL
            if ( ctrl )
            {
                bool value = ctrl->GetCurrentValue() > 
                             a->GetThreshold();
                mGraphic.DoSomething(value);
            }
        }
    };

} // anonymous namespace
    
//---------------------------------------------------

Control const* B::GetControlByName(
    string const &name) const
{
    return 0;
}

Graphic const& B::GetGraphic() const
{
    static Graphic const g;
    return g;
}

void B::Update()
{
    Graphic const &graphic=GetGraphic();
    DoSomethingWithA functor(graphic, *this, 
                             &B::GetControlByName);
    std::for_each(mAPCollection.begin(), 
                  mAPCollection.end(), functor);
}

// eof

C++ : Once false always false

I've recently written a useful little class that can be treated like a plain old bool type but has a couple of behavioural differences. It defaults to true on construction and once it is set to false, it can never be set to true. Here it is

class OnceFalseAlwaysFalse
{
public:
 OnceFalseAlwaysFalse() : m_Value(true) {}
 operator bool() { return m_Value; }
 const bool operator ==(const OnceFalseAlwaysFalse &rhs) 
 { return m_Value==rhs.m_Value; } 
 const bool operator !=(const OnceFalseAlwaysFalse &rhs) 
 { return m_Value!=rhs.m_Value; }
 const bool operator !(void) 
 { return !m_Value; }
 const OnceFalseAlwaysFalse &operator =(const bool & value)
 { if(m_Value) m_Value=value; return *this; }
private:
 bool m_Value;
};

What the hell use is that? I hear you cry. Well, consider the following, fictitious example.

// Function to save as many pages as it can, 
// returns false if any failed to print.
bool PrintDocument(void)
{
        bool success = true;

        if(!PrintPage(1))
                success = false;
        if(!PrintPage(2))
                success = false;
        if(!PrintPage(3))
                success = false;

        return success;
}

And this is the function using the OnceFalseAlwaysFalse class instead of a plain old bool...

bool PrintDocument(void)
{
        OnceFalseAlwaysFalse success;
        success = PrintPage(1);
        success = PrintPage(2);
        success = PrintPage(3);
        return success;
}

A lot neater I think you'll agree. It takes out the multiple if tests needed to ensure that the overall success of the function is stored rather than simply the storing the success of the last operation. The class also illustrates one of Bjarne Stroustrups major intentions for the C++ language, i.e. that custom data types can be treated in exactly the same way as built-in types. This is achieved via the medium of operator overloading. For this class I have overloaded the =, !=, == and bool (implicit conversion to bool) operators. The last one is useful as it allows an instance of OnceFalseOnlyFalse to be returned by a function which is defined to return a bool, as many are.


Hope this can help you write some easier-to-read code!

C++ : C++0x

http://www.artima.com/cppsource/cpp0x.html



Bjarne Stroustrup (the creator of C++) offers a sneak peek at the next version of standard C++ ("C++0x") which should be complete by 2009, and will then become C++09.

The current standard version is C++98, it takes along time to ratify these changes!

See my links on the sidebar for Bjarne Stroustrup's Homepage

HTML : <pre><tt>y code

Well, in my first ever post to this blog I mentioned that I was trying to get the formatting to look good for my code examples. One of the easiest ways I found to do this in HTML was by using the <pre> tag. Any text between the <pre> and </pre> tags will not be formatted, i.e. wrapped or have whitespace stripped which your browser usually does. This is very handy for indented code.

One caveat is that you have to be careful to ensure the lines aren't too long. In this blog I ensure that a code line never exceeds column 67.

Ok, that takes care of the formatting, but how do I get a nice fixed width font for the code examples. Style-sheets! I hear you cry, and indeed they do come in very useful for exactly this kind of thing but there is a simpler way to achieve this common task in HTML, the <tt> tag. This stands for teletype. An easy-to-use tag it is much more suitable for writing code snippets in amongst the normal text. The alternative would be something like this: <div class="code"> and then you'd have to specify the styling, i.e. font etc. in a stylesheet - which, by the way, is the only place you should put style information - remember this simple rule:

HTML/XML = Content

CSS/XSL = Style

The two should always be seperate in any good system. Imagine having to go through every single one of your postings and changing them to conform to a style rather than simply changing the template and republishing!


Obviously you can still add additional styling for the <tt> tag if you wish. Indeed on this blog I have changed the font color slightly just to make the in place code snippets stand out a bit more.


I also enclose my large code examples in <blockquote>'s, which in my stylesheet/template is defined as having a darker background since this is how you'll find it done in most books written about code. Be careful to put the <blockquote> inside the <pre> and <tt> tags otherwise the darker blocks will extend to the top and bottom of the containing paragraphs and look ugly.


Anyway, if you have a blog of your own I hope this can help you have <pre><tt>ier text!


For a look at what a good stylesheet can do visit http://www.csszengarden.com/

C++ : In a bind with function objects part IV

Just to recap let’s look at the relevant parts of class B again in it’s entireity…

class B
{
public:
   void Update()
    {     
        Graphic &graphic = GetGraphic();

        std::for_each(
            m_A_UpdateHandlers.begin(),
            m_A_UpdateHandlers.end(),
            std::bind2nd(
                std::mem_fun_ref(&A_UpdateHandler::Update), 
                &graphic)
        );
    }

private:
    void Init()
    {
        Control *control;

        for(APtrContainer::iterator it = m_APCollection.begin();
            it!= m_APCollection.end(); ++it)
        {
            A &a = *it;
            std::string &name = a.GetName();
            control = GetControlByName(name);
            if(control)
            {
                const int threshold = a.GetThreshold();
                m_A_UpdateHandlers.push_back(
                A_UpdateHandler(*control, threshold));
            }
        }
    }
      
 
       Control *GetControlByName(std::string);
       Graphic &GetGraphic() const;
...
private:
       APtrContainer m_APCollection;
       A_UpdateHandlerContainer m_A_UpdateHandlers;    
}; 

The first thing we notice is that design constraints imposed by the standard during the refactor have forced me to separate the processing of class A objects into an initialisation phase and an update phase. The potentially expensive call to GetControlByName is only done once per object in the initialisation phase as is the check to see if it returns a NULL value. Additionally, if the control indeed is NULL nothing gets added to the handler container. In the worst case, if no controls are found the update function will do nothing! Finally the update function in the handler that does the actual work is succinct and to the point, only expressing the minimum it needs to in order to get the job done. Everything required prior to this call has been handled already and is either passed in or cached where appropriate

void A_UpdateHandler::Update(Graphic *graphic) const
{
       bool value = m_Control.GetCurrentValue() > m_Threshold;
       graphic->doSomething(value);
}

All of these things have improved the code in terms of legibility, ease of maintenance and run-time efficiency, what more do you want!?


A couple of finer points are worth noting here before we end the last part in this series. std::bind2nd is obviously a templated function. The compiler implicitly deducts what types to use to instantiate the function using the types of the parameters. However, std::bind2nd defines the type of the second parameter as a reference type to this type. For this reason we must pass in a pointer to the Graphic object since references to references are illegal in C++ and your local friendly compiler will tell you as much if you attempt it! Also, when using std::mem_fun_ref in combination with std::bind2nd like this the member function must be const as std::bind2nd (and std::bind1st for that matter) don’t allow the use of non-const adaptors as parameters. In our case of using a wrapper class, which acts as a kind of functor with a constant state that we don’t need to change, this is not an issue, then again, there’s always that lovely keyword mutable.

C++ : In a bind with function objects part III

Given this constraint I needed to write a new member function for class A that did the work, at the time (luckily for me as it turned out) this wasn’t an option so I thought that this sounded like a job for a wrapper class!

class A_UpdateHandler
{
public:
    A_UpdateHandler(Control &control,  const int threshold)
        :      m_Control(control)
        ,      m_Threshold(threshold)
    {
    }

    void Update(Graphic *graphic) const 
            // want to pass this in as it doesn’t make                          
            // sense for all the handler objects to 
            // store the same pointer
    {
        bool value = m_Control.GetCurrentValue() > m_Threshold;
        graphic->doSomething(value);
    }

private:
    Control &m_Control;
    const int m_Threshold;
};

typedef std::vector<A_UpdateHandler> 
    A_UpdateHandlerContainer;

Next I needed to create a collection of these handlers and initialise them. So a couple of (private) additions to class B did the trick.

class B
{
    …
    private:
    …
    void Init()
    {
        // Note: using a for-loop here to illustrate the current 
        // point more clearly, I’ll leave refactoring to a pref-
        // erable implementation using for_each as an exercise  
        // for the reader! Clue: try using std::transform with 
        // a back_inserter.
        // When I first came across this problem an Init member 
        // already existed in the real version of “class B”  
        // that iterated through the collection anyway,
        // perhaps I should go back and refactor that too…

        Control *control;

        for(APtrContainer::iterator it = m_APCollection.begin();
            it!= m_APCollection.end(); ++it)
        {
            A &a = **it;
            std::string &name = a.GetName();
            control = GetControlByName(name);
            if(control)
            {
                const int threshold = a.GetThreshold();
                m_A_UpdateHandlers.push_back(
                    A_UpdateHandler(*control, threshold));
            }
        }
    }
    …
    private:
    A_UpdateHandlerContainer m_A_UpdateHandlers;
};

Now class B’s update function can now be written using a call to std::for_each…

void B::Update()
{
    std::for_each(
        m_A_UpdateHandlers.begin(),
        m_A_UpdateHandlers.end(),
        std::mem_fun_ref(&A_UpdateHandler::Update)); 
        // we have a problem!
}

Another problem!! Oh no, but before we explore what it is an how I overcame it to get to the end of this refactor (finally!!) I’d like to point out the use of std::mem_fun_ref above. It does the same as std::mem_fun but works with a collection of references instead of pointers.

template<class Result, class Type>
   std::mem_fun_ref_t<Result, Type> 
      std::mem_fun_ref(Result (Type::*pm)());

So, the problem with calling A_UpdateHandler::Update in this way is that there’s no way of passing the Graphic * parameter that we need - or is there? Enter that old favourite, std::bind2nd and the final update function looks like this:

void B::Update()
{
    Graphic &graphic = GetGraphic();

    std::for_each(
        m_A_UpdateHandlers.begin(),
        m_A_UpdateHandlers.end(),
        std::bind2nd(
            std::mem_fun_ref(&A_UpdateHandler::Update), 
            &graphic)
    );
}

Which in terms of sheer aethestetics looks a lot prettier than our original for-loop! This isn’t mere triviality, in my experience elegant looking code usually indicates a more elegantly designed solution under the hood. There are several reasons why this is the case here.


... and I'll go through it with you in Part IV :)