6

我正在查看我的理论计算机科学课程的教学大纲，并在上下文无关语法的标题中列出了“闭包属性”。我翻阅了关于这个主题的教科书，发现很少。目前它所拥有的东西有点超出我的想象（我还没有上过这门课程），但我了解一点。

我想知道上下文无关语法中的闭包概念是否与函数式编程中的闭包概念相同或相关。据我所知，它谈到了结合语法和解决重叠问题。书中的部分有很多部分我还不明白，所以我不确定这些想法是否相同。

（更多背景信息：我正在给教授写一封电子邮件，询问是否可以将课程从 Perl 切换到 Ruby 或 Python。如果这些概念相关，那可能是我们应该使用 Ruby 而不是 Perl 的另一个原因。）

4

3 回答 3

9

术语“闭包”以多种方式使用，在某种意义上主要追溯到数学的完成概念。

  • 如果将该运算符应用于集合中的值总是从给定集合中产生一个值，则该运算符被“封闭”一组值。例如，加法对整数是封闭的，但除法不是（4 / 2 是整数，但 5 / 2 不是）。因此，整数的加法在某种意义上是“完整的”，而除法不是。

  • 关系的“传递”闭包通过遵循（所有可能的）多个应用程序来“完成”关系。在日常术语中，“is a descendent of”的概念是“is a child of”关系的传递闭包。

  • 通过例如指定如何解析自由变量来“完成”功能性“闭包”。在伪代码表达式中：

    bump = function(x) (x + y)

    x是 的论点bump，但定义似乎留下了“开放”的解决问题y。另一方面，如果我们定义：

    bumper = function(y) (function(x) (x + y))

    然后调用bumper返回一个函数，该函数将 的原始参数添加bumper到创建的函数的参数中，因此：

    add3 = bumper(3)

    相当于定义：

    add3 = function(x) (x + 3)

    嵌套定义“封闭”（或完成）在其定义点可用的变量。

所以，实际上，“闭包”的使用上面都有不同的具体含义，乍一看似乎无关，但有一种微妙的潜在关系。

于 2009-01-10T02:49:32.193 回答
7

闭包属性是这样的：如果 L 和 M 是上下文无关语言，那么 L|M 也是。函数闭包是实现一流函数的一种方式。所以不，他们几乎没有任何关系。

那为什么叫同名呢？函数闭包“封闭”其自由变量：

def adder(n): return lambda m: n + m

这里 n 是 lambda 的一个自由变量。这个名字强调了这一点，因为 Lisp 最初并没有关闭自由变量——当调用内部函数时，它们会从堆栈上的任何绑定中获取它们的值。

数学中属性的闭包更为明显：如果一个集合在一个操作下是封闭的，那么在该集合中应用该操作不会让你脱离它。如果你添加整数，你得到的仍然是一个整数。

于 2009-01-10T01:32:39.323 回答
5

大流士是正确的；“闭包属性”与“函数闭包”无关。只有这么多话要说:-(

闭包属性的思想被应用在整个计算机科学中，但它也被广泛应用于不同类别的语言。不同类别的语言很重要，因为您需要不同的技术来扫描或识别话语。例如，正则表达式可以告诉您是否有保留字，但不能告诉您是否有带平衡括号的表达式——因为您需要上下文无关的语法。

人们普遍感兴趣的是，如果你学习一种特定的语言并且你与另一种语言相交或联合，或者只是补充这种语言，你是否会在同一个班级中获得另一种语言。例如，是否可以编写一个正则表达式来完全匹配那些不是保留字的标记？我们可以回答一个响亮的“是”，因为正则语言在补语下是封闭的，也就是说，正则语言的补语本身就是正则语言。这是一个闭包属性的例子。通常证明是建设性的，也就是说，它不仅告诉你存在一个描述所有非保留字标记的正则表达式，闭包属性的证明会告诉你如何找到这样的正则表达式。

于 2009-01-10T02:12:27.573 回答