在1951年如何编程 – 以 EDSAC 为例

❖EDSAC

EDSAC 是剑桥大学数学实验室设计并建造的计算机。1949年，项目组成功地用 EDSAC 生成并打印了平方数表1，象征着 EDSAC 正式投入使用。

EDSAC的基本计算模型与现代计算机已经非常相似，可以概括为：

  1. 具有 32 个箱（Tank），每个箱存储 32 个字（Word），注意这里的字是 18 个比特，而非 x86 平台上的 16 个比特。这 32 个箱类似于现代计算机的内存（下文用“内存”来称呼这32个箱）。
  2. 具有 5 个寄存器，其中两个寄存器（指令寄存器、指令地址寄存器）用来控制，三个寄存器用来计算。
  3. 计算被表现为顺序地执行指令（Order），每条指令占 1 个字，其中有一位不使用，所以每条指令占 17 个比特。所有的指令与数据都放在之前所说的内存中（事实上，在 EDSAC 的设计中，指令与数据没有区别）。每条指令可能读或写寄存器或内存。
  4. EDSAC 的输入设备是五点式打孔纸带，这种纸带同时也承担了输入程序（具体是什么意思下文会解释）的作用。EDSAC 的输出设备是电传式打印机。它还配备了一个电话，这个电话可以用来进行“人机交互”，在 EDSAC 上实现的世界上的第一个电子游戏–井字棋（有争议）就是通过电话来进行交互的。

❖EDSAC的程序

前文已经说过，在 EDSAC 的设计中，计算就是“顺序地执行指令”，那么这些指令是存储在哪里的呢？和当今的计算机一样，这些指令是存储在“内存”中的。但，内存中的程序又是从何而来的呢？

答案是，内存中的程序是通过纸带读入的。EDSAC 所采用的纸带，是“五点式纸带”，大概长这样：

纸带的每个单元都有 5 个孔，如果被打孔，代表 1，没被打孔代表 0. 所以，理论上来说，我们可以把纸带看作一个列表，列表的每个元素都是 0-31 的自然数。

纸带表示的不是机器码（18位的指令），而是“文本程序”的直接编码。在 EDSAC 的年代，程序员首先需要把文本形式的程序写在纸上，再通过 keypunch（打孔机）把文本形式的程序打在纸带上。

那么，文本形式的程序又是什么样的呢？这种程序类似于今天的汇编语言程序，一个输出“HI”的程序如下：

1T64K
2GK
3ZF
4O5θ
5O6θ
6O7θ
7ZF
8*F
9HF
10IF
11EZ
12PF

这都什么乱七八糟的？确实，这种形式的程序仍然十分难以阅读。我们一点一点来看。

首先，这个程序的每一行都代表三种情况之一：

  1. 指令
  2. 伪指令
  3. 数据

伪指令类似于今天汇编语言中的伪指令，它是给初始化指令提供必要信息的。初始化指令（initial orders）是我们下面要讨论的重点，暂时可以把它理解为一种汇编器。

我们把上面的程序稍加注释：

1T64K        伪指令，含义是把当前的程序加载到第 64 个字（第 2 个箱的第 0 个字）
2GK          伪指令，设置重定位参数（θ参数）为当前位置（下一行，此处为ZF的位置）
3--------------------------------------------------------------
4ZF          停机                                            }            
5O5θ         设置打印机的偏移方式为“字母偏移”（Letter shift）     }     
6O6θ         让打印机打印位置6的最高5位代表的字母（H）             }
7O7θ         让打印机打印位置6的最高5位代表的字母（I）             }      这些行被实际加载到内存中
8ZF          停机                                            }
9*F          O5θ指令索引的数据                                 }
10HF          O6θ指令索引的数据                                 }
11IF          O7θ指令索引的数据                                 }   
12--------------------------------------------------------------
13EZ          伪指令，EZ PF这两个同时使用的时候的作用是告诉初始化指令将当前要执行的指令设置为θ参数的位置
14PF          同上

可见，想要理解这个程序，我们就必须理解纸带与 EDSAC 的关系，以及初始化指令到底是做什么的。

❖初始化指令

初始化指令是 EDSAC 系统中最核心的一段代码，一个程序，以今天的眼光去看，它可以说是 EDSAC 的操作系统、一个可重定位的汇编器与加载器。初始化指令有两个版本，分别叫做初始化指令 1 与初始化指令 2。由于上面介绍的文字形式程序是由初始化指令读取的，所以不同的初始化指令读取的文字形式程序也是不一样的。

为了理解初始化指令，我们最好站在初始化指令的角度去观察纸带上的程序究竟是什么样的。首先，纸带上的程序是文字形式程序的直接转译，纸带上的每个单元都对应着一个字母或者数字。例如说，T64K这一行在纸带上就会产生四个与之对应的单元。这么看来，初始化指令拿到的程序就是文字形式程序在纸带上的编码。初始化指令需要自己将它翻译为 18 个比特的指令，并加载到内存中。

初始化指令通过以I开头的指令读取纸带上的数。例如说：

1I2S

就代表把纸带头的数据读到位置 2 的最低 5 位。（S的含义下面会解释）

这样一来我们立刻会产生一个疑问，英文字母有 26 个，加上 10 个数字，还有 4 个希腊字母（θ ϕ Δ π），要给这每一个符号都唯一编码，起码需要 40 个数，难道五点式纸带（最多 32 个数）不会出现不够用的情况吗？

事实上，打孔器在打孔的时候，P 和 0，Q 和 1，W 和 2，E 和 3，一直到 O 和 9，都打相同的孔：

这难道不会出问题吗？站在初始化指令的角度上，我如何区分读入的一个数是P还是0呢？

答案是，初始化指令并不需要区分。文字形式程序的每一行都是有特定格式的，用形式文法表示一下就是：

Order→Pre N∗ Post \mathsf{Order} \rightarrow \mathsf{Pre}\ \mathsf{N}^*\ \mathsf{Post}

其中：

  • Pre\mathsf{Pre} 代表的是指令的类型，比如I就是从纸带读入，O就是从打印机输出。
  • N∗\mathsf{N}^* 代表多个（可以没有，没有的话这一块就是0）0-9 的整数，代表地址。
  • Post\mathsf{Post} 则是每条指令的后缀，在初始化指令1的设计中，它用来区分短指令和长指令，S为短指令，L为长指令；在初始化指令2的设计中，F代表短指令，D代表长指令，θ代表这条指令的地址要加上θ参数。

这三个部分，实际上对应着真正机器码的 18 个比特的划分：

稍加思考，我们会发现，只要保证Post\mathsf{Post}和N\mathsf{N}不会有相同的编码，那就不会产生歧义。而这是非常容易满足的。

❖函数调用？

1951年的计算机，竟然已经具有函数调用的能力，这无疑是非常令人惊讶的。让人稍感心安的是，这种函数调用不能进行嵌套。

函数调用这种复杂的特性是如何在 EDSAC 上实现的呢？其实，使用初始化指令 1 的程序是不能进行函数调用的，而初始化指令 2 的出现主要就是为了解决这个问题。

初始化指令2 究竟用了什么魔法呢？让我们回忆一下之前说的 θ 参数。如果一条指令以 θ 结尾，那么它的地址在翻译时就要加上 θ 参数当前的值。这个机制，今天叫做“重定位”技术。这使得每一个程序都具有了相对独立性，每个程序都可以引用相对地址而非绝对地址，这样一来，简单地进行复制即可实现函数调用。

具体来说，EDSAC 有一套标准库，每当程序员想用某个库函数的时候，他会在在文字形式的程序里注记一下。而操作打孔器的操作员打到这个位置时，他会用纸带复制器把库函数复制到这条纸带的对应位置2：

❖自举？

天下有信数三：一曰智有所有不能立，二曰力有所不能举，三曰强有所有不能胜。故虽有尧之智而无众人之助，大功不立；有乌获之劲而不得人助，不能自举；有贲、育之强而无法术，不得长胜。故势有不可得，事有不可成。故乌获轻千钧而重其身，非其重于千钧也，势不便也。离硃易百步而难眉睫，非百步近而眉睫远也，道不可也。故明主不穷乌获以其不能自举，不困离硃以其不能自见。因可势，求易道，故用力寡而功名立。时有满虚，事有利害，物有生死，人主为三者发喜怒之色，则金石之士离心焉。圣贤之朴深矣。古明主观人，不使人观己。明于尧不能独成，乌获之不能自举，贲育之不能自胜，以法术则观行之道毕矣。

乌获是一个大力士，大力士能举起很多东西，那么，他能不能举起他自己呢？

根据直觉，这当然是不行的。形式化一下，我们可以说，举起关系是反自反的。

编译器的“自举”正是来源于这个典故。假设 L 语言的编译器 A 是由 L 语言写成的，那么用 A 编译 A 就是“自举”。

初始化指令同样有“自举”的问题。没有初始化指令，纸带上的程序根本没法被执行，但目前为止，我们介绍的程序输入方法只有一种：从纸带输入。没有初始化指令，就没法读纸带；没法读纸带，就没法将初始化指令输入 EDSAC.

如何解决这个问题呢？论文3提到：

These orders are known as the initial orders and are permanently wired on a set of uniselectors. When the starting button is pressed, these orders are automatically transferred to the store and they then cause the input tape to be read.

可见，初始化指令是通过一组叫做 uniselectors 的设备直接写入 EDSAC 的内存的。这个 uniselectors 又叫步进开关（stepping switch），由于作者缺乏电子相关知识，暂时没法给出完整的介绍。

❖一个小问题

看到这里，读者觉得如此伟大的初始化指令2到底会有多少行，或者说多少条指令呢？不妨自己估计一下，然后查阅一下相关资料，你也许会感到非常惊讶的。