程序语言编年史
概述
这次咱们聊下程序语言的发展史，除了程序语言，还会着重讲下程序语言密切相关的计算机的发展史，顺带讲下同时期与程序语言和计算机相关领域的发展,为什么要把程序语言和计算机相关领域放到一块讲, 因为这些领域和计算机的关系太密切了, 程序语言是程序员和计算机沟通交流唯一方式, 计算机的计算模型的发展, 还有计算机的应用领域的发展都对程序语言有着深刻的影响. 通过计算机相关领域的发展, 我们能从中可以找到一些影响程序语言关键因素, 看看这些因素是如何推动程序语言一步步发展成今天这个样子的.
计算机发展史
计算机的发展可以分为两条线进行追溯, 一条是计算理论的发展, 一条是计算机实体的发展, 下面我们看看计算理论和计算机的发展轨迹.
理论模型的演变
计算理论是近现代才出现的一个数学分支,主要研究可计算性,计算的复杂度,计算模型(计算理论中两大计算模型:图灵机,lambda演算),形式语言(编程语言也是一种形式语言).我们可以看到计算理论主要研究的对象的名字中有三个带了计算; 计算这个词很常见,好像和这些词汇所表达的意思挺相近:四则运算,数值计算,逻辑运算.本节就以计算为主线介绍下计算是什么,以及其演变历史,还有它和计算理论的关系.
史前数学：数值计算
第一次数学危机：逻辑证明的奠基
根据 上面四种情况 和 肯定存在一组解使得y*y或x*x为奇数 进一步只分析 使得y*y或x*x为奇数 的情况, 只剩下了三种可能:
综上所述,直角等腰三角形的直角边和斜边不可通约.
我们现在回顾分析上述的数学活动过程, 从等腰直角三角形,通约的定义,然后通过逻辑证明,最后得出等腰直角三角形的直角边和斜边不可通约, 这个过程中计算只参与了各个可能情况中的等值判断, 中间结果和最终结果的流转全是由逻辑证明推动的.从这个时期开始, 数学理论研究工作中的主要方法为推理,以及后来出现公理.比如欧几里得的<几何原本>,书中对几何的研究方法都是以定义和公理以及推理规则为基础.还有比较有名逻辑范式:亚里士多德的三段论. 以及斯多葛的逻辑证明的推理规则如果 命题A 那么 命题B和 命题A 可以导出 命题B.就是这些基础的逻辑范式或者叫推理规则或者正式点叫命题逻辑, 为以后的数学大厦奠定了夯实的基础，后面我们会继续介绍逻辑在数学计算发展史中所发挥的重要作用.
前面的讲述提到的计算其实只参与推理活动需要数值判断的部分;和数学理论研究相反的是实践活动中的数学,计算承担了其中的大部分工作.计算参与数学实践活动有一个比较有名的例子就是欧几里得的辗转相除法求两个数最大公约数,这个计算模型包含了得出最大公约数的能力同时也隐含了最大公约数的推理证明.辗转相除法的计算模型简化了求最大公约数的过程和证明其为最大公约数的过程, 从这里我们似乎看到了计算和证明的一点点模糊关系.
另外值得注意的是这次的数学求解活动将现实中具体问题与数学中抽象的问题完全分割开来,因为此次求解涉及的概念完全是从对现实问题的抽象(数学中的计算,测量,分割)的抽象(对从现实抽象而来的数学概念再次抽象)而来,这次求解开辟了对纯粹的数学抽象概念的研究, 断开了与现实问题的直接连接, 比如这次数学活动中的等腰直角三角形这个概念, 这个概念不涉及任何具体的三角行, 活动要研究的是所有等腰直角三角形的特征,而不是某个具体的等腰直角三角形的特征. 以后的数学所研究的领域也大都是此类从现实问题抽象而来再次抽象的数学问题, 虽然这样的数学问题普适性更广, 也越接近本质, 但是这也是数学为什么这么让人费解犯难的原因之一吧.
数理逻辑时代,从谓词逻辑到计算理论:逻辑证明 = 计算 + 不可停机 ?
总结一下，计算从解决最基础的日常生产中的实际问题开始，此时的计算在数学中占据主要位置；时间往后一点，这个时候数学开始过度到与现实问题不再那么紧密的二次抽象问题上研究，计算在这次过度中其在数学中的重要性被逻辑证明取代，计算似乎只是一种逻辑证明过程中的辅助工具；数学界花费了很长一段时间对逻辑证明进行符号化公理化，他们再这段时间里发现这个目标的实现存在太多问题，其中最严重的问题就一些由自指带来的逻辑悖论，这些逻辑悖论产生的背景其中有一部分是涉及到计算的，这些关于计算的悖论的证明过程让数学家明确了计算是什么以及计算和逻辑证明（演绎推理）的区别，对计算机影响深刻的各种计算模型（图灵机，lambda演算等）也是在这个时期诞生的，关于计算和逻辑，数学和计算机理论中也建立了新的分支：数理逻辑，证明论，计算理论。本文中计算的发展就讲到计算理论的诞生，关于数学计算的研究仍在继续，新的征程：去公理化，自动化证明……
另外我们也可以看到关于计算的抽象级别在逐步降低，而其通用性变得越来越广。从一开始的应用在被抽象成数字的现实物体上的计算规则：计数，分配等；然后又从现实问题中抽象出的数字之上又抽象出数字间的关系：不可通约；类似这种抽象之上的抽象问题开始变得越来越多：逻辑证明的符号化，逻辑证明的一致性和完备性，以及计算是什么，将计算应用到计算之上，这些问题的提出和解决明确了计算的边界，通用计算模型也在此时登场：图灵机，lambda演算。抽象级别的降低使得我们在直接理解这些计算模型时出现了抽象和因果时序关系的断层，所以为了大家能够对计算有个整体的理解，有必要还原一下计算的发展历史，这有助于我们后面讲述计算机和程序语言的发展和演变。后面我们会继续看到抽象在计算模型和计算载体实现上的转变和抽象级别的再次降低，而程序语言的抽象级别的演变却是尝试将抽象还原到与现实问题同等的水平。
计算在生产活动中的实践:通用计算机的诞生
计算工具的出现大大提高了人类的计算效率,从最初的使用直接对现实观察的方式进行测量计数;进而出现了的专用的数字运算工具:算筹,算盘;然后又出现了更高级的专用半自动计算工具:计算尺,机械计算器;最终计算工具的进入了理想形态:通用计算机.
下图是计算工具发展史中的几个关键点:
上表中我们可以清楚的看到计算工具的逻辑载体从机械过渡到电子继电器进而最终发展成电子设备,其中的计算规则的执行也逐渐由机器的自动化执行取代了人工操作;计算工具的计算能力的适用性也由专用的领域拓展到了通用计算.
在计算机的发展历史节点有一个关键点那就是图灵机和lambda演算的出现, 而且这两个模型在同一年被提出, 这两个计算模型都是图灵完备的, 我们在上一节中也讲到过这两个计算模型和计算的能力是等价的. 有意思的是图灵机给现代的程序存储计算机提供了最早的计算理论模型. 而lambda演算作为一种原生形式语言给程序设计语言提供了函数编程范式.
此处重点介绍下图灵机和lambda演算，因为图灵机影响了现代计算机的架构，而lambda演算影响了现代程序语言。
图灵机
图灵机是什么
图灵机是一种状态机,所有计算(前面我们已经定义过计算,阐述过计算的能力)能做的事情, 图灵机也能模拟完成.现代计算机的计算能力和图灵机的计算能力是等价的, 现代的计算机就是受图灵机的原理一步步发展成现在这个样子的.
图灵机的结构
图灵机实现计算的方式是根据自身定义好的状态转换集合,一步步根据纸带上的字符输入,来切换自身当前的状态,改写纸带上的字符移动读写头,图灵机的输入输出都是在一条可以进行读写字符的格子纸带, 最终的计算结果也是靠纸带上字符呈现的. 实际上图灵机的主要结构就是一个无限长的用来记录输入和输出的格子纸带(计算机的内存) 和 一个具有状态转换集合并且可以左右移动的读写头(和cpu很相似, 状态转换集合可以看成cpu的指令集, 左右移动的读写头可以看成cpu对内存进行随机读写)
图灵机的能力图灵机的定义和计算的定义是等价的, 而且它们的执行过程也很相似, 都是对状态进行一步步的转换. 在用图灵机进行计算时, 其中有一个关键的要素, 就是如何将实际问题抽象转化为图灵机可解的计算模型, 这有和我们通过程序语言模拟建模现实问题的解决方案是一样的. 我们知道在使用程序语言进行解决问题时有两个比较关键因素决定了程序的实现难度:一个就是数据结构, 一个就是算法.在图灵机中, 原生的数据结构就是一条可读写字符的格子纸带, 原生算法就是状态转换以及对纸带的读写.
使用图灵机进行计算的步骤:
1.从现实问题中抽象出参与计算的实体,比如数字加法运算中的数字, 你可以将数字定义为纸带上写有1的连续格式的数量, 比如3就是111, 2就是11,6就是111111,依次等等; 当然还要定义算法操作符, 操作符可以选取字符中加号:+
2.定义算法,定义算法时需要根据前面一步中定义的实体的自身特点来进行实际算法实现;比如加法,根据上面对数字的定义, 那么加法的可以定义为读写头擦除第一个数字1,然后读写头向右一直移动到加号+处将+号改为1,最后读写头向右移动到空白处停机; 此时纸带上1的个数就是此次运算的结果.
lambda演算
lambda是什么
lambda的组成
lambda如何实现计算
上面展示的只是lambda演算的算术计算能力, 在合适抽象出数据类型后, lambda不止能进行算术计算, 还能进行其他很多运算比如布尔运算, 递归调用等.
介绍完图灵机和lambda表达式, 可以看出图灵机的运作模式就是一台按照一个固定规则进行运作的机器; 而lambda演算更像一种具有一定文法规则的符号系统, 有一点点语言的感觉. 另外我们在这两个计算模型在实现计算的流程中都经历了数据结构的定义和转换规则的定义,然后按照转换规则对输入的数据结构进行处理输出,这也很我们在写代码时定义数据结构和算法很相似, 再联想一下, 这个过程和我们解决问题也很相似, 根据问题现状, 找到目标, 定义解决方案, 然后根据解决方案中实施步骤执行,最终得到结果.
程序设计语言的发展史
在上面两个经典的计算模型产生以后没几年, 通用计算机就被造了出来:马克一号. 现在我们思考一个问题, 具有计算能力的机器已经有了, 那我们如何使用这台机器呢?--机器指令,当时使用这台机器的方式是通过把机器指令和数据编码后按照执行的顺序存储到打孔纸带,然后将纸带输入到计算机中实现计算.这种使用方式很麻烦, 指令打印错了以后要么用胶带糊要么可能整个纸带都需要换掉重打,工作量太大,耗材也太浪费了,而且不方便阅读,调试(说的有点远了嘿嘿).
按照顺序排列在打孔纸带上的指令, 这就是最初的程序设计语言, 虽然太难读; 那会有一个叫葛丽丝·霍普的女程序员(在马克一号上写代码)就感觉直接在纸带书写指令太麻烦, 就想着能不能直接用人类的语言(前面说过自然语言是一个形式系统,本身具备计算能力)来写程序呢, 于是她就开始了这方面的尝试, 我们常说好事都会发生在别人身上, 果不其然, 她在1951年-1952年做出了第一不完整编译器 A-0 System, 这个编译器内部预置了功能函数, 程序员只能使用这些功能函数, 最终A-0会将代码转换成内置的功能函数的二进制指令, 有点像编译器中链接功能.虽然这个编译器的功能很弱,但是用人类的语言来书写程序的这个想法, 使得程序设计语言和编译器从此开发生根萌芽,一直到现在的百花齐放. 另外有一个让人拍手称快的消息, 这个女程序员发现了史上第一个bug(一个飞蛾), 很嘲讽有么有.
在编译器的概念被提出后, 没过几年, 1956年第一个高级程序语言fortran面世. fortran 支持变量和高级命令语句(IF DO),
变量是对内存的抽象, 命令语言是对计算机指令的抽象. 把对硬件的直接操作抽象成了一种形式语言,而编译器最终将代码语言翻译为机器指令,编译器的翻译功能可以看成形式系统的转换规则,那么编译器和程序设计语言两者则组成了一个形式系统.有意思的地方来了, 一个形式系统(逻辑上具备计算能力)运行在一个真正具备计算能力的机器上(通用计算机,逻辑门电路实现),而形式系统的最终算力实际来自机器,最终的计算结果是机器指令;另外一个有意思的地方,被翻译后的机器指令(可以看成一种形式语言)和计算机(逻辑电路的电信号的转换)再次构成一个形式系统,最终算力来依然来自于计算机,转换规则由编译器提供,也可以看成算力由编译器提供,最终计算结果是内存和各种输入输出设备的状态变化; 还有一个我们最容易忽略的有意思的地方,那就是程序设计语言和程序员的实际也是一种形式系统,算力来自程序员自身,最终计算结果是带有bug的代码,嘿嘿嘿.
最终上面三套形式系统涉及的各个具备算力的对象因为程序设计语言和编译器(逻辑算力)关联串在一起,下面是三个形式系统转换元组(形式语言,转换规则,结果)之间的转换关系
(程序设计语言语法,程序员,程序设计语言代码)->(程序设计语言代码,编译器,机器指令代码)->(机器指令代码,计算机,内存和各种输入输出设备的状态变化)
经过上述过程,人类就可以通过程序设计语言告诉计算机如何计算.
fortan作为高级语言抽象出了变量和语句两个新概念, 后面的程序设计语言都继承了这两个最基础的概念, 并且在这个基础之上发展出来很多其他概念,下表是按照时间先后顺序列出了一些程序设计语言中一些概念出现的时间点和背景.
这里面有很多概念不是由语言直接支持的,而是由语言之上的api库来支持, 例如设计模式,aop,ioc等等. 不过像面向对象,接口,异常这些概念在刚提出的时候当时的编程语言也是不支持的, 是后来程序员发现这些概念在解决问题时特别常用,然后就把这些概念加入到了语言当中. aop,ioc,设计模式等等这些概念会不会得到语言自身的支持, 这还得看语言和语言的使用方式的发展了.值得一提的是观察者模式在C#中直接通过语言的概念提供了支持, C#提供了 event和delegate 关键字来提供了支持.
在程序设计语言这个形式语言中, 各种概念的加入丰富了编程的乐趣,不过带来的更多的是以不同的视角对现实问题的抽象建模的可能,这些概念提出的背景可能涉及很多:代码的可维护性,扩展性,稳定性,复用性,可读性,性能等等.最终这些概念解决了提出它时所要解决的问题,但是也引入了其他问题,当然也没有一个万能的概念能解决所有问题,更多是写代码的人要思考如何使用这些概念的排列组合来解决一个个现实问题.不过这些概念有一个共同的特征,那就是这些抽象出来的概念越来越接近以人类看待现实问题的特点.
计算贯穿了本文的始末,我想也只有这样来写程序设计语言比较合适,因为程序设计语言因为计算而生,然后又是为了计算.有没有感觉刚才的解释形成了一个环, 其实不是, 第一个计算是出于人和计算机之间的沟通,第二个计算是通过代码建模解决实际问题.
不过另外一些问题倒是挺有趣的, 那就是如果以计算来看待这个世界,人具备计算能力,而且创造具备计算能力的机器. 计算机的计算能力来自于人为设计,那人的计算能力来自于何方, 是计算本身吗? 计算机的计算能力是为了帮助人类解决现实问题,那人类的计算能力的目的是为了什么, 是为了人类自身吗?