在编译器中实现闭包

我正在尝试设计一个伪汇编代码的基本编译器。但是，我不知道如何实现闭包。看来我需要将特定的寄存器值与每个“子例程”相关联。我考虑过使用堆栈，但它似乎又不够。似乎只有关联数组才能工作，但是如何在汇编中完成该操作或类似的操作呢？

我选择尝试表示的示例如下，为了简洁起见，以 CoffeeScript 进行交流。

((x) -> (y) -> x(y))((x) -> x)(2)

这是我一直在尝试的总体结构。这是我正在编译的伪程序集的示例。

'((label lam1)   ;; (x) -> x
  (cp resp arg)
  (ret)

  (label lam2)   ;; (y) -> x(y)
  (jmp x)

  (label lam3)   ;; (x) -> [(y) -> ...]
  (cp x arg)     ;; this is the assignment intended for a closure
  (cp resp lam2) ;; this is a returned lambda, needing the closure
  (ret)

  (label main)
  (cp arg lam1)
  (call lam3)
  (set arg 2)
  (call resp))) 

这有效；但是，该值只是在名称下设置x然后返回一个 lambda，x在执行 lambda 之前，值很容易被污染。

计算机程序的结构和解释中的实现描述如下，这对我来说在汇编中似乎不可行。我不知道他们还能使用什么其他策略。

过程对象将在运行时通过将当前环境（定义时的环境）与已编译过程的入口点（新生成的标签）相结合来构造。

总之，寄存器值如何与“子程序”相关联？堆栈就足够了吗？

堆栈是不够的...考虑一个更简单的情况

function bar(f) {
    alert(f());
}

function foo(x) {
    bar(function(){ return x; });
}

foo(42);

在上述情况下，理论上是可以的x在闭包中居住在堆栈框架中foo因为闭包不会比它的创建者活得更久foo。 然而，有一个小小的改变：

function bar(f) {
    to_call_later.push(f);
}

闭包将被存储起来，并且可能会在以下情况下被调用：foo已经终止并且其激活记录的堆栈空间已被回收。清楚地x不能位于该堆栈区域中，因为它必须生存。

因此存在两个问题：

1. 一个闭包必须有一些存储（环境）。当你认为调用时，这是显而易见的foo两次传递两个不同的值应该创建两个独立的存储x。如果闭包只是代码，那么这是不可能的，除非每次调用时都会生成不同的代码foo.

2. 该存储必须存在at least只要闭包本身，而不仅仅是谁创建了闭包。

另请注意，如果您想要读/写封闭变量，则需要额外的间接级别，例如：

function bar(f) {
    alert(f());
}

function foo(x) {
    var c1 = function() { return ++x; };
    var c2 = function() { return x *= 2; };
    bar(c1);
    bar(c2);
}

foo(42);  // displays 42+1=43 and 43*2=86 (not 42*2=84!)

换句话说，你可以有几个不同的闭包共享the same环境。

So x不能在堆栈中foo激活记录，它不能位于闭包对象本身中。闭包对象必须有一个pointer去哪里x活着。

在 x86 上实现此功能的可能解决方案是：

• 使用垃圾收集或引用计数内存管理系统。堆栈目前还不足以处理闭包。

• 每个闭包都是一个具有两个字段的对象：一个指向代码的指针和一个指向封闭变量（“环境”）的指针数组。

• 执行代码时你有一个堆栈esp以及例如esi指向闭包对象本身（所以(esi)是代码的地址，(esi+4)是第一个封闭变量的地址，(esi+8)是第二个封闭变量的地址，依此类推）。

• 每个变量都是一个独立的堆分配对象，只要仍有闭包指向它，它就可以生存。

这当然是一种非常粗暴的做法。例如，SBCL 更加智能，未捕获的变量仅分配在堆栈和/或寄存器上。这需要对闭包的使用方式进行分析。

Edit

假设您只考虑纯函数设置（换句话说，函数/闭包的返回值仅取决于传递的参数并且闭包状态不能改变），那么事情可以稍微简化一些。

您可以做的是制作包含捕获的闭包对象values而不是捕获的变量并且通过同时使闭包本身成为可复制对象，理论上可以使用堆栈（除了闭包的大小可能会根据需要捕获的状态量而变化的问题），所以这并不容易至少对我来说，在这种情况下可以想象一个合理的基于堆栈的参数传递和值返回协议。

通过使闭包成为固定大小的对象来消除可变大小问题，您可以看到这个 C 程序如何仅使用堆栈来实现闭包（请注意，没有malloc calls)

#include <stdio.h>

typedef struct TClosure {
    int (*code)(struct TClosure *env, int);
    int state;
} Closure;

int call(Closure *c, int x) {
    return c->code(c, x);
}

int adder_code(Closure *env, int x) {
    return env->state + x;
}

int multiplier_code(Closure *env, int x) {
    return env->state * x;
}

Closure make_closure(int op, int k) {
    Closure c;
    c.state = k;
    c.code = (op == '+' ? adder_code : multiplier_code);
    return c;
}

int main(int argc, const char *argv[]) {
    Closure c1 = make_closure('+', 10);
    Closure c2 = make_closure('*', 3);
    printf("c1(3) = %i, c2(3) = %i\n",
           call(&c1, 3), call(&c2, 3));
    return 0;
}

Closure结构可以传递、返回并存储在堆栈上，因为环境是只读的，因此您不会遇到生命周期问题，因为可以复制不可变数据而不影响语义。

C 编译器可以使用这种方法来创建只能按值捕获变量的闭包，这确实是 C++11 lambda 所提供的（您也可以通过引用捕获，但要由程序员来确保捕获变量的生命周期）足够持续）。