10

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

我选择尝试表示的示例如下，为了简洁起见，使用 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 之前该值很容易被污染。

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

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

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

4

1 回答 1

15

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

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

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

foo(42);

在上述情况下，理论上x闭包中的 in 可能存在于堆栈框架中，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结构可以被传递、返回和存储在堆栈上，因为环境是只读的，所以你没有生命周期问题，因为可以复制不可变数据而不影响语义。

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

于 2013-08-05T07:43:39.013 回答