1、1程序设计语言概论焦文品http:/ n了解高级程序设计语言的基本概念和原理n了解高级程序设计语言实现技术及原理n了解若干主要的高级程序设计语言3课程主要内容n高级程序设计语言的基本概念、原理、及实现技术n语法程序看起来像什么n语义程序的含义是什么n实现程序是如何执行的n了解求解特定问题最合适的语言，例如：nPascal,C-过程式的，面向语句的nC+,Java,Smalltalk-面向对象的nML,Lisp-函数式的nProlog-基于规则的4课程主要内容n围绕高级语言程序的基本性质及构成展开n语法、语义n编码及运行n数据、处理及其抽象n数据：简单、复杂n处理：语句级（语句内及语句间）、模块
2、级、系统级5授课方式及考核方法n授课方式：n课堂讲授为主 n考核方法：n作业占40%n期末考试占60%6参考书7第一章 程序设计语言研究主要内容n程序设计语言的定义及其特征n为什么研究程序设计语言n程序设计语言的评价n程序设计语言简史n代表性语言n程序设计语言的角色n影响语言的主要因素n程序设计语言的范型9什么是语言(1/4)n语言是信息交流工具。有如下几种定义：1、Webster字典定义nAn artificially constructed primarily formal system of signs and symbols(as symbolic logic)including ru
3、les for the formation of admissible expressions and for their transformationn由人工构造的、基于一组记号与符号的、（基本上是）形式化的系统（如符号逻辑），包括合法表达式的形成规则和转换规则。10什么是语言(2/4)2、Longman字典定义nAny system of signs,movements,etc.,used to express meanings or feelingsn任何表情达意的记号系统。3、英汉双解计算机辞典定义（清华大学出版社）nA set of characters,conventions an
4、d rules,that is used for conveying information.The three aspects of language are pragmatics,semantics and syntaxn用于传递信息的字符、约定和规则的集合。语言的三个方面是语用、语义和语法。11什么是语言(3/4)4、中国大百科全书，电子学与计算机卷n语言的基础是一组记号和一组规则，根据规则由记号构成之记号串的总体就是语言。5、徐家福：软件语言及其实现n语言是基于一组记号与一组规则、根据规则由记号构成之记号串的总体。任何语言均包括语法、语义和语用三个方面。12什么是语言(4/4)n语言的
5、作用n描述作用、交流作用和标志作用（软件语言可作为计算技术发展的里程碑标志）n语言是人类生活的必要工具，不同的语言被使用于不同的领域和方面n在计算领域，也存在不同层次的语言，本书所论及的是实现层次的语言，即程序设计语言。n程序设计语言程序设计语言=字符集字符集+规则集（用于组合字符）规则集（用于组合字符）n任何用于描述算法和数据结构的一套符号系统均可称为程序设计语言13程序设计语言的四个基本特征1.用户不需要具有机器代码的知识，只需学习特定的程序设计语言，并独立于任何特定的机器代码而使用。这并不意味着用户可以完全忽略实际的计算机，如：需知道浮点数的表示或使用某些机器资源。2.程序设计语言必须有
6、较大程度的机器独立性（完全的机器独立性）。这意味着必须有较大潜力，使得源程序可运行在具有不同机器代码的两台计算机上，不需要完全重写。3.当源程序翻译成机器代码时，通常对每个执行单元有多个机器指令，如：A=A+B需多个机器指令来实现4.程序设计语言的记号比机器语言更接近于被求解的问题。如：A=A+B比其机器翻译更易于理解。14本课程研究的对象n主要考虑那些在计算机上实现的程序设计语言n术语“程序设计语言”并没有一个公认的范围定义n通常这个术语是指高级语言返回15纯二进制机器码或符号机器码符号汇编语言宏汇编语言高级语言甚高级语言Byte或word，指令、数据不分用一些符号来代表指令，如sub代表减
7、，Add代表加等，机器地址用十进制。有时汇编语言等同于符号机器码。变量名用符号，地址也可用符号而非数字。编制的程序称为汇编语言程序。用户可以定义新指令及子程序源程序编译为目标程序，或解释执行高级程序语言的高层规约语言，提供比高级程序语言更高级的语言设施。又称为“可执行的规约语言”。有时也不区别于高级语言。计算机上语言的层次返回161.1 为什么研究程序设计语言n两个基本观察：1.已有数百种语言被设计和实现。在1969年，Sammet就列出了当时120种相当广泛使用的语言，在此以后，又有很多语言被开发。在早期，为一个项目的进行而开发一种语言是常有的事。2.大多数程序员通常不会同时使用多种语言，一
8、般限制到12种。事实上，都是直接使用计算机上已有的语言如C、Ada、Fortran等。n既然如此，为什么要去研究各种不同的语言，n有的语言甚至永远不可能再被使用？17学习、研究程序设计语言的理由n不仅仅是停留于肤浅的对语言特性的了解和考虑n深入了解根本性的语言设计概念及它们对语言实现的影响学习、研究程序设计语言的理由(1/6)1、提高开发有效算法的能力n很多语言提供的特性如果被合适地使用，会给程序员带来益处，但如被不合适地使用，将可能导致大量计算机时间浪费或使程序员出现耗时的逻辑错误。n有可能一个长期使用某一语言的程序员也并不理解该语言的所有特性。19学习、研究程序设计语言的理由(1/6)1、
9、提高开发有效算法的能力n如递归特性：是一个非常便利的程序设计语言特性n如正确、合适使用，可得到优美和高效算法的直接实现。n如不正确使用，将可能导致执行时间的天文数字增长。n如果程序员不知道递归蕴含的设计问题和实现困难，将难于使用这种结构；对递归原理和实现技术的了解可使程序员了解在特定语言中的递归的相对代价并通过其理解确定其使用是否合适。n新的程序设计方法不断在文献中引入，如OO程序设计，逻辑程序设计和并发程序设计的使用均需要对实现这些概念的语言的详细了解和掌握。20学习、研究程序设计语言的理由(2/6)2、改善对现行程序设计语言的使用方式 n通过对语言特性的实现细节的了解，可大大增加书写高效的
10、程序的能力。如：n对数据结构，诸如数组、串、表、记录等，如何被创建和操作的了解n对递归的实现细节的了解n以及对对象类如何被创建的了解n将对书写高效程序有很大帮助21学习、研究程序设计语言的理由(3/6)3、增加可使用的有用的程序设计结构的词汇量n语言对思维既有帮助，也有限制n人们使用语言去表达思想，但语言也控制人如何思维，用字句中没有直接表达的方式来思维是十分困难的。n在解决一个问题时，要寻找合适的数据和程序结构，通常人们首先考虑他熟悉的语言中可直接表达的结构。n研究各种语言提供的结构和这些结构被实现的方式，程序员可增加其编程词汇。22学习、研究程序设计语言的理由(3/6)3、增加可使用的有用
11、的程序设计结构的词汇量n对实现技术的了解非常重要。如要使用一个结构，该结构在语言中没有直接提供，程序员必须提供自己的实现（使用语言提供的基本结构）。n如子程序控制结构、协同例程（coroutine）在很多程序中有用，但很少有语言直接提供协同例程特性。nC或Fortran程序员可以设计程序来使用协同例程结构，然后将它们实现为C或Fortran程序（如果熟悉相关概念及实现）从而可以提供大型程序的正确控制结构。23学习、研究程序设计语言的理由(4/6)4、更好地选择程序设计语言n对程序设计语言知识的掌握可以允许程序员针对特定的项目，恰当地选取合适的语言，从而减少编码工作量。如：C、Fortran、A
12、da可用于数字运算，Lisp、ML、Prolog可用于人工智能应用。对每种语言的特性的长处和弱点的了解和掌握有利于程序员做出广泛而正确的选择。24学习、研究程序设计语言的理由(5/6)5、更易于学习新语言n对自然语言语法结构的学习和了解可使对新语言的学习更容易n对程序设计语言各种结构和实现技术的了解，也可使程序员能够在需要时更容易学习新语言25学习、研究程序设计语言的理由(6/6)6、更易于设计新语言n很少有程序员把自己考虑为语言设计者，然而，任何程序都有一个用户界面，这事实上也是某种形式的程序设计语言，用户界面包括提供给用户用于和程序通讯的命令和数据格式。n大型程序，如文本编辑器、操作系统、
13、图形包的用户界面的设计者，必须考虑很多存在于通用程序设计语言设计中的相同问题。n如果程序员熟悉一般程序设计语言中的结构和实现方法，则程序设计将可以大为简化。26学习、研究程序设计语言的理由n总之，程序设计语言的研究十分重要，包括语言特性和实现技术（特别是不同结构的运行时表示技术）等主要研究内容。n理解n使用n设计和实现返回271.2 程序设计语言简史28程序设计语言简史(1/5)29程序设计语言简史(2/5)30程序设计语言简史(3/5)31程序设计语言简史(4/5)n针对非数值数学计算（如形式代数操作）的需要。nIBM的Jean Sammet于1962-1964开发了Formac。nMIT的
14、Joel Moses于1970年代早期开发了Macsyma。n专用领域语言开发。n1956年，MIT的Douglas Ross为机床控制开发了APT。n其他有：ncivil engineer iy:Cogoncomputer-assisted instruction:Coursewriternequipment checkout:Atlas。n19671977，在美国，在给定年度内使用的语言数大概是170种，同时，每年或每两年有2530的增减。32程序设计语言简史(5/5)返回33代表性语言(1/3)34代表性语言(2/3)nComitn1957，第一个实用的串处理和模式匹配语言。nCobol
15、（Common Business-Oriented Language）n1960，最广泛使用的数据处理语言。具有类英文的语法和机器独立性。nAlgol60（ALGOrithmic Language）n1960，用于刻划算法。形式化语法定义，带动了语言的理论和实现技术研究。nLisp（LISt Processing）n1960，引入了函数程序设计概念，基于表处理。nJovial（Jules Own Version of IAL）n1960，第一次包含了科学计算，I/O信息的逻辑操作、数据存贮和处理等能力。大多数Jovial编译器用Jovial书写。35代表性语言(3/3)nGPSS（Genera
16、l-Purpose System Simulator）n1961，第一个仿真语言。nJoss（JOHNNIAC Open-Shop System）n1964，第一个交互式语言。nFormac（FORmula Manipulation Compiler）n1964，第一个广泛使用的形式代数操作语言。nAPL/360（A Programming Language）n1967，引入了许多高级操作子，允许很短的算法，产生了看问题的新方式。nPascaln1971，在一个小语言中引入了如赋类型的新概念，并以优美方式组合了各种著名结构。返回36程序设计语言的角色n早期，计算机非常昂贵，而程序员年薪不高，关
17、键资源是计算机。因此，语言设计是为了更高效地执行程序，高级语言需和汇编语言竞争。nFortran的主要设计者Backus在Fortran面世十年后曾说：n坦率地讲，我们当时未曾有过任何最模糊的关于FORTRAN及其编译器将如何工作的想法。我们只是简单地努力优化目标程序，运行时间，因为当时大多数人不相信你可以真正完成这样的事。他们认为机器编码的程序将是极端低效的，对很多应用都是不实用的。n我们未曾想到的一个结果是：有这样一个系统，它被设计为完全独立于程序将最终运行于其上的机器。这后来证明是非常有价值的能力，但当时我们肯定未曾想到。n我们的活动没有任何组织。程序的每个部分由一到二人完成，除了极少数
18、例外，他们完全负责他们所做的事情。事情无序地发展，当FORTRAN发布时，我们面临这样一个事实：25000条指令将并不是全正确的，存在着大量将在大量使用后才会显示出来的问题。37程序设计语言的角色(2)n60年代中期，程序设计发生了变化，机器价格下降，程序设计价格上升。程序移植的需求越来越多，软件的维护占用了大量的计算资源。此时的目标不再是编译程序后使其高效地运行，高级语言的任务变成使其易于开发正确的程序以解决给定应用领域中的问题。n编译技术成熟于60、70年代，语言技术以解决特定领域问题为中心，如：Fortran用于科学计算，COBOL用于商业应用，JOVIAL用于军事应用，LISP用于人工
19、智能应用，以及Ada用于嵌入式军事应用等。程序设计语言的角色(2)n程序设计语言也会进化和消亡，如：Algol已不再使用，Cobol使用正在下降，Pascal的很多结构仍在Ada中存在，但其黄金时代已过去。n仍在使用的旧语言也经历了不断的修订以反应来自其他计算领域的影响，Fortran和Cobol已有多个标准化标本。Ada有1995年新标准。Lisp修订后有Scheme和Common Lisp。C+和ML则反应了人们在设计和使用语言中获得的经验的混合。返回39影响语言的主要因素(1)1、计算机能力n计算机经历了数代的巨大变化，操作系统成为语言基于的平台（不再仅依靠硬件）。这些因素影响了高级语言
20、的结构和使用语言特性的代价。2、应用n应用领域有了很大变化，计算机应用已渗透到几乎所有领域，新应用的需求影响了新语言的设计和旧语言的修订。特别是近几年，INTERNET的发展进一步拓广的应用范围。3、程序设计方法n人们对书写大型复杂系统的方法的深入研究和程序设计环境的变化也影响语言的发展。40影响语言的主要因素(2)4、实现方法n更好的实现方法影响到新语言中特性的选择。5、理论研究n使用形式化的数学方法，对语言设计和实现的概念基础的研究加深了我们对语言特性的优势和弱点的理解，从而影响语言中特性的选取，如“继承”，因语义复杂，而被有的语言放弃。6、标准化n标准化语言需要易于在不同计算机上实现，使
21、程序易于移植，这对语言的设计影响是保守的，即轻易不引入新特性。41软硬件技术对语言的影响(1)42软硬件技术对语言的影响(2)43软硬件技术对语言的影响(3)44软硬件技术对语言的影响(4)45软硬件技术对语言的影响(5)n199195n硬件：非常快的廉价工作站和微机，大规模并行体系结构，语音，视频，传真，多媒体n方法：开放系统，环境框架，国家信息基础设施（信息高速公路）n语言：Ada 95，过程语言（TCL，PERL）n19962000n硬件：二代Internet，机群，网络计算机（NC）n方法：软件构件技术，Agent，中间件，浏览器/服务器计算，Internet计算n语言：JAVA，XM
22、L，IDL（后两种一个意义上不能算为程序设计语言）返回461.3 程序设计语言的评价n1、可读性n判断程序设计语言的最重要的标准之一就是看程序是否易读和易懂n易维护性在很大程度上取决于可读性n可读性已成为程序语言及程序质量的重要评测指标之一。n2、可写性n可写性是判定程序设计语言是否易于编写给定问题域的程序的度量标准之一n可读性往往会影响可写性n可写性是与应用领域相关的47程序设计语言的评价(2)n3、可靠性n如果程序能在任意条件下执行任务，则程序是可靠的n4、代价n程序的执行、程序的翻译、程序的创建、以及程序的维护影响评判标准的因素特征特征标准可读性可读性可写性可写性可靠性可靠性简单性/正交
23、性YYY控制结构YYY数据类型和结构YYY语法设计YY对抽象的支持YY表达能力YY类型检测Y例外处理Y限制别名Y49好语言应具备的性质(1)1、清晰、简单、一致n程序设计语言既是思考算法的概念框架，又是表达算法的工思考算法的概念框架，又是表达算法的工具具。语言对程序的帮助不仅在编码阶段，还会在此阶段前较长一段时间，均有帮助。语言应该是提供清晰、简单、一致的概念，用作算法开发的基本原语。概念的数量尽可能少、概念的数量尽可能少、组合规则尽可能简单和规范。组合规则尽可能简单和规范。n语言的语法对程序的书写、测试、理解和修改有较大影响，因此，可读性是一个中心问题。特别精简或隐义的语言使程序易于书写（对
24、有经验的程序员），但难于读（当要修改时），如APL，甚至程序员本人过一段间后也难读懂。有的语言几乎相同的语句实际上代表了完全不同的事。因此，一条一条基本原则是，语义不同应在语法中完全反映出来。基本原则是，语义不同应在语法中完全反映出来。50好语言应具备的性质(2)2、正交性n不同不同的语言特征的任意一种组合都是有意义的，如条件语句和任意表达式的组合。n正交性使语言易学，程序易写，因为不需记住太多的例外和特殊情况，缺点是：逻辑上不协调或极端低效的组合可能会被编译器忽略。n正交性在语言设计中是一个有争议的属性。51好语言应具备的性质(3)3、运用的自然性程序的结构反映了算法的逻辑结构n只要正确地使
25、用语言的语法，程序结构就可以反映程序结构就可以反映出算法的逻辑结构出算法的逻辑结构。理想地：直接将程序的设计翻译为合适的反映算法结构的程序语句。顺序算法、并发算法、逻辑算法等各有不同的自然结构。n语言应提供合适的数据结构、操作、控制结构和面向问题的自然语法。语言流行的主要原因之一便是对自然性的需要。n特别适合某类应用的语言将大大简化该领域程序的创建，如Prolog适合于推导，C+适合于OO设计。52好语言应具备的性质(4)4、对抽象的支持程序的数据反映了要解决的问题n即使对最自然的语言，在刻划问题求解的抽象数据结构和操作与语言固有的特别的基本数据结构和操作间总是存在着差距。n如C可能是一个合适
26、的用于构造大学课程调度应用的语言，但抽象的数据结构如“学生”、“课程”、“授课老师”、“教室”等以及抽象操作“分配某学生到某课程”，“安排某课在某教室”等并不在C语言中提供，而它们对应用本身是非常自然的。n程序员的任务之一便是为问题求解设计合适的抽象，然后用实际语言提供的更基本的特性来实现这些抽象。n理想地：语言应允许数据结构、数据类型和操作作为自包含的抽象而定义，程序员可以将它们用在程序的其他部分（只需了解其抽象性质，而无需知道实现细节）。53好语言应具备的性质(5)5、程序易于验证验证程序正确执行了所要求的功能n程序的可靠性总是一个中心的问题，有很多技术验证一个程序是否正确地完成所需功能。
27、n程序可以用形式化方法证明是正确的，n也可以用桌面检查方式非形式地证明正确性（读程序文本）n也可以用测试的方法，用测试数据输入，检查输出结果是否满足规约，n对大型程序，可能需要这些方法的组合n语言应该对程序验证提供支持，其支持力度是选择语言的主要标准之一。n语义和语法结构的简单性是简化程序验证的主要因素。54好语言应具备的性质(6)6、编程环境n语言的技术结构仅仅是影响其使用的一个方面，而合适的编程环境可以弥补语言技术上的弱点。n编程环境包含很多因素：n可靠的、有效的、有良好文档的语言实现自然是首要因素。n特殊的编辑器和测试包可以加速程序的创建和测试。n维护和修改程序的多个版本的机制有利于大型
28、程序的开发。55好语言应具备的性质(7)7、程序的易移植性最终的程序可以从开发它们的计算机上透明地移植到其他计算机系统上运行n程序的易移植性是很多项目的重要目标。n广泛使用的和独立于机器特性而定义的语言是易移植性的有用的基础，如：Ada、Fortran、C、Pascal等有标准化定义的语言书写的程序易移植性较好。568、使用代价n代价是评价语言的主要元素，但具有不同的代价度量。57使用代价(1)a.程序执行代价n在早期，代价主要是程序执行代价。因此，优化编译器的实现、高效的寄存器的分配和高效的运行时支持机制的设计是非常重要的。n程序执行代价对语言设计是重要的，但主要对将要多次执行的大程序来说更
29、为重要。n目前，对很多应用、执行速度不再是主要考虑。n对程序开发的易诊断和易控制、以及程序的维护也需要考虑，在此情况下，执行时间增加10%20%，也是可容忍的。使用代价(2)b.程序翻译代价n当Fortran或C等用于教学时，高效的翻译（编译）比高效执行更为重要。通常学生程序会多次编译，而执行次数不多，需要快速、高效的编译器。59使用代价(3)c.程序生成、测试和使用的代价n对某类问题，程序员最好只需要投入最少的精力就能设计、编码、测试、修改和使用相应的求解方案。如：Smalltalk是价格有效的，求解一个问题的时间和努力均较少。n对使用语言的总代价的考虑在很多情况下变得和传统的代价同等重要。
30、60使用代价(4)d.程序维护的代价n研究表明，对较长时间运行的程序的代价不是初始设计、编码、测试的代价而是整过生命周期代价（涉及开发和维护）。n维护包括发现错误的修改、平台的变化所需的修改、程序的扩展和加强。语言对维护的支持是非常重要的（长期运行的程序由多个人员维护，语言应有支持）返回611.4 语言范型n通常，不同语言的拥护者聚在一起，争论的问题常是：n数组声明的形式（C、Fortran中各不同）n解释和编译的价值，等。n然而，这些不同对语言间的差异并无本质影响，语法上的不同只反映了设计者的希望，对写成的程序并无多大影响。62基本的计算模型(1/4)1、命令型语言（Imperative l
31、anguage）n也称过程型（procedural）、命令驱动的、或面向语句的。n其基本概念是机器状态，程序由一组语句构成，每各语句的执行，将使得解释器改变某些存储位置的值，进入新状态。n程序形式一般为：statement 1;statement 2;63基本的计算模型(1/4)1、命令型语言n如图示，内存包含一组盒子，语句的执行（如将两个变量相加而得到第三个变量）可被表示为访问存储位置，以某种方式组合这些值，将结果存到新的位置。64基本的计算模型(1/4)1、命令型语言（Imperative language）n程序的开发涉及建造连续的、要到达最终答案所需的机器状态。即，建立连续的机器状态，
32、最终达到结果。n大多数传统语言采用这种模型，遵循传统计算机的结构，顺序地执行指令。65基本的计算模型(2/4)2、作用型（或函数式）语言（applicative）n另一种看待语言完成的计算的视角是：看程序所表示的功能，而不是程序执行时的状态变化。n我们只观察希望的结果，而不是可用的数据。即不关心机器为得到结果所经过的状态顺序。66基本的计算模型(2/4)2、作用型语言（applicative）n这样问题就变成：这个函数（功能）是什么？它通过访问初始变量集，而被作用到初始机器状态，以特殊方式组合，得到结果。n程序开发：以已有函数为基础开发新的复杂函数，最终的函数作用将得到结果。n程序执行：连续的
33、函数变换，f1(f2(f3()。n通常也称函数式语言。引用透明性是一个主要特征。67基本的计算模型(3/4)3、基于规则的语言（逻辑型语言）n检查当前条件，当其得到满足时，执行合适的动作。n如图，使用过滤集作用到数据存储上让使能状态(enable state)变化。基本的计算模型(3/4)3、基于规则的语言（逻辑型语言）n其执行类似命令式语言，但语句不是顺序的，使能条件将决定执行顺序。使能条件1动作1使能条件2动作2使能条件n动作nnProlog语言采用这种范型。其它如决策表的业务应用也是一种基于规则的程序设计。69基本的计算模型(4/4)4、OO语言n当前最重要、流行的计算模型。n建立复杂数据对象，限定该对象上的操作集合，并封装在一起。n复杂对象是简单对象的扩展，继承简单对象的性质。n实际上使用了其他两种计算模型的优点，n具体数据对象有命令型语言的效率，n限定功能类到具体数据对象作用型模型的灵活性和可靠性。70计算模型的一般性n前面的讨论，我们使用“支持”，而不是“实现”某计算模型。n语言的使用依赖于程序员。n命令型语言适合面向语句的程序设计，但也可以用LISP、Prolog写出实质上顺序执行并完成相同功能的程序。n用C语言也可以写出具有函数调用的程序作用型。n历史上：命令型语言最早广泛使用，一直占据统治地位。
