Livelymerge 中的对象模型

# Livelymerge 中的对象模型 来源：https://www.inkandswitch.com/livelymerge/notebook/lm-03/ ## 引言 在 *Livelymerge* 项目中，Dan Ingalls、Peter Van Hardenberg 和我（Alex Warth）正在探索将 Automerge 文档用作程序堆（heap）所带来的机遇与挑战。其中一些机遇包括： - **持久性：** 程序的堆是持久化的，类似于 Smalltalk 的镜像（image）。如果你今天关闭程序，两周后再打开，每个对象都会和你离开时一模一样。 - **协作：** 在多用户场景下，所有参与者共享同一个堆，这使其成为一种有趣的协作媒介。 一些挑战： - **一致性：** - 当有多个用户时，谁来负责运行哪些“进程”？例如，如果程序实现了一个模拟，并且有多个用户都在运行该代码，那么某些副作用可能会被执行两次或更多次，这是不可取的。 - 是否有可能以某种方式表示程序的状态，使得当多个用户对重叠对象集合进行交互而导致自动合并时，程序的不变量（invariants）仍然得以保持？ - **性能：** 我们能否让程序运行得足够快，以满足真实使用需求？ - **对长时间运行程序的支持：** 我们希望支持可以“居住其中”的程序——也就是 Dan 所擅长的这类系统，比如 Squeak（https://squeak.org/）和 LivelyKernel（https://www.lively-kernel.org/）。但这些程序会运行无限长的时间，因此它们对应的 Automerge 文档会积累非常大量的变更。我们能实现这一点吗？如果不能（鉴于 Automerge 当前的实现），是否可以对 AM（无论是计划中的还是其他方式）进行一些修改，使其可行？ 这篇笔记描述了为此项目设计并实现的对象模型。它会自动地在程序的 Automerge 文档与数据之间进行序列化和反序列化。你很快就会明白这意味着什么以及为什么需要它。但首先…… ## 为什么叫“Lively”？ 我们对这个项目最感兴趣的程序是像 Squeak 和 Lively Kernel 那样自给自足（self-sustaining）的系统。我们正在创建一个同类的新系统，但这一次我们从一开始就将其设计为“多用户”和协作式的，充分利用 Automerge 提供的好处。 Dan 的 Lively Kernel（LK）是一个类似 Squeak 的系统，完全用 Javascript 编写，并运行在网页浏览器中。系统的用户可以在运行过程中召唤出一个 Smalltalk 风格的*浏览器（browser）*，并修改系统的任何方面（例如，文本编辑的工作方式，甚至是浏览器本身！）。用户更改的效果会立即生效。 作为 Livelymerge 项目的一部分，Dan 编写了一个新的类 LK 系统，其堆以 Automerge 文档的形式表示。它包含一个基于 Morphic（https://rmod-files.lille.inria.fr/FreeBooks/CollectiveNBlueBook/morphic.final.pdf）的图形用户界面、可编辑的文本区域，甚至还有一个 Smalltalk 风格的浏览器。系统中的一切都是从头编写的（图形最终基于 HTML canvas），而且代码可以从系统内部查看和编辑。这意味着用户可以对系统进行根本性的更改，而在多用户场景下，这些更改会应用到所有参与者。 （边注：很长一段时间以来，我一直希望我在 Ink & Switch 的同事们能够亲身体验这种自给自足的系统，而这个项目正好是一个很好的借口来实现这一点。） ## LM 的对象模型 LM 程序是用普通 JavaScript 编写的：对象和数组字面量、顶层声明、闭包，甚至是 `class` 语法，都按你预期的方式工作。不同之处在于对象存储的位置：它们的状态被表示在程序关联的 Automerge 文档中，而不是 JS 堆中。这意味着我们的对象天生就支持持久化和协作。 该实现有两个主要组成部分： - 一个**对象模型**——即本篇笔记的主题——由*全局对象*（相当于 JavaScript 的 `globalThis`，也是堆的根）以及一组用于在堆中创建新对象、数组和函数的小型原语组成。 - 一个**转译器（transpiler）**，它将普通 JavaScript 重写为使用这些原语的形式，因此你永远不需要自己调用它们。（转译器可能值得单独写一篇实验室笔记；在这里我主要讨论其底层的对象模型。） 这里有一个简单的例子来帮助我们开始： ``` f = (x, y) => x * y + 2; f(5, 8); // 计算结果为 42 ``` 到目前为止，这看起来还相当“普通”，但其中有一些有趣的事情在发生。因为 `f` 是一个全局变量，它存在于程序的堆中——也就是说，存在于 Automerge 文档中。例如，假设你和我正在不同的计算机上共同处理这个程序。如果我执行了第一条语句，`f` 就会存储到*我们的*堆中。这意味着如果你**在没有执行第一条语句的情况下**执行第二条语句，你仍然会得到预期结果（`42`）。 下面是另一个例子——我们在演示时，这个例子通常会引来一片“哦——”： ``` makeCounter = () => { let count = 0; return () => ++count; }; counter = makeCounter(); counter(); // 计算结果为 1 counter(); // 计算结果为 2 ``` 到目前为止，还是常规 JavaScript：`counter` 是一个闭包，每次调用都会递增它捕获的 `count` 变量。现在到了“哦——”的部分：如果*你*在你的电脑上执行 `counter()`，你会得到 `3`。被捕获的 `count` 并不存在于*我的* JS 堆中——它和所有其他东西一样，存在于*我们的* Automerge 文档中。换句话说，闭包自由变量（free variables）的状态也是持久化且共享的。我们很快就会看到这是如何工作的。 ## 在 AM 文档中表示对象 在我们的对象模型中，对象的属性可以保存任何值，包括指向另一个对象的引用，甚至是对象自身： 因此，就像在 JS 中一样，LM 程序的堆中也可能存在环（cycles）。但正如我们之前所解释的，整个堆被表示为一个 AM 文档，而 AM 文档是类 JSON 的，并且必须是树形结构的。这意味着我们的对象模型实现必须将值**序列化**为 AM 兼容的格式。下面是我们序列化后的堆的样子： ``` { objectTable: { '84f2...': <>, 'd9c0...': <>, ... } } ``` 如你所见，我们有一个*对象表（object table）*，它将对象 id 映射到其状态。注意，对象 id 不能是顺序编号的，因为这会导致冲突（想想多用户场景！），所以我们使用 UUID。 下面是对象表中某个对象的状态的样子： ``` { // 特殊属性的名称以 $ 开头 $type: 'obj', $id: '84f2...', // 此对象的 id $protoId: 'd9c0...', // 此对象委托（delegates）到的对象的 id // 用户属性以 @ 开头（这绕过了 Automerge 的一个 bug， // 该 bug 涉及与 Object.prototype 冲突的属性名，比如 `toString`） '@x': 5, // 数字表示…… '@y': 6, // ……为数字 // 对象引用（如下面 `next` 属性的值） // 被表示为具有 `$type = 'ref'` 且包含被引用对象 id 的对象： '@next': { $type: 'ref', $id: '52aa...' }, } ``` 函数在对象表中也有自己的条目——毕竟它们是一等公民对象： ``` { $type: 'fun', $id: '7e1b...', $code: '($scope1) => (x) => x + $scope1.y', // 我们实际求值的内容 $codeForShow: '(x) => x + y', // 我们展示给用户的内容 $scopes: [{ $type: 'ref', $id: '05fd...' }], // 捕获的环境 } ``` 注意 `$scopes` 属性：转译器会分析每个函数的自由变量，将捕获的绑定移动到*作用域对象（scope objects）*上（这些是普通的堆对象），并将函数与其作用域的引用一起序列化。这就是计数器例子能够工作的原因：`count` 存在于堆中的一个作用域对象里，所以当你调用 `counter()` 时，你和我在递增的是同一个 `count`。 ### 数组 数组值不能简单地表示为序列化值的数组。这是因为数组需要有一个 id，其他对象才能引用（也就是别名，alias！）它。因此，LM 中的每个数组在对象表中都有一个条目，其 `$type = 'arr'`，并有一个 `$values` 属性来保存其（序列化后的）元素。这种表示方式使我们的对象模型中的数组能够受益于 AM 中的数组合并语义：如果你向一个数组 push 元素，而我从中 splice 掉一些元素，那么两个编辑在合并后都会保留下来。 ## LM 对象模型的接口 现在我们知道对象是如何表示的，可以更详细地讨论接口了。 ### 全局对象 *全局对象*是 LM 堆的根，在对象表中表示为 id 为 `global` 的对象。当你的代码引用一个全局变量（例如上面的 `f(5, 8)`）时，转译器会将该引用重写为对全局对象*代理（proxy）*上的属性访问。这个代理会拦截对象属性的读写： - 在*写入*时，代理会将正在写入属性的值*序列化*，然后存储到程序 AM 文档中的相应位置。 - 在*读取*时，代理会在程序 AM 文档中找到对应的序列化值，然后返回*反序列化*该值的结果。 #### 序列化值 值的序列化表示取决于其类型： - 原始值（例如数字、字符串或布尔值）直接序列化为其自身。 - 对象、数组或函数被序列化为 `{ $type: 'ref', $id: ... }`——即对对象表中对应条目的引用。 上一节中的示例对象表包含了这些类型的例子。 #### 反序列化值 反序列化的工作方式如下： - 序列化的原始值反序列化后就是其自身。 - 序列化的引用会反序列化为被引用对象的*代理*。（对于函数来说，调用该代理会对其反序列化后的 `$scopes` 求值该函数的 `$code`。） 全局对象在这方面并不特殊：在 LM 中，每次我们与对象交互时，实际上都是在与一个知道它对应哪个对象的代理交互。 一个在实践中很重要的细节：代理是按对象 id 缓存的，因此对同一个对象反序列化两次会得到*同一个*代理——这意味着 `===`、`Map` 的键以及 `Set` 的成员关系都能按你预期的方式工作。 ### 创建对象 当你的代码包含对象、数组或函数字面量——`{ x: 5 }`、`[1, 2, 3]`、`(x) => x + 1`——转译器会将其重写为对相应创建原语的调用。该调用会做两件事：它向对象表中添加一个新的（序列化后的）条目，并返回新对象的代理。 类声明也会得到相同的处理：类成为堆中的一个构造函数，其方法位于实例通过 `$protoId` 委托到的原型对象上。而且，由于类和方法与所有其他对象一样都是堆对象，重新定义一个方法——比如说，从系统浏览器中——会立即对所有协作者生效。 转译器和代理共同作用，使 LM 代码感觉上就像是普通 JavaScript——而工作也在两者之间干净地划分。转译器负责重写将内容*放入*堆中的语法：字面量、全局引用、闭包捕获的局部变量。之后你对堆中对象所做的*一切*——读取和写入属性、调用方法——都通过它们的代理进行，代理负责处理所有涉及的序列化和反序列化。 ## LM 工具 我们已经将 Livelymerge 实现为 Patchwork 的一个工具。下面是一个新建的 LM 文档通过该工具查看时的样子： 一个新建的 Livelymerge 文档。画布还是空白的；右上角的面板显示底层 Automerge 文档的状态（其操作数量和当前 heads）；工作区（workspace）在底部打开，我们刚刚用*print-it* 求值了 `3+4`。 页面底部有一个大型文本区域，其工作方式类似于 Smalltalk 的工作区。如果用户选择工作区中的一些代码并调用 “print it”（Cmd-P），这段代码将被 LM 求值，并通过将结果的字符串化值追加到工作区来显示。“Do it”（Cmd-D）会求值所选代码，但不显示结果。 页面中央的区域是一个（初始为空的）HTML canvas。我们提供了一个 `canvas` 全局变量，使 LM 程序能够在上面绘制任何想要的内容。（canvas 是每个用户各自的主机资源，因此它在堆中存储为符号化的*晚期绑定（late-bound）*引用：AM 文档只写 “canvas”，每个用户的副本在运行时将其解析为*各自*的 canvas。） 你可以在工作区中编写并执行代码，在堆中创建新对象，并通过（前述的 canvas 绑定）实现一个类 LK 的 GUI，如下所示： 同一个工具，在工作区中求值了一些代码之后：一个带有可拖动形状的 Morphic 世界、一个世界菜单、一个欢迎窗口，以及一个显示 `Color.prototype.computeFillStyle` 源代码的 Smalltalk 风格浏览器。其中每一个都是堆中的对象——也就是存在于 Automerge 文档中（注意角落里的操作计数！）——而且所有内容都可以从系统内部进行编辑。 Dan 正在撰写一篇关于上述系统的实验室笔记，敬请期待！与此同时，我将用本节的剩余部分来解释 LM 工具如何托管这个系统，重点是其与程序 AM 文档的交互。 ### `change` 函数 我们的 LM 工具拥有程序 AM 文档的一个 `DocHandle`，并通过该 handler 的 `change` 方法对文档进行更改。但我们并不是直接从 UI 调用那个方法——相反，我们将其包装在我们自己的 `change` 函数中： ``` function change(fn) { let exception; let returnValue; docHandle.change((_doc) => { doc = _doc; $global = proxify(doc.objectTable.global); try { returnValue = fn(); } catch (e) { exception = e; } finally { gc(); } }); if (exception) { console.error(exception); throw exception; } return returnValue; } ``` （这里做了简化——真正的版本还处理嵌套调用以及一些超出本篇笔记范围的簿记工作。） 这个函数的参数（`fn`）是我们要在 LM 中执行的代码。通常它是一个根据用户在工作区中选择的代码创建的函数。但我们也在事件处理和渲染循环中使用它。（下一节会有更多相关内容。） 注意，我们在回调内部捕获了文档的最新版本（`doc = _doc`）。我明白这看起来很有趣/危险/不正确，但这其实是没问题的，因为 `doc` 只在传递给 `change` 的函数的内部（更准确地说，是在其*作用域范围内*）使用。（我们也可以选择把 `doc` 从一个函数传到另一个函数，但这会比这个看起来有趣的 hack 更麻烦，所以我决定不这么做。） ### 垃圾回收 LM 在每次 `change` 结束时执行垃圾回收。我们的垃圾回收器提供的一项重要服务与新建对象有关。我将通过描述系统如何渲染来说明为什么这很重要。 LM 每秒重新渲染所有内容 60 次。这是通过调用用户编写的 `render()` 函数完成的。在渲染过程中，常常会创建大量新对象。例如，我们经常为 *morphs*（Morphic 对象）计算包围盒（bounding boxes），因为我们需要这些信息，但我们不会持有这些包围盒对象。这些对象在分代 GC 中被称为*新生垃圾（fresh garbage）*，快速且廉价地回收它们非常重要。 问题在于：即使我们能及时回收新生垃圾，首先将它们安装到对象表中本身就是一场灾难。在一个 doc handler 的 `change` 方法的单次调用中，将一个对象添加到表中然后再移除，实际上相当于一个 no-op——但 Automerge 仍然会记录每一个单独的操作……