Type-erasure and lambda expressions

Type-erasure is a well known and documented topic in C++. Just google ‘type-erasure C++’ and the first page of results will present articles discussing the topic from simple examples to advanced scenarios. Oh, and be sure to have C++ in the query since type-erasure in Java means a completely different thing.

Many of these articles create some kind of Variant type that is capable of holding objects whose type is defined and known upfront. In this post I’m creating something that can hold and later invoke a capturing lambda expression (whose type is not defined by standard). This is what std::function does (and much more), and I was wondering what magic might happen inside std::function. There are no new concepts in this post compared to those articles, but handling lambdas is something (I think) worth writing about.

Code in this post is based on this stackoverflow question, and doesn’t meant to be solid and conforming to the highest C++ standards. I would like to present the key ideas with code as simple and understandable as possible.

Problem statement

I would like to create a C++ something that is capable of holding (capturing) lambdas, and invoke them later. Capturing is an important point since non-capturing lambdas are in fact just unnamed functions which can be ‘stored’ in a function pointer, problem solved. 🙂
Problem statement in code:

#include <iostream>
using namespace std;

int main()
{
    Holder<bool(int)> holder;
    cout << boolalpha;

    {
        // both i, and the lambda exist in local scope, and 
        // die when the scope is closed
        int local=5;
        holder.set([local](int arg)->bool 
        { 
             cout << "captured: " << local 
                  << ", arg: " << arg 
                  << endl;
             return local==arg; 
        });
    }

    bool result = holder.call(5);
    cout << "equal: " << result << endl;

    result = holder.call(1);
    cout << "equal: " << result << endl;

    return 0;
}

// Outputs:
// captured: 5, arg: 5
// equal: true
// captured: 5, arg: 1
// equal: false

First steps

From the code it’s obvious that the ‘C++ something’ is a template class with a function signature as template parameter: returnType(argumentTypes). Template specialization and variadic templates give a nice way to extract type information from this signature:

// blank template class
template<typename T>
class Holder { };

// specialized one with call signature
template<typename RetType, typename... ArgsType>
class Holder<RetType(ArgsType...)> 
{
public:
    RetType call(ArgsType... args);
};

Now, all we need to do is implement set() and call(). There are 2 type-erasure techniques I know of, the basic principle is the same for both: store a generic object and use a mechanism to restore the original type on invocation.

Type-erasure based on polymorphism

This is the more common case: Holder has an inner class hierarchy consisting of a base class with an abstract virtual call() method, and a templated derived class which perform the actual invocation. Holder has a base pointer and virtual method calls do the rest. Note that the lambda expression must be copied, since it’s deleted when the defining scope exits.

template<typename RetType, typename... ArgsType>
class Holder<RetType(ArgsType...)> 
{
    struct InnerBase 
    {
       virtual RetType call(ArgsType... args) = 0;
       virtual ~InnerBase() = default;
    };
    
    template<typename T>
    struct Inner : InnerBase
    {
        T t;
        
        // creates a copy of t!
        Inner(const T& t) : t(t) {}
        
        virtual RetType call(ArgsType... args)
        {
             return t(args...);
        }
    };
    
    
public:
    RetType call(ArgsType... args)
    {
        return ptr->call(args...);
    }
    
    template<typename T>
    void set(const T& lambda)
    {
        unique_ptr<InnerBase> tmp(new Inner<T>(lambda));
        ptr = move(tmp);
    }
    
    unique_ptr<InnerBase> ptr;
};

Full example on GitHub.

Type-erasure with void*

This version doesn’t involve virtual methods, instead it uses a simple void* pointer to hold the copy of the lambda expression and another lambda to perform the type conversion on invocation. This later lambda is a non-capturing one so it’s stored as a simple function pointer. Actually one more lambda is needed to be able to properly delete the void* pointer. This case was handled correctly by the virtual destructor in the previous implementation.

template<typename RetType, typename... ArgsType>
class Holder<RetType(ArgsType...)> 
{
    void* lambdaPtr = nullptr;
    RetType (*caller)(void*, ArgsType...);
    void (*deleter)(void*);

public:
    RetType call(ArgsType... args)
    {
        return caller(lambdaPtr, args...);
    }
    
    template<typename T>
    void set(const T& lambda)
    {
        if (lambdaPtr)
            deleter(lambdaPtr);
        
        lambdaPtr = new T(lambda);
        caller = [](void* t,  ArgsType... args)->RetType 
        { 
            return (*static_cast<T*>(t))(args...); 
        };

        deleter = [](void* t) 
        { 
            delete(static_cast<T*>(t)); 
        };
    }
    
    ~Holder()
    {
        if (lambdaPtr)
            deleter(lambdaPtr);
    }
};

As you can see this version contains more boilerplate code, because the deletes are explicitly handled. Otherwise it’s functionally the same as the previous version. Full example on GitHub.

Improvment

As I mentioned these are not robust solutions, the SO answers are far better. Here are a few caveats that should hinder you from using the above code directly: 🙂

  • Arguments are simply passed to the stored lambda, which breaks move semantics, std::forward should be introduced in a few places
  • Const things should be const
  • Moves should be used to store the lambda expression, or else large captures are copied unnecessarily
  • Coping or moving the Holder class leads to surprises…
Advertisements

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