Chaos Theory

In a couple of ways this article represents a return to my past: both to C++ and to the "Chaos Theory" theme. For the last couple of years my professional interest has been diverted from C++ to other areas (specifically to Java, J2EE and development methods). As a result I've accumulated a backlog of C++ related material waiting to be read. In particular, I've finally found time to read "Modern C++ Design" which demonstrates the ability to use the language to do things at compile time. Other books (like "Generative Programming") that I've read during my diversion have also used these ideas and there are libraries (boost has a fine example) to support these uses. But I wanted to do more than read and admire these novel ideas. I wanted to try them out - but I was in search of a problem.

The problem I chose is one that I wrote about once before - in the "first" article in a series of articles on "Chaos Theory".This was a long time ago, I can't remember why but the rest of the series never materialised (in fact I can't find a copy of thefirst article either - but I think it was published in C Vu about ten years ago.)

Chaos theory is a branch of mathematics that was developed in the nineteenth century by Poincaré in an attempt to solve the problem "Is the Solar System stable?" Although he failed to solve the problem he made a sufficient dent to be awarded a significant prize for this work. Towards the end of the last millennium work on the stability of mathematical systems grew in importance with theincreasing use of computers to do numerical modelling.

The types of mathematical model to which chaos theory applies are those that develop over time and whose current state dependsupon the past. It gets interesting when this change is complicated enough that exact solution is infeasible and numerical modelling is the only approach to getting results. What the mathematicians showed was that even when it isn't possible to write down an exact description of the evolution of the model it is still possible to make useful predictions about the type of behaviour.

This sounded fun, so I decided to try it for myself and started writing a series of articles for C Vu. At least I think I did - I never wrote the second article and I can't find the first! The first article introduced an easy to understand non-linear system and demonstrated the application of these predictions. The system in question takes a pair of numbers and generates a new pair of numbers - and what chaos theory predicts is that one of three things will happen:

(In the particular system I'm writing about the first of these is extremely implausible and it turns out that case 3 is what happens.) My thoughts turned to finding these fixed values at compile time.

/*
  "This sentence has eight vowels and
  twenty consonants"

  The above sentence is false because the
  numbers eight and twenty are arbitary
  (and wrong). But we can create a
  sequence of number pairs (Vn, Cn) by
  substituting the numbers into a sentence
  of this form and counting the vowels and
  consonants to get the next pair of
  numbers.

  Continuing to substitute these values
  back into the sentence then one of three
  things must happen:
  1/ The series of pairs (Vn, Cn)
     diverges
  2/ The series of pairs (Vn, Cn)
     loops though a sequence of values
  3/ The series of pairs (Vn, Cn)
     converges to constant values

  The following program executes this
  algorithm *at compile time* to find
  values of (Vn, Cn) which make the
  sentence true and outputs the
  result.
*/

#include <string>
#include <iostream>
namespace {

/*
The first issue to address is that it
isn't possible to count vowels or
consonants in a string at compile
time. Compile time processing is
limited to creating types and
constant integral expressions. There
are two approaches to this that
occur to me: create a type for each
character and represent a sentence
as a typelist or break the sentence
into subsentences representing the
fixed and variable portions and
represent these as types. While
the former is clearly a lot more
general it involves more work and
it is the latter approach to the
problem that I adopted.
So for the variable parts I have:
*/

template<int count>
struct number_as_subsentence;

/*
OK, we'll have to define some
specialisations for this before we can
use it, but this is a useful placeholder
for the full sentence template.
*/

template<int vowels, int consonants>
struct sentence {
  enum {
    no_of_vowels = 11
      + number_as_subsentence<vowels>::no_of_vowels
      + number_as_subsentence<consonants>::no_of_vowels,
    no_of_consonants = 23
      + number_as_subsentence<vowels>::no_of_consonants
      + number_as_subsentence<consonants>::no_of_consonants,
    is_true = no_of_vowels == vowels
      && no_of_consonants == consonants
  };

  static std::string as_string() {
    static const std::string
          beginning("This sentence has ");
    static const std::string
          middle(" vowels and ");
    static const std::string
          end(" consonants!");
    return beginning
      + number_as_subsentence<vowels>::as_string()
      + middle
      + number_as_subsentence<consonants>::as_string()
      + end;
  }
};

/*
This template provides a compile time
mechanism to take a number of vowels
and a number of consonants and determine
the effect of placing them into our
template for a sentence. It will also
construct the corresponding sentence
for us.

What's next? In the original
program there was a loop to keep
trying the sequence of sentences
until we find one that is true. But
that is another thing that we cannot
do at compile time: we can't do
iteration, we have to rework the
algorithm as recursion:
*/

template<int vowels,
         int consonants,
         bool finished = false>
struct calculate_sentence
       : private sentence<vowels,
                          consonants> {
  typedef typename calculate_sentence<
          calculate_sentence::no_of_vowels,
          calculate_sentence::no_of_consonants,
          calculate_sentence::is_true>::result result;
};

/*
This keeps trying new sentences all
right, but we need to end the recursion
(which is what the third parameter is
for). Interestingly one cannot use a
"metaprogramming if_" (like that in the
boost library) here because both the true
and false conditions get instantiated.
With the current approach we just need a
specialisation of calculate_sentence as
follows:
*/

template<int vowels, int consonants>
struct calculate_sentence<vowels,
                          consonants, true> {
  typedef sentence<vowels, consonants> result;
};

/*
That is really all the interesting bits
of the program done. The templates for
describing the numbers are tediously
repetitive - but there is a useful preprocessor
to handle that:
*/

#define NUMBER_AS_SUBSENTENCE(number,\
                      text, vowels, consonants)\
  template<>\
  struct number_as_subsentence<number> {\
    static std::string as_string() {\
      return text;\
    }\
\
    enum {\
      no_of_vowels = vowels,\
      no_of_consonants = consonants\
    };\
  }

  NUMBER_AS_SUBSENTENCE(0,"zero",2,2);
  NUMBER_AS_SUBSENTENCE(1,"one",2,1);
  NUMBER_AS_SUBSENTENCE(2,"two",1,2);
  NUMBER_AS_SUBSENTENCE(3,"three",2,3);
  ...
  NUMBER_AS_SUBSENTENCE(48,"forty eight",3,7);
  NUMBER_AS_SUBSENTENCE(49,"forty nine",3,6);
  NUMBER_AS_SUBSENTENCE(50,"fifty",1,4);
  #undef NUMBER_AS_SUBSENTENCE
}

/*
To run the program we only need
instantiate the template and output the
result...
*/

int main() {
  std::cout << calculate_sentence<8, 20>
                  ::result::as_string()
            << std::endl;
}

The full program is available on my website at: http://www.octopull.demon.co.uk/C++/ThisSentence/