不动点与强制令

# 不动点与罢工授权 来源：https://pvk.ca/Blog/2012/02/19/fixed-points-and-strike-mandates/ 编译和程序分析中的许多任务（我想在符号计算中总体上也是如此）本质上都是在求解形如 \\(x = f(x)\\) 的方程组。然而，当我们被要求定义这类算法来寻找不动点时，却很少停下来问一句：“我们究竟要找的是哪一个不动点？” 在实践中，我们通常关心的是单调函数的不动点：给定一个偏序 \\((\\prec)\\)，我们有 \\(a \\prec b \\Rightarrow f(a) \\prec f(b)\\)。这当然是一个相当合理的假设，而且它通常还允许我们利用 Tarski 不动点定理（https://en.wikipedia.org/wiki/Knaster%E2%80%93Tarski_theorem）：如果 \\(f\\) 的定义域（连同 \\(\\prec\\)）构成一个完备格（http://mathworld.wolfram.com/CompleteLattice.html），那么 \\(f\\) 的所有不动点的集合也同样构成完备格！作为推论，在 \\(\\prec\\) 之下恰好存在一个最小不动点和一个最大不动点。 这一点极其有用，因为我们可以定义有用的交（meet）与并（join）运算，并享有完备格的性质。例如，当定义域是某个给定集合的幂集时，我们可以用 \\(\\subset\\) 作为序关系、\\(\\cup\\) 作为并、\\(\\cap\\) 作为交。不过，让我觉得很有意思的是：当我们不去关注自己究竟想找哪一个不动点时，人类似乎总是会一致地开发出收敛到最小或最大不动点的算法——取决于具体问题。这就好像我们所有人都共享着同一个*盲点*，遮住了其中一个极端不动点。 一个简单的例子是死值（无用变量）消除。当有人问我会如何识别程序中的这类变量时，得到的朴素方案往往非常相似。它们都基于这样一个观察：如果一个值只被用来计算那些本身也是无用的值，那么它就是无用的。这些例程一开始就假定每个值都是活跃的（被使用的），然后不断剪掉无用的值，直到没有东西可剪为止。 这些算法收敛到的解是正确的，但并非最优（对无环代码除外）。我们希望尽可能多地识别出无用值，从而消除尽可能多的计算。然而，如果我们从“所有值都是活跃的”这一假设出发，算法就会漏掉一些明显无用的值，比如下面这段代码中的`x`： `` for (...) x = x `` 我们可以不断为算法添加更多的特殊情况。但正确（也是最简单）的做法是尝试识别活跃值，而不是无用值。一个值是活跃的，当且仅当它被用于计算某个活跃值。此外，返回值以及对内存的写入永远是活跃的。现在，我们的例程从“只有后者才是活跃的”这一假设出发，不断把它发现的活跃值加入进来，直到没有东西可加入为止。 在这个例子中，直觉方案收敛到的是最大不动点，而我们要找的却是最小不动点。设定正确的初始值，才能保证收敛到正确的不动点。 这一模式的其他常见实例还有：用引用计数（https://en.wikipedia.org/wiki/Reference_counting）代替标记（http://www.memorymanagement.org/glossary/m.html#marking），或者像 SBCL 那样在一开始给所有值都赋予顶类型来执行类型传播。 # (https://pvk.ca/Blog/2012/02/19/fixed-points-and-strike-mandates/#strike-algorithm) 我最近在数学和计算机科学之外也找到了不动点计算的一个用处。 魁北克的大多数大学或 CEGEP（https://en.wikipedia.org/wiki/CEGEP）学生会都已经（或即将）就罢工授权进行投票，以帮助组织针对今冬明春学费上涨的抗议活动。该省有数百个这样的学生会，合计代表约四十万名学生。这些学生会绝大多数只由两百名（甚至更少的）学生组成，许多会员认为只有极少数学生参加罢工会是得不偿失的。因此，罢工授权中常常包含一些条件，规定同样持有罢工授权的其他学生必须达到的最低人数，并对参与的工会、大学或学院的数量再附加下限。据我所知，迄今为止通过的所有授权都是单调的：如果某组罢工的工会满足了这些条件，那么这组工会的所有超集也同样满足。 Tarski 定理再次适用（这次是在学生会集合的幂集上使用 \\((\\subset, \\cup, \\cap)\\)）。那么，我们要找的是哪一个不动点呢？ 在我看来很清楚，我们要找的是罢工工会集合最大的那个不动点。在某些情况下，最小不动点可以平凡地是空集（或者是所有没有设定任何下限的工会）。此外，授权中通常附带这样的解释：如果至少代表 \\(n_0\\) 名学生的学生会采用了相同的授权，那么所有采用该授权的工会将同时罢工。 我请计算机系的研究生同学草拟一个算法，用来根据授权判断哪些工会应当罢工；他们从当前正在罢工的学生会集合出发，不断把条件全部满足的工会加入进来。这类算法会收敛到最小不动点。例如，可能存在两个工会，每个都有 5000 名学生，而它们设定的罢工门槛都是 10000 名学生，那么这类算法就会让两个工会都陷入僵局，都在等对方先开始罢工。 相反，我们应当从“所有（持有罢工授权的）工会都在罢工”这一假设出发，迭代地移除那些条件未全部满足的工会，直到达到最大不动点为止。我相当确信这最终只会是一个纯理论问题，但抽象数学帮助我们解读真实世界状况，这确实是个相当漂亮的例子。 在计算不动点时，这种“直觉上收敛到次优解”的模式似乎频繁出现。这未必是一个糟糕的选择：保守的初始值往往能带来更快的收敛，而且通常还具有中间解始终正确（可行）的性质。当我们需要快速得到结果时，以次优解为满足也是合理的。不过，这应当是一个刻意为之的选择，而不应是由于我们没能考虑其他可能性所导致的后果。