Expression tree

Most of the expressions in xtensor are lazy-evaluated, they do not hold any value, the values are computed upon access or when the expression is assigned to a container. This means that xtensor needs somehow to keep track of the expression tree.

xfunction

A node in the expression tree may be represented by different classes in xtensor; here we focus on basic arithmetic operations and mathematical functions, which are represented by an instance of xfunction. This is a template class whose parameters are:

  • a functor describing the operation of the mathematical function
  • the closures of the child expressions, i.e. the most optimal way to store each child expression

Consider the following code:

xarray<double> a = xt::ones({2, 2});
xarray<double> b = xt::ones({2, 2});

auto f = (a + b);

Here the type of f is xfunction<plus, const xarray<double>&, const xarray<double>&>, and f stores constant references on the arrays involved in the operation. This can be illustrated by the figure below:

../_images/xfunction_tree.svg

The implementation of xfunction methods is quite easy: they forward the call to the nodes and apply the operation when this makes sense. For instance, assuming that the operands are stored as m_first and m_second, and the functor describing the operation as m_functor, the implementation of operator() and broadcast_shape looks like:

template <class F, class... CT>
template <class... Args>
inline auto xfunction<F, CT...>::operator()(Args... args) const -> const_reference
{
    return m_functor(m_first(args...), m_second(args...));
}

template <class F, class... CT>
template <class S>
inline bool xfunction<F, CT...>::broadcast_shape(S& shape) const
{
    return m_first.broadcast_shape(shape) && m_second.broadcast_shape(shape);
}

In fact, xfunction can handle an arbitrary number of arguments. The practical implementation is slightly more complicated than the code snippet above, however the principle remains the same.

Holding expressions

Each node of an expression tree holds const references to its child nodes, or the child nodes themselves, depending on their nature. When building a complex expression, if a part of this expression is an rvalue, it is moved inside its parent, else a constant reference is used:

xarray<double> some_function();

xarray<double> a = xt::ones({2, 2});
auto f = a + some_function();

Here f holds a constant reference on a, while the array returned by some_function is moved into f. The actual types held by the expression are the closure types, more details can be found in Closure semantics.

Building the expression tree

As previously stated, each mathematical function in xtensor returns an instance of xfunction. This section explains in details how the template parameters of xfunction are computed according to the type of the function, the number and the types of its arguments. Let’s consider the definition of operator+:

template <class E1, class E2>
inline auto operator+(E1&& e1, E2&& e2) -> detail::xfunction_type<detail::plus, E1, E2>
{
    return detail::make_xfunction<detail::plus>(std::forward<E1>(e1), std::forward<E2>(e2));
}

This top-level function selects the appropriate functor and forwards its arguments to the make_xfunction generator. This latter is responsible for setting the remaining template parameters of xfunction:

template <template <class...> class F, class... E>
inline auto make_xfunction(E&&... e) noexcept
{
    using expression_tag = xexpression_tag_t<E...>;
    using functor_type = F;
    using type = select_xfunction_expression_t<expression_tag, F, const_xclosure_t<E>...>;
    return type(functor_type(), std::forward<E>(e)...);
}

The first line computes the expression_tag of the expression. This tag is used for selecting the right class class modeling a function. In xtensor, two tags are provided, with the following mapping:

  • xtensor_expression_tag -> xfunction
  • xoptional_expression_tag -> xfunction

In the case of xfunction, the tag is also used to select a mixin base class that will extend its API.

Any expression may define a tag as its expression_tag inner type. If not, xtensor_expression_tag is used by default. Tags have different priorities so that a resulting tag can be computed for expressions involving different tag types. As we will see in the next section, this system of tags and mapping make it easy to plug new functions types in xtensor and have them working with all the mathematical functions already implemented.

The function class mapped to the expression tag is retrieved in the third line of make_xfunction, that is:

using type = select_xfunction_expression_t<expression_tag, F, const_xclosure_t<E>...>;

const_closure_t computes the closure type (see Closure semantics) of each argument and passes it to the function class to instantiate.

Once all the types are known, make_xfunction can instantiate the right function type and returns it:

return type(functor_type(), std::forward<E>(e)...);

Plugging new function types

As mentioned in the section above, one can define a new function class and have it used by xtensor’s expression system. Let’s illustrate this with an hypothetical xmapped_function class, which provides additional mapping access operators. The first thing to do is to define a new tag:

struct xmapped_expression_tag
{
};

Then the tag selection rules must be updated if we want to be able to mix xtensor_expression_tag and xmapped_expression_tag. This is done by specializing the expression_tag_and metafunction available in the namespace xt::extension:

namespace xt
{
    namespace extension
    {
        template <>
        struct expression_tag_and<xtensor_expression_tag, xmapped_expression_tag>
        {
            using type = xmapped_expression_tag;
        };

        template <>
        struct expression_tag_and<xmapped_expression_tag, xtensor_expression_tag>
            : expression_tag_and<xtensor_expression_tag, xmapped_expression_tag>
        {
        };
    }
}

The second specialization simply forwards to the first one so we don’t duplicate code. Note that when plugging your own function class, these specializations can be skipped if the new function class (and its corresponding tag) is not compatible, and thus not supposed to be mixed, with the function classes provided by xtensor.

The last requirement is to specialize the select_xfunction_expression metafunction, as it is shown below:

namespace xt
{
    namespace detail
    {
        template <class F, class... E>
        struct select_xfunction_expression<xmapped_expression_tag, F, E...>
        {
            using type = xmapped_function<F, typename F::result_type, E...>;
        };
    }
}

In this example, xmapped_function may provide the same API as xfunction and define some additional methods unrelated to the assignment mechanics. However it is possible to define a function class with an API totally different from the one of xfunction. In that case, the assignment mechanics need to be customized too, this is detailed in Assignment.