c ++ 11 — способ достижения ленивой оценки в переполнении стека
Вот и я отвечал на вопрос о ленивой оценке (Вот, мой ответ для этого случая излишен, но идея кажется интересной), и это заставило меня задуматься о том, как ленивые вычисления могут быть выполнены в 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]. Есть ли другие вещи, которые я не учитываю?
- В моем примере много слоев косвенности. Кажется, этого можно избежать.
- Правильно ли запоминается результат, так что независимо от того, что или сколько вещей ссылаются на ленивое значение, оно будет оцениваться только один раз (в этом я довольно уверен, но ленивая оценка плюс тонны общих указателей могут привести меня в замешательство)
о чем ты думаешь?
Решение
- Вы можете хотеть иметь
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)(); };
};
Другие решения
Да, то, что у вас есть, лениво. По сути, просто передайте функцию, которая вычисляет аргумент вместо аргумента. После оценки объект заменяется вычисленным значением. Это в основном так, и да, реализовано так, с указателями с подсчетом ссылок, это довольно дорого.
Мемоизация — это старый термин, который часто означает табулирование результата функции. Ни один современный язык не делает это (возможно, PROLOG), это чрезвычайно дорого.
Полная ленивость (никогда не вычисляющая одну вещь дважды) достигается в процессе лямбда-лифтинга, который является устранением свободных переменных (путем помещения их в качестве аргументов). При полностью ленивом подъеме лямбды это максимальные свободные выражения, которые снимаются (скажем, x является свободным, поэтому вхождение sqrt x заменяется новым аргументом, sqrtx).
Существует также так называемое оптимальное сокращение.
Я не думаю, что есть другие способы сделать это. Почему это намного быстрее в ленивом функциональном языке, таком как Haskell? Ну, в общем, ссылки не подсчитываются, то есть анализ строгости (строгий — это противоположность ленивому), который позволяет компилятору заранее знать, что некоторые вещи лучше оценивать строго, распаковывая значения, которые оцениваются строго и относятся к известному типу машины. … не говоря уже о других типичных оптимизациях функционального языка программирования …
Но по сути, если вы посмотрите на реализацию машины сокращения графов, если вы посмотрите на то, как эволюционирует стек, вы увидите, что в основном вы передаете функции в стеке вместо аргументов, и это в основном так.
Теперь в этих машинах узел, который вычисляет аргумент, перезаписывается его значением. Так что, может быть, вам не хватает оптимизации, но такой, которая была бы невозможна в контексте безопасного типа.
Предположим, что все ваши «узлы» являются подклассами главного суперкласса, называемого «узлом», в котором есть только виртуальная функция, которая вычисляет значение … тогда она может быть «перезаписана» другой, которая будет возвращать уже вычисленное значение. Именно благодаря указателям на функции они говорят, что STG-машина Haskell является «безметочной» (G-машиной без привязки), потому что они не помечают элементы данных, вместо этого они используют указатель на функцию, который либо вычисляет, либо возвращает Значение.
Я не думаю, что это может быть сделано не так эффективно в C ++, как в Haskell … если только мы не начнем думать о реализации C ++ совершенно по-другому (можно и нужно делать).
Мы привыкли к таким сложным прологам и эпилогам, сложным соглашениям о вызовах и т. Д. Вызов функции слишком бюрократичен в C / C ++.
Теперь книга, которую вы читаете, когда вам лень, — это, безусловно, «Реализация языков функционального программирования» Саймона Пейтона-Джонса.
Тем не менее, современная реализация описана в свободно доступной статье «Реализация функциональных языков на стандартном оборудовании: G-машина без тегов Spineless», в которой очень приятно прочитать об оптимизации реализации, но другая — это та, которую нужно прочитать, чтобы понять основы.
Вот еще один аспект лени, который был необходим для меня.
// 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;
Библиотека Boost Phoenix реализует Lazyness, среди прочих тонкостей FP, но я не использовал себя, я не уверен, насколько хорошо она работает с C ++ 11, или, возможно, она сделала его хотя бы частично стандартом 2011 года.
http://www.boost.org/doc/libs/1_43_0/libs/spirit/phoenix/doc/html/index.html
В моей реализации класса Lazy я пошел другим путем — лямбда-функция не возвращает значение, она принимает его в качестве параметра. Это помогает достичь некоторых преимуществ:
- Экономия времени на вызов конструктора перемещения для инкапсулированного типа (когда функция инициализации возвращает результат).
- Конструктор копирования и оператор присваивания для инкапсулированного типа не требуются (только если вы хотите сделать это для типа 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;