Closures in OOC

接上一篇Complexity Behind Closure,这次来专注于Rock是如何在C里实现Closure的。

这篇文章同时发布在Github上。

Block as Blocks

首先,需要指出的是,在C里面并不是完全没有办法使用Closure。Apple的GCC Fork里就给C添加了Block,用于实现Closure:

(Stolen from Wiki)

#include <stdio.h>
#include <Block.h>
typedef int (^IntBlock)(); IntBlock MakeCounter(int start, int increment) {
__block int i = start; return Block_copy( ^ {
int ret = i;
i += increment;
return ret;
}); } int main(void) {
IntBlock mycounter = MakeCounter(5, 2);
printf("First call: %d\n", mycounter());
printf("Second call: %d\n", mycounter());
printf("Third call: %d\n", mycounter()); /* because it was copied, it must also be released */
Block_release(mycounter); return 0;
}
/* Output:
First call: 5
Second call: 7
Third call: 9
*/

除去在代码风格上的偏见后,这个扩展看起来不是很差,不过依然有很多限制,比如考虑下面的功能:

isFound := false
filelist each(|filename, mode|
f := func -> String{
filename split("/") each(strip()) strip()[-1]
}
last := f(filename)
if(last == "mysdk"){
isFound = true
return true
}
false
)

尝试这用Apple的block扩展来实现一下?看起来一点不现实。并且就算实现了,也只能在Apple的GCC Fork下面工作,显然并不是我们在追求的东西。

Way to Variable

好的,在开始解释OOC的Closure之前,让我们先来想想Closure要有什么特性:

  • 能够自由的使用“自由变量”。 这里的“自由”是指在语法上定义于Closure以前的变量,比如
void test(Int a){
Int b; // closure
}

这时closure要有能力读写变量a和b。当然,这是闭包的基本要求。

  • 能够定义在任何地方。在Object Pascal/Delphi里,虽然我们能够定义nested function,但它的位置并不是自由的——当你在函数中间写了一个nested function时,编译器会要求你把它移动到顶端。但显然很多情况下我们需要的不仅仅是一个“临时”函数,我们还需要一个包含了之前定义过的所有变量的环境。

  • 能够“携带”定义时的环境。考虑下面的情况:

f := func(a: Int) -> Func->Int{
b: Int = a*2
return func-> Int { a + b }
} f1 := f(3)
f1() toString() println() f1 = f(4)
f1() toString() println()

这个时候应该输出什么? 显然是9和12。但如果我们的闭包不能携带这个环境的话,是没法输出正确的结果的。

Way in OOC

好的,现在让我们来看看在OOC里,closure是怎么实现的,这次让我们从最简单的情况开始:

main: func {
a := 3
f := func -> Int { a }
}

一个闭包,它只用来返回之前定义过的变量的值。在这里,如果你执行"#{f()}" println()的话,会得到结果3。好的,让我们首先看看OOC生成了什么,然后再慢慢解释: (另外,需要注意为什么我们这里要加上main函数? 因为如果没有main的话,所有的变量都会变成全局,在闭包里本身就可以直接读写,也就失去的例子的意义)

    lang_Numbers__Int a = 3;
__simpleclosure_simpleclosure_closure3_ctx* __simpleclosure_ctx4 = lang_Memory__gc_malloc(((lang_types__Class*)__simpleclosure_simpleclosure_closure3_ctx_class())->size);
(*(__simpleclosure_ctx4)) = (__simpleclosure_simpleclosure_closure3_ctx) {
a
};
lang_types__Closure __simpleclosure_closure5 = (lang_types__Closure) {
simpleclosure____simpleclosure_simpleclosure_closure3_thunk,
__simpleclosure_ctx4
};
lang_types__Closure f = __simpleclosure_closure5;
return 0;
} lang_Numbers__Int simpleclosure____simpleclosure_simpleclosure_closure3(lang_Numbers__Int a) {
return a;
} lang_Numbers__Int simpleclosure____simpleclosure_simpleclosure_closure3_thunk(__simpleclosure_simpleclosure_closure3_ctx* __context__) {
return simpleclosure____simpleclosure_simpleclosure_closure3((*__context__).a);
}

对于简单的两行代码,rock生成了一大堆东西。好的,让我们开始看到底发生了什么。

  1. 首先,OOC里closure是一个结构体,它包含两个部分:contextfunction pointer。function pointer很简单,就如同名字上说的,我们把closure当成一个普通函数,这个函数的指针就是function pointer。而context则包含了所有closure需要的变量。用C的代码来说的话,就像这样:
typedef struct {
Closure_Context* context;
void (* thunk)(Closure_Context*);
} myclosure; typedef struct {
Int a;
} Closure_Context;
  1. 当我们声明一个closure时,首先,这个closure会变成一个普通的函数,假设它的名字是closure_impl,但不同的地方是,除了本身声明时的参数外,这个closure还接受一个Closure_Context*作为参数。随后,我们初始化一个Closure_Context,它的成员包含了所有这个closure里用到的外部变量。在刚才那个例子里,我们只有一个Int a。最后,把这两个指针组合成myclosure,我们的声明就完成了。

  2. 到了这里,相信你早就明白该怎么使用它了,只要简单的myclosure->thunk(myclosure->context),一切就自然的完成了。让我们看看是不是真的这样:

main: func {
a := 3
f := func -> Int { a }
f()
}

编译之后:

    lang_Numbers__Int a = 3;
__simpleclosure_simpleclosure_closure3_ctx* __simpleclosure_ctx4 = lang_Memory__gc_malloc(((lang_types__Class*)__simpleclosure_simpleclosure_closure3_ctx_class())->size);
(*(__simpleclosure_ctx4)) = (__simpleclosure_simpleclosure_closure3_ctx) {
a
};
lang_types__Closure __simpleclosure_closure5 = (lang_types__Closure) {
simpleclosure____simpleclosure_simpleclosure_closure3_thunk,
__simpleclosure_ctx4
};
lang_types__Closure f = __simpleclosure_closure5;
((lang_Numbers__Int (*)(void*)) f.thunk)(f.context);

虽然比起手写的代码看起来要复杂,但跟我们的基本思想是完全一致的。

Pain in Context

不过,到这里其实一切并没有结束,因为我有意忽略了一个重要的地方——如何确定我们的context? 很显然,每个closure都有不同的context,不但意味这每个closure的context都要有自己的定义,还意味着我们必须自行推断需要把那些变量放进context里。好吧,让我们先看看第一个问题。

假设我们有这么一个代码:

foo: func{
b: Int = 1
f := func{
b + 1
}
} bar: func{
a, b: Int
f := func{
a = 1
b = 2
}
}

那么根据刚才介绍的构造,每一个f都会变成一个(context,thunk)的集合。thunk没有任何问题——简单的把f写成函数取地址就够了,那么让我们想想context该怎么构造。如果直接写的话,那么会是这样:

typedef struct{
int b;
} foo_f_context; typedef struct{
int* a;
int* b;
} bar_f_context;

这样,我们可以通过foo_f_context* -> b来访问b(只读),而可以通过bar_f_context* -> a来读写变量a。对,这种最简单的方法就是OOC所采用了。原因很简单——OOC不是C,在编译代码时所有closure访问了哪些变量都已经确定下来,我们只需要扫描一次,然后生成对应了struct就足够了。因此你会在头文件里找到这样的定义:

struct ___simpleclosure_simpleclosure_closure3_ctx {
lang_Numbers__Int a;
};

因为一切都是自动生成的,我们并不担心会出错。并且,这种方式非常简单而且高效。不过,如果打算直接在C代码里使用闭包,那问题就要复杂的多了——毕竟我们不可能给每一个闭包手写一个结构体。纵使可以用Hashmap来自由的访问变量,如何收集变量是一个大问题。现在回头看来,似乎Apple挑选了一个最好的方式,在没有破坏C的结构之下引入了闭包。

05-02 11:28