Отложенные вычисления в C++

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

то, что Конрад уже объяснил, можно поставить дальше, чтобы поддерживать вложенные вызовы операторов, все выполняемые лениво. В Примере Конрада у него есть объект выражения, который может хранить ровно два аргумента для ровно двух операндов одной операции. Проблема в том, что он будет выполнять только один подвыражение лениво, что хорошо объясняет концепцию в ленивой оценке, выраженной простыми словами, но не улучшает производительность существенно. Другой пример также хорошо показывает, как можно подать заявку 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= и добавить подходящий конструктор для типа точки и принять 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. Это могла быть большая матрица со множеством полей. Но в то время, когда результат необходим, мы вычисляем его лениво.

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

Я думаю о реализации шаблона класса, который использует 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) в точку, это не достаточно лениво.И когда компилятор решает, что конвертировать, он жалуется. Потому что никто не лучше другого . Вот мое расширение: добавить еще один перегруженный оператор +

    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);

}

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

C++0x это хорошо и все.... но для тех из нас, кто живет в настоящем, у вас есть Boost Lambda library и Boost Phoenix. С целью привлечения большого количества функционального программирования на C++.

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

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

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);
    }
}

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

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

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;
}

давайте возьмем Haskell в качестве нашего вдохновения-он ленив до глубины души. Кроме того, давайте иметь в виду, как Linq в C# использует Перечислители в монадическом (urgh - вот слово - извините) способе. Последнее не менее важно, давайте иметь в виду, что сопрограммы должны предоставлять программистам. А именно разделение вычислительных шагов (например, производителя, потребителя) друг от друга. И давайте попробуем подумать о том, как сопрограммы относятся к ленивости.

все вышесказанное как-то связанный.

Далее, давайте попробуем извлечь наше личное определение того, что такое" ленивый".

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

позволяет получить бетон и в некоторых код. Нам нужен пример для этого! Здесь я выбираю "проблему" fizzbuzz в качестве примера, просто по той причине, что есть какое-то хорошее, ленивое решение.

в Haskell, это выглядит так:

module FizzBuzz
( fb
)
where
fb n =
    fmap merge fizzBuzzAndNumbers
    where
        fizz = cycle ["","","fizz"]
        buzz = cycle ["","","","","buzz"]
        fizzBuzz = zipWith (++) fizz buzz
        fizzBuzzAndNumbers = zip [1..n] fizzBuzz
        merge (x,s) = if length s == 0 then show x else s

функция Хаскелла cycle создает бесконечный список (лень, конечно!) из конечного списка, просто повторяя значения в конечном списке навсегда. В нетерпеливом стиле программирования, написание чего-то подобного вызовет тревожные звонки (переполнение памяти, бесконечное петли!). Но не так на ленивом языке. Хитрость заключается в том, что ленивые списки не вычисляются сразу. А может, и никогда. Обычно только столько, сколько требует последующий код.

третья строка в where блок выше создает еще один ленивый!! список, путем объединения бесконечных списков fizz и buzz С помощью одного рецепта двух элементов "объединить строковый элемент из любого входного списка в одну строку". Опять же, если бы это было немедленно оценено, мы бы придется ждать, пока у нашего компьютера закончатся ресурсы.

в 4-й строке мы создаем кортежи членов конечного ленивого списка [1..n] С нашим бесконечным ленивым списком fizzbuzz. Результат все равно ленивый.

даже в основном корпусе нашего fb функция, нет необходимости, чтобы получить нетерпеливый. Вся функция возвращает список с решением, которое само по себе - снова-лениво. Вы могли бы также подумать о результате fb 50 как вычисление, которое вы можете (частично) оцените позже. Или объедините с другими вещами, что приведет к еще большей (ленивой) оценке.

Итак, чтобы начать работу с нашей версией "fizzbuzz" на C++, нам нужно подумать о том, как объединить частичные шаги наших вычислений в более крупные биты вычислений, каждый из которых по мере необходимости рисует данные из предыдущих шагов.

вы можете увидеть полную историю в суть шахте.

вот основные идеи, лежащие в основе код:

заимствуя из C# и Linq, мы "изобретаем" stateful, generic type Enumerator, которая содержит
- Текущее значение частичного вычисления
- Состояние частичного вычисления (так что мы можем производить последующие значения)
- Рабочая функция, которая производит следующее состояние, следующее значение и bool, который указывает, есть ли больше данных или если перечисление подошло к концу.

для того, чтобы иметь возможность сочинять Enumerator<T,S> экземпляр by средства власти . (точка), этот класс также содержит функции, заимствованные из классов типа Haskell, таких как Functor и Applicative.

рабочая функция для перечислителя всегда имеет вид:S -> std::tuple<bool,S,T здесь S - это переменная универсального типа, представляющая состояние и T является переменной универсального типа, представляющей значение-результат шага вычисления.

все это уже видно в первые строки Enumerator класс определение.

template <class T, class S>
class Enumerator
{
public:
    typedef typename S State_t;
    typedef typename T Value_t;
    typedef std::function<
        std::tuple<bool, State_t, Value_t>
        (const State_t&
            )
    > Worker_t;

    Enumerator(Worker_t worker, State_t s0)
        : m_worker(worker)
        , m_state(s0)
        , m_value{}
    {
    }
    // ...
};

Итак, все, что нам нужно для создания конкретного экземпляра перечислителя, нам нужно создать рабочую функцию, иметь начальное состояние и создать экземпляр Enumerator С этими двумя аргументами.

вот пример - функция range(first,last) создает конечный диапазон значений. Это соответствует ленивому списку в мире Haskell.

template <class T>
Enumerator<T, T> range(const T& first, const T& last)
{
    auto finiteRange =
        [first, last](const T& state)
    {
        T v = state;
        T s1 = (state < last) ? (state + 1) : state;
        bool active = state != s1;
        return std::make_tuple(active, s1, v);
    };
    return Enumerator<T,T>(finiteRange, first);
}

и мы можем использовать эту функцию, например так: auto r1 = range(size_t{1},10); - мы создали себе ленивый список из 10 элементов!

теперь, все отсутствует для нашего " вау " опыта, чтобы увидеть, как мы можем составить перечислители. Возвращаясь к Хаскеллам cycle функция, которая является своего рода прохладно. Как бы это выглядело в нашем мире c++? Вот это:

template <class T, class S>
auto
cycle
( Enumerator<T, S> values
) -> Enumerator<T, S>
{
    auto eternally =
        [values](const S& state) -> std::tuple<bool, S, T>
    {
        auto[active, s1, v] = values.step(state);
        if (active)
        {
            return std::make_tuple(active, s1, v);
        }
        else
        {
            return std::make_tuple(true, values.state(), v);
        }
    };
    return Enumerator<T, S>(eternally, values.state());
}

он принимает в качестве входных данных и возвращает перечислитель перечислитель. Локальная (лямбда) функция eternally просто сбрасывает входное перечисление до его начального значения всякий раз, когда у него заканчиваются значения и вуаля - у нас есть бесконечное, когда-либо повторяя версию списка мы дали в качестве аргумента::auto foo = cycle(range(size_t{1},3)); и мы уже можем бесстыдно сочинять наши ленивые "вычисления".

zip это хороший пример, показывающий, что мы можем создать новый перечислитель с двумя входными счетчиками. Результирующий перечислитель дает столько значений, сколько меньше любого из входных перечислителей (кортежи с 2 элементами, по одному для каждого входного перечислителя). Я реализовал zip внутри class Enumerator сам по себе. Вот как это выглядит например:

// member function of class Enumerator<S,T> 
template <class T1, class S1>
auto
zip
( Enumerator<T1, S1> other
) -> Enumerator<std::tuple<T, T1>, std::tuple<S, S1> >
{
    auto worker0 = this->m_worker;
    auto worker1 = other.worker();
    auto combine =
        [worker0,worker1](std::tuple<S, S1> state) ->
        std::tuple<bool, std::tuple<S, S1>, std::tuple<T, T1> >
    {
        auto[s0, s1] = state;
        auto[active0, newS0, v0] = worker0(s0);
        auto[active1, newS1, v1] = worker1(s1);
        return std::make_tuple
            ( active0 && active1
            , std::make_tuple(newS0, newS1)
            , std::make_tuple(v0, v1)
            );
    };
    return Enumerator<std::tuple<T, T1>, std::tuple<S, S1> >
        ( combine
        , std::make_tuple(m_state, other.state())
        );
}

обратите внимание, как "объединение" также заканчивается объединением состояния обоих источников и значений обоих источников.

как этот пост уже TL; DR;для многих, здесь...

резюме

да, ленивая оценка может быть реализована в C++. Здесь я сделал это, заимствовав имена функций из haskell и парадигму из перечислителей C# и Linq. Там может быть сходство с питонами itertools, кстати. Я думаю, что они придерживались аналогичного подхода.

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

и каков был бы этот ответ без окончательной версии fizzbuz на C++, а? Вот это:

std::string fizzbuzz(size_t n)
{
    typedef std::vector<std::string> SVec;
    // merge (x,s) = if length s == 0 then show x else s
    auto merge =
        [](const std::tuple<size_t, std::string> & value)
        -> std::string
    {
        auto[x, s] = value;
        if (s.length() > 0) return s; 
        else return std::to_string(x);
    };

    SVec fizzes{ "","","fizz" };
    SVec buzzes{ "","","","","buzz" };

    return
    range(size_t{ 1 }, n)
    .zip
        ( cycle(iterRange(fizzes.cbegin(), fizzes.cend()))
          .zipWith
            ( std::function(concatStrings)
            , cycle(iterRange(buzzes.cbegin(), buzzes.cend()))
            )
        )
    .map<std::string>(merge)
    .statefulFold<std::ostringstream&>
    (
        [](std::ostringstream& oss, const std::string& s) 
        {
            if (0 == oss.tellp())
            {
                oss << s;
            }
            else
            {
                oss << "," << s;
            }
        }
        , std::ostringstream()
    )
    .str();
}

и... чтобы привести точку домой еще дальше-здесь вариация fizzbuzz, которая возвращает "бесконечный список" для вызывающего абонента:

typedef std::vector<std::string> SVec;
static const SVec fizzes{ "","","fizz" };
static const SVec buzzes{ "","","","","buzz" };

auto fizzbuzzInfinite() -> decltype(auto)
{
    // merge (x,s) = if length s == 0 then show x else s
    auto merge =
        [](const std::tuple<size_t, std::string> & value)
        -> std::string
    {
        auto[x, s] = value;
        if (s.length() > 0) return s;
        else return std::to_string(x);
    };

    auto result =
        range(size_t{ 1 })
        .zip
        (cycle(iterRange(fizzes.cbegin(), fizzes.cend()))
            .zipWith
            (std::function(concatStrings)
                , cycle(iterRange(buzzes.cbegin(), buzzes.cend()))
            )
        )
        .map<std::string>(merge)
        ;
    return result;
}

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

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

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