计算机百年史 03 · 系统与抽象(1956—2000)

「计算机百年史」系列 · 第 3 篇 / 共 10 篇
按《从铜线到智能——计算机两百年》原书卷次连载。本篇:系统与抽象(1956—2000),共 9 章,约 8.9 万字符。

卷三 · 系统与抽象(1956—2000)卷首语

操作系统不是计算机与生俱来的器官。它没有随第一台通用计算机一同出厂,也没有写在任何一份先驱蓝图里——它是被账单逼出来的壳层。当一台机器的一小时贵过一名工程师的一天,当纳秒级的运算速度与毫秒级的机械输入输出之间裂开一道万倍鸿沟,人类就必须从机器跟前退开,把调度的权力交给一个看不见的中间层。本卷讲述的,正是这道裂谷如何逼出批处理、分时、虚拟内存与整座操作系统的殿堂。

必须预先声明:本卷的技术演进绝非顺理成章。Multics 的乌托邦野心不是 Unix 的垫脚石,它是一场有坚实工程理由的豪赌,输在时机与成本而非远见;Unix 的极简不是品味 superior,而是资源与制度双重挤压下唯一可行的姿态;C 语言重写内核不是"现代软件工程的自然结论",而是一次连它的作者都不敢完全确信的冒险;IBM 的 OS/360 更不是成功叙事的一部分——它以五千人年的代价证明,系统软件不接受人月。这些发明各自生长于各自的约束:冷战军费、反垄断判决、大学预算、乃至一场探亲假。偶然性在这里的密度,不亚于任何一卷。

本卷的主导物理约束只有一条,却贯穿二十章:纳秒级处理器与毫秒级机械存储之间的时延裂谷。批处理用队列绕过它,分时用时钟切片缝合它,虚拟内存用局部性豪赌偿还它——但裂谷从未闭合,只被一层层抽象垫高。每一层抽象都向程序员许诺"你不必关心下层",而每一次系统崩溃、每一次缓存颠簸、每一次缓冲区溢出,都是下层的现实在追讨欠款。本卷的任务,就是把这笔账目的原始凭证,一页页摊开。
阅读指引。 本卷是全书技术门槛最高的一卷:操作系统、虚拟内存、编译器、共识——没有计算机专业背景的读者,建议精读第 024(批处理)、025(分时)、026(Multics)、027(Unix 诞生)这四章叙事驱动的部分,其余(028 C 重写、029 虚拟内存、030 编译器、031 语法形式化、032 SSA 与 LLVM)可以扫读结论段。工程师与计算机专业读者应当全卷精读——这一卷是后续所有卷的技术地基,跳过它,后面每一章的"账单"都会变得难懂。


第 024 章 1956:批处理与操作系统的史前起源

一叠卡片的旅行

1957 年某个工作日的早晨八点半,通用汽车研究实验室的机房窗口前排起了短队——队伍的长度大致与前一天的工程进度成正比:排队的都是来做工程计算的,而他们要算的东西,昨天下午刚从各自的桌子上写完。队首的工程师怀里抱着一叠打孔卡——两千张上下,橡皮筋捆着,边角已经磨毛——那是他昨晚为一次材料应力计算准备的全部:几百行 Fortran 程序、几千个数据、以及十几张写着运行参数的控制卡。机房里的 IBM 704 正在跑别人的作业;轮到他,操作员把卡叠塞进读卡机,机器在两分钟内吃完卡片,算了一分多钟,然后停机,等操作员卸磁带、装下一盘。这套流程里,工程师能做的只有一件事:在窗口外等着,一等就是四五个小时——机器的拥有者给机房立了规矩:作业按提交顺序跑,任何人不得插队,公平是这条规矩唯一的美德。这位工程师在自己的作业上真正花掉的机器时间不到三分钟,而他等了四个小时;更让他难受的是,隔壁桌的同行昨晚只是改了一个数据,今天也排了同样的四小时。要是某张卡在半路掉在地上,顺序错乱,或者程序第 137 行有个逗号打错——整个流程从头再来。

输出要等明天——机房会把结果纸从打印机上撕下来,按作业编号放到取件格子里;编号是他早上交卡时领的,一串没有表情的数字,此刻正替他排队。运气不好,纸上的第一行是语法错误报告,四小时只换来一句“第 137 行逗号位置非法”。这不是某家机房的特殊惨状——它是 1950 年代中期全世界每一台大型计算机的日常。数字的暴政(前一章)刚被集成电路松开一只手,另一种暴政就显了形:机器贵得吓人,跑得飞快,却把大部分生命浪费在两次计算之间的装填、卸载、等人和等人道歉上。解决这道题的第一批人并不是计算机科学家——这个学科当时还没成型——他们是汽车公司研究实验室的工程师,外加一家飞机制造商的同病相怜者。他们也不知道自己在写的东西日后会叫操作系统——那个词还要几年才会被发明;在 1956 年,他们只是把一个令人厌烦的重复流程,交给了世界上最擅长重复的机器自己。他们没有想把这事做成历史第一,只是想让账单变短。他们交出的东西没有名字,后来被称作操作系统。

没有操作系统的年代

把 1956 年之前的计算机机房想成一条手工作业流水线,就不会误解后来的革命。机器一次只能执行一个程序;程序以打孔卡或纸带的形式存在;计算机开机后,操作员先从控制台上的开关与旋钮把一小段引导指令逐位拨进内存,再喂入卡片,等程序跑完,从打印机或穿卡机上取出结果,然后重复整个过程。更早一代的机器连引导都欠奉:工程师在几平米的控制板前手动接线设定运算,机器的状态灯排成一面墙,闪一下表示一位。作业与作业之间的空档全靠人肉填塞:挂磁带、上纸卡、拨开关、核对设备状态。这套流程里没有“系统”可以指责——出错是操作员的错,排队是机房主管的错,等待是谁的错也不是。要理解这种制度为何延续,得看清楚用户是谁:1950 年代中期能碰计算机的机构一只手数得过来——国家实验室、航空与汽车巨头、少数顶尖大学与统计局;机器是机构里最贵的单一设备,机房是可以进出少数人的要地,而程序员与机器的关系,被制度性地隔成递纸条的关系。制度没有恶意,它只是还没有见过另一种可能。行业里甚至发展出一整套操作员的行话与手艺:哪种卡片不能二次过机、哪台打印机挑纸、磁带挂载前要在什么温度下回放——这些手艺没有教科书,全靠跟班学徒式的传承。

代价用钟表结算。作业的“建立时间”——把程序与数据送进机器、挂载磁带、调好设备的全部准备动作——常常比程序真正的计算时间还长;机器越快,这个反差越刺眼:计算以毫秒与微秒计,装填以分钟计,排队以小时计。计算机史上第一道真正的性能裂缝并不在芯片内部,它在芯片与它的外围设备之间。IBM 704 的中央处理器每秒能做几万次运算,而它的读卡机每分钟只能喂几百张卡片——一张卡八十列,读卡机的机械触点要逐列刮过去;打印机每分钟吐一两百行;磁带机快些,也要以秒为单位起停。快与慢之间,横着一道上万倍的速度裂谷:处理器的纳秒对上外设的毫秒与秒,中间没有桥。而当时全世界的处理办法只有一个字:等。CPU 停下来,等读卡机慢慢把卡片变成电信号;操作员停下来,等上一份作业的主人收拾好纸堆。机器贵过人,可人的时间被浪费时,机器也在跟着空转——两头都在付钱,两头都在等待。账算到这里,任何一个成本会计都会得出同一个结论:这种浪费不能再继续了。数学上这叫串行化的荒废——两个速度悬殊的资源互相等待,谁都到不了满负荷。而能得出这个结论并且有能力动手的,往往并非计算机厂商,而是那些被机器账单扎得最疼的大用户。厂商的算盘不同:机器已经卖出去了,装填浪费伤的是用户的钱包,不是厂商的利润——直到用户开始用脚投票,厂商才醒过来接管这块领地。操作系统史上第一条定律因此可以写成:操作系统由痛感最深的一方发明。

底特律派来的监工

通用汽车研究实验室就是被这笔账逼到墙角的部门之一。汽车公司对大型计算的需求出乎外行意料:车身的应力分析、发动机的燃烧模拟、空气动力学的数值求解,全是几十阶上百阶的方程组,手摇计算器与加法员团队早已跟不上型号迭代的节奏。1950 年代中期,实验室购入 IBM 704——当时最快的晶体管化科学计算机之一——用于工程计算;北美航空(North American Aviation,飞机制造商)也在为同一台机器的同类问题头疼:飞机机翼的颤振分析,算量比汽车还狠。两家机构的工程师,通用汽车的罗伯特·帕特里克(Robert L. Patrick)与北美航空的欧文·莫克(Owen Mock),在 1955 年前后决定自己动手。合作的动机里有精明的分担:两家都买了 IBM 704,都在被同样的问题放血,合写一套系统、各按装机量摊成本,比各自为战便宜得多;他们在 IBM 701 旧机器的监视程序(system monitor)思路上扩建,写出了一套输入输出控制系统,1956 年前后成型,得名 GM-NAA I/O——通用汽车-北美航空输入输出系统。帕特里克后来回忆,这套系统的诞生没有任何仪式感——它就是几个工程师把重复劳动写成代码,省出自己的时间;IBM 曾有自己的监视程序方案,但节奏与价格都不合用户的意,于是用户干脆自己动手。顺带一提,“操作系统”这个词本身当时还不存在——早期的这些程序被称作监督程序(monitor)、控制程序或输入输出系统,“operating system”作为标准术语要到 1960 年代初才固定下来。名分的迟到不影响实质:后世的计算机史学家在核对过所有候选者之后,普遍把 GM-NAA I/O 认定为有记录以来的第一个操作系统。

它的能力以今天的标准看薄得像纸:一组常驻内存的监督程序,掌管卡片的读取、磁带的挂载与结果的输出;它没有内存保护——一份跑飞的作业可以直接踩碎监督程序自己,然后整个流程从拨开关重来。早期操作系统的脆弱与它的价值成正比:它越是接管机器的日常,自己崩溃的代价就越大;给这位监工配上护甲,还要再等十年。作业以卡片叠为单位排队,每叠卡片的前几张是控制卡——写明作业标识、账目信息与运行参数;一份作业结束,监督程序自动把下一份装进来,全程不需要人碰开关——监督程序不知疲倦地处理一个又一个作业,实现了作业到作业的自动转接,机器的日夜第一次连成了片。就这么几件事,却在三处改写了历史——而其中最容易被忽略的,是控制卡:为了让监督程序明白每叠卡片的意图,用户必须在程序与数据之外,用约定的格式声明自己的需求。这个“声明”的动作,是操作系统与用户之间签订的第一份契约;它朴素到只是几张打孔卡,却在此后几十年里演化成一门专门的官僚语言——作业控制语言。第一,它为程序提供了统一的共享输入输出接口:程序不再各自为政地驱动硬件,而是调用监督程序提供的服务——应用程序与硬件之间从此有了一层中间人。这个中间人还有一层当时未被充分意识到的意义:硬件的细节从此可以变化,只要中间人的接口不变,写在其上的程序就不必重写——可移植性的种子在这里落了地,尽管要等八年,等到 IBM System/360 用一套指令集统一整个产品线时,才长成参天大树。第二,它把“作业的自动转接”变成了现实:机器空闲时间被成片砍掉。第三,它证明了一件事:操作系统并非 IBM 这样的厂商赐予的礼物,它出自最早的用户在被机器逼急之后的自救。这套系统随后在通用汽车内部的兄弟机构与部分同行间复制流通——愿意采纳的用户把它拷走,按自己机器的脾气做些修改,再把自己的改进传回去。在版权观念尚未覆盖软件的年代,这种基于用户共同体的水平传播,成了业界最早的公共软件流通模式之一;软件作为可复制资产而非每次装机重写的附属品,这个观念本身也随着它传播开来。多年以后回看,这份用户自写的系统还有一层档案学价值:它的痕迹在多个机构的报告与会议记录里保存至今,让“第一个操作系统”的认定有据可查。十几年后PC 世界的共享软件、再后来的开源协作,都能在这条流通线上找到自己的年轮。

   一份批处理作业的卡片叠(1950 年代)  
  
   ┌───────────────────────┐  
   │ 控制卡:作业标识 / 账目  │ ← 谁交的、跑多久、收费记谁账上  
   ├───────────────────────┤  
   │ 控制卡:编译请求        │ ← "先把我编成机器码"  
   ├───────────────────────┤  
   │ Fortran 源程序卡 …几百张│  
   ├───────────────────────┤  
   │ 控制卡:装载数据        │  
   ├───────────────────────┤  
   │ 数据卡 …几千张         │  
   ├───────────────────────┤  
   │ 控制卡:执行 / 输出参数  │  
   └───────────────────────┘  
    ↑ 顺序不可错:错一张,整叠作废重来  
  
   监督程序(GM-NAA I/O,常驻内存):  
   读入一叠 → 编译 → 装载 → 运行 → 写结果  
        → 自动读入下一叠(无人碰开关)  

万倍裂谷与它的卫星

监督程序砍掉了人肉转接,却没有砍掉那道速度裂谷——它只是让人不再直接面对裂缝。批处理机器的日常依然是这样:程序要从磁带读一段数据,CPU 发出指令,然后停下来,空转着等那台以机械速度运转的磁带机慢慢转到位。中央处理器以微秒计时,磁带机以毫秒与秒计时,读卡机更慢——这道纳秒与毫秒之间的万倍时延裂谷,正是本卷的主导物理约束,而 1950 年代的工程师们第一次正面撞上了它。他们的应对方案带着那个年代特有的朴素与昂贵:既然快慢无法调和,那就让它们别待在一起。这道裂谷没有在批处理时代闭合——事实上它永远无法闭合:机械有惯性,介质越大越慢的层级定律至今未破。批处理时代的工程学只是教会了行业与裂谷共存的第一课:不要让最快的部件等待最慢的部件,让队列替它们传话。

1950 年代末的机房里,老练的工程师靠耳朵工作:磁带机的起停声、读卡机的节奏、主机的风扇调门,全是系统状态的广播。裂谷的声音可以被听懂,唯独无法被填平。方案叫脱机批处理。思路是把输入输出从主机身上整个剥离,交给一台不与主机直接相连的廉价机器——所谓卫星机,常见配置是 IBM 1401 这样的商用小机器:打孔卡是它的主场,价格只有主机的零头,坏了自己修。机房的格局因此改成了内外两间:外间是读卡机、打印机与卫星机,一切机械慢活在这里发生;里间是主机与磁带机,只干高速计算。卫星机干两件粗活:把读卡机慢吞吞吐出的卡片内容先整批写到磁带上;把主机写在另一盘磁带上的结果,慢慢送到打印机。主机与卫星机之间不发生任何直接对话——它们只通过磁带交换数据,磁带盘由操作员的手在两间屋子之间搬运。这套安排的账目同样直白:一台卫星机加几卷磁带的价钱,远低于主机每小时空转的损失;用便宜机器伺候贵机器,贵机器的时间才配得上它的价格。主机从此不再与读卡机、打印机这些机械牲口直接说话,只与磁带交换——磁带是当时唯一既便宜又够快的中间介质——每秒几十万字符的读写速度,比读卡机快三个数量级,比主机慢三个数量级,恰好站在裂谷中间当摆渡人。一卷磁带可以存下几十叠卡片的内容,主机从磁带上读一份作业只要几秒,而不是读卡机的几分钟;主机的时间终于大体花在了计算上。这套安排的本质,是把一道速度裂谷拆成了两道可以并行处理的窄缝:卫星机与打印机慢慢磨,主机与磁带快速转,两者的时间轴不再互相拖累。用今天的话说,卫星机是最早的“前端处理机”,磁带是最早的“输入输出队列”,而搬运磁带盘的操作员,是最早的“消息中间件”。它同时也是一次组织学的创新:输入输出从“主机的事”变成“另一个岗位的事”,机房第一次出现了分工——外间的人与里间的人各司其职,而把两者连起来的介质,是可以移动的磁带盘。以今天的眼光看,这是后来一切缓冲、假脱机与异步输入输出技术的直系祖先。它的设计哲学只有一句:当快与慢无法匹配时,先在中间放一个队列。这条哲学此后被反复发明——磁带缓冲了读卡机与主机,内存缓冲了磁带与处理器,磁盘缓冲了内存与网络——每一次都是同一道裂谷在新尺度上的重演。万倍时延裂谷没有被消灭过一次;它只是被一层层队列垫得越来越不碍眼。工程师们给这种垫法起了个稍带自嘲的名字——所有性能问题都可以用一个缓冲区解决,实在不行就两个。

一种叫 JCL 的官话

作业自动转接要成立,监督程序就必须知道每叠卡片想干什么——而这需要一种语言。最早的方案就是控制卡:在作业卡叠的开头插入几张打孔卡,卡片上以约定格式写明“编译这个”“装载那个”“用磁带几号”“把结果打在哪台打印机”。随着监督程序的功能变厚,控制卡的格式也渐渐标准化,最终在 IBM 的体系里长成了正式语言——作业控制语言(Job Control Language,JCL),先用于 7090 系列大型机,此后统治大型机世界数十年。用户在 JCL 里以一叠固定格式的语句向系统声明作业的一切:我需要什么设备、什么数据集、多少内存、出错怎么办。它有着公共机构语言的一切特征——以两条斜杠开头的行为控制语句,命名规则冗长而绝对,语法错误没有商量余地;每一个在大型机时代讨过程序员生涯的人,都记得被 //JOB、//EXEC、//DATA 这几张卡支配的恐惧;一张卡放错位置,作业直接进死信堆,没有人会替你解释原因。“批处理”这个词也是从这条线上叫开的:工程师们把作业攒成批,把批攒成夜,把夜攒成一份按周结算的账单。JCL 的复杂度后来演变成一桩著名公案:一门本该三小时学会的声明语言,最终厚成一本手册——抽象的官僚化,从这里就能看到第一枚细胞。但恐惧归恐惧,JCL 完成了一次关键的抽象:机器需求第一次有了标准文书格式,装填机器的手艺从口耳相传变成了可查文档。与此同时,IBM 在 1950 年代末拿出了官方版本:IBSYS,一套覆盖 704 与 7090 的监督系统,把作业管理、编译器调度与输入输出服务打包成可以随机器订购的标准件。它之前还有一段插曲——1959 年,IBM 709 的用户团体 SHARE 联合做出了一套监督系统,比厂商的货更快落地。SHARE 本身是计算机史上第一桩有趣的制度发明:1955 年由几家大用户自发成立的用户组织,定期开会交换软件、分享补丁、向厂商集体议价;在软件不随机器附赠、厂商各自为政的年代,用户组织就是用户唯一的联邦。用户自造与厂商收编的循环,自此成为操作系统工业的固定剧目。这三代监督系统——用户自写、用户组合写、厂商出品——功能高度相似,真正的差别在流通:第一代靠私下拷贝,第二代靠用户组织分发,第三代随机器合同附送;操作系统从用户自救的手段,变成厂商产品清单上的一行,再变成机器不可分割的一部分。厂商版本、用户版本、机构自研版本并存,一个今天被称作“操作系统生态”的东西,在无人命名它的年代已经成形。

这条路线引出了本章真正的决斗,双方各自握着足以立论的道理。一边是自动化派:机器贵过人,监督程序与脱机卫星把机器利用率成倍拉高,每一分钟消灭的空闲都是真金白银;退一步说,操作员的手终究会抖,监督程序不会——自动化是把可靠性从人的手里移交到代码的手里。另一边的反对同样响亮,而且带着一丝悲凉:批处理把程序员与机器分开了。在裸机时代,一个程序员可以守着机器调试,出错当场改,十分钟一个来回;批处理时代,你把卡叠交给机房窗口,几小时后拿回一张输出纸,上面冷冰冰地印着第 137 行有个逗号错误——你改一行,再排几小时队。迭代速度被抽象这个词亲手杀死了:系统抽象掉了机器操作的琐碎,也顺带抽象掉了与机器即时对话的可能。一个新程序从写好到知道对错,周期以半天计;一个只会犯一次的初级语法错误,要动用整条流水线来伺候。工程师们发明了各种土办法自救——先在纸上逐行读三遍、找人互相检查、把小改动攒成大批量再提交——这些自救办法后来都有了正式的名字:代码评审、结对编程、批量提交。它们诞生于批处理时代,原因却与批处理的初衷相反:那是对失去即时反馈的补偿。第二重反对来自机房操作员——一个真实存在、且人数不少的职业。在裸机时代,操作员是机器唯一的合法驾驶者:他认识控制台上每一盏灯的脾气,知道哪台磁带机在潮湿天会打滑,掌握着所有作业的生死次序;他的判断就是机器的调度算法。监督程序每自动化一步,这份专业权威就被削走一块;到脱机批处理成熟之后,操作员的工作只剩下搬磁带盘、撕打印纸、以及在机器报错时按下重启——驾驶者退化为搬运工。职业的萎缩当时没有任何补偿方案,被顶替的手艺与被淘汰的人,在计算机史的注释里几乎不留名字;只有老照片里那些穿白衬衫打领带、站在磁带柜旁的男子,还保留着这份职业曾经的庄重。还有第三种声音,来自做实时计算的人:防空系统的工程师、天气预报的数值求解者、火箭遥测的处理组——他们的输入是连续到达的数据流,等不得一夜的批;批处理的“攒一批再算”对他们是原则性失配。这批人的需求在 1950 年代没有形成主流,却像埋进土里的种子,十几年后在实时系统与分时系统的名目下接连发芽。这两条反对在 1950 年代没有任何人能当场反驳——事实上,最响亮的反驳要等到 1961 年,麻省理工学院的一群人决定不再让机器迁就效率、而让效率迁就人,那就是下一章的故事。但历史的裁决先给了批处理:在机器以百万美元计、以小时出租的年代,迭代速度是奢侈品,利用率才是生存权。

退位

操作系统诞生史里最沉默的一页,是它的账目页。作业卡叠里那几张账目卡——写明用户、部门与项目编号——并非行政琐事,它们是这门生意的核心:机器按小时计费,每份作业的成本要落到具体的成本中心——大机房的月度账单以五位数计,任何一位研究者的一次手滑都是真金白银;会计系统先于调度系统存在,或者说,会计需求就是最初的调度需求——谁的作业先跑,本质上是钱的优先级问题。大型机行业后来甚至为计费发明了专用计量单位:以千分之一小时为单位的“机器时”,账单精确到每一位付费用户的每一次运行——为计量而生的硬件计数器,是操作系统里最早的一批“遥测”。回望 1956 年,操作系统这个东西的出现顺序颇为讽刺:先有了汽车公司写的输入输出程序,再有了“操作系统”这个概念。GM-NAA I/O 没有名字里的雄心,没有内核与进程的划分,没有今天操作系统的任何一枚徽章;它只是几个被浪费的机器小时逼出来的监工。但卷首那句话在这里第一次应验:批处理时代的遗产清单短得惊人,却件件传世:常驻内存的监督程序,是内核的雏形;控制卡语言,是壳(Shell)与脚本语言的雏形;作业队列与自动转接,是调度器的雏形;脱机卫星机与磁带缓冲,是输入输出子系统的雏形;就连账目卡,也是今天一切云计费系统的远祖:今天按秒计费的云主机账单,逻辑上与 1957 年那张作业账目卡完全同构——资源可以租,租就要计量,计量就要记账。操作系统并非计算机与生俱来的器官,而是“机器过于昂贵,人类必须退位”逼出的资源调度壳层。批处理是这个壳层的第一层皮肤——它让人类第一次从机器的直接操作者的位置上退下来,把装填、排队与交接交给一段常驻内存的程序。这场退位还有一层少有人提的副产品:为了让监督程序接管一切,工程师必须先把机器的每一种行为写成规格——规格书写完,机器才第一次被完整地描述。描述机器的文件,比描述机器的人活得更久;此后的每一代系统文档,都是这份规格书的续篇。此后的每一次进化——分时、多道程序、虚拟内存、分页——都是这同一次退位的续写:人类退得越来越远,机器的假象越来越完整。退位的证据藏在操作员的手册里。1950 年代末的操作员手册厚达数百页,教人如何装填卡片、挂载磁带、解读控制台上的灯语;到 1960 年代中期,这些章节在手册里一节节消失,取而代之的是薄薄几页:提交作业,等待输出。手册的薄化就是退位的进度条——机器学会了自己照顾自己,人类的手册就一页页变薄。手册的薄化附带了一个副产品,值得记下:操作规程从厚变薄的过程,恰好与计算机用户群体的扩张同步——1956 年能操作机器的人以十计,1962 年能提交作业的人以千计,分时之后能直接使用机器的人以万计。制度性门槛的每一次降低,都不是机器做了让步,而是有一段新写的代码,悄悄替人类挡在了机器前面。退位的次序也值得记下:最先退出的是操作机器的手,然后是排队的脚,再然后是等待结果的心——每一轮退位都由同一支笔签字:机器时间的价格表。

所以,本章给出的最终判断是:操作系统不是被发明出来的,它是被账单逼出来的——当机器的一小时贵过工程师的一天,退位就算不上观念革命,它是成本核算的必然结论;批处理赢过所有反对者的方式,并没有证明它更好——它只证明了反对者付不起维持现状的价钱。有人可以反驳:调试速度的损失与操作员的失业难道不该计入同一张账单?当然该计入——批处理的总账里,机器时间的节省记在借方,程序员工时的浪费与一个职业的消亡记在贷方,两相冲抵之后的净额是正是负,取决于机器与人力各自的时价;在 1956 年的美国,机器的时价压倒了一切,净额为正,批处理通行。这个净额是经济变量而非工程常数——所以历史才安排了下一章:当一台机器要同时伺候几十个终端用户时,旧的算法就会被重新翻案,让分时系统把这场决斗再打一遍。而批处理留下的那个问题——人何时可以重新靠近机器——悬置了五年,直到一位麻省理工学院的教授在 IBM 709 上接了一台打字机。批处理不是分时的反例,而是分时的前提——正因为机器被监督程序接管了,让机器反过来照顾人才有了技术起点;1961 年的故事,写在 1956 年的延长线上。


第 025 章 1961:CTSS、分时与多用户假象

一台打字机的心跳

1961 年 11 月,麻省理工学院计算中心的一间机房里,三台 Flexowriter 电传打字机一字排开,纸卷在滚筒上微微颤动。三台机器各坐着一个人,键盘敲击声此起彼伏;同一时刻,机房中央那台改装过的 IBM 709 正在为一个他们谁都看不见的程序进行计算。按旧世界的规矩,这三人中任何一人的作业都该独占整台机器,另外两人此刻应该在楼下排队交卡片。他们没有排队——三人共用着这台机器,谁也不等谁,每台打字机的响应都像那台大型机只为自己一个人运转。演示由费尔南多·科巴托(Fernando Corbató)主持,系统名叫实验分时系统(Experimental Time-Sharing System),它是人类历史上第一次公开的分时演示:一台机器,同时属于很多人。终端是三台改装的 Flexowriter 电传打字机——键盘、纸卷与打印针的组合,在此后的几年里,这种办公机器将改名叫终端,成为人与主机之间唯一的门。

这一幕的机密不在机器里,而在时间里。大型机的运算以微秒计,人的打字以秒计,中间隔着五六个数量级——按批处理时代的逻辑,人碰机器的每一秒都是对算力的侮辱。分时系统翻转了这个判决:它让机器在人的打字间隙里做千百次切换,把整机的算力切成薄片,分给每一个等在键盘前的人。错觉被工程化了:每个人都以为自己独占机器,实际上每个人只占用了机器的千分之几秒——而每个人都心满意足。这笔错觉的算术并不神秘:那台 709 每秒能做几十万次运算,切给三个人,每人每秒仍分得十几万次;同时代最强大的个人设备连它的万分之一都没有。人从来不需要独占机器的全部算力——人只需要独占机器的注意力,而注意力是可以切片的。

一天的等待与一次巴黎的报告

把时钟拨回七年,这个想法的每一步都有先声。1954 年夏,约翰·巴克斯(John Backus,三年后 Fortran 的主持人)在麻省理工学院的暑期课程上说过一句预言式的话:通过分时,一台大计算机可以用作几台小计算机,只需为每个用户设一个读入站。当时 IBM 704 的性能撑不起这个设想,它被记在纸上——注意这句话的时间:1954 年,Fortran 还在孕育,巴克斯已经在想五年后机器该怎么被分享。天才的头脑很少只解眼前的题。1958 年底,MIT 计算中心真的给自己的 704 接了一台打字机输入——意图很朴素:让程序员能以分时的方式向机器追问附加的答案,与机器上同时运行的其他程序共享时间。这是人与大型机的第一次对话,虽然粗陋,方向却已指明。

真正的理论旗帜在 1959 年 6 月竖起:克里斯托弗·斯特雷奇(Christopher Strachey)在巴黎的 UNESCO 信息处理会议上发表《大型快速计算机的分时》,设想一个程序员坐在控制台前调试程序,与此同时另一份程序在机器里运行。斯特雷奇的动机直指批处理时代最痛的伤疤:调试。批处理的规矩是把修改过的代码交上去,然后等一天拿到结果——一个逗号的一天。任何写过程序的人都能体会这种痛:错误也许五秒钟就能改掉,而这五秒钟排在队列的第两百位。行业里流传着各种应对的怪招:有人一次提交五个版本碰运气,有人故意在卡叠里夹上解释性卡片乞求操作员通融,还有人干脆把调试期写成论文致谢的第一段——感谢机房,感谢等待。把痛换算成账:一个程序的调试平均要经历十几次提交,每次提交一天——一个两周的项目,光排队就吃掉一个季度。斯特雷奇的论文里没有一个方程,它讲的完全是这笔时间账。同年,约翰·麦卡锡(John McCarthy)在 MIT 写下分时备忘录;学院先是成立预备研究委员会,再成立工作委员会——MIT 的机构机器全力开动:计算中心出机器与机时,各系出需求清单,委员会出路线图。方案讨论过的细节包括:终端放多远、每人配多少磁带、响应时间承诺几秒——这些参数里最关键的一项,是“时间片多长”:片太长,后来者等得久;片太短,切换开销吃掉全部收益。200 毫秒这个数,就是委员会时代反复权衡的产物。这场运动的非凡之处还在于它的立场:分时的推动者们的理由并非“让机器更快”,而近乎一项主张——计算应当像电力一样从墙上插座取用。这个比方在 1961 年听起来像乌托邦,四十年后云计算几乎逐字兑现了它;本章故事里的那三台打字机,就是第一排插座。这是操作系统史上第一次,一项系统工程的立项走的是学术机构的委员会流程,而不是某家公司的产品线排期;它也预示了此后十年分时研究的基本盘:大学出思想,产业出机器,军方出钱。方向定了,剩下的是工程与人事——主持实施的担子落在科巴托肩上。他 1926 年生,同事都叫他 Corby——为人温和,做事严密;在他主持下,这个后来更名 CTSS 的系统由一支小团队写成,论文致谢里列着六个人的名字,其中两位是女性工程师——在 1962 年,这份名单本身就是一页社会史。

支持这个设想的硬件条件,也在 1961 年前悄悄凑齐。改装后的 IBM 709/7090 拥有了两体磁芯存储器——不是标配的一体,而是两体:一体留给分时监督程序,一体轮流装载用户程序;机器加装了时钟中断——一根定时跳动的脉搏,每过固定间隔就把 CPU 从任何正在运行的程序手里夺回来,交还给监督程序;这是计算机第一次拥有一种凌驾于一切程序之上的裁判机制——在它之前,机器一旦把控制权交给一个程序,就只能等这个程序自己交还,程序死循环,机器陪葬;在它之后,没有任何程序能霸占机器超过一个时钟周期。再加上把内存保护中断挪用作软件中断的技巧,监督程序提供的服务从此可以被用户程序安全地调用。这三件套——双体内存、时钟中断、软件中断——构成了一套最小的“机器治理”框架:有分区、有计时、有传唤。后来的操作系统无论长到多大,治理的骨架仍是这三件。晶体管的 709 比电子管的 704 快了数倍,磁芯内存大了一倍,中断与时钟提供了控制器。所有条件在 1961 年夏天就位:7 月,几条分时命令已经在 709 上跑通。剩下的只是把它们包成一个可以给人用的系统——以及一个敢在院长与赞助商面前按下回车的人。

时钟的诞生

分时系统的心脏是一台闹钟。它的工作循环可以完整地讲清楚:每个用户配一台打字机终端,终端上敲下的字符经硬件中断进入监督程序的缓冲区;用户敲下回车,监督程序接管机器,判断该服务谁——它从 B 体内存里把当前用户的程序整体换出到磁带,把下一个用户的程序从磁带换入 A、B 两体之间,然后跳转过去运行一段固定的时间;换出换入不是一瞬完成的:27K 字的程序经磁带机搬一趟要好几秒——这几秒里机器不属于任何人,只属于磁带;这解释了为什么 CTSS 的每一片时间长达 200 毫秒:切片必须足够长,长到能抵消切片本身的搬运费。所有调度器的第一课,从这里开始:切片的成本永远要算进切片的收益里。时间一到,时钟中断触发,监督程序再次接管。人感觉不到这些换入换出,因为人的手指快不过磁带:你敲两个键的工夫,机器已经完成了一次完整的交换。切片、交换、再切片——多用户假象的全部机关,就藏在这套以固定节拍运转的循环里。

   分时的时间切片(CTSS,1961-1963)  
  
   时钟 │  ├─200ms─┤  ├─200ms─┤  ├─200ms─┤  
        ▼          ▼          ▼          ▼  
   CPU:  [用户A][监督][用户B][监督][用户C][监督][用户A]…  
              ↑换出A,换入B   ↑换出B,换入C  
   ─────────────────────────────────────────  
   双体内存(A体=监督程序,B体=轮流装用户程序)  
   控制台输入 → 硬件中断 → 监督程序缓冲区  
   回车符触发 → 监督程序接管 → 决定下一个运行者  
   量子 200ms,多级反馈队列  

科巴托小组用一把最简单的剪刀切分时间:轮流。每位用户按次序获得一个时间片,片到即换人;时间片长到 200 毫秒——以人的手速,两片之间的等待几乎不可察觉。后来这套调度长成了多级反馈队列:响应快的交互作业被优先对待,算得久的作业自动沉入低优先级层,谁也不许独占。多级反馈队列的直觉后来统治了几乎所有操作系统:观察一个用户的行为,打字打得勤的说明他在等回复,优先;提交了程序埋头等结果的,沉到低层慢慢算。调度器学会了读人心——它不再追问每个用户是谁、在做什么,只看行为的节奏,节奏自己会说话。把这套循环写成最简的骨架,不过几行:

# 轮转调度的时间切片骨架(示意)  
from collections import deque  
  
queue = deque(users)                     # 用户终端排成环形队列  
while queue:                             # 机器不关,循环不止  
    user = queue.popleft()               # 取队首  
    swap_out(running); swap_in(user)     # 换出上一个,换入这一个  
    run(user, quantum=0.2)               # 给他 200 毫秒  
    queue.append(user)                   # 用完排回队尾  
    if has_input(user):                  # 期间敲了回车?  
        handle(user)                     # 下个切片优先响应  

这套机制后来有一长串后裔——Unix 的分时片、现代内核的完全公平调度器,直到云计算按秒计费的弹性实例,全是这只闹钟的改型。而它在 1961 年的全部意义只有一句话:机器的注意力第一次可以被切割、被调度、被公平地分配——在此之前,机器的注意力属于排队的卡片;在此之后,它属于正在打字的人。本章的三个年份各有各的遗产:1954 年的预言活成了 1961 年的演示,1959 年的论文活成了 1963 年的常规服务,1961 年的三台打字机活成了 1973 年红机停机前的几十台终端——遗产的接力没有断过一次。下一章里,这套系统将膨胀成 Multics,再被后人简化成 Unix——分时的故事,才讲到第二幕。这套切片还有一层当时少有人点破的哲学:公平与效率在这里第一次正面相遇。纯效率的调度会把时间全给最重的作业——那是批处理的逻辑;轮转把时间均分给所有人,哪怕有人此刻根本没在算什么。科巴托们选了后者,因为他们卖的不是算力,是响应——此后的计算机界面史,本质上全是响应与效率的反复议价。

三台打字机的共和国

1961 年 11 月的那次演示之后,系统有了正式的名字与正式的论文——而它真正了不起的地方,藏在演示那天的细节里:三台打字机背后各坐着一个真实的、急于求解的研究者,而不是配合表演的操作员;演示跑的是他们各自真要算的题。分时从出生那天起就拒绝摆样子,它直接上岗。1962 年 5 月 3 日,科巴托与达格特、戴利在春季联合计算机会议上发表了它的完整描述——兼容分时系统,CTSS。名字里的“兼容”是全系统最聪明的一处设计:分时与批处理不再是敌人——同一台 IBM 7090 上,前台是敲打字机的交互用户,后台照旧跑着成批的老式作业;批处理客户不需要改变任何习惯,分时用户则立刻获得了即时响应。这个设计里的权衡也毫不掩饰:机器分给交互用户的内存只有体量的一半,交互程序的体量与时长都被严格限制;想跑大作业?请走后台批处理队列——分时是一种服务,不是一种特权,服务的边界从第一天就画得很清楚。效率派的质疑被这一手化解了大半:维基条目转述的那句史料值得重读——后台批处理作业“通常比分时功能占用更多的计算资源”;换句话说,交互用户敲敲打打的那点算力,在整台机器的账本上是零头,真正的吃算大户仍是后台的成批作业。分时没有偷批处理的时间,它捡的是批处理本来就要浪费的碎片。三台 Flexowriter、每个用户两台专用磁带机(一台放文件目录、一台做内存转储)、外加一条系统命令磁带——没有磁盘,27K 字的内存里 5K 归监督程序、27K 轮流给用户,这就是全部家当。

就在这套家当上,今天计算机用户习以为常的一整排东西第一次出现。用户要登录——CTSS 是第一个实现密码登录的计算机系统,每个人的文件从此对他人关闭;——多用户的代价清单随之展开:谁先来、谁后到、谁的结果属于谁,都需要制度;当时实现的命令一共十五条:登录、登出、编辑、加载、运行、列目录、打印——今天任何一台机器上的命令行仍是这份清单的拉长版。有趣的细节是命令的语气全是祈使式:login、edit、run——人对机器说话的方式,从批处理时代的“填表申请”变成了“直接吩咐”,语法的变化暗示了关系的翻转。十五个命令养活的用户群里,有人在写论文,有人在调程序,有人在给同事留言——三种用途,三条日后各自长成产业的枝:文字处理、软件开发、社交网络。密码作为“多用户假象”的门锁,在这里完成了它的世界首演。密码的出现不是为了防黑客——1961 年还没有这个职业;它是为了在共享的机器上划出私人的格子:你和你室友都能上这台机器,但你不希望他偷看你的作业。科巴托后来把这种处境总结成一道两难:完全信任所有用户,恶意者会伤害所有人;完全孤立,人又会无聊。密码是两难之间的折中——也是此后一切身份系统难以逃离的原型困境。CTSS 的密码文件起初几乎是明文存放的,后来还出过被误覆盖的事故;第一条密码与第一次密码泄漏几乎同时到场,这个行业的保密史,就这样在发明与失守的交替中开了头。用户要编辑文本——TYPSET 与 RUNOFF 提供了最早的文字处理之一;要跟同机器的另一人说话——跨用户消息系统在 CTSS 上运行,它是电子邮件与即时消息的共同祖先。路易·普赞(Louis Pouzin)为它写了 RUNCOM,把一串命令存进文件批量执行——这个主意后来经 Multics 的 shell 传给 Unix,长成今天每一个程序员都会写的 shell 脚本;QED 编辑器装在它上面,经肯·汤普森之手加上正则表达式,成了后来 ed、vi、vim 一族的老祖宗;更抽象的一层是 RUNCOM:它把一串命令存进文件、一次执行,还支持参数替换——用今天的话说,这是脚本语言的胚胎。人对机器的指令从此可以成段书写、反复调用;这个习惯一旦养成,就再也回不去了。连最早的聊天机器人 ELIZA,也是在这套系统上第一次开口说话——多用户终端的对面第一次坐进了另一个“人”,哪怕它只会把你的话反射回来。假象的清单上从此又多了一行:机器不但假装属于你,还假装听得懂你。终端前的世界在两年里长出了此后六十年的全部胚胎。更难得的是这一切跑在 27K 字的内存上——折算成今天的单位,不到 150KB,连一张手机照片都装不下;那一代工程师在三位数的字节预算里塞进了一整套多用户世界,他们不是在写代码,是在做刺绣。

假象的普及与它的对手

CTSS 从实验走向日常的速度超出所有预计。1963 年夏,它开始对 MIT 计算中心的用户例行服务;同年 10 月,第二台改装的 IBM 7094(机房里称“红机”)到货,专为项目 MAC(Project MAC)服务,这台机器一直开到 1973 年 7 月 20 日;同年,MIT 借着一笔新到账的资助发起项目 MAC,把分时从计算中心的一间机房,升级成一座跨系共享的计算工厂;同年 10 月,第二台改装的 IBM 7094(机房里称“红机”)到货,专为项目 MAC 服务,这台机器一直开到 1973 年 7 月 20 日;原先那台“蓝机”也服役到 1968 年。终端从三台加到几十台,用户从计算中心的同事扩散到全校——然后越过了校园:加州、南美、爱丁堡大学、牛津大学的用户通过线路远程登录,一台在剑桥市的机器,被两个大陆的人共享。费诺把这套东西的意义讲得直白:机器时间不再是按小时批发的大宗商品,它开始零售,零售给每一个坐在打字机前的研究者。工业界的跟进比学术界的论文更快:各厂商的分时系统与分时服务接连上市,商业分时公司按终端小时向客户收费,甚至有旅馆挂出“客房配有终端”的招牌招揽出差工程师——一桩围绕分时的服务经济,在技术尚未成熟的边界上先热了起来。零售业的全部特征也随之出现:店面(终端室)、客源(各系师生)、会员制度(账号与密码),以及顾客抱怨(响应太慢)——计算这件事,第一次有了服务业的形状。Project MAC 的主持人费诺(Robert Fano)把各路学者聚到这面大旗下,分时成了 1960 年代中叶计算机界最热的词——机器不再按台卖,算力开始按人分。本书的第五条主线(认知负荷与平民化)在这里留下了它最早的里程碑:分时之前的程序员必须穿越操作员、机房与排队制度才能触到机器;分时之后,任何一个会打字的研究者都能直接对机器说话。被剥离的中间层是操作员的职业,被赋权的人群是所有会用键盘的学者——赋权的规模,要等个人计算机出现才见全貌,但门在这里开了。

但决斗并未结束,对手的论据每一层都站得住。第一层来自纯粹的效率:分时是有代价的——每次切片切换,当前用户的程序要被整体换出到磁带,下一个再换入,磁带机转得起劲的时间全是纯开销;统计下来,监督程序与切换吞掉的不是零头,是整整一块内存(5K 对 27K)与可观的机器时间。批处理派说:让几十个打字员按需打断一台昂贵的机器,是用最贵的方式提供最不必要的服务。批处理派的算术并不胡涂:每一次切片切换都是纯粹的损耗,监督程序自己又常住 5K 字内存——折算下来,分时让机器把两位数百分比的时间花在了“伺候切换”上;同样的机器不做分时,纯粹的批处理吞吐量立刻上涨。这不是危言耸听,是当时任何一家机房都能复测的数字。第二层来自工程现实:没有内存保护的多用户系统,一个用户的野指针就能踩碎邻居的数据——CTSS 的运行岁月里确实发生过文件系统被失控程序搅乱、部分用户数据与邮件毁于一旦的事故——多用户假象的账单,从第一天就在寄送。事故的另一面也值得记下:搅乱文件系统的那份失控程序,本身就是一位用户在调试自己的作业——伤害多用户世界的,往往正是多用户世界要保护的普通用户。权限、隔离与审计的整套谱系,从此有了明确的假想敌:并非什么恶意的大敌,而是普通人的失误。多用户假象的账单,从第一天就在寄送。科巴托们的回答分两层:对效率层,答案是“兼容”——交互切片吃剩的机器时间全数交给后台批处理,CPU 一秒也不空转,总利用率不降反升;对脆弱层,答案只能承认——假象之所以是假象,正因为它的地基是脆弱的硬件机制,保护与隔离要留给此后二十年的多道程序、虚拟内存与保护环去逐层加固。分时的教训同样被完整继承:多用户假象的每一次兑现都伴随新的脆弱——容器逃逸、虚拟机漏洞、云上的邻居噪音,全是 1961 年那道“共享与隔离”两难在更大尺度上的回声。科巴托晚年的访谈里仍在讲这道两难;他讲对的地方在于,这道题不会做完——只要假象还在服务人,攻破假象的人就不会失业。分时没有赢在严密,它赢在不可逆:人一旦尝过即时响应,就再也不肯回去排队交卡片。胜负的裁决权再一次交给了需求的净额——1960 年代中后期,分时成了产业:通用电气、DEC、IBM 各自分兵投产分时系统与服务,商业分时公司按终端小时向客户收费——批处理时代的批发商们一夜之间都开起了零售店,货架上的商品只有一个:即时响应。而胜负的算法照旧:需求的净额说了算。但与上一章不同,这场决斗另有一位常被忽略的裁判:终端用户自己。1950 年代末,MIT 的研究者们对机房的怨气是分时最直接的民意基础——委员会的会议记录里,“响应时间”被列为第一需求,优先于内存、优先于语言;用户不知道调度算法的名字,但他们知道等一天是什么滋味。这一局,又是需求的净额说了算。但与上一章不同,分时的净额里有一项批处理从没有过的新收入:交互带来的试错速度。批处理一天一个来回,研究者一周只能验证五个想法;分时一分钟一个来回,一周能验证几百个——想法的验证速度,就是研究本身的速度。这笔账没有出现在任何机房的成本表上,却决定了此后所有计算机的进化方向:机器越来越快固然重要,机器离人越来越近才是真正的赛道。

多用户假象

把本章与上一章并排看,1956 到 1961 这五年完成了一次完整的秩序翻转。批处理建立的秩序是:人迁就机器——作业攒成批、机器连轴转、程序员的结果以天计;分时颠倒的正是这条主从关系:机器迁就人——它切分自己、掩盖自己、假装成许多台小机器,只为让每个坐在打字机前的人相信,眼前这台是自己的。卷首那句话在本章第二次应验:脆弱的硬件机制之上,叠加出了“独占全机”与“不可侵犯”的虚拟假象;而制造假象的原料,只是时钟中断、两个内存体与一套换出换入的纪律。假象是有维护成本的——每一次时钟中断、每一轮换入换出、每一个密码校验,都是为了让台面上的假象维持下去;用户付费购买的从来是“机器只为我服务”的确定性,不是任何一台真实的机器。假象的层次却比原料复杂得多:最底层是资源假象——一台机器装作许多台;往上一层是独占假象——每个终端前的人都以为机器只为自己转;再往上,是隐私假象——密码锁起的文件目录让每个人以为自己的数据不可侵犯;最顶上,是这台章末才会揭晓的假象——机器假装听懂了你。四层假象叠在一起,就是现代计算体验的全部地基。它们此后的工业化身也都认得出:资源假象长成了云计算,独占假象长成了容器与虚拟机,隐私假象长成了权限系统与加密,对话假象——则在六十多年后,以每天回答亿万问题的聊天机器人的形态,把这份 1961 年的名单续到了今天。本卷主导的那道万倍时延裂谷,也在这一章里找到了它的第一道缝合线:CPU 的纳秒被切成薄片,填进人类打字的秒与磁带转动的毫秒之间的空隙里——裂谷没有消失,但它第一次不再漏水。此后的半个多世纪,这套缝合术在每一代系统里重演:缓存垫在内存与 CPU 之间,页换垫在内存与磁盘之间,消息队列垫在服务与数据库之间,直到数据中心里横跨大陆的异步复制——每一层队列,都是 1961 年那只时钟中断的直系后代。

所以,本章给出的最终判断是:分时系统的发明,本质上是把一种错觉变成了服务——科巴托们的全部工程,就是让几十个人同时相信一台机器只属于自己,而这份错觉需要时钟、中断、磁带与纪律昼夜不停地维持,一旦维持中断,假象当场露馅。有人会反驳:错觉这个词低估了它——多用户共享算力是真实的资源革命,不是心理戏。这个反驳成立,也恰好说明本案的裁定应当两面记录:资源革命是它的骨头,认知错觉是它的皮肉,缺了哪一半,今天每一个对着终端以为自己独占整个数据中心的人都还在机房外排队。排队的意象值得在本章结尾再停留一次:1957 年,抱着卡叠的工程师在机房窗口外站四个小时;1961 年,坐在打字机前的用户敲下回车后只需等几秒。两次交付之间隔着的,并非机器速度的差距——机器只快了数倍——而是一场注意力的革命:机器从被排队供养的奢侈品,变成了会派号的柜员。CTSS 的墓碑上值得刻一整列“第一”:第一个分时系统、第一个密码登录、第一封电子消息、第一个即时消息、第一套文字排版工具、第一只聊天机器人的产房。这些“第一”没有一项让它商业化成功——CTSS 只在两台机器上运行过,1968 年蓝机停机,1973 年红机停机,系统退役时甚至没有举行仪式。但退役的不是思想:换入换出流向了 Multics 与 Unix,密码流向了全世界的登录框,消息流向了邮箱与聊天窗口,RUNCOM 流向了每一个 shell 脚本。一台停机的机器,以思想的形式继续通电——这是软件史独有的永生方式。科巴托活到了 2019 年,九十三岁;他在晚年反复提醒的那道两难——信任与孤立的抉择——至今没有标准答案,他留在 CTSS 里的那串密码,倒是一直活到了所有人身上。


第 026 章 1965:Multics 与公共算力的乌托邦野心

1967 年 1 月,新泽西州默里山,贝尔实验室的机房里吊进了一台从未有人造过的机器:通用电气 GE-645。为了它,通用电气拆掉了自家产品线的一半逻辑,麻省理工学院押上了分时研究的全部声望,贝尔实验室派出了自己的软件好手。在场的工程师分属三个世界:麻省理工来的是做过分时系统的元老,通用电气来的是背负翻盘使命的产品团队,贝尔实验室来的是一群把软件当手艺打磨的研究者——此后五年,这三个群体要在同一份代码库与同一条工期线上纠缠不清。那是一台 36 位字长的大型机,机柜排满半间机房,从硅片层面就为分时与保护而重新设计过——市售的通用机器没有一颗晶体管是为这项目标准备的,三家机构一致认为,值得为未来重新发明一台。机器背后的目标写起来毫不掩饰:让计算像电力一样,从墙上的插座里流出来——你插上终端,算力就来。当年的市场研究甚至预测,到世纪末计算服务的规模会赶上电话——预测的量级错了半个世纪,方向却对得惊人,按用量付费,不需要知道发电厂在哪。这台机器所服务的系统,叫 Multics;它的全名是多路信息与计算服务(Multiplexed Information and Computing Service),而它的命运,是成为计算机史上最著名的一次流产,以及几乎所有后来操作系统的匿名父亲。

计算公用事业:一场为未来定价的豪赌

要理解为什么三家风格迥异的机构会同时跳进这个坑,得回到 1964 年算力的处境。彼时一台大型机以百万美元计,机时要排队预约,程序员的纸带在机房外叠成小山;此前数年,麻省理工学院的分时系统 CTSS 已经证明:让几十个人同时坐在终端前,每人分到一小片机器时间,技术上是可行的,体验上是革命性的。CTSS 的成功远不止原理验证:它在麻省理工服务了数十位真实用户,编程、作文、排队调试,终端前的体验让每一位用过的人再也无法忍受批处理的纸带世界;MAC 计划立项之后,各地赶来的研究者把报告会挤得水泄不通。计划的钱袋同样来自战争:MAC 计划的启动经费出自军方研究系统,冷战把计算变成了战略物资,五角大楼是那个年代一切大型计算实验的默认赞助人——学术的雄心、军方的支票与企业的赌注,在这份标书里第一次合流。需求的真实与技术的可行第一次同时到场——这就是 1964 年那个夏天,三家厂商愿意为一份分时系统标书竞标的全部背景。等在机器另一端的是几类截然不同的用户:麻省理工的教授与博士生想要一台永远在线的研究伙伴,贝尔实验室的数千名工程师需要一个随时可用的计算窗口,企业界则在观望分时服务能否成为一门真正的生意——每一种期待都会在几年后变成一条具体的功能需求。顺带一提,CTSS 本尊一直在麻省理工服务到 1973 年才功成身退——父与子的两代分时系统,在同一座校园里共存过四年。主持 CTSS 的科巴托(Fernando Corbató)团队顺势提出下一步的雄心:不再是一台机器服务一所实验室,而是建成一座计算发电厂——全城的人随时接入,按需取用,这就是那个年代反复出现的说法:计算公用事业(computing utility)。1963 年麻省理工学院为此立项 MAC 计划,1964 年夏天向厂商征集定制硬件,DEC、IBM、通用电气三家投标,技术委员会评估后一致选中通用电气。技术委员会的评估记录写下了理由:通用电气的方案把分时所需的保护与重配置能力直接做进了指令集,而不是留给软件打补丁——在硬件与软件的分工哲学上,这笔赌注从一开始就站了队,由它改造出一台从硅片层面为分时与保护而生的机器:GE-645。

三方的算盘各自成立,没有一方是被理想主义冲昏的。麻省理工学院需要它延续分时研究的领先地位;通用电气在大型机市场被 IBM 压得喘不过气,急需要一款代差产品翻盘;贝尔实验室则有自己的现实账本——母公司 AT&T 的工程师与研究人员分散在全国,都需要接入计算资源,自研分时系统的成本由三家分摊,何乐不为。还有一条当时无人介意、日后却至关重要的限制:贝尔实验室的母公司 AT&T 早在 1956 年就因一纸反垄断和解协议被挡在计算机商品市场之外,参与 Multics 只能以自用与研究为目的。这条边界此刻看起来无关痛痒,它将是这个故事后半段最沉默的一根伏线。用今天的语言说,这是一次风险共担的合资研发。通用电气的投标部门在 1964 年给出了一个在内部被视为疯狂的报价:亏本为 Multics 定制一台机器,赌的是系统成功之后整整一代的后续订单。大公司为未来下这种重注,在当时的计算机业并不罕见——罕见的是,这一次连未来本身也在延期;用当年的语言说,这是把未来十年的计算机工业押在一张图纸上。图纸上的机器许诺了一切:同时服务数百个用户,任何人的程序互不侵犯,信息可以安全共享,机器可以边运行边扩容。每一条承诺,在 1965 年都有真切的用户在等待。计算公用事业这个说法,借的是一个已经成功的先例——电力。二十世纪初,工厂曾经家家自备发电机,直到电网把发电从每家每户的负担变成一项公共服务,电才真正改造了世界;计算机工业在 1965 年正处在自备发电机的阶段,每一家机构都要养机器、养机房、养操作员。公用事业的类比由此不胫而走:把机器集中起来,把算力变成水流,用户拧开龙头就取用,按表交费。这不是修辞游戏,它是整套商业计划与技术设计的哲学地基——Multics 的每一行代码,都在为这座看不见的电网施工。

环与段:把权限焊进硬件

Multics 给出答案的方式,是把操作系统的判断下沉到硬件。它最著名的设计是分级保护环:处理器的特权被划成一圈套一圈的环,最核心的环掌握着系统的命脉,外圈的环层层受限——外环的程序可以调用内环的服务,却永远摸不到内环的数据;一个用户的编译器跑在中间环上,既高于普通程序,又低于操作系统内核。GE-645 最终把这套思想做成了八个环,权限随环号一圈圈衰减;十几年后英特尔处理器里那对著名的 Ring 0 与 Ring 3,是这套八环体系流传后世的一枚简化印章。配合保护环的是单一平面存储中的分段机制:程序与信息不再是一串无差别的字节,而是装在一个个段里,每一段携带自己的属性——可读、可写、可执行、可与谁共享——段是权限的最小单位,共享的最小单位,也是故障的最小隔离带。这套分段观在当年是一次信仰选择:相信机器可以既开放又安全,相信共享不必以暴露为代价。科巴托团队的设计文献这样描述:信息存于段中,每段都可能被共享,并携带独立的属性。今天操作系统里那些可执行文件、共享库、权限位,全部能在这种分段观里找到自己的祖父。Multics 的文档文化也值得一记:它的每一层设计都有成文的论证,解释为什么值得做、代价是多少——把设计当论文写的传统,经由它的传人进入了操作系统研究的血脉。

分段还有一重更深的意义:它让动态链接第一次成为系统的内生能力。一个过程在首次被调用时才被链接进程序——写程序的人不必预先知道要用哪个版本的库,机器在运行时把最合适的那一段接上;多个用户调用同一个函数,内存里只保留一份副本供所有人共享。在存储以千字节论价的年代,这一条就值回票价。

环与环之间的每一次跨越都要过一道门:外环程序调用内环服务,参数被逐一检查,返回地址被登记,越权的尝试当场触发硬件陷阱。权限从一份需要自觉遵守的约定,变成了一条物理上无法绕开的轨道——Multics 的用户在终端前敲下的每一个字符,都被这套环体系护送着穿过多层审查。十年后,Unix 在只有一位常驻用户的小机器上省掉了整套环体系,直到多用户需求到来才在更昂贵的机器上补回——保护的价格,从来与共享的人数成正比。

环与段的组合还有一层时间上的红利:权限检查在硬件里一次完成,软件不必再为每一次内存访问做昂贵的判断——在纳秒与毫秒的夹缝里,这是 Multics 少有的省钱设计。七十年代中期,美国空军委托的一项著名安全评估把 Multics 当作多级安全研究的活体标本逐层解剖;那场评估留下的结论与遗憾,直到今天仍在安全学术圈被反复引用——一台失败的商业系统,成了半世纪安全思想的试验台。环体系之外,Multics 还给每一段配上可共享对象的访问名单,身份与权限从此成为文件系统的一部分——这个设计经由它的学生们,长成了今天每一台服务器上的权限位。它证明了那个年代最反直觉的一件事:把智能下沉到硬件,与其说是奢侈,不如说是节俭。

而这一切运转的物理底座,是本章所属卷次的主旋律:处理器的判断以纳秒计,而存储的读写以毫秒计——万倍的时延裂谷横在中间,Multics 用多层缓存式的存储层级(快速内存、磁鼓、磁盘)去填这条裂谷。裂谷的填法本身就是一场精密的编排:程序与数据常住磁盘,活跃的部分被搬进磁鼓,最热的页面才住在内存里;处理器一旦发现要找的段不在快速存储层,就挂起当前工作去慢层取回——每一次搬家都是毫秒级的等待,而处理器在等待里空转的每一微秒都是浪费。Multics 的整个存储体系,就是在纳秒与毫秒之间反复倒手的物流系统;它的一切精巧与一切沉重,都从这里生长出来。这个填法本身没有错,错的是所有人都低估了填谷的代价。把裂谷折算成钱,数字更触目:那个年代一兆字节的内存以百万美元计,每秒百万次的运算能力装在数吨重的机柜里,机房每平方米都在烧钱;让这样的机器同时服务三百个用户,意味着三百套上下文、三百份等待、三百种并发出错的可能。它的每一个子系统,都是对某一种等人场景的矫枉。卷三的主导约束在这段历史里最为刺眼:纳秒级的处理器围着毫秒级的磁盘打转,一切调度、缓存与分层的复杂度,都是在给那道万倍时延裂谷修桥——桥修得越宏伟,桥下的裂谷就显形得越清楚。

   Multics 分级保护环(GE-645 实现为 8 环)  
  
        ┌─────────────────────────────┐  
        │ Ring 7  最外圈:普通用户程序     │  
        │  ┌───────────────────────┐  │  
        │  │ Ring 3  用户自治的子系统   │  │  
        │  │  ┌─────────────────┐  │  │  
        │  │  │ Ring 1  管理层    │  │  │  
        │  │  │  ┌───────────┐  │  │  │  
        │  │  │  │ Ring 0 内核 │  │  │  │  
        │  │  │  └───────────┘  │  │  │  
        │  │  └─────────────────┘  │  │  
        │  └───────────────────────┘  │  
        └─────────────────────────────┘  
   外环可调用内环服务,不得直取内环数据  
   每段(存储段)自带读/写/执行/共享属性  
   过程首次调用才链接 = 动态链接的祖型  

一个系统如何吃掉一家公司

图纸在 1965 年画好,交付却成了一场马拉松。原计划中几年内就该服役的系统,把日期一推再推:GE-645 原型机 1967 年 1 月才运抵麻省理工与贝尔实验室。机器到货时,能让它启动的软件都还在编写——工程师们围着这堆钢铁先调硬件故障,真正的操作系统要到两年后才勉强成形,运到的机器与纸面设计之间隔着堆积如山的补丁;存储管理、保护环、动态链接,每一项功能都在与另外几项打架,调试周期以季度为单位滚动。代价跟着工期一起膨胀。GE-645 是一台为 Multics 定制的机器,定制意味着没有参照、没有现成的编译工具链、没有别的用户替你踩过坑;通用电气把翻盘的希望压在它身上,定价却迟迟换不来对等的性能口碑。几十名研究员与工程师连载数年的心血堆成几十万行代码,复杂到没有任何一个人敢说自己完整理解整个系统——调试一场雪崩式的错误,往往要先回答另一个问题:这段代码当初为什么这样写。工期的每一次顺延都在消耗三家的耐心:麻省理工的教授要赶论文,通用电气的销售在丢订单,贝尔的研究者还有自己的正业。到 1968 年,联盟内部对完成日期的估计已经从明年悄悄滑向了未知——没有人再为新的延期专门开会。机器本身也在追赶未来:GE-645 甚至预留了双处理器协同的能力,在单处理器还是行业常识的年代,这又是一项必须由软件自己消化的超前设计——超前的部件越多,系统里没有图纸的角落就越多,大家心照不宣。到 1969 年春天,贝尔实验室的计算科学研究中心做出了决定:退出。五年的投入、数十名研究员的时间,换回的是一份共识——这套系统太复杂、太贵、成熟得太慢,不符合实验室的需要。贝尔内部的评估写得更直白:这套系统过度雄心勃勃,按实验室的目标衡量已经难以指望。退出备忘录的措辞冷静得近乎残忍。退出之后,实验室里关于操作系统的雄心一夜清零:机器被收走,项目解散,年轻人被重新分派到与计算看似毫不相干的课题上——谁也没想到,正是这段被清零的日子,孕育出了下一个时代的内核——它没有指控谁,只是核算了剩余的工期、预算与机会成本。就在贝尔退出的同一年,美国司法部对母公司 AT&T 提起了新的反垄断诉讼——在诉讼阴影下,计算业务的任何一步扩张都可能加深垄断嫌疑;收缩,成了法律上最安全的姿态。贝尔的退出因此多了一层与工程无关的背景音:母公司正被要求变小。把镜头拉回物理层收束本章:Multics 的每一次排队、每一次换页、每一次磁鼓旋转,都是那道万倍时延裂谷的利息——系统越宏大,利息越精确;当利息超过本金,乌托邦就只能破产重组。两个月后,贝尔的软件好手们各回各的岗位,其中两位,肯·汤普森与丹尼斯·里奇,还没有意识到,这五年学到的每一课都将在他们自己的项目里重生。

对通用电气来说,伤害是结构性的。GE-645 是为 Multics 定制的机器——离开 Multics,它几乎无处可用;而 Multics 的每一次延期,都在 GE-645 的价签上再压一层阴影,客户眼看着这台号称划时代的机器迟迟交不出承诺的性能,订单自然流向了 IBM 那些并不惊艳、但按期到货的产品线。1970 年,通用电气把整个计算机部门出售给了霍尼韦尔(Honeywell)公司——一家以恒温器与航空电子闻名的企业就此接下了 GE-645、接下了 Multics,也接下了这个项目全部的荣耀与拖累;此后 Multics 以霍尼韦尔 6180 系列的名义继续销售,像一件改了标签的嫁衣。霍尼韦尔接手之后并没有立刻埋葬它,反而持续迭代了多年,把它维护成一家企业级用户可以长期租用的生产系统——这份迟来的勤勉恰恰证明了当年判断的另一面:系统是能做成的,只是做成的那天,市场的耐心早已用尽。计算机工业的旁观者后来公认,这个项目连同大型机市场的连续失血,是通用电气永久退出计算机制造业的直接推手之一——一家百年工业巨头的业务版图,被一个操作系统的工期改写了。定制的报应不止于工期:为 Multics 定制的 GE-645 无法转售给任何不用 Multics 的客户,每一台特制机器都是一条被锁死的产品线——为单一系统定制硬件,等于把整个业务押在一份工期表上。IBM 的影子全程压在这场竞赛上方:同期问世的 360 系列以家族化设计与软件兼容横扫市场,GE-645 每延期一个月,竞争对手的装机量就多出一个山头。到通用电气出售部门时,大型机市场的座次尘埃落定——霍尼韦尔买下的名义上是资产,实际上是靠后的位置。霍尼韦尔的工程师们后来把 GE-645 的经验带进自家产品线——这笔跨企业的技术转移,是失败项目罕见的正面外溢。从更长的时段看,Multics 的激进攻变了对手的脚步:IBM 在 360 系列之后加速了虚拟存储与安全的硬件化,连霍尼韦尔都靠着 Multics 的订单把企业级计算机业务撑进了八十年代——乌托邦项目最讽刺的外溢,是它逼着所有现实主义者变得更好。

每一条反对,都成立于当年

把 Multics 的失败讲成一个骄傲者撞墙的寓言,是对 1965 年最粗鲁的误读。回到当时的每个决策现场,每一条替代路线都更不好走。反对派最有力的一支来自 IBM 阵营:不必把保护、共享、动态链接都焊进硬件,把机器造简单些,把复杂性留给每个站点的软件人员自行处理。这条路线最终被证明在商业上聪明得多,但它的代价由整个六十年代的机房默默支付:安全取决于自觉,隔离取决于预算,共享取决于运气。两种哲学的对峙——把复杂性交给硬件,还是把复杂性交给客户——直到今天仍是每一代系统设计的分水岭。这条路线最终被证明是商业上更聪明的,但在学术与工程的良知看来,它等于宣布安全性取决于每个站点的自觉,而 1960 年代后期已经开始有人用分时系统存放机密数据,“自觉”两个字给不了任何承诺。用户的需求也站在天平另一端:六十年代末,已经有企业与政府机构开始把敏感数据放上分时系统,多用户共享一台机器的现实让安全从学术问题变成采购条件——把保护做进硬件,是当时能拿出的最硬的答案。另一支反对来自务实的增量派。促成安全条款的还有一桩被反复转述的插曲:CTSS 的一次故障曾把所有用户的主目录短暂暴露,密码一览无余——分时的安全承诺从那天起,成了每一条设计决议的第一约束:先把 CTSS 扩一扩,别造新机器——可 CTSS 的架构撑不起数百用户,渐进改良的尽头一眼可见。还有一支来自成本:为什么不等半导体存储更便宜?可等待意味着把整个市场的定义权拱手让给 IBM。

同样,失败的判决书也必须写准罪名。Multics 并非造不出来——1969 年 10 月 1 日起,它作为生产系统向麻省理工的用户开放,此后以正式环境连续运行了三十一年,最后一套 Multics 直到 2000 年才退役。2000 年深秋,加拿大国防部机房里最后一台运行 Multics 的主机切断电源,这个为公共算力而生的系统在服役三十一年后安静谢幕;当年嘲笑它臃肿的几代竞争者,此时大多早已退出了历史舞台——活得最久的,反而是那个被宣判失败的产品;它的安全记录、它的可靠性,在服役期内经受住了真实用户的几十年检验。它输掉的不是可行性,而是时机与成本:交付周期击穿了投资方的耐心,系统的复杂度击穿了调试与演进的能力上限,定制硬件的价格击穿了市场的承受线。研究这段史的学者彼得·萨卢斯(Peter Salus)的评述常被引用:Multics 试图做一个远比先前更通用、更灵活的操作系统,而它惨败了。惨败二字指控的,不是愿景的荒谬,而是在同一个系统里兑现全部愿景的代价——每一层抽象单独看都正当,叠加起来就是一座需要十年爬完的山。十年后,布鲁克斯在《人月神话》里给这类失败留了理论注脚:软件的复杂度分两种,一种来自问题本身,删无可删;一种来自实现的手法,可以管理却常常失控。他还描述了第二系统效应——设计师的第一个成功作品之后,第二个系统往往最危险,因为它背负着把第一版所有遗憾一次补齐的冲动。CTSS 到 Multics,恰好是教科书级的第二系统:每一项上一代没做到的能力都要在这一代补上,每一份雄心都值得原谅,直到账单合并的那一天。

废墟上的制度性遗产

清算 Multics 的遗产,清单比它的失败记录长得多。层次文件系统、统一的目录树、按需换页的存储、把权限刻进硬件的保护环、运行时链接的共享代码——这一串今天每个操作系统视为呼吸的东西,第一次被组织进同一个设计。这份清单的后世影响力值得逐条点名:层次目录树与统一文件树,经由 Unix 传给了今天所有的桌面与手机;保护环的思路沉睡在每一颗处理器的特权级里,现代系统对内核态与用户态的区分是它最简化的化身;动态链接长成了每一个操作系统里的共享库。顺带一提它的实现语言:Multics 的主体用 PL/I 写成,在人人默认操作系统必须由汇编手工雕琢的年代,用高级语言写操作系统是一次至今仍被低估的冒险——它证明了操作系统可以像应用程序一样编程;后来 Unix 用 C 重写而震动业界,走的正是 Multics 踩开的那条路;按需换页长成了虚拟存储。今天的程序员在终端里敲下的每一个路径分隔符,语法上都是 Multics 那棵文件树的后代。谱系的另一端写得更加直白:没有 Multics 就没有 Unix,没有 Unix 就没有今天的 Linux、macOS 与 iOS——每一部手机都在运行一份被极简化的 Multics 概念清单。教科书把这段关系压缩成一句话:Multics 雄心勃勃地失败了,Unix 灰头土脸地成功了,而现代操作系统是它们共同的孩子。主持 CTSS 的科巴托守着麻省理工继续耕耘,三十年后,图灵奖把分时研究的最高荣誉补授给了这位冷静的工程师——乌托邦的建筑师没有获奖作品,但有一座以他名字为底座的学科。路线图对掉队者的定价同样冷酷:跟不上曲线的公司,资产会在两三年内从领先技术变成沉没成本——这套机制在 Multics 身上预演过一次:押注下一代的代价,是被当代的现金流绞死。更制度性的一笔遗产藏在人身上:从贝尔实验室的废墟里走出来一支小队。这支队伍的核心是几位在 Multics 项目里耗过数年的年轻人——他们对那套系统的每一处精妙与每一处冗余都了如指掌,因为他们亲手参与过它的建造,也亲手送走了它的工期。两位年轻人在项目里的分工,恰好覆盖了文件系统与输入输出这些后来在 Unix 里大放异彩的部件——他们不是旁观者,是亲历者;这决定了后来那台小型机上的复刻,为什么处处都是对母系统的既继承又反驳。Multics 培养的人四散在业界,把同样的设计判断带去了主机厂、存储公司与后来的微处理器革命——项目失败,人口流动,这才是遗产真正扩散的路径。这份继承关系还有法律层面的余音:Multics 的代码从未开源,它的思想却全部公开——思想的传播不需要许可证,这是它留给公共知识世界的最后一条注释。

他们带着在 Multics 学到的一切——多用户、文件树、保护、以及最重要的,哪些路不要走——在一台没人认领的小型机上,用一个极简主义的复刻完成了对母系统的回应。Multics 与 Unix 之间与其说是讽刺关系,不如说是继承关系:前者是后者的思想母体与反面教材的总和; Unix 的极简,与其说是天生的品味,不如说是在 Multics 的复杂度账单上签过字之后的条件反射。

复刻不是从零开始,是从反省开始的。这份取舍清单后来有了一份署名的底稿。里奇在 1974 年那篇正式向学术界介绍 Unix 的论文与日后的多次访谈里复盘这段师承:Unix 的成功,一半归功于从 Multics 学到的东西,另一半归功于 Multics 教会他们不要做什么——不要为完整的愿景堆叠功能,不要让通用性无限期抵押交付日期,不要把一个系统写成所有思想的总结算。这话出自亲历者之口,与旁观者的讽刺分量完全不同:说它的人参与过母系统的建造,也亲手数过它的延期。同行的还有第三位常被忽略的成员卡纳迪(Rudd Canaday)——三人后来在小型机上重写文件系统的分工,直接对应着他们各自在 Multics 里看过的伤口。更耐人寻味的是晚年的和解:Multics 社区与 Unix 社区在系统相继退役后互相承认谱系,一边承认后者的简化是对的,一边提醒后者别忘了那些简化当初省掉了什么——失败者与胜利者在暮年交换名单,各自补全了对方史料的另一半。失败项目最好的纪念碑,往往不是辩护词,是学生们的取舍清单;Multics 的墓志铭因此有两个版本,石头上刻的是惨败,学生的论文里写的是教员——两个版本都被引用了几十年,谁也没有取代谁。

那项乌托邦愿景本身,也没有死。让计算像公用事业一样随取随用——这个 1965 年的梦,在 Multics 的 GE-645 上以数百万美元与五年工期为代价没能兑现,半个多世纪后在另一套基础设施上以另一种形态全面兑现:今天的用户在浏览器里点击一个链接,算力从万里之外的数据中心流过来,按用量计费,无人知晓发电厂在哪。公共算力的乌托邦没有流产,它只是等来了自己的硬件。Multics 的墓志铭应当这样写:它不是做错了一场梦,而是提前了半个世纪做梦。卷首语里写过,操作系统是机器过于昂贵、人类必须退位逼出的壳层;Multics 是这句判词最重的一次压秤——它想让人退得更彻底,以至于忘了问机器答不答应;错的那部分由它自己吞下,对的那部分由全人类按月付费继承。而云计算的出现不过是把旧梦重提:数据中心集中算力,用户按用量付费,终端只负责展示——Multics 在 1965 年写下的每一行愿景陈述,今天的读者会以为那是某份云计算白皮书的摘录。它甚至等到了网络的黎明:同样在 1969 年,ARPANET 的第一个节点上线,计算机第一次真正开始彼此对话。公用事业需要的全部零件——集中、联网、计量——在同一个年份到齐,只是组装,还需要三十年。而 1969 年春天从贝尔实验室退出会议里走出来的那两个人,即将在一台被冷落的 18 位小型机上,开始讲述这个故事的下一章。shell 这个词就是那次交接留下的:汤普森从 Multics 借来外壳的隐喻,给自己小机器上的命令解释器起了同样的名字——旧系统的词汇,成了新系统的门面。


第 027 章 1969:Unix 的诞生:极简主义的胜利

1969 年夏天,贝尔实验室的软件研究员肯·汤普森(Ken Thompson)遇到了一段完美的空白:妻子带着刚出生不久的儿子回加州探望外祖父母,为期一个月,家里只剩他一个人。桌上的日程表精确到周,每一条都写着一个此前只存在于 Multics 图纸里的部件名。这份日程表后来成了软件史上被引用最多的家事安排:几个独处的星期,换来了此后五十年服务器世界的地基。他给自己排了一张以周为单位的时间表——第一周写内核,第二周给内核配上文件系统,第三周写一个编辑器,第四周写一个命令解释器。四周之后,一台被项目遗弃的 PDP-7 小型机上,跑起了一个短小的操作系统:它有一个谦逊得近乎自嘲的名字,Unics,意思是阉割版的 Multics;后来这个词被拼成了 Unix。人类历史上最重要的一场软件革命,起步于一次探亲假和一个被冷落的小机器。这个故事常被讲成天才的轶事,真正的信息量却在它的结构里:四周的期限逼出了最小可行产品,闲置的机器豁免了一切审批,游戏提供了无人能够拒绝的正当性——创新的三个经典条件,在这里以最不庄严的方式同时到场。此后无数改变行业的软件,都在重复这三种要素的某种组合。

一场撤退留下的真空

这台 PDP-7 从哪儿来,得从上一章的结局说起。贝尔实验室撤出 Multics 之后,计算科学的雄心一夜清零:定制机器被收走,项目组解散,像汤普森和丹尼斯·里奇(Dennis Ritchie)这样在 Multics 里泡了数年的年轻人,被重新分配到与操作系统毫无关系的课题上。汤普森是伯克利出身的电气工程师,话少,只对摆在明面上能验证的逻辑感兴趣;在 Multics 项目里他是贝尔方最年轻的成员之一,撤出令下达时,旁人松了一口气,他像被人从自己的图书馆里请了出去。但需求的真空没有跟着项目一起消失:实验室里数以千计的研究员仍然需要分时计算,打字机终端仍然一排排立在走廊尽头,只是背后没有了可以登录的机器。研究者的日常肉眼可见地倒退回批处理时代。贝尔其实有自己的老底子:实验室自研的一套批处理系统已经服务了多年,稳定、可靠、与本部门的工作流严丝合缝——只是它的哲学与分时背道而驰,它是为机器省时间设计的,不是为人省时间设计的。老系统的可靠与新需求的交互之间,隔着一整个时代:写好的作业装在纸带或卡片上排队,几个小时后取回一沓打印结果,一个逗号的错误就是一轮新的等待。当年连终端都是一种稀缺品:研究员面前的电传打字机以每秒十个字符的速度吱嘎作响,一行命令的回显要等足几秒;分时的全部意义,就是把这种等待变成对话——机器响应人,而不是人伺候机器。刚刚尝过分时甜头的人,是最无法忍受这种倒退的人。顺带一提,缺的也不只是机器:分时系统是一整套生态——编译器、编辑器、文档工具、能互相抄作业的同仁;每一环都要有人重写,而重写的人手,全部要从对 Multics 心灰意冷的幸存者里招募。就在这时,汤普森发现了那台没人认领的 PDP-7——数字设备公司 1964 年推出的 18 位小型机,彼时已属停产型号,原属于别的部门。机器原先服务于专利部门的文字处理试验,项目黄了,机器就没人认领——在讲究每台机器都必须自负盈亏的实验室里,一台闲置设备是最招人嫌的资产,也是最适合隐秘生长的土壤,内存小到以千字节计,磁盘慢到以秒计。在任何人眼里它都是一台报废边缘的废铁,在汤普森眼里它只有一个缺点和无数优点:缺点是小,优点是没人管。移植刚有眉目,里奇与同事卡纳迪就加入了进来,三人把最初那个临时拼凑的文件系统整个重写了一遍——这一次重写没有工期压力,没有甲方审查,每一处设计都只为一个原则服务:让下一行代码写起来更省力。没有人预见,这份自由散漫的重写,是 Unix 后来以清晰著称的源头。它的内存是几千个字的磁芯,字长十八位,算力只够打字机级的任务;但它是自由的——不排机时、不记账、没有管理者,任何深夜的任何想法都可以立刻上机验证。对一台被遗弃的机器来说,被一个闲不住的天才盯上,是它退役前最体面的结局。PDP-7 停产的另一层紧迫感是机器迟早会被收回——三人合写了一份采购申请,为实验室的文书处理要来一台新的小型机,批文在 1970 年落地;那台机器后来被称作 Unix 真正的成年礼舞台。

促使他动手的最后一个理由,说来近乎儿戏:一款他自己写的游戏。太空旅行(Space Travel)是汤普森在 Multics 时代编写的模拟程序,玩家驾驶飞船在太阳系里航行,借助各行星的引力调整轨道——一个纯粹为了好玩的物理玩具。Multics 撤出后,他把游戏搬上了实验室的 GE 机器,结果发现每玩一次,机器按机时折算的成本高达七十五美元;一台大型机跑一个游戏,这笔账荒诞得刺眼。把游戏搬上那台无人使用的 PDP-7,就成了整个项目的合规理由。合规的理由找到了,工作的性质却悄悄变了:为了让游戏在十八位小机器上跑起来,得先给它配磁盘的读写,配磁盘读写就得有文件的组织方式,有了文件就要有修改文件的手段——每解决一层,就冒出下一层,等所有层都铺完,回头一看,一个操作系统的全部骨架已经站在那里了。日程表的执行也并非一帆风顺:内核写完,文件系统卡了几天,编辑器几乎推倒重来——四周里的每一个深夜,隔壁的电话都可能把整个项目叫停,但它奇迹般地安静到了最后一个星期天。那七十五美元一局的标价由此有了完整解释:按机时计费的年代,娱乐是最奢侈的用途;而当游戏跑在了不记账的机器上,省下的每一美元,都在给一个新系统报销开发费。他不是要造操作系统,只是要让游戏免费地跑起来。为了让游戏跑起来,他需要写磁盘调度;写了磁盘调度,就需要文件;有了文件,就需要编辑器;有了编辑器,就需要把这一切管理起来的内核——游戏是诱饵,操作系统是渔获,历史在这四周里完成了一次最不像革命的开局。游戏本身也值得一句描述:飞船在太阳系的行星引力场里穿行,每一脚推进都要按真实的引力公式结算轨道——它是一个披着娱乐外衣的数值计算程序。引力模拟对当时的机器是个苛刻考题:轨道精度取决于浮点运算的耐心,行星位置要画在示波器或打孔纸上,每一步推进都是一次完整的计算流程排练——写这个游戏练出的手艺,与写操作系统的手艺,重合度远比表面看起来高。这台机器后来在历史上有了自己的坐标:Unix 家谱的第一页,用的就是它的序列号——工程师对第一台机器的感情,近似天文学家对第一台望远镜的敬意,对机器的运算与显示都有正经要求。让这样的程序流畅运行,本身就是一次对小型机能力的全面测试。

一切皆文件

四周写出操作系统的故事之所以可能,是因为 Multics 的五年已经把所有的坑都踩过一遍。汤普森和里奇手里没有图纸吗?有——Multics 的设计文件、他们自己写过的代码、哪些设计精妙哪些纯属负担,全都装在这两个人的脑子里。PDP-7 上这套新系统的每一处决策,都是对母系统的一次裁剪:Multics 有的,先问这个只有几十万字节内存的机器配不配拥有;配得上的,用最短的方式重写;配不上的,干脆不要。裁剪下来的第一件成品,成了 Unix 最著名的遗产——文件系统。

Unix 文件系统做出的第一个决定是激进的:不区分文件类型。磁盘上的东西一律是字节的序列,系统不知道也不关心里面是文本、代码还是图像;目录本身也是文件,设备也是文件——你的终端、打印机、磁带机,在文件系统里都以一个文件的名字出现,用同一套读写调用访问。这就是后来被无数文章引用的那句原则:一切皆文件。它的好处在当时体现为极致的省:系统只需要实现一种读写逻辑,所有外设自动获得全部文件操作;它的好处在后来看得更远:任何程序,只要能读写文件,就能与任何设备、任何其他程序对话,接口的统一给了整个系统一种可拼装的通用语。接口统一的深意要再过几年才显影:程序一旦不依赖设备的任何特性,它就不再依赖某一台机器——为这个终端写的程序换个终端照样跑,这份可移植的基因日后长成了 Unix 最重要的商业价值。种子在 1969 年就已埋下,只是当时浇灌它的理由,仅仅是省事。第二件成品是目录的形状:文件系统长成一棵自根而下的树,每层目录都是上一层的一个文件——Multics 也发明过层次目录,Unix 把它简化到只用斜杠和名字就能描述世界上任何一个文件的地址。这段骨架,今天仍然长在每一台电脑里。简化同样体现在权限上:Multics 给每段信息配了一张复杂的属性清单,从读到写到与谁共享逐项登记;Unix 把这一切砍到九个权限位,读、写、执行各配三档身份。砍掉的复杂度都变成了速度与可理解性——一台几千字的机器装不下法案级的权限表格,九个比特刚刚好。对照之下更能看清这份简化的分量:同样的树形结构,在母系统里要与环保护、多层属性、访问名单共同工作,每打开一个文件都要穿过几层检查;在 Unix 里,打开文件就是沿着路径找到那串字节。母系统的每一个部件都更有学问,儿子的每一个部件都更好用——工程史一再证明,学问与好用是两回事。文件名也短得吝啬,系统调用的参数表短得像便条,每一个接口都在为稀缺的内存精打细算;这种从贫困里长出的克制,日后被证明比任何富余的设计都更长寿。贫困还教会了他们另一件事:文档要与代码住在一起。系统的每一版手册都随源码一起更新,功能、用法与限制写在同一页纸上——后来工程师们习以为常的手册文化,就是在那台 PDP-7 的磁盘空间账单里养成的。几十年后,网络资源、进程信息、远端存储都被陆续装进了文件模型的延伸里——一切皆文件,成了系统设计史上被复制最多的一个句式。

   一切皆文件:统一的接口  
  
   /            (根目录——也是文件)  
   ├── usr  ──┐  
   ├── bin    │   目录:是文件  
   ├── etc    │   磁盘:是文件  
   ├── tmp    │   终端:是文件  
   └── home   │   打印机:是文件  
              │  
              ▼  
   read(fd, buf, n)   write(fd, buf, n)  
   ── 同一套系统调用,通吃一切设备 ──  
  
   代价:系统不区分字节里装的是什么  
   收益:任何程序可以读写任何东西  
        → 程序之间有了通用语  

管道:一根竖线接起的工具箱

一切皆文件解决的是程序与设备的对话,真正解决程序与程序之间对话的,是 Unix 的第二件国宝:管道。它的构想其实早于 Unix 本身——贝尔实验室的道格·麦克罗伊(Doug McIlroy)在 1964 年的一纸内部备忘录里就设想过,把程序的输出像园丁的水管一样接进另一个程序的输入,让数据在程序之间像水流一样串起来;当时的系统谁也没有能力实现这个想法,备忘录在抽屉里躺了几年。麦克罗伊是实验室计算技术研究方向的负责人,1968 年就发表过倡导大规模生产软件组件的文章——管道是他那套组件理想在操作系统里的落地:组件之间不共享内部状态,只交换明码的数据;管子两头是谁,彼此不必认识。汤普森在给 PDP-7 系统添置工具时把它捡了起来,做出了管道:内核里开一段缓冲,一个进程的输出从这头流进去,另一个进程的输入从那头流出来,竖线符号 | 立在两个命令之间,数据就自己找到了下游。这根管子的技术本质毫不神秘:内核里开一块缓冲区,写进程把字节放进去,读进程从里面取出来,两边以流水线的节奏自动同步——一端写满就等,一端取空就等,谁也不必知道对方是谁。在管道出现之前,程序之间的接力要靠中间文件:第一个程序把结果写到磁盘,第二个程序再把文件读进来——数据在毫秒级的磁盘上白白落一次地。管道把这次落盘整个取消,接力发生在内存里,速度差了几个数量级;省下的不只是时间,还有把中间结果组织成文件的全部心智负担。

管道的威力,在麦克罗伊后来常举的那类例子里一目了然:统计一批文件里最常用的十个词,把“列出单词”“合并重复”“按频次排序”“取前十”几个只有单一功能的小工具用竖线串起来——六条命令,五根管道,一行程序都不用写,任务就完成了。每个工具只做一件事,把它做到极致;程序的输出应当能成为另一个程序的输入,因为文本流就是通用语言。麦克罗伊后来把这套经验总结成几条可以背下来的原则:让每个程序只做好一件事;让每个程序的输出成为另一个程序的输入;尽早做出原型来试;宁可借用工具,不要雇人写一次性程序。原则没有一条谈到性能或功能,全部在谈程序之间的关系——这套关系学,是 Unix 留给软件工程最深的一枚印章。这套后来被总结成 Unix 哲学的信条,本质上是一种分工制度:与其在每一个程序里重新实现排序和统计,不如把排序和统计各自做成一件好工具,靠管道自由组合。麦克罗伊津津乐道的那个演示,后来成了整个文化的入教仪式:想知道一篇文档里哪个词用得最多,不必打开任何集成软件,把挑单词的工具、合并计数的工具、排序的工具、取前十的工具用四根竖线串成一串,答案就从管子另一头流了出来。每个工具都小到可以在一分钟内学会,每个工具都不知道也不关心整条流水线在做什么——正是这种互不知情,保证了任意重组的可能性。组合的可能性是乘法式的——十件工具两两相接,就有一百种工作流。柯林汉与麦克罗伊在实验室里不知疲倦地布道这套玩法。这场布道能成功,离不开贝尔实验室的土壤:这里数学家、物理学家与工程师混居同一层楼,研究者可以自由选择课题,做成一件工具的声望不亚于发表一篇论文——工具文化是实验室几十年的沉淀,Unix 只是把它推向了极致,工具箱以肉眼可见的速度变厚。厚到一定程度,组合的用法开始反过来教育工具的作者——用户在管道里暴露出的真实用法,成了下一代工具的需求文档。管道之所以敢于自由组合,靠的是一条朴素的纪律:每个工具的输入输出都是同一种东西——文本流。只要接口是字节序列,工具就可以像积木一样任意对接;谁也不需要知道上游是谁、下游是谁。这种正交性让组合的可靠性可以推理,而不是碰运气——大型集成程序做不到这一点,因为它的部件之间互相认识:找文件的、数行的、替换文字的、排版文档的,每件都小得可以被一个人读懂,每件都因此永远可靠。

命名、落地与一场无人预料的扩散

在拥有名字之前,这套系统先拥有一段彻底的与世隔绝。Unix 史料圈把 PDP-7 上的开发期考订为 1969 年年中到 1970 年年底,并记下一句常被忽略的事实:这版系统从未在贝尔实验室之外发布——没有拷贝流出,没有外部用户,没有会议演示,它的全部用户就是写它的那两三个人;Unix 遗产维基(tuhs.org)的档案为此专设条目,逐段记下这版系统从出生到被复制进新机器的全部行程。封闭在后世看来近乎浪费,在当时恰恰是它能长成后来那个形状的前提:没有外人,就没有兼容包袱;没有发布压力,就没有功能清单;每一个设计决定只需要对作者自己的手感负责。从 Multics 带来的构件——层次文件树、shell、把设备抽象成文件的念头——在这十八个月里被拆开、裁剪、重新焊接,系统在无人注视的角落完成了全部定型。这段与世隔绝还解释了 Unix 早期文献的一个脾气:最早的手册不解释动机,只记录行为——作者即用户,动机无须向任何人陈述。等它第一次需要名字的时候,形状已经长死:一个把 Multics 的思想密度压进几十千字节的孤本;后世的考据者把这十八个月称作 Unix 的孵化期——蛋壳里的形状,注定比任何外来的意见都顽固。这份孤傲后来被证明是一种幸运:等外界第一次见到 Unix,它已经度过了最脆弱的婴儿期。给孤本起名,是它面对世界的第一步。

给这个系统起名字的过程,本身就是它的身世自白。它的一切思想来自 Multics,规模却只有对方的几十分之一,柯林汉想出的 Unics——把 Multics 的 MULTI(多)换成了 UNI(单),读音里还藏着阉割(eunuchs)的玩笑——精准得让所有人会心一笑;拼法几经流转。提议这个名字的布莱恩·柯林汉(Brian Kernighan)是实验室里的另一位妙人:他与里奇后来合著的那本 C 语言教材,版税养活了半个 Unix 社区的书架;他起名字时埋下的那个双关,也让 Unix 从出生起就带着对母系统的全部敬意与调侃——一个名字同时记录了出身与叛逆,这在命名史上并不多见。命名上的从容也是实力的旁证:只有当系统的质量过硬时,给它起个玩笑名字的风险才冒得起——玩笑与自信,在这册薄薄的程序员手册里是一回事,定名为 Unix。1971 年 11 月 3 日,《Unix 程序员手册》第一版印成,汤普森与里奇署名——一个操作系统的官方身份证,第一次是以一册内部手册的形式出现。这本手册藏着一个自我指涉的细节:它的排版就是用 Unix 自己的文字工具完成的——系统出生后的第一份公开文件,是用系统自己排出来的;从此以后,吃自己的狗粮成了这个家族的传统。第一版手册收录的命令只有几十条,每页都短得像便条;纸薄,字少,却让任何一个好奇的人可以在一周内读完系统的全部对外行为——文档的尺寸,就是系统的尺寸。

让 Unix 从玩具变成工具的,是实验室里的第一批真实用户。专利科要处理堆积如山的专利文书,需要一个能排版、能检索的文字处理系统;汤普森与里奇用 Unix 加一套排版工具接下了这单生意——专利部门成了 Unix 历史上的第一位客户,一纸一份的专利文书,是这套系统挣到的第一份口碑。为了这份文书生意,Unix 完成了它第一次整机搬家:实验室为新任务租来了一台新的 PDP-11 小型机,系统随之从十八位的 PDP-7 移植过去;配套的排版工具被写出来,第一份用这套流程排出的专利申请文件送进了审核流程。从这一刻起,Unix 不再是一个人的游戏,它有了雇主、有了服务对象、有了必须按时交活的生产压力——玩具在压力下长成了工具。专利科的订单还带来一个副产品:为了排专利文书,系统里长出了格式工具与检索工具的前身——文字处理这个最不起眼的应用,成了 Unix 第一次养活自己的手艺。此后的扩散带着浓厚的时代印记:贝尔实验室的母公司 AT&T 身陷反垄断诉讼,1956 年的和解协议本就禁止它涉足计算机商品市场,1969 年司法部的新诉讼更让任何商业化动作都变成法律风险——Unix 被禁止当作产品出售,只能作为内部工具存在,或以象征性的介质费用向大学提供源代码。这段法律钳制的来龙去脉值得记一笔:1956 年的和解协议本就禁止 AT&T 经营计算机商品,1969 年司法部又发起新的反垄断诉讼——在诉讼期间,把 Unix 卖出去的每一步都可能被解读为垄断行为的延伸。于是贝尔实验室选了最省事的做法:要源码的大学,付一盘磁带的钱就搬走。钳制商业的手,无意中打开了教育的大门。这项限制在当时被所有人视为遗憾,回看却是天赐的礼物:源代码随磁带流进了加州伯克利、流进了全球高校的机房,一代学生在纸上读懂了操作系统的全部秘密——那是任何商业许可证都买不到的传播速度,而它的故事,才刚刚开演。

极简的账单

清算 Unix 的诞生,不能只记下赞歌。极简主义的每一项简化,都在账单的另一页记了成本:文件不区分类型,系统便无从校验,格式错误要等到程序崩溃时才被发现;单用户血统让它从出生起就没有真正的多用户保护——既然当初整台机器只有汤普森一个人用,权限与隔离自然能省则省。代价在系统变成多用户之后立刻显形:七十年代的高校机房里,一门课程作业的失控循环就能把整台机器拖垮,因为内存里没有栅栏;教授们不得不在讲义里附上一页机房礼仪,请求学生手下留情。一个靠自觉运转的系统可以靠传统维系于实验室,却无法靠传统维系于世界——补课的账单,后来以十年为单位陆续寄到。最著名的学费案例是一对貌不惊人的复制命令:它的参数写法直接承袭自大型机时代的作业控制语言,把 Unix 一贯的短平快美学击得粉碎——历史包袱的分量,往往精确落在最常用的那件工具上。这个缺口后来花了几十年、几代机制才补齐;几十万字节的小内存还教会了它用最晦涩的短命令做名字,易写不易读,学习曲线从此陡峭了半个世纪。

补课机制后来都有了正式的名字:身份切换、访问控制、能力令牌——每一个都是一整卷教科书的开头;它们全部源于同一个遗憾:1971 年的那个系统里,只有一个用户。补偿的措施也逐渐长成传统:系统崩溃时把内存原样倾倒出来供人事后解剖,崩溃不再只是事故,而是一份自动生成的作业报告——从错误里学习的成本被压到最低,这是 Unix 对失败最务实的致敬。文本流的通用性同样有边界,遇到二进制数据,整条管道都要绕行。连哲学本身都被人过度引申——麦克罗伊晚年不止一次澄清,小而美讲的是比例感,不是洁癖;把哲学当戒律,恰恰违背了哲学。更隐蔽的一笔账是思想的:极简主义后来在部分信徒手里僵化成了教条——仿佛小就等于美,大就等于错;可 Multics 的复杂并非全然多余,那些为多级安全、为强制隔离付出的复杂度,Unix 用了几十年才以别的方式慢慢补回。Unix 的拥趸后来把母系统简化成一个臃肿的笑话,这既公平也不公平——公平在于它的工期与成本确实失控,不公平在于它为安全与共享趟过的路,胜利者走的时候一样也没少走。历史由胜利者书写,但基础设施由失败者奠基。两条路线的真正区别,在于各自选择了为谁付费:Multics 为所有未来的用户预先付费,Unix 为眼前的这位用户当场付费——商业上前者破产,工程上后者留名,而用户两种账单都付过。

这笔账还改写了“谁能编程”的社会定义。大型机时代的机器属于机构,操作系统属于厂商,普通人与计算机的关系隔着机房与批处理单;Unix 跑在一台小型机上,内核小到一个人可以通读,源代码躺在可以随手翻阅的纸卷里——计算机第一次变得可以被个人完整理解、修改与拥有。管道与工具箱又把这种可及性变成了创造力:一个懂几条命令的普通人,不需要写任何传统意义上的程序,就能把系统里现成的部件组装成新的工具。认知的门槛被这套极简设计实实在在地削低了一截,削低的每一寸,都在为十几年后个人电脑时代的批量平权做准备。有人把这场搬家概括得更狠:大型机时代,知识按职级分发;Unix 时代,知识按好奇心分发——分发机制的变更,比任何单项技术的发明都更能改变行业的人口构成。这种准备有一个常被忽略的前提,机器的价格:Unix 能进入大学机房,靠的是小型机把主机百万美元的门槛降到了几万美元;门槛每降一级,能摸到操作系统源代码的人数就翻一群。认知平权从来是硬件价格的孩子,软件的极简只是让到手的每一台机器都物尽其用。承诺兑现得比预想更快:整个七十年代,Unix 加小型机的组合成了大学计算机系的标配,操作系统的源代码第一次可以被本科生逐行阅读;各国高校用它培养出的那几代学生,此后三十年掌管了从工作站到互联网的全部地基——平权不是口号,是一门可以阅读的课程。

说到最后,1969 年那个夏天最耐人寻味的,是它揭示了极简的真相:Unix 的简单并非设计者的品味偏好,而是资源限制与制度限制的双重挤压之下,唯一可行的姿态——当一台机器小到只能装下必需品,必需品的样子反而清晰起来。汤普森用四周证明了 Multics 用五年没能证明的事:一个系统的第一美德,是可以被一个人完整地理解;而理解,是一切改进与一切平权的前提。十年后,这对搭档摘走了计算机科学的最高荣誉;评审词里最重的分量,恰恰不是某个算法,而是他们证明了一个人人都能读懂的系统,可以比一个无人能读懂的系统更可靠。这段摇摆至今没有终场:云时代的巨头重新抬出公用事业的旧梦,开发者的世界又时时掀起极简的反叛——每一代人都以为自己发明了新的答案,其实只是在汤普森的四周与 Multics 的五年之间,重新选了一次边。


第 028 章 1973:Unix 用 C 重写与可移植性的惊险一跃

把内核逐段换掉的人

1973 年,新泽西州茉莉山的贝尔实验室,计算科学研究中心的一台 PDP-11 整日嗡嗡作响。这台机器 1971 年才到货——此前 B 语言的宿主 PDP-7 已经太小,装不下日渐长大的系统。肯·汤普森(Ken Thompson)与丹尼斯·里奇(Dennis Ritchie)在这台机器上做一件当时几乎没有先例的事:把 Unix 操作系统的内核,从汇编语言逐段翻译成一门两岁大的语言——C。里奇的履历在系统程序员中显得格外学究:哈佛物理学士,应用数学研究生,1968 年的博士论文研究递归函数层级;1967 年进入贝尔实验室后,先在 Multics 项目里写 BCPL 编译器,又为符号数学语言 ALTRAN 写编译器——两次编译器经历,恰好是后来改造 B 语言所需的全部手艺。此前的操作系统几乎一律用汇编写成,理由看似天经地义:内核是机器的最底层,直接操作寄存器与设备,理应与指令一一对应。把这一层换成高级语言,等于宣称“操作系统的生命不必与任何一块芯片绑定”。翻译持续了大半年,到这一年年底,内核的绝大部分已经是 C 代码;同年发布的第四版 Unix,成为第一个内核完全以 C 写成的版本。1971 年 11 月,第一版《UNIX 程序员手册》印行,至今通行的 man page 格式即始于此。1974 年,两人把成果写成论文《The UNIX Time-Sharing System》发表在《美国计算机学会通讯》上——一篇只描述了一个小型分时系统的论文,日后成为被引用最多的系统论文之一。它也是那次重写的公开答辩:世界第一次被正式告知,一个完整的多用户操作系统可以不用一行汇编写成。

这次重写事后被称为惊险一跃,因为它同时踩在两条深渊边上。一边是性能:编译器生成的代码那时普遍慢于手写汇编,而内核慢一分,全系统的每一户分时用户都能感觉到。另一边是表达力:彼时的高级语言大多为科学计算而生,没有哪个既有语言能直接摸到设备寄存器与内存地址——写内核需要一门“比汇编高一寸、比一切语言低一头”的语言。这门语言还不存在,于是他们自己造了一门。C 语言的前身可以追溯到 BCPL,汤普森把它裁成极简的 B 语言用在 PDP-7 上;等系统搬上 PDP-11,B 的无类型与单字长设计捉襟见肘,里奇在 1971 到 1972 年间给这门语言补上数据类型、更丰富的类型结构与新的语法,C 由此成形——名字按字母序接在 B 之后,也向 BCPL 致敬。里奇晚年回忆,C 最具创造性的时期正是 1972 年,整个演化期从 1969 年持续到 1973 年;一门语言与一个操作系统,在同一间办公室里互相塑造着长大。

C 的语言哲学是一次精打细算的妥协。它比汇编高一层:有函数、结构化控制流、数组、结构体、独立编译的单元和一套紧凑的标准库习惯;它又比一切同类低半层:通过指针直接暴露内存地址,允许指针运算,把数组边界、内存回收这些检查统统留给程序员。这种“既贴着硬件又能跨机器”的性格,恰好命中系统编程的软肋——既能写内核与驱动,又不被焊死在某颗芯片上。里奇对它的终身评语只有一句,克制而诚实:“古怪、有缺陷、却获得了巨大成功。”1978 年他与布莱恩·克尼汉合著的《C 程序设计语言》出版——这本薄薄的小书以例子驱动,既当语言参考又当写作范本,后来成了几代程序员的共同启蒙;1989 与 1990 年,ANSI 与 ISO 先后把 C 收编为正式标准。

要理解 C 为什么长成后来的形状,得先看 B 为什么不够用。汤普森在 PDP-7 上创造的 B 语言脱胎于 BCPL,小巧、直接、几乎不带类型——在一台字长统一的小机器上,这种极简主义如鱼得水。1971 年贝尔实验室购入 PDP-11,问题随之而来:新机器以字节为单位处理字符,硬件能力上了一个台阶,B 的无类型字长模型却对不上号;日渐庞大的 Unix 也开始需要更复杂的数据组织。里奇的改造于是有的放矢:给语言装上数据类型与类型结构,让它能描述字节、字、指针各自的疆界;加上结构体与新的语法,让它能组织操作系统需要的复杂数据。C 的几乎每一项发明,都是 PDP-11 与 Unix 的具体需求按在语言身上的手印——里奇本人的回顾反复强调,这些决定是对逼仄机器、现有编译器与真实内核代码的回应,从来都不是在白板上凭空设计一门完美语言。

几个著名的设计决定里,藏得最深的是字符串。C 的字符串以一个全零字节结尾,而不是在开头存长度——后世无数缓冲区漏洞都可以追溯到这里,但它的动机相当务实:B 沿用的那套带长度字段的字符串约定会撞上一个小的长度上限,零值结尾的方案干脆绕开了这个限制。在内存以 KB 计的机器上,这是聪明的取舍;在攻击者学会往结尾之外写数据的年代,它成了漫长的账单。同样的逻辑也解释了指针与数组的纠缠、手工内存管理的放任:每一项“缺陷”在 1972 年的约束下都有一张说得过去的收据,只是收据的偿还期长达半个世纪。语言设计与所有工程造物一样,账期与收益从来不同步。

惊险一跃的论证:为什么操作系统可以用高级语言写

用 C 重写内核并不是灵光一现,而是一场有意识的论证。反对的立场在当年完全站得住脚。汇编派的理由有二:其一,性能——内核代码每周都在热路径上跑,编译器的每一次低效都会放大成全系统的迟钝;其二,传统——操作系统的职能就是封装机器差异,用机器的母语写它,是对这一职能最忠实的表达。何况此前并非没有高级语言写系统的尝试,B 语言在 PDP-11 上的力不从心就是现成的反面教材。把这些理由放回 1972 年,任何一个严谨的系统程序员拒绝 C 重写都是职业判断,而非保守顽固。

汤普森与里奇的对策是把语言的刀口磨到刚好。C 保留了指针运算与位级操作,内核里所有“贴地”的动作——读写设备寄存器、按内存布局解析数据结构、开关中断——都能直接表达;同时函数、结构体与独立编译让内核可以按模块切分、逐段替换。翻译是渐进的:数据结构先换成 C 的结构体,然后是子例程,最后才是调度与中断这些最深的部分。每换一段,系统照常运行,性能全程可测——惊险一跃其实走的是台阶。台阶的另一侧没有安全网:任何一次翻译引入的语义偏差,都会在最意想不到的时刻炸响,而那时的调试工具只有打印语句与过人的耐性。当内核主体完成,收益自动显形:同一套 C 源码在 PDP-11 的各个型号之间已经畅通,而要迁往别的架构,需要重写的只剩编译器与一小撮与机器直接相关的底层代码。里奇与约翰逊随后把 Unix 移植到与 PDP-11 完全异构的 Interdata 8/32 上,这次跨物种迁移证明,可移植性已经溢出了 PDP-11 家族的边界——它成了 C 重写带来的普遍能力。此后十年间,Unix 或类 Unix 系统被移植到至少十六种处理器架构、约六十家厂商的机器上;1983 年,汤普森与里奇因“通用操作系统理论的发展与 Unix 的实现”同获图灵奖。这段生态扩张有一个容易被忽略的基础设施:Unix 是带着源码旅行的。二进制软件的迁移要面对每台机器的指令集,源码的迁移只需面对每台机器的编译器——后者是可以批量培养的专业技能,前者是逐台机器的翻译工程。C 重写把系统软件的迁移成本,从再造降到了适配,操作系统由此第一次成为跨厂商的公共基础设施。

这一跃改写了系统软件的寿命公式。在它之前,操作系统的寿命等于宿主机型的寿命,机器退役、软件陪葬;在它之后,操作系统开始拥有独立于任何硬件的生命线——系统可以被“搬”走,就像书可以换一个书架。软件第一次具备了遗产的形态,而执行这份遗产的机构,是一台编译器。

一件不能卖的产品:反垄断禁令的制度意外

重写成功之后,正常剧本里的下一幕是商业发布——一个更好的操作系统,卖出去。Unix 的剧本在这一页被法律撕掉了。贝尔实验室的母公司是美国电话电报公司(AT&T),而后者自 1949 年起就处于美国司法部的反垄断诉讼之中。1956 年,双方达成庭外和解,史称同意法令:AT&T 此后只能经营受政府监管的公共电信承运业务,被明文禁止进入计算机、软件销售、数据处理等任何其他商业领域。也就是说,1969 年 Unix 在实验室里诞生时,它的母公司在法律意义上根本不存在于计算机行业——这个操作系统从出生起就不具备被出售的资格。

禁令把常规的软件商业模式整个堵死,却把另一条路照亮了。既然不能当产品卖,AT&T 也就没有理由把 Unix 当作机密资产经营;既然无法承诺商业支持,它分发源码的形态反而自由。1974 年那篇论文发表后,各地高校与研究机构索取系统的请求源源不断,贝尔实验室的应对方式在商业史上近乎行为艺术:把 Unix 的完整源码连同手册装上磁带,按磁带与介质的实际成本象征性收费,寄出。不承诺支持,不负责缺陷,不做任何广告——一件法律上不能卖的产品,以研究合作的名义流进了大学的机房。贝尔实验室内部对此的态度与其说是慷慨,不如说是坦然:研究机构的传统本来就是论文与手艺同行,磁带走到哪里,论文的引用与缺陷的报告就回到哪里——对一间靠声誉运转的实验室,这几乎是最划算的回报方式。

这个意外的影响怎么估计都不为过。随磁带而来的不只是可以运行的系统,而是可以阅读、可以修改、可以当成教学母本的完整源码——在软件普遍以神秘二进制交付的年代,一代计算机系学生第一次有机会逐行读到一个真实操作系统的内脏。课程围绕它开设,学位论文围绕它展开,缺陷修复与增强顺着信件回流到贝尔实验室。最重要的节点在加州大学伯克利分校:比尔·乔伊(Bill Joy)在这里成长为 BSD 系统的主要开发者,伯克利分支逐渐长出与贝尔正统分庭抗礼的能力,乔伊后来参与创办了太阳微系统公司(Sun Microsystems)。到 1980 年代,Unix 或类 Unix 系统已可用于至少十六种处理器架构、约六十家厂商的机器;BSD 与获得 AT&T 许可的 System V 成为两大谱系,此后整个 Unix 世界的谱系战争,都在这两个母本的后代之间展开。

制度的钟摆在 1983 年又摆了回来:反垄断诉讼以 AT&T 的解体告终——同一年,图灵奖的评奖词把通用操作系统理论与 Unix 的实现写进汤普森与里奇的获奖理由;一门手艺的最高荣誉与一个生态的解禁判词,落在了同一本日历上。禁令随之解除,AT&T 终于被允许进入计算机业,立刻把 Unix 商业化为 System V,自由分发的公地时代就此落幕,许可证战争拉开帷幕。但已经长成的东西收不回去了——伯克利的血统、教学的传统、源码阅读的文化,都已在禁令年代完成社会化。回头看清这组因果的对称性是必要的:一部 1956 年针对电话垄断的判决,孕育了 1970 年代最开放的软件生态;1983 年的解禁判决本该解放它,实际效果却是把公地圈成了猎场。禁令不是Unix 成功的原因,却决定了它成功的方式——以谁都不曾设计过的形态。

可移植性承诺的成色,要靠最苛刻的检验。Interdata 8/32 是一次严酷的测试:它与 PDP-11 没有任何血缘,指令集、字节序、寄存器组织全然不同。1979 年发布的第七版 Unix 是这条路线的集大成者,被后来的开发者奉为经典母本——此后每一版都不得不在研究趣味与商业许可之间走钢丝。Interdata 8/32 与 PDP-11 没有任何血缘:指令集、字节序、寄存器组织全然不同,堪称最苛刻的试金石。里奇与史蒂夫·约翰逊(Steve Johnson)在汤普森协助下完成的这次移植证明了两件事:其一,C 重写后的 Unix 确实可以跨物种;其二,移植的真实单位被永远改变了——不再是重写一个操作系统,而是为新品写一个 C 编译器,加上数千行与机器直接相关的底层代码。第七版 Unix 正是从这次移植中长成,成为后世诸多系统的母本。

但精确的史观要求把“可移植”三个字的税单也亮出来。C 时代的可移植,严格说是源码级的可移植:同一份源码,在每台新机器上都要重新编译,编译器要重新适配,机器相关的底层要重新校准——“一次编写,到处编译”,而不是后来虚拟机路线许诺的“一次编译,到处运行”。每一台新机器仍要养一小队懂底层的人,维护那一小撮永远无法通用化的汇编边缘;源码虽然通用,依赖机器行为的细节依然是移植事故的高发区。这份税单与 System/360 的兼容路径对比起来格外清晰:IBM 用五十亿美元买下了单一公司内部的机器家族兼容,Unix 与 C 用一间实验室的克制买下了跨公司、跨架构的源码兼容——后者没有统一的公司主体担保,靠的是一门语言标准的权威与整个学术共同体的自觉。两种兼容,两种治理:前者靠契约条款,后者靠共同信仰。自觉这个词值得拆开看:它包含源码可读带来的理解、教学相长带来的熟练,也包括几代学生把改进寄回贝尔实验室的缓慢回流。此后软件世界的可移植性之争,始终在这两种治理模式之间摆动。

Unix 与 C 的故事还有一条常常被略去的伏笔:贝尔实验室 1969 年从 Multics 项目撤退。Multics 是贝尔实验室、麻省理工学院与通用电气合作的宏大分时系统,目标崇高、工程浩大,最终因过于庞大与一再延期而被贝尔实验室放弃。撤退的队伍没有扔掉行囊——进程、层次文件系统、命令解释器、交互分时这些 Multics 的核心想法被原样保留,只是换了一种实现策略:不再造一台服务于全行业的机器,而是先做一个自己用得顺手的小系统。小系统的甜头随后接连涌现:代码少到可以通读,接口紧凑到可以组合,缺陷藏不住。这段对照的教益在后来几十年被反复验证:宏大系统的失败很少败在能力上,多败在复杂度的复利上;而 Unix 证明,那些崇高的想法可以用千分之一的代码量兑现。与此同时, Unix 的文档文化也在成形——手册、论文与源码并行传播,读者不仅能学会系统做什么,还能看到资深系统程序员如何陈述取舍;里奇本人的写作以极度节制著称,这种文风本身成了 Unix 文化的一部分。克尼汉后来在悼词里说,里奇退休之后仍持续出现在贝尔实验室,直到 2011 年去世——一个人与一个实验室、一门语言、一个系统之间长达四十余年的缠绕,至此才算落幕。

C 的另一面:没有安检门的语言

账单的另一面必须全额列出。C 把内存地址直接交到程序员手里,允许指针在数组边界之外运算,不做越界检查,内存的分配与回收全凭手工;字符串以零字节收尾;相当一批程序错误被语言标准定义为“未定义行为”——编译器被允许假设它们不会发生,于是同样的代码在不同优化等级下可能呈现不同结果。这些决定在当时的机器上都是理性的:每一次运行时检查都是真实的时间与内存开销,而内存贵得按 KB 论价。但取舍的利息在几十年间持续累积:这一类缺陷成了此后数十年软件安全漏洞最主要的来源之一,整个内存安全工具链与新一代带运行时检查的语言,本质上都在为 1972 年的那纸取舍补票。补票的方式千差万别:有的在编译期加检查,有的在运行时加护栏,有的干脆发明新语言把危险的句法整个废除——无论哪一种,动机清单的第一行都写着 1972 年那个内存以 KB 计的冬天。Unix 本体的安全模型同样简单——属主、组、其他三组权限位加一个超级用户,设备被当作文件对待;这套模型支撑起了实验室与研究机构,等它面对网络与不可信的多租户世界时,后来的系统不得不在其上层层加码:网络协议栈、访问控制、容器、强制访问控制一层层叠上去。里奇对此并不讳言,他为 C 写下的那句自评,与其说是辩护,不如说是一份公开的损益表。

值得写进结论的是这一切的走向:1989 年与 1990 年,ANSI 与 ISO 相继把 C 正式标准化——一门诞生于贝尔实验室单间办公室的语言,最终以国际标准的身份重新定义了自己。里奇本人在 Unix 上的最后一项重大技术贡献是一套名为 Streams 的设备与协议互联机制;此后他把研究转向分布式系统,贝尔实验室的 Plan 9 把“一切皆文件”的旧信条推到了跨网络的疆域——晚年他没有离开,只是把同一个想法又往前推了几步。从 1973 年那次重写算起,仅仅十六年,C 完成了从内部工具到公共契约的全部路程;此后无论语言如何更替,大括号、分号、赋值表达式这些 C 的视觉语法,都作为通用记号留在了后来者的语言里——C++、Java、JavaScript、Go 的语法谱系里都有一段 C 的基因。两个成就还互为放大器:Unix 的可移植帮 C 开枝散叶,C 的随处可得又让 Unix 走得更远;在其中一个环境里受训的程序员,几乎总会顺手学会另一个。

重写的主角只有两个人,但公允的记述必须抵抗把故事写成单人传奇的冲动。里奇在自己的官方传记里写下的措辞是“我协助了肯·汤普森”,并反复把最早的构想与最初的工作归给对方;反过来,汤普森后来也把语言的成熟归功于里奇。合理的读法是分工而非排名:汤普森是先行者,1969 年在 PDP-7 上的那台玩具系统是他的手笔;里奇是推进者,把系统的可移植性与语言本身推到了临界质量。两人身后站着一整排可以列名的同事——麦克罗伊、罗伯特·莫里斯、史蒂夫·约翰逊、克尼汉——工具、语言、文档与文化各有其父。里奇的数学训练(哈佛的应用数学博士论文研究递归函数层级)给了他从约束出发思考的习惯,他的写作以极度的节制著称;这种“数学胃口配工程厨艺”的气质,恰好是给操作系统选语言、给语言配操作系统所需要的。1983 年的图灵奖同时授予两人,评奖词强调的是通用操作系统理论与 Unix 实现——评奖委员会显然也拒绝二选一。

Interdata 8/32 移植之后,可移植性从证明变成了日常。1979 年发布的第七版 Unix 是这条路线的集大成者:它继承了两台异构机器上打磨过的 C 内核,成为此后 BSD 与 AT&T System V 两大谱系共同的母本之一。此后的谱系战争——伯克利派与 AT&T 派的系统之争——本质上是同一个可移植内核在两个制度环境里的分流:一支长在大学的公地上,一支长在重新获得商业资格的母公司账下。到 1980 年代中后期,Unix 或类 Unix 系统已经至少运行在十六种处理器架构、六十家厂商的机器上——一个 1969 年在报废时间表边缘的 PDP-7 上起步的私人项目,十五年间繁殖成一个覆盖整个产业的操作系统生态。这份生态名单里没有任何一台机器是它的“原生宿主”——它原生附着的介质,是 C 语言与源码本身。

复盘 1969 到 1983 年的这条因果链,会发现没有任何一步是照剧本走的。技术上,汤普森与里奇的重写证明了系统软件可以被翻译;制度上,1956 年的同意法令禁止了这套软件的合法出售;生态上,高校的索取与回馈把一件实验室内部的手艺变成了公共知识;文化的一环是 1974 年那篇论文与随之而来的磁带请求;等到 1983 年禁令解除、System V 商业化时,生态已大到任何一家公司都无法独自继承。链条上的每一个当事人都在做局部理性的决策——汤普森想要一个顺手的编程环境,里奇想给语言补上类型,贝尔实验室的律师要让分发合规,大学教授想要可读的教学母本,研究生想要一个能拆开研究的系统——没有谁在为后来那个庞大的 Unix 生态做布局。顺带做一次简短的反事实推演:假如 1956 年的判决网开一面,允许 AT&T 经营软件,Unix 大概率会以二进制加许可的形态产品化,高校拿不到源码,伯克利分支无从生长,那套源码阅读的文化或许会被锁在一家公司的内网里——禁令的价值,要在它消失之后才看得完整。制度与技术的双螺旋并不互相缠绕,它们只是恰好同处一室四分之一个世纪,然后各自沿着自己的延长线继续延伸。

寿命公式的改写

把这一章放回全书的兼容性主线,1973 年的贡献才能称出准确重量。System/360 在 1964 年确立的是家族内部的兼容——一个公司、一份契约、六台机器;Unix 与 C 在 1973 年确立的是跨越公司与架构的源码兼容——没有任何中央权威担保,靠的是一门语言标准的事实权威与学术共同体的共同习惯。前者是商业契约的兼容,后者是知识契约的兼容。还有第三层兼容在此章成形,它与前两层不同源:同意法令无意间创造的制度兼容——法律禁止变现,客观上禁止了生态被单一主体圈占。三层契约叠加之后,系统软件的世界出现了此前从未有过的现象:操作系统的寿命与任何芯片、任何公司、任何一部法律的任期全部脱钩——它住在源码里,而源码可以被任何人带上任何船。

1973 年的重写没有发明任何一条新指令,它发明的只是一种确定性:系统软件的寿命从此与芯片解绑;而 1956 年那纸针对电话垄断的判决,则以禁止出售的方式,把这套软件送进了人类历史上最慷慨的公共温床。软件世界最辽阔的两条路径,一条由工程师刻意铺成,一条由律师无意打开——此后几十年,每一门试图统治系统的语言、每一份试图圈住生态的许可证,都在这两条路径的延长线上争夺路权。这个断言可以反驳:反驳者只需证明,即便没有那次重写与那纸判决,同样的生态也会以别的路径长成——而这个证明,至今没有人做成。

回到 1971 年那个看似平常的采购事件:贝尔实验室购入 PDP-11。这台机器的到货在当时打破了某种平衡——不是机器坏了,而是原有的语言与机器的匹配坏了:B 语言在 PDP-7 的小字长机器上游刃有余,到了支持字节寻址、字符处理与更丰富硬件的 PDP-11 上立刻水土不服。多年后回望,正是这次“匹配的断裂”给了里奇改造语言的全部理由;没有 PDP-11 的到货,C 或许仍会诞生,但绝不会带着如此清晰的工程议程。历史在此处显示出它惯常的幽默:一次普通的设备采购,触发了一场语言演化;而几乎同一时期,Multics 项目的撤离又把一批成熟想法连同绝望一起留给了撤退者。到货与撤离,一个供给问题,一个供给答案——1973 年的重写站在两者的交点上。

这组对称还有一层制度注脚。Multics 是三家公司的正式合作项目,有合同、有目标、有管理;Unix 是撤退者在角落里的自留地,没有指标、没有审批、甚至最初没有名分。规模化的正式工程输给了角落里的自留地,输掉的方式尤其值得记录:Multics 的败因既与更快的机器无关,也与更高的预算无关——它败给了自身复杂度的复利:每个新功能的接入成本都在上涨,直到增长的曲线穿过任何可用的资源线。此后数十年的大型系统工程反复验证同一条曲线,而 1969 年的撤退报告是它最早的书面证词之一。

第七版发布之时,谱系分裂的条件已悄悄备齐。BSD 一侧握有伯克利的学术声望与乔伊的个人影响力;AT&T 一侧握有法理上的源码版权与即将解禁的商业许可。有趣的是双方对“兼容”的态度:大学分支不断为系统增添实验性能力,商业分支则小心翼翼维护接口稳定以保住企业客户——同一个内核母亲的两个孩子,一个被纵容着创新,一个被要求着守成。1964 年 System/360 时代由 IBM 一家担保的兼容秩序,在 Unix 时代变成了由许可证、学术惯例与市场竞争三方博弈维持的动态秩序。兼容性这个词从 1964 年到 1980 年代的语义漂移,恰好对应着软件产业权力结构的两次转移:先从硬件厂商手里转到操作系统手中,再从操作系统手中散落到整个源码共同体里。漂移并未就此停止——BSD 与 System V 的分立、校园与厂商的攻防、源码共同体与许可证体系的拉锯,全都发生在 1973 年那次重写铺就的源码轨道上。历史的进程从不签署感谢信,它只留下里程碑。


第 029 章 1985:虚拟内存、页表与保护模式的成熟

机器自己搬家的第一夜

1962 年,曼彻斯特大学。一台由汤姆·基尔本(Tom Kilburn)团队与费兰蒂公司联合打造的机器——阿特拉斯(Atlas)——投入运行。同期美国的 LARC 与 Stretch 是它的对照工程;后世把它列为最早超级计算机的有力候选之一。它在当时已经足够惊人:支持多道程序设计,装着当时最接近现代形态的操作系统“Atlas 监管程序”(Atlas Supervisor)——调度、换页、外设协调,第一次有了统一的承办机构;“操作系统”这个词从此不再是论文里的概念,而是一台机器里一份看得见的职责清单。但它真正的革命藏在地址总线上:阿特拉斯第一次区分了“地址”与“存储位置”这两个被计算机界混用多年的概念——程序声称自己要访问一个地址,机器却有权把这个地址安排到任何一块真实的存储位置上。磁芯主存不够用,磁鼓来凑:一套硬件自动把处理器生成的每个地址翻译到当前的真实位置,把暂时没人用的数据块挪去磁鼓,把即将被访问的数据块提前搬回磁芯。首台阿特拉斯安置在曼彻斯特大学,费兰蒂与大学共同使用,随后伦敦大学与英国石油公司联合购入一套,原子能研究机构再购入一套——三家机构轮流排队的时代,一台机器的空闲就是真金白银的流失。这次成功还带来了一个组织上的结果:基尔本在 1964 年创建了英国第一个计算机科学系——一台机器催生了一个学科建制。这套机制被它的设计者称为“一级存储系统”——在程序眼里只有一层连续的存储,背后却是两级介质在自动倒手。项目的动机写在时代的骨头里:那时的计算机贵到不容许闲置,阿特拉斯隶属的多道程序计划,目标就是让昂贵的机器昼夜满负荷运转,让多个程序在内存里排队共存——机器过于昂贵,人类必须退位,卷三的全部故事都从这一句话里生长。曼彻斯特的这台机器每天运转二十个小时,先后跑过上万个程序,使用费按每小时五百英镑向客户收取,收入的一部分回流大学的计算机基金——昂贵的机器与昂贵的制度,在 1962 年就是一对共生的组合。这台首机一直运行到 1971 年 11 月底才关闭;后续最大的一套装机卖给了英国原子能研究机构,配了四万八千字、字长四十八位的磁芯内存与三十二台磁带机。费兰蒂后来推出的缩水版阿特拉斯 2 打算走商业市场,却遭遇了商业失败——技术领先与商业成功之间的时差,在这台机器身上提前上演了一次。

自动化的构想此前已有零星的理论火种——1950 年代一位德国物理学家就描述过类似的一级存储设想——但把它变成可运行机制的是阿特拉斯。要掂量这项发明的重量,得先看它之前的程序员过着什么日子:那个年代的主存通常是磁芯,二级存储通常是磁鼓,处理器只能直接寻址主存;程序员的大量日常工作,是亲手把程序切成块、规划块在两级存储之间的搬运时序,这些块被称为段或页,搬运动作被称为覆盖或交换——内存管理是一门要占掉工程师半张图纸的手艺。阿特拉斯为这项制度写下了三条奠基性发明:硬件地址翻译、按需调页(程序访问到不在主存的页时,由翻译硬件触发中断,把缺失的页调入主存)、页置换算法(找出最没用的页挪回二级存储)。这三件事在 1962 年组合在一起,构成了虚拟存储的完整原型——此后六十年的每一代处理器、每一个操作系统,所做的都只是把这三件事做得更快、更大、更隐形。1985 年,这条演化线等来了它在个人计算机世界的里程碑:英特尔 80386 处理器发布,二十七万五千颗晶体管、十六兆赫兹的主频,第一次把三十二位保护模式与硬件分页装进了 x86——四吉字节的平面地址空间、两级页表、按需调页,阿特拉斯在二十三年前构想的那套制度,从此进入了每一台桌面电脑。

页表:一份由硬件逐条核对的户口簿

虚拟存储的全部魔法,浓缩在一张表里。程序发出的每个地址都是虚拟地址,处理器要拿它去查一张页表——这张表记录着每个虚拟页落在哪个物理页框、是否在内存、是否可写、由哪个进程所有。查表这个动作每条访存指令都要做一次,慢了就是全系统的灾难,所以查表本身必须由硬件完成。80386 的方案是两级页表:虚拟地址被切成三段,高两段索引页目录、中段索引页表,末段是页内偏移——一次完整的翻译走起来像一场三级对接:先查页目录拿到页表的位置,再查页表拿到页框的位置,最后拼上偏移走进真实数据;每个页四千字节,一个页目录加一张页表就能描绘四吉字节的完整地址空间——两级结构本身还是一次空间上的取舍:如果用单级全量表,每个进程都要预付一块巨大的连续表空间,哪怕它只用了地址空间的零头;分级则允许“没用到的那部分地址空间,连页表都不必存在”。页的粒度同样是权衡的产物:页太大,一个一千字节的文件也要占满一整页,剩下的三千字节沦为内部碎片;页太小,页表与翻译的开销又不成比例。四千字节落在了这对矛盾的中点上,此后几十年成为 x86 世界的默认页长。

查表的代价靠一只小小的缓存来摊平。页表自己也是内存里的数据,也要占地址、也要被缓存——查表的第一个玄机因此带着递归的味道:找页表之前,得先知道页表放在哪。硬件的解法是拿一枚专门的寄存器,永远记着页表顶层的物理位置。页表常驻内存,而内存访问本身就是一条耗时上百周期的路——如果每条指令都要为翻译地址先跑一趟内存,性能会塌方。设计者于是把最近用过的地址翻译结果放进一块专用的相联存储器,称快表(TLB):命中时翻译近乎零开销,未命中才走页表的慢路。程序的局部性——这条在第 017 章已经统治过存储层次的原则——在这里再次显灵:绝大多数访存都在快表里命中,硬件户口簿只在极少数时刻被真正翻开。快表未命中要查页表,页表项显示目标页不在内存时,处理器抛出缺页中断:正在执行的指令被挂起,操作系统接管,从磁盘把缺失的页调入主存,找到空闲页框或按置换算法选一个“最没用”的页逐出,更新页表与快表,然后重新执行那条指令——整个过程对程序完全隐形,程序只是感觉到“这次访问慢了一点”。缺页有两类:一类是善意的按需调页——程序第一次访问某页,页根本还没装进来;另一类是恶意的非法访问——地址越界或写只读页,此时操作系统的响应不再是调页,而是终止进程。同一种中断,两种裁决,保护与虚拟在此合流。

快表也有一笔藏在切换里的暗账。它的全部前提是“刚才那个进程刚刚用过这些翻译”,而进程切换意味着地址空间整体更换——快表里满是与新进程无关的旧翻译,要么整体作废重填,要么在表项里贴上进程标签加以区分。切换越频繁,快表越冷,命中率的损失越大;多核时代每个核心各配一份快表,标签与作废的策略进一步复杂。工程界的应对是把页做大——同样的覆盖范围,页越大,需要的表项越少,快表越容易焐热;以及给表项打上地址空间编号,让新旧进程的翻译在同一张快表里和平共处。每一项补救都是一次微调,每一次微调都在提醒:虚拟地址到物理地址的翻译,是处理器每一条访存指令都要过的关卡,这条关卡上省下的每一个周期,都乘以整个系统的指令流量。所以处理器的每一代都在给这道关卡加宽——更大的快表、更细的分级、更聪明的预取;内存墙的另一侧,站着的正是翻译延迟这个沉默的收税人。

保护模式:程序之间的相互猜忌

分页解决的是“内存不够”,保护模式解决的是“内存不可信”。多道程序时代的根本困境是:若干个互不信任的程序共享同一物理内存,任何一个失控的写操作都可能碾碎别人的数据。保护模式给出的方案是一整套硬件化的围墙体系:每个进程有自己的地址空间,页表项里写着访问权限,特权级把代码分成内外圈——内核住在最高特权级,应用程序的每一次越界访问都在地址翻译阶段被硬件当场拦截,抛出异常交由内核处置。这道围墙的验收方式也别具一格:每一次把系统移植到新硬件,工程师都要故意写出越界访问的代码,验证处理器会当场拦截——隔离机制的合格证书,是靠处决一批“示众程序”换来的。崩溃隔离由此成为硬件行为:一个进程的死循环、野指针、内存越界,最多烧掉它自己的地址空间,邻居毫发无损。阿特拉斯的发明者们在 1962 年解决了“地址可以映射到别处”;八十年代的微处理器设计师们把同一思想推到尽头——地址不但可以映射到别处,还可以在映射表上声明“此处禁止你触碰”,而执行裁决的仲裁者是硅片,不是任何一段可以被绕过的内核代码。80386 的保护模式还留了一扇通向过去的门:处理器同时支持多种运行模式——既有完整保护能力的新模式,也保留了让既有软件继续运行的兼容路径,甚至可以让旧程序成组地在受控环境中并存。切换到保护模式并非通电即得:软件必须先装载全局描述符表、设置保护使能位,相当于亲手替硬件围墙完成一次开门仪式——围墙是硅浇的,门钥匙仍握在内核手里。为什么保护模式等到 1985 年才抵达桌面?因为在那之前,桌面机器本来就是单用户单任务的世界,隔离无从谈起;图形界面与多程序的日常化让需求先一步到位,芯片的能力随后赶到——需求与能力的双向奔赴,在产业史上从来都以年为单位对表。1985 年之后,多任务操作系统的“程序互不践踏”从一种编程纪律,变成了一条物理定律。四十年后回看,这颗二十七万五千晶体管的芯片被评价为永远改变了个人计算——它改变的方式并不喧哗:不是让机器变快了多少,而是让机器第一次可以在桌面尺寸里安全地同时做几件事。普通用户第一次体会到这套定律,往往是通过一个朴素的操作:某个程序卡死了,点击“结束任务”,系统关掉它,其余一切照常——这个按钮的全部底气来自硬件隔离;在它出现之前,任何一个程序的死循环都意味着整机重启,重启之前还要对着满屏乱码发一会儿呆。对个人计算机产业而言,这一年的意义要再过几年才完全显形:当三十二位保护模式与硬件分页出现在桌面处理器上,图形化的多任务操作系统有了它等待已久的硬件地基——1990 年代桌面系统的全部内存魔法,都跑在 80386 划定的规则之内。

万倍裂谷:虚拟存储真正的对手

要理解这套机制的分量,得回到卷三的主导约束:处理器以纳秒为单位工作,机械存储以毫秒为单位响应——内存访问一百纳秒上下,磁盘访问以毫秒起步,两者相差五到六个数量级,中间横着一道万倍量级的时延裂谷,而程序的胃口远大于任何主存的容量。虚拟存储的真正对手,正是这道裂谷:它把“程序需要比主存更多的内存”这个死结,转化成“把不活跃的数据沉到慢介质、把活跃的数据留在快介质”的调度问题——换言之,存储层次的金字塔在此多了一层由操作系统亲自管理的夹层,程序的地址空间可以无限大,代价是缺页时跨越裂谷的一次毫秒级跋涉。这套机制能立住,靠的仍然是局部性:程序在一段时间内只碰得到地址空间的一小块,绝大多数页常年无人问津。阿特拉斯的置换算法要找的“最没用的页”,四十年后依然是每一个操作系统内核里反复打磨的算法——只是它背后押上的赌注越来越大:赌赢一次毫无感觉,赌输一次就是一次毫秒级的跋涉,赌输一片就是用户眼里的卡顿。这套机制在工程上几乎是一场豪赌的常态化:系统默认程序大概率用不到全部内存,于是放心地把有限的物理内存超额分派给多个程序;程序员也因此在申请内存时多了一分底气——敢要,因为冷页可以被牺牲;赌局平时稳赢,因为局部性在替系统扛单;一旦一批程序同时触碰各自的冷页,磁盘队列排起长队,系统便集体坠入颠簸。超额承诺、局部性偿还——金融业与虚拟存储在结构上惊人地同构,只是这里的挤兑以毫秒计价。

x86 的路径在这里还有一段自己的弯路。英特尔的 32 位保护模式同时装备了分段与分页两套机制——段是更老的抽象,页是更年轻的抽象,80386 时代两者叠用,软件要先过段翻译再过页翻译。随着三十二位操作系统普及,平面内存模型逐渐胜出,段被架空成一个几乎透明的形式,分页成为事实上的主角——到 1990 年代末,显式使用分段寻址的做法几乎被淘汰。段与页的分别值得多说两句:段是变长的、带语义的——代码一段、数据一段,边界随程序结构而动;页是定长的、无语义的——四千字节一切,不管里面装的是什么。段的抽象更贴合程序员的意图,页的抽象更贴合硬件的管理:变长的段让内存分配变成一件容易产生碎片的麻烦事,定长的页把分配简化成了查表。抽象设计的又一次经典对决——贴近意图输给了贴合机器。这场内部清理的启示与本书反复出现的主题一致:两套为同一问题发明的机制共存时,更简单、更可预测的那一套终将胜出。

一项制度的三次落笔

从 1962 到 1985,虚拟存储走了二十三年,落笔三次。第一次落笔在曼彻斯特:三项发明在大型机上验证了可行性,同期的高端机器纷纷跟进,虚拟存储成为大型机的身份标志。第二次落笔在小型机与工作站:硬件成本的下降让地址翻译单元不再是旗舰机型的专属,工程工作站与中型系统开始把分页当作标准配置,操作系统的研究者终于人人买得起一间实验室来打磨置换算法。第三次落笔就是 80386:三十二位的桌面处理器把整套制度塞进一颗芯片,个人计算机从此与大型机共享同一套内存哲学。第三次落笔能成,靠的也不只是芯片设计——桌面机器的出货量把翻译单元的研发成本摊到了千万台设备上,规模本身成了制度普及的最后一票。每一次落笔都伴随同样一轮怀疑——翻译太慢、表太大、缺页太贵——也伴随同样的验证:只要程序的局部性成立,机制的收入永远大于支出。制度的成熟从来是一遍遍重写同一份可行性报告,直到硬件成本的曲线把怀疑者全部说服。

这场成熟还有一层常被忽略的组织意义:此前的存储管理散落在每个程序的源代码里,覆盖与交换是手艺;此后它集中到操作系统与硬件的交界处,成为一项公共设施。手艺变成设施的过程,就是第 017 章存储层次逻辑在时间维度上的重演——程序曾经亲手搬数据,后来机器接管了搬运;程序曾经亲手搬内存块,后来硬件接管了翻译。每一次接管都伴随着同一个抱怨(机器做得不如人细)与同一个结果(机器做得比人稳)。

反事实短栏:如果没有硬件级虚拟内存

**推演纪律。**本栏只挪动一个变量:硬件级地址翻译(MMU)的存在性——假设 1962 年至今所有处理器都不内置虚拟内存支持;多任务、多用户与保护需求一律按史实保留。

设想一条从未出现 MMU 的世界线——地址翻译、页表、缺页中断从未被做进硬件,多任务操作系统还需要崩溃隔离吗?需要,而且每一条替代路径都代价惊人。

第一条路是语言静态验证:让编译器在运行之前证明程序绝不会越界——所有内存访问都通过带边界的抽象层,指针彻底消失,类型系统承担硬件本该承担的拦截职责。这条路线在逻辑上可行,后世以类型安全著称的语言也确实证明了它;但在 1970 年代的机器上,它的代价是运行时的每一次访问都附带检查开销,编译期则需要一个今天才能勉强兑现的证明体系。更重要的是它改变的不是性能而是生态:所有语言、所有编译器、所有运行库必须全体达标——任何一门不达标的语言写出的程序,都能碾碎整个系统。把系统安全寄托在全体程序员的自觉与全体编译器的严谨上,等于把城市的消防寄托在每个市民不玩火上。这条路线也并非全无后裔——安全攸关的领域后来确实发展出以静态验证替代部分运行时隔离的做法,代价是苛刻的书写规则与漫长的证明流程;它们的存在恰恰反证了硬件路线的主流地位:愿意为静态证明买单的,从来只有出不起事故的行业。

第二条路是软件沙盒:用解释器或校验机制把每个程序关进软件围栏——字节码先经校验再执行,内存访问被翻译成带检查的间接跳转。它能隔离,但隔离的成本落在每一次访存上:同样一条指令,围栏内要多执行三五条检查指令,解释执行的围栏税更以倍数计——隔离税单从不打折,只按访问次数累计。整个系统的吞吐被隔离税层层抽走,而税收换来的是一种永远无法完全证明的安全——软件围栏的每一行代码自身也可能有缺陷,看门人自己需要看门人。没有硬件的裁决,隔离就从“物理定律”退化为“更小心的软件”,而更小心的软件依然是软件。

第三条路最接近当年的现实:放弃隔离,改用协作。没有 MMU 的微控制器上,多任务只能靠各任务自觉让出处理器——任何一处死循环、任何一个野指针,全机殉葬。这不是假设:正是这类约束,把无 MMU 嵌入式世界的程序逼成了静态优先级、扫描循环、禁止动态分配的样式——实时世界用纪律弥补了硬件缺席的围墙,代价是编程的自由被压缩到极致,通用软件那种“崩溃了重启就好”的试错文化根本无从生长。四条推演共同的教训只有一句:隔离的成本取决于隔离的位置——越靠近硬件越便宜,越靠近软件越昂贵。这条先后次序,后来成了体系结构设计反复引用的第一性直觉。这条世界线并没有消失在历史里——今天大量低端微控制器依然不带地址翻译单元,依然跑着协作调度、静态分配的实时系统;它们就是那条没有 MMU 的世界线派驻现实的活化石,替所有主流系统时刻提醒着硬件隔离的真实身价。还有第四条混合路线——用校验过的字节码加解释执行来做隔离,语言自带围栏。它在特定场景确实成功过:解释型语言的程序天生跑在软件围栏里,彼此之间互不践踏。但所有此类方案背负同一笔账:隔离税按次征收,性能以十倍计折损,而且围栏只对同一种语言有效——任意语言、任意二进制的通用生态,在软件围栏的世界里从未成立过。三个方向推演到底,结论指向同一处:没有硬件级虚拟内存,崩溃隔离要么贵得没人用得起,要么严得没人敢编程,要么脆得一碰即溃。硬件 MMU 的历史功绩,在于它把隔离的成本一次性浇筑进硅片,此后每一次访存的保护都近乎免费——多任务操作系统的一切繁荣,都建在这笔一次性基建之上。

三条世界线的推演到此收束。回到现实:1962 年阿特拉斯的三项发明、1985 年 80386 的一次集成,中间二十三年的每一次改进——更细的页表、更快的快表、更聪明的置换——都在反复确认同一个事实:这道围墙必须由硬件看守,因为只有硅片的裁决才快到让每一个访存周期都付得起隔离的价钱。

账单与定性

这套机制的账单同样真实。页表本身要占内存,多级结构以空间换灵活;快表容量有限,进程每次切换都要清空重填,切换频繁的系统里,快表冷启动的损失随核数攀升;缺页中断的每一次跋涉都要跨越万倍裂谷,内存超额认购的系统在尖峰时刻会集体坠入颠簸——页在磁盘与主存之间来回搬运,处理器在原地等待,所有人都在付钱,没有人干活的时刻,是虚拟存储最深的暗面。也正因为这种不确定性,实时世界对分页始终敬而远之——刹车与点火控制器宁可把代码锁进固定内存,也不接受一次无法预测的缺页;虚拟存储与确定性,至今仍是存储设计里的一对宿敌。工程师们为这些代价持续补票:更大更快的快表、更大的页、更精的置换算法、更多级的页表——内核开发者把职业生涯里相当一部分夜晚花在缺页路径的每一个分支上,而应用程序员对这一切毫无感知;同一套机制的复杂度在两头分布得如此悬殊,恰是抽象分层最成功的一次表演。表演的另一面是手艺的代谢:覆盖与交换的手艺随着手工内存管理一同失传,新的手艺在废墟上生长——读懂页表、诊断缺页风暴、给颠簸的系统做调优,成了操作系统工程师的新基本功。每一次抽象换代都遵守同一份合同:旧手艺作废,新手艺上岗,而合同永远只通知一半人。英特尔的分页结构此后从两级长到五级,每一级的添加都在同一个问题上打转:如何在地址空间的疆域扩张与翻译的时间成本之间重新画线。每一代处理器里,地址翻译单元占下的硅面积与功耗逐年攀升——这是一笔为看不见的秩序支付的常设硅税,纳税人浑然不觉,收据写在每一次内存访问的延迟里。

但收益的一侧早已写进每个人的日常。崩溃隔离让应用开发者敢于冒险——写坏一段代码,崩掉的是自己的进程,而不是整台机器;多任务让机器在等待磁盘的毫秒里转去执行别人的计算——万倍裂谷的每一毫秒都不再必然被浪费;内存超额承诺让单机同时服务远超物理容量的工作集——这条从阿特拉斯出发的路线,如今延伸到每一台服务器、每一部手机:每一次进程启动的背后都是一次页表构建,每一次内存访问的身后都站着一次地址翻译;在今天的高端芯片上,地址翻译单元占下的硅面积已足以与计算单元平起平坐——看门人的编制,扩张到了与劳动者相当的规模。而它交付的方式始终如一:全部机制对程序隐形,程序只看见自己独占一台干净机器的假象。卷三的核心矛盾——“如何依靠脆弱的硬件机制,在相互猜忌的程序之间建立独占全机与不可侵犯的虚拟假象”——在 1985 年之后有了工程意义上的标准答案:假象由页表绘制,边界由硅片看守,例外由中断裁决,代价由局部性偿还。它与另一个假象——“每个程序独占一颗处理器”——并列为操作系统时代的两大底层幻术:一个用时间片伪造独占的处理器,一个用页表伪造独占的内存;两者都靠硬件强制兑现,也都在硬件失效的那一刻露出原形。

回到本卷的主导约束:纳秒级的处理器与毫秒级的机械存储之间横着万倍裂谷,而虚拟存储是横跨这道裂谷的第一座桥。桥的设计从 1962 年阿特拉斯的三项发明起步,到 1985 年 80386 把它装进每一台桌面电脑,中间隔着二十三年的材料进步与算法打磨;桥上此后跑过的每一次缺页中断,都是程序与物理介质之间一次被精确计费的越境。虚拟内存从被发明的那天起就带着一种奇特的气质——它明明白白地欺骗程序,却让所有程序因此活得更安全;这套假象的维护者从不寻求被看见,它只要求在最坏的时刻依然准时。程序以为的那块内存是假的,程序为它付出的等待与电费是真的——假象经济学在虚拟存储上完成了它在计算史里最优雅的一次落地。


第 030 章 A-0、编译器与机器无关的宏伟蓝图

1952 年,宾夕法尼亚,埃克特-莫克利公司的机房里,葛丽丝·霍珀(Grace Hopper)把写满符号代码的磁带装进 UNIVAC,键入一串调用号,然后退后一步。机器自己转了起来:它顺着调用号在磁带上检索出预存的子程序,逐段调进内存,拼接、装配,吐出一串可以直接执行的机器码。整个过程里,人的手没有碰过任何一条机器指令——在 1952 年,这句话听起来的震撼不亚于今天说“机器自己写了一篇稿子”。在旁观者眼里,这台计算机正在做一件此前只属于人类的事——写程序。霍珀为这台机器写的这套系统叫 A-0,动笔于 1951 年,完成于 1952 年,是电子计算机上最早的编译器类工具。此后几十年,人类把越来越多的“告诉机器做什么”的工作交还给机器自己:程序员的输入从二进制到助记符,从助记符到公式与句子,每一层抽象的下面,都站着一个把上层语言翻译下去的编译器。本章讲的就是这个翻译层的出生证明——以及它出生时,遭遇的那场至今余音未消的效率审判。而 1952 年这一天,那个翻译层只有雏形大小——它更像一个搬运工:磁带上躺着一排排手工调好的子程序,A-0 负责按号取件、拼装成完整程序。搬运工虽小,方向已定:让机器替人做翻译。本卷的核心矛盾是机器的纳秒与人的分钟之间那道万倍时延裂谷,而编译器是第一件专门为填这道裂谷发明的工具——它填的方向与所有硬件不同:不去加速机器,而是削减人要说的句子。

一天几周:机器贵,人更贵的年代

要理解这个方向为什么在 1952 年是大逆不道的,得先算清当时的编程账。50 年代初,世界上会写程序的人屈指可数,几乎清一色是数学家与物理学家——门槛不在数学的高雅,在于机器码的门只对懂抽象符号的人敞开。绝大多数科学家用机器码或汇编写程序:一个数学公式,必须亲手分解成一串机器专用指令,寄存器怎么分配、内存地址怎么编排,全要逐条显式安排。这项工作要求的不只是数学,还有对具体机器的每一处怪癖的了如指掌——同样是求一个正弦值,在这台机器上和在那台机器上,写法可以毫无相似之处。程序一旦写完,执行速度无可挑剔——它本就是为这台机器手工量裁的;但写完它可能要花几个星期。也就是说,在“计算”这件商品的总成本里,机器执行只占几分钟的价钱,人的准备却占去几周。

更麻烦的是,这笔成本的结构正在悄悄翻转。五十年代初,机器时间贵得吓人,程序员的时间相对便宜,用人的几周换机器的几分钟,账还划算。可计算机一年比一年快,机器执行同一道题的时间不断被压短,准备程序的几周却纹丝不动——于是人的时间在总账本里的占比逐年膨胀。到五十年代中期,任何一个认真记账的管理层都能看出趋势:编程正在成为计算产业里最贵的环节,而它用的还是最原始的手工方式。更急迫的是需求端的爆炸:机器越便宜、装得越多,想用机器的人就越多,会写程序的人却培养不出那么多——供需的剪刀差以年为单位撕开,剪刀的一侧是排队的任务,另一侧是屈指可数的手。这不是一个技术问题,是一个经济学问题;而经济学问题的解决方案,从来不是“更努力地手工优化”,是换一种生产方式。账本的两端还各自嵌着物理的刻度:机器时间按秒计费,一秒就是一秒的租金;人的时间按周计费,一周里大半耗在查阅手册、核对地址与追查抄错的数字上。把人的周折成机器的秒,编程的成本曲线陡得吓人——而曲线越陡,把它削平的诱惑就越大。

“自动编程”这个词,在 1952 年前后的产业语境里听起来近乎玄学——机器读人的话、替人写程序,这与当时一切关于计算机的常识相反。第一批尝试换生产方式的人,几乎都被同一堵墙撞了回来。给机器配一套“更好写的语言”有两条技术路线:要么解释执行——写一个常驻机器的翻译官,逐句读入、当场执行;要么编译执行——先让机器把整个程序翻译成机器码,再一次性运行。解释路线的代表是巴克斯在 IBM 701 上做的 Speedcoding:它提供了便利的操作,连浮点算术都能一条指令搞定,程序员写得舒坦——代价是解释执行把速度砍得一塌糊涂。这里的技术分野值得掰开:解释执行是“翻译官随行”,每一句都在运行现场现翻现用,翻译成本摊进每一次运行;编译执行是“提前出成书”,翻一遍印出来,此后每次运行只走机器码的快道。两种路线的取舍,本质是翻译成本与运行频率的博弈:跑一次的程序,解释无妨;天天要跑的表格,编译才有意义。Speedcoding 的价值在于它是验伤的探针:市场用它的命运给出裁决——科学家欢迎好写的记法,但拒绝为可读性支付巨大的性能损失。解释路线堵死,只剩编译路线:把翻译成本从“每次运行”挪到“一次翻译”,可这条路的门槛高得多——机器必须先长出一个足够聪明的翻译器,而五十年代初没人知道这个东西该长什么样。

减法的发明:A-0 与 FLOW-MATIC

第一个把编译器造出来的人,起点是一名被派去操作机器的数学教师——这个身份错位贯穿了她的整个生涯:在工程师眼里她是数学家,在数学家眼里她是程序员,在海军里她是军官,在每个行当里她都是那个把另一行的知识带进来的人。霍珀在瓦萨学院教数学,1943 年加入海军的紧急志愿服役计划,被派到哈佛克拉夫特实验室,加入了霍华德·艾肯的 Mark I 团队——她是这台美国第一台大型自动数字计算机的第三个使用者。她为 Mark I 写过一本五百页的操作手册,此后又为 Mark II 与 Mark III 编程;1949 年,她离开哈佛,加入埃克特-莫克利公司,那家公司正在造第一台为商业用途建造的计算机 UNIVAC——用磁带而不是穿孔卡输入和存储数据。公司交给她的任务说起来平平无奇:想办法让程序员把“要机器做的事”翻译成机器听得懂的话,翻得省力一点。这句任务书里没有“发明编译器”四个字——编译器这个概念当时还不存在,它是霍珀在执行任务的过程中替人类发明的词。

A-0 就是这笔任务的第一笔产出。它的机制朴素到近乎寒酸:霍珀把一批经过测试、手工调优的子程序存在磁带上,每个子程序登记一个调用号;程序员写主逻辑时,只需用符号化的数学代码写下运算步骤,再在需要的地方填入调用号——A-0 读入这些符号,按号到磁带上取来对应子程序,拼装成一个完整的机器码程序。磁带在这里扮演的角色值得记一笔:它是那个年代能把“程序库”物理化的少数介质——成百段调好的子程序按目录存在一盘盘磁带上,要用哪段,机器自己卷带寻找。穿孔卡的年代,程序库意味着一堆卡片箱;磁带的年代,程序库第一次有了“检索”的形态。用今天的眼光看,A-0 更像一个带程序库的加载器加链接器,离“翻译任意语句”还有十万八千里;但它的方向性无可辩驳:机器第一次参与了自己程序的装配,人的劳动第一次从“逐条写出机器码”降格为“逐段点菜”;效率的来源也随之改变——子程序是熟手写的,一次写好、千处复用,程序的质量第一次与人数脱钩。1952 年,这套系统完成。

随后几年,霍珀把这套思路往两个方向推进:一版版新的编译器工具(B-0 等)逐步把“符号代码”升级为更像英语的表述;到 1955 年前后动工的 FLOW-MATIC,程序里已经可以直接写接近商务英语的指令。她的目标场景是商业——自动开账单、算工资——这与她一贯的信念一脉相承:简化编程,才能让对计算的兴趣走出数学家与计算机科学家的圈子,扩展到普通的会计、职员与管理者。为此她推动的每一步都朝着同一个方向:让程序里的字越来越像人话,让机器承担越来越多的翻译工作。机器写程序,在她看来从来都不是对程序员的冒犯,而是对“程序员必须是天才”这条潜规则的冒犯。这条信念让她成了当时计算机产业里最不合群的声音——主流工程界关心的是如何让程序更快,她关心的是如何让更多的人写得出程序;主流讨论的效率以百分比计,她讨论的门槛以人数计。两个量纲在 1952 年还没有交汇点,要到个人计算机时代,人们才会看清哪一边才是产业真正的主轴。FLOW-MATIC 后来成为五十年代末 COBOL 语言的直接基础——一门让商业组织用自己的词汇写程序的语言。值得把两条线并排放在这里:FORTRAN 的服务对象是科学家,要的是公式与速度;霍珀这条线服务的是账房,要的是文件、记录与组织自己的日常词汇。两者在 1957 年前后殊途同归地证明同一件事:语言可以面向一类问题去设计,而不必面向一台机器去设计——机器无关这个今天听来天经地义的属性,在当年是两拨人分别用两条产品线验证出来的。霍珀在 UNIVAC 上推进这一切时,听到的冷嘲远多于喝彩。她晚年多次回忆当年的处境:没有人相信她有一台真的能运行的编译器,也没有人愿意碰它——人们告诉她,计算机只会做算术,不会写程序。这句反问在当时的工程共识里是有分量的:翻译本身不就是比算术复杂得多的智力活动吗?如果机器能翻译,那还需要程序员干什么?反对者没有意识到,他们用来反驳的这个问题,恰恰就是答案。

一场豪赌:FORTRAN 与它的赌注

编译器的另一半历史在纽约州波基普西写就,执笔的是一位以懒散著称的天才。约翰·巴克斯(John Backus)在 IBM 的第一个大项目是给巨型计算机器 Selective Sequence Electronic Calculator 写程序算月球位置——这份差事他干得并不快乐:逐条手写机器码的编程方式既痛苦又低效,他后来坦言,自己起初就是因为它难才不肯认真学,直到被逼着做了两年,才确信一定存在更好的办法。这个动机在 FORTRAN 的史述里常被一笔带过,它却是最诚实的版本:改变编程方式的第一推动力,有时不是远见,而是一个聪明人对笨工作的忍受到了头。他先交出的答案是 Speedcoding,被市场判了缓刑;到 1953 年底,他把学到的一切写进了一份提案:为 IBM 的新机器 704 开发一套公式翻译系统——让科学家用接近数学的记号写公式,由一个程序把它翻译成机器码。系统的名字把这份任务书写成了缩写:FORmula TRANslation,FORTRAN;一个本该枯燥的产品代号,日后成了延续至今、仍在超级计算机上运行的最古老的编程语言的名字。新机器 704 恰好提供了硬件浮点运算与变址寄存器,这给了翻译系统用武之地;但这两样东西要用出效率来,需要相当精巧的代码组织,也正是这一点,让整个提案的成败押在了一个当时无人能做到的能力上:编译器生成的代码,必须快到与手写汇编分庭抗礼。

IBM 为此组了一支阵容均衡的队伍。哈伦·赫里克、欧文·齐勒、彼得·谢里丹、罗伊·纳特、罗伯特·纳尔逊、洛伊斯·海布特,以及理查德·戈德堡、谢尔登·贝斯特、大卫·塞尔等人先后加入,分工覆盖语法定义、代码分析、优化与测试——在 1954 年,为“写一个写程序的工具”专门组一个十余人的跨职能团队,本身就是革命性的组织决定;此前的“软件”是程序员的副业,从此它第一次有了自己的工种、自己的团队与自己的工期。语言设计沿最实用的路线推进:算术表达式可以直接按数学习惯书写,循环与分支覆盖数值计算的控制流;早期形态里硬件与穿孔卡的痕迹处处可见——代码必须从卡片的规定列开始写,语句标号是纯数字,转移指令就叫 GO TO。这些今天看来莫名其妙的规定,每一项都是时代的一枚化石:固定列是穿孔卡机器的读卡惯例,数字标号迁就的是早期编译器有限的符号处理能力;语言永远带着它出生那天的介质印记,这条定律直到今天仍然成立。但这些都只是表皮。真正的赌注压在编译器身上:它要分析表达式之间的依赖关系,规划寄存器的分配,消减重复运算,让产出的机器码与老练汇编工匠的手工产物掰手腕。项目组给自己定的验收标准毫不掩饰——这个目标从来就不只是“能出正确结果”,而是“出足够快的结果,快到让所有想回汇编的人打消念头”。

1957 年,第一个 FORTRAN 编译器交付,产出的代码效率超过了许多用户的预期,编程时间成倍下降,FORTRAN 随 IBM 的机器铺向整个科学计算界——扩散的载体正是机器本身:制造商把编译器当作随机附带的标准软件交付,买 704 就送 FORTRAN,科学家开箱即用,无须自装。软件随硬件捆扎销售的商业模式,在这里第一次跑通;它既加速了语言的普及,也埋下了日后各厂商方言林立的伏笔——每一家都顺手改一点自己的方便。为什么这件事偏偏发生在 1957 年、发生在 704 上?硬件的成熟是隐形的配套:704 自带的硬件浮点让编译器不必再用一长串定点指令模拟小数,变址寄存器让数组寻址有了规整的硬件抓手——翻译器面对的目标语言越规整,自动翻译的规则就越容易写成有限条数的算法。编译器的成熟与机器的规整,是一对互相成全的条件;没有后者的硬件红利,前者的软件豪赌无从下注。这场胜利的含金量要放回当时的语境里称量:在 1957 年,把优化决策托付给一个软件,是货真价实的赌博——此前没有任何自动系统达到过那个高度。FORTRAN 证明了一件此前只是猜想的事:在大型程序上,编译器能比人更一致地完成机械性优化工作。软件经济学从此改写:计算机不再只负责执行最终的计算,它开始参与制造程序本身。此后谱系扩张的一切——1958 年的 FORTRAN II 支持子程序独立编译、1962 年的 FORTRAN IV 理顺语言、1966 年的第一个美国国家标准——都是这场初胜的余波。独立编译一条尤其值得驻足:子程序可以单独翻译、分开存放、用时链接,意味着大程序可以由多人分头编写、各自的错误各自隔离——现代软件工程“模块化”的地基,就这样从编译器的一项技术特性里长了出来。

机械骨架:机器如何替人写程序

把 1952 年与 1957 年的两台翻译机器拆开对照,能看到编译器从“搬运工”长成“工匠”的完整轨迹:

      A-0(1952,UNIVAC)                 FORTRAN 编译器(1957,IBM 704)  
   程序员书写:                        程序员书写:  
   符号数学代码+调用号          →      接近数学的公式/循环/分支  
        │                                  │  
        ▼                                  ▼  
   按调用号检索磁带库                词法/语法分析 → 中间表示  
   (子程序为手工预调优单元)          依赖分析 → 寄存器分配  
        │                            消除重复运算 → 代码生成  
        ▼                                  │  
   拼接输出完整机器码                       ▼  
   (人:点菜;机器:装订)             机器码(机器:自己掌勺)  
   每次新运算需人工预制子程序          新公式无需任何人工预制件。从调用号到表达式,谱系上每一代编译器都在扩容,但工作定义始终未变:读入一种语言,输出另一种语言,并保证两种语言说的是同一件事——这条“语义相等”的保证,是整个翻译事业的信用本位。  

A-0 的局限一目了然:它能装配的每一个构件,都必须先由人手工写好、调优、编上号。它的贡献是把“程序=子程序库+少量主逻辑”的分工立了起来。FORTRAN 的跨越在于去掉“预制”二字——任何新公式、任何新的循环组合,编译器都能现场生成目标代码,这正是“自动编程”承诺的兑现。而这条编译流水线的核心工序,用今天的语言复述,就是一套逐级降维的翻译:先读懂符号,再验证结构,然后揣摩语义,最后落成指令。以 FORTRAN 团队最看重的优化为例,一个表达式的求值要过三道闸。而整条流水线的分层在 1957 年已初具雏形——先由一道工序把字符流切成符号与数字,再由一道工序把符号序列搭成语法结构,随后逐句核对语义、生成并优化目标指令;这三层职责此后将发展出各自的数学理论,成为下一章的主角,此处只需记下:把“读懂程序”拆成层层可验证的机械步骤,本身就是编译器对人类思维的一次重要示范——原来理解一门语言,可以不需要智能。

/* 优化决策示意(记法现代化) */  
源级:  X = (A+B)*(C+D) + (A+B)*E          /* 人写的公式       */  
识别:  令 T = A+B                          /* 公共子表达式探测 */  
       X = T*C + T*D + T*E                 /* 乘法从三次减到两次 */  
寄存器: T 保活于寄存器,避免两次访存        /* 分配决策         */  
输出:  LOAD/ADD/STORE 序列(机器码)         /* 704 专用指令     */  

在人手里,“A 加 B 算了两遍,存起来复用”是经验;在编译器里,它是一条可穷举的规则——而规则的好处是永不疲劳。Speedcoding 与 FORTRAN 两种路线的差异,同样可以用一张表钉死:

      路线对照        Speedcoding(1953)      FORTRAN(1957)  
      工作方式        解释执行(逐句翻译)       先编译后运行  
      便利性          高(浮点一条搞定)         高(数学式直书)  
      运行速度        大幅下降                 逼近手工汇编  
      每次运行成本    反复支付翻译税           一次翻译,终身免税  
      市场结局        无人采纳                 科学计算事实标准  

这张表是编译路线对解释路线的完胜宣言,也是此后七十年所有编译型语言引以为据的出生证明——尽管后来解释路线在另一个时代借着更快的硬件卷土重来,那是后话。编译器背后的经济学值得单独写进账本:翻译成本一次支付、执行收益无限次摊销,这是典型的固定资产投资模型——程序规模越大、运行次数越多,编译器的摊销优势就越悬殊。但五十年代的机器只有一台,翻译与执行要排队:把编译器装进内存、读入源码、吐出目标码,这一趟走下来,机器的秒表走过的却是真实的租金。批处理机房里的日常因此多了一道工序——程序员的编译作业与运行作业分开排队,编译的产出是一盘装着机器码的磁带,下一班才轮到它上机。CPU 以纳秒计的算力,被以分钟计的磁带读写与人工周转反复打断,这正是本卷要反复清算的那道万倍时延裂谷在编译场景里的第一次亮相:翻译这种高级智能活动,最终也要学会适应机器世界的排队纪律。这个模型还预言了行业的下一步:既然翻译是有价值的固定资产,那么让翻译器本身更聪明(更会优化)就成了产业级别的研发方向——从 1957 年起,“编译技术”成为一门独立的学问,输入是高级语言,输出是性能,中间的每一分聪明都直接折现。

效率的账单

清算这一章的账目,最要紧的是先替反对方把账算完,因为他们的每一笔都成立。其一,效率损失真实存在:五十年代的编译器确实产不出比肩顶级手工汇编的代码——FORTRAN 之前的所有尝试都证明了这个判断,FORTRAN 也只是“逼近”而非超越。汇编工匠的自信有实打实的手艺撑腰:把循环里不变的运算挪到循环外,让上一条指令的末步与下一条指令的起步在时间上咬合,把屈指可数的寄存器用到一空都不剩——这三招没有一招是编译器当年做得来的;人能看出“这两个表达式其实是一回事”,机器在当时看不出。对于那些一段代码要跑几个月、机器按小时计费的极端用户,任何一点性能损耗都是真金白银。其二,黑箱的成本真实存在:把优化决策交给编译器,意味着程序员从此看不到(也管不着)自己代码的最终形态——机器“觉得”该怎么排就怎么排;对习惯了逐条掌控指令的工匠,这不是便利,是失控。其三,可移植性承诺的兑现有漫长迟滞:所谓“机器无关”在五十年代是纸面理想——每台机器仍要有人为它从头写一个编译器,A-0 只属于 UNIVAC,FORTRAN 编译器只在 704 上跑得动;语言与语言之间、机器与机器之间,翻译层并不相通。其四,最隐秘的一笔:编译器自己也是程序,也要有人写、有人调——谁来为翻译器的错误负责?一只编译器的缺陷会静默地污染它翻译出的所有程序,而追查这种污染的难度远高于追查一个普通程序的缺陷。用一个程序去生产所有程序,等于把整个产业的正确性押在少数几个核心程序的正确性上——这门“造工具的工具”的手艺,从此成为软件世界的地基工序,地基一晃,楼上全晃。其五,错误的责任开始转移。程序错得越来越深——是公式错了、语言错了,还是编译器错了?手工时代程序员对每一比特负责,编译时代,一份错误的输出可能来自三层抽象中的任何一层,追责链条从此第一次变得模糊。

这些账单的付款人各不相同:汇编工匠为技能贬值买单,他们引以为傲的寄存器分配手艺被一条条规则写进了编译器——手艺没有消失,是从人脑里搬进了程序里,从业者要么升级去做编译器本身,要么退守到系统底层那些编译器暂时够不着的角落——这条退守路线至今仍在,凡有性能极限处,必有手工优化者的根据地;较真的科学家为性能黑箱买单,此后他们与机器之间永远隔着一层看不透的翻译;而最大的付款人是整个行业——它用几十年的性能损失垫付了“机器无关”这个理想的分期付款,直到优化技术终于追上、并最终远远越过手写水平,这笔月供才算结清。争议的退潮方式颇具意味:反对者并没有被说服,他们是被稀释的——当足够多的不写汇编的人用高级语言做出了足够的成果,汇编阵营的每一句“它不够快”都仍然正确,却已经不再重要;工程史上许多争论的终结,靠的从来不是一方认输;当另一方的胜利变得无关紧要,争论自然会散场。反过来看,收益同样惊人:FORTRAN 的第一个编译器用一次胜利把“软件可以帮人造软件”变成了公理,编程的生产率从此脱离了人手的极限曲线。生产率还带着一张复利表:编程越便宜,人们敢写的软件就越大;软件越大,对编译器与工具的要求就越高;工具越好,门槛越低、胃口越大——门槛与胃口同步上升的循环,从 1957 年起就没有停过。此刻只需先记下一笔:抽象每降一次门槛,世界的软件需求就膨胀一次,这份膨胀既是产业的红利,也是后文一切“软件危机”叙事的源头。编译器与随后将登场的操作系统,是同一枚硬币的两面:一个管“把意图变成指令”,一个管“让指令排队上机”——IBM 很快就把两者合并成一套随机器交付的系统软件,机器出厂即带编译器,将成为此后所有计算机制造商的默认配置。把两条线索合起来看,霍珀与巴克斯其实做的是同一件事——把编程的门槛从“必须懂得机器的每一个寄存器”降为“必须说清楚要机器做什么”,一个从商业账单下手,一个从科学公式下手,方向却完全一致:都把“描述问题”与“描述机器”拆开,把中间的翻译交给机器。这一拆,是人类第一次系统地用机器解决“人机语言不通”的问题——此后从汇编器到编译器到解释器的一切翻译工具,都是这个拆法的技术细节。这是本书主线五在软件层的第一次显形:工具剥离的认知负担,最终决定了谁有资格参与创造;编译器剥掉的是寄存器与地址,释放出来的是一代不懂数字电路的写作者。而抽象的代价同步入账:程序员从此再也无法直接看见自己的代码在机器上的样子——这层看不见的翻译,既是编译器送给人类的礼物,也是人类交给编译器的抵押。抽象泄漏的老定律在此后几十年里反复兑现:编译器偶尔的优化失误、寄存器分配的意外、目标码与直觉的偏差,每一次都会把工程师打回机器层去排查——抽象许诺“不必关心下层”,但从没许诺“下层不会来找你”。霍珀晚年随身带着一段约三十厘米长的导线到处讲演——那是电在一纳秒里走过的距离——她把它们分给台下的将军与学生们,提醒他们机器的速度由物理决定:将军们总问卫星响应为什么这么慢,她的回答是把导线放进他们的口袋,你不可能让信号跑得比光快;而她真正的一生所证,是人可以用机器的速度去翻译人的思想。这段导线与那台 UNIVAC,是同一句话的两个半句:机器的纳秒,终将用于消化人的星期。这场革命的当代账单仍在续写:今天每一次高级语言与底层性能的权衡、每一次“编译器不够聪明”的抱怨与“让编译器更聪明”的研发,都沿着 1952 年画下的那条分界线展开——机器能替人做的部分永远在扩大,人必须亲自掌握的部分永远存在,两边的边界线就是编译器技术的国境线,七十年间只向北移动,从未停火。霍珀本人一路见证了自己点燃的革命走完全程——她以海军少将衔退役时,当年那台只会“做算术”的机器,已经通过一层又一层的编译器,学会了听懂人类的公式、账单乃至近似自然的句子;1992 年她去世时,用高级语言写程序已是全世界数百万人的日常,而这日常的全部起点,是 1952 年那卷没人愿意碰的磁带。不过,翻译要成规模,光有编译器还不够——编译器得先“读懂”程序,而“读懂”这件事需要一套严格的语法规则。当 FORTRAN 与 COBOL 各说各话、ALGOL 呼之欲出时,如何无歧义地描述一门语言,成了下一个十年的核心难题;那场围绕语法的形式化革命,是下一章的故事。


第 031 章 语法的形式化:BNF、上下文无关文法与解析树

1960 年 1 月,巴黎,一间会议室里坐着来自七个国家的十三个人。丹麦、英格兰、法国、德国、荷兰、瑞士与美国各出代表,原定十四人——美国人威廉·图兰斯基在会前被汽车撞亡,报告最终题献给他。他们要用六天时间为一门程序语言敲定最终定义。十三个人——一个足够小以至于六天能吵完所有细节、又足够大以至于七国立场无人缺席的规模——分属学术界与产业界的不同阵营,带着各自机构的立场与各自大陆的习惯——这场会议的组合方式,本身就是一次实验:语言这种东西,此前从来是单一作者或单一公司的私产。而这场会议的方法论,写在半年前的一份会议纪要的动机里:1959 年 6 月的巴黎 ICIP 会议上,欧洲与美国两拨人各自实现了上一版 ALGOL,结果发现双方拿着同一份手册写出的程序互不相认——对同一份散文描述,两个团队“读”出了两门语言。会议主席台上,彼得·诺尔(Peter Naur)放着他重写的草案。此前两年,这门语言的命运一直系在一份名为《ALGOL 公报》的刊物上——诺尔在哥本哈根独自编辑它,欧美两侧的实现者隔着它争论每一个细节;公报没有裁决权,它只是把所有分歧摊在纸面上,直到分歧多到必须开会。1960 年 1 月,十三个人坐进巴黎的会议室时,桌上已经摆好了诺尔连夜重写的全新草案——它吸收了初步报告与历次预备会议的全部建议;会议采纳它为工作基础,然后逐条争论、逐条表决。整份成稿的风格也带着编辑者的手笔:措辞克制、条款编号、每节附示例——后世语言规范的所有排版惯例,几乎都能在这份报告里找到原型。草案的第一节只有一句话足以载入史册:“语法将借助元语言公式描述。”会议结束时报了个冷幽默式的总结,被原样写进了正式报告:本报告代表委员会概念的并集与协议的交集。并集与交集——集合论的措辞,第一次被用来形容一群人如何共同发明一门语言。这句自我批评式的总结值得咀嚼:并集意味着所有提案都收进了文本,交集意味着写成的只有所有人都同意的部分——一部由最大公约数构成的语言,注定处处妥协,也注定处处有人力挺;它商业上的乏力与学术上的不朽,在这句开场白里就写下了判词。

歧义的代价:散文手册的破产

要理解这十三个人为什么跑到巴黎去抠字眼,得先看他们要解决的是哪一类的痛。五十年代的程序语言,定义方式基本靠散文:一本手册,几句自然语言,加上若干示例。这种写法在只有一家公司一种机器时勉强够用——错了一起错,改了一起改;可只要第二个人、第二台机器、第二种实现出现,散文的每一个模糊角落都会裂成分歧。FORTRAN 的历史已经预演过一次:它随 IBM 的机器扩散,每一家拿到手册的厂商都顺手改一点自己的方便之处,方言林立几乎从第一天就开始。到了 ALGOL 58,问题变成了国际事件:这门语言由欧美共同设计,而两侧团队各自实现了一版,1959 年的巴黎 ICIP 会议上,双方发现彼此对若干语法细节的理解完全不同——同一份报告,两个大陆读出了两门语言。散文歧义的裂变机制在这里一览无余:手册说“语句可以加标号”,却没说清标号算不算一种语句、空语句算不算语句、标号与变量同名怎么办;每一处留白都会被实现者按各自的机器惯例补齐,补法不同,语言就分叉了。分歧清单越列越长,唯一可靠的出路是开会——把每一处留白逐条填死。

歧义不是小事,它直接击中“语言”这个词的资格。一门语言如果无法唯一地判定“什么样的句子是合法的”,它就只是一份建议;建立在建议之上的编译器,永远无法保证自己与别人翻译的是同一门语言。形式化前后的差别可以打个比方:散文手册时代的语言像口头祖传的菜谱,每一代厨师按记忆复刻,味道各异;BNF 之后的语言像印着克数与温度的配方,任何烤箱都能烤出同一炉。菜谱变配方,损失的是些微手艺的灵光,换来的是跨地域、跨机器、跨时代的完全可复现——软件作为可复制的产业,从配方这一刻才真正开始。更深的麻烦在于,散文的歧义无法被发现,只能在使用中被撞见——你不知道手册里有几处会出问题,直到有人把它实现成另一副模样。五十年代末,这条裂痕已经开始让跨机构的语言合作寸步难行:每多一个实现者,就多一种解读;每多一种解读,语言的命运就多一分随机。巴黎会议要做的,就是把这门语言从“大家的理解”里拯救出来,钉到某种不会随读者变动的东西上。

巴克斯在 1959 年交出了第一件工具——他后来为这份记法赢得的名声,甚至盖过了 FORTRAN 之父的头衔;一门重要语言的发明者,最终又发明了描述一切语言的记法,这在计算史上是独一无二的连任。更妙的是两件发明的内在连续:FORTRAN 让机器翻译公式,BNF 让公式精确描述语言——他一生都在做同一件事,把人与机器之间的翻译工程往前推一格。这位 FORTRAN 之父基于设计 FORTRAN 与参与 ALGOL 的经验,发明了一种描述语法的记法:用一套符号规则,精确列出“什么样的字符序列构成一门合法的程序”。FORTRAN 的成功本身就是这项发明的助产士——它卖得越好,方言就越多,各家手册的散文歧义就越碍眼;巴克斯是从自家产品的成功里,亲身体会到了“没有形式语法”的代价,才动手去造形式语法。这套记法在 1960 年被诺尔重造后写进 ALGOL 60 报告,后世以两位设计者的名字称呼它——巴克斯-诺尔范式,简称 BNF。它的样子朴素得不像发明:

<数字>  ::= 0|1|2|3|4|5|6|7|8|9  
<表达式> ::= <数字> | <表达式>+<表达式> | <表达式>×<表达式>  

尖括号里是“类”的名字,冒号等号读作“定义为”,竖线读作“或”。就这么两条规则,无穷多个合法表达式便有了精确的出生标准:任何能从“表达式”这个符号出发、按规则一步步推导出的字符串,合法;推导不出的,非法。规则的集合是有限的,规则的产出是无穷的——用有限定义无穷,这正是“语言”需要的数学品质。严格说来,翻译程序在 BNF 之前已经存在:四十年代末的汇编器把助记符翻成机器码,已是第一代翻译工具;但从汇编器到编译器的跃迁,差的正是“描述任意结构”的能力——汇编是一对一的改写,编译则要理解层次结构,而层次结构的形式描述,要等 BNF 供给。

从自然语言借来的火种:乔姆斯基的阶梯

巴克斯的记法看起来是工程灵机,但它的数学骨架来自一个意想不到的方向:语言学。整个二十世纪上半叶,语言学家一直在尝试把自然语言的语法从教学技艺变成科学——西方世界长期把文法当作教学科目而非研究对象,描述全凭非正式的散文;布龙菲尔德与哈里斯等结构主义语言学家前赴后继,到 1956 年,诺姆·乔姆斯基(Noam Chomsky)把生成文法正式形式化,提出了一个把文法按表达力分层的体系,后世称乔姆斯基谱系。这个体系把形式文法分成四型,表达能力逐层递减、分析的机器也逐级降配:

      乔姆斯基谱系(1956)          对应语言            对应机器  
   0 型  无限制文法            递归可枚举语言         图灵机  
   1 型  上下文相关文法        上下文相关语言         线性界限自动机  
   2 型  上下文无关文法        上下文无关语言         下推自动机  
   3 型  正则文法             正则语言              有限状态自动机  

从高到低逐层包含,低型语言不具备高型特征。这个阶梯对编程语言的价值在于,它第一次回答了“该用多强的规则描述一门语言”这个问题。3 型正则文法最弱也最好分析——有限状态自动机就能识别,但表达力太弱,连配对括号都写不出来;0 型文法最强,等价于图灵机,但分析它没有高效办法。而 2 型——上下文无关文法——恰好卡在甜点位上:表达力足以描述绝大多数编程语言的结构(表达式、语句、块、过程),分析它又有现成的机器模型(下推自动机,一台带栈的有限状态机)。有限状态自动机与正则表达式的研究几乎与乔姆斯基的工作同时展开,很快被对号入座为词法层面(单词的识别)的工具——词法与语法的分层,从此既是理论也是工序;上下文无关文法则对号入座为语法层面的骨架——上一章 FORTRAN 编译器里“词法/语法/语义”的工序分层,至此有了自己的数学名字。巴克斯的 BNF,恰好就是上下文无关文法的一种书写形式——他没有读过乔姆斯基也做出了同样的选择,两条独立路径在 2 型文法上会合,这为“编程语言天然适合这套数学”提供了强证据:并非乔姆斯基的理论恰好照顾了编程语言,而是任何一门需要被机器无歧义执行的语言,都只能栖居于 2 型或 3 型的格子——表达力再往上,机器就不再能高效判定;表达力再往下,语言就写不出配对的结构。被执行性逼进哪层格子,是宿命,不是巧合。

语言学家的工具为什么能如此严丝合缝地套住编程语言?因为编程语言是刻意设计的人工产物,语法在造出来之前就已写成规则——自然语言是先有句子后有语法,编程语言是先有语法后有句子,两者顺序相反,后者天然站在形式化的顺风口。同时自然语言里充满习语与例外——它到底属于谱系的哪一层,语言学至今争论不休;编程语言则每个结构都有明确的构成规则,稳稳地落在 2 型的格子里。乔姆斯基的阶梯本是给自然语言画的,编程语言顺势站了进去,而且站得很低:几乎没有编程语言需要动用 1 型以上的表达力。语法的形式化,就这样以一场学科之间的顺水推舟完成了——语言学的数学,成了编译器的宪法。

十三个人与一份模板

巴黎会议的产品——那份 ALGOL 60 报告——之所以被后世反复引用,在于它留下的与其说是一门语言,不如说是一份“语言应该如何被定义”的模板。模板的第一根支柱是三层分离:报告开篇就把语言切成参考语言、出版语言与硬件表示三层——参考语言是委员会的工作语言与定义语言,字符的选择只为人类的相互理解,不受任何机器的限制;出版语言允许印刷与手写的变体(下标、指数、希腊字母),各国可以不同,但必须与参考语言一一对应;硬件表示则是特定机器字符集逼出来的压缩形式,是那台机器的翻译器接受的版本。定义、人读的记法、机器读的记法,从第一页起就被拆成三个对象。拆分的意义要看清:参考语言用一套各国代表都认得的通用符号书写定义,不迁就任何键盘;出版语言承认德国人要印体字母、丹麦人要写下标的排版习惯,只要求与参考语言一一对应;硬件表示才低头,承认每台机器的字符集残缺,允许压缩改写。三层各自独立、层层可译,规范从此是独立于任何实现的东西——这个今天的常识,在这份报告里第一次有了制度形态。对照 1959 年的教训,这层分离正是对“散文手册时代”的制度性报复:定义不再寄居在任何一份实现里。

第二根支柱就是 BNF 本身。报告第一节开宗明义地写下了元语言公式的规则,随后把整门语言的语法从头到尾用这套记法写出——从基本符号、数字、标识符,直到表达式、语句与程序。一门编程语言的全部合法形态,第一次被压缩成几页公式;语法从此可以像数学对象一样被引用、被检验、被讨论。这套记法的命名还经历了一场四年的推敲:最初它被称作“巴克斯范式”(Backus Normal Form),1964 年 12 月,克努特在《ACM 通讯》上发表短信,提议改名“巴克斯-诺尔形式”——理由有三:荣誉应归于巴克斯与诺尔两人;大家熟知的缩写 BNF 得以保留;且从数学上说这根本不是一种“范式”(Normal Form)——任何上下文无关语言都容许无穷多份等价的 BNF 文法,“正规形式”之名名不副实。这条改名建议的技术理由里,藏着形式化最迷人的一课:连描述语言的记法本身,也要接受数学标准的审视,名实不符就要改名。提议从此定案,BNF 三个字母沿用至今——而“范式”一词的让位也带来一个诚实的提醒:这套记法描述文法,但它不唯一、不标准、也不“正规”,它只是好用;形式化的世界不迷信名号,只迷信定义。

第三根支柱埋在报告的第四节:块与作用域。一句话原则——“每个块自动引入一层新的命名层”——派生出此后所有主流语言的命名规则:块内声明的标识符是局部的,它在块外不存在,外部同名实体在块内完全不可见;用到而未声明的标识符是非局部的,指向外层同名实体;块可以嵌套,局部与非局部递归理解。这套规则今天有个名字,叫词法作用域——命名冲突由语言规则裁决,而不靠程序员的自觉或命名纪律。报告还顺手发明了静态变量的原形:声明为 own 的量,离开块再回来时值还在。最富戏剧性的是递归:过程可以调用自身——这条如今天经地义的性质,是在会议很晚的阶段才补进规范的,据记载还遭到了部分委员的反对。反对的账算得出来:递归意味着每一次调用都要为新的一层变量现场开辟存储,而五十年代的机器惯例是给每个过程分配固定地址——允许自调用,等于要求整个存储分配机制换一副骨架。规范上轻描淡写的一个词,实现时要连根改造机器的习惯;这场反对并非顽固,是对实现成本的清醒预判——只是历史又一次站在了愿意付出成本的一边。十三个人逐条争论的会场,就这样在六天里为之后六十年的语言预留了几乎所有承重结构。会议纪要里那些没有写进报告的争执——递归要不要、I/O 归谁管、分号可省不可省——同样是遗产的一部分:后来每一个语言标准委员会里发生的争吵,都是这六天的续集。

这份报告的身后名与生前待遇,构成了一组几乎残忍的对照。ALGOL 60 没有拿下市场——它的用户基本限于欧美的研究型计算机科学家;商业遇冷的原因毫不神秘:报告根本不定义输入输出,而大型机厂商对一门不能读写数据、又被一纸共同规范锁住的语言毫无兴趣。不定义 I/O 并非疏忽,而是委员会的自觉边界——I/O 与机器的绑定太深,写进定义就会让“机器无关”名存实亡;委员会选择了定义的纯洁,代价是让每一台机器的实现者自己发明 I/O,于是同一个 ALGOL 60 程序在两台机器上仍需改写才能读写数据。纯洁与实用的账,在这份报告上结出了最苦的一枚果实:定义的纯度越高,落地的阻力越大。I/O 直到 1975 年才由 IFIP 工作组以修正报告的形式补入,此时市场早已属于别的语言。但同一份报告定义的 ALGOL 60,成了发表算法的标准记法——六十年代的学术论文里,新算法几乎都先用 ALGOL 60 写一遍;它的第一个实现由迪杰斯特拉与宗讷维尔德在 1960 年 8 月为 Electrologica X1 完成;而它的语言谱系枝繁叶茂:CPL、PL/I、Simula、BCPL、B、Pascal、C,都是它不同程度的后代。关于它最著名的那句评语——“这是一门远超其时代的语言,它不仅是对前人的改进,也是对几乎所有后继者的改进”——流传时通常被归于阿兰·佩利;但考据确认,这句话出自 1973 年霍尔的一份文献书单,写在 ALGOL 60 报告的条目下,佩利只是十三人之一。一句被传错作者的名言,一句被市场拒绝的语言,一份被所有后继者继承的报告——ALGOL 60 的身后待遇,是计算史里“影响力”与“市场份额”彻底脱钩的极端案例。份额衡量的是某一年的销量,影响力衡量的是后来者再也绕不开的程度;两者偶尔重合,多数时候背道而驰,而 ALGOL 60 把背道而驰走到了极限。再补一笔名单上的巧合:巴黎的十三人以及这份报告的周边人物里,此后走出了多位计算机科学的标志性人物——佩利、诺尔、迪杰斯特拉、霍尔,一个个名字此后都会在计算史的各个章节里反复出现;一场决定语言语法的会议,顺便成了半个学科名人的合影现场。

机械骨架:解析树与自动机器

语法形式化之所以能撑起整个编译产业,是因为有限条规则背后站着无限的解析树。拿一份最小的表达式文法,看一串字符如何被规则“接生”成结构:

  文法(EBNF 风格):  
    <表达式> ::= <数字> | <表达式> + <表达式> | <表达式> × <表达式>  
  
  输入串:  1 + 2 × 3  
  
  解析树(一种可能):  
            <表达式>  
           /    |    \  
      <表达式>  +   <表达式>  
         |         /   |   \  
      <数字>  <表达式> ×  <表达式>  
         1        |          |  
       <数字>    <数字>  
          2          3  
  ※ 树形即解释:先乘后加的结构被树"记住"了  

同一串字符可以长出不止一棵树——1+2×3 既能解析成 1+(2×3) 也能解析成 (1+2)×3,两种树都符合上面那条文法。这就是歧义文法:文法允许多种解析,语言的意义就悬而未决。解析树的价值也在这个反例里显形——它把“怎么理解这串字符”变成了一个看得见的对象:编译器照着树生成代码,语义分析沿着树核对类型,优化器在树上做等价变换;树是编译器前后的通用语言,而树正是文法规则逐条施行的产物。有文法,才有树;有树,编译器的前半生才有处安放。程序员最熟悉的受益藏在报错里:解析器说“第三行缺一个分号”,说得出位置与性质,正是因为解析在树上断了枝——错误信息能精确到行与符号,是文法形式化之后才配得上的待遇。消除歧义有两条路,要么改写文法把优先级写死,要么在语言规范里另行规定结合性与优先级——ALGOL 60 报告与其后的每一份语言标准都在做这件事。而机器怎么把输入串长成解析树?乔姆斯基谱系在这里给出了机器模型的对应:3 型正则语言用有限状态自动机识别(词法分析——切单词),2 型上下文无关语言用下推自动机识别(语法分析——带一个栈,栈正是长出解析树的空间)。“层次”不是比喻,是四台能力递增的机器。

理论齐备之后,剩下的是工程问题,而工程问题的突破在六十年代中期到来。顺带说清一个年份账:乔姆斯基的谱系发表于 1956 年,巴克斯的记法成形于 1959 年,两条线在六十年代前期被学界打通——上下文无关文法与 BNF 的一一对应被正式确认后,语言学的分类框架立即变成了编译理论的分类框架,此后的每一篇解析论文都同时引用两边。1965 年,克努特发表论文《从左到右的语言翻译》,定义了 LR(k) 分析:从左向右扫描,向前看 k 个符号,就能唯一确定该移进还是该归约、用哪条规则归约——这是自底向上解析的数学完备解,理论上它能覆盖全部确定性上下文无关语言。但完备解有一道残酷的门槛:按定义直接构造的 LR(k) 分析器过于庞大,六七十年代的内存装不下。工程界用十余年时间找到了折中——LALR(向前看 LR),把状态表压缩到可实现尺寸,只损失一小部分文法覆盖面。效率的账也在这里结清:确定性解析免去了回溯——不必把猜错的分支撤回重试,输入串从头到尾只走一遍,解析时间与输入长度成正比——线性时间的保证,让编译这道工序第一次可以被批量规划。对本卷的万倍时延裂谷而言,这是编译侧最重要的填谷工程之一:解析若要反复回溯,一道程序的翻译就要多付数量级的机器时间;把“猜”换成“算”,编译才配得上纳秒级的机器。1975 年前后,贝尔实验室的斯蒂芬·约翰逊把 LALR 技术封装成一个工具:Yacc(Yet Another Compiler-Compiler,又一个编译器的编译器)。程序员只需写一份 BNF 文法加若干动作,Yacc 就自动生成一个完整的语法分析器;它与词法生成器 Lex 配合,构成 Unix 世界里编译器前端的流水线模板。“加若干动作”五个字尤其值得停留:每条文法规则旁边可以挂一段代码,解析器每当用这条规则归约一次,就执行一次挂载的动作——文法的骨架上从此可以挂语义的血肉,语法驱动的翻译就此成为一门手艺;今天各种代码生成器、解释器原型、乃至配置语言,仍在沿用这套“文法加动作”的模具。语法分析从每颗编译器都要重造的轮子,变成了一份文法文件加一条命令。解析本身有两大门派,此处不妨点破:自顶向下从起始符号出发,照着文法从树根长到树叶,直观易写但遇左递归会死循环;自底向上从叶子往树根归约,把输入符号逐个移进栈里,一旦栈顶凑成某条规则的右部就归约成左部。LR 是自底向上门派里最严谨的一支——名字里的 L 指从左向右扫描,R 指构造的是最右推导的逆过程;而 Yacc 生成的 LALR 分析器,正是这门派在工程里的当家武艺。

     写文法( expr.y )        写词法( lex.l )  
          │                     │  
          ▼                     ▼  
       Yacc ────(LALR 状态表)────► y.tab.c  
          │                     │  
          └────────┬────────────┘  
                   ▼  
            C 编译器编译  
                   ▼  
     可执行的语法分析器(解析树或直接执行动作)  

形式化的账单

形式化的账单要从它的欠条记起。第一笔:语法被形式化了,语义没有。BNF 精确判定“什么样的字符串合法”,却一个字都不说“它是什么意思”——ALGOL 60 报告自己就是例证:语法是公式,语义仍是散文,歧义没有被消灭,只是从语法层被赶到语义层;此后语义形式化的各种尝试——描述程序如何一步步执行的操作语义、把程序映射为数学对象的指称语义、借逻辑规则给程序“判卷”的公理语义——追了几十年,各自在学术圈里立住了门户,却至今没有一种达到 BNF 在语法层的普适地位。语义比语法难形式化,是因为它要绑定的对象不同:语法的边界是字符,语义的边界是运行时的一切行为——后者几乎就是计算本身,而计算的形式化正是计算理论自己都没有走完的路。第二笔:理论的完美与工程的可行之间存在真实裂谷。LR(k) 是数学完备解,完备解大得造不出来;LALR 可造,却要放弃一部分文法——程序员至今仍会在 Yacc 里遇到“文法有冲突”的报错,报错的根源可以追溯到那次为装进内存而做的压缩。解析器的冲突报告是许多工程师职业生涯的第一课:数学保证了路的存在,工程决定了你走哪条、绕多远。形式化的受益者名单则一路延烧到今天:Unix 的 Yacc 与它的开源后裔 Bison 长成了编译器工厂,数据库的查询语言、配置文件的格式、网络协议的报文规范,几乎每一份需要“机器判断合法性”的说明都改用了文法记法;JSON、HTTP 等协议的规范文件至今随文法发布——一部协议的现代规范如果只有散文,反而会被同行怀疑不严谨。第三笔:歧义的判定本身不可判定——判定一份任意文法是否歧义,是上下文无关文法的不可判定问题;也就是说,没有任何算法能替你检查所有文法,歧义这个敌人理论上无法彻底清剿,只能对已知的文法逐一排除。形式化把混乱关进了笼子,笼子的栅栏却永远留着几根理论证明拆不掉的。

ALGOL 60 的商业账单同样值得清点。它在市场上几乎全军覆没:没有 I/O,厂商不感兴趣,用户只有研究者。但这份失败的名册恰恰是它影响力的证明——所有重要的后续语言都在向它致敬的路上:CPL、PL/I、Simula、BCPL、B、Pascal、C,谱系清晰可查;词法作用域、块结构、递归、静态变量,每一个概念都经它第一次写进正式规范。它的失败与它的遗产并不矛盾,而是同一件事的两面:它是一份研究共同体的规范,从立项起就没打算讨好任何一台机器的厂商;市场不买账与历史致敬礼,由同一份文件的同一处性格决定。IFIP 工作组 2.1——这支制定 ALGOL 的常设队伍——后来继续召开会议修补与扩展语言,成为此后所有语言标准委员会的组织蓝本:定期集会、公开争鸣、修正报告、版本演进;今天任何一门语言的标准委员会,走的都是 ALGOL 时代铺下的流程。付账的人也因此分成了两拨——当年放弃 ALGOL 的厂商与用户,为生态统一推迟的十年买了单;而十三位代表与他们的后继者收获的,是编程语言此后再也无法退回散文时代的制度红利。

本章的账目合拢处,两条主线同时到账。主线一的账:BNF 把“一门语言的全部合法句子”抽象为有限规则生成的无穷集合,这是典型的抽象收益——用有限的描述管辖无限的对象;它的击穿条件同样被精确划定——歧义文法不可判定、语义不在管辖范围内、文法的表达力每升一级解析成本就暴涨一档,抽象许诺的边界从此清清楚楚。主线四的账更现实:这十三个人来自七个国家,按概念并集与协议交集的方式共同署名一份技术规范,机制上正是十年后标准委员会角力场的原型——ALGOL 60 报告证明了国际协作可以产出高于任何单一厂商的定义,也证明了这种协作的产品注定难以讨好其中任何一家。巴黎那六天的真正遗产,因此可以钉成一句话:它让“一门语言是什么”第一次有了唯一、可检验、可继承的答案——此后每一门语言、每一个接口、每一份协议的规范文件,无论写下多少页,都在沿用这份报告立下的格式;市场记住了赢家,而历史记住的是格式。


第 032 章 优化编译器、静态单赋值(SSA)与 LLVM 范式解耦

2000 年,伊利诺伊大学香槟分校,一名叫克里斯·拉特纳(Chris Lattner)的博士研究生坐在实验室里,面对一个所有编译器研究者都熟悉的困境:他想试验一种新的优化算法,却发现载体现成的编译器是一头几百万行的巨兽——想改动其中一处优化,就像在蜘蛛网上跳舞,牵一发而动全身。那个年代几乎所有编译器研究者都被同一张蛛网困住。拉特纳的选择不是在蛛网上继续爬,而是自问了一个后来改变整个软件工业的问题:编译器为什么必须是一整块?如果把语言与机器之间的那层翻译拆开,让千种语言与百种芯片各自只写一个薄薄的接口,中间全部复用,会怎样?这个问题的答案花了几年时间写成,它的名字叫 LLVM。而在它背后,站着此前四十年里两代编译器研究者铺好的全部地基——从一位在 IBM 教程序员用 Fortran 的女性开始。操作系统给机器盖起了管理的壳,而编译器决定机器听懂什么、听懂多快:本章是卷三的归宿章,它要清点的,是软件世界里最深的那个抽象层——把人类意图翻译成机器约束的那一层——如何被建起来、被标准化,又如何在不肯服从的地方塌了下去。

让机器看懂程序的两张地图

上一章讲过,语法分析解决的是“程序写没写对”:词法、文法、解析树,把一串字符组织成机器可以检查的树。但语法正确的程序离“跑得快”还有十万八千里——同样的语义可以有几十种写法,有的写法比别的快十倍。把“写得对”翻译成“跑得快”的整片疆域,属于编译器的另一半:优化。这片疆域的理论地基,是弗朗西斯·艾伦(Frances Allen)在 IBM 打下的。她 1957 年加入 IBM 研究部门时,第一个任务还是教新来的程序员使用 Fortran——那门语言此前不久才由巴克斯的团队证明“机器可以自己生成合格的代码”。随后她被派去为 Stretch 与 Harvest 这两个 IBM 的超级机项目管理编译器优化团队:巨型机的每个周期都贵得惊人,优化的每一分收益都被放大到无法忽视——正是这种极端环境,把“代码如何被系统地变好”从一个手艺问题逼成了一个科学问题。但她很快发现了真正的问题所在:编译器要优化程序,前提是能“看懂”程序的结构,而高级语言的控制流——分支、循环、跳转——在那个年代没有任何形式化的描述工具。此前一章的解析树解决了“写没写对”,霍珀与巴克斯的早期编译器证明了“机器能生成代码”——但生成出来的代码好不好、能不能更好,全部依赖硬件工程师的手感,没有理论,没有方法,也没有公共的语言可以讨论。

艾伦的回答是两张地图。第一张叫控制流图:把程序切成一段段只有单一入口和单一出口的基本块,以基本块为节点、跳转为边,整个程序的所有可能执行路径就变成了一张有向图——循环是图上的环,死代码是图上不可达的孤岛,一切优化都开始有了一张公共的地基。第二张叫数据流分析:沿着这张图迭代求解“每个变量在哪里被定义、在哪里被使用、沿着哪条路径可以传播到哪”——到达定值分析、活跃变量分析,前向与逆向两股信息流在图上交汇,常量传播、死代码消除、寄存器分配这些优化的合法性,从此可以被数学地证明而不是凭手感猜测。一张控制流图的样子可以用一段最普通的分支程序画出来:入口块做完条件判断后分出两条边,各自通往 then 块与 else 块,再在汇合块重新并成一条边——循环则是图上首尾相接的环。把程序翻译成这样一张图之后,许多此前靠感觉的问题第一次有了精确的答案:图上不可达的块就是死代码,图上的环就是循环,两个变量能否同时活着、一个表达式能否被提到循环外,全部变成图上可以迭代表达的方程。她 1966 年的论文《程序优化》第一次把这套分析系统化,1971 年又与约翰·科克合著《优化变换目录》,把当时已知的全部优化手段编成第一部目录——优化的手册化,就是从这份目录开始的——此后编译器每学会一招新变换,本质上都是往这本目录里再添一条条目。此后的几十年里,她把同一套方法推进到并行编译:1980 年代初她创立的 PTR(并行翻译)项目,研究的是如何让编译器自动把串行程序改写成能在多处理器上同时执行的形态——彼时多处理器还是超级计算机的专属奢侈品,这个问题被主流视为屠龙之技;三十年后多核时代到来,编译器自动并行化重新成为产业级命题,人们回头才发现地图早已画好,只是当年无路可走。2006 年,图灵奖第一次颁给一位女性,表彰的就是这套奠定现代优化编译器基础的体系。把这份荣誉与三十多年前霍珀的 A-0 排在一起看,会有一种谱系学的感慨:编译器这门学科从诞生起就有女性的名字铸在基石上——一位发明了“编译器”这个概念,另一位把它变成了科学;而两位都花了半个世纪,才等到行业迟来的授勋。评委会的授奖词把她的贡献概括为一句话:她让编译优化从零散的技巧变成了一门有公共地基的科学。在她之前,每一款编译器的优化都是各自的手艺;在她之后,“先画控制流图、再做数据流分析、然后应用变换目录”成了全世界编译器的通用语法——一个领域成熟的标志,就是它的问题开始拥有共同的名字。不过这两张地图管的是“程序怎么跑”,还管不到“表示本身能不能更聪明”——那要等一种全新的表示来接管。

一变量一名:SSA

两张地图解决了“在哪里优化”的问题,但没有解决“优化起来有多贵”的问题。答案一度很不乐观。传统编译器的中间表示里,一个变量可以被反复赋值:先等于一,再等于二,循环里再等于三。当程序在分支或循环后汇合时,一个使用点面对的是好几个可能的定义——“这个 x 到底来自哪次赋值?”要回答它,编译器必须做到达定值分析:构建位向量,沿控制流图反复迭代,直到所有信息稳定;想知道变量还活多久,又得逆向再做一遍活跃变量分析。每一种优化前都要重跑这些迭代,数据流方程的开销像税一样摊在每一次优化上。

1991 年,Cytron 等人发表的工作把这个税基直接取消了——其思想此前已在 IBM 的研究里成形。静态单赋值形式,简称 SSA,规则简单到只有一句话:每个变量在整个程序文本中只被赋值一次。原本被反复赋值的 x,现在变成 x1、x2、x3——每次赋值都是一个新名字。“静态”二字值得停半拍:它指这套形式只关心程序文本,不关心循环在运行时真的转了多少圈——循环体里的赋值无论执行十次还是万次,在文本里都只有一个定义点。唯一的麻烦出现在控制流汇合处:if 的两个分支各自给 y 一次赋值,汇合之后的 y 该是谁?SSA 的答案是 φ 函数——在汇合点放一个特殊指令,声明“此处 y 的值,取决于从哪条路走来:从 then 来取 y2,从 else 来取 y3”。一张图看懂这场变形:

 原始程序                     SSA 形式  
 ─────────────────           ─────────────────────────  
 y = 0;                       y1 = 0;  
 if (x > 42) {                if (x > 42) {  
     y = 1;                       y2 = 1;  
 } else {                     } else {  
     y = x + 2;                   y3 = x + 2;  
 }                            }  
 print(y);                    y4 = φ(y2, y3)  ← 汇合点选值  
                              print(y4);  

变形之后,优化经济学被彻底改写。每个名字只有一个定义点,“这个值从哪来”不再需要迭代求解——它就是一条直接的指针;“这个定义被谁用了”也不再需要逆向分析——它就是定义点挂着的使用者名单。到达定值与活跃变量这两大分析的全部工作,被数据结构本身一次性吸收:原来要反复迭代的图论方程,退化成了沿指针的遍历。常量传播、公共子表达式消除、死代码消除,每一种优化都在这张更干净的地基上变快、变简单。举一个最小的例子:若某个值在 SSA 里被定义为常数七,那么从它的唯一定义点出发,沿着使用者名单走一圈,所有引用它的指令都能当场替换成立即数——在旧表示下,这需要证明“七”沿着每一条控制流路径都没有被中途覆盖;在新表示下,这只需要看一眼定义点。优化的判定从“证明一个全称命题”退化成“沿一条链走到底”,编译速度与优化激进的自由度同时被解放。这套形式的影响力甚至溢出了传统编译器:JavaScript 与 Java 的虚拟机用它做即时编译,机器学习框架把它当作算子融合的画布,形式化验证工具借它的单赋值性质做程序证明——凡是要“推理程序行为”的地方,SSA 几乎成了默认起跑线。这套形式的谱系此前已在 IBM 内部成形,正式发表于 1991 年;此后三十年,从 GCC 到 LLVM 到各类虚拟机,几乎所有现代优化编译器都把 SSA 当作中端的母语——它的不变量只有一句话:每个值只定义一次,定义支配使用。它甚至不是贯穿始终的:优化做完后,SSA 会被析构还原,因为最后真正要把名字落到有限个物理寄存器上的寄存器分配,需要的是旧式的多赋值世界——SSA 是中端的母语,不是全编译器的方言。“支配”是控制流图上的严格关系:一个定义点支配某个使用点,意思是所有通往该使用的路径都必须经过这个定义——正是这条数学性质,保证了 φ 函数选出的值在使用处永远有意义。

巨石与解耦

工具齐备之后,剩下的瓶颈在组织。2000 年前后的编译器世界里,事实上的王者是 GCC——GNU 编译器套件,自由软件运动的旗舰工程,几乎每一个开源操作系统都靠它把整个软件世界从源码变成二进制,支持几十种语言与平台,代码数百万行。它的强大无可置疑,它的结构却是典型的巨石:前端、优化器、后端彼此深度耦合,内部虽以 GIMPLE 与 RTL 两种中间表示衔接,但要给 GCC 加一种新的优化,得理解巨石内部错综的依赖;要加一个新目标架构,代价同样高昂。这背后是一个古老的数学困境:若每种语言都要配每一种芯片,M 种语言乘以 N 种架构,就是 M×N 套编译器实现——语言与架构各自增长,组合数却在相乘。行业在这道乘法题前消耗了几十年的重复劳动。更隐蔽的代价是知识的割裂:编译器团队不懂处理器的流水线细节,处理器团队不知道编译器能许诺什么,双方各自为战——上一章里 x86 把 RISC 思想藏进微操作内部,正是这种割裂之下硬件单方面替编译器补课的例子;而编译器这边,能拿到一行处理器手册就不错了。

拉特纳的 LLVM 给出的答案,是把这道乘法题改写成加法。改写后的算术长这样:

   M 种语言前端            N 种目标后端  
   ┌──────────┐          ┌──────────────┐  
   │ Clang(C/C++)│──┐    ┌──│ x86 代码生成   │  
   │ Rust 前端    │──┼─► [ │  LLVM IR (SSA)  │ ] ─┼──│ ARM 代码生成   │  
   │ Swift 前端   │──┘    │  │  优化 Pass ×N   │ │  └──│ RISC-V 代码生成 │  
   └──────────┘          └──────────────┘  
        M 个入口            1 份中间层             N 个出口  
        (语言)            (所有优化只写一份)      (芯片)  

顺带一提这个名字的混乱史:它最初是 Low Level Virtual Machine 的缩写,后来项目长大了,这三个词已经名不副实,社区索性不再展开它——LLVM 就是 LLVM,既指整个基础设施,也指那层中间表示,也指底层的库集合;一个靠毕业论文起家的项目,连自己的名字都追不上自己的体量。它定义了一种语言无关、目标无关的中间表示——LLVM IR,一种 SSA 形式的带类型低层指令集——然后让所有语言只负责把自己翻译到 IR,所有芯片只负责从 IR 往下翻译,中间的全部优化只写一份。C 与 C++ 的前端后来独立成了 Clang;后端覆盖 x86、ARM、RISC-V 等几十种架构;每个优化以“通道”(Pass)为单位注册,可以独立开发、独立测试、自由排序。这套结构与编译原理教科书的经典分层一一对应——顺带一提,GCC 至今没有死去:它依然是许多开源系统默认的编译器,两个编译器体系至今并行服役,双雄并立本身就是对“范式解耦”价值的最好确认——市场容得下两套,说明这套基础设施的需求是真实且长期的:开源世界偏爱 GCC 的成熟与法律干净,商业芯片公司偏好 LLVM 的模块与宽松许可,两侧各自演化出对方无法复制的生态腹地。词法、语法、语义分析属于前端,把源代码逐层提纯成中间表示;中间端在 IR 上做所有与机器无关的优化;后端再做指令选择、寄存器分配这些与机器相关的翻译。分层的目的只有一个——让每一层的正确性可以被单独验证,让每一层的改进不需要重新审计全栈。这与三十年前 C 语言重写 Unix 的逻辑一脉相承:C 用一门可移植的语言让操作系统脱离了芯片引脚,LLVM 用一层可移植的中间表示让全部语言脱离了目标平台——抽象每前进一层,被锁死的东西就少一件。M×N 的组合爆炸被降维成 M+N 的线性工程——一种新语言的成本是一个前端,一种新芯片的成本是一个后端,而两个前端可以共享全部几十个优化通道——加法的经济学,第一次出现在一个以指数增长的行业里。这正是本章标题里“范式解耦”的全部含义:把编译器从一个巨石,解耦成由通用中间层连接的三段式。此后果实累累:Swift、Rust 等新语言在诞生之初就跳过了“为每种平台写代码生成”的全部成本;多家芯片公司的新架构可以立刻获得整个语言世界的支持。编译器第一次从每个项目重复自建的零件,变成了整个行业共用的一层基础设施。此后的连锁反应超出了任何一篇毕业论文的想象:新语言纷纷把 LLVM 当作出厂后端;图形处理器厂商用它生成 GPU 上的计算代码;连苹果与 AMD 这样的芯片巨头,也把自家的编译栈架在这层公共地基上。有一个常常被忽略的技术外因素:LLVM 采用了宽松的许可协议,商业公司可以把基于它的编译器做成闭源产品而不必公开自己的代码——对照 GCC 那份要求衍生品同样开源的通用公共许可证,这个差别决定了哪家编译器能走进每一家芯片公司的内部流程。一家大学实验室的毕业设计,最终成了从手机到超算的默认翻译官。

失败案例栏:Itanium 的大溃败

解耦的价值,最好由一个反例来称量——一个把编译器押到极限、然后被编译器拖垮的例子。时间线值得先对齐:安腾立项于 1994 年,首品上市 2001 年,战略破产于 2003 年前后——它几乎与上一章的多核转折同步;同一个英特尔,一边在桌面市场被频率之墙逼进多核,一边在服务器市场把全部未来押在“编译器可以替硬件调度”的假设上。两场溃败共享同一个时代背景:硬件的旧红利到期了,而两条新路的赌注,分别押给了硬件与软件。
1990 年前后,惠普的工程师得出一个判断:RISC 架构终究会撞上每周期一条指令的天花板,硬件乱序执行的逻辑越来越贵,而编译器的技术正在突飞猛进。他们的方案名叫 EPIC——显式并行指令计算:与其在芯片里用昂贵的硬件去动态猜测哪些指令可以并行,不如在编译期就把能并行的指令显式地捆成长指令包,芯片只需要拆包执行。1994 年,惠普说服英特尔联合开发这套架构,命名为 IA-64;1999 年,处理器的正式名称定为 Itanium——恰逢《泰坦尼克号》热映,业界给它起的绰号 Itanic(安腾号)从第一天就带着不祥。绰号的贴切远超起名者的本意:这艘船不仅在 2021 年沉没,它的沉没方式也如出一辙——不是撞上一座看得见的冰山,而是撞上一座所有人都知道存在、所有人都以为可以绕开的冰山:程序运行时的不可预测性。联盟双方的开价并不对等:惠普想借新架构保住自家高端服务器线的未来,英特尔则看中了甩掉 x86 包袱的机会——既摆脱与对手在旧指令集上的缠斗,又借换代重立行业规则。各怀目标的联合,注定了当困难来临时,两家对“继续坚持”的定义并不相同。

必须先把这个方案的理论优雅写足,否则这场溃败就无从理解。EPIC 的主张在纸面上近乎完美:乱序执行是硬件在用蛮力补偿信息缺失——硬件不知道哪些指令可以并行,只好用重命名、保留站、重排序缓冲区这些昂贵的电路在运行时现算;而编译器手里握着全部源代码,理论上最有资格预先算出并行性。把运行时的调度挪到编译期,芯片可以砍掉整个乱序引擎,省下的晶体管换成更多执行单元;省下的功耗换成主频;指令定长成包,解码电路也随之简化。这不是异想天开——惠普说服英特尔的论据直指要害:你们为 x86 的兼容性付出的解码与乱序代价,早已是全行业之最;现代编译器已经足够聪明,完全能在编译期判断依赖、完成寄存器命名,把并发性直接写进指令包。再加上一个不可拒绝的战略理由:三十二位向六十四位迁移是全行业都要换指令集的天赐窗口,英特尔甚至砍掉了自己在 x86 上支持六十四位的后续计划,准备带着整个产业改嫁 IA-64。

崩溃的裂缝有两条,都藏在编译期视野的边界上。第一条是指针别名:高级语言里两个指针可能指向同一块内存,编译器若不能证明它们互不相干,就必须按最坏情况处理——而证明这一点在通用程序里常常等价于停机问题级别的困难。依赖关系算不清,指令包就捆不起来;捆进去的并行性是假的,运行时又没有硬件兜底,整个包只能降级慢行。第二条是缓存的随机性:哪些数据恰好在缓存里,完全由程序运行时的行为决定,编译器在编译期无从知晓;乱序处理器遇到缓存缺失可以动态切换去干别的活,而捆死的指令包一旦缺数据,整包原地等待。此外还有一道更冷峻的墙:并行性被烧死在了二进制里——指令包的宽度在编译那天就定了型,未来的芯片即使更宽,旧程序也无法受益,除非全行业为每一代芯片重新编译所有软件,而这在商业上不可接受。

现实如期而至。还要认清它的假想敌是谁:IA-64 立项时的对标对象并非 x86,而是 POWER 与 SPARC 盘踞的高端服务器市场——安腾最初的算盘,是用更便宜的兼容生态去蚕食那些昂贵的 RISC 帝国。当年被未来图景吸引的并非少数:微软、硅谷图形、日立、布尔等一大批企业都曾计划跟随 IA-64 放弃自家的 RISC 路线。2001 年上市的首代 Merced 在整数基准上落后于同频的至强;交付一再延期,让这些支持者陆续转投他案;2003 年,AMD 用向下兼容的六十四位 x86 抢走了整个换代的钥匙,英特尔被迫在自己的至强产品线上采纳对手的扩展,等于亲手宣告 IA-64 战略的破产。此后十几年的每一次迭代都只是延缓:产能与性能始终起不来,产品线一缩再缩,到 2017 年的 Kittson 只为存量客户维持供货,2021 年正式停产——从立项到落幕整整三十二年,产业为其付出的研发与生态成本以百亿美元计,而它最终的服务对象只剩下惠普自己的小型机客户。撺掇这场豪赌的惠普把自家关键业务服务器整个押上了安腾,又在机器停产后陪客户再走了最后一程:发起者、殉葬者与守墓人,三重角色由同一家公司领完。设计它的并非庸手——惠普与英特尔的架构师是业界最资深的团队,连克努斯都留下过一句评语:安腾路线本应如此了不起,直到人们发现所期望的那种编译器基本上写不出来。溃败的原因不在编译器技术不够努力,而在把赌注押在了“编译期可以看见一切”这个前提上——通用程序的运行时恰恰由编译期看不见的东西构成:指针的指向、缓存的冷热、分支的实际走向。理论优雅与工程可行之间隔着一条运行时,这条线在 2001 年到 2021 年间,以数百亿美元的成本被量了出来。而 VLIW 的思想也没有死:在延迟可预测、依赖固定的数字信号处理器与图形芯片里,它至今仍是正确答案——失败的从来不是技术,是它与错误问题的一次错配。

抽象的收账

把 SSA、LLVM 与安腾放在同一张桌面上,本章的主线才显出全貌。三十多年前,霍珀与巴克斯的编译器刚问世时,汇编程序员给它们的判词是“效率无法比拟手工精细优化”——这个判词在当年无可辩驳;四十年后,优化编译器生成的代码已经反超绝大多数人手所能达到的水平,而它做到这一点的方式,恰恰是把“优化”本身建成了一门有地图、有目录、有形式化地基的科学。这门科学的账本,最终写在三个地方:优化编译器是程序意图与机器执行之间最高的一层抽象:控制流图把程序抽象成图,数据流分析把执行抽象成方程,SSA 把变量抽象成被支配的值,LLVM IR 把一切语言与一切芯片抽象成同一种中间形态——每一层抽象都让上层的优化变得更普遍,也让下层机器的细节更难渗透。安腾的溃败就是这层抽象代价高昂的一次泄漏:它假设编译期可以完整看见程序的运行时,而指针别名证明这层视野有原理性的盲区;反过来,SSA 与 LLVM 的成功,恰恰因为它们只在编译期视野之内做文章——把不变的东西结构化,把看不见的东西留给硬件。这是主线一在软件层的完整证词:每一层抽象都在兑换可见性与能力,SSA 用“放弃多赋值”换来了分析的免费,LLVM 用“放弃自定义全栈”换来了生态的复利,安腾用“假设全知”换来了全盘的崩塌,崩塌时连本带利。范式解耦之后的世界并不是免费的:中间层成了行业共同依赖的窄口——新语言与新芯片都活在这层通用接口的条款之下,谁定义 IR 的表达力,谁就定义未来十年什么优化是可能的。机器学习编译器把神经网络图下沉到硬件的潮流里,这条铁律再一次显灵:新一代加速器厂商要做的第一件事,不是造芯片,而是给自己的芯片写一层 IR 支持——三十年前那份毕业论文设定的接口,如今是每一颗新芯片的出厂必答题。而它与安腾的对照,还藏着一层更深的对称:硬件乱序执行与编译器静态调度,本是对同一个问题——“指令之间谁先谁后”——的两种解法,前者把答案交给运行时的电路,后者把答案交给编译期的算法。主流芯片选了前者,用晶体管买灵活性;安腾选了后者,用假设换简洁;结果证明,当程序的行为越过编译期的视野边界时,电路的冗余反而是诚实的设计,假设的省略则成了隐蔽的负债。同一道题的两解,一个成了行业标准,一个成了案例栏——分出胜负的不是智力,是对“哪些信息在何时可得”这个前提的判断。从艾伦的第一张控制流图,到 SSA 的一个 φ 函数,再到 LLVM 的一份中间代码,编译器七十年的全部努力指向同一个朴素的信念:程序是数学对象,它的每一次执行都应当可以被推理。这个信念造就了现代软件的一切性能,也埋下了它最深的盲区——它永远无法推理自己看不见的那部分运行时。LLVM 的解耦与安腾的崩塌,不过是这个信念的一体两面:解耦是把确定的部分标准化,崩塌是把不确定的部分赌没了。此后每一个新的编译器项目——从面向机器学习的多层中间表示,到为特定芯片定制的代码生成器——都在重复同一个动作:重新划一条编译期与运行时的线,然后在两条路线之间重新下注。线划在哪里,是编译器研究最古老的问题,也将是最年轻的问题。编译器把人类的意图翻译成机器的约束,而两者之间的裂缝,由每一代编译器研究者用新的中间表示去填补:填补得了的成为标准,填补不了的成为坟碑,安腾是后者,LLVM 是前者,而下一层裂缝,已经在等待它的下一份答案——机器学习时代的新编译器,正在为“算子图”到张量加速器之间的那条缝重新画图。编译器研究的全部历史,就是这道填缝工程的两百年支线:从巴克斯团队用汇编手写第一版 Fortran,到艾伦把优化画成图,到 Cytron 把变量改成单赋值,再到拉特纳把整座编译器拆成三段——每一步都在把“机器能自己理解的东西”的边界向外推一格,每一步也都重新划定了机器永远无法理解的那条边。


「计算机百年史」系列第 3 篇(共 10 篇)。全系列统一标签:计算机百年史。