第二章 语言设计问题

语言设计考虑的因素 早期的语言设计的目标是希望程序能高效地运行于昂贵的硬件上，因此，早期语言总是以翻译成高效的机器码为目标，即使程序难以书写。 现在，硬件价格下降、软件价格上升，更强调程序容易书写，即使慢点也可。 例如，ML的类型特性、C++的类、Ada的包(Package)均以降低执行速度为代价，但对保证程序正确性有帮助。 开发语言时，有三个影响语言设计的主要因素： 计算机本身 在计算机上支持语言的执行模型，即虚拟计算机 语言所实现的计算模型

主要内容 计算机结构与程序设计语言的关系 程序的执行模型：虚拟计算机 C/C++概述 结构上的对应关系 对应关系的实现手段 虚拟机与程序语言实现的关系 程序语言与虚拟机的绑定 C/C++概述

2.1 计算机的结构和操作 一个计算机是能够存储和执行程序的数据结构和算法的集成集合。 计算机可通过用电线、集成电路、电路板等构造为实际的物理设备，此即实际计算机或称硬件计算机。 计算机也可以用运行于其他计算机上的程序（或软件）来构造，此即软件仿真计算机。 程序设计语言的实现是通过一个翻译器，将以语言书写的程序翻译为机器语言程序（可被某计算机直接执行，该计算机可以是硬件计算机，也可以为软硬参杂的虚拟机）。

计算机结构与程序设计语言 一个计算机包含6个主要部件，它们与程序设计语言的主要方面有着非常密切的对应关系。 1、数据：提供各种可供操作的基本数据项和数据结构。 2、基本操作：提供对操作数据有用的基本操作集。 3、顺序控制：提供控制基本操作执行顺序的机制。 4、数据访问：提供控制向操作的执行供给数据的机制。 5、存储管理：提供控制程序和数据存储分配的机制。 6、操作环境：提供与包围程序和被处理数据的外部环境通讯的机制。

计算机硬件 包括程序和被处理的数据 操作主存和高速缓存中的数据 在主存和外部环境间传递程序或数据 返回 完成处理工作 取机器指令 解码 调用指定的基本操作，以指定的操作数作为输入 操作主存和高速缓存中的数据 在主存和外部环境间传递程序或数据 返回

翻译器和软件仿真计算机 尽管理论上有可能直接构造硬件或固件计算机，来运行任何特殊的程序设计语言，但构造这样的计算机并不经济。 现实的考虑是实际计算机采用低级机器语言（基于速度、灵活性和价格考虑），编程仍以高级语言进行。语言实现者面临的任务是如何使高级语言程序执行在实际计算机上，而不必关心其机器语言是什么。 这个实现问题有两个基本方案。 1、翻译（编译） 2、软件仿真（软件解释）

翻译（编译） 翻译过程： 高级语言程序→翻译器→等价的机器语言程序→硬件直接执行 翻译器： 源语言→等价的目标语言

翻译（编译） 几种特殊类型的翻译器： C、装配器或连接编辑器（loader/link editor） A、汇编器 D、预处理器或宏处理器 目标语言：实际计算机的机器语言 源 语 言：汇编语言，机器语言的符号表示 大多数指令是一对一的翻译 B、编译器 目标语言：汇编和机器语言 源 语 言：高级语言 C、装配器或连接编辑器（loader/link editor） 目标语言：实际的机器代码 源 语 言：几乎与机器代码相同，通常包含可重定位的机器语言程序和数据表（刻划可重定位代码为变成真正可执行所必须修改的地方） D、预处理器或宏处理器 源 语 言：某种高级语言的扩展形式 目标语言：同样语言的标准形式。 通常进行宏替换。

翻译（编译） 高级源语言到可执行机器语言的翻译通常涉及多个翻译步骤，有时，编译的某些步骤本身也涉及多遍，如：多遍扫描。

软件仿真（软件解释） 我们可以通过运行在一台宿主机上的程序仿真另一台以高级语言为机器语言的计算机。 用宿主机的机器语言构造一个程序集（表达高级语言执行必需的算法和数据结构），即用软件构造运行于宿主机上的高级语言计算机，称为高级语言计算机在宿主机上的软件仿真（或软件解释）。 仿真计算机接受高级语言程序作为输入，主仿真器程序完成解释算法（解码并执行语言），最后从程序产生输出。

软件仿真和翻译 软件仿真和翻译的不同： 纯粹的翻译和纯粹的仿真形成两个极端 均以高级语言程序为输入，但是， 翻译为目标码后再运行于实际计算机上 仿真计算机直接执行输入程序 翻译器以物理输入顺序处理程序语句，每个语句只处理一次。 仿真器以逻辑控制流处理程序，可能重复处理某些语句而完全忽略其他语句。 纯粹的翻译和纯粹的仿真形成两个极端 全翻译是很少的，除了输入语言和输出语言非常相似，如汇编语言。 全仿真也非常少，除了操作系统控制语言或交互式语言情形。

软件仿真和翻译 通常，语言实现是二者的结合：

软件仿真和翻译 翻译和仿真各有不同优点 有的程序结构最好翻译成更简单的形式，——如循环中语句多次执行，翻译可省去解码时间。有的方面最好保持原有形式，在执行时根据需要处理。 翻译的主要缺点是失去了关于程序的一些信息。 单个的高级语言语句比单条机器语言指令含有更多信息。 仿真的优缺点基本正好相反。 不需要太多的空间来存储代码序列的多份拷贝。但解码代价高。 通常，如源语言结构在目标语言中有直接表示，则代码扩展不太严重，可采用翻译。其他情形，可采用仿真。

软件仿真和翻译 — 语言划分 程序执行时的基本表示是否为实际机器的机器语言，成了语言划分的基础。 1、编译型语言。如：C、C++、Fortran、Ada等 源语言翻成机器码，仿真仅限于一些运行支持例程（用于仿真源语言中和机器语言没有紧密类似的基本操作）。 通过硬件解释器，可实现更快的程序执行。 当然，也可能有的部分仍采用软件仿真，如数据控制结构和存储管理。 2、解释型语言。如：LISP、ML、Prolog、Smalltalk等 翻译器不是产生机器代码，而是产生某种中间形式，比源语言更易执行。 然后使用软件解释器对中间代码进行执行。通常执行慢，也需要对基本操作、存储管理和其他语言特性的仿真， 这类语言翻译器很简单，更多的复杂性在软件仿真。 返回

2.2 虚拟计算机和绑定时间 计算机的构造方式 1、通过硬件实现，直接使用物理设备 2、固件实现，在合适的硬件计算机上使用微程序设计 3、软件仿真，在宿主机上用某种语言实现 4、上述技术的组合，各自选择合适的实现方式 当一个程序设计语言被实现后，程序执行时所使用的运行时数据结构和算法定义了一个计算机。我们称其为由语言实现定义的虚拟计算机。

虚拟计算机 虚拟机的机器语言是该语言的翻译器产生的可执行程序（形式：对编译是实际的机器码形式；对解释是某种任意结构）； 其数据结构是程序运行时使用的运行时数据结构； 基本操作是那些运行时实际可执行的； 顺序控制、数据控制和存贮管理结构也是那些运行时使用的，不管其是用软件、硬件、还是用微程序表示的。

虚拟机和语言实现 (1/3) 语言定义隐含地刻划了一个虚拟机。 如果语言用它们的虚拟机来定义，使得每个语言和一个共同理解的虚拟机相关联，则使用虚拟机来描述语言的语义是直接的。 语言在不同计算机上的每次实现，实现者都会从语言定义中看到略微（或非常）不同的虚拟机。同一语言的两个不同实现，可能使用不同的数据结构和操作集合（特别是在语法中隐藏的部分）。 每个实现者有很大自由度确定自己的虚拟机结构，这些是他的语言实现的基础。

虚拟机和语言实现 (2/3) 当语言在一特定计算机上实现时，实现者首先确定表示语言的语义解释的虚拟机，然后通过基本计算机提供的软、硬件元素来构造虚拟机。 语言实现的组织和结构由实现者的许多细微决策确定，需考虑计算机各种软、硬件设施和使用代价。 例：虚拟机如有整数加和平方根操作，则整数加可直接用硬件提供的整数加来实现，平方根可用软件仿真，使用一个子程序。

虚拟机和语言实现 (3/3) 三个因素导致相同语言的不同实现 实现者还需确定什么通过翻译处理？什么在执行中解决？ 1、实现者虚拟机概念的不同（隐含在语言定义中） 2、宿主机提供的设施的不同 3、实现者如何用宿主机提供的设施仿真虚拟机元素的选择和如何去构造翻译器支持这些虚拟机选择的不同。 实现者还需确定什么通过翻译处理？什么在执行中解决？ 返回

绑定和绑定时间 不严格地说，一个程序元素到某特定特征或性质的绑定，仅是从一个可能性质的集合中性质的简单选择。决定这个选择的程序陈述或处理的时间称为性质对元素的绑定时间。 语言中有不同的绑定和不同的绑定时间。 绑定时间的类型 对绑定类型没有简单的分类，但可区分出一些主要的绑定时间。这里，我们基于一个基本假设：程序的处理总是先翻译，后执行。

绑定时间 (1/4) 1、执行时（运行时） 很多绑定是在程序执行过程中完成的。如：变量到值的绑定，变量到特定存储位置的绑定（在很多语言中）。 进一步可分为： a. 进入子程序或块时。 大多数语言中，重要的绑定只限制发生在执行中进入子程序或块时，如C、Fortran中形参到实参、以及形参到特定存储位置的绑定。 b.在执行中的任意点。 某些绑定可以发生在程序执行中的任意点，如：变量通过赋值到值的绑定，以及在LISP、ML中，名字到存储位置的绑定。

绑定时间 (2/4) 2、翻译时（编译时）绑定，可进而分为三种： a. 程序员选定的绑定 b. 翻译器选择的绑定 写程序时，程序员有很多关于变量名、变量类型、程序语句结构等选择的决定，这些决定代表了翻译的绑定，语言翻译器使用这些绑定确定目标程序的最终形式。 b. 翻译器选择的绑定 有些绑定由翻译器决定，没有直接的程序员规约。如：数据对象在为某过程分配的存储区域中的相对位置（程序员不知道也不关心），数组如何存储，数组描述子如何创建等。不同的语言实现可能以不同方式提供这些特性。 c. 装配器选定的绑定（链接时） 程序通常包含几个子程序，这些子程序被合并为一个可执行程序。翻译器决定变量到每个子程序中存储地址的绑定，这些存储必须被分配物理机中的实际地址。

绑定时间 (3/4) 3、语言实现时 语言定义的某些方面可能对所有运行于同一语言实现上的程序均是相同的，但可能由于语言实现不同而不相同。 如：通常和数的表示以及算术操作的表示相关的细节由底层硬件机进行算术的方式确定。 以某语言编写的程序，如果使用了在实现时固定的特性，则不一定可以在该语言的另一种实现上运行，即使运行也可能有不同执行结果。

绑定时间 (4/4) 4、语言定义时 语言的大多数结构是在语言定义时固定的（对程序员写程序时可用的规约）。如：对程序员可以使用的选择语句形式、数据结构类型、程序结构等。

绑定和绑定时间（例子） 考虑下面简单例子：X:=X+10，假定该语言为L，则需考虑的绑定和绑字时间如下： 1、变量X的可能类型的集合 变量X在语句中通常和某类型相关联，如实数、整数、布尔，X的允许类型集合通常在语言定义时固定，如类型只能是：实数，整数，布尔，集合，字符等。此外，语言可能允许程序定义新类型，此时X的类型绑定在翻译时固定。 2、X的类型 通常在翻译时固定，通过显式的声明语句，如：Float X。有些语言，如Smalltalk、Prolog，类型绑定在运行时完成（无类型、弱类型语言）。

绑定和绑定时间（例子） 3、变量X的可能值的集合 4、变量X的值 5、常量10的表示 如X类型为real，则其值集为实数，真实集应为定义语言的虚拟机可表示和操作的实数，通常是可方便地在硬件机上表示和操作的实数。这样，X的可能值集在语言实现时确定，也可能是在装载时根据执行程序的硬件机确定。 4、变量X的值 在执行中某点，一特定值被约束到X。通常值是在执行时通过对X的赋值而确定的。 5、常量10的表示 整数10的表示作为程序中的常量，使用串‘10’；执行时，表示为位串。程序中十进制的选择通常在语言定义时决定（10也可能为2#的2），而特殊位串的选择是语言实现时决定。

绑定和绑定时间（例子） 6、操作符+的性质 符号+代表加法是在语言定义时确定。 然而，+可以被重载（实数、整数、复数加等，根据语境确定）。在编译型语言中，在编译时确定，通常根据操作数类型判定。 +的详细定义依赖于底层硬件机。如X=2^49，则X+10可能在某一机器上没有定义，因此，+的定义是在语言实现时确定，根据底层硬件机的定义。 这样：+表示加法在语言定义时定，每个加法操作在语言实现时定，符号+被绑定到特定加法操作是在翻译时，每个特定加法对特定操作数的值在运行时定。

绑定时间的重要性 语言中许多重要而微妙的不同是由于绑定时间的不同。 在分析和比较语言时，需要常问的问题是：翻译时做，还是执行时做？ 例如：几乎每个语言均允许数作为数据，并允许在其上的算术操作，但并不是每个语言均适合涉及大量算术编程问题。 ML和Fortran，均允许建立和操作数值的数组，但ML不适合于求解需大数组和大量算术的问题，而Fortran是合适的。 原因：ML中，程序中大多数绑定是在执行时，需要大量执行时间来创建和消除绑定。Fortran中，大多数绑定是在编译时，相同绑定的大部分在编译时做一次，很少的工作在运行时完成，因此，执行更为高效。

绑定时间的重要性 （续） 反过来，为什么Fortran不适合于处理串，而ML更容易？ 原因也在于绑定时间。Fortran中大多数绑定在翻译时完成，即在输入数据被知道前，这样它对执行时有不同数据形式的情况不太合适，Fortran中串的大小和变量类型需在编译时确定。 ML可在执行中延迟到输入数据已被检查，且绑定已确定时，才确定大小和类型。 这两种不同绑定分为早绑定（ early ）和晚绑定（ late ）。二者的优、缺点围绕的冲突是：效率和灵活性，如二者均需考虑，则应提供选择的灵活性，如Ada。

绑定时间和语言实现 语言定义通常允许指定绑定时间。 通常，一个语言设计指定绑定可能发生的最早时间，但很多实现事实上延迟这些绑定。 设计语言时，通常希望某特定绑定可在翻译时完成。但实际的绑定时间只能在语言实现时决定。如：Pascal设计为允许变量类型在编译时确定，但某种实现可以允许在执行时作类型检查。 通常，一个语言设计指定绑定可能发生的最早时间，但很多实现事实上延迟这些绑定。 然而，通常同一语言的大多数实现在相同时间完成大多数和绑定。 如果一个语言设计为允许编译时绑定，则延迟绑定将导致低效，还不一定取得太多的灵活性。 需要注意的是，通常语言中很小的变化会导致绑定时间的大变化，如：Fortran 90允许递归，就修改了很多重要特性的绑定时间，因为绑定时间是实现依赖的。

C 语言概述 C 是由AT&T贝尔电话实验室的 Dennis Ritchie 和 Ken Thompson 在1972年开发出来的 开发C语言是为了在DEC PDP-11上开发UNIX操作系统。UNIX在那个时候还是一个很“小”的操作系统，是为了和MIT和GE的大型操作系统 Multics竞争。 C更像一个环境，而不仅仅是一种简单的语言： C 语言 C 预处理器 (#include, #if, ...) C 的接口假定 (.h 包含文件) C 库 (“内置” 函数，如 printf, malloc, ...)

C 语言的程序结构 C 语言程序是由一序列过程和全局声明构成的 每个过程包含局部声明、命令语句（它们可以调用其它过程） 大多数数据都是整型数据，这极大程度地保证了灵活性，因为差不多所有东西都可以看成是一个整数。 如今，C 和 C++ 在某种程度上已经成为开发系统软件（如操作系统、编译器、应用程序、视频游戏等）的主要程序设计语言。

C 语言程序的例子 1 #include <stdio.h> 2 const int maxsize=9; 3 main() 4 {int a[maxsize]; 5 int j,k; 6 while( (k=convert(getchar())) != 0) { 7 for(j=0;j<k;j++)a[j]=convert(getchar()); 8 for(j=0; j<k; j++) printf("%d ", a[j]); 9 printf("; SUM= %d\n", addition(a,k)); 10 while(getchar() != '\n'); }} 11 /* Function convert subprogram */ 12 int convert(char ch) {return ch-'0';} 13 /* Function addition subprogram */ 14 int addition(v, n) 15 int v[ ], n; 16 {int sum,j; 17 sum=0; 18 for(j=0; j<n; j++) sum=sum+v[j]; 19 return sum; }

C 语言程序的例子 C language C preprocessor C interface assumptions C library 1 #include <stdio.h> 2 const int maxsize=9; 3 main() 4 {int a[maxsize]; 5 int j,k; 6 while( (k=convert(getchar())) != 0) { 7 for(j=0;j<k;j++)a[j]=convert(getchar()); 8 for(j=0; j<k; j++) printf("%d ", a[j]); 9 printf("; SUM= %d\n", addition(a,k)); 10 while(getchar() != '\n'); }} 11 /* Function convert subprogram */ 12 int convert(char ch) {return ch-'0';} 13 /* Function addition subprogram */ 14 int addition(v, n) 15 int v[ ], n; 16 {int sum,j; 17 sum=0; 18 for(j=0; j<n; j++) sum=sum+v[j]; 19 return sum; }

C++ 概述 由 AT&T 的 Bjarne Stroustrup 在 1986 年开发，它是 C 语言的一种扩展。 C++ 基本上包括了 C 的所有东西(包括好的和坏的特征) 增加了强类型 目标是在保持C语言执行的高效性的同时，增加新的特征 C++ 增加了类的概念（借鉴了 Simula 中的相关概念，它是由Algol扩展而来的一种模拟语言)。 数据定义成类的局部属性 函数 (方法) 可以访问局部数据 实现了类的继承概念

C++ 语言程序的例子 Classes Methods 1 #include <stream.h> 2 class DataConvert { 3 protected: int convert(char ch) {return ch-'0';}}; 4 class DataStore: DataConvert{ 5 public: 6 int initial(char a) 7 {ci=0; return size = convert(a);}; 8 void save(char a) {store[ci++]=convert(a);}; 9 int setprint() { ci=0; return size;}; 10 int printval() { return store[ci++];}; 11 int sum() 12 {int arrsum; 13 arrsum=0; 14 for(ci=0;ci<size;ci++)arrsum=arrsum+store[ci]; 15 return arrsum;} 16 private: 17 const int maxsize=9; 18 int size; // Size of array 19 int ci; // Current index into array 20 int store[maxsize];}; // end class DataStore Classes Methods

C++语言程序的例子 (续) 21 main() 22 {int j,k; 23 DataStore x; 24 while((k=x.initial(cin.get()))!=0) 25 {for(j=0;j<k;j++)x.save(cin.get()); 26 for(j=x.setprint();j>0;j--)cout<<x.printval(); 27 cout << "; SUM=" << x.sum() << endl; 28 while(cin.get()!='\n');}}