使用冷门图论解决编程语言问题

Using obscure graph theory to solve programming languages problems

Source | HN Comments

文章讲述了作者使用冷门图论解决编程语言中共享计算（let 绑定）问题的故事。最初的方案复杂且难以维护，作者尝试了多种方法，最终通过研究“最低单公共祖先”（LSCA）的概念，结合现有的库，找到了一种优雅且线性时间复杂度的解决方案。整个过程体现了问题分析、尝试不同方案、寻求专业知识、以及最终找到高效解决方案的历程，并强调了运气、合作和知识积累的重要性。

Using Obscure Graph Theory to solve PL Problems

← → 2025年5月4日 [graph theory](https://reasonablypolymorphic.com/blog/solving-lcsa/</tags/graph theory.html>), development, haskell

通常我写的是我已解决的问题的_解决方案_，但我发现自己越来越对_解决方案的来源_感兴趣。也许是因为我一直在读 Boorstin 的优秀作品 The Discoverers，我强烈推荐这本书。

不管是什么原因，我想今天换个通常的舞步，讨论一下解决我最近遇到的重大问题，实际上是什么样子的，包括我尝试了什么，我查找了什么，以及时间线是什么。

问题

问题是将程序图序列化为一系列 let 绑定。例如，给定以下图：

   +
  /  \
 f ---> g
 |   / \
 a   \ /
   expensive

它表示程序：

[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb2-1>)f a (g expensive expensive) + g expensive expensive

不幸的是，这是程序的简单表示，因为它重复了计算 expensive 四次的工作，以及 g expensive expensive 两次。相反，我们更希望生成等效但更高效的程序：

[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb3-1>)let $0 = expensive
[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb3-2>)  $1 = g $0 $0
[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb3-3>) in f a $1 + $1

这种转换被称为 sharing，因为它在有重复工作要做时共享计算出的答案。

这就是我们要做的。给定原始图，确定插入这些 let 绑定的最佳位置，对于“最佳”的某种合理定义。我们可以假设没有涉及副作用，因此表达式作用域良好的任何位置都是可接受的解决方案。

为了理解我尝试的一些解决方案，值得注意的是，我们的最终解决方案应该构建 Expr 类型的结构，而原始图表示为 IntMap (ExprF Int)。 ExprF 是 Expr 的 Base functor（Base），它的所有自引用都被某个类型变量替换，在本例中是 Int。因此，上面的图看起来更像：

[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb4-1>)_ : IntMap (ExprF Int)
[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb4-2>)_ = IM.fromList
[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb4-3>) [ (0, Apply "+" [1, 3])
[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb4-4>) , (1, Apply "f" [2, 3]
[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb4-5>) , (2, ...) -- a
[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb4-6>) , (3, Apply "g" [4, 4])
[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb4-7>) , (4, ...) -- expensive
[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb4-8>) ]

最初的解决方案

我花了一年多的时间来解决这个问题，在此期间有各种大部分可行的解决方案。我的策略是认真思考，写一些看起来合理的算法，然后针对我们（小的）集成测试套件运行它，以确保它得到与以前相同的答案。

为什么不进行属性测试呢？我尝试了，但发现很难实现能够可靠地引入共享 thunk 的良好类型的生成器。但也许这里应该学到关于编写好的生成器的不同的教训。

无论如何。八个月来，其中一种认真思考的算法满足了要求，并没有给我们带来任何问题。这是一个奇怪的、定制的解决方案，它独立地跟踪每个图片段中的所有自由变量，并尝试在我们进入所有自由变量都在作用域内的上下文中时立即 let-bind 片段。它似乎有效，但它非常混乱且难以维护。

在编写本文时，这种 sharing 算法是我们整个语言中 let-bind 的唯一来源，这意味着它不需要考虑程序中的 let-bind。

当然，这种不变性最终发生了变化。我们添加了一种在源代码中引入 let 的方法，这意味着我的算法是错误的。而且我写它已经有足够长的时间了，以至于我不再记得 它为什么能工作。这意味着我的程序的理论已经丢失，因此我们应该重写它。

展开解决方案

我回到了问题陈述，并长时间地盯着它（回到认真思考的算法！）。盯着这个问题，我意识到我真正要做的是确定 program graph 中 diamond 模式出现的位置。

回想一下我们的原始图：

   +
  /  \
 f ---> g
 |   / \
 a   \ /
   expensive

如果我们重新绘制它，使 g 位于与 f 不同的 rank 上，那么两个 diamond 模式将变得更加清晰：

   +
  / \
 f   |
 | \  |
 a \ /
   g
   / \
   \ /
  expensive

我想出的见解是，如果节点 n 是 diamond 的源，那么我们必须在内联 n 的定义之前立即 let-bind diamond 的 sink。

这就引出了一个问题：“我们如何识别 diamond？” 我们可以做的是给出从每个节点到其可达节点集的映射。例如，在上面，我们将计算映射：

+     -> {+, f, a, g, expensive}
f     -> {f, a, g, expensive}
a     -> {a}
g     -> {g, expensive}
expensive -> {expensive}

然后，当我们去内联一个节点时，比如 +，我们可以查找可以通过其多个直接子项到达的任何节点。由于 + 的直接子项是 f 和 g，我们可以取它们可达集合的交集：

{f, a, g, expensive} union {g, expensive}

得到

{g, expensive}

这正是我们需要执行 sharing 的节点集。如果你对这个集合进行拓扑排序，它会给你执行 let 绑定的顺序。

除了整个事情有一个问题。如果这个 diamond 中的一个项包含自由变量会发生什么？特别是，我们可能会有这样的情况：

   +
  / \
 f   |
 | \  |
 a \ /
   λx
   / \
   \ /
  expensive
   |
   x

当我们查看 + 时，这给了我们一组类似的可达节点，但我们显然不能将 expensive x 提升到 lambda 之上。

解决这个问题需要放弃记忆化整个可达节点集的概念，而是爬取图以确保一切都很好地限定范围。

性能问题

我的算法看起来不错，重要的是，在我们（小的）集成测试套件中，在合理的时间内得到了正确的答案。所以我发布了它，称赞自己做得很好，并没有再考虑它。大约一个星期，直到收到一份错误报告，说我们的编译器现在似乎在大程序上挂起。

这是我没有注意到的，因为我们的集成测试中没有任何大型程序。

糟糕！

在深入研究是什么导致速度如此之慢时，我注意到我的算法意外地变成了二次方。我需要折叠图中的每个节点，这需要查看它下面的整个可达集合。我已经放入了一些明显的保护措施，希望它们能尽早修剪搜索树，但对于伟大的渐近线之神来说，牺牲还不够。

我有没有提到，在这个故事的这一点上，让这个算法快速运行是公司的关键路径？其他所有人都在等着我弄清楚这一点。说说压力！

无论如何。你会注意到，在我对算法的描述中，一切听起来都不错。但正如俗话所说，精华在于细节。计算可达性并不是这里要使用的正确方法，因为它给出的 lambda 示例的答案是错误的。这很不幸，因为我们可以用线性时间完成可达性。

然后，当可达性不起作用时，我就放弃了快速性能，并希望我的定制算法能够完成这项工作。我唯一的救赎来自于至少它得到了正确的答案，即使它做得非常慢。

寻找内核

回到绘图板。

每当我遇到图论问题时，我都会打电话给我的朋友 Vikrem。他擅长这类书呆子 stuff。

我们橡皮鸭了这个问题，并尝试用图论的语言重新定义这个问题。我们经历了一个 Merkiv-Maguire 时刻，我们独立地意识到目标以某种方式与找到节点的 最低公共祖先 (LCA) 有关。

也就是说，粗略地说，我们正在寻找 diamond 图中的分叉。我们已经知道了，但有一些语言来描述它很好。

我们的新问题是，LCA 仅在树上定义。有一些扩展到 DAG，但似乎没有一个是特别站得住脚的。然而，搜索完全这一点带我到了这个 stackoverflow 问题，其中在评论中有人建议发帖人不是在寻找 LCA，而是在寻找一个相关的概念，即 最低单公共祖先。 LSCA 在 2010 年的一篇论文树和有向无环图中的新公共祖先问题中定义。

LCA(x, y) = l 的标准定义是“l 是 x 和 y 的祖先，并且 l 的任何后代都没有此属性。”

但是 LSCA(x, y) = l 的定义是“l 位于所有从根到 x 的路径上，并且 l 位于所有从根到 y 的路径上，并且 l 的任何后代都没有此属性。”

两者之间的区别很容易在下图中看到：

 0
 / \
1  2
| X |
3  4

在标准定义下，LCA 对于 DAG 不是唯一定义的。也就是说，LCA(3, 4) = {1, 2}。但是 1 和 2 都不位于所有从根开始的路径上。因此，在 LSCA 下，我们得到 LSCA(3, 4) = 0，这显然是 let-bind 3 和 4 的正确位置。

该论文给出了一种通过构建“最低单祖先” (LSA) 树来计算 LSCA 的预处理方案。节点的 LSA 是其所有入边的 LSCA。这个定义意味着“任何节点上方的最直接 diamond”。终于！这正是我们所寻找的，因为这是我们必须插入 let 绑定的地方！更好的是，该论文为我们提供了一种以线性时间计算 LSA 树的算法！

第一位实施者

当然，我很懒，宁愿不实现这个东西。因此，我搜索了 hackage 上的 lsca，但一无所获。但随后我搜索了 lca，发现和往常一样，Ed Kmett 领先了我 13 年。

lca 包实现了一种 O(logn) 算法，用于计算图中任意两个节点的 LCA。这对我来说非常方便，因为 LSCA 算法需要能够做到这一点。

我想是时候卷起袖子开始工作了。

这篇论文出乎意料地简单明了，我的第一次尝试是按照给定的（命令式的）算法来实现（命令式的）。第一步是对 DAG 进行拓扑排序，以便知道应该以什么顺序展开 LSA 树。

但正如经常发生的那样，这种拓扑排序实际上与算法无关；它只是以命令式表达算法的编码细节。但是当你站在懒惰的一边时，你不需要它！相反，你可以简单地将知识联系起来并做一些很酷的事情，比如这样：

[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb12-1>)lsaTree :: Ord v => Map v (Set v) -> Map v (Path v)
[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb12-2>)lsaTree input = fix $ \result -> M.fromList $ do
[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb12-3>) (node, parents) <- M.toList input
[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb12-4>) let parentResults = fmap (result M.!) parents
[](https://reasonablypolymorphic.com/blog/solving-lcsa/<#cb12-5>) ...

请注意，我们如何使用 fix 来绑定最终计算的最终结果。然后，我们可以通过在 result 中查找它们来追踪指针——即使它尚未“计算”。谁关心计算机按什么顺序执行它。为什么这是我需要指定的东西？

无论如何。实现 LSA 的确切细节对于这篇博文的其余部分来说并不是特别重要。如果你有兴趣，你可以看看 PR，它非常小。

将它们联系在一起

有了我的 LSA 树，我现在准备回去解决原来的问题，即弄清楚在哪里插入 let 绑定。现在很容易了。给定原始程序图，找到每个节点的 LSA。 LSA 是你应该插入 let 绑定的地方。

因此，给定节点到其 LSA 的映射，反转该映射并取回节点到将其作为 LSA 的后代的映射。现在，当你去内联一个节点时，只需在这个映射中查找所有内容并首先内联它。

事实证明这是一个非常优雅的解决方案。它是我的可怕的临时实现的三分之一，并且以图中节点数的线性时间运行。总而言之，非常好。

人们会问我，我怎么会有这么多好主意。我喜欢这个故事的是，它非常典型地反映了我实际“有” “好” 主意的方式。我想起了运气眷顾有准备的头脑这一事实。细心的读者会注意到，此过程没有是由于我的才华。我碰巧认识了 Vikrem，他是个天才。我们一起拉了一些古老的图论琴弦，并记住了一个事实，有人认为重要的事情要教给我们。这实际上不是正确的路径，但它引导我们到 stackoverflow，在那里有人链接到了一篇相关的论文。我使用其他人完成了繁重工作的库实现了这篇论文，并使用我沿途在某个地方学到的这个打结技巧简化了实现。

另外，我真的很高兴这个解决方案来自于尝试逆向工程相关的图论搜索词。也许这是这里真正的信息。