学习中常常遇到同一个词语出现在多个地方，其中有一部分词语让我相当的困惑：
为什么两个词是一样的，但是感觉没有什么联系？比如「闭包」。

  • 数学中的「闭包」与计算机科学中的「闭包」有什么关系？
  • 内存管理中的「堆」与数据结构中的「堆」有什么关系？

我目前就想到这两个，那我就说说这两个，先说答案：他们没什么关系。

闭包

数学中的「闭包」：

数学中，若对某个集合的成员进行一种运算，生成的仍然是这个集合的成员，则该集合被称为 在这个运算下闭合 。
当一个集合 S 在某个运算下不闭合的时候，我们通常可以找到包含 S 的最小的闭合集合。这个最小闭合集合被称为 S 的（关于这个运算的） 闭包 。
中文维基百科

计算机科学中的「闭包」：

In programming languages, closures (also lexical closures or function closures) are techniques for implementing lexically scoped name binding in languages with first-class functions
Wikipedia

渣翻一下，大意是：

在编程语言中， 闭包 （也叫 词法闭包 或 函数闭包 ）是在语言中使用一等函数实现词法作用域名称绑定的技术。

看定义他们就没什么关系，Peter J. Landin 在 1964 年将术语 闭包 定义为一种包含 环境成分 和 控制成分 的实体，来指代某些其开放绑定（自由变量）已经由其语法环境完成闭合（或者绑定）的 lambda 表达式，从而形成了 闭合的表达式 ，或称闭包。在 SICP 中也提到了这个：

The use of the word “closure” here comes from abstract algebra, where a set of elements is said to be closed under an operation if applying the operation to elements in the set produces an element that is again an element of the set. The Lisp community also (unfortunately) uses the word “closure” to describe a totally unrelated concept: A closure is an implementation technique for representing procedures with free.
Structure and Interpretation of Computer Programs, 2nd ed. p.133

注意加粗的部分。这里需要注意一下，维基百科对闭包的定义与我们通常意义上的闭包是有所区别的，我们通常说的闭包往往是指：

调用一个函数 A，返回一个函数 B，其中函数 B 引用了 A 中的自由变量。我们称函数 A 使用了闭包。

维基百科对闭包的定义是从理论角度出发的，而我们通常意义上所指的闭包是从实践角度出发的，实践角度的闭包是理论角度的一个特例。

「闭包」这个词不仅仅出现这两个地方，我再举几个相关的词。

集合论中的「自反闭包」：

在数学中，集合 X 上的二元关系 R 的 自反闭包 是 X 上包含 R 的最小的自反关系。
集合 X 上的关系 R 的自反闭包 S 的定义为
$$
S=R\cup \left\lbrace(x,x):x\in X\right\rbrace
$$
换言之，R 的自反闭包是 R 与 X 上的恒等关系的并集。

集合论中的「对称闭包」：

在数学中，集合 X 上的二元关系 R 的 对称闭包 是 X 上包含 R 的最小的对称关系。
集合 X 上的关系 R 的对称闭包 S 的定义为
$$
S=R\cup \left\lbrace(x,y):(y,x)\in R\right\rbrace.\,
$$
换言之，R 的对称闭包是 R 与 X 上的逆关系的并集。

集合论中的「传递闭包」：

在数学中，集合 X 上的二元关系 R 的 传递闭包 是 X 上包含 R 的最小的传递关系。
集合 X 上的关系 R 的传递闭包 S 的定义为
$$
S=\bigcup_{i\in \lbrace 1,2,3,\ldots\rbrace} R^i.
$$
其中
$$
\begin{cases}
R^1 = R\,\\[2ex]
R^{i+1} = R \circ R^i
\end{cases}
$$
换言之，R 的传递闭包是 R 与 X 上的传递关系的并集。

形式语言中的「Kleene 闭包」：

假定
$$
V_{0}=\lbrace\epsilon \rbrace\,
$$
递归的定义集合
$$
V_{i+1}=\lbrace wv:w\in V_{i}\wedge v\in V\rbrace\, 这里的\ i>0\,
$$
如果 $V$ 是一个形式语言，集合 $V$ 的第 $i$ 次幂是集合 $V$ 同自身的 i 次串接的简写。就是说， $V_{i}$ 可以被理解为是从 $V$ 中的符号形成的所有长度为 $i$ 的字符串的集合。
所以在 $V$ 上的 Kleene 星号的定义是

$$
V^{*}=\bigcup_{i=0}^{+\infty} V_i=\left\lbrace\varepsilon \right\rbrace\cup V\cup V^{2}\cup V^{3}\cup \ldots
$$

就是说，它是从 $V$ 中的符号生成的所有可能的有限长度的字符串的并集。

自动机理论中的 「ε-闭包」：

对于任何 $p\in Q$，从 p 可到达的状态的集合叫做 p 的 ε-闭包 ，并写为
$$
\,E(\lbrace p\rbrace)=\lbrace q\in Q:p{\stackrel {\epsilon }{\rightarrow }}q\rbrace。
$$
对于 $P\subset Q$ 的任何子集，定义 P 的 ε-闭包 为
$$
E(P)=\bigcup \limits _{p\in P}E(\lbrace p\rbrace)
$$

纵观以上种种「闭包」，除去「词法闭包」，「闭包」都是指具备某种性质的最小集合，他们本质上的思想是一样的。而「词法闭包」与他们没有什么关系。

堆

内存管理中的「堆」：

在计算机科学中, 动态内存分配 （Dynamic memory allocation）又称为 堆内存分配 ，是指计算机程序在运行期中分配使用内存。它可以当成是一种分配有限内存资源所有权的方法。

数据结构中的「堆」：

堆（英语：Heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。这种数据结构具有以下性质

  • 任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
  • 堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

这两个概念毫无关系，Donald Knuth 曾多次说起此事， TAOCP 中提到：

Several authors began about 1975 to call the pool of available memory a “heap.” But in the present series of books, we will use that word only in its more traditional sense related to priority queues.
The Art of Computer Programming, Third Ed., Vol. 1, p. 435

在 CLRS 中也说：

The term “heap” was originally coined in the context of heapsort, but it has since come to refer to “garbage-collected storage,” such as the programming languages Java and Lisp provide. Our heap data structure is not garbage-collected storage, and whenever we refer to heaps in this book, we shall mean a data structure rather than an aspect of garbage collection.
Introduction to Algorithms, Third Ed, p. 151

内存管理中的「堆」，原意是类似「一堆衣物」的「堆」，表示没有具体的顺序，而「堆内存分配」的实现也往往是链表。与数据结构中的「堆」完全没有关系，数据结构中的「堆」源自「堆排序」。

参考：

文档信息
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
本文链接：www.snovey.com/2016/11/polysemy.html