How does a lambda actually get assigned to a std::function<>?

[K. Frank]

Hello Group!

I'm looking for some insight into how an assignment such as:

std::function<int, (int, int)> f = [z](int x, int y){ return x + y
+ z; };

actually works under the hood.

I've been playing around with lambda using a mingw-w64 version
of g++: "g++ (GCC) 4.7.0 20110829 (experimental)".

According to the new c++11 standard, each lambda expression has
its own unique type. (I guess I can see the reason for this.)
If the capture list is empty, the language provides an implicit
conversion to a function pointer, but not if the capture list is
non-trivial. (This makes sense to me as well.)

So I'm assuming that the language doesn't convert a lambda with
a non-trivial capture list into any sort of useful type that
std::function might be able to get its hands on. I therefore
imagine that std::function must define some sort template conversion
operator that can be templatized on a variety of novel types,
including the unique type of the lambda.

I guess this would make sense, but I don't really see how the
details of this would work out. Does std::function wrap a
copy of or a reference to the actual instance of the lambda?
Presumably std::function doesn't know anything about capture
lists, so it would need the lambda to manage that.

One last question: If I try to assign, say, a double to a
std::function, I get a compiler error "cannot be used as a
function".

My thinking is that, in principle, source-based libraries
(i.e., template libraries where the code is in the included
header file) should be implementable solely using the core
language, without any additional compiler support, but that
an implementation is allowed to have additional compiler
support for efficiency, convenience, etc.

So, does this error message indicate that the g++ compiler
knows something special about std::function, or could I, in
principle, write my own template functional implementation,
and get the same kind of compiler errors?

A test program that illustrates some of this appears below.

Thanks for any insight.


K. Frank


***** test program *****
***** compiled with: g++ -std=c++0x -o tst tst.cpp *****

#include <iostream>
#include <typeinfo>
#include <functional>

int main() {

int z = 100;

// type of lambda
// prints out "typeid([z](int x, int y) { return x + Y +
z; }).name() = Z4mainEUliiE_"
std::cout << "typeid([z](int x, int y) { return x + Y + z; }).name()
= " << typeid([z](int x, int y) { return x + y + z; }).name() <<
std::endl;

// a new type...
// prints out "typeid([z](int x, int y) { return x + Y +
z; }).name() = Z4mainEUliiE0_"
std::cout << "typeid([z](int x, int y) { return x + Y + z; }).name()
= " << typeid([z](int x, int y) { return x + y + z; }).name() <<
std::endl;

// another new type...
auto lambda1 = [z](int x, int y) { return x + y + z; };

// prints out "typeid(lambda1).name() = Z4mainEUliiE1_"
std::cout << "typeid(lambda1).name() = " << typeid(lambda1).name()
<< std::endl;

// a type different from the lamdaa
std::function<int (int, int)> function1;

// prints out "typeid(function1).name() = St8functionIFiiiEE"
std::cout << "typeid(function1).name() = " <<
typeid(function1).name() << std::endl;

function1 = [z](int x, int y) { return x + y + z; };

std::cout << "function1 (10, 1) = " << function1 (10, 1) <<
std::endl;

double d = 1.2345;

// function1 = d;
// the above line fails with the compile error:
// error: '*
std::_Function_base::_Base_manager<_Functor>::_M_get_pointer<double>((*
& __functor))' cannot be used as a function

}

***** test program *****

 

[Alf P. Steinbach]

I'm looking for some insight into how an assignment such as:

std::function<int, (int, int)> f = [z](int x, int y){ return x + y
+ z; };

actually works under the hood.

Well, disregarding "actually", here's one possibility for your specific
example:


<code>
#include <iostream>
#include <vector>
#include <memory> // std::shared_ptr

class WrapperBase
{
public:
virtual ~WrapperBase() {}
};

template< class Functor >
class Wrapped
: public WrapperBase
{
public:
Functor f;

Wrapped( Functor const& _f ): f( _f ) {}
};

class MyFunc
{
private:
typedef int (*InvokerFunc)( void*, int, int );

std::shared_ptr< WrapperBase > pFunc_;
InvokerFunc invoker_;

template< class Functor >
static int invoke( void* pF, int x, int y )
{
return (reinterpret_cast< Wrapped< Functor>* >( pF )->f)( x, y );
}

public:
template< class Functor >
MyFunc( Functor const& f )
: pFunc_( new Wrapped< Functor >( f ) )
, invoker_( &invoke< Functor > )
{}

int operator()( int x, int y ) const
{
return invoker_( pFunc_.get(), x, y );
}
};

int main()
{
using namespace std;

MyFunc f = []( int x, int y ) -> int { return x*y; };
cout << f( 6, 7 ) << endl;
}
</code>


The technique used for the invoker function is called "type erasure",
and I believe it was developed (by the Boost guys) for just this
purpose, namely for the implementation of boost::function.


Cheers & hth.,

- Alf

 

[Alf P. Steinbach]

I'm looking for some insight into how an assignment such as:

std::function<int, (int, int)> f = [z](int x, int y){ return x + y
+ z; };

actually works under the hood.

Oh, sorry I forgot to mention, it's not an "assignment", it's
initialization, calling a constructor.

Cheers & hth.,

- Alf

 

[K. Frank]

Hello Alf!

Thank you for this and you previous reply.

I haven't yet absorbed what you wrote, but I do have a quick
question (inline, below).

I'm looking for some insight into how an assignment such as:

    std::function<int, (int, int)>  f = [z](int x, int y){ return x + y
+ z; };

actually works under the hood.

Oh, sorry I forgot to mention, it's not an "assignment", it's
initialization, calling a constructor.

But I could have written:

std::function<int, (int, int)> f;
f = [z](int x, int y){ return x + y + z; };

(as I did in my test program).

So now "f = ..." is an assignment. Does f (e.g., your MyFunc
or std::function) need a template assignment operator that can
be templatized on a lambda, or a conversion operator, or does
it just need the template constructor, which the compiler figures
out how to press into service as a conversion operator?

Cheers & hth.,

So far it has.

- Alf

Thanks again. I'm sure I'll be back with more questions after
I work through your first reply.


K. Frank

 

[K. Frank]

Hi Alf!

Thank you again. This all makes good sense.

I have some comments inline, and some follow-up questions at the
bottom.

I'm looking for some insight into how an assignment such as:

    std::function<int, (int, int)>  f = [z](int x, int y){ return x + y
+ z; };

actually works under the hood.

Well, disregarding "actually", here's one possibility for your specific
example:

<code>
#include <iostream>
#include <vector>
#include <memory>       // std::shared_ptr

class WrapperBase
{
public:
     virtual ~WrapperBase() {}

};

template< class Functor >
class Wrapped
     : public WrapperBase
{
public:
     Functor f;

     Wrapped( Functor const& _f ): f( _f ) {}

};

class MyFunc
{
private:
     typedef int (*InvokerFunc)( void*, int, int );

     std::shared_ptr< WrapperBase >      pFunc_;
     InvokerFunc                         invoker_;

     template< class Functor >
     static int invoke( void* pF, int x, int y )
     {
         return (reinterpret_cast< Wrapped< Functor>* >( pF )->f)( x, y );
     }

public:
     template< class Functor >
     MyFunc( Functor const& f )
         : pFunc_( new Wrapped< Functor >( f ) )
         , invoker_( &invoke< Functor > )
     {}

So just the template constructor for MyFunc is all you need
to support the conversion that takes place implicitly in
an assignment statement.

     int operator()( int x, int y ) const
     {
         return invoker_( pFunc_.get(), x, y );
     }

};

int main()
{
     using namespace std;

     MyFunc  f = []( int x, int y ) -> int { return x*y; };
     cout << f( 6, 7 ) << endl;}

</code>

The technique used for the invoker function is called "type erasure",
and I believe it was developed (by the Boost guys) for just this
purpose, namely for the implementation of boost::function.

So, in this context, does "type erasure" refer primarily to
the template class deriving from the non-template class:

template< class Functor > class Wrapped : public WrapperBase

coupled with the recovery of the type via reinterpret_cast in the
template function invoke:

return (reinterpret_cast< Wrapped< Functor>* >( pF )->f)( x, y );

?

Also I notice that if I comment out the code that applies the
function-call operator to the reinterpret-cast expression, I
can assign other things, for example, a double, to your MyFunc.

Am I right to assume that this is basically how boost::any is
implemented?

Cheers & hth.,

Yes, very much.

- Alf

Best.


K. Frank

 

[Peter Remmers]

Am 14.01.2012 22:24, schrieb Alf P. Steinbach:

I'm looking for some insight into how an assignment such as:

std::function<int, (int, int)> f = [z](int x, int y){ return x + y
+ z; };

actually works under the hood.

Well, disregarding "actually", here's one possibility for your specific
example:


<code>
#include <iostream>
#include <vector>
#include <memory> // std::shared_ptr

class WrapperBase
{
public:
virtual ~WrapperBase() {}
};

template< class Functor >
class Wrapped
: public WrapperBase
{
public:
Functor f;

Wrapped( Functor const& _f ): f( _f ) {}
};

class MyFunc
{
private:
typedef int (*InvokerFunc)( void*, int, int );

std::shared_ptr< WrapperBase > pFunc_;
InvokerFunc invoker_;

template< class Functor >
static int invoke( void* pF, int x, int y )
{
return (reinterpret_cast< Wrapped< Functor>* >( pF )->f)( x, y );
}

I think if the invoker took a WrapperBase*, a static_cast would be
sufficient, right?


Peter

 

[Alf P. Steinbach]

Am 14.01.2012 22:24, schrieb Alf P. Steinbach:

I'm looking for some insight into how an assignment such as:

std::function<int, (int, int)> f = [z](int x, int y){ return x + y
+ z; };

actually works under the hood.

Well, disregarding "actually", here's one possibility for your specific
example:


<code>
#include<iostream>
#include<vector>
#include<memory> // std::shared_ptr

class WrapperBase
{
public:
virtual ~WrapperBase() {}
};

template< class Functor>
class Wrapped
: public WrapperBase
{
public:
Functor f;

Wrapped( Functor const& _f ): f( _f ) {}
};

class MyFunc
{
private:
typedef int (*InvokerFunc)( void*, int, int );

std::shared_ptr< WrapperBase> pFunc_;
InvokerFunc invoker_;

template< class Functor>
static int invoke( void* pF, int x, int y )
{
return (reinterpret_cast< Wrapped< Functor>*>( pF )->f)( x, y );
}

I think if the invoker took a WrapperBase*, a static_cast would be
sufficient, right?

They do the same here, so I used reinterpret_cast for expressing more
clearly the intent: turning a bunch of bits into a pointer value.

But you're right, formally (as opposed to as exposition of the
principles) that code is ungood.

It relies on an in-practice assumption that a static_cast from
WrapperBase& down to Wrapped<T>& will not change the address. And for
other types this is not always the case. For example, if WrapperBase did
not have any virtual functions, and Wrapped<T> did, then with common
implementations that downcast would change the address.

So, to be utterly formally correct I should have written

return
(
static_cast< Wrapped< Functor>* >
(
reinterpret_cast< WrapperBase* >( pF )
)->f
)( x, y );

Here the static_cast is not the same as a reinterpret_cast (it could in
principle change the address). And formally the reinterpret_cast is here
casting back to the /original pointer type/, and so is safe. But I think
this is less clear for communicating the basic idea.


Cheers & hth.,

- Alf

 

[Alf P. Steinbach]

Hi Alf!

Thank you again. This all makes good sense.

I have some comments inline, and some follow-up questions at the
bottom.

I'm looking for some insight into how an assignment such as:

std::function<int, (int, int)> f = [z](int x, int y){ return x + y
+ z; };

actually works under the hood.

Well, disregarding "actually", here's one possibility for your specific
example:

<code>
#include<iostream>
#include<vector>
#include<memory> // std::shared_ptr

class WrapperBase
{
public:
virtual ~WrapperBase() {}

};

template< class Functor>
class Wrapped
: public WrapperBase
{
public:
Functor f;

Wrapped( Functor const& _f ): f( _f ) {}

};

class MyFunc
{
private:
typedef int (*InvokerFunc)( void*, int, int );

std::shared_ptr< WrapperBase> pFunc_;
InvokerFunc invoker_;

template< class Functor>
static int invoke( void* pF, int x, int y )
{
return (reinterpret_cast< Wrapped< Functor>*>( pF )->f)( x, y );
}

public:
template< class Functor>
MyFunc( Functor const& f )
: pFunc_( new Wrapped< Functor>( f ) )
, invoker_(&invoke< Functor> )
{}

So just the template constructor for MyFunc is all you need
to support the conversion that takes place implicitly in
an assignment statement.
Yes.

int operator()( int x, int y ) const
{
return invoker_( pFunc_.get(), x, y );
}

};

int main()
{
using namespace std;

MyFunc f = []( int x, int y ) -> int { return x*y; };
cout<< f( 6, 7 )<< endl;}

</code>

The technique used for the invoker function is called "type erasure",
and I believe it was developed (by the Boost guys) for just this
purpose, namely for the implementation of boost::function.

So, in this context, does "type erasure" refer primarily to
the template class deriving from the non-template class:

template< class Functor> class Wrapped : public WrapperBase

coupled with the recovery of the type via reinterpret_cast in the
template function invoke:

return (reinterpret_cast< Wrapped< Functor>*>( pF )->f)( x, y );

?

The latter.

The type is erased (no longer known), but the important info that it
carried is preserved in the function template instantiation.

Also I notice that if I comment out the code that applies the
function-call operator to the reinterpret-cast expression, I
can assign other things, for example, a double, to your MyFunc.

Am I right to assume that this is basically how boost::any is
implemented?

Most probably something very similar, and involving type erasure, yes.


Cheers,

- Alf

 

[Peter Remmers]

Am 15.01.2012 14:24, schrieb Alf P. Steinbach:

They do the same here, so I used reinterpret_cast for expressing more
clearly the intent: turning a bunch of bits into a pointer value.

But you're right, formally (as opposed to as exposition of the
principles) that code is ungood.

It relies on an in-practice assumption that a static_cast from
WrapperBase& down to Wrapped<T>& will not change the address. And for
other types this is not always the case. For example, if WrapperBase did
not have any virtual functions, and Wrapped<T> did, then with common
implementations that downcast would change the address.

I'd say it doesn't matter, as the (already snipped) construction of
pFunc is essentially a static_cast to the base. It should be well
defined to static_cast to a base class and then back to the derived
class. I think, even if the downcast changes the addres, then so did the
upcast before, so all is well.

So, to be utterly formally correct I should have written

return
(
static_cast< Wrapped< Functor>* >
(
reinterpret_cast< WrapperBase* >( pF )
)->f
)( x, y );

Here the static_cast is not the same as a reinterpret_cast (it could in
principle change the address). And formally the reinterpret_cast is here
casting back to the /original pointer type/, and so is safe. But I think
this is less clear for communicating the basic idea.

The reinterpret_cast would not be necessary at all if invoker() took a
WrapperBase* directly, instead of a void*. A WrapperBase* is what the
shared_ptr holds, and what operator() can forward as-is to the invoker.

Of course, one could argue that in your MyFunc example, you could drop
the shared_ptr and store the wrapper in a void*, as casting to void* and
back is equally well defined. MyFunc as it is would be ok with this, it
just needs a destructor that calls a deleter similar to the invoker,
which casts from void* to Wrapped<Functor>* and deletes the wrapper. But
a shared_ptr makes sense if you want to implement copy construction and
copy assignment for MyFunc, sharing the wrapped functor between instances.


Peter

 

[Alf P. Steinbach]

The reinterpret_cast would not be necessary at all if invoker() took a
WrapperBase* directly, instead of a void*. A WrapperBase* is what the
shared_ptr holds, and what operator() can forward as-is to the invoker.

Huh, I didn't even think of that.

So, I didn't really see everything in your earlier comment - blindness.


Cheers,

- Alf