程序设计语言原理 门理论性较强的提高型课程,从更高的层 次来理解各种语言机制,指导对计算机语言的学 习和程序设计 分析并理解各类高级程序设计语言范型与理 论模型 掌握程序设计语言各主要成分设计中的关键 问题、主要步骤、表示法的基本技能, 学会分析、选择、调合、折中、设计语言的 特征 第2页
第2页 程序设计语言原理 一门理论性较强的提高型课程，从更高的层 次来理解各种语言机制，指导对计算机语言的学 习和程序设计 • 分析并理解各类高级程序设计语言范型与理 论模型 • 掌握程序设计语言各主要成分设计中的关键 问题、主要步骤、表示法的基本技能， • 学会分析、选择、调合、折中、设计语言的 特征
第0章导论 什么是程序设计语言(PL) 为什么研究PL ·语言规范与处理器 本课程内容与要求 第6页
第6页 第0章 导 论 • 什么是程序设计语言(PL) • 为什么研究PL • 语言规范与处理器 • 本课程内容与要求
601什么是程序设计语言(PL)? 人机通信媒体(介),软件的载体 人工语言机器识别,方便人使用 形式语言无二义性 必须可执行 它是计算机科学与计算机工程的交汇点 计算机科学是在符号学、集合论、离散数学、 组合数学基础上发展的 以符号语言表达的软件还要满足正确性、可 靠性、安全性、可扩充、可移植、方便性 第7页
第7页 0.1 什么是程序设计语言（PL）? • 人机通信媒体(介)，软件的载体 – 人工语言 机器识别，方便人使用 – 形式语言 无二义性 – 必须可执行 • 它是计算机科学与计算机工程的交汇点 – 计算机科学是在符号学、集合论、离散数学、 组合数学基础上发展的 – 以符号语言表达的软件还要满足正确性、可 靠性、安全性、可扩充、可移植、方便性
1900 Giuseppe Peano集合论(1895) 910 Alfred north Whitehead, Bertrand russell符号逻辑(1910) 920 自动数学POST 不完全理论, Goedel(1931) 1930POST系统—递归函数论可计算理论 Church, Rosser(1930s) Turing(1936) 940 信息论 Shannon 电子学 形式语言理论 950 Chomsky 开关理论 960形式语法定义 自动化理论 Backus和Naur 1970Kuh:词法分析方法 复杂性理论 编译理论 编译的编译 EL/l:可扩展式语法 diffie 计算机密码学(1976) 980 e.Hellman 随机算法 公共密钥系统(1978) Rivest shamir. Adelman 1990 第8页
第8页 1900 1930 1940 1950 1960 1970 1980 1990 1910 1920 自动数学 POST Alfred North Whitehead BertrandRussell 符号逻辑(1910) 不完全理论 , Goedel(1931) Giuseppe Peano集合论(1895) POST系统 递归函数论 Church,Rosser(1930s) 可计算理论 Turing(1936) 信息论Shannon 形式语法定义 Backus 和Naur 随机算法 形式语言理论 Chomsky 自动化理论 电子学 开关理论 复杂性理论 计算机密码学(1976) Diffie,Hellman 公共密钥系统(1978) Rivest,Shamir,Adelman Knuth:词法分析方法 编译理论 编译的编译 EL/1:可扩展式语法
1930POST系统 递归函数理论 可计算理论 Church, Rosser(1930s) Turing ( 1936) 940 λ演算 Church(1941) 950 程序正确性和验证(1960s 1960 引用透明, Strachey 形式语义定义 SECD机 Landing(194) PL/的 Vienna定义(1967) 指称语义学(1971) 并发性 Scott, Strachey) Dijkstra(1968) Mime类型理论(1978) Hoare: CPS(1978 分布式计算 amport 980 函数式语言 ML Miranda haskell 协作计算1988 990 第9页
第9页 1930 1940 1950 1960 1970 1980 1990 POST 系统 递归函数理论 Church,Rosser(1930s) 可计算理论 Turing(1936) λ演算 Church(1941) 程序正确性和验证(1960s) 引用透明,Strachey 形式语义定义 SECD机,Landin(1964) PL/1的Vienna定义(1967) 指称语义学(1971) Scott,Strachey) Milner:类型理论(1978) 函数式语言: ML Miranda Haskell 并发性 Dijkstra(1968) Hoare:CPS(1978) 分布式计算 Lamport 协作计算1988
重要性 程序设计语言的研究和开发处于计算机科学技术发展的中心: ●计算机理论和方法的研究,许多是由于语言发展的需求 许多理论研究成果体现到程序语言的设计中 ●实际应用中最本质的需要常反映到程序语言里,推动语言的演化和发展 ●语言实现的需要是推动计算机体系结构演化的一个重要因素(如RISC) ●计算机硬件的能力和特征也对程序语言的发展变化有着重要影响(今天和明天,并行性问题) ●理解程序设计语言,有助于提高对整个计算机科学技术领域的认识 推动语言演化发展的要素: 实际应用的需要, 理论研究的成果 硬件的发展和变化,人们对于程序设计工作的认识发展,实现技术鹩开发
第10页 重要性 程序设计语言的研究和开发处于计算机科学技术发展的中心： ⚫ 计算机理论和方法的研究，许多是由于语言发展的需求 ⚫ 许多理论研究成果体现到程序语言的设计中 ⚫ 实际应用中最本质的需要常反映到程序语言里，推动语言的演化和发展 ⚫ 语言实现的需要是推动计算机体系结构演化的一个重要因素（如RISC） ⚫ 计算机硬件的能力和特征也对程序语言的发展变化有着重要影响（今天和明天，并行性问题） ⚫ 理解程序设计语言，有助于提高对整个计算机科学技术领域的认识 推动语言演化发展的要素： 实际应用的需要，硬件的发展和变化，人们对于程序设计工作的认识发展，实现技术的开发， 理论研究的成果
重要性:图灵奖 19662010,45届图灵奖,有15届由于与程序设计语言有关的工作而获奖 1966 Alan J Perlis,早起语言和Agol1983, Dennis ritchie和 Thompson,C语言 60的贡献,图灵奖第一位获奖者 和UNIX 1971, John McCarthy,LISP语言,程序|1984, Niklaus wirth, Alogl W,PL360, 语义,程序理论 Pascal, Modula-1/2, Oberon,逐步求精, 972, E W.Dijkstra, algol编译,结构 结构化程序设计,语法图 化程序设计,并发概念和原语,形199, Robin milner,M语言,并发理论, 式化推到,卫式命令等 CCS 1977 John backus. Fortran语言,FP语言,200,0 le-Johan Dahl和 Kristen Nygaard BNF等 Simula语言,OO概念 1978, Robert floyd, Algol编译,编译2003 Alan Kay, Smalltalk语言,OO概念、 技术,程序优化,归纳断言法和前 语言和程序设计 后断言,程序正确性,编译生成200, Peter Naur,Alg0l60语言的设计和 1979, ELVerson,APL语言 定义,编译,程序设计的原理和实践 1980, C.A.R. Hoare,结构化程序设计,206, Frances Allen,优化编译和并行化 cas语句,公理语义学,并发程序的200, Barbara liskov,数据抽象/O0容 理论,CSP等 错/分布式计算程序的基础和语页」
第11页 重要性：图灵奖 1966-2010，45届图灵奖，有15届由于与程序设计语言有关的工作而获奖 1966，Alan J.Perlis，早起语言和Algol 60的贡献，图灵奖第一位获奖者 1971，John McCarthy，LISP语言，程序 语义，程序理论 1972，E.W.Dijkstra，Algol编译，结构 化程序设计，并发概念和原语，形 式化推到，卫式命令等 1977，John Backus,Fortran语言，FP语言， BNF等 1978，Robert Floyd，Algol编译，编译 技术，程序优化，归纳断言法和前 后断言，程序正确性，编译生成 1979，K.E.Iverson,APL语言 1980，C.A.R.Hoare，结构化程序设计， case语句，公理语义学，并发程序的 理论，CSP等 1983，Dennis Ritchie和Thompson，C语言 和UNIX 1984，Niklaus Wirth, Alogl W, PL360, Pascal, Modula-1/2, Oberon，逐步求精， 结构化程序设计，语法图 1991，Robin Milner, ML语言，并发理论， CCS 2001，Ole-Johan Dahl和Kristen Nygaard, Simula语言，OO概念 2003，Alan Kay, Smaltalk语言，OO概念、 语言和程序设计 2005，Peter Naur, Algol 60语言的设计和 定义，编译，程序设计的原理和实践 2006，Frances Allen，优化编译和并行化 2008，Barbara Liskov，数据抽象/OO/容 错/分布式计算程序的基础和语言
2005/2006/2008图灵奖 2005: Peter Naur, For fundamental contributions to programming language design and the definition of algol 60, to compiler design, and to the art and practice of computer programming 2006: Frances E. Allen,"pioneering contributions to the theory and practice of optimizing compiler techniques that laid the foundation for modern optimizing compilers and automatic parallel execution 2008: Barbara liskov, has led important developments in computing by creating and implementing programming languages, operating systems, and innovative systems designs that have advanced the state of the art of data abstraction, modularity, fault tolerance, persistence, and distributed computing systems The Clu programming language was one of the earliest and most complete programming languages based on modules formed from abstract data types and incorporating unique intertwining of both early and late binding mechanisms 第12页
第12页 2005/2006/2008图灵奖 2005：Peter Naur, “For fundamental contributions to programming language design and the definition of Algol 60, to compiler design, and to the art and practice of computer programming.” 2006：Frances E.Allen, “pioneering contributions to the theory and practice of optimizing compiler techniques that laid the foundation for modern optimizing compilers and automatic parallel execution.” 2008：Barbara Liskov, “has led important developments in computing by creating and implementing programming languages, operating systems, and innovative systems designs that have advanced the state of the art of data abstraction, modularity, fault tolerance, persistence, and distributed computing systems. ... The CLU programming language was one of the earliest and most complete programming languages based on modules formed from abstract data types and incorporating unique intertwining of both early and late binding mechanisms.
新趋势:并行 狭义的摩尔定律已失效,提 高主频的趋势已停止 100000 ●并行环境已逐渐成为我们周 围最常见计算机的基本结构 的一部分 000 如何做并行程序设计的问题 1000 变成对每个计算机工作者的 挑战 100 程序设计语言也需要反应这 方面的需求 ●有关并行语言、程序和程序 设计的问题,将在今后很多 Clock Speed (MHz) 年里成为程序设计语言研究 a Transistors (000) 领域里最重要的问题 13711975179198319871991199519920032007 第13页
第13 页 新趋势：并行 ⚫ 狭义的摩尔定律已失效，提 高主频的趋势已停止 ⚫ 并行环境已逐渐成为我们周 围最常见计算机的基本结构 的一部分 ⚫ 如何做并行程序设计的问题 变成对每个计算机工作者的 挑战 ⚫ 程序设计语言也需要反应这 方面的需求 ⚫ 有关并行语言、程序和程序 设计的问题，将在今后很多 年里成为程序设计语言研究 领域里最重要的问题
新趋势:并行 有关并行系统和并行程序设计的研究已经进行了近40年,但对并行系 统和如何设计实现并行系统的认识仍很不成熟 已开发的并行系统(及分布式系统)经常出现意料之外的错误 ●并行系统的开发方法很难使用,开发低效,对开发人员缺乏良好支 持 描述并发系统的记法形式过于低级和细节,缺乏有效抽象手段 并发系统的验证技术不成熟,系统缺乏可靠性的保证 对于上述问题的研究和并发程序开发实践将未来语言的发展影响有重 大影响 许多新语言里加入了并行特征,包括Java、C#等 些并行理论的研究成果被用于实践,如JCSP 人们重新开始重视无状态的程序设计,函数式程序设计(如 Erlang 语言受到许多人推崇),提出了一些新想法 ●这方面的理论和实际技术研究将成为很长时间的研究热点 第14页
第14页 新趋势：并行 有关并行系统和并行程序设计的研究已经进行了近40年，但对并行系 统和如何设计实现并行系统的认识仍很不成熟： ⚫ 已开发的并行系统（及分布式系统）经常出现意料之外的错误 ⚫ 并行系统的开发方法很难使用，开发低效，对开发人员缺乏良好支 持 ⚫ 描述并发系统的记法形式过于低级和细节，缺乏有效抽象手段 ⚫ 并发系统的验证技术不成熟，系统缺乏可靠性的保证 对于上述问题的研究和并发程序开发实践将未来语言的发展影响有重 大影响 ⚫ 许多新语言里加入了并行特征，包括Java、C# 等 ⚫ 一些并行理论的研究成果被用于实践，如JCSP ⚫ 人们重新开始重视无状态的程序设计，函数式程序设计（如Erlang 语言受到许多人推崇），提出了一些新想法 ⚫ 这方面的理论和实际技术研究将成为很长时间的研究热点