Подтвердить что ты не робот

Ленькая оценка в С++

У С++ нет встроенной поддержки для ленивой оценки (как это делает Haskell).

Мне интересно, можно ли реализовать ленивую оценку на С++ разумным образом. Если да, как бы вы это сделали?

EDIT: Мне нравится ответ Конрада Рудольфа.

Мне интересно, возможно ли реализовать его более общим образом, например, используя параметризованный класс lazy, который по существу работает для T, как матрица_add работает для матрицы.

Любая операция на T вернется вместо лени. Единственная проблема - хранить аргументы и код операции внутри самого ленивого. Может ли кто-нибудь увидеть, как улучшить это?

4b9b3361

ОТВЕТЫ

Ответ 1

Мне интересно, можно ли реализовать ленивую оценку на С++ разумным образом. Если да, как бы вы это сделали?

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

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.

EDIT Я должен был быть более явным. Как бы то ни было, код не имеет смысла, потому что, хотя оценка происходит лениво, все равно происходит в одном выражении. В частности, другое дополнение будет оценивать этот код, если структура matrix_add не изменена, чтобы обеспечить добавление в цепочку. С++ 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. Я перегрузил эту функцию для своего строкового типа, чтобы вернуть прокси-сервер, содержащий ссылку на мою строку, а также желаемую начальную и конечную позицию. Только когда эта подстрока была фактически использована, она запросила API C для извлечения этой части строки.

Ответ 2

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

Ответ 6

Я думаю о внедрении класса шаблона, который использует 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, но я не уверен, повлияет ли это на производительность.

Ответ 7

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

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

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

          return instanceA;
     }
};

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

Как недавно запросили в вопросе.
И украсть дизайн Конрада Рудольфа и расширить его.

Объект Lazy:

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

Ответ 8

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

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!

Ответ 9

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

Ответ 10

В С++ 11 ленивая оценка, подобная hiapay, может быть достигнута с помощью std:: shared_future. Вы все еще должны инкапсулировать вычисления в lambdas, но 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;
}

Ответ 11

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