说到白给,能联想到的是「免费」,而免费的英文是「free」,free 还有个意思是「自由的」。所以这题我们就来聊聊约束变量(bound variables)和自由变量(free variables)。
对于集合 S = {x | x > 2} 中的所有的 x,我们可以对它进行更名(renaming),比如可以将所有的 x 都改名为 y:S' = {y | y > 2}。在这种情形下,S = S'。这样的一个变量 x 就被我们叫作「约束变量」,这样对约束变量更名的操作被叫作 α-变换(α-conversion)。
反之,对于这样的一个式子:a = 2, S = {x | x > a},对于这个集合中的 a,如果对它做更名,比如:a = 2, S' = {x | x > b},这样的一个集合 S' 不再等于原来的 S,这样的变量 a 就被叫作「自由变量」。同时我们可以说,这样的集合 S 捕获(capture)了自由变量 a。
非形式化地,我们举例 C++11 的 lambda expression:
int a = 2;
auto closure = [a](int x) {
return x > a;
};
这样的一个叫作 closure 的谓词(predicate),完成了对自由变量 a 的捕获。
下面,我们非形式化地对某一个语言 L 做不完全的定义:
对多参数的函数定义:
# x y : x + y
表示定义一个函数,接收两个参数,返回它们的「和」。
使用分号来分割同一函数中的多个语句:
# a b : a ; b
为避免歧义,如果有多条语句的函数定义中包含嵌套的函数定义,那么这个嵌套的函数定义一定是出现在尾部的。
那么,我们可以很容易用语言 L 定义对自由变量的捕获:
# a : # x : x > a
这样我们说,内层的函数捕获了自由变量 a。
下面我会给你多层函数嵌套,请你给出每一层函数定义中出现的自由变量。