• 第一章
  • Language Evaluation Criteria
  • Influences on Language Design
  • Language Categories
  • Implementation Methods
• 第二章
• 第五章
  • Names
  • Variables
  • The Concept of Binding
  • Type Checking
  • Strong Typing
  • Type Compatibility
  • Scope
  • Sope and Lifetime
  • Referencing Environments
• 第六章
  • Pointer Problems
• 第七章
  • Arithmetic Expressions
  • Overloaded Operators
• 第九章
  • Introduction
  • Fundamentals of Subprograms
  • Local Referencing Environments
  • Parameter-Passing Methods
  • Overloaded Subprograms
  • Separate and Independent Compilation
  • Accessing Nonlocal Environments
• 第十章
  • The General Semantics of Calls and Returns
  • Implementing FORTRAN 77 Subprograms
  • Implementing Subprograms in ALGOL-like Languages
• 第十一章
  • The Concept of Abstraction
  • Encapsulation
  • Introduction to Data Abstraction
• 第十三章
  • Introduction
  • Introduction to Subprogram-Level Concurrency
  • Semaphores
  • Message Passing

第一章

Language Evaluation Criteria

• 可读性

  正交性：指只用该语言的一组相对少量的基本结构，经过
  相对少的结合步骤，就可构成该语言的控制结构和数据结
  构。而且，它的基本结构的任何组合都是合法和有意义的。

• 可写性

• 可靠性

• 代价

Influences on Language Design

计算机体系结构和编程方法

Language Categories

• 命令式语言

  C,Pascal

• 函数式语言

  LISP,Scheme

• 逻辑语言

  Prolog

• 面向对象语言

  C++,Java

Implementation Methods

编译，C,COBLO,Ada 瓶颈，处理器和内存速度不匹配。

第二章

第一种编译式的高级语言：Fortran

迈向成熟的第一步：ALGOL 60

数据抽象的开始：SIMULA 67

历史上规模最大的语言设计：Ada

面向对象的程序设计：Smalltalk

第一种函数式程序设计语言：LISP

第五章

Names

关键字是程序设计语言中的一种字，它只在特定的上下文里是特殊的。Fortran语言中的特殊字就是关键字。

保留字是程序设计语言中的特殊字，它不能用作名字。作为语言设计的选择，保留字比关键字优越，因为重新定义关键字的功能会导致混淆。

Variables

变量是存储地址的名字，可以使用6种属性来刻画一个变量:名字、地址、数值、类型、生存期、作用域。

变量的地址是与这个变量相关联的存储地址。

有时也将变量地址称为变量的左值，这是因为变量通常位于赋值语句的左边。

多个变量可以具有同一个地址，当用多个变量名来访问单个存储地址时，这些变量名就成为别名。

一个变量的值是与这个变量相关联的存储单元的内容。变量的值有时被称为变量的右值，因为变量被用于赋值语句的右边时，则会要求这种变量值。要取得右值必须首先确定左值。

The Concept of Binding

绑定是一种关联，如存在于属性与实体之间的关联，或者操作与符号之间的关联。在程序中引用一个变量之前，变量必须被绑定到一种数据类型之上。这种绑定具有的两个重要方面是指定类型的方式以及绑定发生的时间。可以通过一些显示或隐式的声明来静态指定变量的类型。

显式声明是程序中的一条说明语句，它列出一批变量名并指明这些变量的特定类型。隐式声明则是通过默认协定的方法而不是声明语句将变量与类型相关联。在隐式声明的情况下，变量名在程序中的第一次出现即构成了它的隐式声明。显式声明与隐式声明都产生对类型的静态绑定。

在使用动态类型绑定时，变量的类型不是由声明语句来说明的，也不能够通过名字的拼法来确定，而是在赋值语句给变量赋值时，变量才与类型相绑定。在执行赋值语句时，被赋值的变量与赋值语句右边的表达式的值的类型相绑定。

如果一种绑定的第一次出现是在运行之时，并且在整个程序的执行过程中保持不变，我们称这种绑定为静态的。

如果一种绑定的第一次出现是在运行时期间，或者这种绑定可以在程序执行中被改变，我们称这种绑定为动态的。

Type Checking

类型检测是保证一个操作符的所有操作数都具有相互兼容类型的措施。兼容类型是对操作符而言为合法的类型，或者在语言规定的允许下，能够被编译器或解释器产生的代码隐式地转换成为合法的类型，这种自动类型的转换被称为强制转换。

Strong Typing

只要某个程序设计语言总能够发现其程序中的类型错误，我们就定义这种程序设计语言为强类型的。这就要求能够在编译时或运行时确定所有操作数的类型。强类型化的重要性在于它能够发现所有因为变量的误用而导致的类型错误。一种强类型的语言也允许在运行时检测能够存储多个类型值的变量中不正确类型值的使用。

Type Compatibility

假如在一个表达式中，一种类型的操作数被另一种类型的操作数替代而无强制性，那么这两种类型是等价的。类型等价是类型兼容的一种严格形式——没有强制性的兼容。

有两种不同的类型等价方法：名字等价以及结构等价。

名字类型等价意味着：两个变量具有按名等价的类型当且仅当它们一起被说明，或者用相同的类型标识符说明，即对应的类型名相同。

结构类型等价意味着:两个变量具有等价的类型，如果它们的类型具有完全相同的结构。（两个变量具有按结构等价的类型当且仅当变量的所有分量有相同类型的值集。）

按定义等价意味着：两个变量具有按定义等价的类型当且仅当两个变量有完全相同的类型（包括相同的域名）。除类型名外的其他特征均相同者即视为按定义等价。

Scope

作用域是理解变量的最重要因素之一。程序变量的作用域是语句的一个范围，在这个范围之内变量为可见的。如果一个变量在一条语句中可以被引用，这个变量即在这条语句中为可见的。

Sope and Lifetime

有时，变量的作用域和生命期似乎是相关的，但却是不同的概念。例如在C和C++中，一个在函数中由修饰符static声明的变量被静态地绑定于函数的作用域，同时也被静态地绑定于存储空间。所以这个变量的作用域是静态的，并且对这个函数为局部的，但它的生存期却扩展到了整个程序的执行期间。

Referencing Environments

一条语句的引用环境是这条语句中所有可见变量的集合。在静态作用域的语言中，一条语句的引用环境是在它的局部作用域所声明的变量和在它的祖先作用域所声明的所有可见变量的集合。

在动态作用域的语言中，一条语句的引用环境是局部声明的变量，加上当前活跃的其他子程序中的所有变量。一些活跃子程序中的变量可能对引用环境为隐藏的。最近的子程序活动可以具有变量声明，它隐藏了前一个子程序活动中具有的同名变量。

第六章

Pointer Problems

悬挂指针，或悬挂引用，是一个包含了已解除分配的堆动态变量地址的指针。

悬挂指针是危险的，首先，悬挂指针指向的位置可能已经被重新分配给一个新的堆动态变量，此外，如果是使用悬挂指针来改变堆动态变量，新堆动态变量的值就会被破坏，最后，这个位置很有可能当前暂时被管理系统所使用

丢失的堆动态变量是一个已经分配的堆动态变量，用户程序不可以再对它进行访问。常常称这种变量为垃圾，因为对于它们的原始目的，它们不再有用，并且它们也不可以为了某种新的用途通过程序给以重新分配。

第七章

Arithmetic Expressions

• Operand Evaluation Order

如果一个操作符的两个操作数都没有副作用，那么操作数的求值顺序是无所谓的。

• Side effects

当函数改变它的一个参数或者一个全局变量时，就会产生函数的副作用（或函数副作用）。（全局变量是被声明于函数之外，但可以在函数中访问的变量。）

Overloaded Operators

一个操作符的多种用途被称为操作符重载。

两个问题：使用同一个符号进行两种完全不相关的操作有损于可读性；编译器很难检测出错误。

第九章

Introduction

一种程序设计语言可以包括两种基本的抽象设施:过程抽象与数据抽象。过程抽象是所有程序设计语言中的主要概念。

第一台可编程的计算机是建造于20世纪40年代的Babbage的分析引擎(Analytical Engine ) ,它具有在程序中的一些不同位置上重复使用一系列指令卡片的能力。而现代的程序设计语言是将这样的语句系列编写成为子程序。这种重复使用导致了在几个不同方面的节省，从存储空间到程序的编码时间。这提高了子程序的可读性。

Fundamentals of Subprograms

子程序定义描述的是子程序的接口以及子程序的抽象行为。

子程序的参数描绘（有时也称为签名）是它所具有的形参的数目、次序以及类型。一个子程序的协议是这个子程序的参数描绘加上它的返回类型，如果它是函数的话。

子程序通常描述计算。有两种方法让子程序能够获取它所要处理的数据:通过对非局部变量的直接访问（在别处被声明，但在子程序中可见)，或者通过参数传递。

参数传递比对非局部变量的直接访问更灵活。

对于非局部变量的大量访问，将导致可靠性程度的降低。

子程序首部中的参数被称为形参。在大多数情况下，只有当子程序被调用时，它们才与存储空间相绑定，并且这种绑定通常经过了一些其他的程序变量。

子程序的调用语句必须包括子程序的名称，以及一组将与子程序中的形参相绑定的参数。这些参数被称为实参。

实参与形参之间的对应是简单地按位置进行的，这样的一些参数被称为位置参数。

关键字参数：将一个与实参相绑定的形参的名称与这个实参在一起说明。关键字参数的优越性是它们能够以任何顺序出现干实参表中。这种形式的唯一限制是，在一个关键字参数出现在列表中以后，必须将所有的其余参数关键字化。之所以这是有必要的，因为在关键字参数出现之后，参数位置的顺序就可能不再遵循原来的定义。

Local Referencing Environments

定义于子程序内部的变量被称为局部变量，因为这些变量的作用域通常就限定于定义他们的子程序之中。

局部变量可以为静态的，也可以为栈动态的。如果局部变量是栈动态的，当子程序开始执行之时，这些变量就与存储空间相绑定，并在执行终止时解除这种绑定。

栈动态的局部变量具有很多优点，其中的主要优点是它们为子程序提供了灵活性。栈动态局部变量的另一个优点是，在活跃子程序中的局部变量的存储空间可以与所有在非活跃子程序中的局部变量共享。

栈动态局部变量的主要缺点如下:首先，对于子程序的每一次调用，这种变量所需要的存储空间分配、初始化（当必要时）以及变量解除分配，都有时间上的代价。其次，对于栈动态局部变量的存取必须是间接的;而对于静态变量的存取则可以是直接的。最后一点，具有栈动态局部变量的子程序不是历史敏感的;也就是说，它们不能够在调用之间保持局部变量的数据值。

Parameter-Passing Methods

• pass-by-value

  当参数是按值传递时，实参的值将被用来为与其相对应的形参设定初值，然后这个形参的行为就像是子程序中的局部变量，并由此实现了输入型的语义。通常将按值传递实现为数据的复制，因为采用这种方法通常具有较高的存取效率。

• pass-by-result

  按结果传递是用于输出型参数的一种实现模式。当一个参数被按结果传递时，并没有将值传递到子程序。相对应的形参的行为就如同一个局部变量，但是在将控制返回到调用程序之前，形参值被传递给调用程序的实参，显然，这个实参必须是一个变量。(如果这个实参是一个字面常量或者一个表达式，调用程序怎么能够引用计算结果呢?)

  按结果传递模式中的一个额外的问题是可能会出现实参冲突，使用按结果传递的方式可能出现的另一个问题是实现人员可以选择在两个不同时刻对实参的地址求值:即在调用时，或在返回时。

• Pass-by-Reference

  按引用传递是对输入输出型参数的第二种实现模式。按引用传递的方式不像按值与结果传递那样，将数据值来回地复制;按引用传递的方式是给被调用子程序传递一条存取途径，通常就是一个地址。这给被调用子程序提供了对实参存储单位的存取途径。因此允许被调用子程序从调用程序单位中存取实参。在实际效果上，被调用子程序就共享了这个实参。

• Pass-by-Name

  按名传递是一种输入输出型参数的传递方法，它不对应于单个的实现模式。当参数是按名传递时，对于子程序中的所有情形，实参实际上都以文本形式替代了与它相对应的形参。这与迄今为止讨论过的方法相当不同。在前面的情况下，形参在子程序调用时被绑定于实际的值或者地址。而一个按名传递的形参，是在子程序调用时被绑定于一种存取方法，而这个形参对于值或者对于地址的实际绑定，则被推迟到对形参赋值或者形参被引用以后。

Overloaded Subprograms

重载子程序是与另一个在相同引用环境中的子程序具有相同名称的子程序。每一个重载子程序的版本必须只具有一个协议，也就是说，它必须与子程序的其他版本在参数的数目、参数的顺序或者参数的类型上不相同;如果它是一个函数的话，则是返回的类型不相同。

C++、Java、Ada以及C#都包括了预定义的重载子程序。

在Ada中，是通过一个重载函数返回的类型来区分调用的是哪一个版本。

Separate and Independent Compilation

分别编译意味着编译单元可以在不同的时间被编译，但是如果其中一个访问或使用了另一个的任何实体，那么它们的编译就不是彼此独立的。

在独立编译的情况下、程序单元可以在没有任何其他程序单元信息的情况下进行编译。

Accessing Nonlocal Environments

子程序的非局部变量是那些在子程序中可见但没有局部声明的变量。

全局变量是指在所有程序单元中可见的变量。

第十章

The General Semantics of Calls and Returns

如果局部变量是非静态的，这种调用必须对在被调用子程序中声明的局部变量进行存储空间的分配，还必须将这些变量与所分配的存储空间相绑定。它必须保留调用程序单位的执行状态。执行状态是任何需要重新启动调用程序单元的状态。调用过程必须安排将控制转移到子程序的代码，并且在子程序执行结束后必须确保能够将控制返回到正确的位置。最后，如果这种语言支持嵌套子程序，调用过程还必须产生某种机制，以提供对被调用子程序为可见的、非局部变量的访问。

如果这种子程序具有输出型参数，并且是通过复制来实现的，那么返回过程的第一个动作就是将形参的局部值转移到相关联的实参上。下一步，它必须将局部变量使用的存储空间解除分配，并且恢复调用程序的执行状态。如果这种语言支持嵌套子程序的话，还必须采取一些行动，将非局部引用的机制返回到调用之前的状态。最后，必须将控制返回到调用程序。

Implementing FORTRAN 77 Subprograms

子程序中的非代码部分的格式(或布局)被称为活动记录，因为这一部分仅仅描述子程序的活动期间或执行期间的有关数据。活动记录的形式是静态的。一个活动记录实例是活动记录的一个具体示例，它是活动记录形式的一组数据。

Implementing Subprograms in ALGOL-like Languages

返回地址通常包括了一个指向指令的指针和调用语句之后那条指令的偏移地址，该指令后接着在调用程序单元的代码段中的调用。

静态链接指向活动的底部。静态链接有时也被称为静态作用域指针，它指向静态父辈活动的活动记录实例的低层。

动态连接是一个指向调用程序活动记录实例顶端的指针。

静态链是栈中活动记录实例的静态连接的一个链。

静态深度为一个与静态作用域相关的整数，它表示一个作用域从最外层作用域开始所嵌套的深度。

在对变量x的非局部引用中，达到正确的活动记录实例所需要的静态链长度，正好是包含x引用的过程的静态深度与包含x声明的过程的静态深度之差。这个差被称为引用的嵌套深度或者链偏移。

第十一章

The Concept of Abstraction

抽象是对于实体的一种观念或者实体的一种表示，它仅仅包括这个实体的最重要的属性。

在程序设计语言的世界里，抽象是对抗程序设计复杂性的一种武器，其目的是简化程序设计的过程。因为抽象允许程序人员将注意力集中于基本属性而忽略次要的属性，因而它是一种有效的武器。

当代程序设计语言中的两类基本抽象是过程抽象和数据抽象。

Encapsulation

封装是一组子程序和它们操作的数据。

Introduction to Data Abstraction

从语法的角度而言，抽象数据类型是一个封装，它仅仅包括一种特定数据类型的数据表示，以及一些给这种类型提供操作的子程序。

第十三章

Introduction

存在着两种并发单位的控制。最普通的一种是假设存在着多个处理器可供使用，并且来自相同程序的几个程序单位同时地运行，这就是物理并发。一种稍微放宽的并发概念是允许程序员和应用软件假设:存在着多个处理器提供真实的并发;然而事实上，程序是在单处理器上被分时地执行。这种形式被称为逻辑并发。

Introduction to Subprogram-Level Concurrency

任务可以通过共享非局部变量、消息传递或是参数，来与其他的任务进行通讯。如果一个任务不以任何方式与程序中的其他任务施行通讯，或者是它不影响任何其他任务的执行，我们就称这个任务是不相关的(disjoint)。因为多个任务常常一起工作来产生一些模拟或者是解决一些问题，因而它们是相关的;并且它们必须使用某种通讯的方式来同步彼此的执行或者共享数据，或者是这两种方式皆而有之。

同步(synchronization)是一种控制任务执行顺序的机制。当一些任务共享数据时，需要有两种类型的同步:即合作同步与竞争同步。当任务A在继续它的执行之前，如果它必须等待任务B完成某种特定活动，在任务A与任务B之间就需要合作同步（cooperation synchronization)。当这两个任务都需要不可能同时使用的某种资源时，这两个任务之间需要竞争同步(competition synchronization)。

Semaphores

信号量(semaphore)是一种数据结构;它由一个整数和一个存储任务描述符的队所组成Monitors

将共享数据上的所有同步操作包括进一个程序单位之中。

管程最重要的特性之一，是共享数据居于管程之中而不是居于任何客户单位之中。这样，程序人员就不需要通过使用信号量或者是其他的机制，来同步共享数据的互斥访问。因为所有的访问都发生在管程中，所以能够将管程实现为任何时刻只允许一个访问的结构，从而保证同步访问。

Message Passing

如果任务A需要发送一个消息给任务B，并且任务B愿意接收，消息就能够被传递过来。这种实际的传输被称为会合（rendezvous)。注意，会合只能够发生在发送者和接收者都希望它发生的时候。