《Build Systems à la Carte: Theory and Practice》
The following article is from 工业聚 Author 工业聚
0、前言
本文主要分为四个部分，在第一部分我们简要描述论文的主题，第二部分讲一下我如何逐渐意识到这篇论文是有巨大启发意义的，第三部分则尝试用 TypeScript 复刻论文里的几个代码案例，并列举现存的几个项目的 builds systems 特征。第四部分进行总结。
1、论文介绍
今天分享的论文是《Build Systems à la Carte: Theory and Practice》[1]，如果不严谨地翻译为中文，大致是《构建系统菜谱：理论与实践》。
它的三位作者分别是 Andrey Mokhov，Neil Mitchell 和 Simon Peyton Jones。其中的 Simon Peyton Jones 是大名鼎鼎的 Haskell 编译器 GHC 的核心开发者。
在这篇论文里，他们挑战了一个难啃的骨头——构建系统。他们描述构建系统时这样说：
构建系统是令人敬畏的，可怕的--也是不受喜爱的。
Build systems are awesome, terrifying – and unloved.
构建系统是令人惊讶的棘手问题。夸夸其谈很容易，而要做到精确则非常困难 Build systems are surprisingly tricky. It is easy to waffle, and remarkably hard to be precise
它们是软件生态系统中一个可悲的不受欢迎的部分，在很大程度上是达到目的的手段，而很少是关注的焦点。
They are a sadly unloved part of the software ecosystem, very much a means to an end, and seldom the focus of attention.
不管是前端的 Webpack/Rollup/Gulp，还是在非前端领域常见的 Make, Ninja, Bazel, Nix 或者 Shake 等构建工具，它们的配置文件都常常让开发者抓狂。最好是一次配置后，万年不用改动，远离它们。
在通常的认知里，构建系统做的事情是非常底层，并且非常 dirty 的活儿，很难有什么理论和抽象可言。
但是在《Build Systems à la Carte》这篇论文里，三位作者偏要找到一些规律。他们的目标是：
通过梳理现有的构建系统，我们可以重新组合它们的组件，从而使我们能够建立具有所需属性的新构建系统原型。
By teasing apart existing build systems, we can recombine their components, allowing us to prototype new build systems with desired properties.
通过梳理 Make 等构建工具包含的特征，他们试图找到所有构建系统的共性，甚至在论文中他们还常常以 Excel 软件作为案例，将 Excel 也视为构建系统的一种。最终他们成果是：
在本文中，我们给出了一个理解和比较构建系统的一般框架，其方式既抽象（省略细节）又精确（以Haskell代码的方式实现）。
In this paper we give a general framework in which to understand and compare build systems, in a way that is both abstract (omitting incidental detail) and yet precise (implemented as Haskell code).
他们提炼出了 general build system 的通用抽象表达，通过配置不同的 scheduler 和 rebuilder，分别对应 Make, Nix，Excel 等不同的构建系统的行为。大致表格如下：
横轴是 scheduler 算法，纵轴是 rebuilder 策略。如 Excel 在其中的位置就是，采用 dirty-bit 脏标志位的 rebuild 策略，采用 restarting 重新启动的 scheduler 调度算法的构建系统。
要看懂论文里的代码，需要具备一定水准的 Haskell 语言的知识。对大部分开发者来说，要立刻看懂可能有一定难度。强烈建议有兴趣的开发者，学习一下 Haskell 这类严肃的函数式语言，可以扩大我们对编程知识的接触面。许多编程实践相关的论文，里面的代码采用的正是函数式编程语言。
不过，阅读本文并不需要 Haskell 知识，只需具备基本的编程知识和前端开发经验即可。
即便如此，看到这里，部分读者心里也可能疑惑：“我一个前端，要看懂 build system 的论文做什么？它对前端有什么价值，对我又有什么帮助？”。
这种疑虑，我完全感同身受，我一开始也是这个想法，后来慢慢逐步地意识到这篇论文对前端开发的启发和价值。
2、三顾《Build Systems à la Carte》
2.1 一顾懵懂
去年(2020) 4 月份，我在推特上刷到《Build Systems à la Carte》，又看到有人说 Rust 作者强烈推荐此文。
我产生了好奇，点进论文一看究竟。然后在某个前端社群里，也分享了这篇论文，当时我对它的介绍大致如下：
一篇讲构建系统的实践和理论的 paper，对比了多个现存构建系统的实践模式，以及关于构建系统的抽象要件的特征。
有趣的是，里面提到了一点:
调度器可以取消过时的任务，一旦它的依赖关系是最新的，就重新启动它。 a scheduler can cancel the obsolete task and restart it once its dependencies are up-to-date.
原来不仅 react 这种组件化的 UI 库，需要 concurrent mode 的 scheduler 能力，buid system 也需要。
当代码文件发生变化，可能引起依赖关系发生变化，有一些任务的执行失去意义，需要被及时打断，重组。
react 组件的 suspense 打断和重新渲染，可以被视为在 render 过程中，组件的数据依赖发生变化，需要打断和重组。
不局限于构建系统或者 UI，里面的思路是更加普适一点的带依赖关系的 task 之间的调度如何表达的问题。
不时拿 Excel 里表格的依赖关系做例子，甚至斐波那契这种递归计算，都能用任务之间的依赖关系去看待，如 fibonacci(n) 可以看作依赖了 fibonacci(n - 1) 和 fibonacci(n - 2)。
有趣。对前端里的构建系统设计有启发价值。
以上。
还算大致准确地描绘了论文的概要，以及它对前端可能的启发价值，当时我也只觉得它里面的思想，对 webpack 等前端构建工具奏效，跟 react 有点类似，没觉得有其它特别值得重视的地方。
2.2、二顾犹疑
然后，今年(2021)3月份，在知乎上看到一个问题——如何看待 React 是种 Build System 的观点？[2]
原来有一位开发者 Chris Penner 在推特上说[3]，React 是一个特化的构建系统，组件的 (props, state, context) 是它的依赖，vdom/dom 是它的产出，当依赖变化，需要最小化重新构建视图，符合通用构建系统的要件定义。
Chris Penner 在该条推特评论里，甚至圈了《Build Systems à la Carte》的三位作者之一的 Neil Mitchell，问现在有没有基于 build-system 的 react 复刻。
“祖与占”去年(2020)8月份的知乎文章《React, Build System & Side Effects》[4]，也明确提到的 React 和 Build-System 的相似性。
当时我看到那个问题后，不以为意，觉得和我去年 4 月份对 build-system 的 React 相似性的认知差不多，并且感觉好像有点太强调 react 是 build-system 的说法。我当时在一个前端技术社群里，吐槽了一段：
我发现，人很容易被自己熟悉的事物束缚。熟悉 build system 的开发者，看到 react，说：react is a form of the build system.
熟悉 react 的开发者，看到 build system，可能又说：build system is a form of react.
假设放宽视野，重新审视 react 和 build system 之间的相似性，可能发现不同的视角。不一定是 react 是 build system，或 build system 是 react。也可能是 react 和 build system 分别是某个更宽泛和抽象的 task/solution 的应用。
它们都满足：1）频繁输出最终产物；2）多次输出的最终产物之间包含可重用部分；3）有很多 deps 依赖可触发 re-produce（re-render,re-build, ...etc）；4）在它们 produce 过程中，deps 可能已经发生变化，将触发新的 produce，即它们都需要 produce 过程可中断；5）produce 的各个环节，有可能可以独立完成，并且彼此之间重要性不等（可划分优先级）……
也就是说，是所有具备 produce/re-produce 的 task 可以有一个相似的 solution/pattern 解决。
用这种更 generalization 的视角，去学习 react/vue 或者其他事物，我们可以获得更容易泛化的知识。UI 开发中的 task 包含的问题性质，在其他领域如 build system，如 ray-tracer，也存在。
包括很多先学会了 monad 的 fp 开发者/爱好者，他们在某个阶段，视野所见皆 monad。
有时，那是别的模型，它们跟 monad 有一些内在关联，或许本质上是同构的，或对偶的。但它们未必是 monad，或者未必有需要把它们当作 monad 来看。
看到一个很强的表达能力的模型，我们可以知道它如何跟 monad 之间做转换，甚至如何把它包装为 monadic 的 api。但我觉得，有时候，很难说“它就是 monad”。
monoadic io 和 dialogue io 可以互相转换。但说 dialogue 是 monad，我个人感觉不到这里产生了什么新信息或者知识，更像是一种口语化的遣词。
暗示着我们大脑里倾向于把两者混合起来看待，暗示着我们对事物之间的边界的认识还不够清晰。
react team 说 hooks 是 algebraic-effects，而函数式社区的部分开发者则致力于强调 “hooks 是 a form of monad”
他们都对，也可以说，都不准确。
或许综合起来，能呈现更立体的认识。hooks 既可以映射到 algebraic-effects，也可以映射到 monad。algebraic-effects 和 free-monad 之间也存在某种映射关系。
hooks 是一个应用，monad/algebraic-effects 是 effect modeling 的抽象模式，它们都可以作为某个应用的底层抽象，也没啥毛病。
以上。
其实我现在仍然保持这个观点，并且为了写这篇文章，又尝试推进和展开这种看法。
2.1.1、探究 build-system 背后的领域
《Build Systems à la Carte》这篇论文，是三位作者升级 Haskell GHC 的构建系统时，所作的抽象升华。但那种根据依赖关系，在数据输入源变动后，按照不同的 Scheduler 和 Rebuilder 策略，做最小化构建的需求，实在太普遍了。
我们可以尝试列举几个场景，观察它们之间的相似性：
1、在构建系统中，它们的任务大致如下：
初次构建时，收集文件之间的依赖关系，当文件发生变化时，根据依赖关系，最大化复用上一次的构建产物，最小化重新构建。
2、在 React 中，它的一个任务大致如下：
在初次渲染后，收集各个组件的依赖关系，当通过 setState 等方式触发依赖的数据源更新时，根据依赖关系找到受影响的组件，最小化 re-render，最大化复用上一次的 render 结果，通过 diff/patch 最小化应用到 dom 视图中。
3、在 Compiler 中，它的任务序列大致如下：
以 TypeScript 作者 Anders Hejlsberg 在某次技术分享中的演示作为例[5]。
Anders 列出了 Compiler 的几个基本流程，处于编译器前端的 Lexer，Parser 和 Type-Checker，和处于编译器后端的 Code-Generator 和 Emitter 等。
其中 Parser 会将 Lexer 解析的 Tokens 根据语法规则，构建出 Abstract Syntax Tree，即抽象语法树（上图红色方块）。当某个代码源文件被编辑时，无脑全盘重新编译，效率太低。特别是对代码编辑器/IDE 来说，尽可能复用上一次的解析产物是很有意义的。
incremental parser 是一种能够以增量方式进行语法分析的设备，避免在每次修改后对程序进行完全的重新解析
An incremental parser is a device which is able to perform syntax analysis in an incremental way, avoiding complete reparsing of a program after each modification
采用 incremental parsing 策略，根据语法分析得到的依赖关系，尝试最大化复用，最小化解析。
4、在 ray-tracing 光线追踪中，也常常有复用上次计算结果的需求。
比如在论文《Incremental Ray Tracing》[6]中，作者们写道：
我们开发了一种减少光线追踪时间的方法，对于固定视角的动态图像序列，只重新计算或更新图像的变化部分。
We have developed a method to reduce the ray tracing time that recomputes or updates only the changed parts of the image for a fixed viewpoint for a dynamic sequence of images.
从这几个例子，我们可以看到共性所在。它们都属于 incremental computation 的范畴。Wiki 词条[7]里对增量计算的描述是：
增量计算，是一种软件特性，每当一项数据发生变化时，它试图通过只重新计算那些依赖于变化的数据的输出来节省时间。
Incremental computing, also known as incremental computation, is a software feature which, whenever a piece of data changes, attempts to save time by only recomputing those outputs which depend on the changed data.
上面的表述，偏向一种功能实现的角度。在论文《Fungi: Typed incremental computation with names》[8]中的描述，我个人觉得更贴近技术要点的角度：
在许多软件系统中，一个固定的算法在一系列增量变化的输入（Inp1, Inp2, ...）上反复运行，产生一系列增量变化的输出（Out1, Out2, ...）。
In many software systems, a fixed algorithm runs repeatedly over a series of incrementally changing inputs (Inp1, Inp2, . . .), producing a series of incrementally changing outputs (Out1, Out2, . . .).
这个表述提炼了几个关键要素：
我们很容易可以在 React/Build-Systems 里找到它们的对应。比如在 react 里：
1）React-DOM 里 virtual-dom -> dom 的渲染算法
2) setState 等驱动的 (state, props, context) 变化
3) React-DOM 所作的 diff/patch 更新产物
在 Incremental computation 的 wiki 词条中，还列举了增量计算的应用场景。
我们可以看到，它里面恰好也包含《Build Systems à la Carte》论文里提到的 build-system 和 Spreadsheets/Excel，以及前面列举的 GUIs，Graph 等场景。
我们至此可以更充分地回答《Build Systems à la Carte》提供的 general build-system 抽象和 react 等事物的关系。
三位作者从 build-system 任务出发，做了抽象的提取和升华，使之可以覆盖 Spreadsheets/Excel，乃至 fibonacci 这种普通函数的高度。作为一种 general framework，它其实已经有点超出了 build-system 的范畴，进入 Incremental computation 的层面。只是还带着它出发时所在应用领域的概念和命名痕迹。
如果三位作者是从 react 出发，或许他们会称之为 general react framework 也不一定。
在论文的 9.2 Self-adjusting Computation 一节，作者们也提到了跟增量计算相关的技术：
很多研究都致力于为 Self-adjusting Computation 寻找有效的数据结构和算法，有一些开源的实现，例如Jane Street（2015）的INCREMENTAL。我们计划在未来的工作中研究这些见解如何被构建系统所利用。
A lot of research has been dedicated to finding efficient data structures and algorithms for self-adjusting computations, with a few open-source implementations, e.g. INCREMENTAL by Jane Street (2015). We plan to investigate how these insights can be utilised by build systems as future work
并表示后续可能从中挖掘一下构建系统的可优化空间。
在论文的 9.3 Memoization 一节，作者们又做了一个展望：
Self-adjusting computation、memoization 和 build systems 是有内在相关的主题，这就提出了一个问题：是否有一个潜在的共同抽象等待我们去发现。
Self-adjusting computation, memoization and build systems are inherently related topics, which poses the question of whether there is an underlying common abstraction waiting to be discovered.
因此，不是 react 是 build system，或者 build-system 是 react。而是 react 和 build system 都属于 Incremental Computation 的应用场景。
尽管如此，这篇文章后续还是用 build system model 代表论文中描述的 Incremental Computation 实践模式，避免在遣词上跟论文有太大出入。
在第二次回顾《Build Systems à la Carte》时，用一个更高的角度，理清了各个事物之间的关系，我当时感到满意。但这种认识，仍然停留在纯知识性的、纯概念性的层面，若说能对编程实践，有什么实质帮助，倒也谈不上，顶多是在技术社群里作为新的谈资。
直到第三次回顾《Build Systems à la Carte》。
2.3、三顾惊醒
在今年（2021）4月底，我尝试做一个思想实验，在脑海里构思实现 lowcode 平台的新思路，琢磨着琢磨着，酝酿出一种设计。
在咀嚼和推演的过程中，我无意中发现，它跟 Excel 有点像，只是 lowcode 里的 UI Block 不是长得像格子，而是各有各的样式和布局。众所周知，Excel 从某个层面也属于 lowcode，它只需要配合少量 Excel 公式这种非图灵完备的 DSL 表达式，就可以完成显著的表格功能，而不必通过专业程序员。
我感到很有趣，react 是一个前端 view framework 视图框架，说它有 build-system 特征也就罢了，基于 react 设计一个 lowcode 平台，也有 build-system 特征。
我于是重新翻看《Build Systems à la Carte》，它里面是 Haskell 代码。我一般不会将 Haskell 代码真的应用于前端，往往是选择用 JS/TS 语言按照相似思路，做重新实现。在之前，我并不预期它能用在前端，因此我是用 Haskell 语言的心智模型去理解里面的 Haskell 代码。
但这一次，我想看看里面的表达 Excel 的 Haskell 代码，能不能用 TypeScript 表达，并扩展成可用的 lowcode 平台的核心底层。代码翻译过程，除了损失一些抽象精度和表达能力以外，并没有实质困难。
我很快用 TypeScript 复刻了论文里简单的 Excel 代码案例，突然惊讶地发现，这个 API 太像 Facebook 在去年(2020) 5 月份在 ReactEurope 里发布的 Recoil[9]，一个 React 的 State Management Library。
如果说，React 只是概念上表现为 build-system 特征，但在代码上不容易看出来。那 Recoil 不仅概念上像，连 API 这种代码细节部分都如出一辙。
后来我忍不住，给 Recoil 提了一个 Issue[10]，问 Is Recoil a build-system?
我想知道，这是一种巧合，还是他们受到了《Build Systems à la Carte》的启发，才开发了 Recoil。可惜，截止到目前，还未得到回复。
在做代码呈现之前，我想先叙述一下，当我发觉 Recoil 也有 build-system 或者说 incremental computation 特征时，我的感受和体验。
今天分享的论文的全称是：
《Build Systems à la Carte: Theory and Practice》
Theory and Practice，即理论和实践。在花了一年多之后，通过 lowcode -> excel -> recoil，才终于从理论层面的理解，走向了实践层面的理解。
当时我很兴奋地在一个技术社群，分享了我的发现：
最近在思考 low code 技术方案设计时，突然对「构建系统菜谱」那篇文献，有了新的理解。
然后发现 recoil 的机制，跟里面的描述很相像。不仅如此，从里面的广义构建系统来看，excel 也属于构建系统。当然，在这个意义上 react 也属于。
这意味着什么？
意味着 state, view, lowcode platform 全部都是构建系统的范畴，可以由相同的机制处理。
意味着，recoil 或许可以脱离 react 独立出来，甚至构建新的 react framework。
《Build Systems à la Carte: Theory and Practice》启发价值很大，不管写状态管理，还是 view library 还是 lowcode/nocode，都有帮助。
可以在不同阶段多读几遍。
尝试解释一下，它为什么有启发价值，或者为什么函数式编程对同一问题的思路，总是富有启发价值。
因为 pure/immutable 消除了捷径，不能靠 mutable/io 等脏活儿把问题缝补出来。
只能靠正确的 abstraction 对问题进行有效建模。
相当于清洗了某个任务的解决方案，找到了它更接近本质的表达。
然后我们用不用函数式，再说咯，我们已经比之前更抓住了问题的关键了。
recoil 和 redux 类似，作者们可能知道、也可能不知道它在函数式文献里的对应关系，凭借着对 pure/immutable 的坚持，摸索出来了。
但这个不自觉的摸索，在某些地方容易走歪。如果提前知道要点，再出发，可以走得更稳。
看这篇文章，需要一定的 haskell 知识，从类型和代码示例里，看到实践指导。只从自然语言层面做方法论理解，不容易 get 到具体代码设计思路。
当然，现在只是发现 recoil 可能有一些函数式设计的理念支撑。或许其它状态管理库也有理论支撑，只是还没被意识到。
意识到之后，我们得到了技术调研的优先级，如果认可上述支撑的价值，优先深入考察 recoil。用不用，又是另外的话题。
对 vue 用同样的视角看得足够久，也能找到很多理论支撑。
什么东西看久了，都像一个 category。
以上。
优秀的论文，或许总是需要在不同时期多读几遍，才能更充分地理解它的意义。
《Build Systems à la Carte》启发了我们看到 incremental computation 在前端开发里的普遍性，从 Parser，Build-Systems 这种底层工具，到State-Management，View-Management 这种运行时的库和框架，再到Lowcode/Nocode 这种产品实现层面的技术设计，都能找到应用场景。
并且，《Build Systems à la Carte》还提供了可运行的代码实现。我们可以尝试用 TypeScript 粗略地复刻里面的代码，让我们能在技术实现层面有更直接的体验和掌握。
3、 Build systems model 的代码实践
说了这么久 Build Systems 的故事，终于到了代码环节。前面我们展开了一些来龙去脉和复杂背景，可能吓到了部分读者，让他们觉得这太高深了，不是我现在能掌握的。
或许这是一种误解哦，《Build Systems à la Carte》里给出的核心代码，比我们想象的要少很多。SPJ 在 2018 年做了一次相关的技术分享[11]：
里面就强调了，Its' only a model。它只是一个模型，几十行 Hasekll 代码就演示出来了。真实的 build systems 包含的代码多了去了，并且这个模型，也没有涉及 Parallelism, Failure and recovery 等功能。
我们可以把它理解成一种函数式的设计模式，用来表达 incremental computation 的某种实现思路。
看到这里，可能部分读者心里会嘀咕：这么少的代码，却写了这么长的论文，说了这么复杂的背景和故事，是不是故弄玄虚？
其实不是的，能从代码量庞大无比的多个 build-systems 工具中，提炼出几十行代码，并且论证不同的 build-systems 是这几十行代码里的几个概念的不同组织方式。这是非常困难，非常值得称道的工作。
此外，越是通用的，越是接近本质的模型，就像数学公式和物理公式一样，它们可能在形式上越是富有简洁之美。
我们细细品味论文，并展开它的故事，是为了让我们更加愿意相信，短短的代码里，可能包含值得反复咀嚼的涵义。
《Build Systems à la Carte》发表后，引起了很多反响，得到了包括 Rust 作者在内的众多专业人士的赞誉和推荐。甚至，现在 google 输入 build systems 关键词，联想出来的第一个关联搜索就是 Build Systems à la Carte。
如果之前有人告诉我这个故事，可能不需要花一年多，三顾论文，直到现在才开始重视里面的代码，才开始思考它对我的前端工作的启发意义。
3.1、解析 Build System 抽象里的关键要素
在解析 build system 抽象时，我们会做简化，并不完全呈现论文里涉及到的所有要素，也不会聚焦论文里关心的多种 Scheduler 和 Rebuilder 的排列组合，虽然它是论文里的重点，不过我个人觉得对前端开发来说，不是启发性最大的部分。并且篇幅所限，详情还是需要亲自去阅读论文。
我们尝试提炼为 3 个要素：
1）store：保存 key-value map 和 build info 信息的持久化对象，可以理解为 react 里的 fiber tree/node 性质的事物
2）task： 描述一种计算过程的抽象任务的函数，可以依赖其它 task 的结果，是 user-defined 用户定义的部分，可以理解为 react component 性质的事物
3）build：用一组 tasks 将一个 store 里的 key-value map 更新到最新版本的函数，相当于 react 里的 ReactDOM.render(<View />, container)
我们分别来看三个要素的 Haskell 源代码和 TypeScript 源代码翻译。
Store 在论文里的类型定义如下：
存储和更新一些信息用的，TypeScript 粗略翻译为：
我们把 build info 的辅助信息也简化掉，只保留 key-value map 部分。
Task 在论文里的类型定义如下：
里面用到了 Hasekll 类型系统的高级特性，如 ConstraintKinds 和 Higher-Kinded Types 等，在 TypeScript 里不容易表达，好在它们主要服务于让代码更通用，我们可以损失代码的通用性，去得到更特化的版本。
重要的技术细节出来了，就是那个 Task 类型里的 fetch callback，它就是精髓所在。我们尝试解析一下它的思路。
从过去的实践经验中，已经可以总结增量计算的一种实现方式，如 wiki 里的介绍：
增量计算可以通过建立一个可能需要重新计算的所有数据元素的依赖图，以及它们的依赖关系来实现。
Incremental computation can be achieved by building a dependency graph of all the data elements that may need to be recalculated, and their dependencies.
我们要构筑的 dependency graph，是由一个个 vertex 或者叫 node 构成。
《Build Systems à la Carte》里提供的思路就是，我们为 graph 的 node 分配一个 key，然后用 graph 的 edge 链接表达依赖关系，每个 node 包含自己的 value。当它的依赖发生变化时，能通过 rebuild 将所有 node 更新到最新版本。
如上，假设每个圆圈都是一个 node，每个箭头表示被谁依赖(consumer)，红圈表示 changed 变化了，绿圈表示 latest 最新状态。
那么，当 key-0 变化后，我们就可以沿着箭头去更新 key-1, key4，然后 key-1 更新后，它又沿着箭头去更新 key-2，最终整个 graph 都处于 latest 状态。
分配 key 的目的，则是为了把所有 node 都存储到 store 里，还记得前面的 store 定义吗？它里面包含的 key-value map 就是储存 graph 里的所有 node 的 value 和当前依赖关系。
只是分配了 key 还不够，每个 node 的更新方式可能是不一样的，可能是用户定义的，甚至它依赖哪些 node 也是用户定义的。毕竟这个抽象的应用场景，如 build-systems 是处理开发者编写的 makefile, webpack.config.js 等配置，如 react 是处理开发者编写的 react component 等组件。
因此，我们还要为每个 node 分配 tasks，由开发者提供。
这就是 Tasks 类型的设计目的，它也是一个函数，从 key 到 task | null。
重新命名这个函数，可以叫 getTaskByKey(key) -> Task | null。
有了这个函数，我们就可以依次遍历 store 里的 keys，获取它对应的 task，如果 task 存在，就调用 task 拿到最新的 return value，作为当前 key 对应的 node 的 latest value 最新值。如果没有拿到 task，拿到 null，说明这个 node 没有依赖，它是 input 输入源。比如上图里的 key-0, key-3 和 key-7 对应的节点。
我们用论文里的 Excel 案例感受一下，假设有表格如下：
按照 Build-Systems 分配 key 的思路如下：
每个 Cell 格子就是 graph 里的 node，而 Cell Address 格子地址就是分配的 key，比如 A1/A2/B1/B2 等，。其中 Excel 公式，如 A1 + A2 和 B1 * 2 就是给每个 node/cell 分配的 Task 计算任务。
执行结果为：
我们用 build-systems 抽象，重新表达如下：
sprsh1 就是那个 Tasks 类型的 getTaskByKey 函数，表达了跟前面的公式一样的逻辑。
遇到 key 为 B1，返回一个 task 函数，表达 A1 + A2。
遇到 key 为 B2，返回一个 task 函数，表达 B1 * 2。
遇到其它 key（格子），返回 Nothing，说不用更新，直接沿用 store 里的 value 即可。
翻译成 TypeScript 代码的话，大概像这样：
如果是前端读者，看到上面的函数，应该会觉得其实很简单。
不就是每个 key 都可以自定义 task 函数，然后 task 函数里的 fetch callback 函数，可以用来获取这个 key 所以来的其它 key 的 value 嘛。
为什么不直接传递 store 参数进来？这样 store.get(key) 也能获取到 value。
为什么要通过 fetch 函数？
这是因为，如果传递 store 进去，那么 store.get(key) 获取的是当前的 key 对应的 value。它不一定是 latest 的，它的依赖可能已经发生变化，它可能也需要 rebuild 更新自己。所以，get(key) 或者 fetch(key) 其实还包含其它计算，比如检查 key 所对应的 node 的依赖是否发生变化，决定是否更新自己，还是复用 cache 等。
并且，传递 store 给 task，让 task 可以 store.set 和 store.delete 的话，将会破坏 graph 里 node 节点的数据一致性，我们需要保证所有 node 都根据依赖关系和它包含的 task 函数计算出 value。
为此，在 《Build Systems à la Carte》里，三位作者专门给出了 build-system 的 Correctness（正确性）的定义：
它的思路就是，如果 store 里的值都没变，再重复执行一次，拿到相同的结果，才说明 build-system 正确处理了依赖关系并更新了所有节点的值。
因此，并非暴露更多的控制权给 task 就意味着更好。很多时候，为了可预测，为了正确性，我们需要做更精细的代码行为的权限控制。
再来看另一个 fibonacci 函数的案例，论文里的 Haskell 代码如下：
fibonacci 作为 build system 看待时，它的 key 分配就是参数 n，其中 n 是数字，而非字符串。
build systems model 的 key 可以是任意的，不只是支持字符串，尽管字符串是很常用的 key 选择。实际上，任何可区分的对象都可以作为 key，后续我们可以看到更多不同的 key 选型。
当 n 小于 2 时，返回 Nothing，是指这个 node 节点没有额外的计算任务和依赖，没有 task，直接用 store.get(key) 里的值即可。
当 n 大于等于 2 时，返回一个 task 函数。在这个函数里，它通过 fetch callback 去获取了 n - 1 和 n - 2 这两个 key 的 latest 最新结果，然后相加，作为当前 node 节点的 latest 值。
翻译成 TypeScript 代码，大致如下：
Tasks 函数包含了所有 key 的计算方式及其依赖的其它节点的信息，然后有一个 store 储存了节点的信息，假设我们有个 build 函数（如上图的 busy），它可以根据 tasks 和 key，将一个 store 里的 key-value map 更新到最新版本。
当我们 store.set(key0, value) 后，再重复执行一次 build 函数，依赖 key0 的所有 node 的 value 又更新到最新版本了。
我们可以在 build 函数的内部实现里，决定如何做 scheduler，如何做 cache invalidation，决定要不要真的 rebuild 一个 node。
总的来说，我们可以将这个模式理解为，一个高级版的 memory 函数。
普通版 memory 通过记忆函数的整个 args 和 result，在下一次调用时，以 args 为 key 匹配 result，复用整个 result。如果不匹配，就重新计算出新的 result，再存入 args -> result 的 store 里。
这在小函数或者小数据量的情况下，挺好的。但在复杂函数或者复杂数据结构时，要么全盘复用，要么重新计算的选择，实在太简陋了。命中率和复用率不高。
因此，我们需要精细化 key 的分配，精细化 result 的存储。让 result 即便不能直接复用，也可以复用必要部分，只重新计算必要部分。
在这种意义上， build systems model 提供的设计模式，可以理解为：结构化的、精细化的 memory 技术。
在应用 build systems model 时，最关键的设计要点可能是：
1）我的 key 是什么？
2）我的 value 是什么？
3）我的 fetch callback 怎么设计？
其实，即便不知道 build systems model，在很多现实项目中，开发者们已经有意无意地使用了相关技术。
我们可以尝试以下，用 build systems 视角重新解读相关的现存项目里的 key, value 和 fetch callback 对应。
如此，既可以帮助我们理解 build systems model，也可以让我们用新的视角去审视那些项目，或许能挖掘出可能的优化空间。
3.2、现存项目里的 build systems 特征
3.2.1、Excel 作为 build systems
再次回顾以下，Excel 作为 build systems 来看，它的 key, value, store 和 task 分别是什么，来看 SPJ 技术分享里的一页 slide：
表格地址为 key，表格内容为 value，整个表格为 store，表格公式为 task。
在真正的 build systems 里则是，文件名为 key，文件内容为 value，文件系统为 store，用户配置为 task。
3.2.2、Recoil 作为 build systems
终于到了我们的 Recoil 了，Recoil 非常直截了当地呈现了上述 build-systems model，且看 recoil 官方文档里的代码。
在 selector 函数的 options.get 方法中，它的 get callback，就是 build systems model 里的 fetch callback。
由 atom/selector 函数返回的 RecoilState 对象作为 key，get(key) 返回 RecoilState 内部 latest 最新的 state 状态。
这不只是牵强附会的联想，实际上我们可以在 build systems model 的基础上，构筑 Recoil like 的 api，并能运行起来。
先定义 atom 函数及其类型：
再定义 selector 函数及其类型：
其中，get 方法的 get 参数类型，我们直接沿用 build systems model 里的 Fetch 类型，其 key 为 Atom 或 Selector，其 value 这里简化为 number，实际上 Recoil 的 fetch value type 是从 key 里面推导出来的。
然后我们用这个 recoil-like 的 api，重新描述前面的表格问题：
相比之前的版本，某种意义上代码看起来更加解耦了。这是因为，recoil 模式把 task 也编码到了 key 里。atom/selector 返回值是 key，同时它也定义了task。
因此，我们不需要把 task 代码都写到 tasks/getTaskByKey 的大函数里维护，我们只需要实现一个简单而通用的 tasks 函数即可：
如上，我们实现了通用的 tasks，里面不再包含具体的处理 B1/B2 的逻辑代码，它只包含解析和调度代码。从 key 匹配出 rule，如果是 atom，就用它的 default 封装成 task。如果是 selector，就用它的 get 方法作为 task。get 方法的 get callback，就是 build systems model 的 fetch callback 的简单封装。
最后我们把 recoil tasks 扔给底层的 build systems model 的 busy/build 函数。就实现了用通用 build systems model 去支撑 recoil 模式的目标。完整代码请见 Gist[14]。
Recoil 的实践模式，对应的是论文的 8.6 Key-dependent Value Types
依赖于键的值类型允许一个构建系统处理多种不同类型的值，其中任何特定值的类型都由键决定
Key-dependent value types allow a build system to work with multiple different types of values, where the type of any particular value is determined by the key
3.2.3、commonjs/AMD 作为 build systems
奇怪的地方出现了，commonjs 和 AMD 不是 module systems 吗？跟 build systems 有什么关联？
不必惊讶，没有乱入。
这是因为《Build Systems à la Carte》提供的 build systems model 是一个高度提炼的抽象，它能表达静态依赖和动态依赖相关的意图。而模块化问题，恰好也包含模块之间的依赖关系处理。
当我们有了更通用的模型后，再看处理具体领域的依赖关系的代码，很容易看到它各部分在通用模型里的对应。
比如这一段 Node.js 代码：
它表达的是动态依赖，根据环境切换 ./dev 和 ./prod 的依赖目标。在真正执行时，node.js 会包装这段代码，因此它真正运行的代码像这样：
美化后：
我们的代码被包装在一个函数里，其中 require 是第二个参数。
现在我们说，require callback 就是 build systems model 里那个 fetch callback。filepath 就是 key，module 产出就是 value。
module store 则在 require.cache 属性里，如此各个 build systems model 的关键要素被安排得明明白白。
相比 Excel 和传统 Build Systems，commonjs 这种处理模块化依赖的，通常只需要计算一次，然后把模块缓存起来，不再变化，直接复用。相当于一次性的 build systems，不容易被直观地发现它的 build systems 特征。
直到我们遇到 Hot Module Replacement，即在开发环境中所需的模块热替换。当一个模块源代码被编辑时，我们希望复用之前没变动的模块的构建结果，只更新变动的部分。这就进入了增量计算的领域。
HMR + Module 就表现为需要多次 rebuild 且只 rebuild 变化的 node 节点（在这里是代码源文件/模块）的 build systems 了。
因此，或许《Build Systems à la Carte》提供的 build systems model ，可以启发我们，从之前把模块热更新当作一个 ad-hoc 的额外事物，变成用更统一的视角去看待模块系统和模块热更新。
模块依赖解析和模块热更新，可以视为一个 build system 体系。在 dev 里 rebuild 一次以上，在 prod 里只 build 一次。当然，如果有需要，在 prod 里实现代码热更新，可能是一个不错的方向，很有现实意义。
至于 AMD/requirejs，它相当于在浏览器里实现类似 commonjs 的模块系统，不过它也有添加一些自己的设计，值得拿来展示以下。
requirejs 支持静态依赖和动态依赖两种模式，在《Build Systems à la Carte》里，对静态依赖和动态依赖，有一个非常精彩的分析，将它们映射到经典的 Appliative 和 Monad 结构中，其中 Applicative 表达静态依赖，Monad 表达动态依赖。感兴趣的同学，可以查阅该论文的 3.4 The Need for Polymorphism in Task 一节。
requirejs 的静态依赖写法如下：
第一个参数为依赖数组，里面包含依赖的 key（模块地址），然后第二个 factory 的参数，就是依赖数组的 keys 对应的 values（模块输出）。
它是静态的是因为，依赖数组提前固定，依赖结果作为参数传入。
同时，requirejs 也支持类似 commonjs 的模式：
require callback 回来了，这种模式是能支持动态依赖的，除非 library 本身对 require(key) 的 key 怎么写有要求，使得它无法发挥出动态能力。
这种静态依赖和动态依赖的区分，有助于我们理解静态依赖的 API 设计，和动态依赖的 API 设计的差别。
1）静态依赖：依赖的目标的 keys 提前确定，依赖的目标通过参数的方式传入
2）动态依赖：依赖的目标的 keys 可以不提前确定，可以根据获取的数据，根据条件进行 key 拼接或者跳过等，依赖的目标通过高阶函数 fetch callback 获取。
如上图所示，这种对比强调的是——高阶函数的表达能力。
静态的依赖，通过静态的参数传入。
动态的依赖，通过静态的高阶函数参数 fetch callback，动态地调用来获取。
放到 ES Modules 标准模块方案，我们一样可以看到上述特征：
上面的 import statement 是表达静态依赖的语法，我们提前配置好了 dep keys。
下面的 dynamic import 是表达动态依赖的写法，我们可以根据条件配置 dep key，甚至拼接 dep key（除非 webpack 等依赖静态分析的工具，限制这个表达能力）。import(key) 函数，就是那个 fetch callack 属性的事物。
通过 build systems model 视角，我们常常能在包含动态依赖的项目和模式中，发现 fetch callback 属性的事物。
3.2.4、Dependency Injection 作为 build systems
依赖注入[12]是实现控制反转[13]的一种技术实现，它也设计依赖关系的追踪，很显然，我们可以用 build systems model 重新审视它的构成，找出 DI 的 key, value, store 和 task。
不同的 DI 框架的 key 选型可能不尽相同，有的用 Symbol，有的用 class constructor，有的用 string 等等。
不同的 DI 的 fetch callback 的表现形式也不同，有的叫 inject，有的叫 autowire 等。
大部分 DI 框架都在尽可能让依赖注入过程无感，通过 decorator/anotation 等语法糖，通过 XML 等配置，通过各种方式尽可能减少复杂度。可以称之为隐式依赖获取。
在实现了 build systems model，我们几乎立即得到了一个显式依赖获取的 API。
fetch callback 的 key 可以是 symbol 或 class-constructor，其 value 则是 class-instance.
如上，依赖注入的 inject 的 fetch callback 类型的一种设计。
跟 Module System 一样，依赖注入往往也只 build 一次，而不像 react/recoil 那样，常常需要反复重新局部计算。可以视为 build systems model 的应用特例。
如果需要自行设计一个依赖注入框架，我们可以先实现基于 build systems model 的显式依赖获取的 API，然后再裹上 decorator/anotation 等语法糖。
4、总结
以上，我们比对了多个不同性质的系统里的 build systems model 要素，相信比之前更能把握 key, value store 和 fetch callback 等概念。
值得一提的是，fetch callback 并非唯一的 callback，它的主要作用是在 get/fetch 层面去追踪依赖，如果我们想要追踪其它操作，如 set/write 操作，我们可以配置不同功能目标的 calblack。
正如在论文的第 9.1 一节的末尾说的：
在我们的模型中，捕捉任意写入的一种方法是将一个回调获取转换为两个回调，例如 read 和 write，允许我们分别跟踪读和写的情况
One way of capturing arbitrary writes in our model is to switch from one callback fetch to two callbacks, say read and write, allowing us to track both reads and writes separately
因此，其实 build systems model 也可以看作一个特例，看作只有 get/fetch 操作被追踪的依赖关系有向图。
build system model 是可拓展的，当我们需要追踪多个不同操作时，只要增加不同的高阶函数参数(callbacks) 即可。
比如 recoil 的 selector 就用到了 set callback 的部分：
作为 Haskell 编译器 GHC 的核心开发，SPJ 几乎花了 30 多年的时间投入在这个领域。对于推广 Haskell 自是不留余力，在《Build Systems à la Carte》的 7.1 Haskell as a Design Language 一节，作者们表达了他们的一些经验和心得，值得摘录一下。
用Haskell编写可执行原型的纪律对我们的思维产生了深刻的影响。它迫使错误的概念及早浮现。它要求我们对副作用有明确的认识。它给了我们巨大的动力去设计那些具有简单类型和可解释目的的抽象概念。
The discipline of writing executable prototypes in Haskell had a profound effect on our thinking. It forced misconceptions to surface early. It required us to be explicit about side effects. It gave us a huge incentive to design abstractions that had simple types and an explicable purpose.
作者们认为，用 Haskell 作为设计语言，显著提升了他们对问题的洞察能力。
还值得注意的是，我们需要一种相当有表现力的语言来忠实地表达在这种环境下似乎很自然的抽象概念。
It is also worth noting that we needed a rather expressive language to faithfully express the abstractions that seem natural in this setting.
他们还强调了语言的表达能力的重要性，因为：
我们的模型后来被翻译成Rust（Gandhi，2018）和Kotlin（Estevez & Shetty，2019），在这两种情况下，由于语言的特定限制，精确度有所下降。
Our models have since been translated to Rust (Gandhi, 2018) and Kotlin (Estevez & Shetty,2019), and in both cases there was a loss of precision due to language-specific limitations
他们的模型，在翻译到 Rust 和 Kotlin 时，都因为这些语言在表达能力上的不足，有损精确度。正如前面我们用 TypeScript 翻译时所做的简化。
这些强大的、模块化的抽象，最终构成了本文概念结构的一部分，在项目的后期出现，因为我们反复审查、重新设计和重构了我们的可执行原型。很难相信，如果没有Haskell作为一种设计语言的支持，我们可以开发出这些东西。
These powerful and modular abstractions, which ultimately formed part of the conceptual structure of the paper, emerged fairly late in the project as we repeatedly reviewed, redesigned, and refactored our executable prototypes.
It is hard to believe that we could have developed them without the support of Haskell as a design language.
他们甚至认为，如果不是用 Haskell，他们可能搞不定这篇论文。
我个人觉得，这正是在工业界里的开发者，也值得去看学术界的论文的一个原因。大部分工业界流行的语言，出于实用目的，在抽象和表达能力上，相较 Haskell/Agda 等学术气息更浓厚的语言，是更弱的。
并且，软件工程师的视角，有时可能太具体，不容易看到更普适的抽象。
通过阅读 FP 或 PLT 领域的论文及其实践，我们有机会获得不同的视角，激发一些新的灵感和思路，也是很有价值的。
希望大家有时间和精力，可以尝试阅读《Build Systems à la Carte: Theory and Practice》，并能有所得。
参考资料：
[1] Build Systems à la Carte: Theory and Practice
https://www.microsoft.com/en-us/research/uploads/prod/2020/04/build-systems-jfp.pdf
[2] 如何看待 React 是种 Build System 的观点？
https://www.zhihu.com/question/450912386
[3] Chris Penner: React is just a specialized composable build system!
https://twitter.com/chrislpenner/status/1374159447577161731
[4] 祖与占《React, Build System & Side Effects》
https://zhuanlan.zhihu.com/p/192914973
[5] Anders Hejlsberg on Modern Compiler Construction
https://www.youtube.com/watch?v=wSdV1M7n4gQ
[6] Incremental Ray Tracing
https://link.springer.com/chapter/10.1007/978-3-662-09287-3_2
[7] Wikipedia: Incremental computing
https://en.wikipedia.org/wiki/Incremental_computing
[8] Fungi: Typed incremental computation with names
https://arxiv.org/pdf/1808.07826.pdf
[9] Recoil is an experimental state management library for React apps.
https://github.com/facebookexperimental/Recoil
[10] Recoil Issue 1020
https://github.com/facebookexperimental/Recoil/issues/1020
[11] Build Systems à la Carte (Distinguished Paper), presented by Simon Peyton Jones
https://www.youtube.com/watch?v=BQVT6wiwCxM
[12] Dependency injection
https://en.wikipedia.org/wiki/Dependency_injection
[13] Inversion of control
https://en.wikipedia.org/wiki/Inversion_of_control
[14] recoil-via-build-system.ts
https://gist.github.com/Lucifier129/4d07491e90c84fbe5afabd8c737fc350