Unary Function
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); }
};
Journey
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 ?!)
Extending State Pattern - Example Code
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.
Extending State Pattern with Secondary Transition Stimuli
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);
}
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.
To use pthreads with C++ :
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;
};
The Monitor pattern vs the Monitor programming construct
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
}