技术奇异点

上周三（6/9）早上醒来，发现全世界都在赞叹 WWDC 里宣布的新版 Swift async/await 特性。看了几条信息隐约说是基于 coroutine。尽管从去年起因为对 Apple Silicon Mac 迁移的失望已经把个人项目向 Windows 平台转移，但看在当年研究 Lua coroutine 和 Lisp continuation 下了很大功夫的份上，决定探索一下这个 Swift 语言新特性的细节。特别是在没有 VM 的语言上采用 coroutine 会有什么样的挑战。

这一看发现 Swift 并非仅仅给普通的 coroutine 库加上一点 syntax sugar 而已。这里要提一下，我最早看到的一条相关信息就是抱怨它只在最新的 iOS 15 上才支持。如果这个新特性真的只是普通 coroutine 库的语法糖，那这个抱怨是合理的。但其实并非如此。要解释这点，先回想一下最开始学 coroutine 的时候，一般的库或者 Lua 这样的语言文档如何给开发者展示第一个例子 [1]。在这个例子中会有 coroutine caller 和 coroutine 本身。前者是普通的 code flow，用 resume 来跳转到 coroutine。后者则用 yield 回到 caller。但 WWDC 的介绍视频里显然没有明确或者隐含提到这两者。所以第一步是找出 Swift 的实现和一般 coroutine 概念之间的联系。

一般概念与 Swift 实现

Swift 的 await 操作中止当前的 event-handler，而这个 handler 的 context 并没有丢失，可以在以后被恢复。所以 await 相当于 Lua 的 yield 操作。这说明了几点：

1. 在 WWDC 视频中的例子里，coroutine caller 是 event-loop。视频并没有明确指出这一点，但是从 await 挂起当前 handler 之后可以处理其它 event 这点可以推断出来。
2. 在 iOS 15 中，event-loop 调用 event-handler 不再是普通的函数调用。而是创建运行 event-handler 的 coroutine 并执行它。
3. 视频的例子中，没有明确的 resume 操作。实际的 resume 操作隐藏在 event-loop 代码中。
4. 在视频最后的例子中，continuation.resume() 并不是真的 resume 操作。它只是给对应的 coroutine 做上标记。而 event-loop 在随后的运行中会通过这个标记决定 resume coroutine。

要做到这几点，event-loop 的代码必须改写并用新版的 Swift compiler 重新编译。这就是只有 iOS 15 支持 async/await 的原因。以上是这个 Swift 语言特性和一般 coroutine 概念的对应关系。

Coroutine 的普及度

从上节可以看到，Swift 的 coroutine 的实现，至少在 WWDC 视频中呈现的场景，和 event-loop 紧密集成。我认为这个设计才是能真正发挥 coroutine 价值的关键，而且是以普通水平的程序员能接受的方式。在没有和 event-loop 紧密集成时，coroutine 虽然看起来炫酷，但在实际中处于「叫好不叫座 」 的局面。下面分析一下为什么缺乏 event-loop 帮助的 coroutine 难以体现价值，至少是难以让大多数程序员受益。

从模型能力来说，coroutine 的价值在于提供了独立的 call stack，并且切换开销比操作系统线程低。要体现它的价值就要充分利用其独立 call stack。在《Programming in Lua》中列举了 coroutine 的三种典型用例：iterator，consumer-producer，协作式多任务。 前两类需求用传统的没有独立 call stack 的方法解决并没有很大问题，并不值得引入 coroutine。

那么协作式多任务是 coroutine 最重要的应用场景吗？在多线程如此普及的时代，为什么需要协作式多任务呢？《Programming in Lua》里给出的解释是，协作式多任务可以把 non-blocking I/O 封装成为普通的 blocking 形式。在 2010 年左右，Lua 作者以 socket select 作为例子。虽然也勉强称为「non-blocking」，但这种传统风格的 I/O 并没有显示 coroutine 的价值。从 2013 年后，non-blocking I/O 的形式发生了很大变化，也脱离了 I/O 这个狭义范畴，变成了带有 completion closure 的 async function [2]。所以我们下面要讨论的 coroutine 应用是如何用它封装 async function。

在继续讨论 coroutine 之前，先说说 async function 本身的问题。它用 completion closure 来处理异步返回的结果。这样它的 continuation 就不能通过普通的 code flow 体现。如果要先后使用多个 async function 的话，就会导致 callback hell。现在设想一下：如果能把 async function 封装成某种形式的函数，在 coroutine 中调用这个新函数，它会调用原来的 async function。这个 async function 会立即返回 [3] ，然后新函数会 yield 当前 coroutine。这之后 coroutine caller 定期用某种方式查看 async function 的 completion closure 有没有触发，如果已经触发过就 resume coroutine；此时 coroutine 里接下来的代码就可以自然的处理 async function 的结果。我们可以把这种新的封装形式称为 coroutine-aware async，它可以让 coroutine 的正常 code flow 而不是 completion closure 来处理 continuation。

这种 coroutine-aware async 允许程序代码用普通的 code flow 调用 async function。看起来一切很美好。但我们还没有考虑一个关键问题，实现 coroutine caller 的复杂度。当某个 coroutine 因为等待 completion closure 被 yield 挂起的时候，我们希望 coroutine caller 能利用这个时间去执行其它有意义的任务。这就要求 caller 不能是普通的应用逻辑，而必须是比较通用的 scheduler。而编写 scheduler 并不是大多数程序员想要做，甚至不是有能力做的事情。所以这种 scheduler 一般都会封装在某种库或者框架中。如果这个库或者框架并不是全局掌管整个 app 运行模式的框架，那这个 scheduler 就只能在局部的特定领域使用。所以，对于大多数程序员来说，coroutine-aware async 很少能和他们接触的领域产生交汇。那么问题另一面是，为何不写一个掌管整个 app 运行模式的 coroutine scheduler？那么答案是，在绝大多数 app 中有一个天然的位置适合做这个 scheduler，就是 event-loop。但是 event-loop 被极少数代码垄断，典型的如 OS vender 自己的 UI framework，或者像 Qt 这样接管全局的框架才能做到。而这些垄断者之前并没有在 coroutine-aware 方面迈出步伐。

直到 WWDC 展示的下一版 Swift 提供了这个 scheduler。它的 async 就是 coroutine-aware async。这个新的语言特性是真正能让 coroutine 出现在更多应用代码中的关键。

尝试跨平台实现

赞叹了 Swift async/await 的设计之后，我面临一个挑战。Mac 作为个人计算平台的角色已经被全面向 Apple Silicon 迁移的战略断送。我自己的个人项目完全转向了 Windows 和 C++。最好能在 C++ 上实现 async/await 技术。

首先面临的问题是，Windows 并不像 macOS/iOS 那样大量使用带有 completion closure 的 async function 作为 APIs。好在我实现了一个简单的类似 libdispatch 的 NuoDispatch。只要能在非 main thread 上安全运行的代码都可以通过 NuoDispatch 改成 async function 形式。接下来就是 coroutine 本身的实现。

最先研究的技术是 C++ 20 引入的 co_await。看了之后大失所望。这个特性实现的是 stackless coroutine，就是说 coroutine 的范围只能是直接使用 co_await 的 function。我不明白 C++ committee 或者任何人怎么会在 2020 年还采用 stackless coroutine。编程语言中的 function 今天是一种封装和重用的机制，而不是控制 code flow 的机制。不能想象，本来应该放到第二层 function 中的代码为了用 co_await 必须放到上一层中。我想 C++ committee 设计 co_await 的时候脑子里一定在想 iterator/consumer-producer 这类的应用，设计出一个根本没法用于 event-loop scheduling 的废物特性。

接下来看了一些 stackful coroutine 的 C++ 实现。很多实现基于 POSIX context，不能支持 Windows。而且我个人对 「集成污染」比较敏感。 一番折腾下来，我开始想放弃这方面尝试。

退一步想想 await 配合 coroutine 的意义在于把 code flow 交还给 event-loop。如果不能用 context switch 的方式回到原来的 event-loop，还有没有其它的方式？Windows 的 event-loop 其实只有三到四行代码，而且本身在 call stack 上几乎没有 contextual data。所以答案是 Win16 时代的老技巧：再开一个新的 event-loop。我给 NuoBackgroundTask 添了两个新方法：

Resume() 在第一次执行时会把 NuoBackgroundTask::_work 交付给 background thread 运行。随后它每次被调用时会分发一次 event-queue 里的消息，让其它 event-handler 有机会运行，然后检查 _work 是否已经结束，并返回其状态。 Await() 的实现是简单的：

通过 Resume()，ModelViewerWindow::OpenFile() 从定义两个 completion closure 的方式变成了自然的 code flow。达到和 Swift async/await 在普通 event-handler 中使用同样的效果。几乎任何语言任何 OS 都可以受益于这种设计模式，而不再局限于最新的 beta iOS/macOS 和 Swift runtime。

再审视 Swift Async/Await

回头看 Swift 语言本身的 async/await，把通用的 stackful coroutine 引入 Swift，并与 event-loop 紧密集成。 这是非常聪明的实现 。但是再想一下，目前它也有很大的局限性。对 event-loop 的侵入式修改使老版本的 iOS/macOS 无法支持，对 runtime coroutine 实现的依赖使得 Swift 以外的语言无法使用。

既然 coroutine 和 event-loop 的结合才能降低 coroutine 的门槛让普通程序员接受，其实第二消息循环也可以做到，而且后者不需要依赖汇编代码，POSIX 特有的 API，或者 LLVM 特有功能。这种方式摆脱了 Swift，让 C++ 也能采用同样的自然 code flow 的设计。而第二消息循环对 root event-loop 的非侵入性让 iOS 15 和 macOS 12 以外的 OS 也能支持这个技术。

脚注：

1. 后面关于 coroutine 的术语如果不加说明，都采用 Lua 的术语。
2. 注意这里的 async function 指类似 iOS 14 和 macOS 11 之前的采用 completion closure 的 API 形式。和 async/await 中的 async 不是一回事。后文会把 async/await 中的 async 方式称为 coroutine-aware async。
3. 这里指普通的 function return，而不是触发 completion closure。

我一直是 C++ exception 的反对者。《Programming in Lua（二）－ 异常与错误码》提到 Russ Cox 谈论 C++ exception 的所谓「根本缺陷」。我以前的认识是返回 error code 是最好的错误处理方式。

和返回 error code 不同，exception 会触发 call stack 的回退，从而失去了错误发生时的程序运行状态（指代运行状态的术语是 continuation）。这是我之前极力避免 exception 的最大原因。但是最近几年的实践里我发现即使不使用 exception 很多情况下也难以避免丢失 continuation。比如说，越来越普遍的 asynchronized APIs 让 continuation 在代码中的表达更加复杂，代码稍作简化就会丢掉 continuation 信息。另一个例子是，任何程序都无法避免 crash。在操作文件的过程中发生 crash，错误处理只能由下一次程序运行来完成，而 continuation 毫无疑问已经丢失。

如果使用 exception 并不是丢失 continuation 的唯一原因，就必须在假定 continuation 必然丢失的情况下进行错误处理。

计算机工程中减少对 continuation 依赖的方法是增加数据结构的能力。这点写过 parser 的人都会了解。实际上我以前提到过 exception 很适合关系数据库的 CRUD 操作的错误处理，那么在设计数据结构时把数据库的 two-phase commit 借鉴过来就可以了。当操作数据结构的时候，把要操作的部分（比如某个 tree 的一个 sub-tree，或者某个文件 folder）先复制一份。全部操作成功之后，才用这个拷贝替换原来的数据，只需保证这个替换过程是 atomic 的过程。通常的操作都能满足这个要求，比如指针赋值和文件目录的改名（而且后者是 crash-proof）。

我想 exception 在计算机工程里引起这么大的争议，和错误的教育是分不开的。基础理论很早就对 continuation 和数据的关系有深入的了解，而在介绍 exception 的文章里，谈到 exception-safe 仅仅等同于「正确的 pair 操作」。连 Russ Cox 之类的优秀工程师也会把这个教育问题当成 exception 机制的固有问题。SQLite 之类方案的存在一定程度上缓解了这个争议，不过更根本的方法是应该对常用的数据结构提供 copy-on-write 的复制机制。

一直以来，我都认为编程语言是程序员之间的语言，是人和人交流的工具。主流编程语言最重要的特性是清晰、准确，开发者个人在使用中是否感受到的灵活、简洁、优雅则是次要的。这是把编程语言和同为交流工具的自然语言比较，同时又因为两者构建文化认同的程度有所不同，所得出的结论。

接触高级动态语言也已经有近四年，一直觉得虽然它们并不适合作为程序员交流的工具，但绝对是程序员的工具箱里不可缺少的一样东西。几个月前写了一篇《高级动态语言与软件业》，主要观点是，语言概念相对简单，用法相对固定的静态语言更适合构建商业级别的产品，而高级动态语言只限用于符号推导系统。之后是对 Lua 的学习和《集成污染》。高级动态语言并非我所能认同的交流工具，但又具有不可否认的必要性，我经常重新考虑『编程语言/自然语言』这个类比应该如何涵盖高级动态语言。

今天和别人讨论 Objective-C  vs. C++ ，突然回忆起到半年前看的《 What Technology Wants 》里对自然语言的描述：

The creation of language was the first singularity (注1) for humans. It changed everything. Life after language was unimaginable to those on the far side before it.  …  But the chief advantage of language is not communication but autogeneration. Language is a trick that allows the mind to question itself; a magic mirror that reveals to the mind what the mind thinks; a handle that turns a mind into a tool.

这时我想到自己从未把自然语言的『自省』功用和编程语言联系到一起。也就是上文引用里的所谓『 question itself 』，『 reveals to the mind what the mind thinks 』。如果把『自省』这个元素考虑在内，『编程语言/自然语言』这个类比就更完整。复杂的产品中用户定制和核心算法的符号推导部分更加接近『自省』而非『交流』。而且，很多有经验的程序员都说过，你不一定要用它来开发产品，但是学习一门高级动态语言能让你更了解编程的本质。这和自然语言的『自省』功用更接近。最后，自然语言的『自省』功用大于『交流』，编程语言的『自省』功用也很重要，但应该退居『交流』功用之后。因为毕竟程序员不是机器，他们的思考大部分还是通过自然语言完成的。软件产品也不是机器人，很多功能进化依然是通过用户反馈、迭代开发加更新发布而非简单的定制完成的。

脚注：

1. 顺便说一下，在读到这段文字之前，尽管我知道『技术奇异点』之后和之前就像人和动物的区别，但是我从来没直接意识到自然语言就是史前的奇异点。

写过《高级动态语言与软件业》之后，Alex 回复说 Lua 语言应该符合我的期望。其实我应该早就意识到 Lua 的存在，因为 Lightroom 就是用它作为 policy 部分的编程语言。只是 Lua 的库不如 Python 等语言强大，作为编写应用程序的主力语言还显单薄。但正是因此使用轻量级的 Lua 的开发者很少受到诱惑用它来开发复杂算法和 policy 之外的东西（比如 UI ），那正是我在《高级动态语言与软件业》里所反对的。

另一方面，作为描述算法和 policy 的动态语言的另一个重要条件在《高级动态语言与软件业》里讨论不多，却正是 Lua 的优势 —— Lua 是我所知的造成『集成污染』最少的库。

什么叫做『集成污染』？简单地说，如果系统的构建（ build ）在加入某个模块之前一直好好的，加入这个摸块之后就开始出现问题，这就叫集成污染。这种症状在编译、链接和运行阶段都可能发生。例如，编译阶段的集成污染的可以来自 C 的 macro ，typedef ，条件编译，C++ 的 template 。运行时的集成污染可能来自不同的多线程模型混用。

一个模块能否被顺利地集成到更大的系统中，取决于它希望别的模块如何对待它。一个模块对其它模块的要求越多，越不明确，集成的困难就越大。当这些要求被错误地理解或者无法满足的时候，就变成了集成污染。如果一个模块只是对数据的类型有所要求，那么任何一个可以定义抽象数据结构的静态语言都能很容易的描述这种要求，而且也很容易得到满足。但是，即使是如此简单的需求，也会遇到命名冲突之类的问题。通常这就是 macro 和 typedef 造成集成污染的原因。

接下来，有些模块的要求在『理论上』能够被满足，但是这种要求超出了现有技术的表达能力。C++ template 和多线程就是这样的例子。一个使用了 template 的模块很难用 C++ 语言本身的结构来说明自己的需求。对多线程来说情况就更严重，因为不仅编程语言不能描述线程模型，连数学语言和自然语言也很难清晰描述一个模型对线程使用的期望。所以，基本上集成涉及多线程的模块是一种盲目试错的过程。

更进一步，有些模块的要求是否能被清晰地描述已经不重要，因为这些要求常常是难以满足的。这些模块要求独占 system-wide 稀缺资源。比如，Cocoa 框架把整个应用的很多初始化工作和主消息循环封装到一个黑箱函数 NSApplicationMain() 中，古老的 C++ Framework 如 MFC 也会隐藏 main() 函数。这些库用自己的方式任意使用消息循环和主函数。如此霸道的模块，在系统中是一山不容二虎。《高级动态语言与软件业》提到很多高级动态语言和静态语言的互操作方式仅限于单向发起 —— 能调用静态语言编写的动态链接库，但是不能作为库被其它（静态）语言调用，这就等同于对主函数（有时连同消息循环）的独占。

解决集成污染的方法是各种边界分离。像 macro 、typedef 之类的命名污染可以通过文件分离来解决。终极方法是进程分离加 IPC 。不论如何难缠的集成污染也会在进程边界止步。另一种解决之道是参与集成的模块低调、收敛、谦虚一些。这就是 Lua 的方式。采用 ANSI C 中最成熟的跨平台部分，避免了编译时的错误。放弃对线程和 I/O 的支持，避免了运行时污染。Lua 能做这样的取舍，原因在于有合理的目标，把自己定位为描述算法的符号操作语言，和 hosting 应用的交互限于严格而且有序的符号集合。这让 Lua 成为扩展 C 语言和的方案中最简洁和最可靠的形式。

顺着 Java 、Perl 、Python 一路看去会发现一个有趣的规律。至少那些 Lisp 高手会发现。后一个比前一个更 Lisp 一点。

If you look at these languages in order, Java, Perl, Python, you notice an interesting pattern. At least, you notice this pattern if you are a Lisp hacker. Each one is progressively more like Lisp.

—— 《 Revenge of the Nerds 》

从 Lisp 说起

好好学一门高级动态语言一直是日程上一项安排，但限于精力未着手施行。最近看了以《 Revenge of the Nerds 》为首篇的一系列讨论 Lisp 的文章，很受启发。联系我现在的工作领域，对高级动态语言的应用有些看法和期待。虽然在入门之前妄谈可以被称为『成见』，不过鉴于深入学习并非很小的投入，预先思考一下也有益处。

算法与系统

上面提到的这些文章当然都在正面评价 Lisp ，我也多少赞同。但是个人经历形成的感觉仍然是，Lisp 这样的高级动态语言（或者说以 Lisp 为终极目标不断进化的动态语言）并不会在短时间内 —— 估计十年内，成为解决软件业主要问题的手段。我不想老生长谈『性能』问题。性能的确是个问题，但我认为除此之外还有更重要的问题，在更长时间之内不会被基本解决的问题：动态语言适合编写复杂的『算法』，但不适合编写复杂的『系统』。很难给『算法』和『系统』做形式上的定义或者区分。《 Re: Revenge of the Nerds 》中引用了 Trevor Blackwell 的大致说明：

我认为，在 Web 崛起之前，绝少有程序包含比排序更复杂的算法。你认为 FreeBSD 里有复杂的算法吗？Nortel （我靠，老东家！）交换机的五千万行代码里可能连排序都没有，全是硬件资源管理和错误处理。Cisco 路由器的上百万行代码也没有几个复杂的算法。

Before the rise of the Web, I think only a very small minority of software contained complex algorithms: sorting is about as complex as it got. Can you think of a complex algorithm in FreeBSD? The 50 million lines of code in a Nortel switch probably didn’t even contain a sort. It was all about managing hardware and resources and handling failures gracefully. Cisco routers also have millions of lines of software, but not many complex algorithms.

高级动态语言适合执行简洁符号的复杂变换和推导。这类问题具有令纯脑力工作者愉悦的挑战性，属于『优雅』的问题。因此，哪怕能让这些问题的表达和解决更优雅一点点，动态语言的设计者和拥护者也会真诚地付出巨大努力。另一方面，复杂系统没有令人愉悦挑战性，包含无数细节，属于脏活累活。这是高级动态语言不擅长的或者说不屑于的。

优雅的，在智力上具有挑战性的，纯粹的符号问题可以由一个人或者一个很小的团队独立完成。为解决这类问题设计的语言更注重问题本身的表达，是高度简洁和脱离具体平台的，但是其互操作性也受到限制。

复杂的充满细节的工作则需要整个业界协作。需要芯片级别、系统集成级别、操作系统、库、和应用不同级别的互操作。这种复杂的互操作不可能通过简洁的符号来完成，取而代之的是 C 级别的 application programming interface 和 application binary interface 。曾经认为以摩尔定律带来的性能提升和业界的标准化努力能逐渐消除这类细节化的工作，但是实际趋势说明这种预计是错误的。首先是对应用的需求总是超过摩尔定律的发展，今天的 mobile 应用和 3D 应用是以前难以想像的。二是人们和计算机的交互总是不断脱离已经定义的符号范围，几十年前是命令行，几年前是菜单和按钮，今天是各种 drag and drop ，scrolling ，gesture ， multi-touch ，未来将是 Kinect 和我们现在还想像不到的东西。

高级动态语言能承担的不过是整个系统中可以被简单符号定义的那部分，正如很多文档中把高级动态语言编写的算法部分叫做 kernel（不要和操作系统 kernel 混淆），只是一个小小的硬核。核内代表优美的数学推导。而外围的复杂系统才是把符号对应到真实世界的建模过程，充满了微妙而且要反复变换的权衡、妥协、近似。

通用和专用

上面所说的高级动态语言的强项限于纯符号问题只是它不能主导软件开发的一方面原因，另一方面，在纯符号问题领域高级动态语言也不是高枕无忧。低级静态语言不适合表达复杂的算法。但是这不表示它们不能。《 Revenge of the Nerds 》也承认，只要是图灵完备的语言都能等价地描述任何算法。当然该文也嘲笑了一番这种做法，它说，一般的方案是：

1. 使用一种高级动态语言，
2. 用（当前适用的静态语言）写一个高级动态语言的 ad-hoc 解释器（为了应付当前的问题凑合实现的不完整功能），
3. 程序员自己充当高级动态语言的人肉解释器。

这种说法似乎成立，当程序员由于种种原因不能使用高级动态语言但是又需要实现复杂算法时，为了使设计清晰不得不自行搭建一层抽象（程序的或者人肉的）。于是，这似乎证明高级动态语言是必需的，只要这种情况是一直成立的。

但是情况会发生变化，当复杂算法足够通用以致为众多领域所需时，软件业对这个算法的投资会达到无需中间抽象而直接用静态语言表示的程度。正如快速傅立叶变换和 H.264 解码有成熟的硬件实现方式，而且不仅仅是几个具体的产品，而是一种脱离具体产品的业界普遍掌握的定式，不需要任何程序或者人肉的抽象。这些通用算法的复杂度虽然很高，却已经不需要『算法 » 高级表示 » 低级等价表示 » 硬件表示』这样的推导过程，而是完全跳过中间步骤。就像小学生每天笔算多位数乘法而不会从十进制定义的角度思考竖式计算原理。定式像生物为了快速行动而做出的不经过逻辑推导的反射行为，也许逻辑是更优雅的智慧结晶，但是反射也是进化的杰作。

我们经常说硬件的发展会减少低级语言的应用领域，但是忽视高级动态语言的应用领域也有类似的时效性。后者的阵地同样不断受到挤压，最终只剩下和各个行业的专业知识紧密相关的专业算法，比如原文中提到的航空管制系统。这些领域原本被认为是 domain-specific language 的适用范围。而动态语言进入这个原本认为应属 DSL 的领域并不奇怪，因为 Lisp 这样的语言里充满了可以把自身调教成另一种形式的 feature ，比如 macro 。按照编程的命名文化，这些创造 feature 的 feature 可以称为 meta-feature 。

虽然动态语言有临时构建类 DSL 语言的能力，但是这样临时搭建的 DSL 必然是千差万别没有标准的，所以用动态语言写成的代码只适合小范围的解决专业问题。。而对于需要大量互操作的问题，对问题本身的优雅和简洁的表示就会退位于对适应不同文化的交流的需求。这就必然退位于概念更为简单，更为固定的静态语言。这方面的反例是试图在通用领域引入 meta-feature 的 C++ 。把过于灵活的语言应用到整个系统，就像现代人和古人用『几何』、『骚人』这样的词语直接对话。

不完美的子语言

我并非用高级动态语言不能成为软件业的主要工具来否定它的前景。相反，我认为一切未成为大众消费级需求的符号变换操作都应该用动态语言编写。需要使用动态语言的领域会越来越多。另一方面，用高级动态语言承担超出这个范围的应用，尤其是在 I/O 和 UI 方面，虽然在产品初期规模较小的原型阶段可能很顺手，但是随着维护期的增长、代码量的扩大和团队的扩大，最后的净收益很可能为负。

我期待的高级动态语言的模式是类似 SQL 的 sub-language 模式，简化到完全省略 I/O ，嵌入到其它语言或者应用中，只关注符号操作。正如 Emacs 和 AutoCAD 提供的 Lisp 接口。可惜这种做法并没有盛行，没有什么高级动态语言真正的努力支持过 SQLite 那种以库的形式在静态语言中 in-process 解释的能力。采用高级动态语言作为算法模块的系统通常要借助 IPC 或者 Web server 来完成互操作。这也让高级动态语言不得不提供 I/O 甚至 UI 支持，成为扬短避长的累赘。而 IPC 在性能和复杂度上的开销也让很多应用用静态语言来凑合描述本该用动态语言描述的算法（ ad-hoc / 人肉解释器）。

我并非 monolithic 的鼓吹者，但是我倾向于把 process separation 作为设计原则而非结构强制。比如，micro-kernel 的强制 user-space device driver 并不成功。而 monolithic kernel 允许设计者自行决定 driver 的结构成就了 FUSE 这样的 user-space driver 。高级动态语言作为一种不能独当一面的语言，最好还是把这种决定权交给应用开发者。高级动态语言并非风格一致的拒绝 in-process 形式，它们通常可以调用静态语言编写的动态链接库，但这种 in-process 交互是单向的，如上所述，动态语言的解释器很少能作为库被其它应用调用。这种单向交互是因为高级动态语言的拥护者很少把自己看作不能脱离静态语言生存的核心，相反，他们把静态语言看作是 legacy ，而且认为高级动态语言才应该是系统的 master 。

这里我们转头看看那个最初来自《人月神话》的著名论断：不论用何种语言，程序员的生产力以『行代码/天』计算的话不会有很大变化，『 bug 数/行』也不会有很大变化。是的，这个论断和我迄今为之的经历没有任何矛盾之处。在我接触过的系统里，程序员用更简洁的语言编写模块会更快，这些模块的 bug 更少，即使有，修改起来也更快。但是，如果系统出现跨模块的问题，若是涉及高级动态语言编写的模块，解决起来会比不涉及这种模块的情况难度高上几个数量级。问题不在于引入高级动态语言模块本身，而在于高级动态语言目前的实现的拙劣的互操作机制 —— 笨重的 IPC ，繁复的参数和数据结构转换。如果这一切有所改观，那么高级动态语应该可以释放更强大的生产力。

只要粗粗看过数据结构，对链表的印象一定是插入、删除操作都很快。不过对 C++ 标准库里的 list（也就是 std::list ）就得多加小心。比如下面的代码：

std::list node_list;
...
NodeData a = node_list.front();
...
node_list.remove(a);

熟悉 STL 的人可能一眼发现其中的陷阱：node_list.remove(a) 可不是一个 O(1) 的操作（虽然经典链表的删除操作是）。这是因为 std::list<T>::remove(const T&) 实际是一个经典链表的查找操作加上一个经典删除操作。虽然能看出这个问题的人也许不在少数，但是犯下这个错误的人也不在少数。而且，当前者遇到后者编写的代码时，修改起来往往很头疼。因为虽然 NodeData 是从链表中取出的，但是它并没有存储前后节点的信息。所以要想把上面的有缺陷的代码改正，必须把所有涉及到 NodeData 参数传递和临时存储的地方都加以修改。所以说，使用 std::list::front() 这样的拷贝语义函数的行为本身看起来就是个错误。

这里先插上两句说说所谓『经典』链表（因为后文会拿来比较）。很多数据结构的书里的链表就是把 NodeData 这个对象本身加上一个 prev 指针和一个 next 指针，用来分别指向前一个和后一个节点。所以『经典』链表的数据结构和节点数据本身由一个对象表示。经典链表对 NodeData 的定义是侵入式的 —— 如果你希望把一个原来和链表操作完全没有联系的对象或者 struct 加入链表，就必须修改它本身的结构。相对的，std::list 的方式是把链表看成一种『容器』，包容原有的对象而无需修改其结构。

所以你的第一反应也许是应该永远用 std::list::begin() 或者 --std::list::end() 之类的操作返回 iterator，相比 NodeData，iterator 更像经典链表的节点，带有前后节点的联系。但是 C++ 永远不会给你简单的方案。这个方案的问题在当在代码的多处拥有指向同一个 NodeData 的 iterator 时，调用任何一个 iterator 或者 list 本身的 erase() 方法都会导致其它 iterator 失效。而且，C++ 标准库仅仅告诉你唯一的以定义行为是其它 iterator 会『失效』。你甚至没有一个 valid() 方法来检验一个 iterator 是否失效。C++ 标准期待的是你无论如何知道这一状态并且决不能再对那些 iterator 做任何操作。

所以 std::list 相比『经典』链表有两个致命问题。第一是直接取出 NodeData 的操作丢失了和 list 本身的联系，让后续操作承受性能损失。第二，『经典』链表可以通过设置 prev/next 让任何拥有 NodeData 指针的代码轻易的判断一个节点数据是否还在链表中，而 std::list 对 iterator 行为的粗略定义让这一点变得不可行。

接下来我们把问题搞得更全面（也更复杂）一些，考虑 NodeData 的生命周期。C++ 标准库一贯的拷贝语义让这个问题得到了（幼稚地）解决。但是对于 std::list 来说，我们已经看到拷贝语义的操作会让取出的节点丢失和 list 的联系，而总是取出 iterator 又会带来失效的问题。

当然，经典链表虽然没有 iterator 失效问题，但是仍然要面对何时销毁节点数据本身的问题。不过，讽刺的是并非所有的数据都是可复制（copiable）的，所以 std::list 里面存储的也经常并非数据本身，而是数据的指针。因此，在同样面对 std::list<NodeData> 的『联系切断』和『iterator 失效』两难之际，std::list<NodeData*> 还必须面对经典链表的销毁节点数据的时机问题。更遗憾的是，C++ 的内存管理法宝 shared_ptr 在这个问题上完全无能为力。一个 std::list< shared_ptr<NodeData> > 同样拥有『联系切断』和『iterator 失效』的矛盾。这时只有经典链表，加上在 NodeData 中实现手工引用计数才算一个比较完美的方案。

链表是 C++ 的好几个设计理念走麦城的地方。链表重在『链』，它的灵活性就在于『链』。把链表作为『容器』，特别是和 STL 其它容器一样保持拷贝语义操作就毁了链表。而且基于拷贝构造和自动析构的共享指针和手工的引用计数相比也并非处处领先。

如果一开始能抛开 STL 那种容器的概念和对数据节点不侵入的要求，C++ 的链表设计不会这么差。比如 Linux 内核的链表设计，把链表节点作为链表数据的一部分，让链表数据包含节点，而不是反之。这样的设计用 C++ 模版也完全可以作到。（当然我更喜欢 Linux 内核的基于宏的设计，而且 Linux 的设计通过一个可被优化的 forced cast 同样保证了类型安全。）

后记：

写这篇 blog 的时候又重温了一下 Java 的 LinkedList 文档，发现 C++ 还不是最差的。LinkedList 的文档是，至少 6.0 还如此 —— 对 LinkedList 做的任何结构更改（什么意思？删除节点算吗？）都会导致所有已经获取的 iterator 失效。什么玩艺，这样的话我还用链表干什么？

C++ 为什么会被设计成现在这个样子，我一直认为和 Bjarne Stroustrup 的个人背景有很大关系。按照 Stroustrup 自己在 《The Design and Evolution of C++》里的描述，设计 C++ 的动机来自于他完成博士论文的时候编写一个模拟器缺乏合适的工具。从这段描述里，我冒昧地认为 Stroustrup 暴露了他早期的局限性，他意识到必须有更好的工具来管理系统的复杂性，但是眼光仅仅局限在源代码的层次。他的模拟器是一个单独的 monolith，在寻求更好设计时，Stroustrup 仅仅追求如何更好的管理这个 monolith 的内部结构，未曾考虑任何更高一级的方法——比如把 monolith 分割成相互协作的更小的模块——来提高系统的可维护性。

C++ 与进程开销

C++ 在 UNIX 上受到的欢迎程度最低，正是因为 UNIX  提供了更多的组织系统的方法，这些方法能够，而且经常是更好的代替源代码级别的方式。UNIX 不仅提供了进程和 IPC，让这些方式成为可能，而且还从一开始就不断寻求降低这些方法的开销，让它们相对于源码级的管理方式——也就是语言——更加有竞争力。所以，在 UNIX 上 C++ 没有获得它在其它一些操作系统中获得的那种主导地位。

在《The Art of UNIX Programming》的3.1.3节说的很清楚，“如果操作系统让创建进程的操作过于昂贵，或者让进程控制的操作过于困难或者过于死板，⋯⋯就会鼓励 (在一个较大的 monolithic 模块内部使用) 像 C++ 一类的源代码级别的内部分层结构，而不是 C 这样的 (在相互协作的小模块中) 相对平坦的内部结构。

我常说一句不太准确的玩笑话—— “C++ 就是微软捧起来的” 。其实也不是全无道理。作为在 PC 发展的黄金时代最广泛应用的操作系统，Windows 没有提供太多的系统级机制来管理应用软件的复杂度，开发者只能着眼于源代码级别的内部结构，寻求 C++ 之类的语言帮助。

C++ 的兴起和 PC 上 anti-UNIX 风格暂时的主导地位有很大关系。Stroustrup 的发明是对 UNIX 上管理系统复杂度的方式的一种不高明的重复。这种重复为那些由于历史原因或者因为经济原因 (比如过弱的硬件支持和操作系统支持) 没有普及 UNIX 文化的领域提供了一种似是而非的，拥有短期效益的替代品，因而受到了欢迎。

C++ 与内部复杂度

UNIX 文化鼓励通过进程和进程协作来降低单独模块的内部复杂度，而不赞成用 C++ 的方式来 “管理” 内部复杂度。事实上，UNIX 文化认为 C++ 的方式在鼓励过度的内部设计而不是有效的对其进行整体管理。

另一方面，C++ 不光忽略了在单个 monolith 的层次之上的管理方式，还低估了现有手段在单个 monolith 中应对复杂度的能力。做出这种错误判断的不只 Stroustrup 一人，在 90 年代操作系统领域兴盛一时的对 micro-kernel 的研究中，研究者和很多业界开发者都认为操作系统内核的复杂度已经到了必需舍弃 monolithic 式的内核设计，由 micro-kernel 加 user-space 进程实现的服务来替代。Linux kernel 的出现及时证明，用 C 这样的技术也足以很好的管理单个 monolithic kernel 的复杂度。Linux kernel 不光和很多 monolithic 内核同样稳定，还在性能和设计复杂度上拥有天然的优势。(比如，对于 Minix 的单线程文件系统的抱怨，其设计者反驳说该 feature 很好实现——但是始终没有真正实现，而对于 monolithic 内核来说，多线程文件系统几乎是自然而然的设计。)

今天，如果你把系统中某个组件的复杂度设计的比 Linux kernel 还高，那是一种罪过而不能被认为是必需使用 C++ 的理由。

结论

C++ 的兴起，在我看来很大程度上是不是一段普通的历史，而是反映了整个业界的一个错误。正如《The Art of UNIX Programming》所说，上世纪80年代，由于各个 UNIX 厂商的愚蠢，UNIX 文化曾经一度奄奄一息。而 UNIX 社区的开发者们又一再忽略兴起的 PC 市场 (而忘记了 UNIX 自己就是在 mainframe 的厂商忽视了 mini-computer 的情形下发展起来的)。在整个世界缺乏 UNIX 文化的情形下，出现了 C++ 这样畸形的尝试。

我承认世界并非完美。有些错误已经成为文化的一部分被保留下来。但是 UNIX 文化因为它强大的生命力终于逐渐回归。这显示出 C++ 不属于那类可以出于历史和文化原因而被永远保留的错误。这个错误至少应该不被扩大，并且可以被逐渐纠正。