闭包和上下文无关文法

Question

我正在查看我理论计算机科学课程的教材大纲，在上下文无关语法的标题下，它列出了“闭包性质”。我查阅了有关这个主题的教科书，但内容很少。其中一些对我来说有点难以理解（我还没有上过这门课），但我已经了解了一些。

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

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

- Saterus

---

我不确定你想表达什么，以至于这支持了从 Perl 切换的论点。Perl 支持闭包，并且有多个 Perl 模块（更不用说正则表达式支持）用于解析 CFG。...我有什么遗漏吗？ - Adam Bellaire

嗯，我的错。不，你没有漏掉任何东西。你是完全正确的，Perl有闭包。所以那个观点是完全无关紧要的。我一直在学习函数式编程，只听说过在fp语言、C#甚至Java中提到过闭包。从未听说过Perl。这是错误的假设。抱歉。 - Saterus

实际上，据我所知，Perl在Java发布之前就已经有闭包了。Ruby从Perl复制了许多东西，包括闭包。 - Brad Gilbert

Answer 1

术语“闭包”在各种情况下都有所用，大多追溯到某种意义上的数学概念完成。

• An operator is "closed over" a set of values if applying that operator to values from the set always produces a value from the given set. For example, addition is closed over the integers, but division isn't (4 / 2 is integral, but 5 / 2 isn't). So addition of integers is somehow "complete" in a sense that division isn't.

• The "transitive" closure of a relation "completes" the relation by following (all possible) multiple applications. In everyday terms, the concept of "is a descendent of" is the transitive closure of the relation "is a child of".

• A functional "closure" is "completed" by e.g. specifying how the free variables are to be resolved. In the pseudo-code expression:

  bump = function(x) (x + y)
  

  x is the argument to bump, but the definition seems to leave "open" the question of resolving y. On the other hand, if we define:

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

  then invoking bumper returns a function which adds the original argument of bumper to the created function's argument, so that:

  add3 = bumper(3)
  

  is equivalent to defining:

  add3 = function(x) (x + 3)
  

  The nested definition is "closed over" (or completed by) the variables available at the point of its definition.

因此，实际上，“closure”的用途主要具有不同的特定含义，乍一看似乎没有关联，但是存在微妙的基本关系。

- joel.neely

Answer 2

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

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

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

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

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

- Darius Bacon

Answer 3

人们通常感兴趣的是：如果您将特定语言与另一种语言相交、并集或者简单地对该语言进行补集，您是否会得到同一类别的另一种语言。例如，是否可能编写一个正则表达式，精确匹配那些不是保留字的标记？我们可以回答一个响亮的“是”，因为正则语言在补集下是封闭的，即，一个正则语言的补集仍然是一个正则语言。这是闭包属性的一个例子。通常证明是构造性的，也就是说，它不仅告诉您存在一个描述所有不是保留字的标记的正则表达式，而且闭包属性的证明还会告诉您如何找到这样的正则表达式。

- Norman Ramsey