计算机与编程之初——神说要有计算机

序言：本篇主要讲述计算机与编程最开始的模样，计算机的发展、高级语言的发展，为后续的更多原理做铺垫。作为第一部分内容，本来是想简单的写成编程介绍，然后写着写着，扩展了很多历史和八卦,也解释了很多基本的概念，比如各类语言是什么意思，图灵完备是什么，高级编程语言是怎么出现的等等，是一个开始编程之旅很好的开始

计算机各个领域是一体的

在说编程之前，我想先讨论一下计算机。作为计算机行业的爱好者和践行者，我一直认为计算机内的各个领域是不分家的，这也是我这两天在和朋友讨论的一个问题。我在上学阶段的时候，老师认为我什么都接触，都懂一点，但每一个方向都没在精通，我也曾以为自己更适合做一个通才，而不是一个专家。

但近些时候，我渐渐觉得将计算机各个领域分离开来是一个错误的想法，当然我现在的想法以后可能还会变，毕竟万物都是变化的。起码我现在觉得，并且也希望自己对计算机各个领域都有所深入，有点像广度优先，但又混入了蝴蝶效应。我们经常说，希望在某方面有所建树，但无论是高耸入云的松柏，还是遮天蔽日的榕树，都有着四通八达的根系。所以，我认为计算机的各个领域是一体的，虽在不同方向有各自的长短利弊，但不可避免的它们的关系是非常紧密的。

那么现在，我们开始扎根吧。

一、计算机理论的发展

编程、编程思想与编程语言

小的时候，我是很顽皮的，各种上房揭瓦，但我还喜欢搭积木、走迷宫、做自己喜欢的手工艺品，在我现在理解说来，编程就像做这些小时候的游戏一样，将自己的想法，通过计算机编程实现出来，做成一个“手工艺品”。 那么对于编程思想，就是如何构造我的作品，有一些基本的原则，还有常用的套路，就像搭积木有着基本的镶嵌模型，还受到摩擦力、重力的影响。然后，如何将我的作品做的精妙、灵动就要看我是如何设计、如何构思的了。

而编程语言，就是我的工具了。十年磨一剑，说的一点都不夸张，当你对你的工具足够熟悉、足够了解，就能庖丁解牛。我一直想寻找一门语言，将其深入作为自己的本命法宝，但一来是时间原因、二来没有什么机会，也就耽搁到现在了。现在，我大概是有意向将golang琢磨透了，这份开发笔记就是开篇吧。

自从我接触计算机以来，林林总总也用过不少语言了，我这里列出了我用过的语言，还有自己的初始感受，以及在查询相应资料后的总结和反馈。

常见编程语言的介绍和比较

那么，问题来了

1、解释型、编译语言…语言类型的各种名词都是什么意思？

2、为什么解释型语言比编译语言的速度慢？

3、我们该选用哪种语言？

下面，我们来一一了解，并会普及一下编程语言发展的脉络。

1 编程语言诞生在计算机出现之前

这就像先有儿子后有老爹一样…?当然不是，这说明，编程语言最开始和计算机是没有关系的！但最终敌不过上天的缘分，‘编程语言’这个漂亮的小姐姐，在遇见了潜力股的‘计算机’后，两人一见钟情，二见倾心，三见生出了计算机编程语言。

记得那是1804年，我方的林则徐刚刚中举，俄国的楞次和德国的韦伯刚刚出生，大哲学家康德悄然逝世，而在大洋彼岸的法国——法兰西第一帝国成立了。法国有一座世界闻名的丝织之都——里昂，里昂的丝织工人很厉害，能用一种手工提花机，能织出绚丽的丝绸锦缎，但是，这种提花机使用起来很繁琐，难度堪比为整理一团被100个猫主子玩过的彩线团。

后来有一个小哥哥，叫雅卡尔，他发明出了一种提花机，利用预先打好孔的卡片来控制编织的样式，提高了提花机的速度，快了25倍。为此，法国皇帝拿破仑还奖励了雅卡尔，并且允许他收专利费。

然后时光转到了1836年，我们的计算机科学先驱、著名的英国数学家查尔斯·巴比奇制作了一台木齿铁轮计算机，用来计算数学题，利用的就是雅卡尔打孔片的原理。也就是说，所谓的编程，就是编织代数模型。

其实，我觉得中国的墨家机关术比提花机这些高级了很多，也比国外早诞生了不知多少年，为什么没有出现计算机，也没有出现编程语言；同样的，四大发明之一的‘烟花’，在外国发展出了武器….潜在的原因，我们可以知道，墨家被灭了，明朝的武器也很发达，后来各种原因改朝换代了，究其本质，跑题了。

巴比奇是计算机的鼻祖暂且不提，在遥远的美国，有一个大名鼎鼎(我才知道)的统计学家——赫尔曼·霍尔瑞斯利用打孔片的原理发明了一种特殊的机器，提供户口调查、处理数据，将要花费十年才能统计一次的人口普查，缩减为一年不到。（普查是很浪费时间和经历的，我曾经在一个经济园区帮着做第四次经济普查，那个园区对比中国来说，是小的不能再小了，前前后后却花了近半年的时间。）

霍尔瑞斯制表机

2 天才所在的时代——计算机科学理论的发展

接下来，我们要重磅出场一个理论———图灵机。

上面已经说了IBM这个时候已经有了最初的机器，但是没有编程语言，没有操作系统。接下来的历史就是世界大战了，而我们的计算机科学理论之父、人工智能之父——图灵，就在这个时候出生了。

1912年，图灵出生

1913-1921 第一次世界大战

1939-1945 第二次世界大战

图灵在剑桥读大学的时候，修了冯·诺依曼的课。诺依曼的课程中讲到了哥德尔不完备性定理的证明 和 尚未解决的判定性问题。

哥德尔不完备性定理

也就说，一定有那么一个公理系统，它是不完备的。

在当时, 逻辑学开始和数学勾搭了，出现了逻辑的数学化，然后诞生了数理逻辑科学。同一时期，数学界也发生了第三次数学危机——罗素悖论。

数学危机

3 可计算性理论——Computability Theory

说了这么多，你以为我跑题了吗？怎么可能，虽然经常跑题，但是这次没有跑哦！！！上述的这些逻辑与数学的思想和理论，是对可计算性理论的研究。

那么问题又来了，什么是可计算性理论？它是计算理论的一个分支，研究的是——在不同计算模型下，哪些算法问题能够被解决。就是精确区分哪些是有求解算法的的，哪些是没有的。因为这样就可以抽象为计算机上的函数了，映射为哪些函数是可以计算的，哪些是不可计算的，将算法与计算连接在一起。

可计算性理论的研究对象：

（1）判定问题

（2）可计算函数

（3）计算复杂性

为了讨论所有的问题是否有求解的算法，数学家和逻辑学家就从不同的角度提出了上面说的（还有很多没说的，炮灰在历史的洪流中的）对可计算性理论的认知，而图灵是这个问题的终结者。

在此之前，对于算法的理解就是有限的、机械的证明步骤，但一直没有精确定义算法的方法。在20世纪30年代（第一次世界大战之后，第二次世界大战之前），有两个人提出了定义方法：图灵、丘奇。鉴于此段的前后文，你应该也知道，图灵的更胜一筹，图灵提出来的图灵机模型更为直观、形象。

图灵曾经思考了三个问题，并将其在写他的论文《论可计算数及其判定性问题上的应用》中，表述如下图：

图灵思考的三个问题

根据这三个问题，就把计算机的边界确定下来了，也就是确定了计算机能做什么——有解的数学问题（想起被有解无解习题支配的恐惧），可以在有限步骤内完成。

图灵机就是图灵设计出来的这个执行计算步骤的机器——通用、有效、等价的机器，按照算法一步步做事，最后得到答案。（80多年来，所有的计算机，包括量子计算机，都是在图灵机爸爸的理论范畴内，感谢祖师爷赏饭）。

4 停机问题

我们已经说了，图灵机的一个核心问题：解答的步骤是否有限。这就要提到第三次数学危机——罗素悖论。

罗素悖论提出之前：集合论得到了几乎所有数学家们的认可，是绝对的严密。学过集合的童鞋们都有一个共同的认知——基本所有数学内容，都是建立在集合的基础上的。然而两年后，罗素出场打脸，carry全场，危机了整个数学体系的确定性和严密性。那么他提出了什么？

理发师悖论

在实际生活中，如果我们加一条规定，比如将自己排除在外，那么理发师悖论就迎刃而解了。我们通过修改规则可以解决实际问题，但对于严格的罗素悖论，这种数学问题，就不能修改问题的条件了。

这么轰动数学界的危机问题，映射在计算机上就是——停机问题。通俗的讲，停机问题就是判断一个程序是否会在有限时间内结束运行的问题。停机问题本质是一高阶逻辑的不自恰性和不完备性

停机问题的等价描述

那么，我们的祖师爷是如何解决这个问题的呢？

硬核内容：证明停机问题

（1）假设停机问题有解，即：存在过程H(P,I)，可以判断对于程序P，在输入I的情况下，是否可以停机。假设P在输入I的时候可停机，即：输入I，H输出“停机”；如果输出“死循环”，则导出矛盾。

（2）因为程序本身也是一种数据，因此，程序可以作为输入，即P=I

（3）所以，H可以判定P输入时候，P是否会停机，即H(P,P)

（4）定义一个过程U(P):

int H(procedure,input); //there are two return values: strop(0) or dead loop(1)int U(P){ //P is the procedure    if H(P,P) == 1 { //if P is dead loop, return stop        return 0    }else{        while(1){} //else, dead loop    }}

（5）H(P)的输出可能出现两种情况

H(U,U)输出停机 –》 U(U)进入死循环

H(U,U)输出死循环 –》U(U)

无论哪一种，U 与 H 输出的结果都是相反的，两者是矛盾的。

（6）所以，H不是总能给出正确答案，前述假设不成立 ==》不存在停机问题的方法

这样证实了哥德尔不完全性定理——从数学上证明了企图以技术方法一劳永逸地解决悖论问题是不可能的。

在图灵机上，停机问题是不可判定的。

停机问题的无解证明，说明：不存在所谓的可以判定一切程序的程序，因为程序本身是程序，停机问题是不可判定的。也就回答了计算机领域的三个基础问题：

（1）当计算机存储和计算能力无穷大的时候，能否解决任何问题？不能，也就是说今天的AI，人工智能无法完全替代人类，AI本身也是程序。

（2）所有语言在计算能力上等价：如果说一个确定的函数，我们可以根据参数，也就是数学当中的自变量，得到确定的值，这个函数就是可计算的。如果一个函数是可以计算的，我们就可以使用图灵机去编写程序计算它，只要满足图灵机的基本条件就可以。

现在所有的语言都是图灵完备的，也就说这个语言可以被用来模拟一台通用图灵机，因此，任何可以用C编程出来的同样也可以用Java，Python这样的语言编程出来，所以，所有语言在计算能力上等价。

（3）不存在一个完美的工具，可以检测出代码的所有错误，保证代码准确无误。

这是互联 和IT生产过程中常见的问题，在测试代码时，我们会使用编译器或是其他各种各样的工具，但是必须要人工辨认操作。虽然很多编译器做的很人性化，在编译过程中就检查了很多错误，比如对代码进行静态类型的检查，这样在运行时，就不会出现运行时的类型错误。如果是像python这种动态类型的，就是运行时检查了。

这也算是理论指导实践，我们通过对停机问题的认识，能解决实际应用当中遇到的问题。而反过来一想，我们是先有的停机理论，而后有的实际应用，不得不感叹图灵思维的强大，而这种思维，就是科研的惯用思维。大胆猜测，严谨求证，合理应用。

5 图灵机、图灵完备

图灵的基本思想：用机器来模拟人们用纸笔进行数学运算的工程。

纸笔进行运算的过程

图灵机模型

上面这张图，就是图灵机的模型？是的，它由四部分组成。

图灵机的四个组成部分

总结来说，图灵机处理信息的四部分：输入集合、输出集合、内部状态、固定的程序指令。

这样的一台装置就能模拟人类所能进行的任何计算过程。结合之前介绍的可计算性理论和停机问题，一切可计算机的问题，图灵机都能计算，所以满足这样要求的逻辑系统、装置或编程语言就叫图灵完备的——能够抽象成图灵机的系统或编程语言，就是图灵完备的。

6 人类是图灵机吗？AI

AI就是将人类抽象为图灵机。

输入集合：五官所看到、听到、闻到、品尝到、感觉到的

输出集合：一言一行

内部状态：任意一个神经细胞的状态组合

程序指令：大脑的实际运行规则

冯诺依曼写过一本书《量子力学的数学基础》，图灵研究此书的时候，意识到计算可以用确定性的机械运动表示，现如今CPU内部的电子运动也是等价于机械运动。

而人的思想、意识来自于量子力学的测不准原理（这不光是围观世界，同时也是这个宇宙本身的规律）。虽然你可能不知道what is the 测不准原理，但是从字面理解，它是不确定的，也就是说，计算机是确定性的、可判定的，而意识是不定的、可计算的。——所以，图灵已经考虑过了，计算机不会和人有一样的意识。

图灵在1950年写过一篇论文《计算机器与智能》，在这篇论文中，图灵测试一词被提出来：

图灵测试

这个测试有多难？目前我们所有的人工智能都没有完成这个测试。最近2018年3月份的谷歌I/O大会上演示的AI产品，据说“部分通过图灵测试”。这个部分到底有多少也未可知。

二、高级语言的发展

上面说了，图灵机是一种数学模型、计算理论模型。

为了能很好的介绍编程语言，我需要较为详细的了解编程语言的整个发展脉络，幸好有前辈大佬先行，我这里只是做了解释和总结，原图见参考资料的脉络图链接和发展历史，对于脉络图为了防止原站丢失，我也copy一份到本站，如果原链接失效，可以点击本站的链接。

以下内容，都是自己做的总结和归纳，如有不正确的地方，跪求大佬请指出

这里，我将编程语言的起源和发展分为两个主线—— Speedcoding 和 IPL。

1. Speedcoding——Fortran

在1946年，第一台计算机诞生。然而直到1953年，计算机一直缺少两个重要功能：浮点计算、数组下标寻址。

1.1 浮点计数

对于浮点计算，就是小数的计算，如何用计算机进行大范围高精度数的算术运算。

对于整数，二进制整数之间的乘法和加法是相对简单的，只要把加法和乘法这些基本操作用更加简单的逻辑或、逻辑与实现，在电子电路上也很好实现。第一台电子计算机——Eniac就支持整数的乘法加法。

对于浮点数，因为一个额外的小数点的引入，在任何时候，都需要注意小数点的对齐。如果用定点计数，则计数范围会受到限制，就不能表示非常大，或是非常小的数。

所以，浮点数一般是用科学计数法表示的，比如IEEE 754标准。科学计数法中，浮点数的加减法每次都要对齐小数点，乘除法为了保持精度，在设计算法上也有很多技巧。

总而言之，相比较于整数的运算和逻辑运算，浮点运算是一个非常复杂的事情，如果要在硬件上设计一个浮点运算，需要复杂的电路和大量的电子元器件，这对于早期的电子管计算机，是很少能做到这么大的集成度的（所以，第三代计算机就高集成了）。

举例：浮点除法Pentium上的浮点数除法，需要耗费39个时钟周期。   如果CPU是流水线设计，这种占用多个时钟周期的浮点运算会让整个流水线暂停，CPU吞吐量下降。为了解决这些问题，现代CPU工程师们发明了超标量、乱序执行、SIMD等多种方式，来克服流水线被浮点运算这种长周期指令堵塞的情况。

在当时，如果需要用浮点运算，有两种方法：软件模拟、额外增加浮点协处理器FPU。后来到了1989年，Intel出了80486芯片，将FPU和CPU融在一起刻蚀到一块硅片上，到此，浮点的处理器普及了，个人计算机也可以做多媒体了，比如音视频（音视频的压缩、转换和回放都是极度依赖于浮点运算的）。

但是，即使到今天，很多低端处理器也是不支持浮点运算的。比如Linux内核不支持浮点运算，它会破坏内核的可移植性。在内核模式下，为了保证内核操作的原子性，一般在内核从事关键任务的时候，所有中断是要被屏蔽的。如果内核支持浮点运算，那么整个系统的性能和实时响应能力会急剧下降。

正因为对于计算机来说，浮点运算是一个挑战性的操作，但又是做科学计算所需要的基本操作，所以浮点计算能力就成了计算机能力的一个测试标准。我们常常听说有一个世界上前 500 台最快的超级计算机列表，这里所谓的“快”的衡量标准，就是以每秒钟进行多少次浮点计算(FLOPS) 为准。按照 Top500.org, 即评选世界上前 500 台超级计算机的机构2009年6月的数据，世界上最快的计算机，部署在美国能源部位于新墨西哥的洛斯阿拉莫斯国家实验室(Los Alamos National Laboratory)，当年造出第一颗原子弹的实验室。这台超级计算机，浮点计算速度的峰值高达 1456 TFlops，主要用来模拟核试验。因为美国的所有核弹头，海军核动力航母中的反应堆以及核试验，都由能源部国家核安全署(NNSA) 管理，所以能源部一直在投资用超级计算机进行核试验。在1996年美国宣布不再进行大规模的物理核试验后的这么多年，美国能源部一直用超级计算机来做核试验，所以在 Top500 列表中，美国能源部拥有最多数量的超级计算机。

1.2 数组下标寻址

当时的计算机，是不支持数组索引的，比如a[2]，不能通过数组索引去访问相应的地址。因为当年的计算机内存只有一两千k，可行的操作只有直接寻址，就是在每条指令后面直接加一个物理地址是最简单、直接的方法，计算机也不需要复杂的地址解码电路。但这样设计非常笨拙，a[2]这样的操作就无法表示了。如果程序员想这样去做间接寻址，只能手工管理内存，然后程序员需要手动分配A的地址并记住，然后手工加上2，但如果出现跳转和判断，或是循环语句，就不能定好A[i]的位置了。那要怎么做呢？

10 * 10 矩阵的乘法：写死10的三次方，也就是1000行地址访问

当然大佬们不可能这么萌萌的写那么多次了。

（1）先取出A的地址，然后做一次加法，把结果，就是A[i]的地址，注射到一个读内存的Load指令后面（2）执行Load指令（3）读A[i]的时候，先看A的地址是600，然后看i是2，然后加一起变成602（4）把指令改为load602

为什么能这么做呢？这要感谢冯诺依曼了，他的体系设计中，数据和程序是混在一起的，所以程序员可以随时像修改数据一样修改要运行的下一条程序指令。

所有不兼容的问题，都由中间层来解决

既然浮点数和数组下标寻址都不给我解决，那我们就要自己想办法了，填补现实与梦想间的落差。所以，IBM的工程师John Backus开发出了一个中间层——SpeedCoding。这是一个运行在IBM 701计算机上的解释器，解释浮点计算和下标寻址的指令，翻译为相应的机器码，用软件的方式模拟浮点计算，自动修改地址。

SpeedCoding大大降低了总成本，但好景不长，划时代的704发不了，它支持了浮点计算和间接下标寻址，同样是机器码编写，但704要快很多，SpeedCoding就没有优势了。

1.3 Fortran创世纪

SpeedCoding失去了优势，它的发明人John Backus总结出要减少程序的开发成本，才能让大家用他的SpeedCoding。但如何从软件工具上入手？他总结出了两点：

程序员可以方便的写数学公式

这个系统最后能够解析/生成足够快的程序

只有这样，程序员才会使用高级工具，也就是现在的高级编程语言，而不是随着硬件的发展在机器码和如speedCoding这样的工具间来回跳跃。所以，他要实现一个比机器码高级的语言。于是，他给IBM写信，得到了IBM的人力物力支持后，在704发布的当年，项目启动。

计算机的最基本、最原始的需求就是计算了，数学是一种语言，那么计算机如果想要计算数学题，就要有一种能模仿数学语言的方式去做数学题。想一下平时我们如何解决一个比较简单的数学题的？我们有很多数学公式，在计算的时候，将具体的数字替换公式的字母，然后计算出结果。所以John Backus也顺着这个思路，让计算机去翻译公式，研究出了第一个编程语言——Fortran，也就是公式翻译系统。

和现在大多数编程语言不一样，FORTRAN 语言的设计的主要问题不是语法和功能，而是编译器怎么写才能高性能。这个高性能的编译器很难写，到 1957 年才写好，总共花了 IBM 216 个人月。等到 FORTRAN 一推出，不到一年的时间，在 IBM 总共售出的 60 台 704上，就部署了超过一半。

fortran  英  [?f??tr?n]   美  [?f??rtr?n]abbr. 公式翻译程式语言（formula translator）

Fortan可以做数学计算、条件判断、GOTO，是图灵完全的。IBM在经过一系列测试，确定这个语言可以用后，就发布了语言规范，并在自己生产的大型机上实现了这个语言。但是，当时的计算机没有操作系统，该如何让计算机去运行程序呢？IBM工程师们写了一个Fortran编译器。当时的编译器由机器语言写的，这就有了一个比较棘手的问题——如何动态开辟内存？为了避免这个麻烦，所以就强迫用户在写程序的时候，定好数组的大小、变量的类型和数目（这些在科学计算中，计算前都是可以知道的）。这样一来，一个程序需要多少内存，编译的时候就很清楚了。于是，IBM工程师们设计出了一种方式——静态地把每个子程序在内存中的位置、参数、返回值和局部变量放的位置、大小都定好，收拾的整整齐齐明明白白的，这样计算机的管理员就能很好的管理机器的内存。

但是这样设计在现在看来，有两个非常大的问题。

（1）不能递归。静态的内存分配，如果要做递归调用，新值就会覆盖旧值。

比如说：Fib 函数，用来计算第 N 个菲波拉契数。这个函数输入一个整数，返回一个整数，FORTRAN 编译器帮我把这个函数给静态分配了。好，我运行 Fib(5) 起来，FORTRAN 帮我把 5 存在某个专门给输入参数的位置。我在 Fib(5) 里面递归的调用了Fib(4)，FORTRAN 一看，哈，不还是 Fib 么，参数是 4，我存。这一存，新的参数4，就把原来的 5 给覆盖掉了，新的返回值，也把原来的返回值给覆盖掉了。

当然，在IBM的大佬佬们以及数学的角度看来，科学计算根本不需要递归，如有递归都展开成循环。于是Fortran不支持递归，这也是它饱受诟病的一点。

（2）另一方面，既然内存都静态分配了，硬件方面也就没有对栈进行支持。

现代CPU内有两个重要的地址寄存器：PC和SPPC：Program Counter，用于标记下一条要执行的执行的位置SP：Stack Pointer，栈顶指针，用于程序调用。（如果没有，程序员则需要手工维护一个栈才能保证程序之间调用返回正确的值）

这样一来，如果想实现递归，就需要程序员借用一个通用寄存器==》作为栈指针，自己硬写一个栈，而且不能用Fortran。

2 Lisp

2.1 递归和IF语句

上面说到的704是一个划时代的神奇机器，世界上最早的语音合成程序就是由Bell实验室的科学家在IBM704上完成的。但它很贵啊，百万美元级别的，不是一般的学校可以买的起的。但以IBM和大学的关系，直接捐给MIT一台704。

John McCarthy在Dartmouth教书，但大佬们都是一个圈子的，他和MIT的Marvin Minsky关系超好，于是他就可以使用这台百万级别的704了。Minsky当时有一个IBM的项目，内容是使用计算机证明平面几何问题，他们思考后想到的解决办法是开发一套支持符 计算的Fortran子系统，用一系列的子程序，来做逻辑推理和符 演绎。

他们把一个计算机工程问题，抽象为了一个数学问题——假设有一系列可以实现的子程序，只要在数学上证明通过子程序的组合，加上自动逻辑推理，就可以证明平面几何定理。

考虑到各种原因，McCarthy是打算用Fortran子程序做列表处理的简单系统，于是，他带着两个研究生将这个想法实现了，并命名为FLPL——Fortran列表处理语言。但做完后，McCarthy对这个成果并不满意，因为它有两个比较大的问题：

（1）递归：上面已经说了，Fortran是不支持递归的，没有递归，很多列表处理函数只能用循环实现。比如函数求导的链式法则，求导过程本身就是递归定义的，如果没有递归求导，就超级难写了。

（2）IF语句：有递归的地方就有if结束判断。

// 现在的if语句IF 条件 THEN    一些语句;ELSE    另一些语句;END IF// 早期的if语句IF (表达式) A B C

‘IF (表达式) A B C’ 表示：如果表达式的值小于零为A，等于零为B，大于零为C。这降低了程序的可读性，为此，McCarthy用XIF的程序完成if的功能：

XIF(条件, 表达式A, 表达式B)

但是，这是错误的语义。在高级语言中，函数参数的值，在进入函数之前是必须全部确定的，所以在这个XIF中，无论条件满足与否，我们都要计算出两个表达式的值。这是不满足IF语义的。

一个值得一提的例子是 C++ 逻辑运算符重载和短路表达式的不等价性。在 C 语言中，逻辑与 (&&) 和逻辑或( || ) 都隶属于短路表达式，也就是说，对于 A && B 这样的表达式，如果 A 已经确定为 false，就无需计算表达式 B 的值，即 B 的计算被”短路”。以 C 为蓝本的 C++ 一方便保留了这些短路表达式，另一方面在面向对象的特性中，引入了运算符重载。具体来说，只要一个对象定义了 operator&& 成员函数，就可以进行 && 运算。乍一看，这是一个很酷的特性，可以让程序员用 A&&B 这样的数学表达式表达复杂的逻辑关系。然而，仔细想想，  A.operator&&(B) 在语义上并不等价于 C 所定义的 A&&B，原因在于 A.operator&&() 是个函数，在求值之前需要先计算 B 的值，而后者是个短路表达式，本质上相当于：IF A:    return TrueELSE:    return B因为短路表达式不一定会对 B 求值，这两者从语义上就是不等价的。如果 B 不是一个简单的对象，而是一个复杂表达式的时候，对 B 求值可能有副作用，而这个副作用，是写 A && B 并把它当做短路表达式的程序员所没有预见的。按照 C++ Gotcha 的说法，这很容易造成潜在的程序 Bug。实际上，C++逻辑运算符重载是一个危险的特性，很多公司的编程标准都禁止使用逻辑运算符重载。

由于这两个问题，Fortran从本质上就不符合McCarthy的期望，以Fortran为宿主开发出的列表处理语言也不能达到想要的结果，于是我们的MIT教授、人工智能之父、学院派大佬John McCarthy创建了最适合人工智能的编程语言———Lisp，为什么这么说，我们下面来一一解释。

2.2 AI与Lisp

既然说到人工智能，我们就有必要提一提人工智能是怎么搞出来的了。二战之后，大批精英科学家从研究制造原子弹中退出，开始研究“智能机器”了，比如说：

维纳在 1948 年发表了《控制论》，副标题叫做 《动物和机器的控制和通信》，其中讲了生物和机器的反馈，讲了脑的行为。

创立信息论的大师香农在 1949 年提出了可以下棋的机器，也就是面向特定领域的智能机器。

同时，1949年，加拿大著名的神经科学家 Donald Hebb 发表了“行为的组织”，开创了神经 络的研究

图灵在 1950 年发表了著名的题为“计算的机器和智能”的文章，提出了著名的图灵测试。

如此多的学科被创立，如此多的学科创始人在关心智能机器，可见当时的确是这方面研究的黄金时期。二战结束十年后，也就是1956年，这些研究者隐隐的都感觉到他们研究的内容属于一个新的领域，所以建立个新招牌就理所当然了。John McCarthy 同学就趁着 1956 年的这个暑假，在 Dortmouth 大学（当年也是美国计算机科学发展的圣地之一，比如说，它是 BASIC 语言发源地）， 和香农、Minsky 等其他人（这帮人当年还都是年轻人），一起开了个会————达特茅斯会议，在会上提出了一个很酷的词，叫做 Artificial Intelligence，算是人工智能这个学科正式成立。（这里还有很多瓜，有机会再讲）

对于人工智能，有两个重要的问题要回答：

怎么表示这个世界

计算机怎么能基于这个世界的知识得到智能

简单来说就是表达的语言和表达的正确方法。由这两个问题，分出了两支派。

如何表示知识的问题。AI的输入数据非常多样化，没有固定的格式，所以为了用统一的数据格式表示多种多样的现实对象，就要设计一个强大、灵活的数据结构，这个结构就是——链表。AI更关注符 和逻辑的计算，比如下棋，这不是一个纯数字的计算问题，车马炮各有自己的规则，存储规则的单元大小也不一致，我们需要的能存储异构数据单元的模块，同时，这些规则和数据要能随时增加、修改、删除等，这样一来，数组存储就非常不合适了，所以用链表而不是数组。而后来，有些Lisp版本，比如Common Lisp还假如数组作为链表的补充，处理图像和矩阵。

科学家证明了列表能表示现实世界的问题，但是列表能够充分表示所有的AI问题吗？AI的所有问题都能通过列表实现吗？这两个问题一直都没有确定答案。在1976年，Lisp前身的两位大佬：Alan Newell和Herbert Simon写了一篇文章，讨论了这个猜想，他们概括了一种大家普遍接受的方式：一个物理符 系统对于一般智能行为，是既充分又必要的。

A physical symbol system has the necessary and sufficient means for general intelligence action

也就是说，AI必须依赖于某种符 演算系统，相反的，基于符 演算系统也能衍生出AI。这个猜想让当时几乎所有的研究者认为：假如我们制造出一个通用的基于符 演算的系统，我们就能用这个系统实现智能。而链表的强大， 表达一个符 演算系统是绰绰有余的，所以如何去构建这样的系统就是全部的问题了，最后的结果是——函数式编程。

Lisp是列表处理语言，如果列表处理对AI至关重要，那么在Fortran和Algol这些通用的编程语言中，写关于列表处理的函数不是更加方便吗？

说到原因，我们还要普及一下AI范式。

Paradigm范式库恩认为范式是指“特定的科学共同体从事某一类科学活动所必须遵循的公认的'模式'，它包括共有的世界观、基本理论、范例、方法、手段、标准等等与科学研究有关的所有东西。”在1960年之后是指在科学领域和知识论行文中的思维的方式。

早在McCarthy提出AI之前，冯诺依曼那一代人就开始研究什么是智能，以及如何实现智能。他们更偏向于研究大脑的内部工作原理，模拟其工作机理来实现智能。

对于这一派的研究者来说，他们相信大脑的结构和工作机理决定了智能，至于大脑是用脑细胞构成的，还是用电子电路模拟的，对于智能来说毫不重要。

这方面的著名工作就是冯·诺伊曼的《计算机和大脑》这篇论文。在这篇不算很学术的随笔里面，他分析了人的大脑有多少个神经元，计算机有多少个晶体管，通过这些定量的比较来解释计算机和人的大脑的差距。

当时和冯·诺伊曼齐名的另一个神童是开创控制论的维纳。他和冯·诺伊曼一样，兼通很多学科。和冯·诺伊曼一样，他职业是数学家，但是也精通如神经科学和脑科学等学科。

一个显然的例子就是在《控制论》这本书里面， 维纳对大脑和神经的分析比比皆是。这种对大脑和神经分析的传统，从 Cajal （对，就是写 Advice for a Young Investigator 的那个大神)）开始，一直延续到了后来 AI 中的联接主义（主要研究神经 络的一个人工智能学派）。

但是当时有很多局限：脑神经解剖学本身不成熟、医学影像技术不发达、电子学的发展和集成度不够…所以，他们对脑的研究不够深刻，也无法用电子电路模拟大脑生成智能，只能模拟一些简单的神经动力学行为。这也就造成他们的研究方向——联接主义学派，一直不是AI领域中的潮流方向，直到80年代后，BP算法的出现，联接主义才重放光芒，但这也是在lisp出现20年后了。

相比于连接主义当时的门可罗雀，AI研究的另一个学派——符 主义学派进行的如火如荼，符 主义学派源自图灵，图灵在人工智能领域做的研究也很多，比如广为人知的图灵测试。

如果一台机器能够与人类展开对话（通过电传设备）而不能被辨别出其机器身份，那么称这台机器具有智能。

在今天看来，即使通过了图灵测试，也未必是有“智能”的，但在 AI 发展的早期，因为图灵测试的拉动，联接主义的相对弱势和符 主义的繁盛，都把全世界的 AI 研究往一个方向拽，这个方向，很自然的，就是“符 处理”

所以也很自然的，什么语言能做符 处理？当然就是Lisp了。Lisp中统一表示程序和数据的方法叫S-Expression，把程序和数据都统一当做符 （可以认为lisp支持meta-programming）。所以，它能通过程序对程序进行处理、生成和修改，相比较下，lisp比其他语言更灵活，恰好满足了AI领域的符 处理，可以进行复杂系统建模，很多编程的方式在lisp里都能实现。（以后我讲SICP的时候，会更深刻）

但放在现在来看，lisp语言是最适合AI的，这个神话已经被打破了，比如AI搜索用C/C++/Java都可以，还可以用php，做机器学习的python，matlab，统计的R，数据挖掘的一大堆，还有各式各样的库。

2.3 Lisp的编写

继续回到Lisp，值得一提的是，在当时，McCarthy跳槽到MIT当助理教授，MIT的编程大佬很多，Steve Russell就是帮助McCarthy完成了Lisp的编写任务。

之前提到过在定义算法的时候，丘奇vs图灵的结果是图灵机更胜一筹，但丘奇提出的Lambda演算也不容小觑，John McCarthy就非常喜欢，而Lambda演算的灵魂就是递归了，所以Lisp从一开始就支持递归的调用。当然，这也产生两个大问题：

（1）他的Lisp理论模型找不到一个可以跑的机器

（2）lisp模型中的eval指令无法解决（eval：可以把一个字符串当成指令在运行时求值）

就连McCarthy也不认为这两个问题可以解决，只是将自己的模型当做是理论。但大佬之外还有大佬——Steve Russell，这位大佬是电子游戏创始人，史上第一个电子游戏Space War就是他写的。

Russell一并将这两个问题都解决了，采用的方法是——解释器。传统的高级编程语言流程是：编译–>运行，然后Russell让Lisp在解释器里跑，就变成了：编写–>解释执行。相当于在IBM机器上用机器码写了一个通用图灵机，用来解释所有的Lisp指令。至此，lisp从理论走到实践。

因为是解释执行，所以就有了一个特殊的环境———运行时环境，Lisp可以轻松实现递归，只要支持一个软件实现的栈就可以了，这部分也是解释器要做的。作为写lisp的程序员，不需要手动管理栈，不用手动的动态分配空间，直接让解释管理空间。随之而来的，管理空间的一个新技术——垃圾收集器。

也就是说，在Fortran上被绕过的问题，在Lisp里面用全新的方法被解决了。同时，Lisp中还出现了很多伴生技术：抽象语法树、动态数据结构、垃圾收集、字节码等等。

同时，必须要提到的是，电子游戏祖爷爷Russell通过软件层面，将lisp的两个问题解决了，但MIT还有一派尝试通过硬件方面去解决，形成了灿烂如烟花般的Lisp machine，在七八十年代崛起，又随着pc的兴起迅速陨落，但是，这铺开了另一条路——虚拟机理论。

3 虚拟机

3.1 安全性和跨平台

在lisp的发展中，因为eval的原因，出现了运行时环境，根据这个概念，发展出了虚拟机技术。

现在，我们知道，虚拟机和字节码的概念。现在的高级语言，编译后的代码都是以字节码的形式存在的，这些字节码程序在虚拟机上运行。跨平台性是虚拟机的一个至关重要的特性。

虚拟机：一台虚假的机器，提供一个环境，其他程序可以在这个环境中运行，而不是在真实的及其中运行。- 安全性：虚拟机可以随时对程序的危险行为、缓冲区溢出、数组访问过界等进行控制- 跨平台性：只要在不同平台上安装支持同一个字节码标准的虚拟机，程序就可以在不同的平台上不加修改而运行。比如java，write once, run anywhere. 各个平台上的java虚拟机都统一支持java字节码，所以用户感觉不到虚拟机下层平台的差异，虚拟机已经把下层平台间的差异性给抹平了。字节码：bytecode，一种非常类似于机器码的指令格式，以二进制字节为单位定义的。

跨平台需求的出现是在微型计算机开始普及后了，因为在这之前，计算机还是庞然大物，程序都是为某一台计算机专门写的，不可能需要跨平台的。计算机普及后，各种平台瓜分了市场，但它们的软件互不兼容，所以就出现了软件跨平台的需求。

题外话：这个时候，随着大规模和超大规模集成电路技术的发展，电子计算机从1971 年开始微型化，一台计算机的大小仅相当于一台电视机。80 年代到90 年代，微型计算机逐渐在家庭推广应用。微型计算机出现后，计算机技术飞速发展，以INTEL 公司为代表的微处理器生产商，不断推出速度更快、功能更强的芯片，使计算机的体积越来越小、速度越来越快、功能越来越强，而价格则越来越便宜，使更多的寻常百姓能够享受计算机带来的方便。

Unix的发展史大家可能并不陌生，它用了跨平台语言C重写了一次，又因开源共享文化，普及开来，一知道dec，intel等各个平台上，产生了无数衍生版本。只要掌握了基本的Unix知识，就可以操作微型计算机了，unix的主打语言是C，一般是各个平台厂商提供编译器的方式实现的，编译生成一个可执行程序。注意，这个可执行程序不是跨平台的。跨平台是源代码级别的跨平台，不是可执行程序层面。

3.2 脚本语言

除了Unix上的主打语言C，还有一款跨平台语言：脚本语言。和普通的编程语言相比，在能完成的任务上并没有什么巨大的差异。脚本语言往往是针对特定类型的问题，语法更为简单，功能更加高层，几百行C能完成的，几行简单的脚本就可以完成。

脚本语言是如何解释与执行的呢？因为脚本语言的源代码本身就是可执行程序，所以它在解释层和执行层都是跨平台的。这个设计是如何实现的？如果要让脚本语言既跨平台，又能被直接执行，就需要有一个中间层，对上分析源代码的语法、逻辑和结构，对下隐藏平台差异。也就是对上解释，对下执行。

脚本语言的设计流派有两个：将解释和执行分开，将解释和执行结合在一起。

（1）解释和执行在一起

设计简单，早期的脚本语言都是采用这种方案，比如awk和perl。awk是unix的标配，入选了IEEE POSIX标准。

int main(int argc, char *argv[]){    ...    syminit();    compile_time = 1;    yyparse();    ...    if (errorflag == 0)    {        compile_time = 0;        run(winner);    }    ...}// runrun(Node *a)    /* execution of parse tree starts here */// winnerNode *winner ;    /* root of parse tree */

上面这段代码，akw调用了yacc解析源码，生成了一个语法树，winner是树的根节点，从根节点开始，往下用run这个函数，一路递归，直到最后把整个语法树遍历完，程序就执行完毕了。这样，通过抽象语法树在两个模块之间通信，避免了设计复杂的字节码规范，设计简单。

当然，这个方法也有缺点：

每次运行都要经过解释这一个过程，所以性能变差。假如有一个脚本，写好后不再修改，只要一直重复执行，那么解释的过程就多余了

递归的方式会让效率变低。递归涉及到栈操作和状态保存恢复，代价比极高，所以能不用递归就不用，特别是在高性能的场合不适用

需要在所有机器上都布置一个解释+运行的模块。因为程序的起点都是源代码，抽象语法树不能作为通用的结构在机器之间互传，所以只能在所有机器上不止一个解释+运行的模块。如果是嵌入式系统，就没法做了。

有些企业和程序员不喜欢开放源代码，如果要发布可执行程序，就等于发布源代码

（2）解释和执行分开：字节码+虚拟机

这种设计中，克服了上面的所有缺点，只需要解释一次语法结构，生成一个结构更加简单、紧凑的字节码文件。

解释一次： 然后每次运行脚本的时候，只需要把字节码文件传送给一个简单的解释字节码的模块就行。因为字节码简单，解释字节码的模块比解释程序的模块要小很多。

脱离语法树：用更加高性能的方式设计运行，避免递归遍历语法树这种低效的执行方式。

嵌入式系统：只部署运行时环境，不部署编译器。

讲到了这里，相信对 Java，对 PHP 或者对 Tcl 历史稍微了解的读者都会一拍脑袋顿悟了：原来这些牛逼的虚拟机都不是天才拍脑袋想出来的，而是被需求和现实给召唤出来的啊！

我们先以 Java 为例，说说在嵌入式场合的应用。Java 语言原本叫 Oak 语言，最初不是为桌面和服务器应用开发的，而是为机顶盒开发的。SUN 最初开发 Java 的唯一目的，就是为了参加机顶盒项目的竞标。嵌入式系统的资源受限程度不必细说了，自然不会允许上面放一个解释器和一个运行时。所以，不管 Java 语言如何，Java 虚拟机设计得直白无比，简单无比，手机上，智能卡上都能放上一个 Java 运行时（当然是精简版本的）。 这就是字节码和虚拟机的威力了。

SUN 无心插柳，等到互联 兴起的时候， Java 正好对绘图支持非常好，在 Flash 一统江湖之前，凭借跨平台性能，以 Applet 的名义一举走红。然后，又因为这种设计先天性的能克服性能问题，在性能上大作文章，凭借 JIT 技术，充分发挥上面说到的优点2，再加上安全性，一举拿下了企业服务器市场的半壁江山，这都是后话了。

再说 PHP。PHP 的历史就包含了从第一种设计转化到第二种设计以用来优化运行时性能的历史。PHP 是一般用来生成服务器 页的脚本语言。一个大站点上的 PHP 脚本，一旦写好了，每天能访问千百万次，所以，如果全靠每次都解释，每次都递归执行，性能上是必然要打折扣的。所以，从1999年的 PHP4 开始， Zend 引擎就横空出世，专门管加速解释后的 PHP 脚本，而对应的 PHP 解释引擎，就开始将 PHP 解释成字节码，以支持这种一次解释，多次运行的框架。在此之前， PHP 和 Perl，还有 cgi，还算平分秋色的样子，基本上服务器上三类 页的数量都差不多，三者语法也很类似，但是到了 PHP4 出现之后，其他两个基于第一种设计方案的页面就慢慢消失了，全部让位给 PHP。WordPress 博客，也是基于 PHP 技术的，底层也是 Zend 引擎的。著名的 LAMP 里面的那个 P， 原始上也是 PHP，而这个词真的火起来，也是99年 PHP4 出现之后的事情。

第二种设计的优点正好满足了实际需求的事情，其实不胜枚举。比如说 在 Lua 和 Tcl 等宿主语言上也都表现的淋漓尽致。像这样的小型语言，本来就是让运行时为了嵌入其他语言的，所以运行时越小越好，自然的，就走了和嵌入式系统一样的设计道路。

三 语言分类

1 根据运行过程划分

根据运行过程划分: 编译型、解释型、混合型

编译型语言

需要通过编译器compiler将源码编译成机器码才能执行的语言。 经过编译、链接两个过程。编译compile：把源码编译成机器码链接linker：把各个模块的机器码和依赖库串连起来生成可执行文件优点：只编译一次，运行时不需要编译，执行效率高，可以脱离语言环境独立运行缺点：编译后如需修改就要整个模块重新编译，编译时根据相应的运行环境生成机器码

解释型语言

不需要编译，在运行程序的时候逐行翻译

优点：在良好的平台兼容性、任何环境中都可以运行（需要安装解释器）

缺点：每次运行的时候都要解释一遍，性能上不如编译型语言

混合型语言：半编译型语言

C# 编译的时候不是直接编译成机器码，而是中间码，.NET平台提供了中间语言运行库，运行中间码。中间语言运行库相当于java虚拟机，.net在编译成IL代码后，保存在dll中，首次运行时由JIT再编译成机器码缓存在内存中，下次直接执行。

严格来说，混合型语言属于解释型语言，c#更接近编译型语言。

2 根据运行时结构划分

根据运行时结构是否可变（代码结构）：动态语言，静态语言

动态语言

面向运行时的语言

运行时可改变结构的语言，如新的函数、对象、甚至代码可以被引进等。运行时，代码可以根据某些条件改变自身结构。

Object-C、C#、JavaScript、PHP、Python、Erlang

静态语言

运行时，结构不可变得语言。

Java，C++，C

很多人认为解释性语言都是动态语言，这个观点是错的！Java是解释型语言但是不是动态语言，Java不能在运行的时候改变自己结构。反之成立吗？动态语言都是解释性语言。也是错的！Object-C是编译型语言，但是它是动态语言。得益于特有的run time机制（准确说run time不是语法特性是运行时环境，这里不展开）OC代码是可以在运行的时候插入、替换方法的。

C#也是动态语言，通过C#的反射机制可以动态的插入一段代码执行

3 根据数据类型检查划分

根据数据类型检查划分（数据类型）：动态类型语言、静态类型语言

动态类型语言：在运行期间才做数据类型检查

动态类型语言的数据类型不是在编译阶段决定的，而是把类型绑定延后到了运行阶段。

主要语言：Python、Ruby、Erlang、JavaScript、swift、PHP、Perl。

静态类型语言：编译期间确定或者说运行前确定数据类型。

编写代码的时候就要确定变量的数据类型

主要语言：C、C++、C#、Java、Object-C

相当一部分程序员，认为解释型语言都是动态类型语言，编译型语言都是静态类型语言。这个也是错的。swift是编译型语言但是它也是动态类型语言。C#和Java是解释型语言也是静态类型语言。

四 语言应用比较

这部分内容有一定的时效性，仅作为参考

应用情况建议采用语言已知大量事实，和之间的约束，要求挖掘关系，比如汉若塔、八皇后、地图着色prolog族语言从小到超大型应用程序，非完全互联 应用C++，Java，C#，VB，GO，Rust程序规模不是很大的数学问题pascal，fortran，lisp，c++，matlab，java，C#需要大量处理字符串perl，C++需要一个胶水，粘结不同语言写出来的程序python，.net自动化测试tcl，shell，python系统底层c系统管理，linuxshell：bash，c shell苹果平台objective-c，swift嵌入式c 页php，js数据库sql,PL(SQL)/Transact-SQL,mongodb并行、分布式GO，Rust，C++，Java，C#特定语言的功能增强Lua人工智能Prolog，lisp，R

参考资料

1. 编译型语言和解释型语言
https://www.cnblogs.com/zy1987/p/3784753.html

2. 编程语言发展脉络图
https://www.cnblogs.com/rufi/p/language_graph.html

3. 大英百科全书——提花织机
https://www.britannica.com/technology/Jacquard-loom

4. 百度百科——提花织机
https://baike.baidu.com/item/%E9%9B%85%E5%8D%A1%E5%B0%94%E6%8F%90%E8%8A%B1%E6%9C%BA/4860470?fr=aladdin

5.高级语言是怎么来的
https://blog.youxu.info/2009/05/13/hpl/

6.百度百科——数学危机
https://baike.baidu.com/item/%E6%95%B0%E5%AD%A6%E5%8D%B1%E6%9C%BA

7.百度百科