编程珠玑番外篇-D. 高级语言怎么来的-1
终于放暑假了, 有心情来八卦了. 我主要想八卦一下高级语言的设计思想和各种范式的来龙去脉, 也就是回答这个问题: 编程语言为什么会发生成现在这个样子哩? 这里面的奥妙又在哪里哩? 我尝试着把这个系列的八卦写下去, 包括虚拟机的设计, 线程的设计, 栈和寄存器两大流派的来龙去脉等等, 也算是完成年初给大家许下的诺言.
高级编程语言的创始纪上写道:”初, 世间无语言, 仅电路与连线. 及大牛出, 天地开, 始有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. 可见, 高爷爷的人脑编译器, 也不是男人编译器…
各位欲知详情的, 猛点这个.
SoM said,
May 13, 2009 @ 8:30 pm
受益匪浅！
wind said,
May 13, 2009 @ 8:41 pm
科学发展史就是牛人的历史啊。
多谢徐宥的介绍。
辛苦了。
easing said,
May 13, 2009 @ 8:43 pm
原来解释器的来由是这样的，以前看SICP实现过一个scheme的解释器，但就是不知道它怎么想到要这么搞，现在终于知道鸟，多谢了，真长见识。
free1879 said,
May 13, 2009 @ 9:08 pm
八卦才是王道
Dr. Kai said,
May 13, 2009 @ 9:13 pm
Eric老大又开工了，等着看续集。
Jan said,
May 14, 2009 @ 2:54 am
好多八卦 :) 抬两扛:
“… 递归就是lambda 演算的灵魂” 感觉没道理， 递归并不是lambda演算直接支持的东西，算不上灵魂吧
“… 对空间分配的动态支持, 随之就带来了一项新技术: 垃圾收集器” 这句话感觉跳跃有点儿大。动态分配空间并不一定要GC支持，还可以像C一样free()，计算中大量中间数据的生成似乎才是导致GC的直接理由？
LM said,
May 14, 2009 @ 6:24 am
栈本质上说来不是CPU的特性，而是语言的特性，所以stack pointer不是必须在CPU中实现的，理论上编译器随便找一个寄存器当栈顶就OK了，当然software convention要保证大家都用同一个寄存器，这样的话才能互相调用。
Jiang said,
May 14, 2009 @ 8:09 am
LISP我不懂，不过看它的历史，倒是知道了SAS中为什么会有%eval(.)，拣得一条好东西。
胡言乱语 said,
May 15, 2009 @ 6:53 am
博主还是整这个好，其他的politic甭管了，省得口水
菜鸟 said,
May 15, 2009 @ 8:12 am
不错。写的像科普读物似的，很生动。
Eric said,
May 15, 2009 @ 4:47 pm
好心的评论者”胡言乱语”:
写什么是我的自由.
瘦肉丝 said,
May 15, 2009 @ 7:27 pm
90年代后期是CGI, 接着来了php， 紧接着又来了asp, 饭还没凉又来了jsp
90末年微软不让玩java了，升级了asp 去 asp+，最后就直接dotnet呢。
00出java阵营出了EJB.
再往后Java阵营打出J2EE的底牌。 各种framework接种而来， 什么Struts, webwork呀
。 都TMD开源。 最后大家发现J2EE不好玩，尤其是EJB。 于是又搞了轻量级的
framework. POJO ,IOC, Dependency Inject, SpringFramework应运而生。
再往后大家发现Java根本就不好用，于是RubyOnRail来了，傻瓜也能做网站了。 做一
个blog 15分钟，做一个twitter 15分钟。傻逼了吧，原来软件可以这么简单。 当你还
在一行一行的码C代码的时候，RoR的程序员已经去和前台小蜜搭讪去了。
预测一下，未来的几年，大家发现计算机语言根本就是扯淡，直接跟计算机讲英文就行
了, 微软为什么每年招这么多能忽悠的，现在忽悠人，以后忽悠计算机。 现在表达能
力不行的，赶快练习怎么忽悠吧。 要么再过10年只能做legacy system维护了。 那些
能忽悠的老印，都去做senior忽悠员去了。
//———————————
徐：评论一下这段话吧。^_^
瘦肉丝 said,
May 15, 2009 @ 7:31 pm
标 题: Re: 90年代到底发生了什么
发信站: BBS 未名空间站 (Fri May 15 02:28:30 2009)
90年代后期是CGI, 接着来了php， 紧接着又来了asp, 饭还没凉又来了jsp
90末年微软不让玩java了，升级了asp 去 asp+，最后就直接dotnet呢。
00出java阵营出了EJB.
再往后Java阵营打出J2EE的底牌。 各种framework接种而来， 什么Struts, webwork呀
。 都TMD开源。 最后大家发现J2EE不好玩，尤其是EJB。 于是又搞了轻量级的
framework. POJO ,IOC, Dependency Inject, SpringFramework应运而生。
再往后大家发现Java根本就不好用，于是RubyOnRail来了，傻瓜也能做网站了。 做一
个blog 15分钟，做一个twitter 15分钟。傻逼了吧，原来软件可以这么简单。 当你还
在一行一行的码C代码的时候，RoR的程序员已经去和前台小蜜搭讪去了。
预测一下，未来的几年，大家发现计算机语言根本就是扯淡，直接跟计算机讲英文就行
了, 微软为什么每年招这么多能忽悠的，现在忽悠人，以后忽悠计算机。 现在表达能
力不行的，赶快练习怎么忽悠吧。 要么再过10年只能做legacy system维护了。 那些
能忽悠的老印，都去做senior忽悠员去了。
/////////////////////////////////
博主评论一下吧 ^_^
瘦肉丝 said,
May 15, 2009 @ 7:32 pm
标 题: Re: 90年代到底发生了什么
发信站: BBS 未名空间站 (Fri May 15 02:28:30 2009)
90年代后期是CGI, 接着来了php， 紧接着又来了asp, 饭还没凉又来了jsp
90末年微软不让玩java了，升级了asp 去 asp+，最后就直接dotnet呢。
00出java阵营出了EJB.
再往后Java阵营打出J2EE的底牌。 各种framework接种而来， 什么Struts, webwork呀
。 都TMD开源。 最后大家发现J2EE不好玩，尤其是EJB。 于是又搞了轻量级的
framework. POJO ,IOC, Dependency Inject, SpringFramework应运而生。
再往后大家发现Java根本就不好用，于是RubyOnRail来了，傻瓜也能做网站了。 做一
个blog 15分钟，做一个twitter 15分钟。傻逼了吧，原来软件可以这么简单。 当你还
在一行一行的码C代码的时候，RoR的程序员已经去和前台小蜜搭讪去了。
预测一下，未来的几年，大家发现计算机语言根本就是扯淡，直接跟计算机讲英文就行
了, 微软为什么每年招这么多能忽悠的，现在忽悠人，以后忽悠计算机。 现在表达能
力不行的，赶快练习怎么忽悠吧。 要么再过10年只能做legacy system维护了。 那些
能忽悠的老印，都去做senior忽悠员去了。
http://www.mitbbs.com/article_t1/Seattle/31521829_0_2.html
///////////////////////////////
博主评论一下？ ^_^
蜡笔公子 said,
May 16, 2009 @ 3:45 am
不知道为什么，http://blog.youxu.info/网址已经不能进了，我通过翻墙的方法才来的。如果直接进http://blog.youxu.info/就会自动进入“域名纠错系统”，难道这里也被和谐了？不应该吧，你又没做什么……
easing said,
May 16, 2009 @ 7:16 am
其实我很想知道计算机发展的最早期的一些故事，从图灵的理论研究到冯诺依曼的存储程序体系结构的出现以及它们之间的联系，中间应该有很多有意思的事儿，主要是我想知道很多东西出现的源动力是什么，不知道eric大大是否可以八卦八卦？
Eric said,
May 16, 2009 @ 11:08 am
easing 老师:
我的八卦也是看书看来的, 你说的那部分历史, 我还真不熟, 八卦不起来啊. 要不你给我举几个例子, 说不定有的我知道. 因为我看过图灵和冯诺依曼早期的不少论文.
瘦肉丝老师:
未来如何很难说的. 你转的那篇文章中很多描述都是戏说而已, 其实真实情况未必这么轻描淡写, 不同的系统有不同的语言选择.
aw said,
May 16, 2009 @ 10:10 pm
徐宥老师不回国了？难道现在回国的人都要盘查嘛？
easing said,
May 17, 2009 @ 8:00 am
Eric 老师：
我也是看书才有疑惑的，wikipedia上说的也比较简短，看过来看过去就《逻辑的引擎》这本书八卦多一点，其它的都直接给结果的。
另外想问一个问题，可能比较弱啊，就是算法定义的一个精确模型是图灵机，那为什么现在的高级语言用上下文无关文法就可以描述算法，它不是只对应于非确定下推自动机吗？抑或是我把语法和语义搞混了？如果按乔姆斯基对文法的分类来说，描述一个算法最少需要几级语言，还是它只是取决于怎么去解释？
我是最近刚看计算理论这方面的内容，很多疑惑啊，不知道哪里可以问，如果打扰到您，还请见谅。
Eric said,
May 17, 2009 @ 1:53 pm
@easing:
描述一个图灵机的语言, 和图灵机能够处理的语言, 不是一回事.
上下文无关文法(CFG) 就可以描述计算机编程语言, 是因为这样计算机编程语言能够被编译器高效的转换成机器码. 事实上我们现在用的计算机编程语言, 大多只是 CFG 的子集, 叫做 LALR(k). 编译原理上都有讲.
描述一个算法, 和这个算法接受的语言, 是不一样的两件事情. 可注意, 一个叫做 e(M), 一个叫做 L(M), 前者 e(M) 是关于这个图灵机的编码, 后者 L(M) 是这个图灵机 M 可判定的语言的集合. 当然, 这两个之间如果巧妙的把 e(M) 扔给 M, 问是不是 L(M), 那就是著名的 SA 问题了. SA 略改一下就是著名的停机问题了. 你可以从看停机问题入手, 就更加清楚了.
easing said,
May 17, 2009 @ 3:18 pm
Eric 老师:
谢谢了，那个SA问题我是知道的，Sipser的那本《计算理论导引》上就把它叫做停机问题，想这个问题的时候，我也意识到了有可能是我把描述或者说编码图灵机和图灵机的语言给搞混了，但我也想不通编码一个图灵机为什么只需要CFG就够了，当时我还在想用正则是不是也可以，后来想要是可以别人早就弄出来了,我觉得这个应该取决于通用图灵机的性质。
再次谢谢你的回答。
瘦肉丝 said,
May 18, 2009 @ 1:33 pm
谢谢
为什么前2次贴的当时看不到？现在又都出来了。
tdus said,
May 19, 2009 @ 9:25 pm
哈哈，跟看货币战争一个感觉啊，很贯通~
Nicholas Yuen said,
June 16, 2009 @ 2:06 am
拜读。感谢！
pligg.com said,
July 7, 2009 @ 10:21 am
» 编程珠玑番外篇-D. 高级语言怎么来的-1 | 4G spaces…
编程珠玑番外篇，这人还是有两把刷子的。…