C++ 没有对惰性求值的本机支持（就像 Haskell 一样）。
我想知道是否有可能以合理的方式在 C++ 中实现惰性求值。如果是，你会怎么做？
编辑：我喜欢康拉德鲁道夫的回答。
我想知道是否有可能以更通用的方式实现它，例如通过使用参数化类lazy，它基本上适用于T，就像matrix_add 适用于矩阵一样。
对 T 的任何操作都会返回惰性。唯一的问题是将参数和操作代码存储在惰性本身中。谁能看到如何改善这一点？
问问题
48442 次
12 回答
107
我想知道是否有可能以合理的方式在 C++ 中实现惰性求值。如果是，你会怎么做？
是的，这是可能的并且经常这样做，例如用于矩阵计算。促进这一点的主要机制是运算符重载。考虑矩阵加法的情况。函数的签名通常如下所示：
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()隐式转换运算符 frommatrix_add到 plain的方法matrix。这样，您可以链接多个操作（当然通过提供适当的重载）。仅当将最终结果分配给matrix实例时才会进行评估。
编辑我应该更明确。实际上，代码没有意义，因为尽管评估是延迟发生的，但它仍然发生在同一个表达式中。特别是，除非matrix_add更改结构以允许链式添加，否则另一个添加将评估此代码。C++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。我为我的字符串类型重载了这个函数，以返回一个包含对我的字符串的引用的代理，以及所需的开始和结束位置。只有当这个子字符串被实际使用时，它才会查询 C API 来检索字符串的这一部分。
于 2009-01-05T19:47:42.227 回答
37
Boost.Lambda 非常好，但Boost.Proto正是您正在寻找的。它已经拥有所有C++ 运算符的重载，默认情况下，它们在proto::eval()被调用时执行它们的常用功能，但可以更改。
于 2009-01-08T06:55:16.483 回答
32
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; }
};
这将存储任何加法运算，甚至是嵌套的，如以下简单点类型的 operator+ 定义所示：
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 类型的临时对象。它可能是一个包含许多领域的大矩阵。但是在需要结果的时候，我们就懒惰地计算了。
于 2009-01-05T20:37:06.183 回答
12
我对 Konrad 的帖子没有什么要补充的，但是您可以查看Eigen ，了解在现实世界的应用程序中正确完成惰性评估的示例。这是相当令人敬畏的。
于 2009-01-05T21:14:23.583 回答
4
我正在考虑实现一个模板类，它使用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代替，但我不确定它是否会影响性能。
于 2013-07-18T10:19:50.777 回答
4
约翰内斯的回答有效。但是当涉及到更多括号时，它并不如愿。这是一个例子。
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！
于 2014-12-08T07:56:22.143 回答
2
正如它将在C++0x中通过 lambda 表达式完成的那样。
于 2009-01-05T19:42:40.507 回答
2
一切皆有可能。
这取决于你的意思：
class X
{
public: static X& getObjectA()
{
static X instanceA;
return instanceA;
}
};
在这里，我们有一个全局变量的影响，该变量在首次使用时被延迟评估。
正如问题中新要求的那样。
并窃取 Konrad Rudolph 的设计并对其进行扩展。
懒惰的对象：
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);
}
}
于 2009-01-05T19:43:47.557 回答
2
在 C++11 中，类似于 hiapay 的答案的惰性评估可以使用 std::shared_future 来实现。您仍然必须将计算封装在 lambda 中，但要注意记忆：
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;
}
于 2016-12-01T20:33:44.993 回答
1
C++0x 很不错……但是对于我们这些活在当下的人来说，你有 Boost lambda 库和 Boost Phoenix。两者都是为了将大量函数式编程引入 C++。
于 2009-01-05T20:36:16.810 回答
1
让我们以 Haskell 为灵感——它从本质上来说是懒惰的。另外，让我们记住 C# 中的 Linq 如何以单子（呃 - 这里是单词 - 抱歉）的方式使用枚举器。最后同样重要的是，让我们记住，协程应该为程序员提供什么。即计算步骤（例如生产者消费者）彼此解耦。让我们试着想想协程如何与惰性求值相关联。
以上所有似乎都在某种程度上相关。
接下来，让我们尝试提取我们对“懒惰”归结为什么的个人定义。
一种解释是：我们希望在执行之前以可组合的方式声明我们的计算。我们用来组成完整解决方案的部分部分可能很好地利用了巨大的（有时是无限的）数据源，而我们的完整计算也可以产生有限或无限的结果。
让我们具体一些代码。我们需要一个例子！在这里，我选择 fizzbuzz“问题”作为示例，只是因为它有一些不错的、懒惰的解决方案。
在 Haskell 中，它看起来像这样：
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单个两个元素配方“将来自任一输入列表的字符串元素连接成单个字符串”。同样，如果要立即对此进行评估，我们将不得不等待我们的计算机耗尽资源。
[1..n]在第 4 行，我们使用无限惰性列表创建有限惰性列表成员的元组fizzbuzz。结果还是懒惰。
即使在我们函数的主体中fb，也不需要急于求成。整个函数返回一个包含解决方案的列表，它本身又是惰性的。您也可以将 的结果fb 50视为您可以（部分）稍后评估的计算。或者与其他东西结合，导致更大的（懒惰的）评估。
因此，为了开始使用我们的 C++ 版本的“fizzbuzz”，我们需要考虑如何将计算的部分步骤组合成更大的计算位，每个计算都根据需要从前面的步骤中提取数据。
您可以在我的要点中看到完整的故事。
这里是代码背后的基本思想：
借用 C# 和 Linq，我们“发明”了一个有状态的泛型类型Enumerator，它持有
- 部分计算的当前值 - 部分计算
的状态（因此我们可以产生后续值）
- 工作函数，它产生下一个状态，下一个值和一个布尔值，它说明是否有更多数据或枚举是否已经结束。
为了能够Enumerator<T,S>通过（点）的力量组成实例.，这个类还包含从 Haskell 类型类中借用的函数，例如Functor和Applicative。
枚举器的工作函数始终采用以下形式：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{}
{
}
// ...
};
所以，我们只需要创建一个特定的枚举器实例，我们需要创建一个工作函数，拥有初始状态并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());
}
它接受一个枚举器作为输入并返回一个枚举器。本地（lambda）函数eternally只要输入枚举值用完就会简单地将输入枚举重置为其起始值，瞧——我们有一个无限的、不断重复的列表版本作为参数::auto foo = cycle(range(size_t{1},3));我们已经可以无耻地组成我们的懒惰“计算”。
zip是一个很好的例子，表明我们也可以从两个输入枚举器中创建一个新的枚举器。生成的枚举器产生的值与输入枚举器中的较小者一样多（具有 2 个元素的元组，每个输入枚举器一个）。我已经zip在内部实现class Enumerator了。这是它的样子：
// 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(..)代码会将迭代器存储到早已不复存在的向量中。
于 2018-09-21T16:46:34.217 回答
0
使用惰性评估的一个非常简单的定义，即在需要时才评估值，我想说可以通过使用指针和宏（用于语法糖）来实现这一点。
#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，它只是取消引用指针以在实际需要之前获取值。惰性类型是原子访问的，因此它是完全线程安全的。
于 2018-11-21T16:32:51.153 回答