什么是自由和绑定变量？

Question

我已经编程了很长时间(实际上太长了),但我真的很难理解"自由变量"和"绑定变量"这两个术语.

我在网上找到的大多数"解释"都是从谈论Lambda演算和形式逻辑或Axiomatic Semantics等主题开始的.这让我想要伸手去拿左轮手枪.

有人可以解释这两个术语,理想情况是从实现的角度来解释.它们是否可以存在于编译语言中,以及它们转换为哪些低级代码？

Answer 1

甲自由变量是在它的值取决于在功能范围内的一些功能中使用的变量调用,调用或使用.例如,在数学术语中,z是一个自由变量,因为它不受任何参数的限制.x是一个有界变量:

f(x) = x * z

在编程语言术语中,自由变量在运行时动态确定,在函数调用堆栈上向后搜索变量的名称.

有界变量求值不依赖于函数调用的上下文.这是最常见的现代编程语言变量类型.局部变量,全局变量和参数都是有界变量.

一个自由变量有点类似于" 擦肩而过名称一些古老的编程语言的"惯例.

假设您有一个f只打印一些变量的函数:

def f():
    print(X)

这是Python.虽然X它不是局部变量,但它的值遵循Python约定:它在定义函数的块的链上向上搜索,直到它到达顶级模块.

因为在Python中,值X由函数声明上下文决定,我们说这X是一个有界变量.

假设,如果X是一个自由变量,这应该打印10:

X = 2

def f():
    print(X)

def g():
    # X is a local variable to g, shadowing the global X
    X = 10
    f()

在Python中,此代码打印2,因为两个X变量都是有界的.局部X变量on g被限制为局部变量,而on on f局限于全局变量X.

履行

使用自由变量实现编程语言需要注意调用每个函数的上下文,并且对于每个自由变量使用一些反射来查找要使用的变量.

自由变量的值通常不能在编译时确定,因为它很大程度上取决于运行时流和调用堆栈.

Answer 2

变量是自由的还是绑定的是相对的; 这取决于您正在查看的代码片段.

在这个片段中,x被绑定:

function(x) {return x + x;};

在这里,x是免费的:

return x + x;

换句话说,自由度是上下文的属性.您没有说" x是自由变量"或" x是绑定变量",而是标识您正在讨论的上下文:" x在表达式E中是空闲的." 因此,根据您所讨论的代码片段,相同的变量x可以是空闲的或绑定的.如果片段包含变量的绑定站点(例如,它在函数参数中列出),则它被绑定,如果不是,则它是空闲的.

从实现角度来看,自由/绑定区别很重要的是当您实现变量替换的工作方式时(例如,当您将参数应用于函数时会发生什么.)考虑评估步骤:

(function(x) {return x + x;})(3);
=> 3 + 3
=> 6

这很好用,因为x在函数体中是自由的.但是,如果x绑定在函数体中,我们的评估需要小心:

(function(x) {return (function(x){return x * 2;})(x + x);})(3);
=> (function(x){return x * 2;})(3 + 3); // careful to leave this x alone for now!
=> (function(x){return x * 2;})(6);
=> 6 * 2
=> 12

如果我们的实现没有检查绑定的出现,它可能已经替换了绑定的x x并给了我们错误的答案:

(function(x) {return (function(x){return x * 2;})(x + x);})(3);
=> (function(x){return 3 * 2;})(3 + 3); // Bad! We substituted for a bound x!
=> (function(x){return 3 * 2;})(6);
=> 3 * 2
=> 6

此外,应该澄清的是,free与bound是语法的属性(即代码本身),而不是在运行时如何评估代码的属性.vz0讨论动态范围变量,它们与自由变量有些相关但不是同义词.正如vz0正确描述的那样,动态变量作用域是一种语言特性,它允许通过查看运行时调用栈来查找包含自由变量的表达式,以查找共享同一名称的变量的值.然而,在不允许动态范围的语言中讨论变量的自由出现仍然是有意义的:如果你试图在这些中计算这样的表达式,你只会得到一个错误(比如" x未定义")语言.

我无法自拔:我希望有一天,当人们提到lambda演算时,你可以在心里找到你的左轮手枪!Lambda演算是思考变量和绑定的好工具,因为它是一种极其简单的编程语言,支持变量和替换而不是其他任何东西.真实编程语言包含许多其他垃圾(例如动态范围),这些垃圾模糊了本质.