第二章
语言设计问题
?早期的语言设计需使程序能高效地运行于昂贵的硬件上，因此，
早期语言总以翻译成高效的机器码为目标，既使程序难以书写。
?现在，硬件价格下降、软件价格上升，更强调程序容易书写，
即使慢点也可。 例如,ML的类型特性,C++的类,Ada的
Package均在执行速度上有代价，但对保证程序正确性有帮助。
?开发语言时，有三个影响语言设计的主要因素,
计算机本身
在计算机上支持语言的执行模型，即虚拟计算机
语言所实现的计算模型
2.1 计算机的结构和操作
?一个计算机是能够存储和执行程序的数据结构和算法的集成集
合。
?计算机可构造为实际的物理设备，用导线、集成电路、电路板
等。此即实际计算机或称硬件计算机。
?计算机构造为软件，用运行于其他计算机上的程序。此即软件
仿真计算机。
?程序设计语言的实现是通过一个翻译器，将以语言书写的程序
翻译为机器语言程序（可为某计算机直接执行，可以是硬件计
算机，也可以为软硬参杂的虚拟机）。
?一个计算机包含 6个主要部件，它们紧密地对应于程序设计
语言的主要方面。
1、数据：计算机必须提供各种基本数据项和操作的数据
结构。
2、基本操作：必须提供对操作数据有用的基本操作集。
3、顺序控制：必须提供控制基本操作执行顺序的机制。
4、数据访问：必须提供控制向操作的执行供给数据的机
制。
5、存储管理：必须提供控制程序和数据存储分配的机制。
6、操作环境：必须提供与包围程序和被处理数据的外部
环境通讯的机制。
计算机硬件
?一个典型的传统计算机组织如下,
包括程序和被处理的数据
操作主存和高速缓存中的数据
在主存和外部环境间传递程序或数据
完成处理工作
取机器指令
解码
调用指定的基本操作，以指定的操作数作为输入
?数据
有三个主要的存贮部件：主存，高速寄存和外部文件。
主存：组织为线性位串，可分为定长的字（ 32或 64）或 8
位字节。
寄存器：字长度的位串，可能有特殊的子域可直接访问，
可存数据或主存地址。
外部文件：存在盘、带或 CD-ROM上，按记录划分，记
录是位或字节的序列。
一个计算机有被硬件基本操作直接操作的固有数据类型。
一般有：整数、单精度实数（浮点数）、定长字符串、
定长位串等。
除了明显的硬件数据元素外，程序（也有固有的内部表
示，称为机器语言表示）也是一种数据形式。
机器语言程序可构造为存储位置的序列，每个包含一或
多条指令，每条包括操作码和若干操作数（指示）。
?操作
计算机必须包含有一个固有的基本操作集，通常和机器
语言指令中操作码一一对应。
典型的操作集包括在固有数值类型上的基本算术操作。
测试数据项各种性质的基本操作 。
访问和修改数据项的基本操作 。
控制 I/O设备的基本操作 。
顺序控制的基本操作。
传统的机器是 CISC,complex instruction set computers,
新近发展的是 RISC,reduced instruction set computers,
更少的基本指令，更简单的内部逻辑。
?顺序控制
程序地址寄存器（位置计数器）的内容决定了下一条将
执行的指令，即包含了下条指令的地址。
某些基本操作允许修改程序寄存器，从而传递控制到程
序的其他部分。
解释器实际地使用程序地址寄存器并指导操作序列。
解释器是计算机操作的中心，其周期动作如图所示,
?数据访问
除了操作码外, 每个机器指令必须指明所需的操作数
（ 必须在主存或寄存器中 ）
计算机必须结合指定操作数的手段和从给定操作数指示
器检索操作数的机制 。 同时, 操作的结果也必须存储在
指定的位置 。
传统的存储控制机制是为存储位置设定整数地址, 提供
操作从给定地址的位置检索内容和存储新值 。
寄存器也赋以整数地址 。
?存储管理
机器设计的一个驱动原则是保持所有计算机资源尽可能
多地被使用，中心冲突是,
CPU中的操作是纳秒级（一个操作 10— 50ns）
访问主存是是微秒级（ 0.1~0.2微秒,100— 200ns）
外部数据操作是毫秒级（ 15— 30毫秒）
这样在内外速度间相差 1000,000倍。
为了平衡速度差异，各种存储管理机制是必须的。
1、在最简单的设计（如低价 PC）中，只有简单的存
储管理设施。程序和数据执行时驻留内存，在一个时
刻只有一个程序准备执行。虽然 CPU必须等待数据，
它也是价格有效的，因为不需加入附加硬件。
2、为加速外部数据访问和 CPU间的平衡，操作系统
常使用多道程序设计，当等待毫秒去读数据时，计算
机将执行另一个程序。为了保证多个程序同时驻留主
存，通常有硬件设施负责页面查找或动态程序重定位，
页面查找通过预测进行，预测在最近将来最可能使用
的页面，将其放入主存。如在主存，则程序执行，否
则，出现页间错，操作系统将从外存中读取所需页，
同时执行别的程序。
3、为加速主存和 CPU间的不平衡，常使用 Cache存储
器（小的高速数据存储）。 Cache可允许计算机操作，
好象主存具有和 CPU相同速度，通常是 1K到 256K字
节,32K的 Cache，可达到 95%的选中率。
?操作环境
计算机的操作环境通常包括外围存储器和 I/O设备，这些
设备表示了计算机的外部世界，和计算机的任何通讯必
须通过它们。
操作环境中通常有硬件的不同，如：高速存储（扩展内
存），中速存储（磁盘），低速存储（磁带）和 I/O设备。
?各种计算机体系结构
计算机硬件的组织有多种形式，上面的讨论是基于 Von
Neumann体系结构。
Von Neumann体系结构,
命名来源于数学家 John von Neumann，他在 40年代开
发这个初始设计，作为 ENIAC计算机设计的一部分，
现今计算机仍属此体系结构。
多处理器,
Von Neumann设计的最大问题是外部数据设备的慢速
和 CPU寄存器高速间的矛盾 。 解决方案之一是在指定
系统中使用多个 CPU,这样的多处理系统已使用了 30
多年, 通过几个相对不昂贵的 CPU的粘合, 再加上单
一的主存, 磁盘, 磁带等, 得到一个高效系统 。 操作
系统将不同程序运行于不同 CPU上, 从而整个性能得
到改善 。
语言和系统设计正在演化，使得能够书写程序在多个
计算机上执行并相互通讯。
?计算机状态
对计算机静态组织的了解只是一个部分, 全面了解则涉
及计算机在程序执行时的动态操作, 包括,
执行开始时各存储部件的内容, 操作执行顺序 。
执行进行时如何修改各种数据部件, 程序执行的最后
结果等 。
通常对计算机动态行为的观察是通过计算机状态 （ 执行
过程中某点主存, 寄存器和外存的内容决定 ） 的概念 。
程序的执行体现为一系列状态的变化
初始状态通过一系列状态变迁 （ 从当前状态通过存贮内
容的修改进入新的状态 ）, 得到最终状态 。
如果我们可以预测状态变迁序列，则可以声称了解了计
算机的动态行为。
固件计算机
?如前定义, 计算机 =算法集 +数据结构集
可执行程序表示为计算机的机器语言程序
?通常认为计算机操作在相当低级的机器语言之上, 具有简单
的指令格式 。 然而, 机器语言并不一定限制到低级 。
?可以选择任何程序设计语言, 精确地刻划数据结构集和定义
程序执行规则的算法, 这样该计算机的, 机器语言, 就是该
高级语言 。
?每个程序定义了计算机的初态, 程序执行的规则定义了程序
执行过程中状态的变迁序列, 程序执行结果由程序执行完成
后计算机的终态决定 。
?给定一个精确的计算机定义, 总是可能将其用硬件实现,
从而可使计算机的机器语言为 C,Ada,或其他高级语言 。
?如此考虑的一个重要的基本原则是：任何精确定义的算法
或数据结构可以用硬件实现 。
?计算机简单地是算法和数据结构的集合, 我们可以假定其
硬件实现是可能的, 不管其复杂度和相应的机器语言 。
?实际的计算机通常有相当低级的机器语言 。 高级语言作为
机器语言会使机器非常复杂, 具应用灵活性较差 。
?一个具有低级通用指令集和简单的, 无结构的主存和寄存
器的计算机 可以被编程为相当广范围的高效计算机 。
?一个常用的选择 （ 相对于计算机的严格硬件实现 ） 是固件
计算机, 由运行在特殊的微可偏程硬件计算机上运行的微
程序来仿真 。
?这种计算机的机器语言是绝对低级的微指令集, 用微指令
集可编码得到微程序, 微程序将仿真所希望的计算机的操
作, 并定义了解释周期和各种基本操作 。
?通常微程序本身驻留在特殊的只读存储器中, 由宿主机硬
件高速执行, 这种计算机在执行速度上和硬件直接实现计
算机无太大差别 。
?计算机的微程序仿真有时可称为 emulation（ 仿真 ）, 该计
算机称为虚拟机, 因为机器本身并不存在 。
翻译器和软件仿真计算机
?理论上, 有可能直接构造硬件或固件计算机, 运行任何特
殊的程序设计语言, 但构造这样的计算机并不经济 。
?现实的考虑是实际计算机采用低级机器语言 （ 基于速度,
灵活性和价格考虑 ）, 编程仍以高级语言进行 。 语言实现
者面临的任务是如何使高级语言程序执行在实际计算机上,
不管其机器语言 。
?这个实现问题有两个基本方案。
1、翻译（编译）
高级语言程序 → 翻译器 → 等价的机器语言程序 → 硬件直
接执行
源语言 → 目标语言
几种特殊类型的翻译器,
A、汇编器
目标语言：实际计算机的机器语言
源 语 言：汇编语言, 机器语言的符号表示
大多数指令是一对一的翻译
B、编译器
目标语言：汇编和机器语言
源 语 言：高级语言
C、装配器或连接编辑器（ loader/link editor）
目标语言：实际的机器代码
源 语 言：几乎相同于机器代码，通常包含可重定位
的机器语言程序和数据表（刻划可重定位代码为变
成真正可执行所必须修改的地方）
D、预处理器或宏处理器
源 语 言：某种高级语言的扩展形式
目标语言：同样语言的标准形式 。
通常进行宏替换。
?高级源语言到可执行机器语言的翻译通常涉及多个翻译步
骤，有时，编译本本身也涉及多遍（多步），如：先产生
某种中间形式。
2、软件仿真（软件解释）
我们可以通过运行在另一台宿主机上的程序仿真一台计
算机，其机器语言为高级语言。
用宿主机的机器语言构造一个程序集（表达高级语言执
行必需的算法和数据结构），即用软件构造运行于宿主
机上的高级语言计算机，称为高级语言计算机在宿主机
上的软件仿真（或软件解释）。
仿真计算机接受高级语言程序作为输入，主仿真器程序
完成解释算法（解码并执行语言），最后从程序产生输
出。
软件仿真和翻译的不同,
均以高级语言程序为输入，但是,
翻译为目标码后再运行于实际计算机上
仿真计算机直接执行输入程序
翻译器以物理输入顺序处理程序语句, 每个语句只处理
一次 。
仿真器以逻辑控制流处理程序, 可能重复处理某些语句
而完全忽略其他语句 。
纯粹的翻译和纯粹的仿真形成两个极端
全翻译是很少的, 除了输入语言和输出语言非常相
似, 如汇编语言 。
全仿真也非常少, 除了操作系统控制语言或交互式
语言情形 。
通常语言实现是二者的结合 。 如图所示 。
?翻译和仿真各有不同优点
有的程序结构最好翻译成更简单的形式, —— 如循环中
语句多次执行, 翻译可省去解码时间 。 有的方面最好保
持原有形式, 在执行时根据需要处理 。
翻译的主要缺点是失去了关于程序的一些信息 。
单个的高级语言语句比单条机器语言指令含有更多信
息 。
仿真的优缺点基本正好相反 。
不需要太多的空间来存储代码序列的多份拷贝 。 但解
码代价高 。
通常, 如源语言结构在目标语言中有直接表示, 则代码
扩展不太严重, 可采用翻译 。 其他情形, 可采用仿真 。
是否程序执行时的基本表示为实际机器的机器语言，形成
了语言划分的基础。
1、编译型语言。如,C,C++,Fortran,Ada等
源语言翻成机器码, 仿真仅限于一些运行支持例程 （ 用
于仿真源语言中和机器语言没有紧密类似的基本操作 ） 。
通过硬件解释器, 可实现更快的程序执行 。
当然，也可能有的部分仍采用软件仿真，如数据控制结
构和存储管理。
2、解释型语言。如,LISP,ML,Prolog,Smalltalk等
翻译器不是产生机器代码, 而是产生某种中间形式, 比
源语言更易执行 。
然后使用软件解释器对中间代码进行执行 。 通常执行慢,
也需要对基本操作, 存储管理和其他语言特性的仿真,
这类语言翻译器很简单，更多的复杂性在软件仿真。
2.2 虚拟计算机和绑定时间
?计算机的构造方式
1、通过硬件实现，直接使用物理设备
2、固件实现，在合适的硬件计算机上使用微程序设计
3、软件仿真，在宿主机上用某种语言实现
4、上述技术的组合，各自选择合适的实现方式
?当一个程序设计语言被实现, 程序执行时使用的运行时数据结
构和算法定义了一个计算机 。 类似计算机的固件实现, 我们称
其为由语言实现定义的虚拟计算机 。
该虚拟机的机器语言是该语言的翻译器产生的可执行程序
（ 形式：对编译是实际的机器码形式；对解释是某种任意
结构 ） ；其数据结构是程序运行时使用的运行时数据结构；
基本操作是那些运行时实际可执行的；顺序控制, 数据控
制和存贮管理结构也是那些运行时使用的, 不管其是用软
件, 硬件或微程序表示 。
语法和语义
?语法：程序看起来象什么 。
语法规则规定了如何书写语句, 声明和其他语言结构 。
?语义：对各种语法结构赋予的含义 。
?在语言手册和其他语言描述中, 通常围绕语言中的各种语
法结构组织语言描述 。 典型地, 给出语法 （ 对一个语言结
构, 如语句, 声明 ）, 然后给出语义, BNF是主要的语法
记号体系 。
?本书的组织方式略有不同，围绕和虚拟机相关联的结构来
组织，这种风格用用在虚拟机中的数据结构和操作来描述
语言的语义。
?有时，这些数据结构和操作是直接和语言语法中的特殊结
构相关联的，而通常，这种联系并不是太直接。如,Pascal
虚拟机中可能在程序执行中使用向量，而向量结构是在声
明中直接给出的；然而，虚拟机也可能有其它不能在程序
中直接可见数据结构，如子程序“活跃记录”的中心栈。
?这些“隐藏”的虚拟机结构和那些直接对应程序员写在程
序中的某些东西的“可见”结构一样，对更好地了解语言
同等重要。
?因此，这里的讨论是围绕在虚拟机中看到的结构，而不仅
仅是语法元素来进行的。
?一个特殊的虚拟机元素可能
在程序中没有语法表示；
可被单个语法元素直接表示；
可被几个分开的语法元素表示（由翻译器合起来产生一
个虚拟机元素）。
虚拟机和语言实现
?如果语言用它们的虚拟机来定义, 使得每个语言和一个共
同理解的虚拟机相关联, 则使用虚拟机来描述语言的语义是
直接的 。
?然而, 语言定义通常是个体地对每个语法结构给出语义,
语言定义仅隐含地刻划了一个虚拟机 。
?语言在不同计算机上的每次实现, 实现者都会从语言定义
中看到略微 （ 或非常 ） 不同的虚拟机 。 同一语言的两个不同
实现, 可能使用不同的数据结构和操作集合 （ 特别是在语法
中隐藏的部分 ） 。
?每个实现者有很大自由度确定自己的虚拟机结构, 这些是
他的语言实现的基础 。
?当语言在一特定计算机上实现时, 实现者首先确定表示语言
的语义解释的虚拟机, 然后通过基本计算机提供的软, 硬件
元素来构造虚拟机 。 语言实现的组织和结构由实现者的许多
细微决策确定, 需考虑计算机各种软, 硬件设施和使用代价 。
例：虚拟机如有整数加和平方根操作, 则整数加可直接
用硬件提供的整数加来实现, 平方根可用软件仿真, 使
用一个子程序 。
整数变量 x可直接用存储位置实现, 该位置存放 x的值；
也可带有标记, 由标记和指针 （ 扩向存取 x值的位置 ） 构
成 ） 。
?实现者还需确定什么通过翻译处理？ 什么在执行中解决？
通常, 如果在程序翻译并建立运行时结构的过程中, 采
用了某些动作, 则可以使用一个特定的表示虚拟机数据
结构或操作的方式 。 如果实现者略去这些动作而简化翻
译器, 则不同的运行时表示可能是必须的 。
?三个因素导致相同语言的不同实现
1、实现者虚拟机概念的不同（隐含在语言定义中）
2、宿主机提供的设施的不同
3、实现者如何用宿主机提供的设施仿真虚拟机元素的
选择和如何去构造翻译器支持这些虚拟机选择的不同。
计算机层次
程序员以某种高级语言编程使用的虚拟机事实上形成了一
个虚拟计算机层次。
?底层：实际的硬件计算机。
通常程序员很少直接使用这个计算机，一般地，硬件机
被一个或多个软件层（或微程序）变换成一个虚拟机，
它可能和硬件机有很大不同。
?二层：由称为操作系统的例程集合定义的虚拟机（如微程
序形成第二层，那么这也可称为第三层）。
典型地,OS提供了一系列新的操作和数据结构的仿真
（这不是由硬件直接提供的）。如：外部文件结构或文
件管理原语。
OS也从 OS定义的虚拟机上删去了某些硬件原语，使得它
们不能由操作系统用户直接访问。如：关于 I/O、错误监
测、多道程序设计和多道处理的硬件原语。
OS定义的虚拟机通常就是高级语言实现者使用的机器。
?三层：语言实现者提供了一个新的软件层，运行于 OS虚拟
机上，仿真高级语言虚拟机的操作；也提供了翻译器：将
用户程序翻译成语言定义虚拟机的机器语言。
?四层：高级语言定义的虚拟机并不是层次的最后一层。实
际上，程序员编制的程序形成了新的一层虚拟机。
那么, 什么是这个程序员定义的软件仿真虚拟机的机器
语言呢？ （ 这个程序的输入数据将由这个机器语言构成
或写成 ） 。
一旦程序员建立了一个程序, 必须有一个, 程序, 在该
程序定义的虚拟机上运行, 这个, 程序, 通过选择合适
的输入数据集合而写成 。
这个概念之所以难于理解, 是因为对很多程序而言, 输
入数据非常简单, 仅仅可称为最平凡的程序设计语言 。
如：排序程序的机器语言可认为是整数集, 即以一定格
式构成的整数表为程序 。
然而, 明显的是：每一个在我们上述层次上构造较低层
次的程序员必须记住这个观点, 因为在每一层构造的程
序和数据结构事实上表示了下一层程序员编程使用的虚
拟机的仿真 。
?上面讨论中一个隐含的中心概念是：程序和数据是等价的 。
我们习惯于在编程中将对象区分为, 程序, 和, 数据,,
这通常是一种有用的直觉的区分, 但如上所讨论, 这种
区分是一种表面性的 。
在某语境中的程序可能在另外的语境中变成数据 。
如：我们写 Pascal程序, 但对 Pascal编译器来说, 该程序
是被输入处理的数据, 其输出是机器语言程序 。 如果观
察程序的执行, 你会发现它又是执行计算机中解释器的
数据 。 我们总是将某程序的输入等价为将被处理的数据
或将被执行的程序 。
进一步考虑这个问题（等价性）。如：在 C,Fortran语
言中，表示可执行程序的存储空间通常是和其数据空间
分开的。但在 LISP和 Prolog中，则没有不同，程序和数
据是混合的，只有执行过程可将其区分开来。
绑定和绑定时间
?不严格地说, 一个程序元素到某特定特征或性质的绑定,
仅是从一个可能性质的集合中性质的简单选择 。 决定这个选
择的程序陈述或处理的时间称为性质对元素的绑定时间 。
?语言中有不同的绑定和不同的绑定时间 。
?绑定时间的类型
对绑定类型没有简单的分类, 但可区分出一些主要的绑
定时间 。 这里, 我们基于一个基本假设：程序的处理总
是先翻译, 后执行 。
1,执行时 （ 运行时 ）
很多绑定是在程序执行过程中完成的 。 如：变量到值的
绑定, 变量到特定存储位置的绑定 （ 在很多语言中 ） 。
进一步可分为,
a,进入子程序或块时。
大多数语言中，重要的绑定只限制发生在执行中进
入子程序或块时，如 C,Fortran中形参到实参、以及
形参到特定存储位置的绑定。
b.在执行中的任意点。
某些绑定可以发生在程序执行中的任意点，如：变
量通过赋值到值的绑定，以及在 LISP,ML中，名字
到存储位置的绑定。
2、翻译时（编译时）绑定，可进而分为三种,
a,程序员选定的绑定
写程序时，程序员有很多关于变量名、变量类型、
程序语句结构等选择的决定，这些决定代表了翻译
的绑定，语言翻译器使用这些绑定确定目标程序的
最终形式。
b,翻译器选择的绑定
有些绑定由翻译器决定, 没有直接的程序员规约 。
如：数据对象在为某过程分配的存储区域中的相对
位置 （ 程序员不知道也不关心 ）, 数组如何存储,
数组描述子如何创建等 。 不同的语言实现可能以不
同方式提供这些特性 。
c,装配器选定的绑定 （ 链接时 ）
程序通常包含几个子程序, 这些子程序被合并为一
个可执行程序 。 翻译器决定变量到每个子程序中存
储地址的绑定, 这些存储必须被分配物理机中的实
际地址 。
3、语言实现时
语言定义的某些方面可能对所有运行于同一语言实
现上的程序均是相同的, 但可能由于语言实现不同
而不相同 。
如：通常和数的表示以及算术操作的表示相关的细
节由底层硬件机进行算术的方式确定 。
以某语言编写的程序，如果使用了在实现时固定的
特性，则不一定可以运行在该语言的另一实现上，
也可能有不同执行结果。
4、语言定义时
语言的大多数结构是在语言定义时固定的（对程序
员写程序时可用的规约）。如：对程序员可以使用
的选择语句形式、数据结构类型、程序结构等。
?考虑下面简单例子,X:=X+10，假定该语言为 L，则需考虑
的绑定和绑字时间如下,
1、变量 X的可能类型的集合
变量 X在语句中通常和某类型相关联, 如实数, 整数,
布尔, X的允许类型集合通常在语言定义时固定, 如
类型只能是：实数, 整数, 布尔, 集合, 字符等 。
此外, 语言可能允许程序定义新类型, 此时 X的类型
绑定在翻译时固定 。
2,X的类型
通常在翻译时固定, 通过显式的声明语句, 如：
Float X。 有些语言, 如 Smalltalk,Prolog,类型绑定
在运行时完成 （ 无类型, 弱类型语言 ） 。
3、变量 X的可能值的集合
如 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允许递归，就修改了很多重要
特性的绑定时间，因为绑定时间是实现依赖的。
2.3 语言范型
?前面讨论了实际的计算机环境, 它包含程序的翻译后目标
码, 以及提供运行时数据存储和操作的虚拟机 （ 为了目标
码的执行 ） 。
?下面将讨论语言支持的计算模型 （ 程序如何执行？ 语言提
供什么种类的结构？ ）
?通常, 不同语言的拥护者聚在一起, 争论的问题常是,
数组声明的形式 （ C,Fortran中各不同 ）
解释和编译的价值, 等 。
?然而, 这些不同对语言间的差异并无本质影响, 语法上的
不同只反映了设计者的希望, 对写成的程序也无多大影响 。
?有四种基本的计算模型,
1、命令型语言（ Imperative language）
也称过程型（ procedural）、命令驱动的、或面向语句的。
其基本概念是机器状态, 程序由一组语句构成, 每各语
句的执行, 将使得解释器改变某些存储位置的值, 进入
新状态 。
程序形式一般为,
statement 1;
statement 2;…
如图示, 内存包含一组盒子, 语句的执行 （ 如将两个变
量相加而得到第三个变量 ） 可被表示为访问存储位置,
以某种方式组合这些值, 将结果存到新的位置 。
程序的开发涉及建造连续的, 要到达最终答案所需的机
器状态 。 即, 建立连续的机器状态, 最终达到结果 。
大多数传统语言采用这种模型, 遵循传统计算机的结构,
顺序地执行指令 。
2、作用型语言（ applicative）
另一种看待语言完成的计算的视角是：看程序所表示的
功能, 而不是程序执行时的状态变化 。
我们只观察希望的结果, 而不是可用的数据 。 即不关心
机器为得到结果所经过的状态顺序 。
这样问题就变成：这个函数 （ 功能 ） 是什么？ 它通过访
问初始变量集, 而被作用到初始机器状态, 以特殊方式
组合, 得到结果 。
程序开发：以已有函数为基础开发新的复杂函数, 最终
的函数作用将得到结果 。
程序执行：连续的函数变换,f1(f2(f3(……)) 。
通常也称函数式语言。引用透明性是一个主要特征。
3、基于规则的语言（逻辑型语言）
检查当前条件, 当其得到满足时, 执行合适的动作 。
如图 25,使用过滤集作用到数据存储上以使能状态变化 。
其执行类似命令式语言, 但语句不是顺序的, 使能条件
将决定执行顺序 。
使能条件 1→ 动作 1
使能条件 2→ 动作 2
┋
使能条件 n→ 动作 n
Prolog语言采用这种范型 。 其它如决策表的业务应用也
是一种基于规则的程序设计 。
4,OO语言
当前最重要, 流行的计算模型 。
建立复杂数据对象，限定该对象上的操作集合，并封
装在一起。
复杂对象是简单对象的扩展，继承简单对象的性质。
实际上使用了其他两种计算模型的优点,
具体数据对象 —— 有命令型语言的效率,
限定功能类到具体数据对象 —— 应用型模型的灵活
性和可靠性。
?计算模型概论
前面的讨论, 我们使用, 支持,, 而不是, 实现, 某计算
模型 。
语言的使用依赖于程序员 。 命令型语言适合面向
语句的程序设计, 但也可以用 LISP,Prolog写出实质上
顺序执行并完成相同功能的程序 。
用 C语言也可以写出具有函数调用的程序 —— 作用型 。
历史上：命令型语言最早广泛使用, 一直占据统治地位 。
70— 80年代, 作用型语言提供了验证和证明程序正确的好
方式 。
图 2.6（ a） 无结构的流程图 。 程序没有明显的结构 。
图 2.6（ b） 结构化图, 可分为 4个功能函数, 因此, 也可算
作用型, 有 4个函数 。
语言设计问题
?早期的语言设计需使程序能高效地运行于昂贵的硬件上，因此，
早期语言总以翻译成高效的机器码为目标，既使程序难以书写。
?现在，硬件价格下降、软件价格上升，更强调程序容易书写，
即使慢点也可。 例如,ML的类型特性,C++的类,Ada的
Package均在执行速度上有代价，但对保证程序正确性有帮助。
?开发语言时，有三个影响语言设计的主要因素,
计算机本身
在计算机上支持语言的执行模型，即虚拟计算机
语言所实现的计算模型
2.1 计算机的结构和操作
?一个计算机是能够存储和执行程序的数据结构和算法的集成集
合。
?计算机可构造为实际的物理设备，用导线、集成电路、电路板
等。此即实际计算机或称硬件计算机。
?计算机构造为软件，用运行于其他计算机上的程序。此即软件
仿真计算机。
?程序设计语言的实现是通过一个翻译器，将以语言书写的程序
翻译为机器语言程序（可为某计算机直接执行，可以是硬件计
算机，也可以为软硬参杂的虚拟机）。
?一个计算机包含 6个主要部件，它们紧密地对应于程序设计
语言的主要方面。
1、数据：计算机必须提供各种基本数据项和操作的数据
结构。
2、基本操作：必须提供对操作数据有用的基本操作集。
3、顺序控制：必须提供控制基本操作执行顺序的机制。
4、数据访问：必须提供控制向操作的执行供给数据的机
制。
5、存储管理：必须提供控制程序和数据存储分配的机制。
6、操作环境：必须提供与包围程序和被处理数据的外部
环境通讯的机制。
计算机硬件
?一个典型的传统计算机组织如下,
包括程序和被处理的数据
操作主存和高速缓存中的数据
在主存和外部环境间传递程序或数据
完成处理工作
取机器指令
解码
调用指定的基本操作，以指定的操作数作为输入
?数据
有三个主要的存贮部件：主存，高速寄存和外部文件。
主存：组织为线性位串，可分为定长的字（ 32或 64）或 8
位字节。
寄存器：字长度的位串，可能有特殊的子域可直接访问，
可存数据或主存地址。
外部文件：存在盘、带或 CD-ROM上，按记录划分，记
录是位或字节的序列。
一个计算机有被硬件基本操作直接操作的固有数据类型。
一般有：整数、单精度实数（浮点数）、定长字符串、
定长位串等。
除了明显的硬件数据元素外，程序（也有固有的内部表
示，称为机器语言表示）也是一种数据形式。
机器语言程序可构造为存储位置的序列，每个包含一或
多条指令，每条包括操作码和若干操作数（指示）。
?操作
计算机必须包含有一个固有的基本操作集，通常和机器
语言指令中操作码一一对应。
典型的操作集包括在固有数值类型上的基本算术操作。
测试数据项各种性质的基本操作 。
访问和修改数据项的基本操作 。
控制 I/O设备的基本操作 。
顺序控制的基本操作。
传统的机器是 CISC,complex instruction set computers,
新近发展的是 RISC,reduced instruction set computers,
更少的基本指令，更简单的内部逻辑。
?顺序控制
程序地址寄存器（位置计数器）的内容决定了下一条将
执行的指令，即包含了下条指令的地址。
某些基本操作允许修改程序寄存器，从而传递控制到程
序的其他部分。
解释器实际地使用程序地址寄存器并指导操作序列。
解释器是计算机操作的中心，其周期动作如图所示,
?数据访问
除了操作码外, 每个机器指令必须指明所需的操作数
（ 必须在主存或寄存器中 ）
计算机必须结合指定操作数的手段和从给定操作数指示
器检索操作数的机制 。 同时, 操作的结果也必须存储在
指定的位置 。
传统的存储控制机制是为存储位置设定整数地址, 提供
操作从给定地址的位置检索内容和存储新值 。
寄存器也赋以整数地址 。
?存储管理
机器设计的一个驱动原则是保持所有计算机资源尽可能
多地被使用，中心冲突是,
CPU中的操作是纳秒级（一个操作 10— 50ns）
访问主存是是微秒级（ 0.1~0.2微秒,100— 200ns）
外部数据操作是毫秒级（ 15— 30毫秒）
这样在内外速度间相差 1000,000倍。
为了平衡速度差异，各种存储管理机制是必须的。
1、在最简单的设计（如低价 PC）中，只有简单的存
储管理设施。程序和数据执行时驻留内存，在一个时
刻只有一个程序准备执行。虽然 CPU必须等待数据，
它也是价格有效的，因为不需加入附加硬件。
2、为加速外部数据访问和 CPU间的平衡，操作系统
常使用多道程序设计，当等待毫秒去读数据时，计算
机将执行另一个程序。为了保证多个程序同时驻留主
存，通常有硬件设施负责页面查找或动态程序重定位，
页面查找通过预测进行，预测在最近将来最可能使用
的页面，将其放入主存。如在主存，则程序执行，否
则，出现页间错，操作系统将从外存中读取所需页，
同时执行别的程序。
3、为加速主存和 CPU间的不平衡，常使用 Cache存储
器（小的高速数据存储）。 Cache可允许计算机操作，
好象主存具有和 CPU相同速度，通常是 1K到 256K字
节,32K的 Cache，可达到 95%的选中率。
?操作环境
计算机的操作环境通常包括外围存储器和 I/O设备，这些
设备表示了计算机的外部世界，和计算机的任何通讯必
须通过它们。
操作环境中通常有硬件的不同，如：高速存储（扩展内
存），中速存储（磁盘），低速存储（磁带）和 I/O设备。
?各种计算机体系结构
计算机硬件的组织有多种形式，上面的讨论是基于 Von
Neumann体系结构。
Von Neumann体系结构,
命名来源于数学家 John von Neumann，他在 40年代开
发这个初始设计，作为 ENIAC计算机设计的一部分，
现今计算机仍属此体系结构。
多处理器,
Von Neumann设计的最大问题是外部数据设备的慢速
和 CPU寄存器高速间的矛盾 。 解决方案之一是在指定
系统中使用多个 CPU,这样的多处理系统已使用了 30
多年, 通过几个相对不昂贵的 CPU的粘合, 再加上单
一的主存, 磁盘, 磁带等, 得到一个高效系统 。 操作
系统将不同程序运行于不同 CPU上, 从而整个性能得
到改善 。
语言和系统设计正在演化，使得能够书写程序在多个
计算机上执行并相互通讯。
?计算机状态
对计算机静态组织的了解只是一个部分, 全面了解则涉
及计算机在程序执行时的动态操作, 包括,
执行开始时各存储部件的内容, 操作执行顺序 。
执行进行时如何修改各种数据部件, 程序执行的最后
结果等 。
通常对计算机动态行为的观察是通过计算机状态 （ 执行
过程中某点主存, 寄存器和外存的内容决定 ） 的概念 。
程序的执行体现为一系列状态的变化
初始状态通过一系列状态变迁 （ 从当前状态通过存贮内
容的修改进入新的状态 ）, 得到最终状态 。
如果我们可以预测状态变迁序列，则可以声称了解了计
算机的动态行为。
固件计算机
?如前定义, 计算机 =算法集 +数据结构集
可执行程序表示为计算机的机器语言程序
?通常认为计算机操作在相当低级的机器语言之上, 具有简单
的指令格式 。 然而, 机器语言并不一定限制到低级 。
?可以选择任何程序设计语言, 精确地刻划数据结构集和定义
程序执行规则的算法, 这样该计算机的, 机器语言, 就是该
高级语言 。
?每个程序定义了计算机的初态, 程序执行的规则定义了程序
执行过程中状态的变迁序列, 程序执行结果由程序执行完成
后计算机的终态决定 。
?给定一个精确的计算机定义, 总是可能将其用硬件实现,
从而可使计算机的机器语言为 C,Ada,或其他高级语言 。
?如此考虑的一个重要的基本原则是：任何精确定义的算法
或数据结构可以用硬件实现 。
?计算机简单地是算法和数据结构的集合, 我们可以假定其
硬件实现是可能的, 不管其复杂度和相应的机器语言 。
?实际的计算机通常有相当低级的机器语言 。 高级语言作为
机器语言会使机器非常复杂, 具应用灵活性较差 。
?一个具有低级通用指令集和简单的, 无结构的主存和寄存
器的计算机 可以被编程为相当广范围的高效计算机 。
?一个常用的选择 （ 相对于计算机的严格硬件实现 ） 是固件
计算机, 由运行在特殊的微可偏程硬件计算机上运行的微
程序来仿真 。
?这种计算机的机器语言是绝对低级的微指令集, 用微指令
集可编码得到微程序, 微程序将仿真所希望的计算机的操
作, 并定义了解释周期和各种基本操作 。
?通常微程序本身驻留在特殊的只读存储器中, 由宿主机硬
件高速执行, 这种计算机在执行速度上和硬件直接实现计
算机无太大差别 。
?计算机的微程序仿真有时可称为 emulation（ 仿真 ）, 该计
算机称为虚拟机, 因为机器本身并不存在 。
翻译器和软件仿真计算机
?理论上, 有可能直接构造硬件或固件计算机, 运行任何特
殊的程序设计语言, 但构造这样的计算机并不经济 。
?现实的考虑是实际计算机采用低级机器语言 （ 基于速度,
灵活性和价格考虑 ）, 编程仍以高级语言进行 。 语言实现
者面临的任务是如何使高级语言程序执行在实际计算机上,
不管其机器语言 。
?这个实现问题有两个基本方案。
1、翻译（编译）
高级语言程序 → 翻译器 → 等价的机器语言程序 → 硬件直
接执行
源语言 → 目标语言
几种特殊类型的翻译器,
A、汇编器
目标语言：实际计算机的机器语言
源 语 言：汇编语言, 机器语言的符号表示
大多数指令是一对一的翻译
B、编译器
目标语言：汇编和机器语言
源 语 言：高级语言
C、装配器或连接编辑器（ loader/link editor）
目标语言：实际的机器代码
源 语 言：几乎相同于机器代码，通常包含可重定位
的机器语言程序和数据表（刻划可重定位代码为变
成真正可执行所必须修改的地方）
D、预处理器或宏处理器
源 语 言：某种高级语言的扩展形式
目标语言：同样语言的标准形式 。
通常进行宏替换。
?高级源语言到可执行机器语言的翻译通常涉及多个翻译步
骤，有时，编译本本身也涉及多遍（多步），如：先产生
某种中间形式。
2、软件仿真（软件解释）
我们可以通过运行在另一台宿主机上的程序仿真一台计
算机，其机器语言为高级语言。
用宿主机的机器语言构造一个程序集（表达高级语言执
行必需的算法和数据结构），即用软件构造运行于宿主
机上的高级语言计算机，称为高级语言计算机在宿主机
上的软件仿真（或软件解释）。
仿真计算机接受高级语言程序作为输入，主仿真器程序
完成解释算法（解码并执行语言），最后从程序产生输
出。
软件仿真和翻译的不同,
均以高级语言程序为输入，但是,
翻译为目标码后再运行于实际计算机上
仿真计算机直接执行输入程序
翻译器以物理输入顺序处理程序语句, 每个语句只处理
一次 。
仿真器以逻辑控制流处理程序, 可能重复处理某些语句
而完全忽略其他语句 。
纯粹的翻译和纯粹的仿真形成两个极端
全翻译是很少的, 除了输入语言和输出语言非常相
似, 如汇编语言 。
全仿真也非常少, 除了操作系统控制语言或交互式
语言情形 。
通常语言实现是二者的结合 。 如图所示 。
?翻译和仿真各有不同优点
有的程序结构最好翻译成更简单的形式, —— 如循环中
语句多次执行, 翻译可省去解码时间 。 有的方面最好保
持原有形式, 在执行时根据需要处理 。
翻译的主要缺点是失去了关于程序的一些信息 。
单个的高级语言语句比单条机器语言指令含有更多信
息 。
仿真的优缺点基本正好相反 。
不需要太多的空间来存储代码序列的多份拷贝 。 但解
码代价高 。
通常, 如源语言结构在目标语言中有直接表示, 则代码
扩展不太严重, 可采用翻译 。 其他情形, 可采用仿真 。
是否程序执行时的基本表示为实际机器的机器语言，形成
了语言划分的基础。
1、编译型语言。如,C,C++,Fortran,Ada等
源语言翻成机器码, 仿真仅限于一些运行支持例程 （ 用
于仿真源语言中和机器语言没有紧密类似的基本操作 ） 。
通过硬件解释器, 可实现更快的程序执行 。
当然，也可能有的部分仍采用软件仿真，如数据控制结
构和存储管理。
2、解释型语言。如,LISP,ML,Prolog,Smalltalk等
翻译器不是产生机器代码, 而是产生某种中间形式, 比
源语言更易执行 。
然后使用软件解释器对中间代码进行执行 。 通常执行慢,
也需要对基本操作, 存储管理和其他语言特性的仿真,
这类语言翻译器很简单，更多的复杂性在软件仿真。
2.2 虚拟计算机和绑定时间
?计算机的构造方式
1、通过硬件实现，直接使用物理设备
2、固件实现，在合适的硬件计算机上使用微程序设计
3、软件仿真，在宿主机上用某种语言实现
4、上述技术的组合，各自选择合适的实现方式
?当一个程序设计语言被实现, 程序执行时使用的运行时数据结
构和算法定义了一个计算机 。 类似计算机的固件实现, 我们称
其为由语言实现定义的虚拟计算机 。
该虚拟机的机器语言是该语言的翻译器产生的可执行程序
（ 形式：对编译是实际的机器码形式；对解释是某种任意
结构 ） ；其数据结构是程序运行时使用的运行时数据结构；
基本操作是那些运行时实际可执行的；顺序控制, 数据控
制和存贮管理结构也是那些运行时使用的, 不管其是用软
件, 硬件或微程序表示 。
语法和语义
?语法：程序看起来象什么 。
语法规则规定了如何书写语句, 声明和其他语言结构 。
?语义：对各种语法结构赋予的含义 。
?在语言手册和其他语言描述中, 通常围绕语言中的各种语
法结构组织语言描述 。 典型地, 给出语法 （ 对一个语言结
构, 如语句, 声明 ）, 然后给出语义, BNF是主要的语法
记号体系 。
?本书的组织方式略有不同，围绕和虚拟机相关联的结构来
组织，这种风格用用在虚拟机中的数据结构和操作来描述
语言的语义。
?有时，这些数据结构和操作是直接和语言语法中的特殊结
构相关联的，而通常，这种联系并不是太直接。如,Pascal
虚拟机中可能在程序执行中使用向量，而向量结构是在声
明中直接给出的；然而，虚拟机也可能有其它不能在程序
中直接可见数据结构，如子程序“活跃记录”的中心栈。
?这些“隐藏”的虚拟机结构和那些直接对应程序员写在程
序中的某些东西的“可见”结构一样，对更好地了解语言
同等重要。
?因此，这里的讨论是围绕在虚拟机中看到的结构，而不仅
仅是语法元素来进行的。
?一个特殊的虚拟机元素可能
在程序中没有语法表示；
可被单个语法元素直接表示；
可被几个分开的语法元素表示（由翻译器合起来产生一
个虚拟机元素）。
虚拟机和语言实现
?如果语言用它们的虚拟机来定义, 使得每个语言和一个共
同理解的虚拟机相关联, 则使用虚拟机来描述语言的语义是
直接的 。
?然而, 语言定义通常是个体地对每个语法结构给出语义,
语言定义仅隐含地刻划了一个虚拟机 。
?语言在不同计算机上的每次实现, 实现者都会从语言定义
中看到略微 （ 或非常 ） 不同的虚拟机 。 同一语言的两个不同
实现, 可能使用不同的数据结构和操作集合 （ 特别是在语法
中隐藏的部分 ） 。
?每个实现者有很大自由度确定自己的虚拟机结构, 这些是
他的语言实现的基础 。
?当语言在一特定计算机上实现时, 实现者首先确定表示语言
的语义解释的虚拟机, 然后通过基本计算机提供的软, 硬件
元素来构造虚拟机 。 语言实现的组织和结构由实现者的许多
细微决策确定, 需考虑计算机各种软, 硬件设施和使用代价 。
例：虚拟机如有整数加和平方根操作, 则整数加可直接
用硬件提供的整数加来实现, 平方根可用软件仿真, 使
用一个子程序 。
整数变量 x可直接用存储位置实现, 该位置存放 x的值；
也可带有标记, 由标记和指针 （ 扩向存取 x值的位置 ） 构
成 ） 。
?实现者还需确定什么通过翻译处理？ 什么在执行中解决？
通常, 如果在程序翻译并建立运行时结构的过程中, 采
用了某些动作, 则可以使用一个特定的表示虚拟机数据
结构或操作的方式 。 如果实现者略去这些动作而简化翻
译器, 则不同的运行时表示可能是必须的 。
?三个因素导致相同语言的不同实现
1、实现者虚拟机概念的不同（隐含在语言定义中）
2、宿主机提供的设施的不同
3、实现者如何用宿主机提供的设施仿真虚拟机元素的
选择和如何去构造翻译器支持这些虚拟机选择的不同。
计算机层次
程序员以某种高级语言编程使用的虚拟机事实上形成了一
个虚拟计算机层次。
?底层：实际的硬件计算机。
通常程序员很少直接使用这个计算机，一般地，硬件机
被一个或多个软件层（或微程序）变换成一个虚拟机，
它可能和硬件机有很大不同。
?二层：由称为操作系统的例程集合定义的虚拟机（如微程
序形成第二层，那么这也可称为第三层）。
典型地,OS提供了一系列新的操作和数据结构的仿真
（这不是由硬件直接提供的）。如：外部文件结构或文
件管理原语。
OS也从 OS定义的虚拟机上删去了某些硬件原语，使得它
们不能由操作系统用户直接访问。如：关于 I/O、错误监
测、多道程序设计和多道处理的硬件原语。
OS定义的虚拟机通常就是高级语言实现者使用的机器。
?三层：语言实现者提供了一个新的软件层，运行于 OS虚拟
机上，仿真高级语言虚拟机的操作；也提供了翻译器：将
用户程序翻译成语言定义虚拟机的机器语言。
?四层：高级语言定义的虚拟机并不是层次的最后一层。实
际上，程序员编制的程序形成了新的一层虚拟机。
那么, 什么是这个程序员定义的软件仿真虚拟机的机器
语言呢？ （ 这个程序的输入数据将由这个机器语言构成
或写成 ） 。
一旦程序员建立了一个程序, 必须有一个, 程序, 在该
程序定义的虚拟机上运行, 这个, 程序, 通过选择合适
的输入数据集合而写成 。
这个概念之所以难于理解, 是因为对很多程序而言, 输
入数据非常简单, 仅仅可称为最平凡的程序设计语言 。
如：排序程序的机器语言可认为是整数集, 即以一定格
式构成的整数表为程序 。
然而, 明显的是：每一个在我们上述层次上构造较低层
次的程序员必须记住这个观点, 因为在每一层构造的程
序和数据结构事实上表示了下一层程序员编程使用的虚
拟机的仿真 。
?上面讨论中一个隐含的中心概念是：程序和数据是等价的 。
我们习惯于在编程中将对象区分为, 程序, 和, 数据,,
这通常是一种有用的直觉的区分, 但如上所讨论, 这种
区分是一种表面性的 。
在某语境中的程序可能在另外的语境中变成数据 。
如：我们写 Pascal程序, 但对 Pascal编译器来说, 该程序
是被输入处理的数据, 其输出是机器语言程序 。 如果观
察程序的执行, 你会发现它又是执行计算机中解释器的
数据 。 我们总是将某程序的输入等价为将被处理的数据
或将被执行的程序 。
进一步考虑这个问题（等价性）。如：在 C,Fortran语
言中，表示可执行程序的存储空间通常是和其数据空间
分开的。但在 LISP和 Prolog中，则没有不同，程序和数
据是混合的，只有执行过程可将其区分开来。
绑定和绑定时间
?不严格地说, 一个程序元素到某特定特征或性质的绑定,
仅是从一个可能性质的集合中性质的简单选择 。 决定这个选
择的程序陈述或处理的时间称为性质对元素的绑定时间 。
?语言中有不同的绑定和不同的绑定时间 。
?绑定时间的类型
对绑定类型没有简单的分类, 但可区分出一些主要的绑
定时间 。 这里, 我们基于一个基本假设：程序的处理总
是先翻译, 后执行 。
1,执行时 （ 运行时 ）
很多绑定是在程序执行过程中完成的 。 如：变量到值的
绑定, 变量到特定存储位置的绑定 （ 在很多语言中 ） 。
进一步可分为,
a,进入子程序或块时。
大多数语言中，重要的绑定只限制发生在执行中进
入子程序或块时，如 C,Fortran中形参到实参、以及
形参到特定存储位置的绑定。
b.在执行中的任意点。
某些绑定可以发生在程序执行中的任意点，如：变
量通过赋值到值的绑定，以及在 LISP,ML中，名字
到存储位置的绑定。
2、翻译时（编译时）绑定，可进而分为三种,
a,程序员选定的绑定
写程序时，程序员有很多关于变量名、变量类型、
程序语句结构等选择的决定，这些决定代表了翻译
的绑定，语言翻译器使用这些绑定确定目标程序的
最终形式。
b,翻译器选择的绑定
有些绑定由翻译器决定, 没有直接的程序员规约 。
如：数据对象在为某过程分配的存储区域中的相对
位置 （ 程序员不知道也不关心 ）, 数组如何存储,
数组描述子如何创建等 。 不同的语言实现可能以不
同方式提供这些特性 。
c,装配器选定的绑定 （ 链接时 ）
程序通常包含几个子程序, 这些子程序被合并为一
个可执行程序 。 翻译器决定变量到每个子程序中存
储地址的绑定, 这些存储必须被分配物理机中的实
际地址 。
3、语言实现时
语言定义的某些方面可能对所有运行于同一语言实
现上的程序均是相同的, 但可能由于语言实现不同
而不相同 。
如：通常和数的表示以及算术操作的表示相关的细
节由底层硬件机进行算术的方式确定 。
以某语言编写的程序，如果使用了在实现时固定的
特性，则不一定可以运行在该语言的另一实现上，
也可能有不同执行结果。
4、语言定义时
语言的大多数结构是在语言定义时固定的（对程序
员写程序时可用的规约）。如：对程序员可以使用
的选择语句形式、数据结构类型、程序结构等。
?考虑下面简单例子,X:=X+10，假定该语言为 L，则需考虑
的绑定和绑字时间如下,
1、变量 X的可能类型的集合
变量 X在语句中通常和某类型相关联, 如实数, 整数,
布尔, X的允许类型集合通常在语言定义时固定, 如
类型只能是：实数, 整数, 布尔, 集合, 字符等 。
此外, 语言可能允许程序定义新类型, 此时 X的类型
绑定在翻译时固定 。
2,X的类型
通常在翻译时固定, 通过显式的声明语句, 如：
Float X。 有些语言, 如 Smalltalk,Prolog,类型绑定
在运行时完成 （ 无类型, 弱类型语言 ） 。
3、变量 X的可能值的集合
如 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允许递归，就修改了很多重要
特性的绑定时间，因为绑定时间是实现依赖的。
2.3 语言范型
?前面讨论了实际的计算机环境, 它包含程序的翻译后目标
码, 以及提供运行时数据存储和操作的虚拟机 （ 为了目标
码的执行 ） 。
?下面将讨论语言支持的计算模型 （ 程序如何执行？ 语言提
供什么种类的结构？ ）
?通常, 不同语言的拥护者聚在一起, 争论的问题常是,
数组声明的形式 （ C,Fortran中各不同 ）
解释和编译的价值, 等 。
?然而, 这些不同对语言间的差异并无本质影响, 语法上的
不同只反映了设计者的希望, 对写成的程序也无多大影响 。
?有四种基本的计算模型,
1、命令型语言（ Imperative language）
也称过程型（ procedural）、命令驱动的、或面向语句的。
其基本概念是机器状态, 程序由一组语句构成, 每各语
句的执行, 将使得解释器改变某些存储位置的值, 进入
新状态 。
程序形式一般为,
statement 1;
statement 2;…
如图示, 内存包含一组盒子, 语句的执行 （ 如将两个变
量相加而得到第三个变量 ） 可被表示为访问存储位置,
以某种方式组合这些值, 将结果存到新的位置 。
程序的开发涉及建造连续的, 要到达最终答案所需的机
器状态 。 即, 建立连续的机器状态, 最终达到结果 。
大多数传统语言采用这种模型, 遵循传统计算机的结构,
顺序地执行指令 。
2、作用型语言（ applicative）
另一种看待语言完成的计算的视角是：看程序所表示的
功能, 而不是程序执行时的状态变化 。
我们只观察希望的结果, 而不是可用的数据 。 即不关心
机器为得到结果所经过的状态顺序 。
这样问题就变成：这个函数 （ 功能 ） 是什么？ 它通过访
问初始变量集, 而被作用到初始机器状态, 以特殊方式
组合, 得到结果 。
程序开发：以已有函数为基础开发新的复杂函数, 最终
的函数作用将得到结果 。
程序执行：连续的函数变换,f1(f2(f3(……)) 。
通常也称函数式语言。引用透明性是一个主要特征。
3、基于规则的语言（逻辑型语言）
检查当前条件, 当其得到满足时, 执行合适的动作 。
如图 25,使用过滤集作用到数据存储上以使能状态变化 。
其执行类似命令式语言, 但语句不是顺序的, 使能条件
将决定执行顺序 。
使能条件 1→ 动作 1
使能条件 2→ 动作 2
┋
使能条件 n→ 动作 n
Prolog语言采用这种范型 。 其它如决策表的业务应用也
是一种基于规则的程序设计 。
4,OO语言
当前最重要, 流行的计算模型 。
建立复杂数据对象，限定该对象上的操作集合，并封
装在一起。
复杂对象是简单对象的扩展，继承简单对象的性质。
实际上使用了其他两种计算模型的优点,
具体数据对象 —— 有命令型语言的效率,
限定功能类到具体数据对象 —— 应用型模型的灵活
性和可靠性。
?计算模型概论
前面的讨论, 我们使用, 支持,, 而不是, 实现, 某计算
模型 。
语言的使用依赖于程序员 。 命令型语言适合面向
语句的程序设计, 但也可以用 LISP,Prolog写出实质上
顺序执行并完成相同功能的程序 。
用 C语言也可以写出具有函数调用的程序 —— 作用型 。
历史上：命令型语言最早广泛使用, 一直占据统治地位 。
70— 80年代, 作用型语言提供了验证和证明程序正确的好
方式 。
图 2.6（ a） 无结构的流程图 。 程序没有明显的结构 。
图 2.6（ b） 结构化图, 可分为 4个功能函数, 因此, 也可算
作用型, 有 4个函数 。
