Jonathan Boccara's blog

Infix Function Calls with Boost HOF

Published January 8, 2021 - 0 Comments

In C++, functions are called with a prefix syntax. This means that at call site, the function name is before the parameters:

myFunction(parameter1, parameter2);
^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^
 function         parameters

On the other hand, binary operators such as operator+ are called with an infix syntax, which means that the operator is between the parameters:

parameter1 + parameter2

Some languages allow to call functions with an infix syntax too. For example, Haskell allows to transform a prefix function into an infix one by using backticks:

parameter1 `myFunction` parameter2

C++ doesn’t allow that.

But Boost, as often, pushes the boundaries of the language, and with the recent HOF library, it is now possible (amongst other things) to emulate the infix notation in C++.

Why the infix notation

Before looking at how to implement it, what is the point of an infix notation?

The infix notation can make the code more expressive and more correct.

For example, in the case of a function taking two parameters of the same type, we need to identify the role of each one. Let’s take the example of a function that searches a substring into a string. The standard algorithm search does this, and a simplified version of its C++20 range interface looks like this:

template<forward_range Range1, forward_range Range2>
safe_subrange_t<Range1> search(Range1&& range1, Range2&& range2);

Given that it returns a subrange of the first range, we can assume that it looks for range2 into range1. But look at the call site:

auto result = std::ranges::search(s1, s2);

It’s not clear which string is the one we are looking for and which one we are looking into. And if it is not clear, then the code is not expressive, and there is a risk of mixing up the parameters, leading to a bug.

One way to remedy to that is to use strong types to identify the role of the parameters at call site:

auto results = search(s2, Within(s1));

Or sometimes with more original names:

auto result = search(Needle(s2), Haystack(s1));

But wouldn’t it be simpler to write something like this:

auto result = s2 `searchedInto` s1; // imaginary C++

Another example is a function that determines if a string is a prefix of another one:

auto result = isPrefixOf(s1, s2);

It is unclear which string we’re checking is the prefix of the other, and this can lead to a bug if we mix up the arguments.

It would be so much clearer to use an infix notation here:

auto result = s1 `isPrefixOf` s2; // imaginary C++

Let’s now see how Boost HOF emulates the infix notation in C++.

The infix notation with Boost HOF

Boost HOF (standing for Higher Order Functions) allows to use the infix notation with any function taking two parameters, by using an astute overloading of operator< and operator>: surround the name of the function with angle brackets, and the library takes care of the rest.

Let’s see it work on an example, with the function that checks if a string is a prefix of another one.

As we saw in the article of checking for prefixes in C++, here is a very basic implementation of the function:

bool isPrefixOf(std::string const& prefix, std::string const& text)
{
    auto const differingPositions = std::mismatch(begin(prefix), end(prefix), begin(text), end(text));
    return differingPositions.first == end(prefix);
}

To allow Boost HOF to work with it as an infix function, we use boost::hof::infix:

#include <algorithm>
#include <string>
#include <boost/hof.hpp>

auto isPrefixOf = boost::hof::infix(
    [](std::string const& prefix, std::string const& text)
    {
        auto const differingPositions = std::mismatch(begin(prefix), end(prefix), begin(text), end(text));
        return differingPositions.first == end(prefix);
    });

Now we can just use the infix notation:

auto const result = s1 <isPrefixOf> s2;

How nice is that?

The implementation of the infix notation

Boost infix uses operator overloading for operator< and operator> to implement the infix notation in C++.

Let’s understand how this is implemented. This exploration is interesting in itself, and also by understanding the implementation we will also understand the cases where it works well and the cases that it doesn’t support.

Let’s try to code up a simple version of infix.

The infix type

In essence, the infix function creates an object that overloads the comparison operators. It combines with operator< with the left hand argument producing an object combining with operator> with the right hand argument, calling the function on those two arguments.

Calling infix with a function returns an object storing that function With C++17 deduction of template parameters in constructors, we can define infix as the type of this object:

template<typename Function>
struct infix
{
    explicit infix(Function function) : function_(function){}
    Function function_;
};

Storing the first argument

When combined with the first argument, infix must return an object that can later be combined with the second argument. This object also has to store the function, and also the first parameter, in order to later perform the function call. Let’s call the type of this object LeftHandAndFunction:

template<typename LeftHandValue, typename Function>
struct LeftHandAndFunction
{
    LeftHandAndFunction(LeftHandValue const& leftHandValue, Function function) : leftHandValue_(leftHandValue), function_(function){}

    LeftHandValue leftHandValue_;
    Function function_;
};

In this implementation, we have to decide how to store the first parameter. Do we store it by value, or by reference?

Storing it by value incurs a move (or copy), and disconnects the value passed from the value that the function will receive. But on the other hand, storing it by reference is complicated to implement: if it is a lvalue reference, it has to be const, otherwise it won’t bind on rvalues. And if it is not const, then to accommodate rvalues we’d need to store by value in this case only.

To start with a simple implementation, let’s store this first argument by value in all cases, and copy it from the input. This is suboptimal, and we’ll come back to this in a moment.

operator< then combines the infix object with the first argument:

template<typename LeftHandValue, typename Function>
LeftHandAndFunction<std::remove_reference_t<LeftHandValue>, Function> operator< (LeftHandValue&& leftHandValue, infix<Function> const& infix)
{
    return LeftHandAndFunction<std::remove_reference_t<LeftHandValue>, Function>(std::forward<LeftHandValue>(leftHandValue), infix.function_);
}

We use std::remove_reference_t in case LeftHandValue is an lvalue reference. This way, we store the value of the first argument and not a reference to it.

Storing the first argument

The next step is to combine this object with the second argument with operator>, which completes the elements needed to call the function:

template<typename LeftHandValue, typename Function, typename RightHandValue>
decltype(auto) operator> (LeftHandAndFunction<LeftHandValue, Function> leftHandAndFunction, RightHandValue&& rightHandValue)
{
    return leftHandAndFunction.function_(leftHandAndFunction.leftHandValue_, std::forward<RightHandValue>(rightHandValue));
}

And that’s about it for an implementation of infix working in simple cases.

Handling more advanced cases

Now that we have the whole structure laid out, let’s come back to how to store the first argument efficiently.

The code of Boost HOF stores a reference to the first argument if it is an lvalue, and moves (or copies) it in if it an rvalue. To do this, it uses techniques similar to what Miguel presented us on how to construct C++ objects without making copies:

template<typename LeftHandValue, typename Function>
struct LeftHandAndFunction
{
    template<typename LeftHandValue_>
    LeftHandAndFunction(LeftHandValue_&& leftHandValue, Function function) : leftHandValue_(std::forward<LeftHandValue_>(leftHandValue)), function_(function){}

    LeftHandValue leftHandValue_;
    Function function_;
};

Note that we’ve made the constructor a template function, inside of a template class. The point of using a new template parameter (LeftHandValue_, with a trailing underscore), allows to use forwarding references. Indeed, from the perspective of the constructor LeftHandValue (with no underscore) is not a template parameter. It has been fixed at the instantiation of the code of the class.

The code of operator< then looks like this:

template<typename LeftHandValue, typename Function>
LeftHandAndFunction<LeftHandValue, Function> operator< (LeftHandValue&& leftHandValue, infix<Function> const& infix)
{
    return LeftHandAndFunction<LeftHandValue, Function>(std::forward<LeftHandValue>(leftHandValue), infix.function_);
}

Note that the std::remove_reference_t are gone.

How does this all work?

If the first parameter is an lvalue, then LeftHandValue is an lvalue reference and LeftHandAndFunction stores a reference (that can even be not const) to the first parameter.

If the first parameter is an rvalue, the LeftHandValue is another instance of the value of the first argument itself. Bringing that initial value in with std::forward carries the information that it come from an rvalue. Therefore, the value inside LeftHandAndFunction is filled with a move if it is available on the type (and a copy otherwise).

And what if the first argument cannot be moved or copied, for example if it involves unique_ptr passed as lvalues? In this case the code would not compile either, even with Boost HOF, as we can see on that example.

Higher order functions

With this nice infix helper giving us more flexibility to write expressive and correct code, Boost HOF looks like a very interesting libray.

We will explore more of its components in future posts.

You will also like

Don't want to miss out ? Follow:   twitterlinkedinrss
Share this post!Facebooktwitterlinkedin