Ленивые вычисления в с++0x, тест новых фич

    Всем привет. А особенно тем, кто пишет на плюсах и интересуется грядущими изменениями языка.
    Для исследования фич нового стандарта С++ я сделал забавную штуку — функцию для превращения простого функтора в ленивый. Т.е. вычисляемый не более одного раза, и только при первом обращении.
    Для использования вам понадобится простой функтор, без аргументов, возвращающий значение.
    Применяете к нему calc_once(some_func) — и он становится ленивым.

    auto my_func = calc_once([]{ return SomeHugeCalculation(); });
    if ((my_func() && some_case) || (!my_func() && some_other_case))
    {
    }


    * This source code was highlighted with Source Code Highlighter.


    Под хабракатом код, там и auto, и decltype, и лямбды.

    UPD. Спасибо за карму. Перенес в блог С++.


    #include <boost/optional.hpp>

    //делает лямбда-выражение рассчитываемым только один раз (при последующих вызовах возвращает кэшированное значение)
    //использование: auto my_func = calc_once([]{ return SomeHugeCalculation(); });

    template<typename LambdaFunc, typename result_type>
    class calc_once_func
    {
    public:
      calc_once_func(LambdaFunc func) : func_(func) {}
      result_type operator()()
      {
        return val_.is_initialized() ? val_.get() : (val_ = func_()).get();
      };
    private:
      boost::optional<result_type> val_;
      LambdaFunc func_;
    };

    template<typename LambdaFunc>
    auto calc_once(LambdaFunc func) -> calc_once_func<LambdaFunc, decltype(func())>
    {
      return calc_once_func<LambdaFunc, decltype(func())>(func);
    }


    * This source code was highlighted with Source Code Highlighter.

    Комментарии 29

      0
      А как с поддержкой всего этого дела? GCC держит?
        0
        VS2010 держит. У GCC поддержка лямбд вроде в отдельном бранче была.
          +4
          visual studio 2010 RC и GCC 4.5 такое осилят.
          В gcc 4.4 не хватает лямбд.
          Студия от gcc 4.5 отстает в поддержке списков инициализации (но их тут нет).
            0
            последние снапшоты gcc из оверлея toolchain деражат
            0
            Извините, промазал. Отвечал Gorthauer87 (-:
          0
          Честно говоря, словосочетание «ленивые вычисления» у меня ассоциируются с несколько иным смыслом. Но вообще код выглядит неплохо.
            +1
            Ориентировался на википедию:
            «Отложенные вычисления, ленивые вычисления или нестрогие вычисления — концепция в некоторых языках программирования, согласно которой вычисления следует откладывать до тех пор, пока не понадобится их результат.»

            Код функтора выполнится при первом требовании, сохранит результат для последующих вызовов.
            Если функтор не будет вызван — никакой работы не будет.
            Если будет вызван несколько раз — работа произойдет один раз, при первом вызове.

            Разве не лениво? :)
              +1
              Лениво было бы вот так:
                +7
                Пардон, отправил случайно :)

                В общем, лениво было бы вот так:

                int a = some_lazy_func();  // по идее возвращает какое-то значение,
                                           // но на самом деле пока ничего не вычислялось
                
                
                cout << a; // нужно отобразить результат, значит,
                           // самое время вычислить то, что должны были
                
                
                  +1
                  Совсем такое только компилятор может обеспечить.
                  С функтором немного сложнее, зато имеем явную декларацию поведения — откладывать или не откладывать.
                  auto a = calc_once([]{ return some_func(); });
                  cout << a();
                    0
                    Ну, поэтому я и удивился немного такому названию.

                    А чем этот Ваш пример будет отличаться от:

                    auto a = []{ return some_func(); };
                    cout << a();
                    

                    ?
                      +1
                      А, ну в общем я понял. Если мы будем вызывать функтор несколько раз в разных местах, то он будет вычисляться только единожды. То есть фактически Вы просто запомнили возвращённое значение, но внутри самого функтора. Не очень-то лениво :)
                  0
                  Не совсем лениво. Вы правильно цитируете, что «вычисления откладываются до тех пор, пока не понадобится их результат». Но на самом деле методика с кэшированием недостаточно ленива.

                  Один из любимых примеров в ленивых языках — это численный поиск решения уравнения. Представьте себе, что решение итеративно ищется алгоритмом x[i+1] = F(x[i]). Если разница между соседними решениями меньше e, алгоритм прекращает работу.

                  Так вот, в ленивом языке можно запустить генерацию бесконечного списка x, а затем просто пройтись по нему и посмотреть, где соседние элементы близки. В реальности пока мы не прочтём значение x[i], его и не вычисляют. Я не думаю, что с помощью кэширование такого можно добиться.
                    0
                    Все просто: x — это ленивый генератор ленивых функторов :).
                    Когда от него просят x[i], и в своем контейнере функторов для i у него ничего нет — он делает ленивый функтор и сохраняет его в контейнер. Функторы знают свой индекс и знают X, у которого могут запрашивать доступ к соседям.

                    И вся эта чехарда, чтобы написать что-то вроде:
                    for (unsigned i = 0; ( x[i + 1]() - x[i]() ) >= eps; ++i);
                      0
                      Ну понятно, что можно левой ногой правое ухо чесать :)

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

                      Если ленивые вычисления доступны, можно писать эти алгоритмы независимо друг от друга, а потом тривиально объединить. Как обычно, просто повышаем абстракцию, ради этого все надстройки над Ассемблером и выдуманы…
                0
                Я ещё не слишком знаком со стандартом C++0x, но мне кажется, что вы просто написали урезанную версию std::future. Разве что там вычисление асинхронное.
                  0
                  Спасибо за наводку, но это не совсем то.
                  Насколько я понял, std::future делает вычисления в параллельном потоке, и начинает сразу (т.е. нифига не ленится :)).
                  Ее стоит использовать, когда вам гарантировано понадобится результат, но вы хотите, пока он считается, заняться чем-нибудь другим.
                  –1
                  Это не ленивые вычисления, а типа «чистая» функция с некоторой оптимизацией. Например, в Digital Mars D есть для таких случаев ключевое слово pure, а компилятор уже сам занимается запоминанием готовых результатов.

                  ленивые вычисления в фунциональных языках — это получение результата только по непосредственному требованию; к оптимизации отношение такая фича имеет только косвенное.
                    +1
                    Это именно класс, реализующий ленивое вычисление. pure в Digital Mars D не имеет к данному топику никакого отношения, как и lazy, который не запоминает результат первого вычисления.

                    Кстати, AndrewAZ, у этой реализации на C++ будут проблемы, если функция не чистая т.к. при изменении глобального состояния может измениться результат вызова функции, а при использовании calc_once результат не изменится.

                    Вы можете возразить, что использовать глобальное состояние — плохо, на что я отвечу, что в таком случае вам не нужен C++ ;)
                      0
                      ну я не очень знаю D, факт, но вот с функциональными языками знаком нормально.

                      Где здесь ленивые вычисления?
                        +1
                        С Вики:

                        «Отложенные вычисления, ленивые вычисления или нестрогие вычисления (англ. lazy evaluation) — концепция в некоторых языках программирования, согласно которой вычисления следует откладывать до тех пор, пока не понадобится их результат.»

                        с английской вики:

                        «In computer programming, lazy evaluation is the technique of delaying a computation until the result is required.»
                      0
                      А зачем вам дополнительная анонимная функция понадобилась?
                      Почему не просто

                      auto my_func = calc_once(SomeHugeCalculation);

                      Так выразительней — практически связное предложение получается :)

                      Да и стрелочка лишняя, можно так:

                      template
                      calc_once_func calc_once(LambdaFunc func)
                      {
                      return calc_once_func(func);
                      }

                      А так — моя версия буста не захотела собираться:

                      template
                      class calc_once_func
                      {
                      public:
                      typedef decltype(LambdaFunc) result_type; //(*)

                      public:
                      calc_once_func(LambdaFunc func): func_(func) {}
                      result_type operator()()
                      {
                      return val_.is_initialized()? val_.get(): (val_ = func_()).get();
                      };
                      private:
                      boost::optional val_; //1>c:\boost\boost_1_37_0\boost\optional\optional.hpp(110): error C2070: '': illegal sizeof operand

                      LambdaFunc func_;
                      };

                      template
                      calc_once_func calc_once(LambdaFunc func)
                      {
                      return calc_once_func(func);
                      }
                        0
                        Да и стрелочка лишняя, можно так:
                        template<typename LambdaFunc>
                        calc_once_func<LambdaFunc, decltype(LambdaFunc)> calc_once(LambdaFunc func)
                        {
                         return calc_once_func<LambdaFunc, decltype(LambdaFunc)>(func);
                        }

                        Так не собралась моя версия буста:

                        template<typename LambdaFunc>
                        class calc_once_func
                        {
                        public:
                          typedef decltype(LambdaFunc) result_type;

                        public:
                         calc_once_func(LambdaFunc func): func_(func) {}
                         result_type operator()()
                         {
                          return val_.is_initialized()? val_.get(): (val_ = func_()).get();
                         };
                        private:
                         boost::optional<result_type> val_; //1>c:\boost\boost_1_37_0\boost\optional\optional.hpp(110): error C2070: '': illegal sizeof operand
                         LambdaFunc func_;
                        };

                        template<typename LambdaFunc>
                        calc_once_func<LambdaFunc> calc_once(LambdaFunc func)
                        {
                         return calc_once_func<LambdaFunc>(func);
                        }

                        int SomeHugeCalculation()
                        {
                          return 7;
                        }

                        int _tmain(int argc, _TCHAR* argv[])
                        {
                          auto my_func = calc_once(SomeHugeCalculation);
                          if (my_func())
                          {

                          }

                          return 0;
                        }

                        * This source code was highlighted with Source Code Highlighter.
                          0
                          Не собирается, потому что decltype(LambdaFunc) — это совсем не то. Для того там и стрелочка чтобы написать decltype(func()) — т.е. тип, который бы вернул объект(функтор) func, в ответ на свою операцию скобочки.
                          Стрелочка для того чтобы перенести определение возвращаемого значения ф-ции правее, в то место, где входной параметр ф-ции, объект func уже определен и может нам сказать, что он возвращает на операцию скобочки.

                          А decltype(LambdaFunc) — это идентично просто написать LambdaFunc, или даже просто не имеет значения.
                            0
                            Так то работает:
                            Да и стрелочка лишняя, можно так:
                            template<typename LambdaFunc>
                            calc_once_func<LambdaFunc, decltype(LambdaFunc)> calc_once(LambdaFunc func)
                            {
                            return calc_once_func<LambdaFunc, decltype(LambdaFunc)>(func);
                            }

                            * This source code was highlighted with Source Code Highlighter.

                            Ибо:
                            If the expression parameter is a call to a function or an overloaded operator function, decltype(expression) is the return type of the function. Parentheses around an overloaded operator are ignored.
                              0
                              Первая посылка: компилятор вам заявляет «дружище, что бы у тебя в качестве result_type не было определено, но sizeof я для этого сделать никак не могу».

                              Вторая посылка: обычно компиляторы не испытывают проблем с sizeof(int).

                              Вывод: result_type не является типом int.

                              «If the expression parameter is a call to a function...» — означает «Если вы в скобочках написали что-то, что похоже на вызов ф-ции...».
                              А вызов ф-ции/функтора обычно выглядит как применение оператора скобочки для объекта ф-ции/функтора (т.е. func()), а не чистое написание типа ф-ции/функтора (LambdaFunc).
                                0
                                template<typename LambdaFunc, typename result_type = decltype(LambdaFunc()())>
                                class calc_once_func
                                {

                                };

                                Так работает, но Студия 2010 говорит что не стандарт.
                        +5
                        Описанный процесс называется мемоизацией. www.botik.ru/~abram/blackhead/s_09_a.ru.html
                        И в С++ применять его, как мне кажется, нужно с умом. Потому что нельзя контролировать «чистоту» функции от влияния глобальных переменных. А что если они изменятся, а закэшировано будет то же самое.

                        За пост спасибо!

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                        Самое читаемое