§ 6. Ленивые вычисления

01Ленивиые вычисления — это прием в программировании, который позволяет откладывать вычисления до тех пор, пока их результат не понадобится использовать в обычных вычислениях. Этот прием широко используется в функциональных языках для следующих целей:

использование кода как данных для передачи по сети, записи в файл или вывода на экран;
выполнение кода при необходимости (если результат не понадобился, то и код не будет зря выполняться);
оптимизация математических и аналогичных выражений, используя набор правил.

В C++ ленивые вычисления применяются, в основном, для оптимизации математических выражений, работающих с многомерными массивами.

Ленивые вычисления в C++ реализуются путем создания классов, которые описывают синтаксическое дерево математических операций, которые необходимо оптмизировать (арифметические операции, тригонометрические, гипергеометрические и специальные функции и другие). Для каждой операции создается отдельный класс, содержащий аргументы операции в виде полей, а сама операция реализуется в методе evaluate для отдельного элемента массива.

template <class E1, class E2>
class Plus: public Expression {
public:
    using value_type =
        typename std::common_type<typename E1::value_type,
                                  typename E2::value_type>::type;
private:
    const E1& _a;
    const E2& _b;
public:
    explicit Plus(const E1& a, const E2& b): _a(a), _b(b) {}
    value_type evaluate(int i) { return this->_a.evaluate(i) +
                                        this->_b.evaluate(i); }
    int size() const { return this->_a.size(); }
    void display(std::ostream& out) const {
        out << "Plus(" << this->_a << ", " << this->_b << ')';
    }
};

В классе присутствует метод для определения размера массива, вывода операции на экран в виде выражения, а также возвращаемый тип данной операции value_type. В примере показана операция сложения для элементов одномерного массива, но подход легко обобщить для нескольких измерений.

02В дополнение к классам, описывающим операции, идут глобальные функции, которые вызывают операции для каждого элемента массива.

template <class E>
Vector<typename E::value_type> evaluate(const E& expr) {
    using value_type = typename E::value_type;
    const auto n = expr.size();
    Vector<value_type> result(n);
    for (int i=0; i<n; ++i) {
        result(i) = expr.evaluate(i);
    }
    return result;
}

Здесь Vector<T> является одномерным массивом. В этой функции сначала определяется размер массива, а затем вызывается метод evaluate для каждого элемента массива. Обычно, в этой функции делают различные оптимизации, позволяющие векторизовать поэлементные операции, т.е. использовать векторные регистры процессора, чтобы применять одну и ту же операцию одновременно к нескольким элементам массива. Это значительно ускоряет код и является одной из причин создания библиотек для эффективной работы с многомерными массивами.

Помимо функции evaluate полезно добавить оператор вывода для отладки выражений.

template <class E>
typename std::enable_if<std::is_base_of<Expression,E>::value,
                        std::ostream&>::type
operator<<(std::ostream& out, const E& expr) {
    expr.display(out); return out;
}

Поскольку выражение может иметь любой тип, то мы используем специальный шаблон std::enable_if, который позволяет определить оператор вывода только для тех типов, для которых класс Expression является базовым. Вторым аргументом этого шаблона является возвращаемый тип. Если первый аргумент равен true, тогда тип определяется в виде поля type шаблона std::enable_if, иначе никакого поля в нем нет. А если поля нет, то значит оператор вывода для соответствующего типа не определен. Сам базовый тип Expression является пустым, такие типы иногда называют классами-метками, поскольку они используются только во время компиляции для метапрограммирования.

Наконец, надо определить оператор сложения для наших выражений, чтобы использовать знакомый и интуитивный математический синтаксис.

template <class E1, class E2>
typename std::enable_if<std::is_base_of<Expression,E1>::value &&
                        std::is_base_of<Expression,E2>::value,
                        Plus<E1,E2>>::type
operator+(const E1& a, const E2& b) {
    return Plus<E1,E2>(a,b);
}

Здесь тоже используется std::enable_if, но с более сложным условием. Сам оператор возвращает выражение, а не результат вычислений, т.е. является функцией-конструктором для выражения Plus.

03Результатом наших усилий является набор классов и функций, которые позволяют генерировать эффективные и легко векторизуемые поэлементные циклы, используя знакомую математическую нотацию. Например, код

Vector<T> a{1,2,3}, b{4,5,6}, c{7,8,9};
Vector<T> d = a+b+c;

сгенерирует цикл следующего вида.

for (int i=0; i<n; ++i) {
    d[i] = a[i] + b[i] + c[i];
}

04Данный подход работает для поэлементных операций, но аналогично можно реализовать любые другие операции над массивами. Поэлементные реализуют в первую очередь из-за оптимизаций, которые можно таким образом получить. В заданиях мы добавим в этот код больше выражений.

Задания

05Перед выполнением заданий скопируйте исходный код программы, используя следующие команды.

git clone https://courses.igankevich.com/system-programming/linalg.git
cd linalg
meson build
cd build
ninja
./src/linalg/linalg

Перед вами программа, которая реализует ленивые вычисления на C++. Вычисления производятся поэлементно над одномерными массивами.

Реализуйте следующие операторы по аналогии с Plus.
- унарный оператор -
- унарный оператор +
- бинарный оператор -
- бинарный оператор *
- бинарный оператор /
Реализуйте бинарный оператор сравнения <, который возвращает Vector<bool>. Оператор сравнивает соответствующие элементы переданных в него выражений и записывает результат сравнений в выходной массив. Реализуйте оператор all, который возвращает истину, если все элементы выражения являются истиной. Этот оператор непоэлементный, поэтому для него придется написать отдельную глобальную функцию evaluate.
Реализуйте тернарный оператор ?:. Поскольку переопределить в C++ его нельзя, то роль функции-конструктора будет играть функция where. Оператор where(a,b,c) должен лениво вычислять выражение b или c в зависимости от предиката a, который также является выражением.
Проверьте работоспособность следующих операторов с помощью модульных тестов.
- любой унарный оператор
- бинарный оператор сравнения < и любой другой бинарный оператор
- тернарный оператор