闭包和上下文无关语法

Question

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

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

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

Answer 1

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

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

• 关系的“传递”闭包通过遵循（所有可能的）多个应用程序来“完成”关系。在日常用语中，“是……的后代”的概念是“是……的孩子”关系的传递闭包。

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

  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)
  

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

因此，实际上，“闭包”的使用首先具有不同的具体含义，乍一看似乎无关，但存在微妙的潜在关系。

Answer 2

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

为什么同名？函数闭包是“关闭”它的自由变量：

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

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

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

Answer 3

大流士是正确的; “封闭性质”与“功能关闭”无关。只有这么多的话要说： - （

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

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