介绍 Incremental

# 介绍 Incremental 我很高兴地宣布 **Incremental** 库的发布，这是一个用于构建 *自调整计算* 的强大库，即当输入发生变化时能够高效更新的计算。 简单来说，你可以把自调整计算想象成一个高级的电子表格。在电子表格中，每个单元格要么包含简单数据，要么包含一个公式，描述该单元格的值应如何从其他单元格的值推导出来。总体上，这构成了一种图结构的计算，而 Excel 的关键优化之一是：当某些单元格发生变化时，Excel 仅重新计算图中依赖于这些变化单元格的部分。 自调整计算（SAC）与电子表格的不同之处在于其动态性。SAC 中计算图的结构可以在运行时根据输入数据的变化而改变。 这种动态性带来了很大的灵活性，可以以不同的方式使用。以下是一些例子。 **在线组合算法。** Incremental 基于 Umut Acar 等人关于自调整计算的工作（正是这个术语的来源），他们主要致力于为各种组合算法构建高效的在线版本。在许多情况下，他们可以通过对全量算法进行简单的增量式化，来匹配定制化在线算法的渐近复杂度。 **增量式 GUI 构建。** 建模 GUI 应用程序的一种简单自然的方式是，将显示结构化为一个函数，该函数从更抽象的数据模型生成视图。每次迭代都从头构建视图的函数虽然简单，但代价过高。但如果能编写一个生成增量式计算的函数，就能得到既简单又高效的解决方案。我们在一些 UI 中使用了这种技术，效果很好。 这可能会让你想起函数响应式编程（FRP）在 Elm 等语言中用于构建 GUI 的方式。SAC 和 FRP 具有不同的语义——FRP 主要关注时间类计算，而 SAC 主要优化 DAG 结构计算——但它们在实现层面密切相关。你可以在这篇文章中看到我对包含 FRP 和 SAC 的更广泛概念景观的描述。 **可配置计算。** 一个来自我们自身工作的例子是风险计算。计算投资组合的风险指标涉及组合来自复杂且相互依赖的模型集合的数据。每个模型既依赖于市场的实时数据，也依赖于用户确定的配置。配置变更可能只是调整一个系数，也可能改变计算的整体结构，例如更改某个模型使用的因子列表。Incremental 允许你构建一个计算，该计算能够在统一框架下高效地响应简单数据变化以及更具结构性的配置变化。 ## 初识 Incremental 很难用几行代码给出一个令人信服的 Incremental 实战示例，因为 Incremental 真正有用之处在于它如何帮助你构建大型复杂计算。不过，小例子可以让你对库的工作原理有所了解。 为此，让我们看几个小例子。首先，我们需要实例化 Incremental 函子。 ``` open Core.Std module Inc = Incremental_lib.Incremental.Make () ``` 这样生成的每个实例都是自己独立的计算世界。Incremental 函子是生成式的，意味着每次应用它都会产生新的类型，从而防止不同增量世界中的值意外混合。 Incremental 计算始终从其 *变量* 开始。对变量的修改是将输入数据的更新传达给 Incremental 的方式。 让我们写下几个对应长方体尺寸的变量。 ``` module Var = Inc.Var (* 长方体的尺寸 *) let width_v = Var.create 3. let depth_v = Var.create 5. let height_v = Var.create 4. ``` 我们可以使用 `Var.watch` 来获取与每个变量相关联的（平凡）增量计算。 ``` let width = Var.watch width_v let depth = Var.watch depth_v let height = Var.watch height_v ``` 以下是对棱柱底面积和体积的增量计算。 ``` let base_area = Inc.map2 width depth ~f:( *. ) let volume = Inc.map2 base_area height ~f:( *. ) ``` 为了从增量计算中获取信息，我们需要通过创建 *观察者* 节点来明确标记我们想要数据的节点。由于框架知道哪些节点被观察，它可以追踪计算的哪些部分对结果仍然是必要的。 ``` let base_area_obs = Inc.observe base_area let volume_obs = Inc.observe volume ``` 为了强制计算运行，我们需要显式调用 `Inc.stabilize`。以下代码使用 stabilize 来运行计算，然后从观察者中获取信息。 ``` let () = let v = Inc.Observer.value_exn in let display s = printf "%20s: base area: %F; volume: %F\n" s (v base_area_obs) (v volume_obs) in Inc.stabilize (); display "1st stabilize"; Var.set height_v 10.; display "after set height"; Inc.stabilize (); display "2nd stabilize" ``` 如果我们运行它，会看到以下输出： ``` 1st stabilize: base area: 25.; volume: 125. after set height: base area: 25.; volume: 125. 2nd stabilize: base area: 25.; volume: 250. ``` 注意，仅仅设置高度不足以改变观察到的值；我们需要一次 stabilization 才能实现这一点。 这是一个相当简单的计算，当然没有太多可增量化的东西。让我们尝试一个稍微复杂一点的例子：一个用于合并一个增量数组的函数，使用某种可交换且可结合的运算符，如加法或最大值。 ``` let rec merge ar ~f = if Array.length ar <= 1 then ar.(0) else let len = Array.length ar in let len' = len / 2 + len % 2 in let ar' = Array.init len' ~f:(fun i -> if i * 2 + 1 >= len then ar.(i*2) else Inc.map2 ar.(i*2) ar.(i*2+1) ~f) in merge ar' ~f;; ``` 由于这使用了依赖图的二叉树结构，更新一个元素的复杂度为 `log(n)`，其中 `n` 是数组的大小。我们可以用它来计算平均值： ``` let average ar = let sum = merge ar ~f:(+.) in Inc.map sum ~f:(fun s -> s /. float (Array.length ar)) ``` 这样可行，但我们可以做得更好，至少在性能方面，如果我们的合并操作有逆操作的话。在这种情况下，维护和原则上可以在常数时间内完成，方法是先移除旧值，再加入新值。Incremental 有一个函数可以利用这种结构。 ``` let sum ar = Inc.unordered_array_fold ~f:(+.) ~f_inverse:(-.) ar;; ``` 现在，假设我们想做更动态一点的事情：具体来说，如果我们想要计算给定数组的前缀的平均值？为此，我们需要使用 bind 函数，它允许我们在增量计算内部生成新的增量节点。 ``` let average_of_prefix ar length = Inc.bind length (fun length -> average (Array.init length ~f:(fun i -> ar.(i)))) ``` 这个函数的类型是 `float Inc.t array -> int Inc.t -> float Inc.t`，因此前缀的长度是增量计算中完全合格的一部分。因此，该计算的依赖结构会动态变化，例如，如果 `length` 的值是 `7`，那么计算仅依赖于 `length` 和数组的前 `7` 个元素。 希望这能让你对 Incremental 是什么有一个足够的认识，开始思考它可能在你哪些地方有用。请注意，Incremental 的开销并非微不足道——在我的笔记本电脑上，触发一个节点大约需要 30 纳秒，这远远超过例如对数字求和。Incremental 在以下情况下往往有用：放入单个节点的计算相对于该开销来说是大的，或者计算图相对于需要重新计算的子图来说是大的。我们的经验是，在这个范围内有很多应用程序可以从 Incremental 中受益。 Yaron Minsky 于 2002 年加入 Jane Street，并声称拥有说服公司开始使用 OCaml 的“可疑”荣誉。