enCODE

I was debugging a piece of code and hit that all-too-common situation again where though I could fix the problem but could not understand why compiler generated that particular error message from boost::bind library. So just out of curiosity, I decided to understand boost::bind implementation. Googled for it and searched stackoverflow without any real answer and decided to trace through the code for a simple example.

Lets take this example :

class MyArg
{
    public:
        explicit MyArg(int i) : i_(i) {}
        int get_i() const
        {
            return i_;
        }
    private:
        int i_;
};

void f(MyArg a, MyArg b)
{
    cout << "a = " << a.get_i() << " b = " << b.get_i() << endl;
}

int main()
{
    MyArg obj_1(11), obj_2(22);
    bind(f, _1, obj_2)(obj_1);
    return 0;
}

Now check the code that is being used for this particular example with g++ 4.3.0 on linux. I have removed everything else other than the code required for the above example including all the portability features. I am sure I might be missing a lot of the tricks and optimizations by pruning it this way, but still it gave some insights that may help me debug my programs in the future. Do not include boost::bind to run the following piece of code, as I have not changed any of the names, but only got them out of boost namespace.

///placeholders
template<class T>
struct is_placeholder
{
    enum _vt { value = 0 };
};

template<int I>
struct arg
{
    arg(){}
    template<class T>
    arg ( T const& )
    {
        typedef char T_must_be_placeholder[ I == is_placeholder<T>::value ? 1: -1 ];
    }
};

template<int I>
struct is_placeholder< arg<I> >
{
    enum _vt { value = I } ;
};

template<int I>
bool operator==( arg<I> const&, arg<I> const&)
{
    return true;
}

template<int I>
struct is_placeholder< arg<I>(*)() >
{
    enum _vt { value = I } ;
};

///value
template<class T>
class value
  {
  public:

      value(T const & t): t_(t) {}

      T & get() { return t_; }
      T const & get() const { return t_; }

      bool operator==(value const & rhs) const
      {
          return t_ == rhs.t_;
      }

  private:

      T t_;
  };

////storage
template<class A1>
struct storage1
{
    explicit storage1(A1 a1):a1_(a1) {}
    A1 a1_;
};

template<class A1, class A2>
struct storage2: public storage1<A1>
{
    typedef storage1<A1> inherited;

    storage2( A1 a1, A2 a2 ): storage1<A1>( a1 ), a2_( a2 ) {}

    A2 a2_;
}; 

///list1
template< class A1 >
class list1: private storage1< A1 >
{
    private:

        typedef storage1< A1 > base_type;

    public:

        explicit list1( A1 a1 ): base_type( a1 ) {}

        A1 operator[] (arg<1>) const
        {
            return base_type::a1_;
        }

        A1 operator[] (arg<1> (*) ()) const
        {
            return base_type::a1_;
        }

        template<class T> T & operator[] ( value<T> & v ) const
        {
            return v.get();
        }

};

// unwrap
template<class F> struct unwrapper
{
    static inline F & unwrap( F & f, long )
    {
        return f;
    }
};

//type
template<class T>
struct type{};

//list2
template< class A1, class A2 > class list2: private storage2< A1, A2 >
{
    private:

        typedef storage2< A1, A2 > base_type;

    public:

        list2( A1 a1, A2 a2 ): base_type( a1, a2 ) {}

        template<class F, class A> void operator()(type<void>, F & f, A & a, int)
        {
            unwrapper<F>::unwrap(f, 0)(a[base_type::a1_], a[base_type::a2_]);
        }

};

//result_traits
template<class R, class F> struct result_traits
{
    typedef R type;
};

//bind_t
template<class R, class F, class L>
class bind_t
{
    public:

        typedef bind_t this_type;

        bind_t(F f, L const & l): f_(f), l_(l) {}

        typedef typename result_traits<R, F>::type result_type;

        template<class A1>
            result_type operator()(A1 & a1)
            {
                list1<A1 &> a(a1);
                return l_(type<result_type>(), f_, a, 0);
            }
    private:
        F f_;
        L l_;

};

//add_value
template < class T, int I>
struct add_value_2
{
    typedef arg<I> type;
};

template<class T>
struct add_value_2<T, 0>
{
    typedef value<T> type;
};

template<class T>
struct add_value
{
    typedef typename add_value_2<T, is_placeholder< T >::value >::type type;
};

template<class A1, class A2>
struct list_av_2
{
    typedef typename add_value<A1>::type B1;
    typedef typename add_value<A2>::type B2;
    typedef list2<B1, B2> type;
};

template<class R, class B1, class B2, class A1, class A2>
bind_t<R, R (*) (B1, B2), typename list_av_2<A1, A2>::type>
bind( R (*f) (B1, B2), A1 a1, A2 a2)
{
    typedef R (*F) (B1, B2);
    typedef typename list_av_2<A1, A2>::type list_type;
    return bind_t<R, F, list_type> (f, list_type(a1, a2));
}

static arg<1> _1;

class MyArg
{
    public:
        explicit MyArg(int i) : i_(i) {}
        int get_i() const
        {
            return i_;
        }
    private:
        int i_;
};

void f(MyArg a, MyArg b)
{
    cout << "a = " << a.get_i() << " b = " << b.get_i() << endl;
}

int main()
{
    MyArg obj_1(11), obj_2(22);
    bind(f, _1, obj_2)(obj_1);
    return 0;
}

Explanation of the code above :

1. In bind you use placeholders for parameters to be supplied later. Placeholders are really variables in global namespace of type arg<T> where T is integral type giving you the position of the actual argument to be passed.

2. So as seen above bind is a templated function returning a bind_t instance.

3. But before bind returns bind_t instance, list_av_2 lets you create a list_type.

4. To get the list_type, which is of type list2<B1, B2>, list_av_2 derives B1 and B2 from original argument types A1 and A2. In the example A1 is arg<1> and A2 is MyArg.

5. list_av_2 uses struct add_value to derive B1 and B2. B1 remains arg<1> but B2 becomes value<MyArg>

6. arg_value uses add_value_2<T, I> where I is the integral template parameter of arg<I>.

7. To get the integer template parameter of arg<I>, arg_value_2 uses is_placeholder<T>::value. is_placeholder<T> is partially specialized for is_placeholder<arg<I> >. The partial specialization of is_placeholder<T> for arg<I> would assign I to is_placeholder<T>::value, otherwise for any other type is_placeholder<T>::value will just be 0.
Now from step 3 is_placeholder<A1>::value will be 1 and is_placeholder<A2>::value will be 0.

8. By the way, is_placeholder is also used in the copy constructor of arg<I> :

typedef char
  T_must_be_placeholder[ I == is_placeholder<T>::value ? 1: -1 ];

The above statement makes sure that arg<I> can be copy constructed from another arg<I> of exactly the same type and with the same value of I; otherwise you get mysterious eror message like:
“error: creating array with negative size (‘-0×000000001’)”.

9. Now from 6 in add_value, add_value_2 is used with add_value_2<T, 1> for A1 which is arg<1> and add_value_2<T, 0> for A2 which is MyArg, respectively. add_value_2<T, 0> is partially specialized so that add_value_2<T,0>::type becomes value<T>, while add_value_2<T,1>::type remains arg<1>.

10. To return back to step 3, we get list_type which is list2< arg<1>, value<MyArg> >. To instantiate bind_t, a list2< arg<1>, value<MyArg> > instance is created with a1 and a2 where a1 is _1 and a2 is obj_2.

11. list2 is inherited from storage2<A1, A2>. While there was not anything interesting in list2 constructor, we must check storage2<A1, A2>. storage2<A1, A2> is inherited from storage1<A1>. While constructing storage2<A1, A2> stores a2 a member variable but passes a1 to storage1<A>. bind/storage.hpp follows the same pattern with any number of arguments. So storage3<A1, A2, A3> is inherited from storage2<A1, A2> and stores a3 as a member variable while passing on a1 and a2 to storage2. This way the order of argument evaluation could be kept fixed. By the way, we have ommited partial specialization of storage for arg<I> and arg<I>(*).

12. At last we create an instance of type :

bind_t<void, void(*)(MyArg, MyArg), list2< arg<1>, value<MyArg> >

to be returned back to bind caller.

13. Now comes the second part of invoking the binder with obj_1 as an argument. This will naturally invoke bind_t::operator()() which is being passed actual argument obj_1. bind_t<R, F, L>::operator()(A1) stores the parameter in list1<A1&> which as we have seen above, let storage1<A1> store the object.

14. Next it invokes, list2<arg<1>, value<MyArg> >::operator()() with stored function pointer, and the list1<MyArg&>. In the above code we kept only the function specialization for type<void>. Here the most interesting part involves calling list1<MyArg&> subscript operator list1<MyArg&>::operator[] with a1 and a2 from base_type or storage2.

15. So we go back to check the subscript operator implementation of list1 which is really an overloaded implementation where:
— If the paramter is of type arg<1> then you get the value stored in list1 which is list1::base_type::a1_.
— But if the parameter is of type value<T>, v.get() is returned.

Now when we call a[base_type::a1_], base_type::a1_ is really _1 of type arg<1>, so the subscript operator returns the value stored in list1 which we just stored in step 13 when we instantiated list1 with the real argument passed to operator()().
On the other hand a[base_type::a2_] is of type value<MyArg> so that returns the object stored in value<T>, which is the one we passed when bind was called.

admin C++ bind, boost, c++

The short answer is : use boost::function.
But bind returns a binder that is of unspecified type by definition.
So what would be the simplest possible way to store something without knowing its type ? I could come up with the following implementation. This is not how boost::function works, this is just how I can hide the type.

using std::cout;
using std::endl;
using std::string;
using boost::bind;

template<typename Ret, typename Arg>
class Invoker
{
   public:
      virtual Ret operator()(Arg a) = 0;
      virtual ~Invoker() {}
};

template<typename Ret, typename Arg, typename T>
class ConcreteInvoker : public Invoker<Ret, Arg>
{
   public:
      explicit ConcreteInvoker(T cb) : pcb_(cb)
     {
     }

      Ret operator()(Arg a)
     {
         return pcb_(a);
      }
   private:
      T pcb_;
};

template<typename Ret, typename Arg, typename T>
Invoker<Ret, Arg>*
get_invoker(const T& ob)
{
   return new ConcreteInvoker<Ret, Arg, T>(ob);
}

You need to use get_invoker() to get an Invoker that can be stored like the following :

class SomeClass
{
    public:
        explicit SomeClass(int i):i_(i){}

        int some_func(const string& s) const
        {
            cout << "In SomeClass::some_func with : "  << s << endl;
            return i_;
        }
    private:
        int i_;
};

void free_func(int i)
{
    cout << "In free function with " << i << "." << endl;
}

int main()
{
    SomeClass some_ob(22);
    Invoker<int, string> *inv_1 =
          get_invoker<int, string>(bind(&SomeClass::some_func, some_ob, _1));
    int ret = (*inv_1)("Hello.");
    cout <<  "ret from inv_1 :" << ret << endl;

    Invoker<void, int> *inv_2 = get_invoker<void, int>(bind(free_func, _1));
    (*inv_2)(int());
    return 0;
}

Well it was quite simple really. With get_invoker() compiler deduces the real type so you dont need to bother about it. Then the type gets hidden in the ConcreteInvoker while at the usage level you just deal with abstract base class Invoker which does not require the actual type !

admin C++

The reason why some parts of STL never got really popular was down to the fact that some of those functional algorithms were really difficult to use. Truth is, to remember all the function names like bind1st, bind2nd and mem_fun and mem_fun_ref and then to know how are you are supposed to combine them in different ways to make them work in some cases was definitely a pain. Boost::bind rescued us from all that, probably bind is the single greatest thing that happened to C++ after vector. I am sure with C++0x, bind is ‘bound’ to get more popular.

Like everything else some idioms of how we use bind is more interesting than others and there are plenty of anti-idioms(anti-patterns) possible with bind as well, where you can obfuscate C++ out of recognition. I thought it would be a good idea to collect all the uses (and probably abuses as well) of bind somewhere; it really needs a wiki page rather than a blog post, but for the time being I want to start this activity here anyway and then I may update this page from time to time. By the way, though lambda would be the ultimate candidate to create useful unnamed functions, bind does the job pretty alright in many cases, and it is a smaller leap for the likes of me who are not deep into functional programming (yet).

1. To convert member function to a function object: This is a replacement for mem_fun. This is required for member functions to be used with STL algorithms.
If I have class Widget like this:

class Widget
{
   public:
     ...
     void paint();
     ...
};

So when I need to call paint on all my widgets, I can do the following:

std::for_each(widgets.begin(), widgets.end(), bind(&Widget::paint, _1));

2. Adapting functions by substituting arguments: This is the general case of bind1st and bind2nd. So in the above case if paint() takes a target view to draw on, we may have to do something like the following:

class Widget
{
   public:
     ...
     void paint(TargetView target);
     ...
};

std::for_each(widgets.begin(), widgets.end(),
                     bind(&Widget::paint, _1, target));
...

More general cases are mentioned here.

3. Function composition: You can compose multiple functions to create new functionality in place:

std::for_each(m_assets.begin(), m_assets.end(),
             bind(&PubManager::show_publisher, pubmanager,
             bind(&MediaAsset::get_id, _1)));

Evidently the classes used above looks like:

class PubManager
{
   public:
   string show_publisher(int id)
   {
        ...
   }
};

class MediaAsset
{
   public:
      int get_id()
      {
         ...
      }
};

So the m_asset instance from the container is actually passed to the inner bind, which generates an id. This id generated by the inner bind is used by the PubManager::show_publisher() method specified in the outer bound to show the publisher.

4. Composition with STL algorithm : For find_if type of algorithms such composition with operators are quite useful, for example :

vector::iterator it = std::find_if(m_assets.begin(), m_assets.end(),
                       bind(&PubManager::get_publisher, pubmanager,
                               bind(&MediaAsset::get_id, _1)) == "publisher-333");
...

Some other examples from boost site are quite useful as well, like this one:

std::remove_if( first, last, !bind( &X::visible, _1 ) );

With operator overloading this kind of compositions can really compete with lambda, for example check the example below:

class SomeClass
{
   public:
     explicit SomeClass(int i = 0) : _id(i)
     {
     }
     int get_id()
     {
        return _id;
     }
     private:
        int _id;
};

int main()
{
  vector<SomeClass*> obs;
  obs.push_back(new SomeClass(4));
  obs.push_back(new SomeClass(7));
  obs.push_back(new SomeClass(12));
  obs.push_back(new SomeClass(10));

  int count = std::count_if(
      obs.begin(),
      obs.end(),
      bind(&SomeClass::get_id , _1) > 5
      && bind(&SomeClass::get_id, _1) <= 10);

  cout << count << endl;
  return 0;
}

Such examples without operator overloading are explained here : http://www.informit.com/articles/article.aspx?p=412354. Boost::bind started supporting operator overloading boost 1.33 and it makes those constructions simpler and more readable.

5. Composition with member variables : You can create composite functions using member variables and operators on the fly.  This is very useful when used within member functions and here are some examples collected from from boost documentation:

std::find_if( first, last, bind( &X::name, _1 ) == "Peter" );
std::find_if( first, last, bind( &X::name, _1 ) == "Peter"
               || bind( &X::name, _1 ) == "Paul" );
bind( &X::name, _1 ) == _2;
std::sort( first, last, bind( &X::name, _1 ) < bind( &X::name, _2 ) );
// sort by name

6. Bind with std::map: At times digging values and keys out of maps for infrequest special case uses gets quite complicated … unless you have helpers with bind. For example :

using std::cout;
using std::endl;
using std::vector;
using std::map;
using std::string;
using boost::bind;

template<typename K, typename V>
void get_keys(map<K, V>& m, vector<K>& keys)
{
   std::for_each(m.begin(), m.end(), bind(&vector<K>::push_back, boost::ref(keys),
                       bind(&map<K, V>::value_type::first, _1)));
}

template<typename K, typename V>
void get_vals(map<K, V>& m, vector<V>& vals)
{
   std::for_each(m.begin(), m.end(), bind(&vector<V>::push_back,
                       boost::ref(vals), bind(&map<K, V>::value_type::second, _1)));
}

int main()
{
   map<string, int> m;
   m["one"] = 1;
   m["two"] = 2;
   m["three"] = 3;

   vector<string> keys;
   get_keys(m, keys);
   std::copy(keys.begin(), keys.end(), std::ostream_iterator<string>(cout, "\n"));

   vector<int> vals;
   get_vals(m, vals);
   std::copy(vals.begin(), vals.end(), std::ostream_iterator<int>(cout, "\n"));

   return 0;
}

7. Compare functions : As it should be clear by now, bind can also be used to create the compare function to be provided to associative containers or STL sorting algorithms. For an example, do you remember Item 20 from Effect STL by Scott Meyers.  It was an essay about how if you have an associative container container of the form

set<string*> ssp;

The container is going to be sorted by the value of the pointer and not the string, as it is really a shorthand for

 set<string*, less<string*>, allocator<string*> > ssp;

. Later on he showed how we can have a DereferenceLess functionobject to be passed to such containers so that they are ordered correctly:

struct DereferenceLess
{
   template<typename PtrType>
   bool operator()(PtrType pT1, PtrType pT2) const
   {
       return *pT1 < *pT2;
   }
};

Now in the same article he also needed to print the content of such a set to stdout for which he created another function object called Dereference :

struct Dereference
{
   template <typename = T>
   const T& operator()(const T* ptr) const
   {
        return *ptr;
   }
};

transform(ssp.begin(), ssp.end(),
   ostream_iterator<string>(cout, "\n",
   Dereference());

The point of the above digression is to show that with such requirements you will need different function objects for different tasks which you can achieve using a single Dereference function object when you use bind. For example :

template<typename T>
struct Dereference : std::unary_function<T*, T>
{
        const T& operator()(const T* ptr) const
        {
            return *ptr;
        }
};
int main()
{

    function<bool(string*, string*)> Peq(bind( std::less<string>(),
                                bind(Dereference<string>(), _1),
                                bind(Dereference<string>(), _2)
                               ));
    set<string*, function<bool(string*, string*)> > ssp2(Peq);
    ssp2.insert(new string("Zebra"));
    ssp2.insert(new string("Anteater"));
    ssp2.insert(new string("Wombat"));
    ssp2.insert(new string("Dog"));
    ssp2.insert(new string("Lemur"));
    ssp2.insert(new string("Penguin"));
    ssp2.insert(new string("Armadillo"));
    std::transform(ssp2.begin(), ssp2.end(),
            std::ostream_iterator<string>(cout, "\n"),
            Dereference<string>());
    return 0;
}

By the way, one difference between Dereference in the above piece of code with the earlier example is how this one needs a template parameter while the earlier one does not. To be honest with C++ we should not have to specify type in these situations and the earlier Dereference is actually utilizing the full power of C++. But it is not only about C++ it is also important to be compatible with STL. To be a really useful generic function object with other algorithms it is better to make a function object adaptable, this will save us more effort later. You make something adaptable by inheriting unary_function, and that’s what we did above.

8. Callbacks  with boost::function : Though I am not sure where you should draw the line before you make it too complicated and if my use of bind in the example is very idiomatic (perhaps in an unnamed lambda function might be right candidate).

struct Media
{
   enum type { VIDEO_STREAM = 1, AUDIO_STREAM };

   static bool is_video(type media_type)
   {
      return media_type == Media::VIDEO_STREAM;
   }

   static bool is_audio(type media_type)
   {
      return media_type == Media::AUDIO_STREAM;
   }

};

class Engine
{
   public:
      typedef boost::function<bool(Media::type media_type, string data)> callback_t;

      void register_callback(callback_t callback)
      {
         m_callback = callback;
      }

      void media_ready(Media::type media_type)
      {
         m_callback(media_type, " >> Media Data << ");
      }

private:
   callback_t m_callback;
};

class Player
{
   public:

      bool play_audio(string audio_data)
      {
         cout << "Player1 is playing audio. " << endl;
         cout << audio_data << endl;
         cout << "Player1 has finished playing audio." << endl;
         return true;
      }

      bool play_video(string video_data)
      {
         cout << "Player1 is playing video. " << endl;
         cout << video_data << endl;
         cout << "Player1 has finished playing video." << endl;
         return true;
      }

};

int main()
{
   Player player;
   Engine engine;

   engine.register_callback(
            bind(&Media::is_video, _1) &&
            bind(&Player::play_video, player, _2) ||
            bind(&Player::play_audio, player, _2));
   cout << "Video Ready:" << endl;
   engine.media_ready(Media::AUDIO_STREAM);
   cout << "Audio Ready:" << endl;
   engine.media_ready(Media::VIDEO_STREAM);

   return 0;
}

References:
It is also my intention to collect links to good articles and blog posts.
http://www.boost.org/doc/libs/1_41_0/libs/bind/bind.html
http://www.informit.com/articles/article.aspx?p=412354 : This is from the boost book I think.
http://mostlycoding.blogspot.com/ : Check it to see when you may need boost::protect.
http://accu.org/index.php/journals/1397

admin C++ bind, c++

Is there anything called bottom-up learning? This is an example.  Go through some source code – try to understand whats going on – ask questions.

#include <functional>

struct Check_state: public std::unary_function<int, bool>
{
explicit Check_state(int state = 0): m_state(state){}

bool operator()(int x) const
{
return x == m_state;
}

private:
int m_state;

};

This piece of code shows a class that can be instantiated to create functors or function objects, as it overrides operaor(); the thing to notice is the fact that we are derving it from unary_function<>, lets ask questions and investigate the matter.

Why does stl have unary_function<Arg, Result> and why did we derive from it?
Well, unary_function<Arg, Result> is not just a unary function. It is the base class for an adaptable unary function. In this case we derived the functor from unary_function<Arg, Result> to make Check_state functor an adaptable unary function. By the way this particular example is really an example of adaptable predicate. ( A predicate is a boolean valued unary function i.e. a unary function that returns a bool – the truth or falsehood of some state or condition ).

Why do I need an adaptable unary function ?
As the name suggests, an adaptable unary function can be used by adaptors.  Now that Check_state is an adaptable unary function, it can be used by adaptors.

What is the use of adaptors ?
An adaptor or more specifically a function object adaptor can be used to extend or specialize a function object. For example a negator is an adaptor that reverses the truth value of a predicate. The advantage of using such an adaptor is that you do not have to define a new class when you need a function object to do the reverse of your current, already defined function object does. So for the purpose of our example we have the adaptor unary_negator<T>, for the above Check_state class, we can have something like :

Check_state check_state(5); // instantiating Check_state to get a function object check_state, check_state(num) will be true whenever num is equal to 5.

std::unary_negate<Check_state> ncheck_state(state); //instantiating std::unary_negate<Check_state> to get the negator function object of check_state.

Here every time check_state(num) says true, ncheck_state(num) says false.

We rarely instantiate std::unary_negate<T> in real world, we always have a corresponding convenient function, in this case not1() – it’s just that we take advantage of the fact that normally you do not have to mention the type for a template function, compiler takes of it.  gcc implementation of not1 looks like this :

template <class _Predicate>
inline unary_negate<_Predicate>     not1(const _Predicate& __pred)
{
return unary_negate<_Predicate>(__pred);
}

Okay, now back to the starting point, so why do we need to have an adaptable unary function to be able to use adaptors ?
This is a ‘white box’ type question. We already know that we can use unary adaptors only with adaptable unary functions, and we can make a functor class adaptable by deriving it from the corresponding adaptable base class. These are the rules, but we have not yet explained why we need these rules. Lets check the implementation of unary_negate<T> :

template <class _Predicate>
class unary_negate    : public unary_function<typename _Predicate::argument_type, bool>
{
protected:
_Predicate _M_pred;
public:
explicit   unary_negate(const _Predicate& __x) : _M_pred(__x) {}

bool  operator()(const typename _Predicate::argument_type& __x) const
{
return !_M_pred(__x);
}
};

It is pretty simple, we keep an instance of _Predicate as _M_pred and do !_M_pred(__x) whenever the function object is invoked with __x. The only problem was to know the type of __x which we get from _Predicate::argument_type. Now this argument_type is actually a typedef defined in unary_function<A, R>. So now if you check the implementation of unary_function<A, R>,  you see that it defines typedefs, argument_type and result_type.  You need these typedefs if you want your functor to be adaptable ; deriving from unary_function<A, R> is just a convenient way of having those typedefs in your class.

template <class _Arg, class _Result>
struct unary_function
{
typedef _Arg argument_type;   ///< @c argument_type is the type of the
///     argument (no surprises here)

typedef _Result result_type;  ///< @c result_type is the return type
};

Okay so is a normal c++ function taking a single argument, a unary function ?
Ofcourse and so is a function pointer taking a single argument. By the way, I think we really need an umbrella term covering all ‘calleables’. Though in some c++ literature ‘function object’ or ‘functor’ has been used as the generic term for all calleables, I think Stroustrup does not think so, he said ” An object of a class with an application operator is called a function-like object, a functor, or simply a function object. ” But to come back to our question : though a normal function or function pointer is a unary function, they are surely not adaptable unary functions as they dont have those typedefs ! We can get an adaptable unary function from a function pointer using the adaptor pointer_to_unary_function<T> or rather the convenient method ptr_fun() ( just like not1() above). Just check the implementation to see whats going on :

template <class _Arg, class _Result>
class pointer_to_unary_function : public unary_function<_Arg, _Result>
{
protected:
_Result (*_M_ptr)(_Arg);
public:
pointer_to_unary_function() {}

explicit
pointer_to_unary_function(_Result (*__x)(_Arg))
: _M_ptr(__x) {}

_Result
operator()(_Arg __x) const
{ return _M_ptr(__x); }
};

admin C++

Agile is interesting because agile is human. One of of the practices that I think should be there in any agile methodology is ‘continuous training’. I abhor most of those corporate training sessions where you learn ‘advanced techniques’ of something, sitting in a classroom, five days in a row, six hours everyday, staring at the white board, trying to hide your yawns. I have reasons to believe that any learning programme should be as agile as any development programme. You learn something, you use your knowledge to solve real world problems, get stuck somewhere, learn some more, in an iterative continuous process.

But unlike projects the learning process never ends, you keep learning, keep exploring newer avenues, keep innovating … ( and get some awareness of some subtler kind of life beneath it all ?!)

admin philosophy

This is an example toy implementation of state pattern extended with secondary transition stimuli. We dicussed in the last post that a context is more than a wrapper here, and thus it provides an interface to states to raise secondary events. As handling of the secondary events would vary from concrete context to concrete context, state is provided with an interface of an abstract context, as shown below:

class AbstractContext
{
    public:

        typedef std::map
            InstanceTable_t;

        virtual ~AbstractContext();
        virtual void
            raiseSecondaryEvent(
                    const SecondaryEvent::SecondaryEvent_t&
                    ) = 0;
        void activateState(const AbstractState::State_t& stateType);

        void onEvent_1();
        void onEvent_2();
        void onEvent_3();

    protected:
        AbstractContext();

        AbstractState* getStateInstance(
                const AbstractState::State_t& type);

        virtual AbstractState*
            createStateInstance(
                    const AbstractState::State_t& type
                    )const = 0;

        AbstractState::State_t getCurrentStateType() const;

    private:
        AbstractState*  state_;
        InstanceTable_t instances_;
};

A concrete context will have an implementation of the transition table mapping (current state, secondary event) -> next state; naturally a simple representation of the table would be an stl::map. Notice that states were instantiated with a factory method createStateInstance(), which is defined in concreteContext and used from AbstractContext::getStateInstance(); to use this on demand instantiation pattern properly we always have to use this accessor function getStateInstance() to get any state instance.

#include <map>
#include "AbstractContext.hpp"

class ConcreteContext : public AbstractContext
{
    public:
        typedef
            std::map,
            AbstractState::State_t> TransitionTable_t;

        ConcreteContext();
        virtual void
            raiseSecondaryEvent(
                    const SecondaryEvent::SecondaryEvent_t& event
                    );

    protected:
        void populateTransitions();
        AbstractState*  createStateInstance
            (const AbstractState::State_t& type) const;

    private:
        TransitionTable_t transitionTable;
};

Abstract state interface is typical. See concreteState classes to check how we are raising secondary events.

class AbstractContext;
class AbstractState
{
    public:
        enum State_t
        {
            State_1 = 1,
            State_2 = 2
        };
        virtual ~AbstractState(){}
        virtual void onEvent_1(AbstractContext* context) = 0;
        virtual void onEvent_2(AbstractContext* context) = 0;
        virtual void onEvent_3(AbstractContext* context) = 0;
        virtual State_t stateType() const = 0;
    protected:
        AbstractState(){}
};

class ConcreteState_1 : public AbstractState
{
    public:
        ConcreteState_1(){}

        virtual void onEvent_1(AbstractContext* context)
        {
            std::cout << "Process primary event-1 in ConcreteState-1";
            std::cout << std::endl;
        }

        virtual void onEvent_2(AbstractContext* context)
        {
            std::cout << "Process primary event-2 in ConcreteState-1";
            std::cout << std::endl;
        }

        virtual void onEvent_3(AbstractContext* context)
        {
            std::cout << "Process primary event-3 in ConcreteState-1";
            std::cout << std::endl;
            context->raiseSecondaryEvent(SecondaryEvent::Trigger_1);
        }

        virtual AbstractState::State_t stateType() const
        {
            return AbstractState::State_1;
        }
};

class ConcreteState_2 : public AbstractState
{
    public:
        ConcreteState_2(){}

        virtual void onEvent_1(AbstractContext* context)
        {
            std::cout << "Process primary event-1 in ConcreteState-2";
            std::cout << std::endl;
        }

        virtual void onEvent_2(AbstractContext* context)
        {
            std::cout << "Process primary event-2 in ConcreteState-2";
            std::cout << std::endl;
        }

        virtual void onEvent_3(AbstractContext* context)
        {
            std::cout << "Process primary event-3 in ConcreteState-2";
            std::cout << std::endl;
            context->raiseSecondaryEvent(SecondaryEvent::Trigger_2);
        }

        virtual AbstractState::State_t stateType() const
        {
            return AbstractState::State_2;
        }
};

Now the cpp definitions for AbstractContext and its concrete derived class -
AbstractContext.cpp :

AbstractContext::AbstractContext() : state_(NULL)
{
}

AbstractContext::~AbstractContext()
{
    InstanceTable_t::iterator it = instances_.begin();
    InstanceTable_t::iterator itEnd = instances_.end();
    while(it != itEnd)
    {
        delete it->second;
        ++it;
    }
    instances_.clear();
}

void AbstractContext::onEvent_1()
{
    state_->onEvent_1(this);
}

void AbstractContext::onEvent_2()
{
    state_->onEvent_2(this);
}

void AbstractContext::onEvent_3()
{
    state_->onEvent_3(this);
}

void
AbstractContext::activateState(
        const AbstractState::State_t& stateType)
{
    state_ = getStateInstance(stateType);
    assert(state_ != NULL);
}

AbstractState*
AbstractContext::getStateInstance(const AbstractState::State_t& type)
{
    AbstractState* stateInstance = NULL;
    InstanceTable_t::const_iterator it =
        instances_.find(type);

    if(it != instances_.end())
    {
        stateInstance = it->second;
    }
    else
    {
        stateInstance = createStateInstance(type);
        instances_[type] = stateInstance;
    }
    return stateInstance;
}

AbstractState::State_t AbstractContext::getCurrentStateType() const
{
    assert(state_ != NULL);
    return state_->stateType();
}

ConcreteContext.cpp :

ConcreteContext::ConcreteContext()
{
    populateTransitions();
}

void ConcreteContext::raiseSecondaryEvent(
        const SecondaryEvent::SecondaryEvent_t& event)
{
    TransitionTable_t::iterator it  =
        transitionTable.find(
                std::make_pair(getCurrentStateType(), event));
    if(it != transitionTable.end())
    {
        activateState(it->second);
    }
}

void ConcreteContext::populateTransitions()
{
    transitionTable[std::make_pair(AbstractState::State_1,
            SecondaryEvent::Trigger_1)] = AbstractState::State_2;
    transitionTable[std::make_pair(AbstractState::State_2,
            SecondaryEvent::Trigger_2)] = AbstractState::State_1;
}

AbstractState*
ConcreteContext::createStateInstance(
        const AbstractState::State_t& type) const
{
    AbstractState* state = NULL;
    switch(type)
    {
        case AbstractState::State_1:
            state = new ConcreteState_1();
            break;
        case AbstractState::State_2:
            state = new ConcreteState_2();
            break;
        default:
            assert(false);
            break;
    }

    return state;
}

Now client code would just create a ConcreteContext, activate initial state and expose itself to primary events – that’s it.

admin C++, Design Pattern

State machine in procedural programming and corresponding state pattern in OOP has been there and served us well to implement event driven scenarios for some time now. To be accurate, state machine is an architectural pattern which was there even before OO, while ’state pattern’ is really the OO implementation of State Machine. The intent and benefit are clear for the basic state pattern. The state pattern lets you implement state specific behaviour without cluttering your code with conditionals. State pattern is based on OO principle of delegation to a polymorphic base class – and it is very clean that way ( yes, just like strategy pattern ). A ‘context’-wrapper delegates all requests to the ConcreteState class through an abstract state interface. Naturally, ‘the context’ is also responsible for presenting an interface of the state machine to its client.

Now – the most important question – what does this really solve ?
Well, as GOF stated it succinctly, it “localizes state specific behaviour” – that says it all .
So when you want to modify the behaviour of the system when it is in a particular state, you just have to modify the implementation of that particular concreateState class; your changes are going to be ‘contained’. It is also easier now to add a new state : create a new class for the new state and give flesh to all the abstract methods defined in State interface and have the new state in your context … but unfortunately in this case that is not the end of it, in most implementations you have to change other states as well for transitions to your new state. And this leads us to the next section.

Though state pattern is the perfect solution for a number of problems, a definite weakness of the state pattern is that it does not specify a clean solution to implement state transitions.
About transitions GOF says :
“Either Context or the ConcreteState subclasses can decide which state succeeds another and under what circumstances.”
and
“The State pattern does not specify which participant defines the criteria for state transitions. If the criteria are fixed, then they can be implemented entirely in the Context. It is generally more flexible and appropriate, however, to let the State subclasses themselves specify their successor state and when to make the transition. This requires adding an interface to the Context that lets State objects set the Context’s current state explicitly”.

So GOF’s suggestion is to let subclasses specify transitions and the sample code from GOF looks like this :

class TCPConnection {
 ...
 void ChangeState(TCPState*);
 private:
 TCPState* _state;
 };

Here TCPConnection is the context object which has the state changing interface ChangeState(TCPState*) and TCPState is the state interface. ChangeState() has been implemented as :

void TCPConnection::ChangeState (TCPState* s) {
 _state = s;
 }

TCPConnection::ChangeState() is invoked by TCPState::ChangeState() which looks like :

class TCPState {
 ...
 void ChangeState(TCPConnection*, TCPState*);
 };

void TCPState::ChangeState (TCPConnection* t, TCPState* s) {
 t->ChangeState(s);
 }

Now a concreteState implementation would change the state when necessary as shown below :

void TCPEstablished::Close (TCPConnection* t) {
 // send FIN, receive ACK of FIN
 
 ChangeState(t, TCPListen::Instance());
 }

Here TCPEstablished is a concreteState.

The problem :

The main weakness of the above approach is that there is coupling among states – to quote GOF : ” A disadvantage of decentralization is that one State subclass will have knowledge of at least one other, which introduces implementation dependencies between subclasses.”
Though this is a known problem, in certain scenarios where each state object may represent a complex component from the problem space rather than just a state, this is a huge price to pay .
Let us take an example a GUI state machine that delegates behaviour to subelements according to current user state. Each subelement in our example is complex, has its own model, and may have sub-subelements. Each subelement behaves in a certain way with user events. And some of these events may trigger transitions to other other subelements. The stimuli-subelements-transition map is context dependent and the context may change dynamically.

Now let us check the forces we are dealing with here :

I. It should be easy to add, modify and even delete subelements without modifying other subelements. In a real world development team the responsibility of implementing these subelements may lie with multiple developers, so it could be a real necessity to have minimum possible coupling among them.

II. The stimuli-subelements-transition map is context dependent.

III. Contexts change dynamically.

The solution :
Reactions to events are sub-element specific, and we need sub-elements to be independent of each other. So, a la classic state pattern each subelement must have a concrete derivation with a ‘context’ talking to an abstract ’subelement’ interface. Now, if we let each subelement decide its successor we not only have strong coupling among subelements but we can not also support the requirement of having multiple, dynamically changing contexts. The dirty subelement implementation to support such a scenario with multiple contexts may look something like :

if(context.type == Context::Navigation)
{
ChangeState(Subelement::BreadCrumb);
}
else if (context.type == Context::ShortCut)
{
ChangeState(Subelement::ShortCutMenu);
}

Where the subelement implementation is of course tightly coupled with the context.

So how do we solve this problem ? The essential core of the proposed solution can be stated as : “distribute reactions among subelements but centralize the transition-stimuli map”. The basic problem with traditional state pattern is that the State Transition Table is scattered across all the states. To balance all the forces mentioned above a ‘context’ now may actually have to act its role and take the responsibility of centralizing the State Transition Table, which makes perfect sense because after all a transition table is the characteristic of a ‘context’ not a state! Note that in traditional state pattern a ‘context’ was just a wrapper that delegated everything to current state. So now if you need to change the state transition table, you just need to change your context – states/subelements are not affected by changing the context. This is also very clean since the transition table is in one place and not ‘contaminated with the implementation of the actions’ (I picked this phrase from Robert C Martin, though he came up with a different solution to the same problem).


Implementation :
To implement this design we need to define a protocol between the context and states. This protocol is defined with events and secondary transition stimuli. Events are generated externally and are handled by states, while states generate secondary transition stimuli towards the context upon receiving/processing a ’significant event’. A context defines a transition table that has mapping from [current state, secondary transition stimulus] to [next state]. To check this implementation with our example, subelements process, consume and react internally to most of the user events. A subset of those user events may trigger a transition from one subelement to another. While processing such a user event a subelement generates a secondary transition stimulus towards the context. Note that subelements responsibility ends at generating the secondary stimulus, it does not care about how that may effect a state transition.

A very common question is so how is it different from a straight forward table driven state machine ? Or, why dont we have everything in a table like the pre-OO implementation of state machine where we have a two dimensional table of states, events and function pointers?
Because the designing in terms of ’state’s, where states are decoupled from each other, and where each state reacts to events in an independent fashion is much cleaner design. We needed the current solution because though each state reacts to event and ‘reaction’ is state specific, only some events trigger transitions and transitions are context specific.

I am going to publish a toy example implementation in my next post.

admin Design Pattern

Yes, it was easy – but even before boost there has always been some C++ wrapper. So when you go to check this piece of code wriiten a couple of years ago using pure pthreads you are not always sure if everything is alright with the code.

So here are some interesting and not so interesting information about POSIX threads :

- POSIX 1003.1c deals with threads.

- The current posix threads library in linux is NPTL ( Native POSIX Thread Library). NPTL is 1:1, kernel supported threading library, it uses clone() system call to create a thread and uses the new system call futex() to resolve contention. By the way, futexes are kind of cool and fast because kernel’s involvement is required only when a contended case requires arbitrattion. On a 2.6.x linux kernel to know the latest pthread library you use

$ getconf GNU_LIBPTHREAD_VERSION

I find it interesting that you use opaque objects everywhere in pthreads library; it is a ‘C’ way to implement API constraints(and interedependency) with data hiding – it is pretty clean. For example when you want to set an attribute (setting an attribute is the way to set the stack size, to make it joinable etc) you initialize the attribute separately, set properties on it and then pass it to pthread_create() – pthread_create() is the function to create a new thread.

So it would look like :

pthread_t tid;
int arg = 10;
pthread_attr_t attr;
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
rc = pthread_create(&tid, &attr, startFunction, &arg);
pthread_attr_destroy(&attr);

Whenever we are using C++, we have to remember that startFunction is a c function – hence no namemangling is allowed there. Your C++ compiler would always mangle the name to support overloading etc, so the globally visible name of a function may not be same as the name you declared it with.(Since you can have multiple functions with the same name, C++ compiler creates a unique name by using the signature of the function) Naturally, you cannot use a namemangled function as the callback function for C library. The solution is to use extern “C” linkage declaration – it can be done with global and static functions only.

The next point is to remember that you do not know when a thread is going to be scheduled, so manage your resources with care, for example you can pass an argument to the start routine ( as you can see in the above example) but the passed argument is going to be used by the newly created thread only when it is scheduled, so naturally the parent thread must not try to modify the argument before that !

As soon as you learn to use multiple threads sharing the same address space, using each others data freely, you have to learn to use guards to protect your data as well – it comes with the territory. For example you have the case where you want to implement some kind of transactional sanity in a situation where multiple threads are effectively jumbling up each others data to create a confusion … check the following code :

This could be the main.cpp :

#include "transaction.hpp"

using std::cout;
using std::endl;
using std::terminate;

extern "C"
{
    void* runTransactionA(void* arg)
    {
        Transaction* trans = static_cast<Transaction*>(arg);
        trans->transactAs();
        return 0;
    }

    void* runTransactionB(void* arg)
    {
        Transaction* trans = static_cast<Transaction*>(arg);
        trans->transactBs();
        return 0;
    }
}

int main()
{

    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);

    pthread_t firstHandle, secondHandle;
    Transaction transaction("Transaction");

    int rc;
    rc = pthread_create(&firstHandle, &attr, runTransactionA,
            &transaction);
    if(rc != 0)
    {
        cout << "Error - return code from pthread_create() ";
        cout << rc << endl;
        terminate();
    }
    rc = pthread_create(&secondHandle, &attr, runTransactionB,
            &transaction);
    if(rc != 0)
    {
        cout << "Error - return code from pthread_create() ";
        cout << rc << endl;
        terminate();
    }

    pthread_attr_destroy(&attr);

    void* status = 0;
    rc = pthread_join(firstHandle, &status);
    if(rc != 0)
    {
        cout << "Error - return code from pthread_join() ";
        cout << rc << endl;
        terminate();
    }

    rc = pthread_join(secondHandle, &status);
    if(rc != 0)
    {
        cout << "Error - return code from pthread_join() ";
        cout << rc << endl;
        terminate();
    }

    transaction.displayServerLink();
    pthread_exit(0);

}

Where the Transaction implementation would look like :

#include
#include
#include
#include

#include

class Transaction
{
    public:

    //constructor
    Transaction(std::string name) : m_name(name)
    {
        pthread_mutex_init(&serverMutex, 0);
    }

    //destructor
    ~Transaction()
    {
        pthread_mutex_destroy(&serverMutex);
    }

    void transactAs()
    {
        struct timespec req;
        struct timespec rem;
        req.tv_sec = 0;
        req.tv_nsec = 10000;
        pthread_mutex_lock(&serverMutex);

        serverLink << std::endl;
        serverLink << m_name << " : ";
        for (int step = 0; step < 10; ++step)
        {
            serverLink << "<< step << ">";
            nanosleep(&req, &rem);
        }
        serverLink << " :" << std::endl;

        pthread_mutex_unlock(&serverMutex);
    }

    void transactBs()
    {
        struct timespec req;
        struct timespec rem;
        req.tv_sec = 0;
        req.tv_nsec = 10000;
        pthread_mutex_lock(&serverMutex);

        serverLink << std::endl;
        serverLink << m_name << " : ";
        for (int step = 0; step < 10; ++step)
        {
            serverLink << "<< step << ">";
            nanosleep(&req, &rem);
        }
        serverLink << " :" << std::endl;

        pthread_mutex_unlock(&serverMutex);
    }

    void displayServerLink()
    {
        std::cout << "Current Buffer in ServerLink is";
        std::cout << serverLink.str() << std::endl;
    }

    private:
        std::string m_name;
        std::stringstream serverLink;
        pthread_mutex_t serverMutex;
};

admin C++, Multithreading Multithreading, pthreads

Though, the monitor programming construct is always there to support the monitor pattern, it is important to understand the programming construct separately from the pattern. This is necessary because the pattern can be used with all modern threading libraries even if the ’specific programming language’ being used does not have any specific keyword for that.

Monitor as a programming language construct :

Basically, when supported, ‘monitor’ as a programming language construct is there to hide mutual exclusion. So if a procedure is defined to be a monitor then by definition that piece of code is taken to be a critical region. A critical region is a piece of code which can only be executed by one thread at a time. In case of a monitor the programmer himself does not have to put the critical region inside lock-mutex and unlock-mutex, the programming language would take care of it.

[ But this is not there in C++:

For example java has 'synchronized' keyword for monitors, java virtual machine has corresponding monitorentry and monitorexit opcodes, and when java virtual machine encounters monitorentry it acquires a lock, and similarly it releases the lock when encounters monitorexit - the opcodes are not used for monitor procedures but ultimately jvm works with the same principle of locking and unlocking ]

On the other hand the monitor pattern is something like (mutex for critical section) + (wait) + (notify) – the language that has a monitor-like keyword would have all the facilities but the programming language construct is not necessary to implement the pattern.

In C++, with boost 1.34 – replacing the monitor keyword would be as simple as having a scoped mutex :

#include <boost/thread/mutex.hpp>

boost::mutex someMutex;

void someMethod()

{

       boost::mutex::scoped_lock lock(someMutex);

       // more code

}

 

admin Design Pattern, Multithreading