在编译器中实现闭包

Question

我试图为伪汇编代码设计一个基本的编译器.但是，我不知道如何实现闭包。似乎我需要将特定的注册值与每个“子例程”相关联。我已经考虑过堆栈的使用，但是再次看来它是不够的。似乎只有一个关联数组才能工作，但是如何在程序集中实现这一点，或者类似的事情呢？

我选择尝试表示的示例如下，为了简洁，以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，在执行lambda之前，x值很容易被污染。

对计算机程序的结构和解释中的实现的描述如下，在我看来，在汇编中这是不可行的。我不知道他们还会用什么战术。

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

总之，如何将值注册到“子例程”？堆栈是否足够？

Answer 1

堆栈是不够的..。考虑一个更简单的例子。

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. 此存储必须在至少与闭包本身一样长的上运行，而不仅仅是由谁创建闭包。

还请注意，如果您希望有读/写关闭变量，您需要额外的间接级别，例如：

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!)

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

因此，x不能在foo激活记录堆栈中，也不能在闭包对象本身中。闭包对象必须有一个指针，指向x所在的位置。

在比如说x86上实现这一点的一个可能的解决方案是：

• 使用垃圾收集或引用计数内存管理系统。堆栈远远不足以处理闭包。
• 每个闭包都是一个有两个字段的对象:一个指向代码的指针和一个指向封闭变量的指针数组(“环境”)。
• 在执行代码时，您有一个堆栈esp，例如，esi指向闭包对象本身(因此(esi)是代码的地址，(esi+4)是第一个闭包变量的地址，(esi+8)是第二个闭包变量的地址，等等)。
• 每个变量都是一个独立的堆分配对象，只要仍然存在指向它的闭包，该对象就可以生存下来。

这当然是一种非常粗糙的做法。例如，SBCL要聪明得多，没有捕获的变量只在堆栈和/或寄存器上分配。这需要对如何使用闭包进行分析。

编辑

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

您可以做的是使包含捕获的值的闭包对象，而不是捕获的变量，同时使闭包本身成为一个可复制的对象，这样理论上就可以只使用一个堆栈(但问题是闭包的大小取决于需要捕获多少状态)，所以至少在这种情况下，我很难想象一个合理的堆栈协议，用于参数传递和值返回。

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

#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所提供的(您也可以通过引用捕获，但要由程序员来确保捕获的变量的生存期足够长)。