I am moving my personal projects to GitHub. While I had a good run with the simple gitweb interface, it just is not up-to-date any more. I hope to increase the reach of my projects via GitHub, in particular the QtOSG widget project.

You may find my main profile under http://github.com/Submanifold. My previous project domain, http://git.annwfn.net has been set up to provide a permanent redirect to this profile.

Posted Saturday afternoon, April 4th, 2015 Tags:

John Oliver recently explained the need for privacy in his great show Last Week Tonight by using a rather NSFW example, namely his private parts. There is even a new website about this very issue. I love the internet.

However, I am not entirely satisfied with the reason for privacy. Taking and sending pictures of your junk is a deliberate action of your part. Eric Schmidt had the following to say about this:

If you have something that you don't want anyone to know, maybe you shouldn't be doing it in the first place.

This is certainly not completely wrong—and this is precisely the reason why I dislike the example used by John Oliver. Let me explain: In German, we have two words for privacy. We have Intimsphäre, which pertains to things that are “intimate”, e.g. your junk. We also have the word Privatsphäre, which pertains to things that are (merely) private. In my opinion, it is a bad idea to reduce the problem with surveillance to the most intimate of things! Of course, most people would not like the government to make copies of their nude pictures or whatever. That is beside the point. I even resent governments or anyone snooping in things that are clearly private.

A more useful example is the current state of my apartment. When I am having people over, I clean everything to make sure that no discarded clothes, papers, or anything messy is around. When I am on my own, books start to occupy all surfaces over time. This is not something I need to hide, but I would still be embarassed if I am having a visitor and the apartment is not cleaned. Now imagine the government being able to look over your daily affairs, with all the social make-up removed. All your journal entries, e-mails to loved ones (with or without pictures of private parts), comments on social networks, and so on. This is the real issue with (government) surveillance. We must not let the NSA and others take over our Privatsphäre and fall back to our Intimsphäre. They need to be kept out of both!

(I wrote this as a result of a very intriguing coffee-break discussion with friends and colleagues. Thank you for the insights)

Posted Sunday afternoon, April 12th, 2015 Tags:

Every C++ programmer sooner or later happens to stumble over template meta-programming. I was no exception. And suddenly, the old adage applied to me as well: "If all you have is a hammer, everything starts to look like a nail"

A very useful technique from template meta-programming is the concept of type lists. Briefly put, a type list is a list that contains types instead of values. It is thus defined at compile-time already. When might this be useful? In itself, probably never. Except for showing off. But in my opinion, the real utility of type lists unfolds when they are coupled with type switches. A type switch is another—you guessed it—concept from meta-programming. Given a type list, a type switch offers a way for calling a functor with a given type from the type list. The whole point is that the type switch permits the selection of a functor at runtime! Hold on to your hats, gentlefolks! This means I can essentially write something like this:

typedef TypeList<char, short, int, long> IntegerTypes;
Functor f;
TypeSwitch<IntegerTypes> ts;

unsigned int index = 0;
std::cin >> index;

ts( index, f );

The snippet above does not compile yet, but we'll get there! You can see that we have deferred the decision about which type to use in the functor call. We let a user input at runtime decide about the type. Even though we are using templates. When I first learned about this, it seemed like magic to me. As we all know, any sufficiently analysed magic is indistinguishable from science, though. So, let's try to get there. Throughout this post, I will include some snippets from real code. You can get the complete project on GitHub.

Type list

There are many ways for designing a type list. I chose a very easy one by limiting my type list to 10 types, which spared me from having to define it recursively. Andrei Alexandrescu has a great article about recursively-defined type lists and their applications. We start out differently, by defining a generic base case first:

struct EmptyType
{
};

template <
    typename T0 = EmptyType,
    typename T1 = EmptyType,
    typename T2 = EmptyType,
    typename T3 = EmptyType,
    typename T4 = EmptyType,
    typename T5 = EmptyType,
    typename T6 = EmptyType,
    typename T7 = EmptyType,
    typename T8 = EmptyType,
    typename T9 = EmptyType
> struct TypeList;

So far, nothing wild is going on. We have an empty type and a template declaration. We shall now use template specialization to refine the type list:

template <
    typename T0,
    typename T1,
    typename T2,
    typename T3,
    typename T4,
    typename T5,
    typename T6,
    typename T7,
    typename T8,
    typename T9
> struct TypeList
{
  typedef T0 head;
  typedef TypeList<T1,T2,T3,T4,T5,T6,T7,T8,T9> tail;

  enum
  {
    length = tail::length + 1
  };
};

This is also not very spectacular. We have a typedef for the head and a reduced type for the tail of the list. We also define a recursive enum. This is allowed because tail refers to a type that is known at compile-time. We are not finished, though. We still need to define a base case, namely that of the fully empty type list:

template <> struct TypeList<
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType>
{
  enum
  {
    length = 0
  };
};

And there we have it! A simple type list that is utterly useless. Well, we can at least query its size:

typedef TypeList<char, short, int, long> IntegerTypes;
std::cout << IntegerTypes::length << std::endl;

This should yield an output of 4. We can capture this in a nice struct:

template <typename TypeList> struct TypeListLength
{
  enum
  {
    value = TypeList::length
  };
};

This permits us to write TypeListLength<IntegerTypes>::value, making the intent somewhat clearer. Also, it makes writing an access struct easier.

Accessing a type from a type list

A useful operation for the type list would be an access functor. Given an index, we should be able to query the time at that index. If the index is out of range, we refuse to compile. That's at least one good thing about templates—we catch problems early with very confusing compiler output. Let's start with an access functor then:

template <
  typename TypeList,
  unsigned int Index,
  unsigned int Step = 0,
  bool Stop = ( Index == Step ),
  bool OutOfRange = ( TypeListLength<TypeList>::value == 0 )
> struct TypeListGet
{
  typedef typename TypeListGet<typename TypeList::tail, Index, Step + 1>::type type;
};

This is only the general case. We have an Index attribute that refers to the desired index in the type list by the client, and some "internal" attributes for keeping track of where we are in the type list.

Now let's handle the specialization. The first one is easy. If we have reached the end of the type list, we define the struct to be empty. This will result in a compile-time error when a client aims to access an incorrect index:

template <
  typename TypeList,
  unsigned int Index,
  unsigned int Step,
  bool Stop
> struct TypeListGet<
  TypeList,
  Index,
  Step,
  Stop,
  true>
{
  // This is empty by design.
};

The other specialization is straightforward as well. In case Index and Step coincide, the Stop attribute is set to true. This means we have found our desired type and it is at the very beginning of the type list. Hence:

template <
  typename TypeList,
  unsigned int Index,
  unsigned int Step,
  bool OutOfRange
> struct TypeListGet<
  TypeList,
  Index,
  Step,
  true,
  OutOfRange>
{
  typedef typename TypeList::head type;
};

Now our demo program may become slightly more involved:

#include "type_list.hh"

#include <iostream>
#include <typeinfo>

int main( int, char** )
{
  typedef TypeList<char, short, int, long> IntegerTypeList;

  std::cout << IntegerTypeList::length << "\n";

  std::cout << "The type list has a length of " << TypeListLength<IntegerTypeList>::value << std::endl
            << "The first type is " << typeid( TypeListGet<IntegerTypeList, 0>::type ).name() << std::endl
            << "The second type is " << typeid( TypeListGet<IntegerTypeList, 1>::type ).name() << std::endl
            << "The third type is " << typeid( TypeListGet<IntegerTypeList, 2>::type ).name() << std::endl
            << "The fourth type is " << typeid( TypeListGet<IntegerTypeList, 3>::type ).name() << std::endl;

  return 0;
}

The output should read like this:

The type list has a length of 4
The first type is c
The second type is s
The third type is i
The fourth type is l

Still not terribly useful, but somewhat cool, I guess.

The type switch

Now let's add the magic. Given a functor that provides a templated operator()(), we want to call it with a type that is selected at runtime using an index. The generalized case is very ugly here because we do not know the return type of the functor beforehand. Lucky for us, C++11 offers the decltype specifier:

template <
  typename TypeList,
  unsigned int Index = 0,
  bool Stop = ( Index == TypeListLength<TypeList>::value )
> struct TypeSwitch
{
  template <class Functor> decltype( Functor().template operator()<typename TypeListGet<TypeList, Index>::type>() ) operator()( unsigned int i, Functor f )
  {
    if( i == Index )
      return f.template operator()<typename TypeListGet<TypeList, Index>::type>();
    else
    {
      TypeSwitch<TypeList, Index + 1> next;
      return next.operator()( i, f );
    }
  }
};

The decltype ensures that we get the proper return type of the functor for the current type at the requested index of the type list. If we have not found the proper index yet, we create a new type switch (with adjusted index) and recurse.

Now the only thing that is left to handle is the when the index goes out of bounds. Here, we can use a specialization with a fixed value for the Stop attribute. Recall that it is set when the index is equal to the length of the type list, i.e. upon encountering the first invalid index.

template <
  typename TypeList,
  unsigned int Index
> struct TypeSwitch<
  TypeList,
  Index,
  true>
{
  template <class Functor> decltype( Functor().template operator()<EmptyType>() ) operator()( unsigned int /* i */, Functor /* f */ )
  {
    throw std::runtime_error( "Index is out of range" );
  }
};

And that's it. We may now use such cool constructions as the following:

#include "type_list.hh"
#include "type_switch.hh"

#include <iostream>
#include <typeinfo>

struct Functor
{
  template <class T> void operator()()
  {
    std::cout << "Called with the following type: " << typeid(T).name() << std::endl;
  }
};

int main( int, char** )
{
  typedef TypeList<char, bool> MyTypes;

  Functor f;
  TypeSwitch<MyTypes> ts;

  for( unsigned int i = 0; i < TypeListLength<MyTypes>::value; i++ )
    ts( i, f );

  try
  {
    ts( 42, f );
  }
  catch( std::runtime_error& e )
  {
    std::cerr << "Oops, this type does not exist: " << e.what() << std::endl;
  }

  return 0;
}

This results in the following output:

Called with the following type: c
Called with the following type: b
Oops, this type does not exist: Index is out of range

OK, maybe the program is not completely useful. In general, type switches can be very useful, though. I have used it in the past to loop over pre-defined types for volume data. The functor in this case simply checked whether it was possible to load volume data of a fixed size with a given type. If so, we knew that we had identified the right type. The advantage of this approach is that it naturally scales with the number of types we define. We do not have to resort to ugly dynamic_cast constructions or something like that.

If you want to learn more, I can only recommend the books by Andrei Alexandrescu. If you are a bit like me, please also take JWZ's law into account:

Some people, when confronted with a problem, think "I know, I'll use regular expressions template meta-programming." Now they have two problems.

Enjoy your templates!

I want the code

Sure, you can have it. It's on GitHub and licensed under an MIT license.

Posted Sunday afternoon, April 19th, 2015 Tags:

I recently started thinking about event handling systems. I have been using Boost.Signals for some time now and was pretty happy with it. Then the number of signals spiralled out of control and forced me to re-think the design. The venerable design patterns book offers the Observer pattern or its modified form, the Publish–subscribe pattern. Both design patterns involve passing information between possibly unrelated objects.

My goal was to come up with a system that couples objects very loosely. Ideally, the central instance, which I am going to call dispatcher because it makes Tamiko happy, should know barely anything about an event it delivers. Using C++11, I came up with a rather simple and straightforward design.

The following discussion will leave out unsubscriptions by observers because it makes the code samples harder to follow. The code on GitHub, though, has this functionality.

A base event class

Regardless of how anything else is implemented, we need a base class for describing an event. Mine looks like this:

class Event
{
public:
  virtual~ Event();

  using DescriptorType const char*;

  virtual DescriptorType type() const = 0;
};

Not much to see here. The destructor is kept virtual because Event is a polymorphic base class. Every derived event needs to implement the type() function to describe itself. The DescriptorType refers to const char*, meaning that each event uses a const char* to create a unique identifier. In practice, this is what it might look like:

class DemoEvent : public Event
{
public:
  DemoEvent();
  virtual ~DemoEvent();

  static constexpr DescriptorType descriptor = "DemoEvent";

  virtual DescriptorType type() const
  {
    return descriptor;
  }
};

Note that the DemoEvent class also offers a static constexpr descriptor. This permits us to write DemoEvent::descriptor when referring to the descriptor of this class. In other words, we do not need to instantiate anything here.

The dispatcher

The role of the dispatcher is to manage multiple observers that are interested in a certain event. To this end, we need a predefined interface every observer needs to implement. C++11 offers std::function for this purpose. We also need to keep track of which observers are interested in which event. This is where the DescriptorType of events comes in. Since DescriptorType is a const char*, we can use it as key in a map! Whenever an event occurs, we then look up its corresponding type, use this to access the map, and call all observers.

This is the basic interface of the dispatcher:

class Dispatcher
{
public:

  using SlotType = std::function< void( const Event& ) >;

  void subscribe( const Event::DescriptorType& descriptor, SlotType&& slot );

  void post( const Event& event ) const;

private:

 std::map< Event::DescriptorType, std::vector<SlotType> > _observers;
};

Using post() any client can send events to all observers that are interested in them. The dispatcher keeps track of slots to call using the map. The implementation turns out to be surprisingly simple:

void Dispatcher::subscribe( const Event::DescriptorType& descriptor, SlotType&& slot )
{
  _observers[descriptor].push_back( slot );
}

void Dispatcher::post( const Event& event ) const
{
  auto type = event.type();

  // Ignore events for which we do not have an observer (yet).
  if( _observers.find( type ) == _observers.end() )
    return;

  auto&& observers = _observers.at( type );

  for( auto&& observer : observers )
    observer( event );
}

Defining observers

So, how do we use the dispatcher then? By invoking the magic of std::bind. Let us first define a simple observer class. In this class, we can also check the underlying event type, for example if we want to react differently to certain events:

class ClassObserver
{
public:
  void handle( const Event& e )
  {
    if( e.type() == DemoEvent::descriptor )
    {
      // This demonstrates how to obtain the underlying event type in case a
      // slot is set up to handle multiple events of different types.
      const DemoEvent& demoEvent = static_cast<const DemoEvent&>( e );
      std::cout << __PRETTY_FUNCTION__ << ": " << demoEvent.type() << std::endl;
    }
  }
};

Again, we can see that the static constexpr comes in handy. We do not need an instance of DemoEvent here. Now, assuming we have a dispatcher variable called dispatcher, which is very creative, we can finally use std::bind():

int main( int, char** )
{
  using namespace std::placeholders;

  ClassObserver classObserver;
  Dispatcher dispatcher;

  dispatcher.subscribe( DemoEvent::descriptor,
                        std::bind( &ClassObserver::handle, classObserver, _1 ) );

  dispatcher.post( DemoEvent() );
}

This also demonstrates the basics of posting an event. It is probably not apparent in this example, but the dispatcher does not need to know anything about events excepts that they are inheriting from the same base class. We can pass arbitrarily complex objects to and fro without changing the coupling between the dispatcher and the observers.

Limitations

A severe limitation of the design in this form is the inability to handle events in different threads. The post() interface assumes that it gets passed a const reference to an event. This makes sense insofar as we do not know how "heavy" an event is—or whether it makes sense to be copied. Thus, in case one observer chooses to handle an event in a separate thread, the event could potentially be destroyed before the observer finished handling it. One solution for this problem would be to use std::shared_ptr to pass events around. This at least would solve the destruction issue—but I am not very firm concerning the thread safety of std::shared_ptr.

Another issue is a systematic problem: I cannot guarantee the uniqueness of the self-described events. If a client chooses to implements events A and B and both return, say "Foo" as their event type, the dispatcher will not be able to separate between these events. Currently, I do not have a solution for this—hence, comments would be highly appreciated!

The code

A slightly more involved implementation is available as the "Events" repository in my GitHub account. The code is licensed under an MIT license.

I hope reading this was both insight- and eventful for you.

Posted at midnight, April 25th, 2015 Tags: