Freestyling on patterns, idioms and semantics…

Icon

vivid hallucinations for bloodthirsty digital vampires

IoC revisited: from callback to closure!

I have been told to consider the IoC pattern for this series and I decided to explore it because I was not really familiar with this pattern.

Wikipedia defines IoC (Inversion of Control) as an abstract principle that describes an aspect of some software architecture design in which the flow control of a system is inverted in comparison to procedural programming. According to Martin Fowler, the term IoC is at least dated 1988, but, it’s still unclear whether it can be considered a pattern or just an architectural principle.

Although IoC is a generic principle, concrete implementations depend on the semantics in play. Indeed, in the everyday C++ programming, IoC can be found in different forms. Among them:

  • Pointer to functions (callback)
  • Generic Programming: STL algorithms, functors and callable objects
  • Polymorphism and NVI idiom
  • Policy Classes
  • Strategy pattern and std::function
  • Lamba functions and closures

The listed idioms differ each other, but the principle on which they are based is common: to provide a means for customizing an algorithm, improving both software decoupling and code reusability. In particular, the principle focuses on the separation between the code implementation and the execution.

In this essay we will examine different idioms, pointing out the properties that each one has in common with the IoC principle. In doing so, we will put emphasis on some possible implementations with respect to the C/C++ and the upcoming C++0x language.

Pointers to function

Pointer to function is the more ancient means that implements IoC. Even if most modern programming language got ride of them, pointers are supported by both C and C++ language and today still represent a valuable programming element.

Pointer to functions allow to customize a generic algorithm by means of callbacks. As an example the  GNU C library, which provides functions for searching and sorting arrays of arbitrary objects.

Let’s examine qsort:

qsort (void *array, size_t count, size_t size, comparison_fn_t compare)

The third argument, comparison_fn_t type, defined as “int comparison_fn_t (const void *, const void *)”, is the signature of the callback. The client code is supposed to provide a congruent comparison function in order to specialize the sort algorithm. For example:

     int
     compare_doubles (const void *a, const void *b)
     {
       const double *da = (const double *) a;
       const double *db = (const double *) b;

       return (*da > *db) - (*da < *db);
     }

The advantage of pointers to function in comparison to other semantics is the ability to customize an algorithm with a callback whose address can even be unknown at compile time (for example with functions dynamically loaded at run time from a shared library). The other side of the coin is that this feature results in a performance penalty, a major drawback if compared to other mechanism provided by  C++ and templates.

Generic Programming: STL algorithms, functors and callable types.

One of the big wins of C++ over C is represented by the templates, a semantic that enables generic programming. The Standard Template Library today is an exceptional example we all have something to learn from. More importantly, not only is it possible to customize generic STL algorithms by means of function pointers, but also it is possible to pass callable objects at the instantiation point (instances of callable types).

A callable type is defined as:

  • a pointer to function
  • a pointer to member function
  • a pointer to member data
  • a class type whose objects can stand at the left-hand side of a function call operator, that is a class that implements the operator() or a conversion to a pointer to function.

At the instantiation point, there’s no difference between passing a function pointer or an instance of a callable object as argument to a template function.

    template <typename Fun>
    void algorithm(Fun f)
    {
        f(arg1, arg2, ...);
    }

The function algorithm can either take a pointer to function or an instance of a callable type: both must have a matching signature.

A classic callable object is represented by functor, that is a class that implements the operator():

    struct generic_functor
    {
        void operator()(int arg1, arg arg2, ....) const
        {
           ...
        }
    };

Unlike a pointer to function, a functor can have a private state that can be accessed across different executions. Unfortunately, the standard does not specify that the STL algorithms must not make internal copies of the passed functors. As a result, the client code cannot take advantage of this, and this reason explains why the instances of callable types are usually passed to algorithms as temporary objects. Yet, passing a functor by std::ref() may lead to wrong results, if later we expect to find a consistent state as it were never copied.

The sole exception to this is represented by std::for_each algorithm, which returns a copy of the callable object in order to expose to the client code the state of the object utilized during the iteration. std::for_each guarantees that the instance of the function used during the iteration is unique.

    generic_functor out = std::for_each(vec.begin(), vec.end(), generic_functor());

In term of performance, there’s an important difference between calling a pointer to function and invoking a functor. In particular, the code of the operator() can be inlined into the algorithm, while the code of a function referred by a pointer can’t be because the value of the pointer is known at runtime (even if in some cases it could be statically determined at compile time).

The C++ standard provides a rich set of functors in the header <functional>. Among them, std::greater<> and std::less<> predicates that can be used to customize algorithms with different way to compare objects. For example, it’s possible to customize the std::sort in order to obtain a vector of integers sorted into descending order:

    std::sort( vec.begin(), vec.end(), std::greater<int>());

Polymorphism and NVI idiom

Another important lesson to learn from STL is that virtual functions should never be declared public. This principle, known as NVI idiom (Non Virtual Interface) or “the template method”, enables pre-condition and post-condition checking of virtual functions.

The NVI idiom, behind his back, can used to implement the IoC principle on the top of the inheritance polymorphism. The idea is simple: the base class exposes public methods implemented in term of the protected virtual functions provided, in turn, by the concrete class.

One important example of NVI idiom is, for example, the std::streambuf class, a class provided by the standard library to implement user-defined stream buffers. Streambufs are meant to customize the std::stream class, in order to accomplish the operations of read and write of character sequences.

As an example, my membuf class, a streambuf that can be used to stream from/to in-memory buffers:

    struct membuf : public std::streambuf
    {
        membuf(char *buffer, size_t size)
        {
            this->setp(buffer,buffer+size);
            this->setg(buffer,buffer,buffer+size);
        }

        char *end()
        {
            return this->pptr();
        }
    };

Policy class

Policy-based class design was first presented by Andrei Alexandrescu in the book Modern C++ Design. To repeat his words, the policy class is a technique that enables the creation of flexible, highly reusable template libraries. Such a design enables the separation of the implementation from the generic aspects of a class, increasing software decoupling, especially when multiple policies are concurrently deployed.

A policy-class can be, but it’s not limited to, a struct containing static methods that embody the details of the implementation. The classes that belong to the same policy are syntax oriented, and must respect the interface defined by the policy itself. Whether the policy-class or the included methods are templated, instead, is a matter of implementation.

A template class based on policy-classes is called host class and it’s where the magic of IoC happens. Policy-classes are passed to the host in different manners: as a template argument if the policy class includes only static methods, by means of inheritance otherwise.

Such a host class takes advantage of the implementations provided by the policy-classes at its instantiation point. Unlike the NVI, which is implemented by means of polymorphic inheritance, the host class enables IoC with no performance penalty, thanks to the static methods mixed-in by templates or by the non-polymorphic inheritance (the policy class has no virtual functions).

The policy class is similar to a traits class and differs from it only in that it’s more focused on the behavior rather than on the properties of the type. Also, the policy-class revamps the implementation of the Strategy pattern with compile-time bindings.

The C++ standard has an important example of policy-class: the std::char_traits, which is used to customize the behavior of the std::basic_string. Despite the name, indeed, char_tratits is a policy class rather than a traits class.

Strategy pattern and std::function

The strategy pattern is a particular design where the algorithms to run is dynamically selected. It is the ancestor of the policy-class: it provides the same functionality, with the difference that the binding with strategies happens at runtime, while the binding with policies does at compile time.

While different implementations are possible, the most convenient one is by means of  C++0x  std::function(or std::tr1::function available with C++03). Strategies, indeed, can be implemented with pointers to function or by means of polymorphic functors (with a common interface).

The std::function extends the strategy pattern with the ability to capture any kind of callable object with a consistent signature. The std::function allows to pass a function pointer to the strategy that later can be replaced with an instance of a callable object. All of this is possible thanks to the type erasure mechanism, a technique buried inside its implementation.

An example of a strategy-based class is:

    class strategy_based_class
    {
        typedef std::function fun_type;

        void set_compare(const fun_type &cmp)
        { _M_compare = cmp;}

        fun_type get_compare() const
        { return _M_compare; }

        void algorithm()
        {        ....
             if(_M_compare(a,b)) {
                 ....
             }
        }

    private:
        fun_type _M_compare;
    };

Like the other idioms, the use of std::function can be interpreted as an implementation the IoC principle: the stategy class can focus on the execution rather than on the implementation, demanded to the std::function itself.

Lambda functions and closures

The C++0x introduces a new kind of callable type, directly implemented in the core language: the lambda function. However, lambdas are not a real news in the C++ language. The boost library already implemented it (on the top of c++03) by means of the magic template metaprogramming.

Lambdas are a means to implement anonymous functions that can be declared inline, right where you need them. It’s possible to declare a lambda at the instantiation point of a generic algorithm, without the need to declare the callable type with global visibility. The use of lamba functions is very handy and effective.

Lambdas have also the ability to refer to identifiers declared outside the lambda itself, much like the nested functions of the C language. A lambda function that access to external variables is known as closure, in honor to the Lips language.

With respect to IoC, lambdas are just another way to customize a template function/algorithm, like those of STL, and they are also assignable to a std::function<> with a compatible signature.

As examples, the std::sort of a container in descending order and the accumulate algorithm, implemented by std::for_each, both in term of lambda functions.

    std::sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; });

and

    int sum = 0;
    std::for_each(vec.begin(), vec.end(), [&sum](int n) { sum += n; });

The original article of Martin Folwer covers more detailed aspects of IoC, especially from the point of view of the Java language.  Also more information can be obtained at http://martinfowler.com/bliki/InversionOfControl.html.

In this essay I covered the IoC pattern, presenting some implementations from the point of view of the expressive C++ language. While the acronym IoC is not so common in the C++ world, its meaning can be found in very different forms: it’s a matter to distinguish it in a plethora of semantics.

Enjoy C++0x, always.

Advertisements

Filed under: c++, C++11, programming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: