高级语言怎么来的（一）：一切从递归开始
终于放暑假了，有心情来八卦了。我主要想八卦一下高级语言的设计思想和各种范式的来龙去脉，也就是回答这个问题：编程语言为什么会演变成现在这个样子呢？这里面的奥妙又在哪里呢？我尝试着把这个系列的八卦写下去，包括虚拟机的设计，线程的设计，栈和寄存器两大流派的来龙去脉等等，也算是完成年初给大家许下的诺言。
高级编程语言的创始纪上写道：“初，世间无语言，仅电路与连线。及大牛出，天地开，始有 FORTRAN，LISP。ALGOL 随之，乃有万种语：” 我们都知道，LISP 是基于递归函数的，FORTRAN 是做科学计算的。现在的 C 等等，都比较像 FORTRAN 不像 LISP。可是很少有人知道，最初，FORTRAN 是不支持函数递归调用的，而 LISP 是一生下来就支持的，所有高级语言里面的递归调用，都是逐渐从 LISP 那里学来的。这段尘封的历史非常有趣，值得八卦一番。
一般人学编程，除了写 Hello World 之外，人生写的第二个程序，不是阶乘就是菲波拉契数列，要不就是汉洛塔。而这几个程序，基本上都是因为函数的递归调用才显得简单漂亮。没有递归的日子里，人民非常想念您。可是，第一版的 FORTRAN 就居然不支持递归。细心的读者要问了，不支持递归的语言能图灵完全么？当然可以，图灵机就是没递归的典型的例子。但是没递归调用的程序会很难写，尤其像汉诺塔这种。那么，FORTRAN 他怎么就悍然不支持递归呢，让我们回到 1960 年。
话说当年，IBM 是计算机行业的领军者。那时候的计算机，都是比柜子还大的大家伙，至于计算能力嘛，却比你的手机还弱。那时候计算机所做的最多的事情，不是发邮件打游戏，而是做计算。做计算嘛，自然需要一种和数学语言比较接近的编程语言。于是，1960年，IBM 就捣鼓出了 FORTRAN，用行话说，就是公式翻译系统。这个公式翻译系统，就成了世界上第一个编程语言。这个编程语言能做数学计算，能做条件判断，能 GOTO。用现在的眼光看，这个语言能构模拟图灵机上的一切操作，所以是图灵完全的。学过数值计算的同学都知道，科学计算无非就是一大堆数学计算按照步骤进行而已。所以，一些控制判断语句， 数学公式加上一个数组，基本上就能完成所有的科学计算了。IBM 觉得这个语言够用了，就发布了 FORTRAN 语言规范，并且在自家的大型机上实现了这个语言。
在实现这个语言的时候，IBM 的工程师要写一个 FORTRAN 编译器 (请注意那时候的大型机没有操作系统)。那时候的编译器都是用机器语言或者很低级的汇编语言写成的，所以编译器要越简单越好。这些工程师觉得，弄一个让用户运行时动态开辟内存的机制太麻烦了，所以干脆，强迫用户在写程序的时候，就要定好数组的大小，变量的类型和数目。这个要求并不过分，因为在科学计算中，数组的维度，用到的变量等，在计算之前，就是可以知道大小的。用现在的话说，就是不能动态开辟内存空间，也就相当于没有 malloc 的 C，或者没有 new 的 C++。这样的好处是，一个程序要多少内存，编译的时候就知道的一清二楚了。这个主意看上去很聪明，不过 IBM 的工程师比你想得更加聪明，他们想，既然一个程序或者子程序要多少内存在编译的时候都知道了，我们干脆就静态的把每个子程序在内存中的位置，子程序中参数，返回值和局部变量放的位置，大小都定好, 不就更加整齐高效么。是的，我们都知道，在没有操作系统管理的情况下，程序的内存策略越简单越好，如果内存放的整整齐齐的，计算机的管理员就能够很好的管理机器的内存，这样也是一件非常好的事情。（再次强调，当年还没有操作系统呢，操作系统要等到 1964 年发布的 IBM 360 才有，具体开发一个操作系统之难度可参考《人月神话》）。
可是，聪明的读者一下子就看出来了，这样静态的搞内存分配，就递不成归不了了。为啥呢。试想，我有个 Fib 函数，用来计算第 N 个菲波拉契数。这个函数输入一个整数，返回一个整数，FORTRAN 编译器帮我把这个函数给静态分配了。好，我运行 Fib(5) 起来，FORTRAN 帮我把 5 存在某个专门给输入参数的位置。我在 Fib(5) 里面递归的调用了Fib(4)，FORTRAN 一看，哈，不还是 Fib 么，参数是 4，我存。这一存，新的参数 4，就把原来的 5 给覆盖掉了，新的返回值，也把原来的返回值给覆盖掉了。大事不好了，这么一搞，新的调用的状态居然覆盖了老的调用，这下，就没法返回原来的 Fib(5) 了，这样一搞，怎么递归啊？
IBM 这些写编译器的老前辈们，不是不知道这个问题，而是压根就鄙视提出这个问题的人：你丫科学计算递归什么呀，通通给我展开成循环，展不开是你数学没学好，想用递归，你就不要用 FORTRAN 了。那时候 IBM 乃是老大, 只有他们家才生产大型机，老大发话，下面的消费者只能听他的。
既然软件不支持，硬件也就可以偷工减料嘛，所以，硬件上，就压根没有任何栈支持。我们都知道，计算机发展史上，软件和硬件是相互作用的。我们现在也很难猜测，是 IBM 的软件工程师因为 IBM 的硬件工程师没有在硬件上设计出堆栈所以没有能在 FORTRAN 里面设计出递归调用呢，还是 IBM 的硬件工程师觉得既然软件没要求，我就不设计了呢？不管怎么样，我们看到的是，1960 年前，所有的机器的硬件都没有直接支持栈的机制。熟悉 CPU 的都知道，现代 CPU 里面，都有两个至关重要的地址寄存器，一个叫做 PC， 用来标记下一条要执行的指令的位置，还有一个就是栈顶指针 SP。如果没有后者，程序之间的调用就会非常麻烦，因为需要程序员手工维护一个栈，才能保证程序之间调用最后还能正确的返回。而当年，因为 FORTRAN 压根就不支持递归，所以支持 FORTRAN 的硬件，就省去了栈指针了。如果一个程序员想要递归调用，唯一的实现方法，就是让程序员借用一个通用寄存器作为栈指针，自己硬写一个栈，而且不能用 FORTRAN。
因为 FORTRAN 不支持递归调用，按照自然规律，自然会有支持递归的语言在同时代出现。于是，很快的， LISP 和 ALGOL 这两个新语言就出道了。我们只说 LISP。它的创始人 John McCarchy 是 MIT 教授, 也是人工智能之父，是学院派人物。他喜欢丘齐的那一套 Lambda 演算，而非图灵的机械构造。所以， LISP 从一开始，就支持递归的调用，因为递归就是 lambda 演算的灵魂。但是有两大问题摆在 McCarchy 面前。一是他的 LISP 理论模型找不到一个可以跑的机器，二是他的 LISP 模型中有一个叫做 eval 的指令，可以把一个字符串当成指令在运行时求值，而这个，当时还没有人解决过。按照 Paul Graham 大叔在他的 Hackers and Painters 里面的说法，McCarchy 甚至压根就不想实现这个 eval 指令，因为当 IBM 的一个叫 Steve Russell的工程师宣称要实现 eval 的时候，McCarthy 还连连摇手说理论是理论，实际是实际，我不指望这个能被实现。可是, Russell 居然就把这两个问题一并给解决了（这哥们也是电子游戏创始人，史上第一个电子游戏就是他写的，叫 Space War）。他的方法，说来也简单，就是写了一个解释器，让 LISP 在这个解释器里面跑。这个创举，让传统上编译 -> 运行的高级语言流程，变成了编写 -> 解释执行的流程，也就是著名的 REPL 流程。他做的事情，相当于在 IBM 的机器上用机器码写了一个通用图灵机，用来解释所有的 LISP 指令。这个创举，就让 LISP 从理论走到了实践。
因为有了运行时的概念，LISP 想怎么递归，就可以怎么递归，只要运行时支持一个软件实现的栈就可以了。上面我也说了，也就是写解释器的人麻烦一点而已，写 LISP 程序的人完全就可以不管下层怎么管理栈的了。同时，有了解释器，也解放了原来动态分配空间的麻烦，因为现在所有的空间分配都可以由解释器管理了，所以，运行时环境允许你动态的分配空间。对空间分配的动态支持，随之就带来了一项新技术：垃圾收集器。这个技术出现在 LISP 里面不是偶然的，是解释器的自然要求和归宿。在 FORTRAN 上本来被绕过的问题，就在 LISP 里面用全新的方法被解决了。LISP 的划时代意义和解释器技术，使得伴随的很多技术，比如抽象语法树，动态数据结构，垃圾收集，字节码等等，都很早的出现在了 LISP 中，加上 LISP 本身规则很少，使用起来非常灵活，所以，每当有一项新技术出现，特别是和解释器和运行时相关的一项新技术出现，我们就会听到有人说，“这玩意儿 LISP 里早就有了”，这话，是有一定道理的。
除了上面的软件模拟之外，MIT 还有一派在作硬件模拟，这一派，以后发展成了灿烂一时的 LISP machine，为日后所有虚拟机理论铺开了一条新路。这一派在 70，80 年代迅速崛起，然后随着 PC 的兴起又迅速的陨落，让人唏嘘不已。
最后附送一个八卦：1960 年的时候，高级语言编程领域也发生了一件大事，即 ALGOL 60 的提出。ALGOL 是划时代的标准，我们今天用的 C/Java 全是 ALGOL 家族的。ALGOL 注意到了 FORTRAN 的不支持递归的问题，于是从一开始，就订立标准支持递归。但是，处理递归需要很小心的安排每个函数每次调用的地址和所谓的活动窗口（Active Frame），而并不是每个编译器都是牛人写的，所以在处理递归这样一个新事物上，难免会出点小问题和小 BUG。这时候, 搞笑的高爷爷（Knuth）出场了，他提出了一个测试，叫做 “是男人就得负 67”。 （The man or boy test）。 恕我功底不深，不能给各位读者把这个男人测试的关窍讲清楚，但是，我知道，这个测试，乃是看 ALGOL 60 编译器有没有正确的实现递归和外部引用的。照高爷爷的说法，真的男人要能得到正确答案，不是男人的就得不到正确答案。当然，高爷爷当时自己也没有男人编译器，所以自己猜了一个 -121，后来, 真的男人编译器出来了，正确答案是 -67。可见, 高爷爷的人脑编译器，也不是男人编译器…
各位欲知详情的，猛点这个。