Deceive “lambda-unable” algorithms with mimesis

Posted: April 16, 2013 in Programming Recipes
Tags: , ,

Some general-purpose algorithms accept a range (e.g. two iterators) and an additional value. For example std::iota fills the specified range with sequentially increasing values, starting with a certain value V and repetitively evaluating ++V:


vector<int> aVector (5);

iota ( begin(aVector), end(aVector), 1);

// aVector is {1, 2, 3, 4, 5}

This algorithm is really simple, but how is it possible to operate on the initial value in a quite generic way? Suppose we want to reuse iota to fill the range with increasing squared values, e.g.: {1, 4, 9, 16, 25}.

Since iota accepts nothing but a value in the range, we cannot pass, say, a lambda. We have to feed it with a special value or something like that. A mimesis object (explained in Advanced C++ Metaprogramming, by Davide Di Gennaro) is something we may take inspiration from. Actually, according to Davide’s definition, a mimesis for a type T is a unary predicate that behaves like an instance of T. It generally implements operator==(const T&), operator!=(const T&) and operator “cast to T”. In other words if M is a mimesis for type T, then the fundamental property for M is:


M<T> m;

assert(m == static_cast<T>(m));

A simple example is a mimesis that identifies positive numbers:


template <typename scalar_t>;
struct positive
{
 bool operator==(const scalar_t& x) const
 {
    return x>0;
 }

 operator scalar_t() const
 {
    return 1; // an arbitrary positive number
 }
};

template <typename scalar_t>;
inline bool operator==(const scalar_t& x, const positive<scalar_t>& p)
{
    return p == x;
}

...
double arr[] = {-1.0, 2.5, 5.0};
auto it = std::find(arr, arr + 3, positive<double>()); // 2.5

With mimesis, we could unify algorithms (e.g. in the previous example we don’t need find_if anymore). You’re right, a mimesis takes more effort than a lambda, but it’s worth especially for generalizing functions that take a special value as an argument (I suggest you to read, for example, the “End of range” section in Davide’s book).

Ok, this was a very short intro. Back to our problem: How to use mimesis to generalize iota? Let’s have a look at a possible implementation of iota:

template<class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value)
{
    while(first != last) {
        *first++ = value;
        ++value; // pre-increment operator
    }
}

Suppose value is a mimesis that initially stores a certain int (say 1). The mimesis have to be able to perform two operations:

  • pre-increment (for line 6)
  • cast to int (for line 5)

My idea is to create a generic mimesis “holder” for iota that receives a function that performs the user’s operation, and which result will be casted to T (but you can extend it, for example, by providing also a pre-increment function):


template<typename T, typename MainFn>
struct iota_mimesis_t : MainFn
{
 template<typename TT, typename FF>;
 iota_mimesis_t(TT&& aValue, FF&& aMainFn)
    : MainFn(forward<FF>(aMainFn)), value(forward<TT>(aValue))
 {}

iota_mimesis_t& operator++()
 {
    ++value; // can be generalized
    return *this;
 }

 operator T()
 {
    return MainFn::operator()(value);
 }

 T value;
};

template<typename T, typename F>
iota_mimesis_t<T,F> iota_mimesis(T&& value, F&& fn)
{
 return iota_mimesis_t<T,F>(forward<T>(value), forward<F>(fn));
}

...

vector<int> v (5);
iota ( begin(v), end(v), iota_mimesis(1, [](int anInt){ return anInt*anInt; }));
// aVector is {1, 4, 9, 16, 25}

The key point here is to grasp the internals of iota (that are easy). Different algorithms could be more complicated, but often it’s worth striving to generalize some stuff. Mimesis could be precious allies to deal with “value-only” algorithms (think of legacy code also) and mixing them with modern lambdas can generalize even further.

This succint post is just an introduction. If you spot “lambda-unable” algorithms, try to make them “lambda-able” with mimes and be generic!

Advertisements
Comments
  1. CS says:

    This is a nifty trick and very clever, but using a for loop or std::for_each instead of iota would get the job done and the code would be easy to understand.

    Is there a better real world example where this mimesis trick would be preferable to using a simple loop? Without a beter example, I’d say this is a maintenance nightmare and warn anyone willing to trying away.

    Also there is a bug, aVector is {1, 4, 9, 16, 25} instead of {1, 3, 9, 16, 25}

    • Marco Arena says:

      Hi there. I start from the end:

      – thanks, there is a bug in the comment. Fixed.

      – I don’t think this will be a maintenance nightmare. Mimesis are generally concise and straightforward to understand, and, in my example, the iota_mimesis is unlikely to change but it’s quite generic because you can feed it with arbitrary functions performing the real job. They accomodate the Open-Closed principle, that is: “Closed for modification, open for extension”.

      – You’re right, this is not likely to be a real world example. I successfully used mimesis with legacy code and they supported me to unify some algorithms.

      – Considering my example, a for_each can do the same, even if it could require you to add some extra logic (e.g. the for_each applies a function for each element, here you can’t just write “anInt * anInt” in the lambda, because you also must take care of increasing something). I used iota just because it’s a very simple case of what I defined “lambda-unable” algorithm in the STL.

      Thanks for your comment.

    • I think we all agree that std::iota is not a “real world example” (yes, I’d probably write a for-loop), but it’s simple enough to convey the idea. The elegance of the mimesis idea is precisely the reuse of code in “the other direction”: everyone knows how to implement std::find using std::find_if, but the opposite is less trivial (though not exactly a technique you’d need everyday).

      if you really care for a better example, I’ve seen containers-of-T where the interface is overloaded to accept a generic type X. think about something like:


      template<typename K, typename V>
      class mymap
      {
      public:
      template<typename X>
      V & operator[](const X & key); // more generic than const K &

      V & operator[](const K & key); // may or may not exist
      };

      the obvious motivation is that internal operations (lookups, etc.) are usually implemented using some T::operator…, which can be overloaded, and passing directly X could save the construction of a expensive temporary (think about T=std::string and X=const char*).
      In this case, with the right mimesis you can achieve some interesting results, like finding a string that STARTS with key (not all search criteria will work, though).

  2. CS says:

    The map example shows where this trick can be useful. Thanks for the reply, Theply.

    I see how your iota_mimesis_t works with the defined operations of the iota, prefix increment and assigment to a dereferenced forward iterator. The example is robust.

    More generically, I still have a minor concern when using a mimesis with a standard algorithm. How and a development team be sure that the mimesis works with the standard’s definition of the algorithm and not some quirk of the compiler’s current implementation? The mimesis patern does remind me a bit of std::vector, and how a vector of bools is not a really a vector and the problems this can cause. Am I being overly pessimistic?

    Another possible bug in the iota_mimesis_t constructor…

    iota_mimesis_t(TT&& aValue, FF&& aMainFn)
    : MainFn(forward(aMainFn)), value(forward(aValue))

    Should this instead have “value(forward(aValue)”? or “forward(aMainFn)”? I’m assuming that it should be TT for both and FF for both, but I’m not exactly sure how to correctly use std::forward.

  3. Marco Arena says:

    Thanks guys, this discussion is more interesting than I hoped!

    Davide, you hit it on the nail. Your example is cool.

    CS, thanks again for spotting another copy-paste bug. Fixed now. Regarding your concern, you could be right, some implementations can dramatically differ from others (e.g. iota could be implemented differently, e.g. using post-fix increment) and this scenario is a pain. Mimesis are more likey to win if you have the total control over the algorithms you are using.

    I also think that mimesis are useful when dealing with:

    – legacy code (to “deceive” unmodifiable APIs)
    – unifying functions/algorithms (e.g. find VS find_if or Davide’s map example)

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