匿名函数与闭包实现

Posted on In Disqus:

简单记录一下如何实现函数式语言的必备功能——匿名函数与闭包。

closure 闭包

看一段 Python 中闭包的例子：

1
2
3
4
5
6
def add2(a):
    def add1(b):
        return a + b
    return add1

print(add2(1)(2))  # output 3

Python 是允许函数嵌套的，其中 add1 就是一个闭包的例子。闭包与函数的区别在于，闭包中还包含了在那个函数中出现的自由变量（由函数外部决定取值的变量）的值。在 add1 中，a 没有在它的参数列表中，也没有在函数体内被定义，而是来源于上层函数 add2 的参数，那么它就是一个自由变量。也就是说，add1 作为一个闭包，它同时拥有函数定义以及自由变量 a 的取值。

1
add2(1) = closure(<function definition>, a=1)

再来看一下 C++ 中的例子：

1
2
3
4
5
6
7
std::function<int(int)> add2(int a) {
    return [a](int b)->int { return a + b; };
}

int main() {
    std::cout << add2(1)(2) << std::endl;
}

一个微小的区别就是，我手动指定了闭包中需要捕获的自由变量是 a（当然也可以用 & 或者 = 来自动按引用或者按值捕获）。

lambda lifting 匿名函数提升

假设我们的目标代码是 machine code（机器语言），汇编中可以有函数的概念（比如对于 x64，参数按顺序放在寄存器里，返回值放在 eax 里，还有 call 指令），但肯定没有闭包的概念（因为连变量的概念也没有）。那么我们要做的事情就是把闭包变得和普通函数一样。

同样以 python 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Closure:
    def __init__(self, f=None, env=None):
        self.f = f
        self.env = env
        
    def __call__(self, *args, **kwargs):
        return self.f(*args, **kwargs, __env=self.env)


def add1(b, __env):
    return b + __env['a']

def add2(a):
    return Closure(add1, dict(a=a))

print(add2(1)(2))

和之前的区别在于，add1 不再是一个嵌套函数，而是变成了一个顶层函数（这个过程就被称为 lambda lifting）。对于闭包函数中的自由变量，塞进了一个名为 __env 的函数参数里。而闭包本身不再是一个 <function> 的对象，而是一个 Closure 类的对象，包含了函数本身以及所需的自由变量的值。

lambda function 匿名函数

剩下的就是处理匿名函数的问题了，这部分其实最为简单。依旧以 Python 为例子：

1
2
3
4
5
6
7
8
9
10
11
factorial = lambda x: x * factorial(x - 1) if x > 0 else 1
print(factorial(10))  # output 3628800


def __lambda_0(x, __env):
    return x * __env['factorial'](x - 1) if x > 0 else 1

f = Closure()
f.f = __lambda_0
f.env = dict(factorial=f)
print(f(10))  # output 3628800

唯一的区别就是给 lambda 取个名字，然后用之前提到的方法把它变成顶层函数，再用对应的 closure 替换原来这个 lambda 所在的位置。

实现

为了实现 lambda 和 closure，编译器需要做的事情有：

  • 给匿名函数取个名字
  • 分析所有函数的自由变量，并用一个新的顶层函数替代它，这个新的顶层函数参数除了原有参数外还包含了所需的自由变量
  • 用一个包含函数指针 (f) 和所有自由变量取值 (env) 的结构体 (closure) 取代所有匿名函数或者闭包所出现的位置

最后效果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct closure {
    void *f;
    void *env;
};

/*
def add2(a):
	def add1(b):
		return a + b
    return add1
*/
struct __add1_env {
    int a;
};
int __add1(int b, void* env) {
    return ((__add1_env*)env)->a + b;
}
closure __add2(int a, void* env) {
    auto add1_env = new __add1_env{a};
    return closure{(void*)__add1, add1_env};
}
closure add2 = {(void*)__add2, nullptr};

int main() {
// f = add2
    closure f = add2;
// g = add2(1)
    closure g = ((closure(*)(int, void*))f.f)(1, f.env);
// h = g(2)
    int h = ((int(*)(int, void*))g.f)(2, g.env);
// print(h)
    std::cout << h << std::endl;
}

注：

  • 为了统一，所有的函数以闭包形式出现，对于原有的顶层函数或者不含自由变量的匿名函数，env 参数为空）
  • 虽然以 C++ 代码呈现，但是可以很容易地转成 LLVM IR

参考

  • https://nim-lang.org/docs/intern.html#code-generation-for-closures