Quote of the week – type systems and unit tests

A type system is the most cost effective unit test you’ll ever have.

Peter Hallam

Peter Hallam was a language designer on the first three versions of C#, then became technical lead for the C# compiler before moving to Google and building the Traceur compiler which compiles JavaScript.next to standard JavaScript. If you want to hear him talk about Traceur checkout this video.

Peter’s a man who knows his type systems – good, bad and ugly.

I saw a nice example of using the type system to prevent bugs when I worked on Pixel Bender at Adobe. Pixel Bender is an image processing toolkit. Images are made up of pixels, however, pixels are not always 1×1 in size, and they are not always square – in particular, video processing often uses rectangular pixels. At the time we started the project we hadn’t come to grips with non-square, non-unit-sized pixels so we started with a single coordinate system where moving right one unit moved you one pixel across, and moving up one unit moved you one pixel up. This pixel coordinate system is not isotropic – one unit on the X axis is not necessarily the same distance as one unit on the Y axis. We wanted to be able to represent rectangular areas of pixels so we created two classes – Position (containing x and y values) and Extent (containing width and height values).

We got away with our pixel coordinate system for quite a long time, however eventually we realized that we needed to have an underlying, isotropic, coordinate system. We called this world coordinates. We converted between pixel coordinates and world coordinates by using the width and height of a single pixel. Since we already had Position and Extent classes we used them for our world coordinate system as well.

Imagine you see a function that takes a Position as an input parameter. Is that Position in world coordinates or pixel coordinates? We instituted some naming conventions. They sort of worked. Mostly. Except when they didn’t. We had plenty of tests, which caught some of the bugs, but working with a Position or an Extent was more fragile than we wanted.

Our solution was to create separate classes for pixel and world coordinates. We ended up with:

PixelPosition
WorldPosition
PixelExtent
WorldExtent

The two Position classes were identical apart from their name, as were the two Extent classes. In both cases we just had the simplest possible wrapper around two double values with appropriately named accessor methods. We could have used some template magic to avoid code duplication. We could have used some “clever” macros (and I put “clever” in quotes to indicate my disdain). We actually just wrote separate classes – very simple classes, with some repetition of boilerplate between them. Breaking the normal “don’t repeat yourself” rule seemed justified here. For a little (and it really was a little) more work up front we had a very simple system that served us well. If we had been working with tens or hundreds of different coordinate systems we might have used another method to generate the code, but we only had two, and we were relatively convinced that we were never going to add more than one or two additional coordinate systems (as it turned out we only needed pixel and world coordinates).

By looking at code you knew what coordinate system was in use. When writing new code you could specify what coordinate system it needed its inputs to be in. If you tried to pass a value in the wrong coordinate system to a function the compiler would stop you. The system worked. We made it easier to do it right than to do it wrong – using the type system eliminated a whole class of bugs from our code.

std::bind and lambda functions 5

Let’s start with a quick reminder of what a lambda expression looks like:

std::vector< int > v_i( functionReturningVector() );
std::vector< double > v_d;

float f = functionReturningFloat();

std::transform( 
    std::begin( v_i ), 
    std::end( v_i ), 
    std::back_inserter( v_d ), 
    [ f ]( int i ){
        return i + f;
    } );

The lambda expression is this part:

[ f ]( int i ){
    return i + f;
} 

The standard says “Lambda expressions provide a concise way to create simple function objects”. The lambda expression we have just seen corresponds to the Adder function object that we looked at earlier in this series:

class Adder
{
public:
    Adder( float f )
    : f_( f )
    {}
    
    double operator()( int i ) const
    {
        return i + f_;
    }
    
private:
    float f_;
};

Repeating what I said in this post:

The lambda function consists of three parts, contained in three different types of brackets. It starts with square brackets – [] – moves on to round brackets – () – then finishes off with curly brackets – {}.

The three parts correspond to the three essential features of the function object we created for solution #2:

  1. The value(s) passed into the constructor of the function object appear in the square brackets – []
  2. The value(s) passed into operator () appear in the round brackets – ()
  3. The code in operator () appears in the curly brackets – {}

If we take our three options: a custom function object; std::bind wrapping a function and a lambda expression, we can find the commonality between them:

  • f is the value passed in to the constructor of our function object.
  • f is the value bound by std::bind.
  • f is the value we place in the square brackets of the lambda (in standardese, the square brackets are called a lambda-capture, f is a capture-list with a single element).
  • i is the value passed to the function call operator defined on the callable object. An object of type Adder is a callable object, the result of std::bind is a callable object and a lambda expression is a callable object.
  • { return i + f; } is the code that we actually want to execute. For std::bind the code we want to execute has to be wrapped in a function, for a custom function object or a lambda we can just use the code directly.

If we want to, we can invoke the function call operator on a lambda directly:

float f = functionReturningFloat();

double d = [ f ]( int i )
{
    return i + f;
}( 7 );

(we probably don’t want to, although I am sure somebody has already come up with a use for this)


A lambda-expression is an expression, and expressions have a type. We tried to work out what the type of the result of std::bind was last time – let’s try the same exercise with a lambda expression.

Section 5.1.2 of the standard talks about the type of a lambda expression. The type is a unique, unnamed nonunion class type. The standard tells us plenty about the properties of the type without ever revealing what the type actually is. As with std::bind I can force a compiler error and see what type the compiler is using. For Visual Studio I get this:

test_bl5_1::<lambda_d35a8a85fcf19231607c0773125e04ed>

For GCC I get this:

test_bl5_1()::__lambda1

(The lambda in question is declared in function test_bl5_1)

As with the type of the return value of std::bind, we are clearly not meant to use these types deliberately – the standard is telling us so, they are different between different compilers, in the case of Visual Studio, the “type” isn’t really a type at all – it is some implementation magic, the GCC type starts with an underscore, and, in case I haven’t mentioned it enough, the standard tells us that we can’t use these types. Believe the standard – it’ll make life easier. This diversion into the actual types of std::bind and lambda has been exactly that – a diversion from our main purpose of actually using these things.

So we are in the same situation as we were with std::bind. We can’t use the type directly, we don’t know what it is. We do know what the properties of the type are – in particular we can apply operator () to objects of that type.

We can use the type deduction facilities of C++11 to handle lambdas without needing to know their type. We have already used a lambda with a templated function (std::transform) and auto and decltype work exactly as we would expect:

auto fn = [ f ]( int i ){ return i + f; };
typedef decltype( fn ) SingleArgumentAdd;

Last week we looked at std::function and saw that std::function can wrap a callable object. Since a lambda expression is a callable object, std::function can wrap a lambda expression:

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

SingleArgumentAdd fn;

fn = [ f ]( int i ){ return i + f; };

std::cout << fn( 42 ); // And of course we can call it

If we need to save callable objects, std::function is the way to go. std::function can be the type of a member variable, it can be passed to and returned from functions. std::function is our all purpose "thing that supports operator ()"

Finally, there is one thing that I have glossed over. When I was describing the commonality between std::bind, a function object and a lambda I looked at every variable and every type except one - the type of the result of invoking operator ().

If we look at the lambda we've been working with, we can see that if we remove the capture block (the bit inside square brackets) we have something that is very close to being a function declaration:

( int i )
{ 
    return i + f;
};

It is missing the function name (which is what we'd expect - a lambda is an unnamed function), but it is also missing the return type. In this case, because the lambda consists of a single statement that is just a return we don't have to specify the return type, the compiler will deduce it for us - that gives us another place where the compiler does type deduction.

In our case, the result of i + f is a double - that is exactly what we want. But what if we did need a return type, either because the type of the expression was not what we wanted, or because we had more complicated code within the lambda?

Lambdas use the new trailing-return-type syntax so if we wanted to be explicit about the function call operator returning a double we would write this:

[ f ]
( int i ) -> double
{ 
    return i + f;
};

That's it for this post, and almost it for this series. I have one more post in mind which will tie up a few loose ends then I'll move on to something else.

Quote of the week – object oriented vs. functional programming

Object oriented programming makes code understandable by encapsulating moving parts. Functional programming makes code understandable by minimizing moving parts.

Michael Feathers

This week’s quote comes with an article, to be specific, this piece by John Carmack on functional programming. There is plenty to like in the article but two points in particular struck me:

  1. A function doesn’t have to be 100% pure to get many of the benefits of purity. Of course you don’t want to use the fact that it’s not 100% pure as an excuse for making it even less pure either.
  2. A more functional programming style often results in more parameters to a function.

A functional style does lead to more parameters, but as Carmack notes, it is much easier to test the functions in isolation. Also, if a function needs a certain set of data to do its job, it has to obtain that data from somewhere. If the data doesn’t come from the arguments passed in, it either comes from globals, or member variables of a class, and that leads us right into the issues Carmack describes with state – storing it and updating it. There are definitely costs associated with all the options, but I am beginning to think that a couple more parameters on a function might not be the worst thing in the world.

std::bind and lambda functions 4

I have been sloppy in my use of language. I am going to try to be less sloppy. Instead of using function or function object (and I suspect getting them reversed in some cases) I am going to start using the standard-approved term callable object. As always, the standard provides a strict definition, for us it will be good enough to say that a callable object allows us to apply operator() to it. Callable objects include functions, function objects, whatever it is we get back from std::bind, and lambda functions.

In part 3 I said I would reveal the return type of std::bind. If we look up the relevant section of the standard (20.8.9.1.2) we see the following declaration:

template
unspecified bind(F&& f, BoundArgs&&... bound_args);

Unspecified. That doesn’t seem terribly helpful. Of course, this being the standard, there is a definition for unspecified. Section 1.3.25 of the standard states:

unspecified behavior behavior, for a well-formed program construct and correct data, that depends on the implementation [ Note: The implementation is not required to document which behavior occurs. The range of possible behaviors is usually delineated by this International Standard. —end note ]

Still not terribly helpful. Perhaps we can find a way to determine the type anyway. By setting up an error condition I can force the compiler to tell me what type it is actually using for the result of std::bind. Assuming that I am binding add in the same way I have been doing, on Visual Studio 2013 I get this for the type:

std::_Bind<true,double,double (__cdecl *const ) (int,float),int,float &>

and on GCC I get this:

std::_Bind_helper<false, double (&)(int, float), int, float&>::type 
{aka std::_Bind<double (*(int, float))(int, float)>}

There are only three problems.

  1. The types are different on the two different compilers (because they use different implementations of the standard library).
  2. Both compilers use types beginning with an underscore – any name starting with an underscore is reserved for the implementation (see 17.6.4.3.2 in the standard).
  3. The standard has already told us clearly and explicitly that the type is unspecified – it can vary between compilers, it can vary between releases of the same compiler, it can vary between updates to the standard library. We cannot rely on the type staying the same.

However much we twist and turn, determining the actual type of the returned value from std::bind is a non starter. Even when we can find out what the type is, we can’t rely on it.

Fortunately, C++11 gives us a way of avoiding knowing the actual type – we can do type deduction.

We can assign the result of std::bind to a variable using auto:

auto fn = std::bind( add, _1, f );

That works for the situations where we can use auto, but doesn’t help us when we want to store the object in a (non-template) class or pass it to a (non-template) function – we can’t declare a parameter as auto.

We’ve already seen one of the other ways we can use type deduction with std::bind. We used std::bind successfully with std::transform, because std::transform is a template function and does type deduction. If we are passing the result to a template function or template class we might can use the result of std::bind without ever needing to know what type it is.

There is a third option. C++11 added decltype. You hand decltype an expression (which it does not evaluate, it just uses it to deduce the type), and it gives us the type of that expression. For example:

auto fn = std::bind( add, _1, f );
typedef decltype( fn ) SingleArgumentAdd;

decltype( fn ) evaluates to the type of fn (at compile time), and we typedef the result to SingleArgumentAdd. This is useful, finally we have an actual type (as in type of an object) that we can type (as in hit keys on the keyboard). It still isn’t perfect though. The example above only works within the current scope – we can’t put the typedef into a header file (at least not without doing other things in the header file that we really shouldn’t). Turns out there is a solution to this problem too. We can do this:

typedef decltype( 
    std::bind( 
        add, 
        _1, 
        std::declval< float >() ) ) SingleArgumentAdd;

We have something new – std::declval. Let’s work out what’s going on here. decltype requires an expression. In our first example of its use we gave it the expression fn. In the second example we want to give it an expression involving std::bind. This means that we need to pass arguments of the right type to std::bind. The first argument is easy – it’s the callable object that we’re trying to wrap. The whole point of this exercise is to wrap that callable object so we need to have it visible. The second argument is also easy, it’s the placeholder _1. For the third argument we must pass it a float value (not the float type, but a value of type float). If we happened to have a float variable in the current scope we could use that. We could also pass it a float constant such as 1.0f. The constant would work well here because it is a nice simple value, but what if it wasn’t a float? What if it was something which required several arguments to its constructor? We don’t want an actual value, just something that represents the value and has the correct type. For that, we can use std::declval. To quote Stroustrup:

The intent is to use declval< X > as a type where the type of a variable of type X is needed.

(The C++ Programming Language Fourth Edition, section 35.4.2)

std::declval does return a value, but we cannot use that value. Since decltype does not evaluate its expression we are safe.

Having jumped through all of those hoops to get the type SingleArgumentAdd it turns out to be a pain to use. When we looked at the definition of unspecified from the standard it stated:

The range of possible behaviors is usually delineated by this International Standard.

That range of possible behaviors for SingleArgumentAdd is pretty small. We already know that the result of std::bind can have operator () applied to it, the standard adds requirements for MoveConstructable and CopyConstructable, but it adds no other requirements. In particular, default construction and assignment are not available:

float f( functionReturningFloat() );
float f1( otherFunctionReturningFloat() );

SingleArgumentAdd fn; // Error, cannot default construct

SingleArgumentAdd fn2 = std::bind( add, _1, f );

fn2 = std::bind( add, _1, f1 ); // Error, cannot assign

Even if we could default construct and assign SingleArgumentAdd it would still be unsatisfactory. Our current definition of SingleArgumentAdd only lets us store the return value from std::bind. Wouldn’t it be nice to have a type that will allow us to store any callable object that has the correct call signature.

A call signature is the name of a return type followed by a parenthesized comma-separated list of zero or more argument types. – C++11 standard, section 20.8.1

The C++11 standard gives us exactly what we want – std::function. Let’s set up a function with the correct parameter and return types:

double singleArgAdd( int i )
{
    return i + 7;
}

Now let’s look at what we can do with std::function:

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

SingleArgumentAdd fn; // We can default construct it

fn = std::bind( add, _1, f );  // We can assign the result
                               // of std::bind to it

fn = singleArgAdd;  // We can assign a function 
                    // of the correct signature to it

std::cout << fn( 42 ); // And of course we can call it

std::function wraps a callable object. When we call operator () on a std::function object, it calls operator () on the callable object it is wrapping, known as the target. std::function therefore needs to know what the return type and the parameter types are for operator (). The syntax that we use for the call signature is very similar to the syntax for declaring a function pointer - std::function< double( int ) >

Finally, an uninitialized std::function object is known as empty (and is even displayed like that in the Visual Studio debugger). If we attempt to call an empty std::function, it will throw the exception std::bad_function_call. Fortunately, it is easy to test a std::function object to see if it is empty or not:

SingleArgumentAdd fn2;

// Some code that might or might not assign something to fn2

if( fn2 )
{
    fn2( 42 );
}

That's it for this week, next week we will finally get to lambda functions.

Quote of the week – overloading

overloading n. 1 Semantics Ganging up on a poor signifier until it collapses from excessive signification. 2 OOP Assigning unlikely meaning to well-known operators. Ideally, for maximum confusion, the overloading definitions should be hidden.

Stan Kelly-Bootle The Computer Contradictionary

Sadly, Stan Kelly-Bootle died in April 2014. He was a major figure in the computer world and the folk song world. Obituaries can be found here, here and here.

I could quote Stan Kelly-Bootle infinitely, and when I say “infinitely” I do mean infinitely. The Devil’s DP Dictionary gives the following definition:

recursive adj. See RECURSIVE.

although this was later modified in The Computer Contradictionary to:

recursive adj. while (unclear) { unclear--; See RECURSIVE }

Of course the definition of operator -- is overloaded and hidden.

Unfortunately The Devil’s DP Dictionary and The Computer Contradictionary are both out of print but there are plenty of second hand copies available from Amazon or Alibris.

std::bind and lambda functions 3

In part 2 we saw that by wrapping a function inside a function object we could take a function that requires two arguments and turn it into a function object that requires one argument. The code we ended up with looks like this:

class Adder
{
public:
    Adder( float f )
    : f_( f )
    {}
    
    double operator()( int i ) const
    {
        return add( i, f_ );
    }
    
private:
    float f_;
};
std::vector< int > v_i( functionReturningVector() );
std::vector< double > v_d;

float f = functionReturningFloat();

std::transform( 
    std::begin( v_i ), 
    std::end( v_i ), 
    std::back_inserter( v_d ), 
    Adder( f ) );

There is a problem here – we had to write a lot of boilerplate in order to wrap one function – Adder is 15 lines long, the call to add is a single line. Fortunately, C++11 gives us a couple of ways to get the same effect but with much less boilerplate. We can use std::bind to adapt add as follows:

std::vector< int > v_i( functionReturningVector() );
std::vector< double > v_d;

float f = functionReturningFloat();

std::transform( 
    std::begin( v_i ), 
    std::end( v_i ), 
    std::back_inserter( v_d ), 
    std::bind( add, std::placeholders::_1, f ) );

[ Aside:

I have put in the fully scoped name of the placeholder _1 just to show where it comes from. Even though I am normally a fan of using the fully qualified name this one is just so ugly I will assume that:

using namespace std::placeholders;

is in use for the rest of my examples. This simplifies our loop to:

std::transform( 
    std::begin( v_i ), 
    std::end( v_i ), 
    std::back_inserter( v_d ), 
    std::bind( add, _1, f ) );

End aside ]


We have two std::transform loops, one of which uses Adder( f ), the other of which uses std::bind( add, _1, f ).

We know what the code Adder( f ) does. It creates a function object of type Adder which implements operator () to call add with one argument that comes from the function call operator, and another argument that was supplied in the constructor. We need the code std::bind( add, _1, f ) to do something very similar.

Let’s remove std::bind from the context of std::transform so we can focus on one thing at a time. Here’s some code we can use to look at std::bind in isolation:

float f = functionReturningFloat();
auto fn = std::bind( add, _1, f );
std::cout << fn( 7 ) << "\n";

The call to std::bind returns a function object that we assign to the variable fn. I am using auto because I don't want to get into the question of what the type of the return value of std::bind is yet (we'll look at it later). fn is a function object that takes a single argument to its function call operator. We can therefore invoke the function call operator with a single argument - fn( 7 ) and write out the result, which will be a double because the return value of add is a double.

There are a lot of moving parts here. I am going to walk through them.

We have three functions in play:

  • add The function we ultimately want to call. The function we are going to wrap.
  • fn The function (object) that wraps add. This is the thing that converts a two argument function into a single argument function.
  • std::bind The function that creates fn from add.

We call std::bind to create fn. Later we call fn which in turn will call add.

The function we want to wrap - add - is a two argument function. Anything that calls add must call it with two arguments. Therefore, fn must call add with two arguments. Since std::bind is creating fn, std::bind must know what the two arguments are. When we call std::bind we not only supply it with the function to be wrapped - add - we also supply it with the two arguments that must be passed to add. These two arguments are _1 and f.

The second argument is easy. f is a variable of type float and we already know that the second argument to add must be of type float. It all matches just as it should.

The first argument is more interesting - _1. Arguments of the form _n are called placeholders, that's why they live in the std::placeholders namespace. The placeholder argument links the argument we pass when we call fn to the first argument that gets passed to add. Let's look at the code again:

auto fn = std::bind( add, _1, f );
std::cout << fn( 7 ) << "\n";

_1 says "take the first argument that is passed to fn and pass it to add as the first argument". In this example, when we call fn( 7 ), that ultimately results in a call to add( 7, f )

Any argument that is passed to fn can be passed on to add in any position. The placeholder we use (_1, _2 etc.) tells us which argument to use from the argument list passed to fn::operator (). The position of the placeholder in the call to std::bind tells us which position that argument will end up in when we call add.

Let me lay out the code slightly differently:

float f = 10.0f;
auto fn = std::bind( 
    add,        // add is the function we are wrapping
    _1, f       // add has two arguments therefore 
                // we supply two arguments here.
    );

// At this point, std::bind has been called but 
// add and fn have not been called

std::cout << fn( 7 ) << "\n";   // Call fn, which in 
                                // turn calls add.

Here's an example with a different placeholder:

float f = 10.0f;
auto fn = std::bind( add, _2, f );
std::cout << "result = " << fn( 7, 12 ) << "\n";

We are now using placeholder _2. This means that we have to supply the call to fn with two arguments (and if we don't we get an unfriendly error message). The output of this piece of code is:

result = 22

showing that the second argument from the call fn is the one that is used. Of course this is a nonsensical example because there is no point in passing two arguments to fn in the first place - the first argument is ignored so there was no point in supplying it.

There are plenty of other cute tricks we can play. Since an int is convertible to a float we can do this:

auto fn = std::bind( add, _1, _2 );
std::cout << "result = " << fn( 7, 12 ) << "\n";
result = 19

or this:

auto fn = std::bind( add, _2, _1 );
std::cout << "result = " << fn( 7, 12 ) << "\n";
result = 19

Since add is commutative the result is the same - I am just showing that we can change the order in which the arguments are supplied to std::bind (and therefore the order of the arguments supplied to add).

We can use a placeholder more than once:

auto fn = std::bind( add, _1, _1 );
std::cout << "result = " << fn( 7 ) << "\n";
result = 14

Or not use a placeholder at all (yes, doing this in real life is a waste of time, I just want to show all the possibilities):

auto fn = std::bind( add, 6, 5 );
std::cout << "result = " << fn() << "\n";
result = 11

I can call the object returned from std::bind directly:

float f = 10.0f;
double d = std::bind( add, _1, f )( 10 );
std::cout << "result = " << d << "\n";
result = 20

For a not-pointless example, back in this post I used placeholders to swap the order of arguments to a comparator in order to reverse the sorting order:

std::partial_sort( 
    ReverseIter( pivotElementIterator ), 
    ReverseIter( displayBegin ), 
    ReverseIter( std::begin( files ) ), 
    std::bind( comparator, _2, _1 ) );

Errors

There are a number of things we can do wrong.

We can specify too many arguments in the std::bind call. add takes two arguments, let's try giving it three:

double d = std::bind( add, _1, f0, f1 )( 10 );

Visual Studio gives the surprisingly helpful error message:

// error C2197: 'double (__cdecl *)(int,float)' : too many arguments for call

The message from GCC is longer and more confusing, but does include the words "too many arguments to function".


We can specify too few arguments in the std::bind call:

double d = std::bind( add, _1 )( 10 );

I get the following (also very helpful) error message from Visual Studio:

error C2198: 'double (__cdecl *)(int,float)' : too few arguments for call

As before, the GCC message is more verbose, but does include the words "too few arguments to function".


We can specify too few arguments in the call to fn:

auto fn = std::bind( add, _1, f );
std::cout << "result = " << fn() << "\n";

Sadly the resulting error message is almost incomprehensible.


Specifying too many arguments in our call to fn does not result in an error:

auto fn = std::bind( add, _1, f );
std::cout << "result = " << fn( 
    7, 15.6, 
    std::complex< double >( 1.0, 2.0 ) ) << "\n";

As always, just because you can do something doesn't mean that you should do it.


We can give an argument of the wrong type to std::bind:

std::complex< double > c( 1.0, 2.0 );
auto fn = std::bind( add, _1, c );
fn( 7.0 );   // Error reported here
error C2664: 'double (int,float)' : cannot convert argument 2 from 'std::complex' to 'float'

Interestingly, the error is not reported until we try and call fn.


We can give an argument of the wrong type when we call fn:

std::complex< double > c( 1.0, 2.0 );
auto fn = std::bind( add, _1, f );
fn( c );
error C2664: 'double (int,float)' : cannot convert argument 1 from 'std::complex' to 'int'

Finally, let's get back to our std::transform call:

std::transform( 
    std::begin( v_i ), 
    std::end( v_i ), 
    std::back_inserter( v_d ), 
    std::bind( add, _1, f ) );

std::transform is a function. When we call a function, we evaluate all of the arguments to that function. One of those arguments is the result of a call to std::bind. As we have seen, the result of calling std::bind is a function object that wraps add and turns it into a single argument function. Look at the definition of std::transform (this is from the GCC implementation. I have removed some error checking and done some reformatting):

template<
    typename _InputIterator, 
    typename _OutputIterator,
    typename _UnaryOperation >
_OutputIterator
transform(
    _InputIterator __first, 
    _InputIterator __last,
    _OutputIterator __result, 
    _UnaryOperation __unary_op)
{
    for (; __first != __last; ++__first, ++__result)
        *__result = __unary_op(*__first);
    
    return __result;
}

std::transform loops from __first to __last, and each time around the loop invokes the function call operator on __unary_op with a single argument - __unary_op(*__first). We must supply std::transform with a thing-that-supports-the-function-call-operator-taking-a-single-argument. That is exactly what we have done using std::bind.

More to come in part 4, including the mysterious type of the return value of std::bind.

Quote of the week – design

Without requirements or design, programming is the art of adding bugs to an empty text file.

Louis Srygley

If I were a cynical person I would point out that this quote implies that programming is better with requirements and design, an implication that is too often false. Fortunately I am not a cynical person, so I won’t mention it.

Design of software has always interested me – not just coming up with the design, but also communicating the design and modifying it as the project inevitably evolves. How do you get a design from person A’s head into the heads of persons B-Z?

What header?

I am bad at remembering what header file I need to include to use which standard library facility. I can handle the obvious ones like vector, but that still leaves many where I have to go and look it up. To make looking it up a little easier, I have created a page that lists all of the symbols in the standard library sorted by various criteria – including what header file they are in. There is a C++98 version and a C++11 version. I am sure there are mistakes in the pages, I will correct any mistakes I am told about.

C++11 Standard Library Symbols
C++98 Standard Library Symbols

std::bind and lambda functions 2

In part 1 we looked at various things we can do with functions in C. Since C++ is mostly a superset of C we can do those things in C++ as well. C++ also gives us some other ways of creating functions though. Let’s dispense with the easy options quickly then get on to the more interesting possibilities.


A function in a namespace

namespace arithmetic
{
    double add( int i, float f )
    {
        return i + f;
    }
}
double (*pFn)( int, float ) = arithmetic::add;

A static function in a class

class TestClass
{
public:
    static double add( int i, float f )
    {
        return i + f;
    }
    
};
double (*pFn)( int, float ) = TestClass::add;

Nothing tricky about putting functions into a namespace, or a class acting as a namespace.


Overloaded functions

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

double add( int i, double f )
{
    return i + f;
}
double (*pFn)( int, float ) = add;

Even overloaded functions work just as we’d expect. Section 13.4 of the C++11 standard states:

The function selected is the one whose type is identical to the function type of the target type required in the context.

Let’s not get too confident though, overloads are going to return to trouble us later.


Pointer to member function

class TestClass2
{
public:
    double add( int i, float f )
    {
        return i + f;
    }
    
};

Ignore the fact that add makes absolutely no sense as a member function (very few of these examples make any sense outside of a narrow context).

What is the type of a pointer to member function? We already know what the type of add would be if it wasn’t a member function:

double (*)( int, float );

The key thing missing is the name of the class of which the function was a member. The type has to specify the class for type safety – you don’t want anyone trying to call the add function for an object that doesn’t even have an add function (and yes, you can force this with casting, but you can force almost anything with casting). Given that * is in the place where the function name used to go, we put the class name in the obvious (ish) place:

double (TestClass2::*)( int, float );

We can write this code to get the address of the add function:

double (TestClass2::*pFn)( int, float ) = &TestClass2::add;

And we can call it like this:

TestClass2 c;
(c.*pFn)( 10, 20.0f );
TestClass2* p = &c;
(p->*pFn)( 10, 20.0f );

We have two new operators .* and ->*.

Notice that this time we had to use the address-of operator & to get the address of the function and, because the function call operator () is higher precedence than .* and ->*, we need the brackets around c.*pFn and p->*pFn.

(This also works with virtual functions).


There is one more trick we need to know about before we can start applying our knowledge to std::bind and lambda. At the beginning of part 1 I wrote:

The round brackets are known as the function call operator.

At the time, referring to the function call operator might have seemed like overkill. It’s a C function, you just call the thing by passing in the arguments in the brackets. That nomenclature is important though because C++ supplies us with a function call operator that we can use as a member function of a class:

class Adder
{
public:
    double operator()( int i, float f ) const
    {
        return add( i, f );
    }
    
};

(There is a reason why I am calling the add function rather than just doing the addition correctly – that reason will become apparent later).

We call the member function operator() by applying the function call operator to an object of type Adder :

Adder a;
a( 10, 20.0f );

While describing a function in part 1 I said:

we take a thing with a name … and apply an operator – () – to it.

Well, that’s what we have here. We have a thing with a name (a) and we’re applying the function call operator (()) to it. That calls the member function operator().

We have a thing that is acting like a function but is actually an object. It is often known as a function object or functor. At first glance a function object seems like a rather heavyweight way of creating a function, but objects have a really useful property – they can store state.

Let’s look at what we can do with that property of storing state. We don’t have to pass in both arguments to operator(), we can have one of the arguments specified at construction time:

class Adder
{
public:
    Adder( float f )
    : f_( f )
    {}
    
    double operator()( int i ) const
    {
        return add( i, f_ );
    }
    
private:
    float f_;
};
Adder a( 20.0f );
a( 10 );

Again, this just looks like a heavyweight way of creating a function-like thing. It’s more work, it’s not as convenient to call – why should we bother? We bother because we have taken a function that takes two arguments to the function call operator – add – and turned it into a function (object) that takes a single argument to the function call operator. The second argument is supplied in the constructor. This is the C++ version of currying.

The one-argument version is useful because there are algorithms that expect a function that takes a single argument, for example the single source sequence version of std::transform :

std::vector< int > v_i( functionReturningVector() );
std::vector< double > v_d;

float f = functionReturningFloat();
Adder a( f );
std::transform( 
    std::begin( v_i ), 
    std::end( v_i ), 
    std::back_inserter( v_d ), 
    a );

We don’t even need to create a named Adder object, we can just use a temporary:

std::transform( 
    std::begin( v_i ), 
    std::end( v_i ), 
    std::back_inserter( v_d ), 
    Adder( f ) );

The call to std::transform is equivalent to doing this:

for( 
    std::vector< int >::iterator i( std::begin( v_i ) ); 
    i != std::end( v_i ); 
    ++i )
{
    v_d.push_back( add( *i, f ) );
}

And this is why the fact that we took a two argument function and turned it into a single argument function is important. std::transform requires a single argument function. By wrapping add in a function object and specifying the second argument in the constructor we ended up with a single argument function (a unary operation in standardese).

If we take a look at the declaration of std::transform in the standard (again, just the single-source-sequence one), we see this:

template<
    class InputIterator, 
    class OutputIterator,
    class UnaryOperation >
OutputIterator
transform(
    InputIterator first, 
    InputIterator last,
    OutputIterator result, 
    UnaryOperation op);

The final parameter of the function std::transform is a unary operation – it takes one argument. Internally, std::transform is going to use the function call operator on op, i.e. it is going to perform op( elem ) for each element in the input sequence. It is all templated, and op follows the normal rules when passing an object to a templated parameter – whatever functions are called on op must be supported by the type of op type. Since the function that std::transform calls is operator() with a single argument, the type of op must support that. We know of two “things” in C++ world that can support the function call operator – functions and function objects.

What I have been trying to say in multiple different ways is that by wrapping a function (in this case add) in a function object we can turn a function into something requiring fewer arguments at the point where the function call operator is invoked. Of course the extra arguments have to come from somewhere, and in this case they are specified in the constructor of the function object. We can give the standard algorithm exactly what it needs (an operator() with the right number and type of parameters) but supply any necessary extra paraeters via the constructor of the function object.

Here’s another example. Let’s take the file metadata structure I used in a previous post:

struct FileMetaData
{
    std::string fileName_;
    std::string directory_;
    
    std::size_t size_;
    std::time_t lastWriteTime_;
};

Assume we have an unsorted vector of file metadata objects and we want to search for a file with a given file name. std::find_if looks like the obvious choice since it lets us specify our own predicate for the search.

It seems like this function would be useful:

bool compareFileName( 
    FileMetaData const& metaData, 
    std::string const& fileName )
{
    return metaData.fileName_ == fileName;
}

compareFileName will be useful, but it is a two argument function and std::find_if takes a UnaryPredicate. Unary means it expects a single argument, and according to Merriam-Webster a predicate is:

something that is affirmed or denied of the subject in a proposition in logic

For our purposes that comes down to “something returning a bool”. compareFileName is a predicate (it will affirm or deny whether the file names match), but it is not unary.

We’re going to use our “wrap it in a function object” trick to turn compareFileName into a single argument function (object):

class CompareFileName
{
public:
    CompareFileName( std::string const& fileName )
    : fileName_( fileName )
    {
    }
    
    bool operator()( FileMetaData const& metaData ) const
    {
        return compareFileName( metaData, fileName_ );
    }
    
private:
    std::string fileName_;
};

Then we can use CompareFileName like this:

std::vector< FileMetaData > files( getFiles() );
std::string fileNameToFind( getFileName() );

std::vector< FileMetaData >::iterator i(
    std::find_if(
        std::begin( files ),
        std::end( files ),
        CompareFileName( fileNameToFind ) ) );

There is one more thing. When we looked at overloaded functions before we had no problem assigning them to a function pointer. If we try and use overloaded functions in an algorithm we run into trouble.

Here is a pair of overloaded functions:

double negate( int i )
{
    return -i;
}

double negate( float f )
{
    return -f;
}

And here is a way in which we might want to use the integer version:

std::vector< int > v_i( functionReturningVector() );
std::vector< double > v_d;

std::transform( 
    std::begin( v_i ), 
    std::end( v_i ), 
    std::back_inserter( v_d ), 
    negate );

Just using the name of the function directly doesn’t work, we get this error message from Visual Studio:

error C2914: 'std::transform' : cannot deduce template argument as function argument is ambiguous

How come it worked before but doesn’t work now? The reason it worked before was because of this clause in the standard:

The function selected is the one whose type is identical to the function type of the target type required in the context.

The important words are target type. When we are supplying an argument to a template function we don’t know what the target type is. We can’t have a target type until we know the function type, but in order to pick the right function (and hence find out its type) we need to know the target type.

There are at least three ways around this. One is to assign the function to a function pointer where we know the target type and therefore won’t get an error:

double (*pNegateFn)( int ) = negate;

std::transform( 
    std::begin( v_i ), 
    std::end( v_i ), 
    std::back_inserter( v_d ), 
    pNegateFn );

Secondly, we can use what is possibly the most legitimate cast ever:

std::transform( 
    std::begin( v_i ), 
    std::end( v_i ), 
    std::back_inserter( v_d ), 
    static_cast< double (*)( int ) >( negate ) );

And finally we can specify the template arguments to std::transform explicitly. We don’t normally do this with functions, but in this case it gives us the target type that the compiler is looking for:

std::transform< 
  std::vector< int >::const_iterator, 
  std::back_insert_iterator< std::vector< double > >,
  double (*)( int ) >( 
    std::begin( v_i ), 
    std::end( v_i ), 
    std::back_inserter( v_d ), 
    negate );

Note that I had to specify the type of std::back_inserter for this to compile. When you are specifying template arguments explicitly you need to get them right.

In practice I rarely run into problems with overloaded functions, when I do, I use static_cast to get around them.


We’ve reached the end of part 2 and still haven’t talked about std::bind or lambda. At least we’re looking at the right language now, and we have laid all of the groundwork for the next exciting episode where I promise we will get to std::bind (and maybe lambda).