foonathan::blog()

Thoughts from a C++ library developer.

Lazy evaluation of function arguments in C++

Sometimes you’re lazy. You know you need to do something, but don’t want to do it yet. You don’t need to do it right now, only at some later point. And maybe later it turns out that you don’t need to do the entire work, just a part of it or nothing at all! So if you’re eager and do it right now, you might do more work than needed.

The same applies to your code. Sometimes you do things even though it is not necessary. You call a function passing it some arguments that were expensive to calculate and then the function don’t need all of them due to some other arguments. Wouldn’t it be great to only calculate the arguments when they are actually needed?

This is called lazy evaluation of function arguments and this blog post presents how it can be done in C++.


Advertisement

Motivation

Consider a function that logs a message:

logger.debug("Called foo() passing it " + std::to_string(argument_a) + " and " + std::to_string(argument_b));

The logger has various log levels like “debug”, “warning”, “error” etc. This allows you to control how much is actually logged; the above message will only be visible if the log level is set to the “debug” level.

However, even when it is not shown the string will still be constructed and then discarded, which is wasteful. A possible fix is to delay the string construction until it is necessary:

logger.debug("Called foo() passing it ", argument_a, " and ", argument_b);

Now the string is only formatted before it is logged, so if the message won’t be logged, the string won’t be formatted. However, the arguments are still evaluated, if argument_a is an expensive expression itself, that must be calculated. With lazy function argument evaluation we don’t need to do that.

The goal

For the sake of this post consider a simpler case, optional<T>::value_or() (of my ts::optional<T> of type_safe). This function either returns the contained value in the optional or a provided fallback value. A straightforward implementation can look like this:

template <typename U>
T optional<T>::value_or(U&& fallback)
{
    if (has_value())
        return value();
    return static_cast<T>(std::forward<U>(fallback));
}

Note that my actual implementation doesn’t do an explicit cast but relies on an implicit conversion. But I need to cheat a little and use the static_cast here in order to make a point later on.

Our goal is to implement lazy evaluation for fallback; if we call it like so:

auto result = opt.value_or(foo());

foo() should only be called if the result is actually needed, i.e. opt does not store a value.

Take 1: Macros

A straightforward solution is to use a macro instead of a function. Macros have the ““nice”” “"”feature””” that they don’t actually evaluate everything but just paste the expression into the function body.

So the following works:

#define VALUE_OR(opt, fallback)          \
    [&](const auto& optional) {          \
        if (optional.has_value())        \
            return optional.value();     \
        return static_cast<T>(fallback); \
    }(opt)

The idea is to create a new value_or() function for each expression we want as fallback value. This is achieved by creating a lambda that does the specified value_or(): it either returns the value or it calculates something and returns that. The lambda is then immediately invoked on the given optional object.

Call would look like this:

auto result = VALUE_OR(opt, foo());

However, this completely relies on macros, so let’s try to make it better.

Take 2: Lambdas

The previous macro was tightly coupled to the specific functionality we want to lazily evaluate - the value_or(). Let’s try to decouple it: we write the functionality and then pass it a lazily evaluated expression.

How do we create a lazily evaluated expression?

We use a lambda. Instead of calling it normally, we give it a lambda that returns the argument:

auto result = opt.value_or([&] { return foo(); });

Implementation of value_or() - that supports both lazy and non-lazy evaluation - can look like this:

// normal implementation
template <typename U, typename = decltype(static_cast<T>(std::declval<U>()))>
T optional<T>::value_or(U&& fallback)
{
    if (has_value())
        return value();
    return static_cast<T>(std::forward<U>(fallback));
}

// lazy evaluation
template <typename U, typename = decltype(static_cast<T>(std::declval<U>() ( /* function call*/ ) ))>
T optional<T>::value_or(U&& lambda)
{
    if (has_value())
        return value();
    return static_cast<T>(std::forward<U>(lambda)());
}

The first overload just casts the expression, the second one invokes the lambda and casts the result of that. The strange typename = decltype(…) is used for SFINAE. If the expression inside the decltype is well-formed, the overload is considered. And the expression is just the behavior we expect for that overload.

Note that this implementation breaks if we pass a type that is both convertible to T and callable resulting in something convertible to T. Then both overloads are valid and the call is ambiguous. Fixing this is left as exercise for the reader. For a hint, take a look at the technique used here.

The call is a little bit ugly with the lambda, but we can use a macro to improve it:

#define LAZY(Expr) \
    [&]() -> decltype((Expr)) { return Expr; }

This just creates a lambda capturing everything by reference and returning the expression. Note the double parenthesis around the decltype(). decltype(42) and decltype((42)) both yield the same type, int, but for an int i;, decltype(i) yields int and decltype((i)) yields int&, and we want to get the reference here.

Then the usage is like this:

auto result = opt.value_or(LAZY(foo()));

Take 3: Making it non-intrusive

While the previous approach works, it requires some amount of work from the implementer of the algorithm. Wouldn’t it be nice if we could make it non-intrusive and just let the caller arbitrarily decide when to have lazy evaluation?

This can be done by introducing a special type, a lazy_expression. Instead of passing a lambda to the algorithm, the LAZY macro can create a special object that is convertible to the type. And that conversion will evaluate the expression.

This can look like this:

template <class Lambda>
class lazy_eval
{
    const Lambda& lambda_;

public:
    lazy_eval(const Lambda& lambda)
    : lambda_(lambda) {}

    lazy_eval(const lazy_eval&) = delete;
    lazy_eval& operator=(const lazy_eval&) = delete;

    using expression_type = decltype(std::declval<Lambda>()());

    explicit operator expression_type() const
    {
        return lambda();
    }
};

It just stores a reference to a lambda and has an explicit conversion operator that returns the result of the lambda. We just need to do a little change to the LAZY macro:

#define LAZY(Expr) \
    lazy_eval([&]() -> decltype((Expr)) { return Expr; })

This uses C++17 class template argument deduction which saves us the boilerplate make function we’d need as we can’t explictly pass it the type of a lambda expression.

But with that in place the original value_or() function…

template <typename U>
T optional<T>::value_or(U&& fallback)
{
    if (has_value())
        return value();
    return static_cast<T>(std::forward<U>(fallback));
}

… can be used like this:

auto a = opt.value_or(42); // non-lazy
auto b = opt.value_or(LAZY(foo())); // lazy

The LAZY macro can now be used in all places where the implementation does a static_cast to some type. If an implementation relies on implicit conversion or if the function in question is not templated, it won’t work but this will be detected by a compilation error. The only assumption this makes on the called function is that it only does a static_cast when the result is actually needed. This value_or() won’t work lazily:

template <typename U>
T optional<T>::value_or(U&& fallback)
{
    T result(std::forward<U>(fallback));
    if (has_value())
        return value();
    return result;
}

But that is a somewhat dumb implementation anyway.

Evaluation

We’ve now implemented a non-intrusive and easy to use implementation of lazy argument evaluation. But how usable is it really?

As I’ve already pointed out it is not quite non-intrusive, it relies on implementations to do late casting. It also don’t work if the implementation doesn’t cast at all or isn’t templated.

Furthermore, it relies on macros to create a decent interface. And interfaces relying on macros are usually not a good idea.

In the case of value_or() the best solution - if we need lazy evaluation of the fallback - is probably to simple provide a value_or_lazy() overload that takes a lambda or the Take 2 implementation without the lazy macro. My original motivation for toying with lazy evaluation was to provide a “give me the value or throw this exception” mechanism, which is very useful for .map().value_or() chains. While this can be done with LAZY(), it is not obvious.

LAZY() requires a conversion to the actually expected type. So even if we lazily throw an exception, we need to return something of the correct type. If you’d want to do a generic LAZY_THROW(T, Ex) that throws an exception of type Ex but returns something of type T in order to make the generic code work, how would you do that? Remember: not all types are default constructible.

Hint: The “object” you return does not need to be a valid object as it will never be created anyway, execution will be aborted with the throw before.

So for type_safe I’d probably go with just providing a value_or_error() function or something like that.

But note that this technique of using lambdas to delay evaluation is very useful: I did it in my debug_assert library to be able to control assertions by compile-time constants. I’ve described it in great detail in this blog post.


Advertisement

Conclusion

Lazy evaluation of function parameters is useful in certain circumstances. By using lambda expressions - and hiding them behind a macro - we can achieve that in C++.

However, I wouldn’t suggest actually using that like this in production code. Most often, a better solution would be to design the algorithm so that it works lazily. range v3, for example, can work on infinite ranges which are lazily evaluated as needed.

Note that languages like Haskell are also lazily evaluated and that D has a lazy storage class for function parameters.