闭包和上下文无关语法

Question

我正在查看我的理论计算机科学类(class)的教学大纲，并在 Context Free Grammars 的标题中列出了“闭包属性”。我已经翻阅了关于这个主题的教科书，但发现的很少。目前它确实有一点点在我的头上(我还没有上过这门课)，但我有点理解。

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

(更多上下文:我正在给教授写一封电子邮件，询问是否可以将类(class)从 Perl 切换到 Ruby 或 Python。如果这些概念相关，这可能是我们应该使用 Ruby 而不是 Perl 的另一个原因。)

Answer 1

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

如果将运算符应用于集合中的值总是从给定的集合中产生一个值，则运算符是“封闭”一组值。例如，加法对整数是封闭的，但除法不是(4/2 是整数，但 5/2 不是)。所以从某种意义上说，整数的加法是“完整的”，而除法不是。

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

一个功能性的“闭包”是由例如“完成”的指定如何解析自由变量。在伪代码表达式中:

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)

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

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