Ленивое вычисление в C++

Как это будет сделано в C++ 0x, с помощью лямбда-выражений.

Все возможно.

Это зависит от того, что именно вы имеете в виду:

class X
{
     public: static X& getObjectA()
     {
          static X instanceA;

          return instanceA;
     }
};

Здесь у нас есть влияние глобальной переменной, которая лениво вычисляется при первом использовании.

В соответствии с новым запросом в вопросе. И похищение дизайна Конрада Рудольфа и его расширение.

Ленивый объект:

template<typename O,typename T1,typename T2>
struct Lazy
{
    Lazy(T1 const& l,T2 const& r)
        :lhs(l),rhs(r) {}

    typedef typename O::Result  Result;
    operator Result() const
    {
        O   op;
        return op(lhs,rhs);
    }
    private:
        T1 const&   lhs;
        T2 const&   rhs;
};

Как это использовать:

namespace M
{
    class Matrix
    {
    };
    struct MatrixAdd
    {
        typedef Matrix  Result;
        Result operator()(Matrix const& lhs,Matrix const& rhs) const
        {
            Result  r;
            return r;
        }
    };
    struct MatrixSub
    {
        typedef Matrix  Result;
        Result operator()(Matrix const& lhs,Matrix const& rhs) const
        {
            Result  r;
            return r;
        }
    };
    template<typename T1,typename T2>
    Lazy<MatrixAdd,T1,T2> operator+(T1 const& lhs,T2 const& rhs)
    {
        return Lazy<MatrixAdd,T1,T2>(lhs,rhs);
    }
    template<typename T1,typename T2>
    Lazy<MatrixSub,T1,T2> operator-(T1 const& lhs,T2 const& rhs)
    {
        return Lazy<MatrixSub,T1,T2>(lhs,rhs);
    }
}

I'm wondering if it is possible to implement lazy evaluation in C++ in a reasonable manner. If yes, how would you do it?

Да, это возможно и делается довольно часто, например для матричных вычислений. Основным механизмом, способствующим этому, является перегрузка оператора. Рассмотрим случай сложения матриц. Сигнатура функции обычно выглядит примерно так:

matrix operator +(matrix const& a, matrix const& b);

Теперь, чтобы сделать эту функцию ленивой, достаточно вернуть прокси вместо фактического результата:

struct matrix_add;

matrix_add operator +(matrix const& a, matrix const& b) {
    return matrix_add(a, b);
}

Теперь все, что нужно сделать, это написать этот прокси:

struct matrix_add {
    matrix_add(matrix const& a, matrix const& b) : a(a), b(b) { }

    operator matrix() const {
        matrix result;
        // Do the addition.
        return result;
    }
private:
    matrix const& a, b;
};

Магия заключается в методе operator matrix(), который является оператором неявного преобразования из matrix_add в простой matrix. Таким образом, вы можете связать несколько операций (конечно, путем предоставления соответствующих перегрузок). Оценка происходит только тогда, когда окончательный результат присваивается экземпляру matrix.

РЕДАКТИРОВАТЬ Я должен был быть более точным. Как бы то ни было, код не имеет смысла, потому что, хотя вычисление происходит лениво, оно все равно выполняется в том же выражении. В частности, другое дополнение будет оценивать этот код, если структура matrix_add не будет изменена, чтобы разрешить связанное добавление. C++ 0x значительно облегчает это, разрешая вариативные шаблоны (то есть списки шаблонов переменной длины).

Однако есть один очень простой случай, когда этот код действительно принесет прямую пользу:

int value = (A + B)(2, 3);

Здесь предполагается, что A и B являются двумерными матрицами и что разыменование выполняется в нотации Fortran, то есть вышеупомянутое вычисляет элемент один из суммы матриц. Разумеется, добавлять матрицы целиком - бесполезно. matrix_add приходит на помощь:

struct matrix_add {
    // … yadda, yadda, yadda …

    int operator ()(unsigned int x, unsigned int y) {
        // Calculate *just one* element:
        return a(x, y) + b(x, y);
    }
};

Есть и другие примеры. Я только что вспомнил, что недавно реализовал кое-что связанное с этим. По сути, мне пришлось реализовать строковый класс, который должен придерживаться фиксированного, предопределенного интерфейса. Однако мой конкретный строковый класс имел дело с огромными строками, которые на самом деле не хранились в памяти. Обычно пользователь просто получает доступ к небольшим подстрокам из исходной строки с помощью функции infix. Я перегрузил эту функцию для своего строкового типа, чтобы вернуть прокси, который содержал ссылку на мою строку вместе с желаемой начальной и конечной позициями. Только когда эта подстрока действительно использовалась, он запрашивал C API для получения этой части строки.

C++ 0x хорош и все такое ... но для тех из нас, кто живет в настоящем, у вас есть библиотека Boost lambda и Boost Phoenix. Оба с намерением привнести в C++ большой объем функционального программирования.

То, что уже объяснил Конрад, может быть добавлено к поддержке вложенных вызовов операторов, выполняемых лениво. В примере Конрада у него есть объект выражения, который может хранить ровно два аргумента для ровно двух операндов одной операции. Проблема в том, что он будет выполнять только подвыражение один лениво, что хорошо объясняет концепцию ленивого вычисления, выраженную простыми словами, но не улучшает производительность существенно. Другой пример также хорошо показывает, как можно применить operator() для добавления только некоторых элементов, используя этот объект выражения. Но для оценки произвольных сложных выражений нам нужен какой-то механизм, который может хранить и его структуру. Мы не можем обойтись без шаблонов для этого. И название для этого - expression templates. Идея состоит в том, что один шаблонный объект выражения может рекурсивно хранить структуру некоторого произвольного подвыражения, как дерево, где операции являются узлами, а операнды - дочерними узлами. Хорошее объяснение очень, которое я нашел сегодня (через несколько дней после того, как я написал приведенный ниже код), см. В здесь.

template<typename Lhs, typename Rhs>
struct AddOp {
    Lhs const& lhs;
    Rhs const& rhs;

    AddOp(Lhs const& lhs, Rhs const& rhs):lhs(lhs), rhs(rhs) {
        // empty body
    }

    Lhs const& get_lhs() const { return lhs; }
    Rhs const& get_rhs() const { return rhs; }
};

Это сохранит любую операцию сложения, даже вложенную, как видно из следующего определения оператора + для простого типа точки:

struct Point { int x, y; };

// add expression template with point at the right
template<typename Lhs, typename Rhs> AddOp<AddOp<Lhs, Rhs>, Point> 
operator+(AddOp<Lhs, Rhs> const& lhs, Point const& p) {
    return AddOp<AddOp<Lhs, Rhs>, Point>(lhs, p);
} 

// add expression template with point at the left
template<typename Lhs, typename Rhs> AddOp< Point, AddOp<Lhs, Rhs> > 
operator+(Point const& p, AddOp<Lhs, Rhs> const& rhs) {
    return AddOp< Point, AddOp<Lhs, Rhs> >(p, rhs);
}

// add two points, yield a expression template    
AddOp< Point, Point > 
operator+(Point const& lhs, Point const& rhs) {
    return AddOp<Point, Point>(lhs, rhs);
}

Теперь, если у вас есть

Point p1 = { 1, 2 }, p2 = { 3, 4 }, p3 = { 5, 6 };
p1 + (p2 + p3); // returns AddOp< Point, AddOp<Point, Point> >

Теперь вам просто нужно перегрузить operator = и добавить подходящий конструктор для типа Point и принять AddOp. Измените его определение на:

struct Point { 
    int x, y; 

    Point(int x = 0, int y = 0):x(x), y(y) { }

    template<typename Lhs, typename Rhs>
    Point(AddOp<Lhs, Rhs> const& op) {
        x = op.get_x();
        y = op.get_y();
    }

    template<typename Lhs, typename Rhs>
    Point& operator=(AddOp<Lhs, Rhs> const& op) {
        x = op.get_x();
        y = op.get_y();
        return *this;
    }

    int get_x() const { return x; }
    int get_y() const { return y; }
};

И добавьте соответствующие get_x и get_y в AddOp в качестве функций-членов:

int get_x() const {
    return lhs.get_x() + rhs.get_x();
}

int get_y() const {
    return lhs.get_y() + rhs.get_y();
}

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

Мне нечего добавить к сообщению Конрада, но вы можете посмотреть на Эйген пример правильной ленивой оценки в реальном приложении. Это довольно внушает трепет.

Boost.Lambda очень хорош, но Boost.Proto - это точно, что вы ищете. В нем уже есть перегрузки операторов C++ все, которые по умолчанию выполняют свою обычную функцию при вызове proto::eval(), но могут быть изменены.

Я думаю о реализации класса шаблона, который использует std::function. Класс должен выглядеть примерно так:

template <typename Value>
class Lazy
{
public:
    Lazy(std::function<Value()> function) : _function(function), _evaluated(false) {}

    Value &operator*()  { Evaluate(); return  _value; }
    Value *operator->() { Evaluate(); return &_value; }

private:
    void Evaluate()
    {
        if (!_evaluated)
        {
            _value = _function();
            _evaluated = true;
        }
    }

    std::function<Value()> _function;
    Value _value;
    bool _evaluated;
};

Например использование:

class Noisy
{
public:
    Noisy(int i = 0) : _i(i)
    {
        std::cout << "Noisy(" << _i << ")"  << std::endl;
    }
    Noisy(const Noisy &that) : _i(that._i)
    {
        std::cout << "Noisy(const Noisy &)" << std::endl;
    }
    ~Noisy()
    {
        std::cout << "~Noisy(" << _i << ")" << std::endl;
    }

    void MakeNoise()
    {
        std::cout << "MakeNoise(" << _i << ")" << std::endl;
    }
private:
    int _i;
};  

int main()
{
    Lazy<Noisy> n = [] () { return Noisy(10); };

    std::cout << "about to make noise" << std::endl;

    n->MakeNoise();
    (*n).MakeNoise();
    auto &nn = *n;
    nn.MakeNoise();
}

Приведенный выше код должен отобразить на консоли следующее сообщение:

Noisy(0)
about to make noise
Noisy(10)
~Noisy(10)
MakeNoise(10)
MakeNoise(10)
MakeNoise(10)
~Noisy(10)

Обратите внимание, что конструктор, печатающий Noisy(10), не будет вызываться до тех пор, пока не будет осуществлен доступ к переменной.

Однако этот класс далек от совершенства. Первым делом при инициализации члена должен быть вызван конструктор по умолчанию для Value (в данном случае печать Noisy(0)). Вместо этого мы можем использовать указатель на _value, но я не уверен, повлияет ли это на производительность.

Ответ Йоханнеса работает, но когда дело доходит до большего количества скобок, он работает не так, как хотелось бы. Вот пример.

Point p1 = { 1, 2 }, p2 = { 3, 4 }, p3 = { 5, 6 }, p4 = { 7, 8 };
(p1 + p2) + (p3+p4)// it works ,but not lazy enough

Поскольку три перегруженных оператора + не охватывают случай

AddOp<Llhs,Lrhs>+AddOp<Rlhs,Rrhs>

Таким образом, компилятор должен преобразовать либо (p1 + p2), либо (p3 + p4) в Point, это не достаточно ленивый. И когда компилятор решает, что преобразовать, он жалуется. Потому что никто не лучше другого. А вот и мое расширение: добавить еще один перегруженный оператор +

    template <typename LLhs, typename LRhs, typename RLhs, typename RRhs>
AddOp<AddOp<LLhs, LRhs>, AddOp<RLhs, RRhs>> operator+(const AddOp<LLhs, LRhs> & leftOperandconst, const AddOp<RLhs, RRhs> & rightOperand)
{
    return  AddOp<AddOp<LLhs, LRhs>, AddOp<RLhs, RRhs>>(leftOperandconst, rightOperand);

}

Теперь компилятор может правильно обрабатывать описанный выше случай, и никакого неявного преобразования, volia!

В С ++ 11 ленивая оценка, аналогичная ответу hiapay, может быть достигнута с помощью std :: shared_future. Вы все еще должны инкапсулировать вычисления в лямбдах, но позаботимся о мемоизации:

std::shared_future<int> a = std::async(std::launch::deferred, [](){ return 1+1; });

Вот полный пример:

#include <iostream>
#include <future>

#define LAZY(EXPR, ...) std::async(std::launch::deferred, [__VA_ARGS__](){ std::cout << "evaluating "#EXPR << std::endl; return EXPR; })

int main() {
    std::shared_future<int> f1 = LAZY(8);
    std::shared_future<int> f2 = LAZY(2);
    std::shared_future<int> f3 = LAZY(f1.get() * f2.get(), f1, f2);

    std::cout << "f3 = " << f3.get() << std::endl;
    std::cout << "f2 = " << f2.get() << std::endl;
    std::cout << "f1 = " << f1.get() << std::endl;
    return 0;
}

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

#include <stdatomic.h>

#define lazy(var_type) lazy_ ## var_type

#define def_lazy_type( var_type ) \
    typedef _Atomic var_type _atomic_ ## var_type; \
    typedef _atomic_ ## var_type * lazy(var_type);  //pointer to atomic type

#define def_lazy_variable(var_type, var_name ) \
    _atomic_ ## var_type _ ## var_name; \
    lazy_ ## var_type var_name = & _ ## var_name;

#define assign_lazy( var_name, val ) atomic_store( & _ ## var_name, val )
#define eval_lazy(var_name) atomic_load( &(*var_name) )

#include <stdio.h>

def_lazy_type(int)

void print_power2 ( lazy(int) i )
{
      printf( "%d\n", eval_lazy(i) * eval_lazy(i) );
}

typedef struct {
    int a;
} simple;

def_lazy_type(simple)

void print_simple ( lazy(simple) s )
{
    simple temp = eval_lazy(s);
    printf("%d\n", temp.a );
}


#define def_lazy_array1( var_type, nElements, var_name ) \
    _atomic_ ## var_type  _ ## var_name [ nElements ]; \
    lazy(var_type) var_name = _ ## var_name; 

int main ( )
{
    //declarations
    def_lazy_variable( int, X )
    def_lazy_variable( simple, Y)
    def_lazy_array1(int,10,Z)
    simple new_simple;

    //first the lazy int
    assign_lazy(X,111);
    print_power2(X);

    //second the lazy struct
    new_simple.a = 555;
    assign_lazy(Y,new_simple);
    print_simple ( Y );

    //third the array of lazy ints
    for(int i=0; i < 10; i++)
    {
        assign_lazy( Z[i], i );
    }

    for(int i=0; i < 10; i++)
    {
        int r = eval_lazy( &Z[i] ); //must pass with &
        printf("%d\n", r );
    }

    return 0;
}

Вы заметите, что в функции print_power2 есть макрос под названием eval_lazy, который не делает ничего, кроме разыменования указателя для получения значения непосредственно перед тем, когда оно действительно необходимо. Доступ к ленивому типу осуществляется атомарно, поэтому он полностью потокобезопасен.