c++ - 一种在 C++ 中实现惰性求值的方法

Question

所以我回答了一个关于惰性求值的问题(here，我的回答对于这种情况来说有点矫枉过正，但这个想法似乎很有趣)，这让我想到了如何在 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 的使用有什么问题吗？我在 LAZY 宏中的 E 周围添加了额外的括号，以确保单个名称得到公平对待，就像 vec[10] 一样的引用。还有其他我没有考虑的事情吗？
• 在我的示例中有很多间接层。这似乎是可以避免的。
• 这是否正确地记住了结果，以便无论有什么或有多少东西引用了惰性值，它只会评估一次(我对此非常有信心，但惰性评估加上大量共享指针可能会给我带来循环)

你有什么想法？

Answer 1

是的，你所拥有的是懒惰的。基本上，只需传递一个计算参数而不是参数的函数。评估后，对象被计算值替换。基本上就是这样，是的，用引用计数的指针实现这样的，它是相当昂贵的。

内存是一个古老的术语，它通常意味着将函数的结果表化。没有现代语言可以做到这一点(也许是 PROLOG)，它非常昂贵。完全惰性(从不计算一件事两次)在 lambda 提升的过程中实现，即消除自由变量(通过将它们作为参数)。在完全惰性的 lambda 提升中，提升的是最大的自由表达式(假设 x 是自由的，因此 sqrt x 的出现被新参数 sqrtx 替换)。还有所谓的最优归约。

我认为没有其他方法可以做到这一点。为什么在 Haskell 等惰性函数式语言中速度要快得多？好吧，基本上，没有引用计数的指针，然后是严格分析(严格与惰性相反)，它允许编译器事先知道有些东西最好严格评估，将严格评估且机器类型已知的值拆箱...更不用说其他典型的函数式编程语言优化...但本质上，如果你看一下图形缩减机器的实现，如果你看一下堆栈是如何演变的，你会发现基本上你是在堆栈上传递函数而不是参数，基本上就是这样。

现在，在这些机器中，计算参数的节点被其值覆盖。所以你可能错过了一个优化，但在类型安全的上下文中是不可能的。

假设您的所有“节点”都是主父类(super class)的子类，称为“节点”，它只有一个计算值的虚函数......然后它可能被另一个返回已经计算的值的“覆盖”。那件事，带有函数指针，就是为什么他们说 Haskell 的 STG 机器是“无标签的”(Spineless Tagless G-Machine)，因为它们不标记数据元素，而是使用计算或返回的函数指针值(value)。

我不认为它在 C++ 中的效率不如在 Haskell 中那么高效......除非我们开始考虑以完全不同的方式实现 C++(可以而且应该这样做)。我们已经习惯了如此复杂的序言和结语以及复杂的调用约定等......函数调用在C/C++中过于官僚。

现在，当您感到懒惰时，可以阅读的书绝对是 Simon Peyton-Jones 的《函数式编程语言的实现》。但是，现代实现在免费提供的文章“在库存硬件上实现功能语言:无脊椎无标签 G 机器”中进行了描述，该文章非常适合阅读有关实现优化的内容，但另一篇是阅读以了解基础知识。