Способ достижения ленивой оценки в C++

Question

Так что я отвечал на вопрос о ленивой оценке ( здесь мой ответ для этого случая излишен, но идея кажется интересной), и это заставило меня задуматься о том, как ленивая оценка может быть выполнена в C++. Я придумал способ, но я не был уверен во всех подводных камнях в этом. Есть ли другие способы достижения ленивой оценки? как это может быть сделано? Какие подводные камни и этот и другие конструкции?

Вот моя идея:

#include <iostream>
#include <functional>
#include <memory>
#include <string>

#define LAZY(E) lazy<decltype((E))>{[&](){ return E; }}

template<class T>
class lazy {
private:
    typedef std::function<std::shared_ptr<T>()> thunk_type;
    mutable std::shared_ptr<thunk_type> thunk_ptr;
public:
    lazy(const std::function<T()>& x)
        : thunk_ptr(
            std::make_shared<thunk_type>([x](){
                return std::make_shared<T>(x());
            })) {}
    const T& operator()() const {
        std::shared_ptr<T> val = (*thunk_ptr)();
        *thunk_ptr = [val](){ return val; };
        return *val;
    }
    T& operator()() {
        std::shared_ptr<T> val = (*thunk_ptr)();
        *thunk_ptr = [val](){ return val; };
        return *val;
    }
};

void log(const lazy<std::string>& msg) {
    std::cout << msg() << std::endl;
}

int main() {
    std::string hello = "hello";
    std::string world = "world";
    auto x = LAZY((std::cout << "I was evaluated!\n", hello + ", " + world + "!"));
    log(x);
    log(x);
    log(x);
    log(x);
    return 0;
}

Некоторые вещи, которые меня волновали в моем дизайне.

• У decltype есть несколько странных правил. Есть ли у меня использование decltype есть ошибки? Я добавил дополнительные скобки вокруг E в макросе LAZY, чтобы убедиться, что отдельные имена обрабатываются справедливо, как ссылки, как vec[10]. Есть ли другие вещи, которые я не учитываю?
• В моем примере много слоев косвенности. Кажется, этого можно избежать.
• Правильно ли запоминается результат, так что независимо от того, что или сколько вещей ссылаются на ленивое значение, оно будет оцениваться только один раз (в этом я довольно уверен, но ленивая оценка плюс тонны общих указателей могут привести меня в замешательство)

о чем ты думаешь?

Answer 1

• Вы можете хотеть иметь thunk_type и ссылка на него как на отдельные объекты. Прямо сейчас копия lazy<T> ничего не получит от оценки происхождения. Но в этом случае вы получите дополнительный косвенный доступ.
• Иногда вы можете избавиться от переноса в std::function, просто используя шаблоны.
• Я не уверен, что значение должно быть shared_ptr. Может быть, звонящий должен решить это.
• Вы собираетесь производить новые замыкания при каждом доступе.

Рассмотрим следующую модификацию:

template<typename F>
lazy(const F& x) :
  thunk_ptr([&x,&this](){
    T val = (*x)();
    thunk_ptr = [val]() { return val; };
    return val;
  })
{}

Или альтернативная реализация может выглядеть так:

template<typename F>
auto memo(const F &x) -> std::function<const decltype(x()) &()> {
    typedef decltype(x()) return_type;
    typedef std::function<const return_type &()> thunk_type;
    auto thunk_ptr = std::make_shared<thunk_type>();
    auto *thunk_cptr = thunk_ptr.get();

    // note that this lambda is called only from scope which holds thunk_ptr
    *thunk_ptr = [thunk_cptr, &x]() {
        auto val = std::move(x());
        auto &thunk = *thunk_cptr;
        thunk = [val]() { return val; };
        // at this moment we can't refer to catched vars
        return thunk();
    };

    return [thunk_ptr]() { return (*thunk_ptr)(); };
};

Answer 2

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

Мемоизация - это старый термин, который часто означает табулирование результата функции. Ни один современный язык не делает это (возможно, PROLOG), это чрезвычайно дорого. Полная ленивость (никогда не вычисляющая одну вещь дважды) достигается в процессе лямбда-лифтинга, то есть устранения свободных переменных (путем помещения их в качестве аргументов). При полностью ленивом подъеме лямбды это максимальные свободные выражения, которые снимаются (скажем, x является свободным, поэтому вхождение sqrt x заменяется новым аргументом, sqrtx). Существует также так называемое оптимальное сокращение.

Я не думаю, что есть другие способы сделать это. Почему это намного быстрее в ленивом функциональном языке, таком как Haskell? Ну, в общем, ссылки не подсчитываются, то есть анализ строгости (строгий - это противоположность ленивому), который позволяет компилятору заранее знать, что некоторые вещи лучше оценивать строго, распаковывая значения, которые оцениваются строго и относятся к известному типу машины.... не говоря уже о других типичных оптимизациях функционального языка программирования... Но, по сути, если вы посмотрите на реализацию машины сокращения графов, если вы посмотрите на эволюцию стека, вы увидите, что в основном вы передаете функции на стек вместо аргументов, и это в основном все.

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

Предположим, что все ваши "узлы" являются подклассами главного суперкласса, называемого "узлом", в котором есть только виртуальная функция, которая вычисляет значение... тогда она может быть "перезаписана" другой, которая будет возвращать уже вычисленное значение. Именно поэтому, с указателями на функции, они говорят, что STG-машина Haskell является "безметочной" (G-машиной без привязки), потому что они не помечают элементы данных, вместо этого они используют указатель на функцию, которая либо вычисляет, либо возвращает Значение.

Я не думаю, что это может быть сделано не так эффективно в C++, как в Haskell... если только мы не начнем думать о реализации C++ совершенно по-другому (можно и нужно делать). Мы привыкли к таким сложным прологам и эпилогам, сложным соглашениям о вызовах и т. Д. Вызов функции слишком бюрократичен в C/C++.

Теперь книга для чтения, когда вы чувствуете себя ленивым, определенно "Реализация языков функционального программирования" Саймона Пейтона-Джонса. Тем не менее, современная реализация описана в свободно доступной статье "Реализация функциональных языков на стандартном оборудовании: G-машина без тегов Spineless", в которой очень приятно прочитать об оптимизации реализации, но другая - это та, которую нужно прочитать, чтобы понять основы.

Answer 3

Вот еще один аспект лени, который был необходим для меня.

// REMARK: Always use const for lazy objects. Any, even const operation coming from ValueType called over Lazy<ValueType> freezes it.
template < typename ValueType >
struct Lazy
{
    typedef ValueType              Value;
    typedef std::function<Value()> Getter;

    Lazy( const Value& value = Value() )
        : m_value( value )
    { }

    Lazy( Value&& value )
        : m_value( value )
    { }

    Lazy( Lazy& other )
        : Lazy( const_cast<const Lazy&>(other) )
    { }

    Lazy( const Lazy&  other ) = default;
    Lazy(       Lazy&& other ) = default;
    Lazy& operator = ( const Lazy&  other ) = default;
    Lazy& operator = (       Lazy&& other ) = default;


    template < typename GetterType,
               typename = typename std::enable_if<std::is_convertible<GetterType,Getter>::value>::type >
    Lazy( GetterType&& getter )
        : m_pGetter( std::make_shared<Getter>( std::move(getter) ) )
    { }

    void Freeze()
    {
        if ( m_pGetter )
        {
            m_value = (*m_pGetter)();
            m_pGetter.reset();
        }
    }

    operator Value () const
    {
        return m_pGetter ? (*m_pGetter)() : m_value;
    }

    operator Value& ()
    {
        Freeze();
        return m_value;
    }

private:
    Value                   m_value;
    std::shared_ptr<Getter> m_pGetter;
};

С использованием, как это:

template < typename VectorType,
           typename VectorIthValueGetter = std::function<typename VectorType::const_reference (const size_t)>
         >
static auto MakeLazyConstRange( const VectorType& vector )
    -> decltype( boost::counting_range( Lazy<size_t>(), Lazy<size_t>() ) | boost::adaptors::transformed( VectorIthValueGetter() ) )
{
    const Lazy<size_t> bb( 0 ) ;
    const Lazy<size_t> ee( [&] () -> size_t { return vector.size(); } );
    const VectorIthValueGetter tt( [&] (const size_t i) -> typename VectorType::const_reference { return vector[i]; } );
    return boost::counting_range( bb, ee ) | boost::adaptors::transformed( tt );
}

и позже:

std::vector<std::string> vv;
boost::any_range<const std::string&, boost::forward_traversal_tag, const std::string&, int>
    rr = MakeLazyConstRange( vv );

vv.push_back( "AA" );
vv.push_back( "BB" ); 
vv.push_back( "CC" ); 
vv.push_back( "DD" ); 

for ( const auto& next : rr )
    std::cerr << "---- " << next << std::endl;

Answer 4

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

1. Экономия времени на вызов конструктора перемещения для инкапсулированного типа (когда функция инициализации возвращает результат).
2. Конструктор копирования и оператор присваивания для инкапсулированного типа не требуются (только если вы хотите сделать это для типа Lazy).

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

#pragma once
#include <mutex>
#include <atomic>
#include <functional>

template <typename T>
struct Lazy
{
    using value_type = T;

    Lazy() : mInitializer(nullptr) {}

    Lazy(const std::function<void(T&)>& initializer)
        : mInitializer(std::move(initializer))
        , mInitFlag(false)
    { }

    Lazy(const Lazy& other)
        : mInitializer(other.mInitializer)
        , mInitFlag(other.mInitFlag.load())
        , mValue(other.mValue)
    { }

    Lazy(Lazy&& other)
        : mInitializer(std::move(other.mInitializer))
        , mInitFlag(other.mInitFlag.load())
        , mValue(std::move(other.mValue))
    { }

    Lazy& operator=(const std::function<void(T&)>& initializer)
    {
        mInitFlag.store(false);
        mInitializer = initializer;
        return *this;
    };

    Lazy& operator=(const Lazy& rhs)
    {
        if (this != &rhs)
        {
            std::lock_guard<std::mutex> lock(mMutex);

            mInitializer = rhs.mInitializer;
            mInitFlag = rhs.mInitFlag.load();
            if (mInitFlag) {
                mValue = rhs.mValue;
            }
        }
        return *this;
    };

    Lazy& operator=(Lazy&& rhs)
    {
        if (this != &rhs)
        {
            std::lock_guard<std::mutex> lock(mMutex);

            mInitializer = std::move(rhs.mInitializer);
            mInitFlag = rhs.mInitFlag.load();
            if (mInitFlag) {
                mValue = std::move(rhs.mValue);
            }
        }
        return *this;
    };

    inline operator T&()                { return get(); }
    inline operator const T&() const    { return get(); }

    inline T& get()             { return const_cast<T&>(_getImpl()); }
    inline const T& get() const { return _getImpl(); }

private:
    const T& _getImpl() const
    {
        if (mInitializer != nullptr && mInitFlag.load() == false)
        {
            std::lock_guard<std::mutex> lock(mMutex);
            if (mInitFlag.load() == false)
            {
                mInitializer(mValue);
                mInitFlag.store(true);
            }
        }
        return mValue;
    }

    mutable std::mutex mMutex;
    std::function<void(T&)> mInitializer;
    mutable std::atomic_bool mInitFlag;
    mutable T mValue;   // Value should be after mInitFlag due initialization order
};

Образец использования:

using ValuesList = std::vector<int>;
Lazy<ValuesList> lazyTest = [](ValuesList& val) { val.assign({1, 2, 3, 4, 5}); };
const Lazy<ValuesList> lazyTestConst = lazyTest;

ValuesList& value = lazyTest;
const ValuesList& cvalue = lazyTestConst;

Answer 5

Библиотека Boost Phoenix реализует Lazyness, среди прочих тонкостей FP, но я не использовала себя сама. Я не уверена, насколько хорошо она играет с C++ 11, или, возможно, она сделала ее хотя бы частично стандартом 2011 года.

http://www.boost.org/doc/libs/1_43_0/libs/spirit/phoenix/doc/html/index.html