在编译器中实现闭包

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,在x执行lambda之前,该值很容易被污染.

计算机程序的结构和解释中的实现描述如下,在组装中似乎不可行.我不知道他们可以使用什么其他策略.

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

总之,如何将寄存器值与"子程序"相关联？堆叠是否足够？

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 结构可以传递,返回并存储在堆栈中,因为环境是只读的,因此您不会遇到生命周期问题,因为可以复制不可变数据而不会影响语义.

AC编译器可以使用这种方法创建只能按值捕获变量的闭包,实际上是C++ 11 lambda提供的(你也可以通过引用捕获,但是由程序员来确保捕获变量的生命周期)持续足够).