用脚本语言实现 lambda

Question

我从有关匿名函数的维基百科文章中获取了这个修改后的代码示例。

comp(threshold)
{
    return lambda(x)
    {
        return x < threshold;
    };
}

main()
{
    a = comp(10);

    lib::print( a(5) );
}

将匿名函数添加到我的脚本语言中应该不会太难。它应该只是以正常方式添加函数代码的情况，但访问该函数的唯一方法是通过为其分配的变量。

上面的闭包示例的问题在于，匿名函数的函数体引用（一般意义上）在调用闭包时无效（或将无效）的内存位置。

我脑子里已经有两个可能的解决方案；在尝试将此功能添加到我的语言中之前，我只想先获得一些建议。

Answer 1

我不知道最合理的方式，但你可以在 Lua 5.0的实现。另请参阅幻灯片。

Lua 实现闭包的要点是有效处理上值或外部局部变量。这使得 Lua 能够支持完整的词法作用域。有关 Lua 设计中这种支持如何演变的说明，请参阅 HOPL III 论文，The Evolution of卢阿。

Answer 2

由于你的问题不是很具体，只能用通用算法来回答。我也没有声称这是“最明智”的方式，只是一种有效的方式。

首先，我们需要定义问题空间。

您的脚本语言具有局部变量（使用 Lua 术语）：非全局变量。这些变量理论上可以被 lambda 捕获。

现在，我们假设您的脚本语言无法动态选择局部变量。这意味着，只需检查语法树，就可以看到以下内容：

1. 函数捕获了哪些局部变量。
2. 哪些局部变量不被函数捕获。
3. 哪些函数捕获其范围之外的局部变量。
4. 哪些函数不捕获其作用域之外的局部变量。

鉴于此信息，局部变量现在分为两组：纯局部变量和捕获的局部变量。我将这些称为“纯粹的当地人”和“捕获的当地人”。

由于缺乏更好的术语，纯粹的本地人是寄存器。当您编译为字节代码时，纯局部变量是最容易处理的。它们是特定的堆栈索引，或者它们是特定的寄存器名称。无论您如何进行堆栈管理，纯本地变量都会在特定范围内分配固定位置。如果您使用 JIT 的力量，那么这些将成为寄存器，或者最接近寄存器的东西。

关于捕获的局部变量，您需要了解的第一件事是：它们必须由内存管理器管理。它们独立于当前调用堆栈和作用域而存在，因此，它们需要是自由的-由捕获它们的函数引用的站立对象。这允许多个函数捕获相同的本地数据，从而引用彼此的私有数据。

因此，当您输入包含捕获的 lambda 的作用域时，您将分配一块内存，其中包含属于该特定作用域的所有捕获的局部变量。例如：

comp(threshold)
{
    local data;
    return lambda(x)
    {
        return x < (threshold + data);
    };
}

comp函数的根作用域有两个局部变量。他们两人都被俘虏了。因此，捕获的本地人的数量为2，纯本地人的数量为0。

因此，您的编译器（对于字节代码）将为纯局部变量分配 0 个寄存器/堆栈变量，并且它将分配一个包含两个变量的独立对象。假设您正在使用垃圾收集，您将需要一些东西来引用它才能使其继续存在。这很简单：您在寄存器/堆栈位置引用它，脚本无法直接访问该位置。所以实际上，您确实分配了一个寄存器/堆栈变量，但脚本无法直接触及它。

现在，让我们看看 lambda 做了什么。它创建了一个函数。同样，我们知道这个函数捕获了一些超出其范围的变量。我们知道它捕获了哪些变量。我们看到它捕获了两个变量，但我们也看到这两个变量来自同一个独立的内存块。

因此 lambda 所做的就是创建一个函数对象，该对象具有对某些字节码的引用以及对其关联的变量的引用。字节码将使用该引用来获取其捕获的变量。您的编译器知道哪些变量是函数的纯本地变量（例如参数 x ），哪些是外部捕获的本地变量（例如阈值）。所以它可以弄清楚如何访问每个变量。

现在，当 lambda 完成时，它会返回一个函数对象。此时，捕获的变量由两个事物引用：lambda 函数和堆栈：函数的当前作用域。然而，当 return 完成时，当前作用域将被销毁，并且之前引用的所有内容都不再被引用。因此，当它返回函数对象时，只有 lambda 函数拥有对捕获变量的引用。

但这一切都相当复杂。一个更简单的实现是有效地捕获所有局部变量； 所有局部变量都是捕获的局部变量。如果你这样做，那么你的编译器会变得更简单（而且可能更快）。当进入一个新的作用域时，该作用域的所有局部变量都被分配在一个内存块中。创建函数时，它会引用它使用的所有外部作用域（如果有）。当退出作用域时，它会删除对其分配的局部变量的引用。如果没有其他人引用它，则可以释放内存。

这非常简单明了。

Answer 3

如果我将其翻译成 C++（没有 lambda），它会看起来像这样：

struct comp_lamda_1 {
    int threshold;
    comp_lamda_1(int t) :threshold(t) {}
    bool operator()(int x) {
        return x < threshold;
    };
};

comp_lambda_1 comp(int threshold)
{
    return comp_lamda_1(threshold);
}

int main()
{
    auto a = comp(10);
    std::cout << a(5);
}

这表明解释器不应该将匿名函数视为独立函数，而应将其视为函数对象，它有成员来捕获所需的变量。

（要明确的是，关键是 comp_lamda_1 是一个函数对象，我知道您并没有要求对上述代码进行 C++ 翻译）

Answer 4

我一直在阅读有关 Lua 中使用的 upvalues 的内容。我将尝试实现一个类似的系统来处理闭包和完整的词法范围。棘手的部分是让编译器根据需要将关闭命令放置在正确的位置。

function()
{
    a = 6, b;

    {
        local c = 5;

        b = lambda() { return a*c; };

        // close c in closure;
    }

    b();

    // close a in closure
}