# 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:

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.