1、第3章 计算学科中的3个学科形态,3.1 一个关于“学生选课”的例 子,对“学生选课”例子的感性认识,现给出“学生”和“课程”两个实体,它们的联系为：一个学生可以选修若干门课程每门课程可以被任一学生所选修请建立一个信息管理系统，以实现对“学生选课”这一信息的管理。,概念模型,用于信息世界的建模，是客观世界到信息世界的抽象。概念模型中的主要概念有：实体、属性、码、域、联系等。实体：客观存在并可相互区别的事物。属性：实体所具有的某一种特性。码：能惟一标识实体的属性集。域：属性的取值范围。 联系：指不同实体集之间的联系。两个实体之间的联系分为：一对一（1:1）、一对多（1:N）、多对多（N:M）3类
2、。,E-R模型（Entity-Relationship）,1976年，美籍华人陈平山（Peter Pingshan Chen）提出的用E-R模型来描述客观世界并建立概念模型的抽象方法。实体用矩形表示，属性用椭圆形表示，联系用菱形表示，实体间的联系有一对一（1:1）、一对多（1:N）和多对多（N:M）3种情况。要实现对客观事物的感性认识，必须将客观世界（在例中客观世界就是“学生选课”）抽象为信息世界。,图3.1 学生选课E-R图,关系模型,概念模型不是机器世界所支持的数据模型，而是客观世界到机器世界的一个中间层次概念模型还需要转换成机器世界能支持的数据模型。在数据库领域中，数据库管理系统（DBM
3、S）能支持的数据模型有：层次、网状、关系以及面向对象等数据模型。关系模型支持的是一种二维表结构的数据模型，它由关系数据结构、关系数据操作和关系数据的完整性约束条件三部分组成。其中关系就是一张二维表。,概念模型（E-R图）关系模型,转换：学生（学号，姓名，年龄，性别）；课程（课程号，课程名）；学生选课（学号，课程号，成绩）概念模型是对现实原形的理想化，因此，将概念模型直接转换成关系模型，还不能说完全达到了对“学生选课”这一客观世界的理性认识，换言之，就是所转换的关系模型有可能还存在问题。,感性认识中存在的问题,在学生（学号，姓名，年龄，性别）关系中增加系名、系主任等属性时，即学生关系变为（学号，
4、姓名，年龄，性别，系名，系主任）时，便开始出现以下问题。插入异常一个系刚成立，系主任已确定，但还未招学生时，则无法将系名和系主任的名字插入到数据库中（学生实体中学号为码，码不能缺）删除异常当一个系的学生全部毕业，删除所有毕业生时，系名和系主任的名字也就删除了冗余太大由于一个学生对应一个系名和系主任的名字，则该系系名和系主任的名字要重复。,关系模式的形式化定义,关系模式（R）是一个四元组，即 R=其中：（1）U表示关系中所有属性的集合；（2）D表示属性集合U中属性所来自的域；（3）dom是属性到域的映射；（4）F是属性集合U上的一组数据依赖。,关系模式的形式化定义,由于D、dom与模式设计关系不
5、大，可将关系模式简单地表示为一个二元组 R=1NF的定义：作为一张二维表的关系，每一个分量必须是不可再分的数据项，满足这个条件的关系模式就属于1NF。2NF的定义：若R1NF，且每一个非主属性不存在对码的部分函数依赖，则 R2NF。在定义中，非主属性为不属于码的那些属性。3NF的定义：若R2NF，且每一个非主属性不存在对码的传递函数依赖，则 R3NF。,对“例子”问题的理性认识,例子最初是属于1NF、2NF、3NF，但是当在学生属性集U中增加系名和系主任后，就出现了这样的传递函数依赖：学号（码）系名，系名系主任。因此，它就不属于3NF了。不属于3NF的所有关系模型都会出现插入异常、删除异常和冗
6、余的问题。还必须依靠分解算法对模式进行分解，并满足3NF的要求。在数据依赖理论的指导下，可完成模式的分解任务。就例子而言，可以再划分一个关系，即系（系号，系名，系主任名），从而满足了关系模式规范化的要求，实现了对例子的理性认识。,从概念模型向满足规范化要求的关系模型的转换，其实质是认识过程由感性认识（抽象）上升到理性认识（理论）的过程，这个过程包含两方面的内容：一方面是有关理论的建立；另一方面是如何在理论的指导下，在具体的设计中，实现对客观世界的理性认识。前者是对科学研究而言的，而后者是对工程设计而言的。,“学生选课”系统的工程设计,建立起正确的关系模型后，还要根据具体的关系数据库管理系统对该
7、模型进行定义，下面，给出定义该模型的SQL语句：CREATE TABLE STUDENT( SNO CHAR(9) NOT NULL， SN CHAR(16)， SAGE INT， SEX CHAR(1) )；,“学生选课”系统的工程设计,CREATE TABLE COURSE( CNO CHAR(6) NOT NULL， CN CHAR(22) )； CREATE TABLE SC( SNO CHAR(9) NOT NULL， CNO CHAR(6)， GRADE INT )； CREATE TABLE DEPARTMENT( DNO CHAR(9) NOT NULL， DN CHAR(16
8、)， DEAN CHAR(8)；,“学生选课”系统的工程设计,接下来，便可以进行数据的输入、修改和查询，从而完成对“学生选课”的管理。一个简单的查询：查询选修了“数据库”课程，并且成绩在90分以上的所有学生的学号和姓名。SELECT SNO,SNFROM STUDENT,SC,COURSEWHERE CN=数据库 AND GRADE90;系统运行以上语句后，即可在屏幕上显示所求的结果。,3.2.1 抽象形态,3.2 计算学科的3个学科形态,一般科学技术方法论中有关抽象形态的论述,科学抽象是指在思维中对同类事物去除其现象的、次要的方面，抽取其共同的、主要的方面，从而做到从个别中把握一般，从现象中
9、把握本质的认知过程和思维方法。学科中的抽象形态包含着具体的内容，它们是学科中所具有的科学概念、科学符号和思想模型。,计算学科中有关抽象形态的论述,计算作为一门学科报告认为：理论、抽象和设计是我们从事本领域工作的3种主要形态按人们对客观事物认识的先后次序，我们将报告中的抽象列为第一个学科形态，理论列为第二个学科形态。抽象源于实验科学。按客观现象的研究过程，抽象形态包括以下4个步骤的内容： （1）形成假设； （2）建造模型并作出预测； （3）设计实验并收集数据； （4）对结果进行分析。,例子中有关抽象形态的主要内容及其简要分析,在“学生选课”例子中，有关抽象形态的内容可以用集合的方式表示为：A=学
10、生，属性，码，关系，学号，姓名，年龄，性别，课程，课程号，课程名，成绩，E-R图，“学生选课”E-R图，关系模型，“学生选课”关系模型， 对“学生选课”问题的抽象（感性认识）就是通过建立“学生选课”的E-R模型和关系模型来实现的，这一步是实现“学生选课”系统的关键。,3.2.2 理论形态,3.2 计算学科的3个学科形态,一般科学技术方法论中有关理论形态的论述,科学认识由感性阶段上升为理性阶段，就形成了科学理论。科学理论是经过实践检验的系统化了的科学知识体系，它是由科学概念、科学原理以及对这些概念、原理的理论论证所组成的体系。理论源于数学，是从抽象到抽象的升华，它们已经完全脱离现实事物，不受现实
11、事物的限制，具有精确的、优美的特征，因而更能把握事物的本质。,计算学科中有关理论形态的论述,在计算学科中，从统一合理的理论发展过程来看，理论形态包括以下4个步骤的内容： （1）表述研究对象的特征（定义和公理）； （2）假设对象之间的基本性质和对象之间可能存在的关系（定理）； （3）确定这些关系是否为真（证明）； （4）结论。,例子中有关理论形态的主要内容及简要分析,在与“学生选课”例子有关的关系数据库领域中，理论形态的主要内容可以用集合的方式表示为：T=关系代数，关系演算，数据依赖理论，在数据库理论的指导下，我们就可以在“学生选课”关系模型（感性认识）的基础上，建立对“学生选课”问题的理性认识
12、，从而为“学生选课”管理系统的设计奠定基础。,3.2.3 设计形态,3.2 计算学科的3个学科形态,一般科学技术方法论中有关设计形态的论述,设计形态与抽象、理论两个形态存在的联系 设计源于工程，并用于系统或设备的开发，以实现给定的任务。设计形态和抽象、理论两个形态具有许多共同的特点。设计必须以对自然规律的认识为前提。设计必须创造出相应的人工系统和人工条件，还必须认识自然规律在这些人工系统中和人工条件下的具体表现形式设计形态的主要特征与抽象、理论两个形态的主要区别： 设计形态具有较强的实践性、社会性、综合性。,计算学科中有关设计形态的论述,在计算学科中，从为解决某个问题而实现系统或装置的过程来看
13、，设计形态包括以下4个步骤的内容： （1）需求分析； （2）建立规格说明； （3）设计并实现该系统； （4）对系统进行测试与分析。,例子中有关设计形态的主要内容及简要分析,“学生选课”一例中，有关设计形态的内容是指：在数据库理论的指导下，运用E-R图和关系模型，实现对例子的感性认识和理性认识，最后借助某种关系DBMS（如Oracle等），实现“学生选课”应用软件的编制。最终成果是“学生选课”应用软件以及相关资料（如需求说明书）。就例子而言，其内容可以用集合的方式表示为：D=“学生选课”应用软件，“学生选课”需求说明，,3.2.4 3个学科形态的内在联系,3.2 计算学科的3个学科形态,一般科学
14、技术方法论中有关3个学科形态内在联系的简要论述,在计算机科学与技术方法论的原始命题中，蕴含着人类认识过程的两次飞跃，第一次飞跃是从物质到精神，从实践到认识的飞跃。这次飞跃包括两个决定性的环节：一个是科学抽象，另一个是科学理论。第二次飞跃是从精神到物质，从认识到实践的飞跃。这次飞跃的实质对技术学科（计算学科就是一门技术学科）而言，其实就是要在理论的指导下，以抽象的成果为工具来完成各种设计工作。,计算学科中有关3个学科形态内在联系 的论述,3个学科形态的内在联系 抽象源于现实世界。建立对客观事物进行抽象描述的方法 建立具体问题的概念模型，实现对客观世界的感性认识。 理论源于数学。建立完整的理论体系
15、 建立具体问题的数学模型，从而实现对客观世界的理性认识。设计源于工程 。对客观世界的感性认识和理性认识的基础上，完成一个具体的任务；对工程设计中所遇到的问题进行总结，提出问题，由理论界去解决它。,3.7 计算机语言的发展及其 3个学科形态的内在联系,计算机语言在计算学科中占有特殊的地位，它是计算学科中最富有智慧的成果之一，它深刻地影响着计算学科各个领域的发展。不仅如此，计算机语言还是程序员与计算机交流的主要工具。因此，可以说如果不了解计算机语言，就谈不上对计算学科的真正了解。,现在，我们从自然语言与形式化语言、图灵机和冯诺依曼型计算机、机器指令与汇编语言、计算机的层次结构、虚拟机的意义和作用、
16、高级语言、应用语言和自然语言的形式化问题等方面，介绍计算机语言的发展历程及其在抽象、理论和设计3个学科形态取得的主要成果，从而揭示计算机语言发展过程中3个学科形态的内在联系。,3.7.1 自然语言与形式语言,自然语言的定义人类的语言（文字）是人类最普遍使用的符号系统。其最基本、最普遍的形式是自然语言符号系统自然语言是某一社会发展中形成的一种民族语言。例如，汉语、英语、法语和俄语等。,自然语言符号系统的基本特征,歧义性；不够严格和不够统一的语法结构。例3.2 他的发理得好。他的理发水平高；理发师理他的发理得好。例3.3 他的小说看不完。他写的小说看不完；他收藏的小说看不完；他是个小说迷。,高级语
17、言的歧义性问题,高级程序设计语言其实也有语义的歧义性问题,高级程序设计语言存在较少的歧义性而已例3.4 IF (表达式1) THEN IF (表达式2) THEN 语句1 ELSE 语句2。IF (表达式1) THEN (IF (表达式2) THEN 语句1 ELSE 语句2)；IF (表达式1) THEN (IF (表达式2) THEN 语句1) ELSE 语句2。,形式语言,人们在自然语言符号系统的基础上，逐步建立起了人工语言符号系统（也称科学语言系统），即各学科的专门科学术语（符号），使语言符号保持其单一性、无歧义性和明确性。人工语言符号系统发展的第二阶段叫形式化语言，简称形式语言。形式
18、语言是进行形式化工作的元语言，它是以数学和数理逻辑为基础的科学语言。,形式语言的基本特点,有一组初始的、专门的符号集；有一组精确定义的，由初始的、专门的符号组成的符号串转换成另一个符号串的规则。在形式语言中，不允许出现根据形成规则无法确定的符号串。,形式语言的语法,形式语言的语法：形式语言中的转换规则。语法不包含语义。在一个给定的形式语言中，可以根据需要，通过赋值或模型对其进行严格的语义解释，从而构成形式语言的语义。语法和语义要作严格的区分。,例3.5,语言W定义为：初始符号集：a，b，c，d，e。形成规则：上述符号组成的有限符号串中，能组成一英语单词的为一公式；否则不是。问：W是否为一形式语
19、言？答：不是。因为，根据形成规则，无法精确地定义转换规则。原因：形成规则（语法）中包含了语义。,例3.6,语言X定义为：初始符号集：a，b，c，d，e，(，)，。形成规则：上述符号组成的有限符号串中，构成表达式的为一公式，否则不是。问：X是否为一形式语言？答：不是。原因：与例3.5相同。,例3.7,语言Y定义为：初始符号集：a，b，c，d，e，(，)，。形成规则：上述符号组成的有限符号串中，凡以符号“(”开头且以“)”结尾的符号串，为一公式。问：Y是否为一形式语言？答：不是。因为，根据形成规则，无法对不是以符号“(”开头且以“)”结尾的符号串进行判定。例如，(a+b)c。,例3.8,语言Z定义
20、为：初始符号集：a，b，c，d，e，(，)，。形成规则：上述符号组成的有限符号串中，凡以符号“（”开头且以“）”结尾的符号串，为一公式，否则不是。问：Z是否为一形式语言？答：是。,形式化的产物,由于技术科学（计算学科主要是一门技术科学）的语言从类型上说基本上是描述性、断定性而非评论性的，在描述性语言中又以分析陈述为主。技术科学就更有可能充分运用形式语言来表达自己深刻而复杂的内容，并进行演算化的推理。计算机语言是一种形式化语言。计算机的诞生又与形式化研究的进程息息相关。不论是计算机语言还是数字计算机，它们都是形式化的产物。,3.3.2 图灵机与冯诺依曼型计算机,3.3 计算机语言的发展及其3个
21、学科形态的内在联系,图灵机及其他计算模型,图灵的观点及结论：凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。与图灵机等价的计算模型：递归函数-演算POST规范系统图灵机是从过程这一角度来刻画计算的本质，其结构简单、操作运算规则也较少，从而为更多的人所理解。,图灵机,图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成，,图灵机,写在带子上的符号为一个有穷字母表：S0，S1，S2，Sp。可以认为这个有穷字母表仅有S0、S1两个字符，其中S0可以看作是“0”，S1可以看作是“1”，由 “0”和“1”组成的字母表可以表示任何一个
22、数。,由于“0”和“1”只有形式的意义，因此，也可以将S0改称为“白”，S1改称为“黑”，甚至，还可以改称为“桌子”和“老虎”，这样改称的目的在于割断与直觉的联系，并加深对布尔域中的值真，假，以及二进制机器本质的理解。机器的控制状态表为：q1，q2，qm。将一个图灵机的初始状态设为q1，在每一个具体的图灵机中还要确定一个结束状态qw。,一个给定机器的“程序”,机器内的五元组（qiSjSkR（或L或N）ql）形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下： qi表示机器目前所处的状态； Sj表示机器从方格中读入的符号； Sk表示机器用来代替Sj写
23、入方格中的符号； R、L、N分别表示向右移一格、向左移一格、不移动；ql表示下一步机器的状态。,一个机器计算的结果是从机器停止时带子上的信息得到的。容易看出，q1S2S2Rq3指令和q3S3S3Lq1指令如果同时出现在机器中，当机器处于状态q1，第一条指令读入的是S2，第二条指令读入的是S3，那么机器会在两个方块之间无休止地工作。另外，如果q3S2S2Rq4和q3S2S4Lq6指令同时出现在机器中，当机器处于状态q3并在带子上扫描到符号S2时，就产生了二义性的问题，机器就无法判定。,例子：,b表示空格，q1表示机器的初始状态， q4表示机器的结束状态，设带子上的输入信息是10100010，读入
24、头位对准最右边第一个为0的方格，状态为初始状态q1。规则如下：q1 0 1 L q2 q1 1 0 L q3 q1 b b N q4q2 0 0 L q2 q2 1 1 L q2 q2 b b N q4q3 0 1 L q2 q3 1 0 L q3 q3 b b N q4,计算结果是10100011，即对给定的数加1。,以上命令计算的是这样一个函数：S(x)x1。当没有输入时，即初始状态所指的方格为空格（b）时，不改变空格符，读写头不动并停机。,图灵机的计算能力,图灵机可以计算S(x)x1（后继函数），N(x)0（零函数），Ui(n)(x1，x2，xn)xi，1in（投影函数）上述3个函数的任
25、意组合。从递归论中，我们知道这3个函数属于初始递归函数，任何原始递归函数都是从这3个初始递归函数经有限次的复合、递归和极小化操作得到的。从可计算理论可知每一个原始递归函数都是图灵机可计算的。,冯诺依曼型计算机,ENIAC的结构在很大程度上是依照机电系统设计的，还存在重大的线路结构等问题。在图灵等人工作的影响下，1946年6月，美国杰出的数学家冯诺依曼（Von Neumann）及其同事完成了关于“电子计算装置逻辑结构设计”的研究报告，具体介绍了制造电子计算机和程序设计的新思想至今为止，大多数计算机采用的仍然是冯诺依曼型计算机的组织结构，只是作了一些改进而已。因此，冯诺依曼被人们誉为“计算机器之父
26、”。,冯诺依曼型计算机的组织结构,输入设备和输出设备,输入设备和输出设备,作用：是将信息输入计算机和输出计算机。常用的文字输入设备是键盘（还有扫描仪、穿孔卡片读入机和鼠标等专用输入设备）当在键盘上按下一个键时，按下的键通过编码变换成机器可读的数据形式，如字符“A”变换成ASCII码“1000001”，该编码数据随即存入存储器等待处理，通过与“1000001”对应的字符点阵数据在屏幕上显示一个字符“A”。输出设备有打印机、显示器、绘图仪、磁记录设备等。,存储器,存储器是一种数据或信息的存储部件，它分成很多存储单元，并按照一定的方式进行排列。每个单元都编了号，称为存储地址。指令和数据存放在存储器中
27、,而且对指令和数据同等对待，都不加区别地送到运算器中运算。指令在存储器中基本上是按执行顺序存储的，由指令计数器指明要执行的指令在存储器中的地址。 存储器一般分为内存储器与外存储器两大类。内存一般安装在主机板上，根据材料和工作原理的不同，内存可分为随机存储器（RAM）和只读存储器（ROM）两种。控制器和运算器只能接受在内存中存放的指令和数据。 外存一般安装在主机板之外，例如磁盘就是一种常用的外存。外存上面的信息可长久保存，但这些信息必须读入内存之后才能被控制器和运算器所利用。磁盘按其材料的不同，又可分为软盘和硬盘两种。,存储器,存储器是一种数据或信息的存储部件，它分成很多存储单元，并按照一定的方
28、式进行排列。每个单元都编了号，称为存储地址。指令和数据存放在存储器中,而且对指令和数据同等对待，都不加区别地送到运算器中运算。指令在存储器中基本上是按执行顺序存储的，由指令计数器指明要执行的指令在存储器中的地址。 存储器一般分为内存储器与外存储器两大类。内存一般安装在主机板上，根据材料和工作原理的不同，内存可分为随机存储器（RAM）和只读存储器（ROM）两种。控制器和运算器只能接受在内存中存放的指令和数据。,存储器,外存一般安装在主机板之外，例如磁盘就是一种常用的外存。外存上面的信息可长久保存，但这些信息必须读入内存之后才能被控制器和运算器所利用。磁盘按其材料的不同，又可分为软盘和硬盘两种。,
29、CPU(运算器和控制器 ),central processing unit,Register、控制单元,计算机中控制数据操作的电路并不与主存直接相连这些电路被封装在一起，即CPUCPU含有自己的存储单元（register）Register作为临时空间来存储CPU所操作的数，保存算术逻辑单元的输入与输出数据控制单元负责将主存中的数据移到register，然后通知算术逻辑单元所需要的数据在哪个register,总线,总线：CPU与主存之间用总线连接，利用总线CPU通过提供存储单元目标地址以及读信号来选择、读取数据CPU通过提供存储单元目标地址以及写信号来放置、写入信号谁发明了什么程序存储的概念：由
30、宾西法尼亚大学Moore电子工程学院的J.P.Echert提出，John von Neumann只是先发表了程序存储的概念,CPU和主存储器通过总线相连,3.3.3 机器指令与汇编语言,3.3 计算机语言的发展及其3个 学科形态的内在联系,机器指令与汇编语言,为了实现程序存储的概念，CPU要能识别二进制编码的指令机器语言指令集合以及编码系统,指令系统,CPU必须能够解码并执行的机器指令很少一旦计算机可以执行一些基本的而且是精选的操作，加入额外的操作理论上是不会改变计算机的能力的是否充分利用这种特性导致了两种不同的计算机设计：CISC(complex instruction set comput
31、er)RISC(reduced instruction set computer),CISC,最初人们采用的是进一步增强原有指令的功能，并设置更为复杂的指令的方法采用这种设计思路的计算机被称为复杂指令系统计算机（CISC）。CISC的思路是由IBM公司提出的，并以1964年IBM研制的IBM 360系统为代表。,CISC缺点,80%的指令只在20%的运行时间里用到；一些指令非常繁杂，而执行效率甚至比用几条简单的基本指令组合的实现还要慢。庞杂的指令系统也给超大规模集成电路（VLSI）的设计带来了困难，它不但不利于设计自动化技术的应用，延长了设计周期，增加了成本，容易增加设计中出现错误的机会，从而
32、降低了系统的可靠性。,RISC,思路主要是通过减少指令总数和简化指令的功能来降低硬件设计的复杂度，从而提高指令的执行速度。优点:与CISC技术相比简化了指令系统，适合超大规模集成电路的实现； 提高了机器执行的速度和效率；降低了设计成本，提高了系统的可靠性； 提供了直接支持高级语言的能力，简化了编译程序的设计。,机器指令,机器指令系统每台数字电子计算机在设计中，都规定了一组指令。机器语言用机器指令形式编写的程序。在裸机级，计算机语言关于算法的描述采用的是实际机器的机器指令，它的符号集是0，1，支撑实际机器的理论是图灵机等计算模型；在图灵机等计算模型理论的指导下，有关设计形态的主要成果有冯诺依曼型
33、计算机等具体实现思想和技术，以及各类数字电子计算机产品。,计算机语言在裸机级所取得的主要成果,汇编语言,采用字符和十进制数来代替二进制代码的思想。例3.10 对2+6进行计算的算法描述用机器指令对“2+6”进行计算的算法描述： 1011000000000110 0000010000000010 101000100101000000000000汇编语言对“2+6”进行计算的算法描述： MOV AL，6 ADD AL，2 MOV VC，AL,汇编语言语句与特定的机器指令有一一对应的关系，但是它毕竟不同于由二进制组成的机器指令，它还需要经汇编程序翻译为机器指令后才能运行。汇编语言源程序经汇编程序翻译
34、成机器指令，再在实际的机器中执行。就汇编语言的用户而言，该机器是可以直接识别汇编语言的，从而产生了一个属于抽象形态的重要概念，即虚拟机的概念。,3.3.4 高级语言,3.3 计算机语言的发展及其3个 学科形态的内在联系,高级语言,虽然与机器语言相比，汇编语言的产生是一个很大的进步，但是用它来进行程序设计仍然比较困难。于是人们着手对它进行改进。一是发展宏汇编，即用一条宏指令代替若干条汇编指令，从而提高编程效率。现在人们使用的汇编语言，大多数都是宏汇编语言。二是创建高级语言，使编程更加方便。如用高级语言对例子2+6进行计算的算法描述，其描述与数学描述一样，即2+6。,高级语言的分类,按语言的特点，
35、可以将高级语言划分为：过程式语言（如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的文本设计中第一次使用了
36、BNF范式来表示语法，并且第一次在语言文本中明确提出应将语法和语义区分开来。,高级语言的形式化,20世纪50年代至60年代间，面向语法的编译自动化理论得到了很大发展，使语法形式化研究的成果达到实用化的水平。语法形式化问题基本解决以后，人们逐步把注意力集中到语义形式化的研究方面, 20世纪60年代，相继诞生了操作语义学指称语义学公理语义学代数语义学等语义学理论,数据类型的抽象,相对于汇编语言和机器语言，高级语言的数据类型的抽象层次有了很大地提高，出现了整型实型字符型布尔型用户自定义类型抽象数据类型数据类型的抽象极大地方便了用户对数据的抽象描述，为实现软件设计的工程化奠定了基础。,高级语言中有关抽
37、象、理论和设计3个形态的主要内容,3.3.5 应用语言,3.3 计算机语言的发展及其3个 学科形态的内在联系,计算机语言的划分,一般将它划分为5代：第一代为机器语言；第二代为汇编语言；第三代为高级语言；第四代为“非过程性语言”；第五代为自然语言。,4GL,提供了功能强大的非过程化问题定义手段，用户只需告知系统“做什么”，而无需说明“怎么做” 以数据库管理系统所提供的功能为核心，进一步构造了开发高层软件系统的开发环境，报表生成多窗口表格设计菜单生成系统等4GL的代表性软件系统有：PowerBuilder、Delphi和INFORMOX-4GL等。,应用语言中有关抽象、理论和设计形态的主要内容,3
38、.3.6 自然语言,3.3 计算机语言的发展及其3个 学科形态的内在联系,自然语言计算机处理层次的划分,四个层次：第一层次是文字和语音，即基本语言信息的构成；第二层次是语法，即语言的形态结构；第三层次是语义，即语言与它所指的对象之间的关系；第四层次是语用，即语言与它的使用者之间的关系。,自然语言的输入问题,键盘（汉字的编码输入也是通过键盘进行输入）扫描手写语音等方式进入计算机计算机可以对输入的文字进行各种加工和处理（如放大、变形等），现在大多数的报纸、杂志、书籍等就是这一处理的产物。,自然语言的形式化问题,要使计算机对自然语言进行处理, 就必须使其形式化。乔姆斯说：一个说本族语的人具有一种理解
39、他过去从未听到过的句子的能力，他也能十分贴切地说出大量新的句子，而说同一种语言的人对听懂这些句子是毫不困难的。这个事实表明：人不仅具有创造新句子的能力，而且还有创造“合格”句子的能力。语言“创造性”过程的本质，其实就是由有限数量的词根据一定的规则产生正确句子的过程，进一步而言，其实质也就是一个字符串到另一个字符串的变换过程。,自然语言形式化的方法及实例,现有一个具体的形式语法G0=，其中： Vn为非终结符号的有限集合； Vt为终结符号的有限集合； Po为生成式（或称产生式）的有限集合，即形式规则； S为开始符号。,该形式语法的定义为：Vn=S，NP，VP，N，VVt=我，他，学，教，英语，汉语
40、，希望Po=SNP VP，NPN，VPV NP，VPV S，N我，N他，V学，V教，V希望，N英语，N汉语。,（1）S表示句子；（2）NP表示名词短语；（3）VP表示动词短语；（4）N表示名词；（5）V表示动词；（6）SNP VP表示：句子由名词短语和动词短语组成；（7）NPN表示：名词短语由名词构成。,（1）我学英语； （2）他学汉语； （3）我教他学汉语； （4）他教我学英语； （5）我希望他教我学英语； （6）他希望我教他学汉语；。,3.3.7 小结,3.3 计算机语言的发展及其3个 学科形态的内在联系,3.3.7 小结,综上所述，计算机语言经历了从机器语言、汇编语言、高级语言、应用语言
41、到自然语言的发展阶段，其功能变得越来越强大，人机交互也变得越来越方便，这种发展过程反映了人们的认识从感性认识（抽象）上升到理性认识（理论），再回到实践（设计）中来的科学思维方式。,由于高层次语言总要转为低层次语言来解释或执行，因此，带有更高抽象层次的语言系统将更加庞大，对软硬件资源的消耗也就更加严重，应用也将越来越受到硬件的限制，运行效率不可避免地也将越来越低，这就是一般新的系统软件为什么越来越庞大，而又往往在原有机器上运行效率较低（或不能运行）的主要原因之一。在整体能力上，不同层次的语言也有一定的差异，比如，汇编语言所具有的与机器有关的某些功能（如某些I/O功能），高级语言就不具备，同时，又
42、由于汇编语言的高效性，因此，在一些软件的研制中，汇编语言至今仍被人们所使用。,为了人与机器的交流更加友好、方便，计算机语言必然要朝着更高层次的方向发展。随着计算机硬件技术的迅猛发展，高层次语言对计算机软硬件资源相对消耗较大的缺点也就相对减弱了，从而为计算机语言的发展，实现人们认识的螺旋式上升提供了必要的条件。对计算机语言抽象、理论和设计3个学科形态的研究，有助于我们正确理解计算机语言的本质，以及更好地把握它的研究方向，从而能更好地进行计算学科的研究。,最后，讨论计算机语言局限性的问题。计算机语言是一种形式系统，由于形式系统所固有的局限性，因此，我们可以想象在计算机语言中必然存在一个表达式既不为真，也不为假，它的真假对一个形式系统（计算机语言）而言是不可判定的。计算机语言方面的内容极其丰富，本节只是从计算机发展的角度作了比较简单的概述，详细内容请读者查阅有关资料。,
