第一章 计算机语言的学科形态与发展历程 计算机语言在计算学科中占有特殊的地位，它是计算学科中最富有智慧的成果之一，它深刻地影响着计算学科各个领域的发展。不仅如此，计算机语言还是程序员与计算机交流的主要工具。因此，可以说如果不了解计算机语言，就谈不上对计算学科的真正了解。
计算学科中的抽象形态 《计算作为一门学科》报告认为：理论、抽象和设计是我们从事本领域工作的3种主要形态。 按人们对客观事物认识的先后次序，抽象列为第一个学科形态，理论列为第二个学科形态。抽象源于实验科学。按客观现象的研究过程，抽象形态包括以下4个步骤的内容： （1）形成假设； （2）建造模型并作出预测； （3）设计实验并收集数据； （4）对结果进行分析。
计算学科中的理论形态 在计算学科中，从统一合理的理论发展过程来看，理论形态包括以下4个步骤的内容： （1）表述研究对象的特征（定义和公理）； （2）假设对象之间的基本性质和对象之间可能存在的关系（定理）； （3）确定这些关系是否为真（证明）； （4）结论。
计算学科中的设计形态 在计算学科中，从为解决某个问题而实现系统或装置的过程来看，设计形态包括以下4个步骤的内容： （1）需求分析； （2）建立规格说明； （3）设计并实现该系统； （4）对系统进行测试与分析。
计算学科中的3个学科形态内在联系 3个学科形态的内在联系 抽象源于现实世界。建立对客观事物进行抽象描述的方法。建立具体问题的概念模型，实现对客观世界的感性认识。 理论源于数学。建立完整的理论体系 建立具体问题的数学模型，从而实现对客观世界的理性认识。 设计源于工程 。对客观世界的感性认识和理性认识的基础上，完成一个具体的任务；对工程设计中所遇到的问题进行总结，提出问题，由理论界去解决它。
现代信息技术的起源—数学原理 伯特兰·罗素：符号主义，为每一个数学事实都给出证明，而且都是机械进行的。 悖论问题：贝里悖论、理发师悖论 信息技术 发展历程 伯特兰·罗素：符号主义，为每一个数学事实都给出证明，而且都是机械进行的。 悖论问题：贝里悖论、理发师悖论 库尔特·哥德尔：元数学、形式，是否只需要一些机械规则就能证明任何定理-不存在完全自治的形式体系。 图灵计算机 --- 阿兰·图灵，论可计算数，设计了一个自动计算的机器，用于生成可计算数 6
现代信息技术的起源—二战后期 电报、电话和无线电技术迅猛发展—密码挑战 信息技术 发展历程 电报、电话和无线电技术迅猛发展—密码挑战 1941年 Z-1计算机：德国人发明。第一台采用二进制和继电器的通用程序计算机。用于破译敌人的密码，德国政府没有批准 1943年，Colossus（巨人计算机） 英国政府秘密组建一个由科学家和工程师组成的绝密小组，使得英国军方能够窃取并破译德国的军事情报。 阿兰·图灵，设计了一个自动计算的机器，部分参与了上述计算系统的研制。 7
电子计算机——ENIAC 1946 年 第一台真正运转的电子计算机，开启了电子计算机的序幕 ENIAC：美国人发明。 信息技术 发展历程 ENIAC：美国人发明。 背景：军械部为计算弹道和射击表启动的计划，宾夕法尼亚大学。 1946年宣告竣工。 使用18 000个电子管，占地 167 平方米，重达 30 吨。 每秒5000次加法，300次乘法。 冯·诺依曼体系结构：来源于EDVAC（101）方案 1946 年 存储器 运算器 控制器 输出设备 输入设备 第一台真正运转的电子计算机，开启了电子计算机的序幕 8
现代信息技术的起源—二战后期 信息技术 发展历程 信息论的诞生 ---- 克劳德·香农，安全密码系统，通信的数学理论：在一点精确地或近似地复现另一地点所选取的讯息。 信息是熵，信息的量度是一种不确定性的度量， 需要一个单位bit.---Information的由来。 9
现代信息技术的起源—二战后期 信息技术 发展历程 控制论-- 关于在动物和机器中控制和通信的科学。 10
目录 1、形式化语言、图灵机和冯·诺依曼型计算机、机器指令系统 2、汇编语言、计算机的层次结构、虚拟机、高级语言形式化 3、当代计算机语言发展趋势与形态演变 4、程序设计语言分类与主要典型代表
一、形式语言、图灵机与冯·诺依曼型计算机
形式语言的基本特点 有一组初始的、专门的符号集； 有一组精确定义的，由初始的、专门的符号组成的符号串转换成另一个符号串的规则。 在形式语言中，不允许出现根据形成规则无法确定的符号串。
形式语言的语法 形式语言的语法：形式语言中的转换规则。 语法不包含语义。 在一个给定的形式语言中，可以根据需要，通过赋值或模型对其进行严格的语义解释，从而构成形式语言的语义。 语法和语义要作严格的区分。
图灵机 图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成，
图灵机 写在带子上的符号为一个有穷字母表：{S0，S1，S2，…，Sp}。 可以认为这个有穷字母表仅有S0、S1两个字符， 由 “0”和“1”组成的字母表可以表示任何一个数。
由于“0”和“1”只有形式的意义，因此，也可以将S0改称为“白”，S1改称为“黑”，甚至，还可以改称为“桌子”和“老虎”，这样改称的目的在于割断与直觉的联系，并加深对布尔域中的值{真，假}，以及二进制机器本质的理解。机器的控制状态表为：{q1，q2，…，qm}。 将一个图灵机的初始状态设为q1，在每一个具体的图灵机中还要确定一个结束状态qw。
一个给定机器的“程序” 机器内的五元组（qiSjSkR（或L或N）ql）形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下： qi表示机器目前所处的状态； Sj表示机器从方格中读入的符号； Sk表示机器用来代替Sj写入方格中的符号； R、L、N分别表示向右移一格、向左移一格、不移动； ql表示下一步机器的状态。
图灵机及其他计算模型 图灵的观点及结论： 与图灵机等价的计算模型： 凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。 与图灵机等价的计算模型： 递归函数 λ-演算 POST规范系统 图灵机是从过程这一角度来刻画计算的本质，其结构简单、操作运算规则也较少，从而为更多的人所理解。 它们于20世纪30年代共同奠定了计算科学的理论基础。
图灵机的计算能力 图灵机可以计算 S(x)＝x＋1（后继函数）， N(x)＝0（零函数）， Ui(n)(x1，x2，…，xn)＝xi，1≤i≤n（投影函数） 上述3个函数的任意组合。 从递归论中，我们知道这3个函数属于初始递归函数， 任何原始递归函数都是从这3个初始递归函数经有限次的复合、递归和极小化操作得到的。 从可计算理论可知每一个原始递归函数都是图灵机可计算的。
冯·诺依曼型计算机 ENIAC的结构在很大程度上是依照机电系统设计的，还存在重大的线路结构等问题。 在图灵等人工作的影响下，1946年6月，美国杰出的数学家冯·诺依曼（Von Neumann）及其同事完成了关于“电子计算装置逻辑结构设计”的研究报告， 具体介绍了制造电子计算机和程序设计的新思想 至今为止，大多数计算机采用的仍然是冯·诺依曼型计算机的组织结构，只是作了一些改进而已。因此，冯·诺依曼被人们誉为“计算机器之父”。
冯·诺依曼型计算机的组织结构
指令系统 CPU必须能够解码并执行的机器指令很少 是否充分利用这种特性导致了两种不同的计算机设计： 一旦计算机可以执行一些基本的而且是精选的操作，加入额外的操作理论上是不会改变计算机的能力的 是否充分利用这种特性导致了两种不同的计算机设计： CISC(reduced instruction set computer) RISC(complex instruction set computer)
CISC 最初人们采用的是进一步增强原有指令的功能，并设置更为复杂的指令的方法 CISC的思路是由IBM公司提出的，并以1964年IBM研制的IBM 360系统为代表。
CISC缺点 80%的指令只在20%的运行时间里用到； 一些指令非常繁杂，而执行效率甚至比用几条简单的基本指令组合的实现还要慢。 庞杂的指令系统也给超大规模集成电路（VLSI）的设计带来了困难， 它不但不利于设计自动化技术的应用，延长了设计周期，增加了成本， 容易增加设计中出现错误的机会，从而降低了系统的可靠性。
RISC 思路主要是通过减少指令总数和简化指令的功能来降低硬件设计的复杂度，从而提高指令的执行速度。 优点:与CISC技术相比 简化了指令系统，适合超大规模集成电路的实现； 提高了机器执行的速度和效率； 降低了设计成本，提高了系统的可靠性； 提供了直接支持高级语言的能力，简化了编译程序的设计。
机器指令 机器指令系统——每台数字电子计算机在设计中，都规定了一组指令。 机器语言——用机器指令形式编写的程序。 在裸机级，计算机语言关于算法的描述采用的是实际机器的机器指令，它的符号集是{0，1}， 支撑实际机器的理论是图灵机等计算模型； 在图灵机等计算模型理论的指导下，有关设计形态的主要成果有冯·诺依曼型计算机等具体实现思想和技术，以及各类数字电子计算机产品。
计算机语言在裸机级所取得的主要成果 抽象 理论 设计 裸机级的主要内容和成果 语言的符号集为：{0，1}； 用机器指令对算法进行描述 语言的符号集为：{0，1}； 用机器指令对算法进行描述 图灵机（过程语言的基础）、波斯特系统（字符串处理语言的基础）、λ-演算（函数式语言的基础）等计算模型 冯·诺依曼型计算机等实现技术； 数字电子计算机产品 计算机语言在裸机级所取得的主要成果
二、高级语言出现、发展与主要学科形态
汇编语言 采用字符和十进制数来代替二进制代码的思想。 例3.10 对2+6进行计算的算法描述 用机器指令对“2+6”进行计算的算法描述： 例3.10 对2+6进行计算的算法描述 用机器指令对“2+6”进行计算的算法描述： 1011000000000110 0000010000000010 101000100101000000000000 汇编语言对“2+6”进行计算的算法描述： MOV AL，6 ADD AL，2 MOV VC，AL
汇编语言语句与特定的机器指令有一一对应的关系，但是它毕竟不同于由二进制组成的机器指令，它还需要经汇编程序翻译为机器指令后才能运行。 汇编语言源程序经汇编程序翻译成机器指令，再在实际的机器中执行。 就汇编语言的用户而言，该机器是可以直接识别汇编语言的，从而产生了一个属于抽象形态的重要概念，即虚拟机的概念。
虚拟机 抽象的计算机 由软件实现，并与实际机器一样，都具有一个指令集并可以使用不同的存储区域。 例如，一台机器上配有C语言和Pascal语言的编译程序，对C语言用户来说，这台机器就是以C语言为机器语言的虚拟机，对Pascal用户来说，这台机器就是以Pascal语言为机器语言的虚拟机。
虚拟机的层次之分 虚拟机可分为 固件虚拟机 操作系统虚拟机 汇编语言虚拟机 高级语言虚拟机 应用语言虚拟机等
虚拟机的意义和作用 有助于我们正确理解各种语言的实质和实现途径 推动了计算机体系结构以及计算机语言的发展 有助于各层次计算机语言自身的完善 当机器（实际机器或虚拟机）确定下来后，所识别的语言也随之确定；反之，当一种语言形式化后，所需要支撑的机器也可以确定下来。从计算机系统的层次结构图中可以清晰地看到这种机器与语言的关系。虚拟机是计算学科中抽象的重要内容。引入虚拟机的概念，就计算机语言而言，有以下意义和作用： 有助于我们正确理解各种语言的实质和实现途径 推动了计算机体系结构以及计算机语言的发展 有助于各层次计算机语言自身的完善 当机器（实际机器或虚拟机）确定下来后，所识别的语言也随之确定；反之，当一种语言形式化后，所需要支撑的机器也可以确定下来。从计算机系统的层次结构图中可以清晰地看到这种机器与语言的关系。
高级语言 虽然与机器语言相比，汇编语言的产生是一个很大的进步，但是用它来进行程序设计仍然比较困难。于是人们着手对它进行改进。一是发展宏汇编，即用一条宏指令代替若干条汇编指令，从而提高编程效率。现在人们使用的汇编语言，大多数都是宏汇编语言。二是创建高级语言，使编程更加方便。 如用高级语言对例子2+6进行计算的算法描述，其描述与数学描述一样，即2+6。
高级语言的分类 按语言的特点，可以将高级语言划分为： 过程式语言（如Cobol，Forturn，Algol，Pascal，Ada，C） 函数式语言（如Lisp） 数据流语言（如SISAL，VAL） 面向对象语言（如Smalltalk，CLU，C++） 逻辑语言（如Prolog） 字符串语言（如SNOBOL） 并发程序设计语言（如Concurrent Pascal，Modula 2）等
高级语言的形式化 20世纪50年代 美国语言学家乔姆斯基（Noam Chomsky）关于语言分层的理论， 巴科斯（Backus）、瑙尔（Naur）的关于“上下文无关方法表示形式”的研究成果推动了语法形式化的研究。 其结果是，在ALGOL60的文本设计中第一次使用了BNF范式来表示语法，并且第一次在语言文本中明确提出应将语法和语义区分开来。
高级语言的形式化 20世纪50年代至60年代间，面向语法的编译自动化理论得到了很大发展，使语法形式化研究的成果达到实用化的水平。 语法形式化问题基本解决以后，人们逐步把注意力集中到语义形式化的研究方面, 20世纪60年代，相继诞生了 操作语义学 指称语义学 公理语义学 代数语义学等语义学理论
高级语言简史 50年代高级语言出现 60年代奠基性研究 70年代完善的软件工程工具 80年代面向对象发展 90年代多范型、持久化、多媒体、平台无关 并行、声明式程序设计时代
java 数学表示法 1950 单元记录设施 符号名称 符 号 汇编 （ 1950年代中期 ） FORTRAN（1956） 数据规格说明 符 号 汇编 （ 1950年代中期 ） FORTRAN（1956） 数据规格说明 COBOL（1958） ALGOL-58 结构化控制 MAD（1959） 1960 APL （1962） ALGOL-60 CPL（1963） 非算法规格说明 RPG（1964） BASIC（1964） BCPL （1967） 交互使用 结构化数据 ALGOL-68 PL/1 （1966） B(1970) 面向对象编程 Simula （1967） 并发Pascal (1975) 1970 并发 Pascal(1973) 数据抽象 Modula C (1972) CLU(1977) 1980 Ada(1982) Smalltalk True BASIC(1980s) 1985 C++ 1995 多范式型 Ada(95) java 1996 平台无关
高级语言中抽象、理论和设计形态 抽象 理论 设计 常用的符号：数字(09)，大小写字母(AZ、az)，括号，运算符(+，，*，/)等; 用高级语言对算法进行的描述； 语言的分类方法； 各种数据类型的抽象实现模型； 词法分析、编译、解释和代码优化的方法； 词法分析器、扫描器、编译器组件和编译器的自动生成方法 形式语言和自动机理论； 形式语义学：操作、指称、公理、代数、并发和分布式程序的形式语义 特定语言：过程式的COBOL，FORTURN，ALGOL，Pascal，Ada，C），函数式的（LISP），数据流的（SISAL，VAL），面向对象的（Smalltalk，C++），逻辑的（Prolog），字符串（SNOBOL），和并发（Concurrent Pascal，Modula 2）等语言； 词法分析器和扫描器的产生器（如YACC，LEX），编译器产生器； 语法和语义检查，成型、调试和追踪程序
三、面向应用的计算语言发展与学科形态
计算机语言的划分 一般将它划分为5代： 第一代为机器语言； 第二代为汇编语言； 第三代为高级语言； 第四代为“非过程性语言”； 第五代为自然语言。 4GL以数据库管理系统所提供的功能为核心，进一步构造了开发高层软件系统的开发环境，如报表生成、多窗口表格设计、菜单生成系统等，为用户提供了一个良好的应用开发环境。 4GL的代表性软件系统有：PowerBuilder、Delphi和INFORMOX-4GL等。
4GL 提供了功能强大的非过程化问题定义手段，用户只需告知系统“做什么”，而无需说明“怎么做” 以数据库管理系统所提供的功能为核心，进一步构造了开发高层软件系统的开发环境， 报表生成 多窗口表格设计 菜单生成系统等 4GL的代表性软件系统有：PowerBuilder、Delphi和INFORMOX-4GL等。
应用语言中有关抽象、理论和设计形态的主要内容 用应用语言对算法进行描述 特定应用领域的支撑理论：数据库等领域的支撑理论 在文件处理等方面的应用：如表生成，图、数据处理，统计处理等； 第四代语言（4GL），如XML、HTML等
二十一世纪语言趋势 并行：如何做并行程序设计是每个计算工作者的挑战 脚本语言：计算机应用的崛起 软件设计：基于组件、服务、AOP的软件开发 狭义摩尔定律失效 并行系统的可靠性 并行系统开发效率 脚本语言：计算机应用的崛起 WEB服务端：PHP，ASP，JSP等 Web客户端：Javascipt 广泛应用开发：Perl，Python，Ruby 专用脚本语言：Tcl/tk 丰富、灵活、快速开发、解释执行、社区 软件设计：基于组件、服务、AOP的软件开发
对计算机语言抽象、理论和设计3个学科形态的研究，有助于我们正确理解计算机语言的本质，以及更好地把握它的研究方向，从而能更好地进行计算学科的研究。
信息技术发展的三个维度 能力 资源 复杂性 人类社会 物理系统 信息世界 追求高能力（如功能、性能、智能、易用等）是信息化的客观需求，也是人类追求科学技术极限的主观愿望使然。 人类社会 物理系统 信息世界 复杂性是现实世界的客观属性，控制复杂性也是人类在构造计算系统时自然的追求 资源的合理消耗是人类社会可持续发展的基本保障 复杂性 资源 48
四、程序设计语言分类与典型语言
语言分类 机器依赖 应用领域 低、高、中 商用 科学 系统 模拟 实时 COBOL FORTRAN BLISS GPSS CHILL 商用 科学 系统 模拟 实时 COBOL FORTRAN BLISS GPSS CHILL 各种表单语言 C,C++ C,C++ SIMULA GYPSY 嵌入式 人工智能 处理命令 教学 正文 Ada Prolog Sell Pascal SNOBOL LISP TCL PERL BASIC LOGO Word 打印出版 串、数组、表 数据库 Postscript APL SQL TeX SNOBOL LISP
续 程序范型 单范型/多范型 多范型Nail (1983) G (1986) C++、Ada-95 、CLOS 命令式（过程式） FORTRAN、COBOL、PL/1、PASCAL、Ada-83 面向对象 Smalltalk、Java、Eiffel 数据流 Val 函数式 ML LISP 逻辑式 Prolog 关系式 SQL 多范型Nail (1983) G (1986) C++、Ada-95 、CLOS
重要语言20种 FORTRAN、COBOL、ALGOL、PL/1 LISP、ALGOL-68、BASIC、PASCAL APL、Ada、Simula、C/C++ Smalltalk、ML、Prolog、SQL Java、XML、Python、Ruby