C++ 实现惰性求值
作者：SkyFire
- 2023-01-30 陕西
本文字数：12808 字
阅读完需：约 42 分钟
定义
惰性求值是一种计算机编程技巧，其特点是把表达式的求值推迟到实际需要其值的时候再进行。这种方法的主要优势在于可以避免不必要的计算，提高程序性能，特别是在求值耗时或耗资源的情况下。
惰性求值有如下优点：
提高性能：惰性求值允许程序避免不必要的计算，通过延迟表达式的求值直到它的值实际需要时提高性能。
减少内存使用：通过延迟表达式的求值，惰性求值可以减少内存使用，因为计算的中间结果不存储在内存中。
提高代码的清晰度和可读性：惰性求值可以通过允许开发人员将计算结果与其使用分离来提高代码的清晰度和可读性。
更好的错误处理：使用惰性求值，可以在程序执行后期检测和处理错误，这比立即检测和处理错误更方便和高效。
更好的函数式编程支持：惰性求值是函数式编程的关键技术，允许创建高阶函数和更简洁，优雅的代码。
解题思路
要实现惰性求值，主要要解决的问题是记录“求值过程”，换句话说，就是要保存函数调用的函数和参数信息，以及表达式中的运算符信息。
对于函数调用的函数和参数保存，可以使用 tuple 和 function 对象完成，后续的计算过程可以使用 apply 函数。
对于表达式语句来说，运算符本身也可以看做是函数调用，可以通过封装一层 lambda 函数使其与普通函数对外表现一致。
实现
基础版本
首先实现一个简单的版本，如下：
#include <tuple>#include <iostream>
template <typename Func, typename... Args>class lazy_t{private: Func func; std::tuple<Args...> args; using result_type = std::invoke_result_t<Func, Args...>;
public: lazy_t(Func f, Args... a) : func(f) , args { a... } { }
operator result_type() { return std::apply(func, args); }};
template <typename Func, typename... Args>lazy_t(Func, Args...) -> lazy_t<Func, Args...>;
int add(int a, int b){ std::cout<<"start calc"<<std::endl; return a + b;}
int main(){ auto t = lazy_t(add, 5, 6); std::cout<<"before output"<<std::endl; std::cout << t << std::endl;}
复制代码
这段代码定义了一个名为lazy_t的模板类，该类接受一个函数对象和多个参数作为构造函数的参数，并存储它们作为类的成员变量。
这个lazy_t类重载了类型转换操作符，因此它可以被隐式转换为函数对象在给定参数下的返回类型。通过定义模板类型推导规则，我们可以直接创建lazy_t对象，而不必手动指定类型。
最后，在 main 函数中创建了一个名为t的lazy_t对象，该对象在构造函数中调用了函数add，并传递了两个参数：5 和 6。在输出该对象之前，不会计算该对象。实际计算发生在第一次使用该对象时。
该代码的输出如下：
before output
start calc
11
封装函数
使用 lazy 调用一个函数不那么直观。包装一下，使其成为更直观的函数调用可能更好。
#include <functional>#include <iostream>#include <tuple>
template <typename Func, typename... Args>class lazy_t{private: Func func; std::tuple<Args...> args; using result_type = std::invoke_result_t<Func, Args...>;
public: lazy_t(Func f, Args... a) : func(f) , args { a... } { }
operator result_type() { return std::apply(func, args); }};
template <typename Func, typename... Args>lazy_t(Func, Args...) -> lazy_t<Func, Args...>;
template <typename Result, typename... Args>class lazy_wrapper_t{private: using FuncType = std::function<Result(Args...)>; FuncType func;
public: lazy_wrapper_t(std::function<Result(Args...)> f) : func(f) { }
template <typename... LazyArgs> auto operator()(LazyArgs... args) { return lazy_t(func, args...); }};
template <typename Result, typename... Args>lazy_wrapper_t(std::function<Result(Args...)>) -> lazy_wrapper_t<Result, Args...>;
// 对外接口
template <typename Func>auto lazy_wrapper(Func f){ return lazy_wrapper_t(std::function(f));}
// 以下为测试代码
int add(int a, int b){ std::cout << "start add" << std::endl; return a + b;}
int sub(int a, int b){ std::cout << "start sub" << std::endl; return a - b;}
int main(){ auto lazy_add = lazy_wrapper(add); auto lazy_sub = lazy_wrapper(sub); auto v = lazy_add(lazy_sub(9, 4), 10); std::cout << "before output" << std::endl; std::cout << v << std::endl;}
复制代码
这段实现相比第一版主要有以下改动：
增加了
lazy_wrapper_t类，此类对普通函数进行包装，使其返回一个可调用对象，调用此对象的时候，不会发生真实的计算，而是创建出一个lazy_t对象，在需要的时候再进行计算。定义
lazy_wrapper_t的模板推导规则。创建了一个模板函数
lazy_wrapper,此函数将入参转换为std::function实例化对象，辅助构造lazy_wrapper_t对象。
此代码的输出如下：
before output
start sub
start add
15
可以看到，add和sub的调用都在输出的时候才进行。
需要注意的一点是，在重载括号运算符的时候，没有使用Args...作为参数，而是使用了新的模板形参LazyArgs...，为什么不能用Args...呢？因为Args...是包装函数实际使用的参数类型，而我们传入的参数可能是lazy_t类型的，也可能不是，所以必需使用新的模板参数。而到真正调用的时候，非lazy_t类型的实参会直接传入被包装函数，而lazy_t类型的参数需要经过隐式转换，在隐式转换的过程中会触发自动求值，从而完成计算。
运算符支持
除了函数，很多计算过程都需要运算符，接下来开始对运算符进行支持。
#include <functional>#include <iostream>#include <tuple>#include <type_traits>#include <utility>#include <cassert>
template <typename Func, typename... Args>class lazy_t;
// type_of_lazy 用于判断类型是否是lazy_t模板实例化出来的template <typename T>struct type_of_lazy : std::false_type{};
template <typename... Ts>struct type_of_lazy<lazy_t<Ts...>> : std::true_type{};
template <typename Func, typename... Args>class lazy_t{private: Func func; std::tuple<Args...> args;
public: using result_type = std::invoke_result_t<Func, Args...>; using self_type = lazy_t<Func, Args...>; lazy_t(Func f, Args... a) : func(f) , args { a... } { }
// 手动计算 result_type call() const { return std::apply(func, args); }
// 进行类型转换的时候自动开始计算 operator result_type() const { return call(); }
// 数组下标运算符重载，只能在类内部 // 数组下标分为两种，一种是非lazy_t对象，另一种是lazy_t对象，对于lazy_t类型的对象，要先完成计算 template <typename Right> auto operator[](Right r) const { if constexpr (!type_of_lazy<Right>::value) { auto f = [](self_type a, Right b) { return a.call()[b]; }; return lazy_t<decltype(f), self_type, Right> { f, *this, r }; } else { auto f = [](self_type a, Right b) { return a.call()[b.call()]; }; return lazy_t<decltype(f), self_type, Right>(f, *this, r); } }
// 括号运算符 template <typename... InvokeArgs> auto operator()(InvokeArgs... a) const { auto f = [](self_type f, auto... a) { f.call()(a...); }; return lazy_t<decltype(f), self_type, InvokeArgs...>(f, *this, a...); }
// 指针运算符 auto operator->() const { auto f = [](self_type a) { return result_type::operator->(a.call()); }; return lazy_t<decltype(f), self_type>(f, *this); }};
template <typename Func, typename... Args>lazy_t(Func, Args...) -> lazy_t<Func, Args...>;
// lazy函数包装template <typename Result, typename... Args>class lazy_wrapper_t{private: std::function<Result(Args...)> func;
public: lazy_wrapper_t(std::function<Result(Args...)> f) : func(f) { }
// 函数调用，实际不发生调用，而是生成一个lazy_t对象 template <typename... LazyArgs> auto operator()(LazyArgs... args) { return lazy_t(func, args...); }};
template <typename Result, typename... Args>lazy_wrapper_t(std::function<Result(Args...)>) -> lazy_wrapper_t<Result, Args...>;
// 生成lazy_t对各种双目运算符的重载// 使用泛型实现，需要保证至少有一个是lazy_t类型的 ，此处使用requires做限制// 另外通过conexpr if在编译期针对不同的情况生成代码，决定是否需要计算#define MAKE_OP2(op) \ template <typename Left, typename Right> \ requires(type_of_lazy<Left>::value || type_of_lazy<Right>::value) auto operator op(Left l, Right r) \ { \ if constexpr (!type_of_lazy<Right>::value) \ { \ return lazy_t([](Left a, Right b) { return a.call() op b; }, l, r); \ } \ else if constexpr (!type_of_lazy<Left>::value) \ { \ return lazy_t([](Left a, Right b) { return a op b.call(); }, l, r); \ } \ else \ { \ return lazy_t([](Left a, Right b) { return a.call() op b.call(); }, l, r); \ } \ }
MAKE_OP2(+);MAKE_OP2(-);MAKE_OP2(*);MAKE_OP2(/);MAKE_OP2(%);MAKE_OP2(^);MAKE_OP2(&);MAKE_OP2(&&);MAKE_OP2(|);MAKE_OP2(||);MAKE_OP2(<);MAKE_OP2(<=);MAKE_OP2(>);MAKE_OP2(>=);MAKE_OP2(==);MAKE_OP2(!=);MAKE_OP2(>>);MAKE_OP2(<<);MAKE_OP2(<<=);MAKE_OP2(>>=);MAKE_OP2(+=);MAKE_OP2(-=);MAKE_OP2(*=);MAKE_OP2(/=);MAKE_OP2(%=);MAKE_OP2(&=);MAKE_OP2(|=);MAKE_OP2(^=);
// 逗号运算符无法通过宏生成，手动生成template <typename Left, typename Right>requires(type_of_lazy<Left>::value || type_of_lazy<Right>::value) auto operator,(Left l, Right r){ if constexpr (!type_of_lazy<Right>::value) { return lazy_t([](typename Left::result_type a, auto b) { return a, b; }, l, r); } else if constexpr (!type_of_lazy<Left>::value) { return lazy_t([](auto a, typename Right::result_type b) { return a, b; }, l, r); } else { return lazy_t([](typename Left::result_type a, typename Right::result_type b) { return a, b; }, l, r); }}
#undef MAKE_OP2
// 单目前缀运算符#define MAKE_OP1_PREFIX(op) \ template <typename LazyValue> \ requires(type_of_lazy<LazyValue>::value) auto operator op(LazyValue v) \ { \ return lazy_t([](LazyValue t) { \ return op t.call(); \ }, \ v); \ }
MAKE_OP1_PREFIX(+);MAKE_OP1_PREFIX(-);MAKE_OP1_PREFIX(++);MAKE_OP1_PREFIX(--);MAKE_OP1_PREFIX(!);MAKE_OP1_PREFIX(~);MAKE_OP1_PREFIX(*);
#undef MAKE_OP1_SUFFIX
#define MAKE_OP1_SUFFIX(op) \ template <typename LazyValue> \ requires(type_of_lazy<LazyValue>::value) auto operator op(LazyValue v, int) \ { \ return lazy_t([](LazyValue t) { \ return t.call() op; \ }, \ v); \ }
MAKE_OP1_SUFFIX(++);MAKE_OP1_SUFFIX(--);
#undef MAKE_OP1_SUFFIX
// 对外接口
// 封装函数template <typename Func>auto lazy_wrapper(Func f){ return lazy_wrapper_t(std::function(f));}
// 封装值template <typename V>auto lazy_value(V v){ return lazy_t([v]() { return v; });}
// 以下为测试代码
#define TRACE std::cout << __LINE__ << ":call " << __FUNCTION__ << std::endl;
int add(int a, int b){ TRACE; return a + b;}
struct FuncObj{ int operator()(int a, int b) { TRACE; return a + b; }};
struct Int{ int data;
Int(int d) : data(d) { }
Int operator+(Int a) { TRACE; return Int { data + a.data }; } Int operator-(Int a) { TRACE; return Int { data - a.data }; } Int operator*(Int a) { TRACE; return Int { data * a.data }; } Int operator/(Int a) { TRACE; return Int { data / a.data }; }
int operator[](int index) { TRACE; return index * data; }};
void change(int& a){ TRACE; a++;}
int main(){ auto f1 = lazy_wrapper(add); // 普通函数 auto r1 = f1(10, 20);
auto f2 = lazy_wrapper([](int a, int b) { // lambda TRACE; return a + b; }); auto r2 = f2(10, 20);
auto f3 = lazy_wrapper(FuncObj {}); // 可调用对象 auto r3 = f3(10, 20);
auto r4 = Int { 5 } + lazy_value(Int { 10 }) * Int { 20 } / Int { 2 } - Int { 6 }; // 自定义重载运算符
auto r5 = 5; auto f6 = lazy_wrapper(change); // 引用 auto r6 = f6(std::ref(r5));
auto r7 = r4[100]; // 下标访问
std::cout << "start calc" << std::endl; assert((int)r1 == 30); assert((int)r2 == 30); assert((int)r3 == 30); assert(((Int)r4).data == 99); r6.call(); assert(r5 == 6); assert(r7 == 9900);}
复制代码
本次的代码与上次的代码相比修改很大，主要体现在以下方面：
增加了一个简单的
type_traits，实现了lazy_t对象的判断，为后面的运算符重载提供支撑；lazy_t中增加了call成员函数，用于发起手动计算。当惰性求值的函数返回值是void类型时，无法通过类型转换自动求值，可以手动调用此函数发起求值；为
lazy_t增加了双目运算符重载，其中[]、()、→只能是类成员函数。逗号运算符手动重载，其他的双目运算符（不包含宙飞船运算符）通过宏生成；为
lazy_t增加了单目运算符重载，包括前缀和后缀；增加了
lazy_value函数，将值对象封装为一个lazy_t对象；完善了注释
上面的程序输出：
start calc
272:call add
334:call operator()
280:call operator()
306:call operator*
311:call operator/
296:call operator+
301:call operator-
324:call change
317:call operator[]
可以看出，各种操作都是在最后需要的时候进行计算的。
从输出我们可以看到一些问题，对于r4的使用，求值进行了两次，这是因为r4在隐式类型转换的时候，并不知道是否已经求值，所以只能重新求值。而且，计算过程中的函数与参数信息都保存在lazy_t对象中，一旦发生对象拷贝，这些信息也都会复制一份，事实上，这些数据都是不变的，可以多个对象共享一份数据。
因此，我们做一下最后的优化。
最后的优化
优化后的代码如下：
#include <functional>#include <iostream>#include <tuple>#include <type_traits>#include <utility>#include <cassert>#include <memory>
template <typename Func, typename... Args>class lazy_t;
// type_of_lazy 用于判断类型是否是lazy_t模板实例化出来的template <typename T>struct type_of_lazy : std::false_type{};
template <typename... Ts>struct type_of_lazy<lazy_t<Ts...>> : std::true_type{};
template <typename Func, typename... Args>class lazy_t{private: using result_type = std::invoke_result_t<Func, Args...>; static constexpr bool is_result_void = std::is_same_v<result_type, void>; using inner_result_type = std::conditional_t<is_result_void, int, result_type>; using self_type = lazy_t<Func, Args...>;
// 声明为shared_ptr，多个副本之间共享 std::shared_ptr<Func> func; std::shared_ptr<std::tuple<Args...>> args; std::shared_ptr<std::shared_ptr<inner_result_type>> result;
public: lazy_t(Func f, Args... a) : func(std::make_shared<Func>(f)) , args(std::make_shared<std::tuple<Args...>>(a...)) , result(std::make_shared<std::shared_ptr<inner_result_type>>()) { }
// 强制调用，忽略已计算的结果 result_type call_force() const { if constexpr (is_result_void) { *result = std::make_shared<inner_result_type>(); std::apply(*func, *args); } else { *result = std::make_shared<inner_result_type>(std::apply(*func, *args)); } if constexpr (!is_result_void) { return **result; } }
// 手动计算 result_type call() const { if (*result == nullptr) { call_force(); } if constexpr (!is_result_void) { return **result; } }
// 进行类型转换的时候自动开始计算 operator result_type() const { return call(); }
// 数组下标运算符重载，只能在类内部 // 数组下标分为两种，一种是非lazy_t对象，另一种是lazy_t对象，对于lazy_t类型的对象，要先完成计算 template <typename Right> auto operator[](Right r) const { if constexpr (!type_of_lazy<Right>::value) { auto f = [](self_type a, Right b) { return a.call()[b]; }; return lazy_t<decltype(f), self_type, Right> { f, *this, r }; } else { auto f = [](self_type a, Right b) { return a.call()[b.call()]; }; return lazy_t<decltype(f), self_type, Right>(f, *this, r); } }
// 括号运算符 template <typename... InvokeArgs> auto operator()(InvokeArgs... a) const { auto f = [](self_type f, auto... a) { f.call()(a...); }; return lazy_t<decltype(f), self_type, InvokeArgs...>(f, *this, a...); }
// 指针运算符 auto operator->() const { auto f = [](self_type a) { return result_type::operator->(a.call()); }; return lazy_t<decltype(f), self_type>(f, *this); }};
template <typename Func, typename... Args>lazy_t(Func, Args...) -> lazy_t<Func, Args...>;
// lazy函数包装template <typename Result, typename... Args>class lazy_wrapper_t{private: std::function<Result(Args...)> func;
public: lazy_wrapper_t(std::function<Result(Args...)> f) : func(f) { }
// 函数调用，实际不发生调用，而是生成一个lazy_t对象 template <typename... LazyArgs> auto operator()(LazyArgs... args) { return lazy_t(func, args...); }};
template <typename Result, typename... Args>lazy_wrapper_t(std::function<Result(Args...)>) -> lazy_wrapper_t<Result, Args...>;
// 生成lazy_t对各种双目运算符的重载// 使用泛型实现，需要保证至少有一个是lazy_t类型的 ，此处使用requires做限制// 另外通过conexpr if在编译期针对不同的情况生成代码，决定是否需要计算#define MAKE_OP2(op) \ template <typename Left, typename Right> \ requires(type_of_lazy<Left>::value || type_of_lazy<Right>::value) auto operator op(Left l, Right r) \ { \ if constexpr (!type_of_lazy<Right>::value) \ { \ return lazy_t([](Left a, Right b) { return a.call() op b; }, l, r); \ } \ else if constexpr (!type_of_lazy<Left>::value) \ { \ return lazy_t([](Left a, Right b) { return a op b.call(); }, l, r); \ } \ else \ { \ return lazy_t([](Left a, Right b) { return a.call() op b.call(); }, l, r); \ } \ }
MAKE_OP2(+);MAKE_OP2(-);MAKE_OP2(*);MAKE_OP2(/);MAKE_OP2(%);MAKE_OP2(^);MAKE_OP2(&);MAKE_OP2(&&);MAKE_OP2(|);MAKE_OP2(||);MAKE_OP2(<);MAKE_OP2(<=);MAKE_OP2(>);MAKE_OP2(>=);MAKE_OP2(==);MAKE_OP2(!=);MAKE_OP2(>>);MAKE_OP2(<<);MAKE_OP2(<<=);MAKE_OP2(>>=);MAKE_OP2(+=);MAKE_OP2(-=);MAKE_OP2(*=);MAKE_OP2(/=);MAKE_OP2(%=);MAKE_OP2(&=);MAKE_OP2(|=);MAKE_OP2(^=);
// 逗号运算符无法通过宏生成，手动生成template <typename Left, typename Right>requires(type_of_lazy<Left>::value || type_of_lazy<Right>::value) auto operator,(Left l, Right r){ if constexpr (!type_of_lazy<Right>::value) { return lazy_t([](typename Left::result_type a, auto b) { return a, b; }, l, r); } else if constexpr (!type_of_lazy<Left>::value) { return lazy_t([](auto a, typename Right::result_type b) { return a, b; }, l, r); } else { return lazy_t([](typename Left::result_type a, typename Right::result_type b) { return a, b; }, l, r); }}
#undef MAKE_OP2
// 单目前缀运算符#define MAKE_OP1_PREFIX(op) \ template <typename LazyValue> \ requires(type_of_lazy<LazyValue>::value) auto operator op(LazyValue v) \ { \ return lazy_t([](LazyValue t) { \ return op t.call(); \ }, \ v); \ }
MAKE_OP1_PREFIX(+);MAKE_OP1_PREFIX(-);MAKE_OP1_PREFIX(++);MAKE_OP1_PREFIX(--);MAKE_OP1_PREFIX(!);MAKE_OP1_PREFIX(~);MAKE_OP1_PREFIX(*);
#undef MAKE_OP1_SUFFIX
#define MAKE_OP1_SUFFIX(op) \ template <typename LazyValue> \ requires(type_of_lazy<LazyValue>::value) auto operator op(LazyValue v, int) \ { \ return lazy_t([](LazyValue t) { \ return t.call() op; \ }, \ v); \ }
MAKE_OP1_SUFFIX(++);MAKE_OP1_SUFFIX(--);
#undef MAKE_OP1_SUFFIX
// 对外接口
// 封装函数template <typename Func>auto lazy_wrapper(Func f){ return lazy_wrapper_t(std::function(f));}
// 封装值template <typename V>auto lazy_value(V v){ return lazy_t([v]() { return v; });}
// 以下为测试代码
#define TRACE std::cout << __LINE__ << ":call " << __FUNCTION__ << std::endl;
int add(int a, int b){ TRACE; return a + b;}
struct FuncObj{ int operator()(int a, int b) { TRACE; return a + b; }};
struct Int{ int data;
Int(int d) : data(d) { }
Int operator+(Int a) { TRACE; return Int { data + a.data }; } Int operator-(Int a) { TRACE; return Int { data - a.data }; } Int operator*(Int a) { TRACE; return Int { data * a.data }; } Int operator/(Int a) { TRACE; return Int { data / a.data }; }
int operator[](int index) { TRACE; return index * data; }};
void change(int& a){ TRACE; a++;}
int main(){ auto f1 = lazy_wrapper(add); // 普通函数 auto r1 = f1(10, 20);
auto f2 = lazy_wrapper([](int a, int b) { // lambda TRACE; return a + b; }); auto r2 = f2(10, 20);
auto f3 = lazy_wrapper(FuncObj {}); // 可调用对象 auto r3 = f3(10, 20);
auto r4 = Int { 5 } + lazy_value(Int { 10 }) * Int { 20 } / Int { 2 } - Int { 6 }; // 自定义重载运算符
auto r5 = 5; auto f6 = lazy_wrapper(change); // 引用 auto r6 = f6(std::ref(r5));
auto r7 = r4[100]; // 下标访问
std::cout << "start calc" << std::endl; assert((int)r1 == 30); assert((int)r2 == 30); assert((int)r3 == 30); assert(((Int)r4).data == 99); r6.call(); assert(r5 == 6); assert(r7 == 9900);}
复制代码
在这个版本中，做出了以下修改：
在
lazy_t中增加了保存结果的成员result，针对结果为void类型的计算，使用int标识结果。result的类型为二级智能指针，主要是应对没有空参数构造函数以及构造函数有副作用的返回类型的场景；将函数、参数对象使用智能指针存储，对象复制的时候共享一份数据；
增加
call_force成员函数，执行求值运算，并将结果保存到result中；原本的
call成员函数检测结果是否已计算（result指向的值是否为空），如果计算了，不再重复计算，直接返回结果；
上面的程序输出：
start calc
270:call add
332:call operator()
278:call operator()
304:call operator*
309:call operator/
294:call operator+
299:call operator-
322:call change
315:call operator[]
从结果可以看出，这个版本消除了r4的重复计算。
总结
这里只是对惰性求值进行了一些简单的思路展示，完成了基本的函数包装、表达式包装等功能。主要的思路就是利用元编程对函数、参数进行保存以及对返回值进行包装。
代码还有很多值得改进的地方，比如对引用的支持、对类型的限制等。此处仅是起一个抛砖引玉的效果，期待更好的代码实现。
划线
评论
复制
发布于: 刚刚阅读数: 5
版权声明: 本文为 InfoQ 作者【SkyFire】的原创文章。
原文链接:【http://xie.infoq.cn/article/a0818095804bf5871bbb0ba58】。文章转载请联系作者。
SkyFire
关注
这个cpper很懒，什么都没留下 2018-10-13 加入
会一点点cpp的苦逼码农
评论