跳到主要内容

两台样机 — 送货机器人与 Egg 语言

这一章讲三件事: 状态先行的设计怎么救你于纠缠(机器人); 广度优先搜索为什么「第一次碰到终点就是最短路」; 一门语言的本体不过是一棵树和一个递归函数(Egg)。 读完你能回答两个大问题:「该把什么存成状态」与「语言是怎么跑起来的」。

1. 为什么要有项目章​

书在理论章之间穿插项目章,理由直白:读和写真实程序与学理论同样重要。本章合并原书两个项目:送货机器人与编程语言 Egg;并把它们排在错误、正则之前——两个项目只用到前六章的概念,先拿旧武器打一场验收,再学新家伙,顺序更稳。作者对 Egg 的目标说得谦逊又骄傲:造语言意外地容易(只要别把目标定太高),而且没有魔法1。

2. 样机一:送货机器人​

2.1 世界是一张图​

Meadowfield 村:11 个地点、14 条路,记成一列 "甲-乙" 字符串。图(graph)= 一批点,加点与点之间的线;机器人就在这张图上动2。先把字符串表换成好用的结构:每个地点 → 从它出发能到哪儿的列表。注意 buildGraph 用 Object.create(null) 造表——上一章刚讲过,当映射用,别让原型链漏东西进来3。

2.2 设计裁决:先说「这个直觉是错的」​

任务:机器人捡起包裹、送到目的地。想象世界的状态时,直觉会说:给机器人写个类、给包裹写个类、给地点写个类,各自带可变属性。书里的原话:「这是错的。至少,通常是对的这种事不发生。」——听起来像对象的东西,不自动该是程序里的对象;给每个概念反射式地造类,得到的是一堆各自揣着内部可变状态、彼此缠绕的对象,难懂易碎4。

取而代之的裁断:把村庄状态压到最小——机器人现在的位置 + 未送包裹列表(每个包裹记在哪、送往哪)。就这些。然后一条更深的规矩:移动不改状态,而是算出新状态5。

2.3 主走查(一):move 的一步​

let first = new VillageState("Post Office",
  [{place: "Post Office", address: "Alice's House"}]);

let next = first.move("Alice's House");

  第 1 步  Post Office 有路直达 Alice's House?有 → 允许移动
  第 2 步  map 所有包裹:
           该包裹 place == 机器人当前位置 → 跟着搬 → {place: "Alice's House", address: "Alice's House"}
  第 3 步  filter:place == address 的包裹已送达,移出列表 → parcels = []
  第 4 步  造新状态 new VillageState("Alice's House", [])

  验证:next.place → "Alice's House"
        next.parcels → []
        first.place → "Post Office"   ← 旧状态纹丝不动

最后一行是全部重点:move 给你新世界,旧世界还在。包裹对象也不是被改,而是被重造6。

2.4 为什么坚持「不变」:动机不是洁癖​

这种不改的数据叫持久(persistent)数据,行为像数字和字符串。JS 万物皆可改,想坚持不变得靠自律(Object.freeze 能让写入被忽略,但书里说**「写入被忽略」和「写错」一样让人糊涂**,他更愿意口头约定别乱碰)7。

动机在书里说得极清楚,值得整句留下:对象不变,我才能孤立地推理(在脑子里单独推演)每一步——从同一起点移到 Alice 家,永远得到同一个新状态;对象会变,推理就多出一整个时间的维度。紧接着是全书最重要的一句工程论断:「我们能造什么样的系统,最重要的上限是我们能理解多少。」任何让代码更易懂的东西,都让更大的系统成为可能8。作者也诚实补了边界:语言不帮忙时,设计持久结构更难,所以本书两种风格都用9。

2.5 三代机器人:63 步、26 步、16 步​

机器人被定义成一个函数:(状态, 记忆——随身的便签) → {direction, 记忆}。记忆的存在让它能执行多步计划10。

代际策略战绩(送 5 个包裹)
randomRobot每步随机挑一条路平均几十步,书中实测 63 步——「能行」的最笨策略11
routeRobot背一条经过全村的固定邮路,跑两遍必完事上限 26 步;记忆存剩余路线12
goalOrientedRobot对第一个未处理包裹用 findRoute 找最短路约 16 步;书中把「继续优化」留成练习13

2.6 主走查(二):广度优先 — 第一根线碰到终点就是最短路​

寻路是典型的搜索问题:你能轻易验证一条路线对不对,却没法像 2+2 那样直接算出答案,只能不断生成候选直到撞上可行的14。两条剪枝:只找从起点出发的;绕回走过地点的路线绝不可能是最优的15。

findRoute 的做法:维护一个工作列表(work list),从 [起点, 空路线] 开始,每次取列表最前面的项,把它的邻居追加到队尾——先到的先探索,所以短路线永远排在长路线前面16。书里的画面感极佳:

想象一张「已知路线的网」从起点均匀向外爬,绝不缠回自己;第一根碰到终点的线,顺着它回到起点,就是最短路线。17

用 dijkstrajs 包验证(把每条边的权重设成 1 来适配它的带权图):find_path 从 Post Office 到 Cabin 给出 [Post Office, Alice's House, Cabin]——正是那根先到的线18。还有一处坦白值得学:代码不处理「工作列表空了」,因为本书的图是连通的,搜索不可能失败——知道自己的前提,才能省掉防御代码19。

3. 样机二:Egg:150 行的语言​

3.1 设计:Egg 里一切都是表达式​

Egg 只有四种表达式:名字、数字、字符串、以及「应用」(圆括号调用,兼当 if/while 用)20。于是 JS 里的运算符,在 Egg 里就是普通的绑定——>(x, 5) 和 f(x, 5) 没有任何地位差别21。

3.2 解析器:文本 → 树​

解析器(parser) 读进文本,吐出反映程序结构的数据结构;不合语法就报错22。第 09 章那种按行处理的配置文件解析器够用,是因为行没有嵌套;这里表达式有递归结构(应用里套应用),所以解析器也递归:parseExpression 认出原子(字符串/数字/名字),把剩余文本连同已认出的表达式交给 parseApply;后者看到左括号就继续用 parseExpression 解析每个参数——两个函数互相递归23。连 multiplier(2)(1) 这种「调用结果再调用」都照顾到了:parseApply 收尾时再看一眼有没有下一个括号24。

>(x, 5) 解析出来的树(书里原样给出):

{type: "apply",
 operator: {type: "word", name: ">"},
 args: [{type: "word", name: "x"},
        {type: "value", value: 5}]}

这叫语法树:对象是点,引用是线;表达式套表达式,正如树枝分叉再分叉25。

3.3 求值器:树 → 值​

求值器(evaluator) 拿到树和一个作用域对象,递归地算出值:value 型直接返回自己的值;word 型去作用域查(查不到抛 ReferenceError);apply 型先看操作符是不是特殊形式,不是就把操作符和参数各求值后调用26。

四件套 if/while/do/define 都定义在 specialForms 表里。其中 if 必须是特殊形式的原因,是全章最锋利的一个点:

普通函数的实参在调用前全部求值;而 if 必须只求值两个分支中的一个。所以它当不了普通函数,只能当「拿到未求值的参数表达式、自己决定求哪个」的特殊形式27。

另外 Egg 比 JS 更倔:if 的条件里只有 false 算假,0 和空串都不算——这是它与 JS 的分界线28。作用域的实现顺手漂亮:run 时用 Object.create(topScope) 造局部作用域,原型链充当作用域链,程序加局部绑定不会污染全局29。最后一步是 fun 形式造函数:最后一个参数是函数体,前面的都是参数名,局部作用域照旧用原型链挂在外层上——闭包自然出现,不用任何额外机制(书里的练习让你解释 f(4)(5) 为什么得 9)30。01 章那道「1 加到 10」在 Egg 里跑出 55;作者总结:比 JS 丑,但对一个不到 150 行实现的语言,不算坏31。

3.4 编译、作弊与 DSL​

现在这台机器边解析边求值,是解释器(interpreter)。编译(compilation)= 在解析与运行之间加一道变换,把能提前做的提前做——比如把「每次按名字查绑定」换成「直接去预定位置取」。传统上编译指译成机器码,但书里给的定义宽得多:任何把程序换一种表示的过程都算编译;把 Egg 译成 JS 字符串再交给 Function 跑,就是一个可行的迷你编译器32。

作者还自首:if/while 就是 JS 自家 if/while 的薄包装,Egg 的值就是 JS 的值——「作弊」。但要紧的推论在后面:搭桥到机器码无非是同款工作的加厚版;而且小语言能干真活——为狭窄领域量身定做的领域特定语言(DSL),因为只描述该描述的东西,反而比通用语言更有表达力(书里随手给了一个「用逻辑记法描述语言、编译成解析器」的 DSL 草样)33。

4. 作者的判断与证据​

  • 「反射式造类是错的」:设计立场,配了机制论证(可变状态→难推理)4;
  • 「理解力是系统规模的上限」:立场,但与本章所有例子对得上8;
  • 「第一根线即最短路」:可证的算法性质(先到先探),不是猜想17;
  • 「造语言没有魔法」:证据就是 150 行的 Egg 本体,复现即可验证1。

判断(我们的,不是书里的): 这两个项目共享一个更深的心法——先造一个能被推理的小核心, 再让外围变量(机器人策略、Egg 程序)在核心上活动。机器人核心是「状态+move」, Egg 核心是「parse+evaluate」,核心都不超过几十行。学会辨认一个系统里「哪几十行是核心」, 比学会任何具体框架都保值。 如果错,会错在: 有些系统的复杂度恰恰在核心里(比如浏览器排版引擎),「核心很小」不是普适规律,而是这两个教学项目的特征。

5. 边界与局限​

  • 机器人不比较不同策略的平均战绩(练习补上:同一批 100 个任务两边都跑);
  • findRoute 没有处理不可达(依赖连通前提),也没优化「先取件还是先送件」;
  • Egg 没有数组、没有注释、没有 set(修作用域),出错时也不报行列号——书中全部留作练习或明说省略;
  • Egg 的 if 把一切非 false 当真值处理为假——与 JS 的 falsy 体系不同,别混用直觉;
  • 两个项目都在内存里,没有持久化(第 14 章的项目会补上)。

6. 可带走的​

  1. 听起来像对象的东西不自动该是对象;先压状态,再谈类;
  2. 每次移动算新状态:旧世界还在,推理就能孤立进行;
  3. 「理解力是系统规模的上限」——一切可读性投资的最终理由;
  4. 机器人=函数;记忆让策略能做计划;随机 63 步 → 邮路 26 步 → 寻路 16 步;
  5. 搜索=验证容易、直接求解难;广度优先的第一根线就是最短路;
  6. 图的映射记得 Object.create(null);
  7. 解析器=文本→语法树;求值器=树+作用域→值;两者互为镜像;
  8. if 必须是特殊形式:它不能承受「实参全部先求值」;
  9. 原型链可以充当作用域链——一个机制两处用;
  10. 编译=提前做功;DSL 因「只描述该描述的」而更有表达力。

7. 原文地图​

主题原书章原文位置
项目章的用意Project: A Robottext/10-fm-project-a-robot.txt:9(搜「pummeling」)
村庄与图同上text/10-fm-project-a-robot.txt:15(搜「Meadowfield」) · :27(搜「graph」)
buildGraph 与无原型表同上text/10-fm-project-a-robot.txt:31(搜「buildGraph」) · :32(搜「Object.create(null)」)
「这是错的」同上text/10-fm-project-a-robot.txt:61(搜「This is wrong」)
最小状态与算新状态同上text/10-fm-project-a-robot.txt:63(搜「minimal set」) · :65(搜「compute a new state」)
move 走查与旧状态不动同上text/10-fm-project-a-robot.txt:92(搜「first」) · :103(搜「Post Office」)
Object.freeze 与口头约定同上text/10-fm-project-a-robot.txt:111(搜「freeze」)
可理解的动机同上text/10-fm-project-a-robot.txt:118(搜「understand my programs」) · :120(搜「how much we can understand」)
机器人=函数+记忆同上text/10-fm-project-a-robot.txt:128(搜「memory」)
随机机器人 63 步同上text/10-fm-project-a-robot.txt:145(搜「dumbest」) · :185(搜「63」)
邮路 26 步同上text/10-fm-project-a-robot.txt:209(搜「26」)
搜索问题与剪枝同上text/10-fm-project-a-robot.txt:217(搜「search problem」) · :219(搜「twice」)
work list 与先到先探同上text/10-fm-project-a-robot.txt:240(搜「work list」) · :238(搜「in the right order」)
爬网画面与连通前提同上text/10-fm-project-a-robot.txt:244(搜「web of known routes」) · :246(搜「connected」)
目标机器人 16 步同上text/10-fm-project-a-robot.txt:262(搜「16 turns」)
dijkstrajs 验证最短路Modulestext/13-fm-modules.txt:241(搜「find_path」)
造语言没有魔法Project: A Programming Languagetext/15-fm-project-a-programming-language.txt:9(搜「surprisingly easy」) · :11(搜「no magic」)
Egg 一切皆表达式同上text/15-fm-project-a-programming-language.txt:19(搜「Everything in Egg」)
运算符是普通绑定同上text/15-fm-project-a-programming-language.txt:30(搜「normal bindings」)
解析器定义同上text/15-fm-project-a-programming-language.txt:17(搜「parser」)
互递归解析同上text/15-fm-project-a-programming-language.txt:108(搜「indirect」) · :110(搜「multiplier」)
语法树与 >(x,5)同上text/15-fm-project-a-programming-language.txt:47(搜「syntax tree」) · :38(搜「apply」)
求值器三型同上text/15-fm-project-a-programming-language.txt:136(搜「evaluate」)
if 为何必须特殊形式同上text/15-fm-project-a-programming-language.txt:190(搜「special form」)
只有 false 算假同上text/15-fm-project-a-programming-language.txt:188(搜「empty string」)
原型链当作用域链同上text/15-fm-project-a-programming-language.txt:264(搜「prototype chains」)
fun 与闭包练习同上text/15-fm-project-a-programming-language.txt:280(搜「fun」) · :369(搜「f(4」)
150 行与 55同上text/15-fm-project-a-programming-language.txt:276(搜「150 lines」)
编译的定义同上text/15-fm-project-a-programming-language.txt:327(搜「Compilation」) · :329(搜「machine code」)
作弊与 DSL同上text/15-fm-project-a-programming-language.txt:335(搜「Cheating」) · :355(搜「domain-specific」)

Footnotes​

  1. 出处:「Project: A Programming Language」第 9 段(text/15-fm-project-a-programming-language.txt:9,搜「surprisingly easy」)。 ↩ ↩2

  2. 出处:「Project: A Robot」第 27 段(text/10-fm-project-a-robot.txt:27,搜「graph」)。 ↩

  3. 出处:「Project: A Robot」第 32 段(text/10-fm-project-a-robot.txt:32,搜「Object.create(null)」)。 ↩

  4. 出处:「Project: A Robot」第 61 段(text/10-fm-project-a-robot.txt:61,搜「This is wrong」)。 ↩ ↩2

  5. 出处:「Project: A Robot」第 63 段(text/10-fm-project-a-robot.txt:63,搜「minimal set」)与第 65 段(text/10-fm-project-a-robot.txt:65,搜「compute a new state」)。 ↩

  6. 出处:「Project: A Robot」第 92 段(text/10-fm-project-a-robot.txt:92,搜「first」)与第 90 段(text/10-fm-project-a-robot.txt:90,搜「entirely intact」)。 ↩

  7. 出处:「Project: A Robot」第 109 段(text/10-fm-project-a-robot.txt:109,搜「persistent」)与第 111 段(text/10-fm-project-a-robot.txt:111,搜「freeze」)。 ↩

  8. 出处:「Project: A Robot」第 118 段(text/10-fm-project-a-robot.txt:118,搜「understand my programs」)与第 120 段(text/10-fm-project-a-robot.txt:120,搜「how much we can understand」)。 ↩ ↩2

  9. 出处:「Project: A Robot」第 122 段(text/10-fm-project-a-robot.txt:122,搜「a little harder」)。 ↩

  10. 出处:「Project: A Robot」第 126 段(text/10-fm-project-a-robot.txt:126,搜「robot is a function」)与第 128 段(text/10-fm-project-a-robot.txt:128,搜「memory」)。 ↩

  11. 出处:「Project: A Robot」第 145 段(text/10-fm-project-a-robot.txt:145,搜「dumbest」)与第 185 段(text/10-fm-project-a-robot.txt:185,搜「63 turns」)。 ↩

  12. 出处:「Project: A Robot」第 209 段(text/10-fm-project-a-robot.txt:209,搜「26 turns」)。 ↩

  13. 出处:「Project: A Robot」第 262 段(text/10-fm-project-a-robot.txt:262,搜「16 turns」)。 ↩

  14. 出处:「Project: A Robot」第 217 段(text/10-fm-project-a-robot.txt:217,搜「search problem」)。 ↩

  15. 出处:「Project: A Robot」第 219 段(text/10-fm-project-a-robot.txt:219,搜「twice」)。 ↩

  16. 出处:「Project: A Robot」第 240 段(text/10-fm-project-a-robot.txt:240,搜「work list」)与第 242 段(text/10-fm-project-a-robot.txt:242,搜「first」)。 ↩

  17. 出处:「Project: A Robot」第 244 段(text/10-fm-project-a-robot.txt:244,搜「web of known routes」)。 ↩ ↩2

  18. 出处:「Modules」第 241 段(text/13-fm-modules.txt:241,搜「find_path」)。dijkstrajs 的适配代码在第 233 段。 ↩

  19. 出处:「Project: A Robot」第 246 段(text/10-fm-project-a-robot.txt:246,搜「connected」)。 ↩

  20. 出处:「Project: A Programming Language」第 19 段(text/15-fm-project-a-programming-language.txt:19,搜「Everything in Egg」)。 ↩

  21. 出处:「Project: A Programming Language」第 30 段(text/15-fm-project-a-programming-language.txt:30,搜「normal bindings」)。 ↩

  22. 出处:「Project: A Programming Language」第 17 段(text/15-fm-project-a-programming-language.txt:17,搜「parser」)。 ↩

  23. 出处:「Project: A Programming Language」第 55 段(text/15-fm-project-a-programming-language.txt:55,搜「parseExpression」)与第 108 段(text/15-fm-project-a-programming-language.txt:108,搜「indirect」)。 ↩

  24. 出处:「Project: A Programming Language」第 110 段(text/15-fm-project-a-programming-language.txt:110,搜「multiplier」)。 ↩

  25. 出处:「Project: A Programming Language」第 47 段(text/15-fm-project-a-programming-language.txt:47,搜「syntax tree」)与第 47 段(text/15-fm-project-a-programming-language.txt:47,搜「treelike」)。 ↩

  26. 出处:「Project: A Programming Language」第 132 段(text/15-fm-project-a-programming-language.txt:132,搜「evaluator」)与第 136 段(text/15-fm-project-a-programming-language.txt:136,搜「evaluate」)。 ↩

  27. 出处:「Project: A Programming Language」第 190 段(text/15-fm-project-a-programming-language.txt:190,搜「special form」)。 ↩

  28. 出处:「Project: A Programming Language」第 188 段(text/15-fm-project-a-programming-language.txt:188,搜「empty string」)。 ↩

  29. 出处:「Project: A Programming Language」第 260 段(text/15-fm-project-a-programming-language.txt:260,搜「run」)与第 264 段(text/15-fm-project-a-programming-language.txt:264,搜「prototype chains」)。 ↩

  30. 出处:「Project: A Programming Language」第 280 段(text/15-fm-project-a-programming-language.txt:280,搜「fun」)与第 371 段(text/15-fm-project-a-programming-language.txt:371,搜「f(4」)。 ↩

  31. 出处:「Project: A Programming Language」第 276 段(text/15-fm-project-a-programming-language.txt:276,搜「150 lines」)。 ↩

  32. 出处:「Project: A Programming Language」第 327 段(text/15-fm-project-a-programming-language.txt:327,搜「Compilation」)与第 329 段(text/15-fm-project-a-programming-language.txt:329,搜「machine code」)。 ↩

  33. 出处:「Project: A Programming Language」第 335 段(text/15-fm-project-a-programming-language.txt:335,搜「Cheating」)与第 355 段(text/15-fm-project-a-programming-language.txt:355,搜「domain-specific」)。 ↩