C + + 中的惰性求值

C + + 0x 很不错。但对于我们这些生活在当下的人来说，你有 Boost Lambda 图书馆和 Boost Phoenix。两者的目的都是为 C + + 带来大量的函数式编程。

Konrad 已经解释过的内容可以进一步支持运算符的嵌套调用，所有这些调用都是懒惰执行的。在 Konrad 的例子中，他有一个表达式对象，可以存储正好两个参数，一个操作的正好两个操作数。问题在于它只会延迟地执行 一子表达式，这很好地解释了延迟计算中的概念，但是并没有显著地提高性能。另一个示例也很好地演示了如何应用 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 类型的临时类型。它可能是一个包含许多字段的大矩阵。但是在需要结果的时候，我们计算它 懒洋洋的。

我没有什么可以添加到 Konrad 的文章中，但是你可以在 Eigen中找到一个实际应用程序中正确执行懒惰评估的例子。真是令人敬畏。

加油。Lambda 是非常好的，但 提升，原型是 没错什么你正在寻找。它已经重载了 所有 C + + 运算符，默认情况下，它们在调用 proto::eval()时执行通常的函数，但是可以进行更改。

我正在考虑实现一个使用 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)转换为 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！

在 C + + 11中，可以使用 std: : share _ future 实现类似于 hiapay 的惰性计算。您仍然需要将计算封装在 lambdas 中，但是要注意制表:

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 作为我们的灵感——它从根本上就是懒惰的。 另外，让我们记住 C # 中的 Linq 是如何以一元方式使用枚举器的(urh-here is the word-sorry)。 最后，让我们记住，协程应该为程序员提供什么。即计算步骤(例如生产者消费者)之间的解耦。 让我们试着思考协程与惰性评估之间的关系。

所有这些似乎都有某种联系。

接下来，让我们尝试提取我们对“懒惰”的个人定义。

一种解释是: 我们希望以一种可组合的方式声明我们的计算，之前执行它。我们用来构成完整解决方案的一些部分很可能利用巨大的(有时是无限的)数据源，我们的完整计算也会产生有限或无限的结果。

让我们进入一些具体的代码。我们需要一个例子！在这里，我选择 fizzbuzz“问题”作为一个例子，只是因为有一些很好的，懒惰的解决方案。

在哈斯克尔，情况是这样的:

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

Haskell 函数 cycle创建一个无限列表(当然是惰性的!)从一个有限的列表，通过简单地重复有限的列表中的值永远。在急切的编程风格中，编写这样的代码会敲响警钟(内存溢出，无休止的循环!).但在一种懒惰的语言中，情况并非如此。诀窍在于，惰性列表不会马上被计算出来。也许永远不会。通常只有在后续代码需要它的时候才需要。

上面的 where块中的第三行创建了另一个惰性! ！列表，通过组合无限列表 fizz和 buzz的方法，通过单两个元素的配方“连接一个字符串元素从任何一个输入列表到一个单一的字符串”。同样，如果要立即进行计算，我们必须等待计算机耗尽资源。

在第4行中，我们使用无限延迟列表 fizzbuzz创建有限延迟列表 [1..n]成员的元组。结果仍然是懒惰。

即使在我们的 fb函数的主体中，也没有必要急于求成。整个函数返回一个包含解决方案的列表，该解决方案本身也是惰性的。您也可以将 fb 50的结果视为一种计算，以后可以(部分地)对其进行计算。或者与其他东西结合，导致一个更大的(懒惰的)评估。

因此，为了开始使用 C + + 版本的“ fizzbuzz”，我们需要考虑如何将计算的部分步骤组合成更大的计算比特，每个计算步骤根据需要从前面的步骤中提取数据。

你可以在 我的一个要点中看到完整的故事。

下面是代码背后的基本思想:

借用 C # 和 Linq，我们“发明”了一种有状态的通用类型 Enumerator，它持有
- 部分计算的当前值
- 部分计算的状态(这样我们就可以产生后续的值)
- worker 函数，它产生下一个状态、下一个值和一个 bool，它指出是否有更多数据或者枚举是否已经结束。

为了能够通过 .(点)的能力组成 abc0实例，这个类还包含函数，借用了哈斯克尔类型的类，如 ABc2和 ABc3。

枚举器的辅助函数总是这样的形式: 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{}
{
}
// ...
};

因此，我们只需要创建一个特定的枚举器实例，我们需要创建一个 worker 函数，具有初始状态，并使用这两个参数创建一个 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个元素的惰性列表！

现在，我们所缺少的“哇”的经验，是看看我们如何可以组成枚举数。 回到 Haskellscycle函数，这很酷。在我们的 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());
}

它接受一个枚举数作为输入并返回一个枚举数。Local (lambda)函数 eternally只是将输入枚举重置为它的开始值，只要它的值用完了，就可以了——我们有一个作为参数给出的列表的无限的、不断重复的版本: : auto foo = cycle(range(size_t{1},3));我们已经可以厚颜无耻地组合我们懒惰的“计算”了。

zip是一个很好的例子，它表明我们还可以从两个输入枚举器创建一个新的枚举器。生成的枚举数产生的值与任何一个输入枚举数(元组有2个元素，每个输入枚举数一个)的值一样多。我已经在 class Enumerator内部实现了 zip。它看起来是这样的:

// 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 的范例。顺便说一下，这可能与 pythons itertools 有相似之处。我认为他们采取了类似的做法。

我的实现(参见上面的主要链接)只是一个原型——顺便说一下，不是生产代码。所以我这边没有任何保证。不过，它提供了很好的演示代码，以便理解大体思路。

如果没有最终的 C + + 版本的 fizzbuz，这个问题的答案会是什么呢:

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(..)代码将存储向量的迭代器，而这些向量早已不复存在。

使用一个非常简单的延迟计算定义，即直到需要时才对值进行计算，我认为可以通过使用指针和宏(用于语法 Sugar)来实现这一点。

#include <stdatomic.h>


#define lazy(var_type) lazy_ ## var_type


#define def_lazy_type( var_type ) \
typedef _Atomic var_type _atomic_ ## var_type; \
typedef _atomic_ ## var_type * lazy(var_type);  //pointer to atomic type


#define def_lazy_variable(var_type, var_name ) \
_atomic_ ## var_type _ ## var_name; \
lazy_ ## var_type var_name = & _ ## var_name;


#define assign_lazy( var_name, val ) atomic_store( & _ ## var_name, val )
#define eval_lazy(var_name) atomic_load( &(*var_name) )


#include <stdio.h>


def_lazy_type(int)


void print_power2 ( lazy(int) i )
{
printf( "%d\n", eval_lazy(i) * eval_lazy(i) );
}


typedef struct {
int a;
} simple;


def_lazy_type(simple)


void print_simple ( lazy(simple) s )
{
simple temp = eval_lazy(s);
printf("%d\n", temp.a );
}




#define def_lazy_array1( var_type, nElements, var_name ) \
_atomic_ ## var_type  _ ## var_name [ nElements ]; \
lazy(var_type) var_name = _ ## var_name;


int main ( )
{
//declarations
def_lazy_variable( int, X )
def_lazy_variable( simple, Y)
def_lazy_array1(int,10,Z)
simple new_simple;


//first the lazy int
assign_lazy(X,111);
print_power2(X);


//second the lazy struct
new_simple.a = 555;
assign_lazy(Y,new_simple);
print_simple ( Y );


//third the array of lazy ints
for(int i=0; i < 10; i++)
{
assign_lazy( Z[i], i );
}


for(int i=0; i < 10; i++)
{
int r = eval_lazy( &Z[i] ); //must pass with &
printf("%d\n", r );
}


return 0;
}

你会注意到在函数 print_power2中有一个叫做 eval_lazy的宏，它只是取消引用一个指针来获取实际需要之前的值。延迟类型是自动访问的，因此它是完全线程安全的。