Quote of the week – analogies

Comparing to another activity is useful if it helps you formulate questions, it’s dangerous when you use it to justify answers.

Martin Fowler

I like analogies, probably more than I should. One of my favourite analogies is to compare code quality to the three different types of equilibrium I was taught in physics class.

Stable equilibrium is like a cherry in the bottom of a bowl. You can push the cherry slightly and it will return to its original position at the bottom of the bowl. It’s like well written code that can be changed without breaking in unexpected ways – perhaps the team followed the “Don’t Repeat Yourself” rule so that when a constant needed to be changed it was changed in one place and the change percolated correctly through the system.

Unstable equilibrium is when the bowl is overturned. With care you can balance the cherry on the top of the bowl, but the moment the cherry is disturbed it will roll off. I have seen lots of multithreaded code that was tweaked and tuned and hacked around until it “worked”. The moment anything changed, often something innocuous, the program would fall apart.

The third type of equilibrium is neutral equilibrium. Imagine that the bowl is filled with jelly (jello to our American readers) and the cherry is suspended inside the jelly. I think this proves a corollary to Martin Fowler’s original statement – you can only push an analogy so far before it breaks down (although if someone does manage to come up with a decent code analogy to neutral equilibrium I’d love to hear it).

Algorithms in action – iota and shuffle

When I was working on my sorting code for this post, I wanted a vector of randomly ordered, unique integers for testing.

The code is straightforward:

std::vector< int >
getRandomVector( int n )
    std::vector< int > v_i( n );

    std::iota( std::begin( v_i ), std::end( v_i ), 0 );

    std::default_random_engine dre;
    std::shuffle( std::begin( v_i ), std::end( v_i ), dre );

    return v_i;

C++11 added std::iota – an algorithm that assigns incrementing values to a sequence. In my example the values are integers starting at zero.

I was confused when I first saw iota. Initially I thought someone had misspelt itoa (not a standard function but sometimes available as an extension), then I thought since iota is atoi backwards there must be a link between them.

I was wrong on all counts. std::iota represents the Greek letter iota ( Ι, &#x03B9 ) which (depending on your font and which case you are examining) looks similar to a lower case “L”, an upper case “i”, a one “1”, or a vertical bar “|”.

The Greek letter iota is used in the programming language APL to generate a sequence of consecutive integers. APL has a wild and wonderful character set described here. My favourite part of the Wikipedia article is the statement “Most APL symbols are present in Unicode”. In other words, some APL symbols are not present in Unicode (the article goes on to identify the missing symbols). I think this is wonderful. There are over 100,000 characters in Unicode and you still can’t use it to write APL (I realize that APL predates Unicode so was not trying to fit into its character set, and also that there are implementations of APL that do limit themselves to characters generally available on a modern computer). I thought digraphs and trigraphs were bad enough – C++ programmers have it easy compared to APL programmers.

std::iota uses prefix operator ++ to generate successive values. I wish I had a good example other than integers to show. I don’t, but I’ll look out for one.

One final point, std::iota assumes that you have a sequence already created – it isn’t possible to use it with std::back_inserter (or any other inserter) to create the sequence. For my example it really doesn’t make any difference, but if there is a use case with a more complicated type, possibly one that doesn’t support a default constructor, it would be nice not to have to default construct the sequence first. Of course, if this ever becomes a real problem it is easy enough to write iota_n.

I am using std::shuffle (added in C++11) rather than std::random_shuffle (available since C++98) so that I can use the bright shiny new random number generators we get in C++11. (See Stephan T. Lavavej’s talk rand() Considered Harmful for more on why the new C++ random number generators are much better than rand).

For this example I haven’t bothered to seed the random number generator, and I am not that worried about perfect randomness anyway but I am trying to drag my programming style into the C++11 world. I suspect I will succeed at embracing C++11 at about the same time C++14 is unleashed.

While we are on the subject of randomness, here’s an interesting note from the C++11 standard. The description of the three shuffle algorithms includes this phrase:

Effects: Permutes the elements in the range [first,last) such that each possible permutation of those elements has equal probability of appearance.

Given a perfect random number generator the output from any of the shuffles should be perfectly uniform. Sounds reasonable enough, however there is at least one “obvious” shuffling algorithm that fails this test:

Iterate over the elements of the sequence and swap each element with a randomly chosen element (possibly itself).

Jeff Atwood goes into more details here, and also mentions a common algorithm which does produce uniform results, the Fisher–Yates shuffle, also known as the Knuth shuffle (both links take you to the same Wikipedia page).

Roughly speaking the Fisher–Yates shuffle is:

Pick an element randomly from the input sequence, add it to the result sequence and remove it from the input sequence. Repeat until the input sequence is empty.

It’s equivalent to picking a card at random from the deck, putting it into a separate “shuffled” pile and repeating until all the cards are in the “shuffled” pile.

Many years ago I looked at a couple of standard library implementations of shuffle algorithms and they were using the Fisher–Yates shuffle. I assumed this would still be true. Once again I was wrong. Both Visual Studio and GCC are using another shuffle algorithm which I haven’t been able to track down the name of (if anyone knows, please post a comment). As far as I can tell, the algorithms works something like this:

Assume you have a perfectly shuffled sequence of n elements. Add another element to the end of the sequence, then swap it with a randomly chosen element of the new (size n + 1) sequence (possibly itself).

I assume that this procedure produces another perfectly shuffled sequence (although I can’t prove it). Since we can start with a single element (perfectly shuffled) we can build up to any number of elements.

References for shuffling:

  • The C++11 standard Section 25.3.12 Random shuffle
  • Knuth: The Art of Computer Programming Volume 2, Seminumerical Algorithms 3rd edition Section 3.4.2 Random Sampling and Shuffling
  • Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms 2nd edition Section 5.3 Randomized algorithms

std::bind and lambda functions 6

This is the last post in this series, and I am going to use it to wrap up a few things that didn’t quite fit in anywhere else.

As I said at the start, this series is not the ultimate guide to std::bind and lambda, it has focused on a few things that I find interesting. As always, if you want definitive information look at these three references:

As you’d expect, Herb Sutter has written and spoken about lambdas many times.

Passing values by reference

All of my examples have assumed that bound or captured arguments are captured by value. Take a look at this code:

double add( int i, float f )
    return i + f;

typedef std::function< double( int ) > SingleArgumentAdd;
float f( 10.0f );

SingleArgumentAdd fn0( std::bind( add, _1, f ) );
SingleArgumentAdd fn1( [ f ]( int i )
    return add( i, f );
} );

f = 20.0;

std::cout << fn0( 5 ) << ", ";
std::cout << fn1( 5 ) << "\n";

It writes out 15, 15 showing that the value of f that is used is the value when the function object is created.

We could pass in a pointer to f rather than f itself:

double add1( int i, float* pF )
    return i + *pF;
float f( 10.0f );
float* pF( &f );

SingleArgumentAdd fn0( std::bind( add1, _1, pF ) );
SingleArgumentAdd fn1( [ pF ]( int i )
    return add1( i, pF );
} );

f = 20.0;

std::cout << fn0( 5 ) << ", ";
std::cout << fn1( 5 ) << "\n";

This time we get 25, 25 - the pointer is not dereferenced until fn0 and fn1 are called.

What about passing f by reference? That should give us the same result as passing by pointer - the value of f is the value when the function is called. Here's the code:

float f( 10.0f );

SingleArgumentAdd fn0( std::bind( add, _1, std::cref( f ) ) );
SingleArgumentAdd fn1( [ &f ]( int i )
    return add( i, f );
} );

f = 20.0;

std::cout << fn0( 5 ) << ", ";
std::cout << fn1( 5 ) << "\n";

The code prints out 25, 25, just as we'd expect. We had to do two things differently though:

  1. We have to explicitly tell std::bind that f must be passed by reference (a const reference in this case). If we don't do this, std::bind will dereference f and use whatever value is in f when std::bind is called. std::cref is a function that returns an object that wraps the reference and makes sure that the reference is not dereferenced until fn0 and fn1 are called. See The C++ Programming Language, 4th Edition, section 33.5.1 for more information.
  2. Lambdas are much simpler. We write &f in the capture block to indicate that f should be captured by reference.

Whether we are using pointers, references, lambdas or std::bind there is one thing we need to keep in mind - when we dereference the reference, the object it refers to must still exist.

Nesting and chaining functions

When we have an object of type std::function it is a first class object in C++. We can copy it, pass it to functions, return it from functions, store it as a member variable and treat it like any other object.

This means that we can set up nested functions, we can chain functions together and we can use std::function objects for callbacks. As always, just because you can doesn't mean that you should. I am experimenting with chains of functions for my current project and, while I can make it work, it isn't pretty and it isn't clear what is going on.

operator () should be const for predicates

I am not going to go into this in detail because others have done a better job than I have. In general, when you write your own predicate function object, operator () should be const - it cannot update any stored state in the function object. There are two reasons for this:

  1. The standard does not place any restrictions on the number of times a predicate is copied (I think that std::for_each is the one exception). As Josuttis points out in The C++ Standard Library: A Tutorial and Reference (2nd Edition) section 10.1.4, a typical implementation of std::remove_if does copy the predicate and will give the wrong result if the predicate is storing state.
  2. By default, there is no guarantee that the algorithm will traverse the list from the beginning to the end. As far as I can tell, these are the only algorithms which are guaranteed to traverse from beginning to end: std::for_each, std::copy, std::move, std::accumulate, std::inner_product, std::partial_sum and std::adjacent_difference. I found these by searching the standard for the phrases starting from first and proceeding to last, and in order.

By default, the function object constructed by a lambda expression has a const operator (). If you really want it to be non-const you can declare the lambda mutable.

Why do we need std::find_if and std::count_if?

There are algorithms which have an overloaded predicate and non-predicate version, for example, std::is_sorted :

is_sorted( ForwardIterator beg, ForwardIterator end );

is_sorted( ForwardIterator beg, ForwardIterator end, BinaryPredicate op );

If we look at std::find we see why we can't overload it with a predicate and non-predicate version:

find( InputIterator beg, InputIterator end, const T& value );

Despite the fact that we can supply template specializations that will match a function, we can't know whether we are supplying a function because we are searching for a function in a container of functions or whether we are supplying a function to act as a predicate. That means we have to have a separate std::find_if (and std::count_if) function.

std::bind and member functions

In part 2 we looked at pointers to member functions, but I never demonstrated how these work with std::bind.

class MemberFunctionDemo
    double add( int i, float f )
        return i + f;

        std::cout << std::bind( 
            20.0f )( 10 );

The first argument to std::bind is always the function that will be called. For member functions we have to use & to get a pointer to the function, and the function name must be fully qualified. The second argument is the object to call the function on - it can be a pointer or a reference to the object, in my example, I am using this.

std::bind as a way of limiting scope

A colleague at Adobe pointed out that we can use a lambda to create a block of code that does not have access to all variables in the surrounding scope:

int i, j, k;

// Some code here...

[ i, j ](){
    // Only have access to i & j here.
    // No access to k

I am not sure whether this is a Good Thing, a Bad Thing or just a Thing.