PapersWeLove
只要将求值过程中的等号视为对称的代数约束而非单向执行流程,极简解释器就能在不额外编写求解器的情况下自动逆向合成未知代码、解出Quine并完成实时定理证明。
AI-assisted summary of William Byrd on "The Most Beautiful Program Ever Written" [PWL NYC] — original source. Check the original for full context.
Source published:
Key ideas
- William Byrd 探讨了被称为“软件领域麦克斯韦方程组”的 Lisp 元循环解释器,指出只需保留变量查找、Lambda 抽象与过程调用三行核心规则,即可构成图灵完备的微型求值器。 (5:27)
- 通过在逻辑编程语言 miniKanren 中将求值器重新实现为双向关系,传统的单向代码执行被转化为代数约束求解,使得系统能够逆向求解输入、枚举 Quine 乃至自动合成程序。 (61:02)
- 基于该理论开发的程序合成工具 Barliman 结合了剪枝优化与 Gensym 机制,搜索速度相比原生版本提升约 1000 万倍,可在交互式测试驱动开发中实时证明不完全代码与测试用例之间的逻辑不兼容。 (77:21)
- 研究团队最新的初步实验表明,通过在关系式解释器中融入人类常见的 AST 父节点惯用模式(如 lambda 内部倾向于嵌套 if/cond),能将程序合成效率提升数个数量级。 (87:36)
Detailed notes
## Background 本视频由 YouTube 频道 PapersWeLove 于 2017 年 5 月 24 日发布,记录了在纽约举办的技术分享活动。页面简介指出,犹他大学的研究副教授 William E. Byrd 在演讲中深入探讨了他心目中“有史以来最美丽的程序”——用 Lisp 编写的 Lisp 元循环解释器,并解析了围绕该解释器展开的诸多惊人思想与前沿延伸。
## TL;DR William Byrd 从师从 Daniel Friedman 的经历切入,现场演示了如何在 Scheme 中逐步构建出一个基于高阶表示的微型 Lisp 解释器,并展示其如何被浓缩为仅有三行核心规则(变量查找、Lambda 抽象与函数调用)的图灵完备程序。随后,Byrd 将视角从传统的单向求值推向数学与逻辑上的双向对称关系,揭示了“认真对待等号”的深层含义。通过基于 miniKanren 的关系式解释器及其衍生工具 Barliman,演讲生动展示了代码逆向推导、自产生程序(Quine)的自动生成、完形填空式的程序合成,以及后台实时定理证明等突破性应用。
## Atmosphere & style 整场演讲洋溢着纯粹的极客热忱与学术幽默,Byrd 举重若轻地在白板式现场编码与深刻的数理哲学反思之间自如切换。他频频用“奶昔”、“极客战栗(nerd chills)”以及调侃 Haskell 程序员的俏皮话打破高深理论的距离感,让现场充满阵阵会心的笑声。随着代码从几行极简规则一路演化到惊人的程序自动合成,观众在轻松欢快的氛围中体会到计算本质的震撼之美。
## Bulletin - [05:27](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=327s) William Byrd 探讨了被称为“软件领域麦克斯韦方程组”的 Lisp 元循环解释器,指出只需保留变量查找、Lambda 抽象与过程调用三行核心规则,即可构成图灵完备的微型求值器。 - [01:01:02](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=3662s) 通过在逻辑编程语言 miniKanren 中将求值器重新实现为双向关系,传统的单向代码执行被转化为代数约束求解,使得系统能够逆向求解输入、枚举 Quine 乃至自动合成程序。 - [01:17:21](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=4641s) 基于该理论开发的程序合成工具 Barliman 结合了剪枝优化与 Gensym 机制,搜索速度相比原生版本提升约 1000 万倍,可在交互式测试驱动开发中实时证明不完全代码与测试用例之间的逻辑不兼容。 - [01:27:36](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=5256s) 研究团队最新的初步实验表明,通过在关系式解释器中融入人类常见的 AST 父节点惯用模式(如 lambda 内部倾向于嵌套 if/cond),能将程序合成效率提升数个数量级。
## Key takeaways - [02:33](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=153s) 自认为完全掌握某项经典概念是程序员最危险的思维定势,正如仅有几行规则的考拉兹猜想(3n+1)至今仍难倒顶尖数学家一样,极简代码同样蕴含极深的理论复杂度。 - [05:27](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=327s) Alan Kay 将写在《LISP 1.5 Programmer's Manual》第 13 页的 Lisp 元循环解释器誉为“软件领域的麦克斯韦方程组”,其微小的体积承载了 CPS 变换、定界续体以及可变状态等海量语言特性的衍生可能。 - [08:30](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=510s) 反思解释塔(Reflective Towers of Interpreters)构建了多层相互解释的架构,下层解释器可向上访问并修改上层机制以在运行时改写自身语义,展现了元循环解释器极致的理论演化方向。 - [12:40](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=760s) 嵌套列表本质上就是树形结构,而递归是处理树最自然的手段;Lisp 的同音异义性与 S-表达式让程序能够以最纯粹的形式自如修改与操作自身。 - [34:02](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=2042s) 测试解释器时必须严格为输入代码包裹 quote(引用),避免测试表达式在外层宿主 Scheme 环境中被提前求值,从而产生解释器已实现特定特性的假象。 - [39:16](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=2356s) 算术操作和条件分支在理论上都是可以剔除的语法糖,图灵完备解释器的最核心精髓仅由三行构成:变量查找、Lambda 抽象生成闭包以及过程调用。 - [49:10](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=2950s) 在高阶表示的解释器中,环境与过程闭包本身均被表示为 Scheme 的高阶函数,变量寻值被精简为调用环境函数 (env var),未命中则向父闭包递归转发。 - [59:38](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=3578s) 约翰·麦卡锡在论文中写下的 value(e, r) = v 中的等号往往被传统编译器视为从左到右的单向流动,但严肃对待等号的数学双向对称性是打破传统计算范式的关键。 - [01:01:02](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=3662s) 在 miniKanren 中实现的 43 行关系型解释器 eval-expo 消除了输入与输出的界限,支持通过指定结果来逆向推导代码或输入参数,例如秒解 Quine 与列表拆分组合。 - [01:13:56](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=4436s) 将关系型解释器中任意代码位置替换为未知逻辑变量,系统便跨入程序合成领域;面对逻辑系统如“狡黠精灵”般钻空子硬编码常量的行为,需通过扩充测试集与 Gensym 施加结构性约束。 - [01:21:55](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=4915s) Barliman 界面不仅能基于输入输出示例自动合成递归算法,其后台运行的 miniKanren 还能作为定理证明器,在用户敲入冲突代码的瞬间在数学层面上证明不一致性并实时拦截。 - [01:29:52](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=5392s) 关系式程序合成在搜索未知变量时并非盲目枚举,而是由解释器内置的环境作用域(如 letrec 绑定)动态约束其候选空间,使递归调用自然纳入候选分支。
## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=0s) 从中学生涯到印第安纳大学:五行改变人生的代码
演讲者 William E. Byrd(昵称 Will)回顾了自己的经历:他曾做过初中老师、开办过夏令营,后来拿到计算机科学学位并成为一名 Java 工程师。由于厌倦了 Java 和 JavaScript 琐碎的开发日常,他决定前往印第安纳大学(Indiana University)攻读研究生,跟随 Daniel P. Friedman 教授学习。Dan Friedman 撰写了著名的经典教材《The Little LISPer》(以及修订版《The Little Schemer》、《The Seasoned Schemer》),后来两人还共同合著了《The Reasoned Schemer》。在 Will 入学第一学期的前几周,Dan 向他展示了一段彻底改变他一生的极简代码。
Will 直言,过去十二三年来他一直在试图真正参透这“短短五行代码”,甚至做好了将余生全部投入去理解其深远影响的准备。与那些热衷于编写包含十万行代码的编译器或两百万行操作系统内核的工程师不同,Will 坦言自己更偏爱极其精炼、高度抽象的极简设计。
- **卡片哲学**:Dan Friedman 推崇一种“3x5 英寸卡片”(或 4x6 英寸卡片,折算大约相当于 A4 纸的一小角)的思考法则——如果无法把一个核心思想浓缩在一张 4x6 的卡片上,说明你想得还不够透彻,必须“think harder”;一旦成功提炼到 3x5 卡片上,就可以基于它写出一本小册子。 - **震撼体验**:这段核心程序每每被 Will 回想起来,依然会让他激动得浑身泛起“nerd chills(极客战栗)”。
---
[02:33](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=153s) 所谓“理解”的危险陷阱与考拉兹猜想(Collatz Conjecture)
面对现场众多熟知 Lisp、刷过 SICP(《计算机程序的构造和解释》)、写过很多解释器并对 Lambda 演算有所了解的资深开发者,Will 坦言自己作这场报告十分忐忑。他指出,随着编程年限增长,程序员最容易陷入一种致命的心态,即自认为已经彻底弄懂了某个经典结构,觉得它再也变不出什么新花样:
> “And that's the most dangerous way of thinking is to think you understand something right and that there are no kind of new tricks in this.” —— William E. Byrd
他习惯每隔两三年便回过头去重新审视那些很早以前就学过且以为掌握了的旧概念,却几乎总能从中发现全新的观察视角。在计算机科学及任何深奥的学科中,真正伟大的思想都具备多面性。
为了证明极其简短的程序同样能蕴含无穷无尽的深奥复杂度,Will 举了著名的“考拉兹猜想”(Collatz Conjecture,即 $3n+1$ 问题)作为类比:一个只有两三行乘除与加法的简单函数,数十年来全世界顶尖的数学家竭尽全力都无法证明它对于任意正整数输入是否一定停机。传奇数学家保罗·埃尔德什(Paul Erdős)曾对此感慨道:“数学还没有准备好应对考拉兹问题。”连三行算术代码都能难倒历史上最伟大的数学大脑,这也警戒着人们必须对“写在 3x5 卡片上的极简程序”抱有足够的敬畏之心。
```mermaid flowchart TD accTitle: Collatz Function Complexity accDescr: 一个简单的 3n+1 规则展示了极简代码可能具备的惊人数学深度与停机复杂性。 Start["正整数输入 n"] --> Check{"n 是否为 1?"} Check -->|"是"| Stop["停机终止"] Check -->|"否 (偶数)"| Div["n / 2"] Check -->|"否 (奇数)"| Mul["3n + 1"] Div --> Check Mul --> Check ```
---
[05:27](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=327s) Lisp 元循环解释器:软件领域的麦克斯韦方程组
Will 随后引出了本次分享的核心主角:用 Lisp 本身编写的 Lisp 解释器(即“元循环解释器”)。初涉 Lisp 的人往往会被满眼的括号所困扰,继而纠结于 `lambda` 究竟是什么、嵌套两层 `lambda` 又是何用意;但在一步步手动跟踪执行追踪、弄清求值语义后,人们就会开始对解释器进行改写与把玩。这个解释器最美妙的地方在于,它是进行编程语言实验的完美实验台,具备近乎无限的可扩展性与衍生性:
- **程序变换的“诱导剂”**:Will 把续体传递风格(Continuation-Passing Style, CPS)形容为程序变换界的“入门毒品(gateway drug)”。只要把解释器转化为 CPS 风格,就能大展身手;如果做“二次 CPS 变换(CPS it twice)”,便能自然导出定界续体(Delimited Continuations)。 - **语言特性的极简扩展**:在解释器参数中增加一个 `store`,就能轻易引入 `box`,实现可变状态(mutation)和副作用;还能极其轻松地自由切换传值调用(Call by Value)、按需调用(Call by Need)与传名调用(Call by Name)。
Will 指出,整个计算机科学界没有任何其他构件能像这套解释器一样,以如此微小的体积承载如此繁多的思想。面向对象编程先驱艾伦·凯(Alan Kay)在早年翻到《LISP 1.5 Programmer's Manual》第 13 页底部时,被那段用 Lisp 写出的 Lisp 解释器深深震撼,甚至改变了自己的一生,并感叹它就是“软件领域的麦克斯韦方程组(Maxwell's equations of software)”:
> “These are Maxwell's equations of software.” —— Alan Kay
就像经典物理中把前人总结的四道优美电磁方程写在一张卡片上、花上一生去体会其衍生含义一样,Lisp 解释器在计算领域同样扮演着这一角色。
---
[08:30](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=510s) 反思塔、类型推断与“来自上帝之书的代码”
为了展现该程序令人惊叹的发展方向,Will 提到了更为深奥的奇特结构——反思解释塔(Reflective Towers of Interpreters):底层解释器被上一层解释器解释,上一层又被再上一层解释,构成多层乃至无穷高度的解释塔。其极其迷人却又烧脑的机制在于:被解释的下层解释器能够反向“向上触及”正在解释它自身的上层解释器,并通过修改上层解释器的执行机制,在运行时动态改写自己本身的语义。Dan Friedman 甚至公开表示自己拒绝再碰反思塔,因为那“太烧脑了(melted his brain too much)”,是他明确立誓不再触碰的领域。对此有兴趣的读者可以参考浅井健一(Kenichi Asai)的研究,以及 Nada Amin 在 Strange Loop 上题为《Programming Should Eat Itself》的主题演讲。
```mermaid flowchart TD accTitle: Reflective Tower of Interpreters accDescr: 无穷反思塔中底层解释器向上访问并改变自身语义的执行关系。 subgraph ReflectiveTower["反思解释塔 (Reflective Tower)"] L3["更高层解释器 (Level N)"] L2["上层解释器 (Level 2)"] L1["底层解释器 (Level 1)"] L3 -->|"逐层解释运行"| L2 L2 -->|"解释并驱动执行"| L1 L1 -.->|"反射修改 (改变自身语义)"| L2 end ```
这种前沿探索即便让 Lambda 演算的资深专家思考其推论时,脸上都会泛起恐惧的神色。除了反思塔,元循环解释器还可以向类型推断系统延伸:使解释器与类型推断器共享同一个核心 AST 结构并产生紧密交互。正如 CPS 是代码变换的 gateway drug 一样,“Lisp in Lisp”正是领略整个程序设计语言宏伟世界的 gateway drug。
Will 表示,在接下来的时间里,他将现场带领大家以 Dan Friedman 的方式重新编写这个 Lisp 解释器。这里他引用了数学家保罗·埃尔德什的浪漫传说:上帝有一本珍藏了宇宙间所有最完美证明的“天书(The Book)”;而在软件世界里,这几行 Lisp 元循环解释器,正是那段理应收录于天书之上的极致神作。
[11:15](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=675s) “书中的程序”与 S-表达式入门
William Byrd 引用了数学家保罗·埃尔德什(Paul Erdős)关于“上帝之书”的典故:每当数学家发现一个极其优雅美丽的证明,就会感叹这是收录在“天书”(the Book)中的证明。Byrd 指出,他当晚要展示的正是这样一段“天书中的程序”。Byrd 直言:“I've written hundreds of interpreters and I've read lots of books on interpreters, but this to me is the one in the book. Everything else is a pale imitation.”(我写过成百上千个解释器,也读过无数关于解释器的书籍,但在我看来,唯独这个是收录在天书里的程序,其他一切不过是拙劣的仿作)。
为了让全场跟上节奏,Byrd 询问台下有多少人熟悉 S-表达式(symbolic expressions)或能够看懂括号,结果举手的大约只有一半。Byrd 安慰大家不用担心,他会亲自演示教学。他提醒听众,这篇论文蕴含着极其深邃的思想,今晚即便只是浮光掠影地扫视,也可能会让人感到“眩晕”;若真的觉得头晕,不妨“闭上双眼、身体前倾,房间就会停止旋转”。他保证,一旦大家对这个概念有了感知,就会被一种狂热的激情所点燃,想要把其余的所有细节全部搞懂,甚至可以在演讲后一起喝着奶昔深入讨论。
- 核心演讲主题:“天书中的程序”——用 Lisp 编写的 Lisp 元循环解释器(metacircular interpreter)。 - 现场受众基础:现场大约只有 50% 的听众熟悉 S-表达式和 Lisp 语法。
---
[12:40](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=760s) Chez Scheme 的交互体验与树状数据结构
Byrd 解释道,Scheme 是 Lisp 的一种方言,而 Lisp 的名字正是源自“表处理”(List Processing)。他打开了信赖已久的 Chez Scheme(现已遵循开源许可证)。他特别强调了 Chez Scheme 的交互式顶层环境叫做 REPL,并幽默地纠正其发音是“reppel”而不是“reple”。Chez Scheme 的卓越之处在于,即使用户只是在终端里交互式输入表达式,系统也会在后台即时将其直接编译为机器码;Chez Scheme 会预先进行分析,判断是直接求值更快,还是先编译再求值更快。
```mermaid flowchart TD accTitle: REPL Evaluation Flow accDescr: Flowchart illustrating how Chez Scheme processes input expressions either by direct evaluation or by compiling on the fly to machine code. subgraph REPL ["Scheme REPL (Read-Eval-Print Loop)"] Input["输入 S-表达式 (例如 5, (+ 2 3))"] --> Analysis{"速度判定分析"} Analysis -->|"直接求值更快"| Eval["直接求值 (Evaluate)"] Analysis -->|"编译后执行更快"| Compile["即时编译至机器码 (On-the-fly Compile)"] Eval --> Output["输出结果"] Compile --> Output end ```
随后 Byrd 带领观众认识最基本的数据构成:纯数字 `5` 求值得到 `5`;包含数字的列表 `(5)` 则由优美的圆括号包裹;包含两个元素的列表 `(5 6)` 绝不会被“逗号等杂物玷污”。列表内部还可以嵌套列表形成 `((5))` 乃至更深层次的结构。Byrd 指出,“嵌套列表”在计算机科学里的另一个名字就是“树”(tree)。他顺带调侃了技术发展史:现在的 XML 以及更早的 SGML,其用于树结构样式转换的语言除了 XSLT 之外,SGML 时代还有一个名为 DSSSL(Document Style Semantics and Specification Language)的语言,而 DSSSL 本质上就是 R4RS Scheme。树是一种归纳定义的数据类型,处理树的最自然方式就是递归(recursion)。大多数程序天然就是树形结构,如果想要一种能够自如修改和操作程序的编程语言,基于树与递归的 Lisp 是无可比拟的。
- 推荐学习资源:Andrew Plotkin(网名 zarf)编写的互动小说游戏《Lists and Lists》,玩家在游戏中由一位神灯精灵指导学习 Scheme 编程,甚至能在其中实现逻辑编程系统(受限于 Z-machine 的内存上限)。 - 语法纯粹性:列表元素以空格分隔,完全省略了主流语言中的逗号分隔符。
---
[17:03](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=1023s) 逻辑值、引用(Quote)与符号(Symbol)
在 Scheme 的类型系统中,布尔值真表示为 `#t`,假表示为 `#f`。Byrd 调侃道:“#t is a representation of truth; there is no representation of beauty, but we have #f which is a representation of false.”(`#t` 代表真理;虽然没有代表美丽的符号,但我们有代表虚假的 `#f`)。Scheme 规定,除了 `#f` 之外,系统内的所有值在条件上下文中都会被视为真(例如数字 `5` 也是真)。
随后 Byrd 引入了一个极其深邃且引发诸多理论争议的运算符——`quote`(引用)。`quote` 的作用是原样返回其包裹的内容,阻止求值。由于数字 `5` 是自求值字面量(self-evaluating literal),`quote 5` 依然是 `5`;但对于列表 `(5 6)` 或空列表 `()`,使用 `quote` 可以直接获得其字面数据。为了避免繁琐的输入,Scheme 引入了单引号语法糖,即 `'(5 6)`。
除了数值、布尔值和列表,Lisp 还有一个至关重要的一等公民类型——“符号”(Symbol)。Byrd 针对面向对象语言打趣道:“If you program in Java, I'm sorry, you don't get symbols.” 符号(如 `'milkshake`)既不是变量名,也不是字符串,而是一个表示概念的不可分割的原子值(atomic value)。在 Scheme 底层,符号之间的比较在指针级别极快,因此非常适合用于表示具有特定语义的数据实体,而无需像 C 语言那样用冷冰冰的数字常量来充当枚举。
---
[19:48](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=1188s) 谓词、Cons 构造器与分支条件(if / cond)
在操作列表与数据时,Byrd 介绍了基础谓词(predicate)。Scheme 的函数调用均采用前缀表达式,例如 `(null? '())`。以问号结尾是 Scheme 命名谓词的约定,此表达式判断传入参数是否为空列表并返回 `#t`,而 `(null? 5)` 则返回 `#f`。
接着,Byrd 讲解了如何构造列表结构。除了直接引用字面量或调用 `(list 3 4 5)` 外,最核心的底层运算符是 `cons`(意为 Construction)。Byrd 回忆道,他的博士导师 Dan Friedman 曾与 David Wise 在 1976 年合作发表了具有里程碑意义的论文《CONS Should Not Evaluate Its Arguments》,奠定了类似 Haskell 中的惰性求值思想;随后 Henry Baker 还撰写了一篇标题极具双关戏谑风格的论文《CONS Should Not CONS Its Arguments》。基础的 `cons` 接受两个参数,把一个新元素链接到现有列表的头部,例如 `(cons 5 '())` 产生 `(5)`,而嵌套的 `(cons 6 (cons 5 '()))` 则构筑起链表结构。
```mermaid flowchart LR accTitle: Cons Memory Structure accDescr: Diagram illustrating how cons pairs construct a linked list of two elements: six and five. subgraph ConsCells ["内存中的 Cons 对 (Pair) 结构"] C1["cons cell 1"] C2["cons cell 2"] N["'() (空列表)"]
C1 -->|"car (数据)"| D1["6"] C1 -->|"cdr (后续)"| C2 C2 -->|"car (数据)"| D2["5"] C2 -->|"cdr (后续)"| N end ```
在程序控制流方面,Byrd 演示了条件分支的基本形态: 1. `if` 表达式:由测试表达式、后继表达式(consequent)与替代表达式(alternative)三部分构成。例如 `(if (null? 5) 6 7)` 的求值结果为 `7`。 2. `cond` 表达式:用于消除深层嵌套 `if` 所带来的混乱。每个分支由条件与结果配对组成,系统会按顺序检索首个满足条件的分支。 此外,Byrd 还展示了 Scheme 的基本算术函数(如 `+` 和 `*`),它们本身是绑定到具体计算过程的普通函数对象,并原生支持大整数(bignums)的任意精度计算。最后,他引出了定义变量和函数的 `define` 操作符。
[23:37](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=1417s) 变量绑定、环境与 Lambda 表达式
William Byrd 继续讲解 Scheme 的基本概念,首先通过 `define` 为值赋予名称。为了举个生活化的例子,他提到自己刚刚喝了一杯香芋奶茶,于是写下 `(define taro 'good)`,将符号 `'good` 绑定到名称 `taro` 上。随后他在 REPL 中输入 `taro`,系统便会在“环境”(environment)中查找该变量,并返回其值 `'good`。通过这一操作,Byrd 说明了 `define` 的本质:为一个值赋予名称,无论这个值是符号还是其他类型。
```mermaid flowchart LR accTitle: 变量求值流程 accDescr: 展示在 REPL 中输入变量名后通过环境查找其值的基本求值流程
subgraph EvalProcess["求值流程"] Input["输入: taro"] Env["环境 (Environment)<br/>taro ↦ 'good"] Output["返回值: 'good"] Input -->|"查找变量"| Env Env -->|"取得绑定值"| Output end ```
接着,Byrd 引入了“函数”(或者严格来说叫“过程”,procedure)的概念,在 Scheme 中使用核心表达式 `lambda` 来创建。在终端里,他的编辑器自带排版替换功能,将输入的 `lambda` 自动显示为数学符号 $\lambda$。Byrd 解释道,一个 `lambda` 表达式包含形参列表(formal parameters)和函数体(body)。例如,恒等函数写作 `(lambda (x) x)`,Byrd 念作 “Lambda x x”,它的功能仅仅是返回传入参数的值。
在 Scheme 中,外层圆括号通常表示过程调用(procedure call),除非首位置出现诸如 `quote` 或 `define` 这样的“特殊形式”(special form)。Byrd 展示了将恒等函数应用于参数 `5` 的全过程: - 运算符表达式(operator,常称作 “rator”)求值为一个接受单参数的过程; - 操作数表达式(operand,常称作 “rand”)求值自身(即数值 `5`); - 运行时执行过程应用(procedure application),将求得的过程应用到求得的实参上,最终返回结果 `5`。
Byrd 强调了“表达式”(expression)与“值”(value)之间的关键区别,并指明这套操作数与运算符求值并应用的机制,正是他们接下来要亲手实现的解释器核心。
随后,Byrd 定义了一个名为 `double` 的过程。在演示时,他打趣说:“I can double my fun”,结果引发了错误,他笑着调侃 Haskell 程序员肯定会因此找他麻烦(“The Haskellers are going to give me grief”)。接着他测试了对 `5` 进行双倍运算。Byrd 还进一步展示了 Scheme 的灵活性甚至危险性:他执行了 `(define define 5)`,将关键字 `define` 自身重定义成了整数 `5`。面对观众的反应,Byrd 解释说:“I can do a lot more than that. I can change what Lambda means and things like that; that's where the real fun begins.” 不过他打住话题,重启了 Scheme 交互环境,并开玩笑对台下说大家还没准备好见识那样的魔法:“You're not ready yet.”
---
[27:11](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=1631s) 宏系统与 Pmatch 模式匹配
Byrd 对听众说,大家现在已经掌握了 Scheme 的基本要素;虽然听上去像句玩笑,但写解释器真正需要的基础知识就只有这么多。在正式动手之前,他还想引入一个虽然不属于标准 Scheme、但极易通过宏(macro)扩展出来的工具——模式匹配宏 `pmatch`。Scheme 拥有极为强大的宏系统,允许开发者自由扩展语言语法。
Byrd 加载了 `pmatch` 宏,并解释它的设计精神与条件分支 `cond` 类似,但它不是判断布尔条件,而是针对表达式的结构进行匹配。他现场演示了一个例子:对表达式 `(list 3 4)` 进行模式匹配,匹配的模式形式为 `(,x,y)`。Byrd 说明,虽然无需深究逗号在语法层面的全部细节,但可以直观理解为这个双元素模式与传入的列表相匹配,从而使变量 `x` 绑定到 `3`,`y` 绑定到 `4`。匹配成功后,右侧的表达式 `(+ x y)` 便可使用这些绑定变量,顺利计算出结果 `7`。
Byrd 指出,模式匹配非常强大,尤其在与 Scheme 的“准引用”(quasiquotation,即反引号 `` ` ``)和“去引用”(unquote,即逗号 `,`)结合使用时。在 `pmatch` 内部,实际上隐式包含了这种准引用的反解机制。
---
[29:10](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=1750s) 构建解释器骨架:从命名到 Eval-expr
具备了所有预备知识后,Byrd 切换回代码文件开始编写解释器。在着手写逻辑前,面临的第一个难题是起名字:“One thing that we need to do is, you know, decide on the name for our interpreter. That's the hard part, right? So names are hard.” 台下一位观众提议命名为 `Fitzroy`。Byrd 跟着打趣并记下:“Define Fitzroy... All right, so we have a name. This is our life now, and thank you, derailed us all.”
玩笑过后,Byrd 询问大家下一步该写什么。有人回答 `pmatch`,Byrd 指出还差一步:必须先定义接收参数的过程,而“当心存疑虑时,答案永远是 Lambda”(“When in doubt, the answer is Lambda, right?”)。由于调用求值器时传入的是一个待求值的表达式并期望返回其值,Byrd 决定将这个函数命名为 `eval-expr`(尽管他觉得叫 `Fitzroy` 也不错)。Byrd 特别给出了一条安全提示:绝不能把形式参数命名为 `exp`,因为 Scheme 自带求以 $e$ 为底的指数函数 `exp`,一旦参数名与内置函数冲突,在后续编写中很容易引发极其古怪的错误(“If you call your function eval, hilarity may ensue”)。
定义好过程签名后,主体部分正是针对形参 `expr` 展开的 `pmatch` 匹配。整个求值架构由此确立:
```mermaid flowchart TD accTitle: eval-expr 调度流程 accDescr: 展示 eval-expr 接收表达式并通过 pmatch 派发到对应子句的流程
ExprIn["输入表达式 expr"] --> PMatch{"pmatch expr"} PMatch -->|"数值卫句 (,n (? number?))"| RetN["返回自身: n"] PMatch -->|"(add1,e)"| Recur["递归求值: (add1 (eval-expr e))"] PMatch -->|"更多特殊形式 / 应用"| FutureForms["后续扩展 (Lambda, 变量等)"] ```
---
[32:02](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=1922s) 支持自求值数值与引用的重要性
确立了解释器骨架后,Byrd 开始填充能够处理的具体表达式类型。首先是基础数值(例如最开始测试过的数字 `5`)。在 `pmatch` 中,如果仅写匹配模式 `,n`,它会无差别地匹配任何传入的表达式。因此必须引入“守卫”(guard)或谓词(predicate),形如: ```scheme (,n (guard (number? n))) ``` 只有当模式结构匹配且守卫函数(此处为 `number?`)返回真值(即任何非 `#f` 的值)时,该匹配分支才会执行。
现场有观众提问:为什么不直接使用 `cond` 搭配 `(number? expr)` 呢?Byrd 回答:完全可以使用 `cond`,目前的简单场景下 `pmatch` 确实显得大材小用;甚至整套解释器根本不需要宏,仅靠 `car` 和 `cdr` 等列表基本操作就能写出来。然而,等到后续引入带有更复杂结构的 `lambda` 表达式时,`pmatch` 的解构优势就会体现得淋漓尽致。
对于数值的求值结果,Byrd 提问数值应该求值成什么,台下回应:“自身”。于是右侧求值体直接返回 `n`。至此,一个最简的解释器诞生了。Byrd 将代码保存到文件 `interp.scm` 并在 REPL 中加载测试。他邀请观众给出一个测试表达式,有人喊出 `5`。Byrd 幽默地回应:“You will go far, but that's the wrong answer.”(你会大有前途的,但这个回答是错的)。
Byrd 澄清,正确的测试调用必须是 `(eval-expr '5)`,给参数加上引用号。因为如果不加引用,测试表达式在传入 `eval-expr` 之前就会先被宿主 Scheme 环境求值。例如若执行 `(eval-expr (+ 2 3))`,外层 Scheme 会先将其计算为 `5` 再传给解释器,从而给人一种“我们的解释器竟然已经支持加法运算了”的假象: > “Our interpreter works so well that we already can handle addition! Wow, that's really impressive. And if you've written enough interpreters, you've run into this problem before. It's like, whoa, I guess I can turn in my homework early.”
Byrd 指出,这是初写解释器时非常经典的错误,因此向解释器喂入代码时必须严谨地加上 `quote`。
---
[35:06](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=2106s) 扩展原始操作:递归求值 Add1
确立了数值自求值的逻辑后,Byrd 决定为这门解释语言添加更多能力,首选便是 Scheme 内置的自增操作符 `add1`。
在解释器中,他们新增了一个匹配子句来处理列表结构: ```scheme (`(add1,e) (add1 (eval-expr e))) ``` Byrd 借此展示了使用 `pmatch` 的直观性:模式清楚地要求外层是一个 `add1` 列表,里面包含一个子表达式 `e`。这个子表达式 `e` 可以是任意复杂的结构,不仅可以是一个数字,还可以是另一个会产生数值的子表达式(例如嵌套调用 `(add1 (add1 5))`)。
在右侧的求值实现中,解释器递归调用 `(eval-expr e)` 来解析内部子表达式的值,然后借助宿主 Scheme 提供的底层 `add1` 函数对求出的结果加一并返回。Byrd 总结道,通过借用 Scheme 自身的 `add1` 来实现目标语言中的 `add1`,元循环求值的初步机制已经显现,接下来便是在交互环境中载入并验证其正确性。
[36:33](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=2193s) 完善算术操作与条件分支语句
William Byrd 继续在解释器中扩充基础特性。处理一元操作符时,他在模式匹配中加入对 `add1` 和 `sub1` 的支持,并强调测试时必须严格对子表达式进行递归求值,否则很容易出现漏求值的情况。Byrd 调侃道,自己刚才本该使用高大上的“复制粘贴抽象”(copy and paste abstraction),惹得台下一阵笑声。
紧接着是乘法 `*` 的实现。乘法与先前的一元操作不同,它接受两个子表达式 `E1` 和 `E2`。Byrd 提问这里需要进行几次递归调用,观众异口同声回答“两次”。处理方法非常直观:分别递归调用 `eval-expr` 计算出 `E1` 和 `E2` 的值,再用宿主环境的乘法函数将它们相乘。
接下来是条件分支表达式 `if`,其结构包含测试条件(test)、结论分支(consequent)和可选分支(alternative)。对于 `if` 的求值,Byrd 再次幽默地套用“复制粘贴抽象”,并打趣说“Haskell 里大概有个复制粘贴单子(copy and paste Monad)之类的东西吧”。观众询问 `if` 是否具有短路特性,Byrd 澄清:像 `and` 和 `or` 确实会做短路求值,而对于 `if`,必须先求值测试条件;如果测试为真,则只求值第一个子表达式,否则只求值第二个分支,两者绝不会被同时执行。
- `add1` 与 `sub1`:匹配单参数形式,递归求值其子表达式后再进行加减一运算。 - 乘法 `(* E1 E2)`:需要发起两次递归调用分别求值 `E1` 和 `E2`。 - 条件分支 `(if test consequent alternative)`:通过宿主 Scheme 的 `if` 结构调度,仅对匹配条件的那一条分支求值。
---
[39:16](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=2356s) 图灵完备的核心:三大核心规则与过程调用
Byrd 话锋一转,指出当前写出的解释器其实“非常无聊”,因为它本质上只是个计算器,尚未触及整个解释器最美丽的核心。他断言,解释器最精华的部分仅由“三行代码”构成。面对他的提问,台下观众猜了 `lambda`、`apply`、`eval`、`define` 和 `quote` 等各种关键字。Byrd 揭晓,这三行正是:`lambda`、过程调用(application)以及变量查找。除此以外的算术和结构都是次要的,仅凭这三者就足以达成图灵完备。他感慨丘奇(Alonzo Church)的 Lambda 演算早在图灵机之前就已经诞生,甚至哥德尔最初都不相信它是图灵完备的。
Byrd 首先实现过程调用。在 Scheme 极简的语法中,函数调用被表示为包含运算符表达式(rator)与运算对象表达式(rand)的列表。在模式匹配库 `pmatch` 中,这行通配模式必须放在最后,以免覆盖其他具体特性的匹配模式。求值过程遵循常规思路:分别对 `rator` 和 `rand` 递归求值。
求得两个值之后,`rator` 的值代表过程,而 `rand` 的值代表实参。应用过程的方法极其直接——直接使用括号将其包裹起来执行调用。Byrd 强调,这行代码极其精炼,“要是眨一下眼,你就会错过它”;有些人患有所谓的“括号盲症”(parentheses blindness),看不出加了括号有何玄机,但这种行为上的本质差异是毋庸置疑的。
> “The beautiful part of the interpreter has to do with three lines and only three lines.” —— William Byrd
```mermaid flowchart TD accTitle: 三大核心规则求值流 accDescr: 展示表达式如何通过三大核心规则进行求值、环境查找与过程调用。
subgraph EvalRouter["eval-expr 表达式分发"] E["输入表达式"] --> CaseVar{"是否为符号(变量)?"} CaseVar --"是"--> VarLookup["【规则一】变量查找:(env x)"] CaseVar --"否"--> CaseLambda{"是否为 Lambda?"} CaseLambda --"是"--> LamCreate["【规则二】Lambda:构造闭包过程并等待调用"] CaseLambda --"否"--> AppCall["【规则三】过程调用:((eval-expr rator) (eval-expr rand))"] end ```
---
[42:00](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=2520s) 引入环境传递:变量表示与符号查找
在分析 `lambda` 表达式时,形参 `x` 以标识符形式出现。如果 `x` 随后出现在函数体或引用的表达式中,它就成了一个变量引用。变量 `x` 当前的值是多少?Byrd 直言:“现在还不知道,只有在运行时真正发生过程调用时才会揭晓。”如果传入实参 5,那么在函数体内 `x` 的值就是 5。
为了能够在函数体执行时查找与变量绑定的具体值,解释器必须引入一个查找机制,即经典的“环境”(environment)。Byrd 宣布他们将编写一个“环境传递解释器”(environment-passing interpreter)。一旦在参数列表中加入 `env`,整个解释器的架构就发生了质的飞跃,前面提到的三行核心代码全部都与环境紧密纠缠在一起。
第三条核心规则正是变量查找(variable lookup)。在 Scheme 中,变量可以直接用符号(symbol)来表示。为了匹配独立的变量,Byrd 在模式匹配中增加了一个 `symbol?` 的保护谓词(guard)。至于环境的具体内部实现,Byrd 采取了一种极致精简且斯巴达式的设计:将环境直接表示为一个接受单一变量作为参数的过程。既然环境本身就是一个过程,那么查找变量 `x` 的方式就变成了直接调用该环境过程 `(env x)`。
- 过程调用的形式:`(rator rand)` 分别对两者递归求值,然后执行 `((eval-expr rator env) (eval-expr rand env))`。 - 变量的本质:编译/解析期只是标识符,其实际值被延迟绑定到运行时的调用时刻。 - 环境机制:在参数中传递 `env`,用高阶过程表示环境映射,通过直接执行 `(env var)` 完成寻值。
---
[46:25](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=2785s) 闭包的本质:Lambda 与环境扩展
最后是 `lambda` 规则的处理。在 Scheme 中,`lambda` 表达式求值后会生成一个过程(procedure)。Byrd 将过程解释为一种“延迟计算”(delayed computation):在定义函数的当下,由于尚未获取到实参,解释器缺乏足够的信息来执行函数体;唯有等到该过程被真正调用、实参绑定到形参之上、并形成具备正确作用域的环境后,才能求值函数体。
如何表示这样一个过程?台下观众打趣喊道“Lambda”,Byrd 笑着引用电影台词回应:“没错,这招‘60% 的时候,每一次都管用’(60% of the time, it works every time)。”解释器生成的正是一个 Scheme 的底层 `lambda` 过程:`(lambda (arg)...)`。
Byrd 郑重提醒大家厘清概念:这里的 `arg` 并不对应形参名 `x`,而是对应运算对象 `rand` 求值后得到的具体数值。过程调用行与 `lambda` 行在逻辑上紧密相扣——调用时传入实参值,形参 `arg` 便绑定该值。最后,过程被调用时,需要在一个“扩展了的环境”(extended environment)中递归求值函数体 `body`。Byrd 随即着手对之前写好的各行代码进行“重构”(retro-fit),将环境参数 `env` 贯穿传递下去,并引出了下一个关键动作:如何用最简洁的 `lambda` 来构造扩展环境。
> “Lambda expression evaluates to what in Scheme? A procedure... which you can think of as a delayed computation where we don't have enough information to do the computation in the body yet, but we're going to wait until the procedure gets called.” —— William Byrd
[49:10](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=2950s) 用 Lambda 构建高阶环境与闭包
William Byrd 带领现场观众完成了求值器(`eval-expr`)中最核心、最具魔力的闭包与环境扩展部分。当面对“如何扩展环境”这一问题时,观众席给出了“用 `lambda`”的答案,Byrd 笑着称赞道:“没错,确实是用 `lambda`。虽然它是个‘只会一招的小矮马’(one trick pony),但这招实在太厉害了。”他随即写下 `(lambda (y)...)`,并兴奋地表示:“这就是‘极客战栗’(nerd chills)开始的时刻。”
```mermaid flowchart TD accTitle: 高阶环境查找逻辑 accDescr: 展示传入变量 y 后与绑定变量 x 进行比较并决定返回 arg 还是向父环境递归查找的流程
subgraph Lookup["环境闭包 (lambda (y)...)"] Check{"y 等于 x 吗?<br/>(eq? y x)"} Hit["返回当前参数值<br/>arg"] Miss["在父环境中递归查找<br/>(env y)"] end
Check -->|"是 (命中)"| Hit Check -->|"否 (未命中)"| Miss ```
这个所谓扩展后的“环境”,本质上就是一个接受单一参数 `y` 的 Scheme 过程。在它的内部,求值逻辑通过条件判断完成: - 调用 `(eq? y x)` 比较查找的变量 `y` 与刚刚绑定的形参 `x`。 - 如果二者相等,则直接返回实参求值后的值 `arg`。 - 如果二者不相等,则执行 `(env y)`,把查找任务委托给上一层旧环境。
Byrd 强调,这个最内层的 `lambda` 构成了扩展环境,而外层的 `lambda` 则构成了所定义的程序函数(Procedure)。这种在解释器内部同时将环境与过程均表示为函数的设计,被称为环境与过程的高阶表示(Higher-order representation)。在这种表示下,函数应用分支(Application)无需显式操作数据结构;但 Byrd 指出,如果未来改用列表(List)等纯数据结构来表示环境和过程,原本写在 `lambda` 分支里的闭包构建工作,就会挪到应用分支(Application)中去完成。
---
[51:36](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=3096s) 修复初始环境与阶乘测试成功
在写完核心逻辑后,Byrd 准备测试这个解释器。当尝试调用 `(eval-expr '(+ 1 6))` 时,系统立刻报错,观众席敏锐地提醒他忘记传入初始环境。Byrd 称赞道:“非常聪明,你说得对!”那么最底层的空环境(Empty Environment)长什么样?答案依然是 `lambda`:
```scheme (lambda (y) (error 'lookup "unbound")) ```
只要试图在空环境中查找任何未绑定的变量 `y`,系统就会抛出 `unbound` 错误。修复之后,基础算术运算返回了正确的 `7`,查找未绑定变量 `x` 成功报错,恒等函数 `((lambda (x) x) 5)` 也正确求得 `5`。为了进行终极测试,Byrd 又补上了一个 `zero?` 条件分支。
接下来是检验解释器完整性的终极考验:使用 Dan Friedman 所谓的“穷人版 Y 组合子”(Poor Man's Y Combinator)来运行递归阶乘(Factorial)。Byrd 解释说,当前的微型语言里既没有 `define`,也没有用于相互递归的 `letrec`,但因为有强大的 `lambda`,便能通过纯粹的函数构造达到不动点(Fixed point)并实现递归。当他在黑板上的解释器中把这串复杂的阶乘表达式送入求值并成功打印出计算结果时,全场响起掌声与欢呼,Byrd 赞叹道:“Awesome, well done!”
---
[55:08](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=3308s) 剔除“废码”:写在 4×6 索引卡片上的宇宙钥匙
验证成功后,Byrd 笔锋一转,开始对刚刚写出的几十行代码进行大刀阔斧的“净化”。他半开玩笑地宣称:“除了最后三行,前面加的所有分支全都是‘毒瘤’(abomination)!”他一口气把数字常量、`zero?`、加减法、`if` 表达式全部删掉,只保留了最纯粹的三个分支:变量查找(Variable lookup)、抽象(Lambda abstraction)和应用(Application)。
```mermaid flowchart LR accTitle: 极简求值器的三大核心支柱 accDescr: 展示仅剩的三行核心解释器架构:变量引用、函数构造与函数调用
subgraph CoreInterpreter["3×5 索引卡片求值器"] Var["1. 变量查找<br/>(lookup x in env)"] Abs["2. Lambda 抽象<br/>(构造高阶过程闭包)"] App["3. 函数应用<br/>(求值算子与操作数并调用)"] end
Var ~~~ Abs ~~~ App ```
Byrd 指出,这仅有三行核心逻辑的代码就是著名的“写在 3×5(或 4×6)索引卡片上的解释器”。他赞叹道: > “That is the magic. Okay, this is the key to the universe. You have everything here.”(这就是魔法所在。这就是解开宇宙的钥匙,你所需要的一切都在这里了。)
- **极简主义与图灵完备**:无需内置数字,数字可以通过丘奇编码(Church encoding)实现;无需内置 `if`,条件分支同样可以用函数编码。所有这些为了实用性与效率添加的语法糖都可以剔除,仅凭这三行代码就达到了完整的图灵完备性(Turing-complete),甚至其背后的 Lambda 演算模型在历史上比图灵机出现得更早。 - **环境传递求值器**:该程序本质是一个按值调用(Call-by-value)、基于环境传递的 Lambda 演算解释器。 - **可扩展性演进路径**: - **状态与可变性(Mutation)**:在此解释器中引入 Store(存储),即可支持类似 Scheme 中 `set!` 的赋值操作。 - **延续与控制流(Continuations)**:对该解释器实施 CPS 变换(Continuation-Passing Style),把程序未来的计算表示为一个延续过程;若进行双重 CPS 变换(CPS twice),就能得到限定延续(Delimited continuations),进而模拟任何现代控制流结构。 - **作用域规则转变**:只需修改变量在环境中的查找方式,便能轻松在词法作用域(Lexical scope)与动态作用域(Dynamic scope)之间切换。
Byrd 动情地回顾了导师 Dan Friedman 对所有学生的教诲:拿一叠 4×6 的空白索引卡片,花上 45 分钟一遍又一遍地手写这几行解释器代码,“直到你的眼睛开始流血,将它深深烙印在你的大脑和心灵之中,你就永远不会忘记它”。只要彻底参透并亲手推动它运转,就能领略计算理论中所有可计算函数的终极奥秘。
---
[59:38](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=3578s) 重读麦卡锡:等号的双向性与关系式视角的开启
在演示完高阶解释器后,Byrd 将话题转向这套思想在全新语境下的深刻演化。他展示了约翰·麦卡锡(John McCarthy)的经典论文《A Micro-Manual for LISP - Not the Whole Truth》(LISP 微型手册——并非全貌)。在该论文中,麦卡锡以极其简练的数学规则定义了 `cons` 以及名为 `value` 的 Lisp 求值器。
Byrd 引导观众敏锐地观察麦卡锡论文中的公式表达:麦卡锡写下了 `value(e, r) = v`,即表达式 `e` 在环境 `r` 下“等于”值 `v`。关于这个不起眼的等号,Byrd 发出了深刻的反思: > “The notion of equality is actually one of the most subtle notions in all of mathematics and logic and computer science. Anyone who thinks they understand equality as just kind of some throwaway idea hasn’t thought about it hard enough.”(等同性的概念实际上是整个数学、逻辑学和计算机科学中最微妙的概念之一。任何认为自己理解了等同性、并把它当作随手可抛的简单概念的人,都还没有对其进行足够深入的思考。)
Byrd 指出,传统编程语言、解释器和编译器的思维定势,总是把那个等号视为“从左到右”单向流动的单行道:给定一段表达式,写一个求值函数或编译器把它单向运行出最终的值。然而,从数学和逻辑关系的角度来看,等号两边本应具备对等的对称性。如果打破从左向右的单向求值枷锁,把求值器视作一个真正的多向关系(Relation),计算将展现出完全不同的广阔天地。
[01:01:02](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=3662s) 把等号当真:关系型编程与 miniKanren 解释器
William Byrd 将视线从常规的求值函数拉回到一个根本性的数学问题:在普通代数中,等号是双向的约束,而在传统编程中,求值往往只是一个单向箭头。高中代数教大家解方程时,核心是通过 $x$、$y$、$z$ 等未知变量推导让等式两边成立的数值。Byrd 提出了一个大胆的前提:“如果我们认真对待等号会怎样?如果我们认真地说,好吧,这就像代数,对吧?”(“what if we seriously said all right well this is like an algebra right”)。为此,他和 Daniel P. Friedman、犹他大学的 Michael Ballantyne 以及 Greg Rosenblatt 等学者耗费了整整 12 年时间,在逻辑/关系型编程语言 miniKanren 中构建了一门解释器。
```mermaid flowchart LR accTitle: 传统解释器与关系型解释器的对比 accDescr: 对比传统求值单向流动与关系型求值双向约束的运行机制
subgraph Traditional["传统解释器(单向计算)"] E1["表达式 Expr"] -->|"求值 eval"| V1["值 Val"] end
subgraph Relational["关系型解释器 miniKanren(双向约束)"] E2["表达式 Expr 或未知量?"] <-->|"eval-expo 逻辑关系"| V2["值 Val 或未知量?"] end ```
Byrd 指出,这个在 miniKanren 中用 `eval-expo` 实现的解释器虽然不能像极简 Lisp 一样缩印在 3×5 英寸的卡片上,但也只有 43 行代码左右,且结构与数理逻辑中的操作语义(Operational Semantics)完全平行。在现场加载代码并启动 miniKanren 查询系统时,Byrd 调侃道:“在必须加载文件之前,一切都很好,对吧?这种破事可没有数学支撑,大概得用 Monad 之类的垃圾玩意儿来解决。”(“it's all fine and good until you have to do things like load a file right there's no math for that probably a monad or something junk for that”)。进入系统后,解释器隐去了初始空环境,表达式和计算结果作为关系的两个端口并列存在。在最基础的正向查询中,向表达式端口传入数字 `5`,系统便如实推导未知量 $X$ 为 `5`;传入恒等函数 `((lambda (x) x) 5)`,系统同样正确解出其闭包求值结果为 `5`。
- 该关系型解释器基于逻辑编程语言 miniKanren 编写,核心关系命名为 `eval-expo`。 - 解释器的形式化逻辑与教科书式的操作语义规则几乎逐行对应,总长度仅约 43 行。 - 在 miniKanren 查询中,传统函数的“输入参数”与“返回值”被降维为平等的逻辑项,均可放入逻辑未知量。
---
[01:06:26](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=3986s) 逆向程序生成:“我想要奶昔”与 99 种说“我爱你”的方式
一旦求值过程变成了代数方程,系统就具备了逆向求解程序代码的能力。Byrd 演示了这一机制:固定输出端口的值为列表 `(I want milkshake)`(我想要奶昔),而将代码表达式端口设为未知变量进行求解。系统首先给出的解是直接引用字面量 `'(I want milkshake)`;随后要求给出更多解时,系统推导出了一个由无参匿名函数包裹并立即调用的复杂程序 `((lambda () '(I want milkshake)))`;紧接着,系统生成了通过 `car` 获取嵌套列表头元素的程序 `(car '((I want milkshake)))`。
Byrd 结合犹他大学同事 Matt Might 的博客故事作了生动的引申:Matt Might 曾在情人节写过一篇题为《在 Racket 中说“我爱你”的 99 种方法》(*99 ways to say I love you in Racket*)的博文。Byrd 现场使用 `run 99` 指令,让解释器当场自动合成了 99 个求值结果均为 `(I love you)` 的 Scheme 表达式。这些自动生成的代码包含各种嵌套调用、高阶函数和列表操作构造,每一段程序都能在标准 Scheme 环境中合法且准确地跑出这句表白。
---
[01:09:02](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=4142s) 解出 Quine 与逆向列表追加(Append)
在成功生成常规程序的基础上,Byrd 将问题引向了计算机科学领域的经典难题——Quine(自产生程序,即输出结果与自身代码完全一致的程序)。他提到 John McCarthy 在 1960 年的奠基论文中曾留下一道难题:“一个高难度的数学练习:寻找一个列表(即程序表达式)e,使得 e 的值等于 e”(“a difficult mathematical type exercise find a list e that means a program expression e such that the value of e is equal to e what is that called a quine”)。在 miniKanren 中,解决这个问题仅仅需要书写一行代数等式:要求求值关系的表达式与目标结果绑定到同一个逻辑变量 `e` 上。系统率先给出了数值自求值(`5` 求值为 `5`)和布尔自求值(`#t`、`#f`),随后经过简短推导,自动搜寻出一段符合严格 Quine 定义的高阶闭包构造代码。
```mermaid flowchart TD accTitle: 利用关系型解释器逆向推导代码与输入 accDescr: 展示关系型解释器在 Quine 生成和 append 逆向参数推导中的应用场景
subgraph QuineGen["Quine 生成"] Q["求解: eval(e) = e"] --> S1["简单平凡解: 5, #t, #f"] Q --> S2["高阶非平凡解: 自产生闭包表达式"] end
subgraph RelAppend["列表追加 append 逆向求解"] Def["解释执行递归 append 定义"] --> InputSolve["设定结果: '(a b c d e)"] InputSolve -->|"已知右侧参数 '(d e)"| SingleVar["解出未知参数 X = '(a b c)"] InputSolve -->|"双未知数求解"| MultiVar["解出 X 与 Y 的所有拆分可能"] end ```
随后,Byrd 展示了 Michael Ballantyne 提出的方向:在解释器内部运行更复杂的实用程序。Byrd 用 `letrec` 编写了一个标准的递归列表拼接函数 `append`,其逻辑是检查列表 `L` 是否为空,空则返回 `S`,否则递归取头并 `cons` 到剩余部分的拼接结果上。当正向运行拼接 `'(a b c)` 与 `'(d e)` 得到 `'(a b c d e)` 验证无误后,Byrd 颠倒了计算的方向:将结果固定为 `'(a b c d e)`,并将第一个输入参数替换为未知变量,询问“什么列表和 `'(d e)` 拼接能得到 `'(a b c d e)`?”系统立即秒推解出 `'(a b c)`。这种双向推演不仅限于单参数,即使将输入参数同时设为两个未知数 $X$ 和 $Y$,关系系统也能自动枚举出将结果拆解为两个子列表的所有有效组合方案。
[01:12:47](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=4367s) 关系式解释器的双向性与等号的真义
William Byrd 现场展示了关系式解释器强大的双向求解能力。他提出一个查询:寻找哪两个列表拼接起来能够得到 `(A B C D E)`。解释器给出的第一个解是空列表 `()` 与 `(A B C D E)`;随后他将查询方式换成 `run*`,解释器一口气找出了所有可能的分割配对组合。Byrd 指出,熟悉 Prolog 或 miniKanren 等逻辑编程语言的人对这种查询并不陌生,但这里的关键在于:“请注意,我们并没有去写一个专门的逻辑程序,我们只是把一个普通的 Scheme 程序放进了我们的解释器里。”
```mermaid flowchart LR accTitle: Bidirectional Execution of Append accDescr: Diagram showing how a relational interpreter solves for append inputs and outputs symmetrically. subgraph Inputs["自由逻辑变量"] L1["变量?x"] L2["变量?y"] end subgraph Engine["关系式解释器 (miniKanren)"] App["(append?x?y) = '(A B C D E)"] end subgraph Results["反向求解全解集"] R1["'() 与 '(A B C D E)"] R2["'(A) 与 '(B C D E)"] R3["... 其余所有分割组合"] end Inputs --> Engine Engine --> Results ```
通过这一操作,计算范式发生了本质转变。Byrd 强调:“我们正在严肃地对待等号——我们主张‘相等’真的就意味着‘相等’,而且等号本身并不具备方向性,我们理应能够求解任意一侧的未知项。”不仅可以反向推算输入,如果向系统提供完整的输入与输出(比如输入 `(A B C)` 与 `(D E)`,声明输出为 `(A B C D E)`),miniKanren 会返回一串代表一致性满足的逻辑变量符号,证明命题成立。
- 传统的函数调用具有严格的输入到输出的单向性,而关系式解释器消除了这一限制。 - `run*` 能够穷尽搜索空间,返回匹配该等式的所有解组合。 - 逻辑编程的核心优势在于不需要编写专用解算器,而是借助语义约束自动双向推演。
---
[01:13:56](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=4436s) 迈入程序合成:从推导变量到“狡黠的精灵”
既然逻辑变量可以放置在输入和输出位置,Byrd 顺势向听众发问:代码里还有哪些地方可以塞入逻辑变量?答案是:任何地方。Byrd 现场做了一个实验,把代码中原本写着符号 `s` 的位置替换为一个代表未知表达式的逻辑变量,随后调用 `run 1`。解释器准确无误地把被抹掉的 `s` 推断了出来。这一刻标志着演示正式跨入“程序合成”(Program Synthesis)的领域。开发者只需指定预期的输入与对应的输出,利用关系式解释器的语义作为逻辑规则,系统便会通过搜索和约束求解,自动推断出缺失的代码碎片。
然而,当 Byrd 尝试把原本的函数名 `append` 挖空替换为逻辑变量时,意想不到且引人发笑的事情发生了。解释器给出的第一个解并不是大家预期的 `append`,而是一个直接忽略入参、永远硬编码返回 `(A B C D E)` 的匿名过程。面对台下的哄堂大笑,Byrd 调侃道:“miniKanren 就好像在说:‘有种你证明我是错的啊!’”为了制服这个像“阿拉丁神灯里的狡黠精灵”一样钻空子的解释器,Byrd 增加了测试样例——不仅要求它处理 `(A B C)` 和 `(D E)`,还要求处理两个空列表并返回空列表。有了多组样例的约束,解释器被迫收敛,终于正确合成了 `append`。当进一步要求生成第二个解时,系统立刻又给出了一个零参数的可变参数函数包装调用,再次展现了逻辑系统寻找捷径的滑稽“智慧”。
“我们有能力以‘期望的输入及其对应的期望输出’这种形式来指定信息,并借助我们编写为关系及逻辑编程系统的解释器语义来进行推断——本质上就是进行搜索和约束求解,从而推断出缺失的值。”——William Byrd
---
[01:17:21](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=4641s) Barliman 工具与基于示例的交互式合成
原生 miniKanren 在无优化状态下进行程序合成极其缓慢,因为随着代码变大,搜索空间呈指数级膨胀。为此,Byrd 介绍了由他与 Greg Rosenblatt、Michael Ballantyne 等人联合开发的工具——Barliman。Barliman 的底层包含大量剪枝优化,运行速度比朴素版本快了约 1000 万倍;前端则是 Byrd 自学 Swift 编写的极简图形界面。在该界面左上方,函数的结构被大量挖空(例如定义为 `define` 一个未知函数名 `,A`,接受未知参数列表 `,B`,函数体也是未知的逻辑变量 `,C`)。
```mermaid flowchart TD accTitle: Barliman Synthesis Workflow accDescr: Flowchart illustrating how Barliman synthesizes programs from incremental test examples. subgraph UI["Barliman 界面"] Code["挖空模板: (define,A (lambda,B,C))"] Tests["测试示例集合 (I/O Examples)"] end subgraph Solver["优化搜索核心 (1000 万倍加速)"] Search["剪枝约束求解器"] Gensym["Gensym 机制 (杜绝字面常量作弊)"] end subgraph Output["合成演进"] Draft1["阶段1: 常量硬编码返回"] Draft2["阶段2: 条件分支与单层解构"] Final["阶段3: 递归调用生成完整 append"] end Code & Tests --> Search Search --> Gensym Gensym --> Draft1 --> Draft2 --> Final ```
在演示中,Byrd 逐步向 Barliman 提供示例: 1. **第一个测试**:输入两个空列表 `()` 与 `()`,期望得到 `()`。Barliman 几毫秒内给出的解是:一个返回 `()` 的全通函数。 2. **第二个测试**:追加 `'(a)` 和 `'(b)` 输出 `'(a b)`。Barliman 迅速生成一个 `if` 判断:如果第二个参数为空则返回空,否则返回字面常量 `'(a b)`。 3. **引入 Gensym**:为了杜绝这种硬编码字面常量的“作弊行为”,Byrd 引入了生成符号(gensym)。系统必须保证测试中的特定符号绝对不会出现在生成的源码中,从而迫使合成器必须通过结构性操作来转移数据。 4. **第三个测试**:增加一个长度为 2 的列表样例。Barliman 停顿思考了片刻,屏幕上终于跳出了递归调用,完整合成了标准的 `append` 算法核心逻辑。
现场 Byrd 还打趣地跟听众互动,当自己不小心敲错测试输入时,台下观众立即指出错误,Byrd 笑着回应:“有没有人想来 Barliman 团队当 QA 测试员?”
---
[01:21:55](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=4915s) 极限测试驱动开发与后台自动定理证明
Byrd 进一步展示了 Barliman 超越普通代码合成器的潜能:将其作为一种极致的“测试驱动开发”(TDD)实时辅助编辑器。假设面临一个合成器由于搜索空间过大而无法一步到位的复杂任务,开发者可以先写测试,然后由人类亲自编写代码骨架,并留下若干挖空的占位符表达式。在输入过程中,Barliman 的后台线程会持续运转,不断验证用户当前键入的代码与既有测试样例之间是否存在逻辑矛盾。
为了验证这一点,Byrd 在编写 `append` 的条件分支时,故意在判断列表为空后尝试返回错误的变量 `l`。Barliman 瞬间将该测试标红并报错拒绝——“电脑说不行”(Computer says no)。Byrd 解释说,这是因为后台的 miniKanren 本质上是一个定理证明器(Theorem Prover),它能够严格在数学层面证明:用户当前写下的不完全代码片段,与某个给定的测试用例在逻辑语义上是绝对不相容的。
“你可以只把它当成一个编辑器来用,它会在后台持续耗尽你的所有 CPU 核心、温暖你的公寓,并不顾一切地试图证明——请注意这真的是一种‘证明’,因为 miniKanren 本身就是一个定理证明器——你所编写的部分指定的代码,实际上与你的某一个测试是不相容的。”——William Byrd
- 实时不一致性检测能精确定位冲突,但不代表一定是代码写错了,也可能是测试本身有 Bug,甚至是底层解释器的语义定义存在漏洞。 - 无论出错的原因属于哪一种,系统都可以百分之百断定代码与规范之间存在无法调和的矛盾。 - 这种融合了定理证明与不完全程序规约的技术,已经开始走向实际应用,并在更广阔的程序合成前沿领域展现出巨大价值。
[01:24:20](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=5060s) 关系语义、程序合成与最美程序的秘密
William Byrd 谈到程序合成(Program Synthesis)领域目前正在经历一场复兴,但他认为他们团队的独特之处在于实现合成的方法:回归讲座一开始展示的那段优美的解释器代码,重新审视其最初的数学描述,并“把等号真正当回事”。这种做法将传统用于形式化规范的关系语义(Relational Semantics)直接转变为可执行代码。团队设计了 miniKanren 语言来优雅地编码这些关系,并辅以大量的搜索优化。一旦将解释器写成关系,就能玩起强大的“填空游戏”(完形填空式程序合成)。
```mermaid flowchart TD accTitle: 基于 miniKanren 的关系式解释器架构 accDescr: 展示了如何将数学定义的关系语义编码为 miniKanren 解释器,进而通过约束求解实现双向执行、程序填空合成以及定理证明。
subgraph RelationalCore["理论与实现"] A["数学形式规范<br/>(关系语义中的等号)"] --> B["miniKanren 关系编码<br/>(消除输入输出方向)"] B --> C["高度优化的<br/>关系式解释器"] end
subgraph Capabilities["衍生能力与应用"] C --> D["正向求值 / 逆向生成<br/>(如生成 Quine)"] C --> E["填空式程序合成<br/>(根据测试样例补全代码)"] C --> F["验证器逆转<br/>(Proof Checker 变为 Theorem Prover)"] end ```
Byrd 指出,这种关系化思路具有极高的通用性,例如将一个证明检查器(Proof Checker)写成关系,就能直接把它变成自动定理证明器(Theorem Prover)。他推荐感兴趣的观众观看他和 Greg Rosenblatt 在上一届 Clojure/conj 上所作的演讲,其中展示了更多范例。随后他向社区发出邀请,推荐访问 minikanren.org,并欢迎大家参加他在周末举办的线上 Hangouts(分为入门与进阶系列),甚至表示如果有人想参与研究、改进工具的 UI 或者单纯聊聊,“给我发封邮件,打个招呼,我们一起去喝杯奶昔”。
在总结演讲主题时,Byrd 再次赞叹用 Lisp 编写的高阶解释器是何等精妙:它不仅极其紧凑,融合了计算机科学的核心思想,而且无论从无限解释器之塔、元循环、程序变换还是关系语义的角度去审视它,每一次换个视角,它都能揭示出全新的奥秘。William Byrd 总结道:“从某种意义上说,我们对解释器了如指掌,但在另一种切实的意义上,我绝不会猜到只要把那个程序用逻辑编程语言编码,你就能做到这种事情,但事实证明你确实能做到。”他呼吁大家花时间深入研读并理解这一经典作品,寻找属于自己的观察视角。
- 推荐参考资料:William Byrd 与 Greg Rosenblatt 在 Clojure/conj 上的演讲,深入展示了关系编程与合成的应用。 - 社区入口:访问 minikanren.org 获取研究资料;Byrd 在周六和周日定期主持入门与高阶 Google Hangouts。 - 核心哲学:同一个微小(few-line)的核心程序,换用关系逻辑来执行,就能从普通的“解释器”蜕变为“程序合成器”。
---
[01:27:36](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=5256s) 问答环节:高阶元约束与启发式加速
在全场掌声之后,进入了简短的现场提问环节。第一位观众提问:既然测试用例被当作程序的约束条件来猜测未知代码,那么能否施加“元约束”(Meta-constraints)?例如规定“必须是常数时间算法”或“内存占用为 $O(1)$”?
Byrd 回答称这是一个极好的问题。在程序合成中,核心难点在于如何明确形式化你对程序行为的预期。目前他们除了使用输入输出测试,还可以使用类型推导(以相同风格编写关系式类型推断器)或逻辑中的高层性质来约束搜索。关于运行时间或内存复杂度的元约束,Byrd 坦言:“我们目前还没达到可以讨论预期运行时间那种程度,尽管那确实是我非常希望能做到的事情。”不过,程序合成学界已有其他研究团队在专注解决带有预期渐进复杂度的合成问题。
紧接着,Byrd 分享了他们刚刚开展的一项突破性实验: - 就在演讲前一天,Byrd 编写了一个新版本的技术,让系统学习 Scheme 代码中的常见惯用模式(Idiomatic patterns)。 - 这种学习非常简单,仅通过分析表达式的父节点模式,例如:在 `define` 内部通常会出现 `lambda`;在 `lambda` 内部通常会出现 `if` 或 `cond`。 - 将人类的编程风格先验知识融入关系式解释器中进行特化,而不仅仅依赖纯语义规则。 - 初步实验显示,仅仅引入这种极简的代码结构模式先验,“看起来就将合成速度提升了许多个数量级”(speeds up synthesis many orders of magnitude)。团队目前正在探索如何将该技术与现有的各项搜索优化相结合。
---
[01:29:52](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=5392s) 问答环节:环境作用域与搜索空间的确定
第二位观众针对之前的代码补全演示提出了疑问:“在给出 `append` 答案的例子中,系统是如何看待搜索空间的?它怎么知道要找到 `append`,`append` 是如何进入搜索空间的?”观众注意到系统并非凭空猜出递归,最开始甚至猜过直接返回参数列表的简单函数。
William Byrd 解释了其中的机制: - 搜索并非漫无目的地在所有可能的符号中乱撞,而是完全由解释器内置的环境(Environment)与作用域机制决定的。 - 在关系式解释器内部,团队完整实现了变量查找机制(Variable Lookup)以及 `letrec` 的绑定语义。 - 在对 `append` 进行合成时,未知的空缺代码处于 `letrec` 定义的作用域内部。根据 `letrec` 的语义,被定义的函数名 `append` 在其函数体执行时已经绑定在当前环境中。 - 当解释器在填空过程中尝试为未知表达式寻找合理的变量时,它的规则之一就是:“解释器会去查找当前环境中已绑定的所有变量,逐一尝试,看看是否有助于导出符合测试的解。”因此递归调用天然地包含在候选分支中。
简短的答疑结束后,现场再次致谢并结束了本场分享。
## Notable quotes > [59:38](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=3578s) The notion of equality is actually one of the most subtle notions in all of mathematics and logic and computer science. Anyone who thinks they understand equality as just kind of some throwaway idea hasn’t thought about it hard enough. — William Byrd
> [02:33](https://www.youtube.com/watch?v=OyfBQmvr2Hc&t=153s) And that's the most dangerous way of thinking is to think you understand something right and that there are no kind of new tricks in this. — William E. Byrd
## Mentioned William E. Byrd, Daniel P. Friedman, John McCarthy, Alan Kay, Alonzo Church, Paul Erdős, Ken Shirriff, Michael Nielsen, Kenichi Asai, Nada Amin, David Wise, Henry Baker, Andrew Plotkin, Matt Might, Michael Ballantyne, Greg Rosenblatt, Chez Scheme, Scheme, Lisp, Java, JavaScript, Haskell, Prolog, Racket, Swift, miniKanren, Barliman, The Little LISPer, The Little Schemer, The Seasoned Schemer, The Reasoned Schemer, Essentials of Programming Languages, LISP 1.5 Programmer's Manual, A Micro-Manual for LISP - Not the Whole Truth, Two Sigma, Chartbeat, University of Utah, Indiana University
## Video description Meetup: http://bit.ly/2okyAH3 Audio: http://bit.ly/2qkAczZ
Sponsored and hosted by Two Sigma (@twosigma) and Chartbeat (@Chartbeat)
Description ------------------ William E. Byrd "explores what he considers to be the most beautiful program ever written---a Lisp interpreter written in Lisp---and a few of the many amazing ideas related to this metacircular interpreter."
References
- The Little Schemer by Daniel P. Friedman and Matthias Felleisen - Essentials of Programming Languages by Daniel P. Friedman and Mitchell Wand - John McCarthy's Recursive functions of symbolic expressions and their computation by machine, Part I - LISP 1.5 Programmer's Manual by John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart and Michael I. Levin (see especially page 13!) - John McCarthy's A micro-manual for LISP - not the whole truth - "Maxwell's equations of software" examined by Ken Shirriff - Lisp as the Maxwell’s equations of software by Michael Nielsen - miniKanren, live and untagged: quine generation via relational interpreters (programming pearl) by William E. Byrd, Eric Holk, and Daniel P. Friedman - The Reflective Language Black by Asai, Kenichi - Programming Should Eat Itself by Nada Amin, Strange Loop, 2014
Bio ----- William E. Byrd (@webyrd) is a Research Assistant Professor in the School of Computing at the University of Utah. He is co-author of 'The Reasoned Schemer', and is co-designer of the miniKanren relational programming language. He loves StarCraft (BW & SC2). Ask him about the scanning tunneling microscope (STM) he is building.
[Source](https://www.youtube.com/watch?v=OyfBQmvr2Hc)