1.2 强制式语言

通常的高级语言又称为强制式语言(Imperative Language)，本书主要讨论强制式语言的设计和实现。

1.2.1 程序设计语言的分类

语言的分类没有一个统一的标准，通常按不同的尺度有不同的分类方法和结果。例如，按语言设计的理论基础来分类，可分为4类语言，即强制式语言，其基础是冯·诺依曼(Von Neumann)模型；函数式语言(Functional Language)的基础是数学函数；逻辑式语言(Logic Language)的基础是数理逻辑谓词演算；对象式语言(Obj ect-oriented Language)的基础是抽象数据类型(Abstract Data Type)。

人们习惯上按语言的发展历程来对语言进行分类。

1.第一代语言

第一代语言(First-generation Language)通常称为机器语言，它与机器孪生。实际上，它完全依赖于机器的指令系统(Instruction System)，以二进制代码表示。这类语言的程序既难编写，又难读懂。

2.第二代语言

第二代语言(Second-generation Language)通常称为汇编语言，它将机器语言符号化，用符号来代表机器语言的某些属性。例如，用符号名来代表机器语言的地址码。这样可以帮助程序员记忆，摆脱使用二进制代码的烦恼，提高了程序的可写性和可读性。

不同的机器有不同的机器语言和汇编语言，通常人们又把它们称为与机器有关的语言，或面向机器的语言。

3.第三代语言

第三代语言(Third-generation Language)通常是指高级语言，这类语言的设计基础与冯·诺依曼体系结构有关。高级语言程序按语句顺序执行，因此又称为面向语句的语言(Sentence-oriented Language)。通常，每条语句对应机器的一组命令，因此又称命令式语言(Order Language)。用这类语言编写的程序，实际上是描述对问题求解的计算过程，因此也有人称它为过程式语言(Procedure Language)。

这类语言书写自然，具有更好的可读性、可写性和可修改性(Modifiability)，读者使用过的语言大多是这种高级语言。高级语言程序就是要告诉计算机“做什么”和“怎么做”。

4.第四代语言

第四代语言(Fourth-generation Language)是说明性语言(Declaration Language)，它只需要告诉(说明)计算机“做什么”，不必告诉计算机“怎么做”；也就是说不需要描述计算过程，系统就能自动完成所需要做的工作。所以，这类语言又称为超高级语言或甚高级语言(Very-high-level Language)，典型的例子是SQL语言。

5.新一代语言

另一类不同风格的语言，如函数式和逻辑式语言，它们的理论基础和程序设计风格均不同于高级程序设计语言。它们不适合称为第五代语言或第六代语言，因此，语言学家把它们称为新一代程序设计语言。

1.2.2 冯· 诺依曼体系结构

当今的计算机模型是由数学家冯·诺依曼提出来的，我们称为冯·诺依曼模型(Von Neumann Model)或冯·诺依曼机(Von Neumann Machine)。直到今天，几乎所有的计算机都是沿用这一模型设计的。1978年，巴科斯(Backus)在获得图灵奖的颁奖大会上发表演说，批判了冯·诺依曼的体系结构和程序设计风格，称这种结构和风格影响了计算机系统的执行效率，提出了函数式程序设计风格，并发表了FP和FFP语言。今天，人们越来越多地强调使用并行体系结构和并行程序设计，以提高计算机的执行效率。

下面讨论冯·诺依曼体系结构和它对高级语言的影响。

冯·诺依曼机的概念基于以下思想：一个存储器(用来存放指令和数据)，一个控制器和一个处理器(控制器负责从存储器中逐条取出指令，处理器通过算术或逻辑操作来处理数据)，最后的处理结果还必须送回存储器中。我们可以把这些特点归结为以下4个方面。

(1)数据和指令以二进制形式存储(数据和指令在外形上没有什么区别，但每位二进制数字有不同的含义)。

(2)“存储程序”方式工作(事先编好程序，执行之前先将程序存放到存储器某个可知的地方)。

(3)程序顺序执行(可以强行改变执行顺序)。

(4)存储器的内容可以被修改(存储器的某个单元一旦放入新的数据，则该单元原来的数据立即消失，且被新数据代替)。

冯· 诺依曼体系结构的作用体现在命令式语言的下述三大特性上。

(1)变量 存储器由大量存储单元组成，数据就存放在这些单元中，汇编语言通过对存储单元的命名来访问数据。在命令式语言中，存储单元及其名称由变量的概念来代替。变量代表一个(或一组)已命名的存储单元，存储单元可存放变量的值(Value)，变量的值可以被修改；也正是这种修改，产生了副作用(Side Effect)问题(参见3.3.l节)。

(2)赋值 使用存储单元概念的另一个后果是每个计算结果都必须存储，即赋值于某个存储单元，从而改变该单元的值。

(3)重复 指令按顺序执行，指令存储在有限的存储器中；要完成复杂的计算，有效的办法就是重复执行某些指令序列。

1.2.3 绑定和绑定时间

一个对象(或事物)与其各种属性建立起某种联系的过程称为绑定(Binding)。这种联系的建立，实际上就是建立了某种约束。绑定这个词是由英文Binding音译过来的，过去也曾翻译成“联编”、“汇集”、“拼接”或“约束”等。现在之所以选定“绑定”这个词，除了它能形象地表达上述过程外，它还与英文读音一致。

一个程序往往要涉及若干实体，如变量、子程序和语句等。实体具有某些特性，这些特性称为实体的属性(Attribute)。变量的属性有名字(Name)、类型(Type)和保留其值的存储区等。子程序的属性有名字、某些类型的形参(Formal Parameter)和某种参数传递方式的约定等。语句的属性是与之相关的一系列动作。在处理实体之前，必须将实体与相关的属性联系起来(即绑定)。每个实体的绑定信息来源于所谓的描述符(Descriptor)。描述符实际上是各种形式的表格的统称(抽象)，用来存放实体的属性。例如，程序员用类型说明语句来描述变量的类型属性，编译时将它存放在符号表(Symbol Table)中；程序员用数组说明语句来描述一个数组的属性，编译时将这些属性存放在一个专门设计的表格中(参见7.4节)，这个表格称为数组描述符，又称内情向量(Dope Vector)。

对于计算机科学来说，绑定是一个随处遇到且重复使用的重要概念，借助于它可以阐明许多其他概念。把对象(实体)与它的某个属性联系起来的时刻称为绑定时间(Binding Time)。一旦把某种属性与一个实体绑定，这种约束关系就一直存在下去，直到对这一实体的另一次绑定实现，该属性的约束才会改变。

某些属性可能在语言定义时绑定，例如，FORTRAN语言中的INTEGER类型，在语言定义的说明中就绑定了，它由语言编译器来确定这个类型所包含的值的集合。Pascal语言中允许重新定义integer类型，因此integer类型在编译时才能绑定一个具体表示。若一个绑定在运行之前(即编译时)完成，且在运行时不会改变，则称为静态绑定(Static Binding)。若一个绑定在运行时完成(此后可能在运行过程中被改变)，则称为动态绑定(Dynamic Binding)。

今后讲到的许多特性，有的是在编译时所具有的，有的是在运行时所具有的，凡是在编译时确定的特性均称为静态的(Static)；凡是在运行时确定的特性均称为动态的(Dynamic)。

1.2.4 变量

强制式语言最重要的概念之一是变量，它是一个抽象概念，是对存储单元的抽象。如前所述，冯·诺依曼机基于存储单元组成的主存储器(Main Memory)概念，它的每个存储单元用地址来标识，可以对它进行读或写操作。写操作就是指修改存储单元的值，即以一个新值代替原来的值。语言中引入变量的概念，实质上是对一个(或若干个)存储单元的抽象，赋值(As-signment)语句则是对修改存储单元内容的抽象。

变量用名字来标识，此外它还有4个属性：作用域(Scope)、生存期(Lifetime)、值和类型。变量可以不具有名字，这类变量称为匿名变量(Anonymous Variable)。下面将讨论上述4个属性，以及它们在不同语言中所采用的绑定策略。

1.变量的作用域

变量的作用域是指可访问该变量的程序范围。在作用域内，变量是可控制的(Manipula-ble)。变量可以被静态地或动态地绑定于某个程序范围。在作用域内变量是可见的(Visi-ble)，在作用域外变量是不可见的(Invisible)。按照程序的语法结构定义变量的作用域的方法，称为静态作用域绑定(Static Scope Binding)。这时，对变量的每次引用都静态地绑定于一个实际(隐式或显式)的变量说明。大多数传统语言采用静态作用域绑定规则。有的语言在程序执行中动态地定义变量的作用域，这种情况称为动态作用域绑定(Dynamic Scope Binding)。每个变量说明延伸其作用域到它后面的所有指令(语句)，直到遇到一个同名变量的新说明为止。APL，LISP和SNOBL4语言是采用动态作用域规则的语言。

动态作用域规则很容易实现，但掌握这类语言的程序设计比较困难，实现的有效性也偏低。对于动态作用域语言，给定变量绑定于特定说明之后程序执行到的某个特定点，因为其不能静态确定，所以程序很难读懂。

2.变量的生存期

一个存储区绑定于一个变量的时间区间称为变量的生存期。这个存储区用来保存变量的值。我们将使用术语“数据对象”(Data Obj ect)，或简称“对象”(Obj ect)来同时表示存储区和它保存的值。

变量获得存储区的活动称为分配(Allocation)。某些语言在运行前进行分配，这类分配称为静态分配(Static Allocation)，如FORTRAN语言；某些语言在运行时进行分配，这类分配称为动态分配(Dynamic Allocation)，如C、C++语言。动态分配可以通过两种途径来实现：或者程序员用相关的语句显式提出请求，如C++语言通过new进行；或者在进入变量的作用域时隐式自动进行分配，如C语言的活动记录的分配。采用什么样的分配，这要看语言是如何规定的。

变量所分配的存储单元的个数，称为变量的长度(Length)。

3.变量的值

变量在生存期内绑定于一个存储区，该存储区中每个存储单元的内容是以二进制编码方式表示的变量值，并绑定于变量。编码表示按变量所绑定的类型来进行解释。

在某些语言中，变量的值可能是指向某个对象的指针(Pointer)，若这个对象的值也是指针，那么，可能形成一个引用链(Reference Chain)，这个引用链通常称为访问路径(Access Path)。

若两个变量都有一条访问路径指向同一对象，那么，这两个变量共享(Share)一个对象。经由某个访问路径修改一个共享对象的值时，这种修改能被所有共享这个对象的访问路径获知。多变量共享一个对象，可以节省存储空间。但是，由于一个变量的值被修改，就造成所有共享这个对象的变量的值都被修改，使程序很难读懂。

特别地，访问匿名变量的基本方法是通过访问路径来实现的。

变量的值在程序运行时可以通过赋值操作来修改，因此，变量与它的值的绑定是动态的。一个赋值操作，例如

          b：=a

将变量a绑定的值复制到变量b绑定的存储区内，从而修改变量b绑定的值，以一个新值(a的值)来代替b原来的值。

然而，有的语言允许变量与它的值一旦绑定完成就被冻结(Frozen)，不能再修改。例如，在Pascal语言中，符号常数语句定义为

          const pi=3.1416

在ALGOL 68中，语句

          real pi=3.1416

定义了pi绑定于值3.1416。在表达式中使用值3.1416可写成

          circumference ：=2*pi*radius

式中的pi具有它所绑定的值3.1416。这个绑定在整个程序执行过程中不能改变，即不能向pi赋新值。显然，语句

          pi：=2*pi

是错误的。Pascal语言中的符号常数(Symbolic Constant)的值可以是一个数，也可以是一个字符串，这类变量在编译时即可完成对值的绑定。同时，编译程序可以在编译过程中合法地以这个值去替代程序中出现的相应符号名。ALGOL68的符号常数还可以定义为

          real pi：=3.1416+x

它允许将值定义成变量(或表达式中含变量)，由于有变量，它只能在程序运行中待这些变量建立时才能完成绑定。

对一般变量而言，当它建立时，才会获得所分配的存储区，同时完成变量与存储区的绑定。此时，该变量绑定的值是什么呢？这是变量值的初始化问题，这个问题十分微妙。例如，程序段

          procedure
              integer x，y；
              x：=y+3；

中的语句

          integer x，y；

建立了两个整型变量，允许执行到该过程时，变量x和y绑定于不同的两个存储单元，但它们绑定的是什么整数值并不确定，原因是未对变量x和y赋初值。当执行到语句

          x：=y+3；

时y绑定什么值是不明确的，即未对y赋初值，因而计算的结果x绑定什么值也不明确。在上述程序段中未对y赋初值就引用了它，程序可能出错。因此，在程序设计中，读者应当遵从对变量“先赋初值后引用”的原则。

虽然有许多方法可以解决“初值问题”，但遗憾的是，通过语言定义来解决这个问题的大多数尝试都不太成功，因为同一语言的不同实现可能采用不同的方法。例如，FORTRAN语言定义了一个初值语句(Initial Value Statement)，不同的编译程序采用不同的方法来实现，程序员用起来很不方便。要在语言定义中设定一种方式，实现对所有变量初始化是十分困难的。

最简单也是最常用的解决办法是，在语言设计时，忽略初始化问题，在这种情况下，一旦存储区绑定于某个变量，该存储区当前的内容就是该变量绑定的初值。实际上，这个值是随机的位串。类似的方法还有，规定一个非初始化值(Uninitialized Value)，由编译程序在把某存储区分配给变量时，将这个特殊的值赋给每个已分配的存储单元。当程序运行时，每引用一个变量，先检查引用单元的值是否是这个特殊的非初始化值，若是，则出现错误，由系统报告这一错误，这种方法可以彻底解决非初始化问题，但执行效率较低。

有些实现方法提供了定义初值的强制手段，例如，若定义整型变量，初值强制置0，若定义字符串变量，初值强制置空串。总之，程序员在使用一个语言编程时，一定要注意初值问题。

4.变量的类型

变量的类型可以看成与变量相关联的值的类，以及对这些值进行的操作(例如，整数加、浮点数加、建立、存取和修改等操作)的说明。类型也可用来解释变量绑定的存储区的内容(二进制位串)的意义。

根据上述对类型的定义，在定义语言时，类型名通常绑定于某一个值类和某一组操作。例如，布尔类型boolean绑定于值true和false，以及操作and，or和not。

语言实现时，值和操作绑定于某种机器的二进制代码表示。例如，false可以绑定于位串00000000，true绑定于位串11111111。and，or和not操作可以通过表示布尔量位串操作的机器指令来实现。

在某些语言中，程序员可以用类型说明方式来定义新类型。例如，Pascal语言的语句

          type t=array[l..10]of boolean

在编译时就能建立一个名为t的类型，并使它绑定于一个实现(即由10个布尔值组成的数组，借助于下标1～10可访问每个数组元素)。类型t继承了它所代表的数据结构(布尔数组)的所有操作，用数组内的下标能够读取和修改类型t的对象的每个分量(元素)。

变量可以静态或动态地绑定于类型，大多数传统语言都采用静态绑定。例如，FOR-TRAN，ALGOL 60，COBOL，Pascal，ALGOL 68，SIMULA 67，CLU，C和Ada语言等。在这些语言中，变量和它的类型定义之间的绑定通常都是由显式的变量说明来规定的。例如，语句

          var x，y ：integer；
              z ：boolean；

将变量x和y绑定为整型，将变量z绑定为布尔型。然而，在某些语言中，例如FOR-TRAN语言允许隐式说明并绑定变量的类型。一个未被说明的新变量，它的第一次出现即可根据变量名的第一个字母来绑定该变量是整型还是实型。语言设计时提出I-N隐式说明规则，以I到N开头的变量为整型，其他字母开头的变量为实型。这种隐式说明方式的优点是，可以省去显式类型说明语句，写程序要方便些。然而，它的缺点是，不利于编译时检查拼写错误。例如，有FORTRAN程序段：

          INTEGER I，J，ALPHA
          ALPHA=5
          ALPHA=ALPH+I

其中，ALPH是一个新变量还是变量ALPHA的拼写错误，编译程序无法辨别，它总是把ALP H当作一个新变量来处理，这个新变量隐式说明为实型。

隐式说明的缺点不是语义上的问题，单就变量的类型而言，Pascal语言和FORTRAN语言中变量的类型在语义上是等效的，两者均是在定义或编译时绑定于变量，它们都是静态绑定。不同的是，FORTRAN语言具有确定的默认(隐式)类型说明规则，两种语言的绑定时间在某种意义下是相同的。

APL和SNOBOL4语言的类型绑定是动态的，程序编译时无法确定变量的类型，只有在程序运行到某个语句时，才能确定变量的类型。例如，在APL语言中，一个变量名可以在执行期间的不同执行点分别表示一个简单变量、一个一维数组、一个多维数组或一个标号。实际上，APL语言变量的类型不是显式说明的，而是在程序执行时隐式说明的，且动态变化。例如，APL程序段

当执行到语句

          A←5

时，A成为具有值5的整型变量。若其后执行到语句

          →A

时，把A处理成标号变量，执行这条语句的意义是把控制转移到A绑定的值所标记的那个语句，若A的值是5，则转移到标号为5的语句执行。当执行到语句

          A←12510

时，使A成为具有4个元素，且其值分别为1，2，51和0的一维数组，隐含的下标下界为1。

动态绑定类型对建立和操作数据提供了很大的灵活性，但也影响程序的编写、检查和实现的效率。因为在语句中出现的变量类型，在编译时不能确定，它依赖于给定程序的执行路径，所以程序的可读性差。在上述程序片段中，语句

          A[2：3]←5

的意义是对一个二维数组中位于第2行第3列的元素赋值为5，当程序执行到这个语句时，A应该已经绑定一个合适的二维数组，但在上述程序中，A此时绑定的类型是整型，其值为0，因此这个语句是错误的。而这个错误要执行到这个语句时才能发现，这就需要动态类型检查来查证上述错误。采用动态类型检查方式，可在程序运行时查证所使用的每个变量与它的类型是否一致。我们再考查语句

          A←B+C

若运行到这个语句时，B和C都是简单变量，或其中一个是简单变量，语句是正确的；若B和C是维数相同且大小相同的数组，语句也是正确的。这个语句的执行依赖于B和C，若B和C都是简单变量，则语句隐含的操作是简单加和赋值；若B和C是一维数组，则隐含的操作是由加和赋值构成的一个循环，且A被绑定成一个一维数组。

上例表明，有关APL语言变量的类型信息必须在运行时使用，它不仅用于执行动态类型检查，而且还用于选择执行这个语句的合适操作。为了能在运行时使用运行信息，有关描述符(说明)必须保留到运行时，并且在每次新的绑定完成时，必须对描述符中所保留的类型信息进行相应的修改。对于静态绑定的语言，例如Pascal语言的类型信息，在编译时就能确定并加以处理，所以在运行时不必保留类型描述符。

动态绑定的语言实现采用解释(Interpretation)方式处理更合适，因为对于一个不能确定变量类型的表达式，在运行之前没有足够的信息来生成合适的代码(参见7.1节)。语言实现采用编译还是解释方式，受到变量与类型绑定规则的严重影响。动态绑定的语言是面向解释的语言(Interpretation-oriented Language)，静态绑定的语言是面向编译的语言(Compilation-oriented Language)。

动态类型绑定的语言，往往其作用域也是动态绑定的，因此，这类语言又称为动态语言(Dynamic Language)。

1.2.5 虚拟机

我们知道，程序设计语言早期经历了从机器语言发展到汇编语言的时期。机器语言实际上是计算机的指令系统，它是直接由电子线路(硬件)实现的，是实际的机器，我们把它记为M1。

为了使电子线路尽量简单，机器采用二进制代码，使用起来非常不便，于是出现了汇编语言。机器不能直接执行用汇编语言编写的程序，必须先将汇编语言程序(L2)经汇编程序翻译成等效的机器语言程序(L1)。也就是说，汇编语言程序要在实际机器(M1)和汇编程序上才能执行，若把汇编语言看成某个虚拟机器(Virtual Machine，Virtual Computer)的机器语言，那么这个虚拟机M2=M1+汇编程序。

后来，程序设计语言又从汇编语言发展到高级语言，用高级语言编写的程序L3必须经过编译程序编译成等效的汇编语言程序L2(或机器语言程序L1)，机器才能执行。也就是说，高级语言要在虚拟机M2和编译程序上才能实现。若把高级语言看成某个虚拟机的机器语言，那么M3=M2+编译程序。

由此可见，虚拟机是由实际机器加软件实现的机器，它可看成一个有别于实际机器的新机器。若一台实际机器配置上Pascal和FORTRAN编译程序，对Pascal用户来说，这台机器就是以Pascal语言为机器语言的虚拟机(Pascal机)；对FORTRAN用户来说，这台机器就是以FORTRAN语言为机器语言的虚拟机(FORTRAN机)，它们按各自的需要去使用，互不干扰。在计算机系统结构课程中，将专门讨论虚拟机的层次分级概念。图1-1给出一个网络应用程序的虚拟机层次。

这一节我们介绍了强制式语言的一些概念，这些概念在非强制式语言中，有些也适用。几十年来，已经有许多很成熟的强制式语言，图1-2给出了主要的强制式语言，以及它们之间的关系。