PL真有意思（六）：子程序和控制抽象

前言

在之前我们把抽象定义为一种过程，程序员可以通过它将一个名字与一段可能很复杂的程序片段关联起来。抽象最大的意义就在于，我们可以从功能和用途的角度来考虑它，而不是实现。

在大多数程序设计语言中，子程序是最主要的控制抽象的方法。大多数子程序都是参数化的，即通过传递一些参数来影响子程序的行为。

回顾栈的布局

当一个子程序被调用的时候，在栈的顶部将给它一个新的栈帧或称为活动记录。这个栈帧可能包含实际参数和/或返回值、簿记信息（包含返回地址和保存的寄存器）、局部变量和/或各种临时量。当子程序返回时，栈帧从栈中弹出。

如果某个对象的大小在编译时位置，那么就将它放在栈帧的顶部大小可变的区域，并将它的地址和内情向量保存在栈帧的某个部分，放在相对于栈指针的一个静态可知的偏移处。

在那些允许嵌套子程序和静态作用域的语言，对象有可能出现在外围的子程序中，通过维护一个静态链就可以找到这些既非局部也非全局的对象。每个栈帧都包含一个对词法上位于其外围的帧的引用

调用序列

维护子程序调用栈是调用序列的责任。所谓调用序列就是由调用方紧接着子程序子程序调用和之后执行的代码。

在进入自称的过程中需要完成很多工作，包括出艾迪参数，保存返回地址，修改程序计数器，修改栈指针以分配空间，保存那些维护着重要的值但是可能被子程序改写的寄存器等等等

寄存器的保存和恢复

许多处理器调用序列都是将并非为特殊用途而保留的寄存器分为数目差不多的两组，其中一组由调用方负责，另一组由被调用方负责。

静态链的维护

在有嵌套子程序的语言中，至少有一部分静态链维护工作必须由调用方完成，而不能由被调用方完成

• 被调用直接嵌套在调用方内，在这种情况下，被调用方的静态链应该直接引用调用方的栈帧

• 被调用方在k>=0作用域之外，更接近词法嵌套的外层，在这种情况下，所有围绕着被调用方的作用也围绕着调用方。这时候调用方就对静态链做k次间接引用，将结果送给被调用方做静态链

典型的调用序列

一般的调用序列调用方可以按如下的方式操作：

• 保护起那些由调用方保存、其值在调用之后还需要的寄存器
• 计算出参数的值，并将它们移入栈或者寄存器中
• 计算出静态链，将它作为一个隐含的参数传递
• 执行一条特殊的子程序调用指令跳进子程序，同时将返回地址放入栈或某个寄存器中

被调用方的前序操作则是：

• 分配一个帧，也就是将sp指针减去某个适当的常数
• 将原来的栈指针保存在栈中，并给帧指针赋以适当的新值
• 保存那些由被调用方负责，而且在当前子程序中可能被复写的寄存器

在子程序完成之后的后序操作：

• 如果有返回值，则将返回值移入某个寄存器或栈中的某个保留位置
• 根据需要恢复被调用方保存的寄存器
• 恢复fp和sp
• 跳回到返回地址

最后调用方则可以：

• 将返回值移入需要它的位置
• 根据需要恢复调用方保存的寄存器

内联展开

作为基于栈的调用方式的一种替代，许多语言实现中还允许将特定子程序在调用的位置内联展开。被调用子程序的副本成为调用方的一部分；没有任何实际子程序调用发生。

在C中可以由程序员来指示是否建议将某些子程序内联化

inline int max(int a, int b) { return a > b ? a : b;}

但是与真正的子程序调用相比，内联展开的一个明显缺点就是增加了代码量

参数传递

大多数子程序都是参数化的，它们将得到一些参数，这些参数或控制着子程序行为的某些特定方面，或指定子程序需要来操作的数据。

参数模式

之前提了一下实参传递，以及明确实参与形参关系的语义规则。有些语言定义了唯一一组规则，适用于所有参数，这样的语言包括了C 、Fortran和Lisp，其它一些语言则提供了两组或更多组不同的规则

对于f(x)我们有两种实现方式，

• 可以为f提供一个x的副本
• 直接将x的地址传递给f

这两种最基本的参数传递模式分别称为值调用和引用调用，它们的设计反映了它们的实现方式

值调用和引用调用在使用值模型的语言的语言中最有意义。在使用引用模型的语言中，变量本身已经是对象的引用，这两种模型实际上都没有意义。

在Java中，内部类型使用值调用，而用户定义类型使用引用模型。相对的是C#中使用的是值调用，但是可以通过显式的关键字来使用引用传递。

闭包作为参数

闭包（对一个子程序的引用，再加上该子程序的引用环境）也会因为某些原因需要作为参数传递。最明显的原因就是当参数被声明为子程序时。

在子函数式语言中，子程序往往是作为参数传递的，并作为结果返回

在面向对象语言中，虽然没有嵌套子程序，但是也可以模仿子程序闭包的行为，方法是将与一个方法和它的环境打包在一个显示的对象里，

C#的代理扩展了对象闭包的概念，代理不仅可以用特殊的对象方法来实例化，也可以用静态函数或者匿名嵌套代理或lambda表达式来实例化。

特殊目的的参数

相似数组

在不同语言中，数组维数和边界的约束时间也不大相同，可推迟到运行时再确定形状的形式数组参数称为相似数组参数或开放数组参数，例如C中的多维数组。

默认参数

默认参数就是调用方可以不提供的参数，如果没有给出就使用预先设置的默认值

实现方式也是直截了当的，调用时如果缺少了某个实际参数，编译器就认为提供的是相应的默认值

命名参数（关键字参数）

在至今为止的讨论中，我们一直假定参数按位置相互对应：第一个实参对应于第一个形参，以此类推。实际上，在一些语言中，如Lisp和Python，这些语言都允许对参数进行命名，命名参数与默认参数结合时特别有用。

命名参数不仅可以使参数以任意顺序描述，还可以起到说明参数用途的作用

可变个数的参数表

在Lisp、Python和C及其后羿的一个不寻常之处，是它允许用户定义一类子程序，这种子程序的参数个数可以变化

在C中，printf可以按如下方式声明：

int printf(char *format, ...)

C中通过内置的函数来获取省略参数

在Java中则是将省略参数包装成一个数组

static void print_lines(String foo, String...lines)

函数返回

对于函数指定返回值的语法，各语言之间区别很大，在Lisp和ML这种不区分表达式和语句的语言中，函数的值就是函数体的值，而函数体本身就是一个表达式

而现在的许多命令式语言都引入了显示的return语句

return expr

泛型子程序和模块

子程序为在许多不同的对象值（参数）上执行某个操作提供了一种很自然的方式。在大型程序中，也常常需要在许多不同的对象类型上做某个操作。

在之前有一篇讲到隐式参数多态性绕过了这个问题，它使我们可以声明一种子程序，其参数类型式没有完全描述的，但仍然是类型安全。但是这种方式，需要将所有的类型检查推迟到类型检查时才来做。

还有一种显式多态性的泛型机制，使一组类似的子程序或模块可以通过唯一一段源代码创建出来。

不同实现方法

泛型特征可以通过多种方式实现。在C++的大多数实现中，它们是一种纯粹的静态机制，创建和使用泛型代码多个实例的所有工作都在编译时完成。在通常情况下，编译器为每个实例创建一个独立代码副本。但是在C++中，为这样每个实例安排独立的类型检查

而在Java中使用一种类型擦除的机制，从效果上看，如果T是Java中的一个泛型类型参数，那么类T的对象将被当作标准基类Object的实例对待，但程序员不需要在将它们用作T类的对象之前插入显式的类型强制，而且编译器可以保证这样的省略的强制不会发生失败。

泛型参数的约束条件

因为泛型也是一种抽象，其接声明的头部应该为抽象的用户提供使用它需要知道的全部信息

在Java和C#中，利用了面向对象和继承的能力来实现。它可以要求某个泛型参数必须支持一组特定的方法

例如在Java中：

public static <T extends Comparable<T>> void sort(T A[]) {

}

异常处理

异常可以定义为程序执行过程中出现了没有预料的情况，或者至少是不寻常的情况，而这种情况很难在局部上下文中处理。异常情况可能是由语言实现自动检查的，或者是由程序本身显式引发的。

异常的定义

在许多语言中，动态语义错误会自动产生程序可捕获的异常。程序员还可以定义其它特定于具体应用的异常

在大多数面向对象语言中，异常是某个与风衣或用户定义的类类型的一个实例。

通常使用嵌入在If语句中的throw语句或raise语句来在运行时引发异常。如果一个子程序引发了异常，但是其内部没有捕获，那么它就可能以某种非预期的方式返回。在Java和C++中，在子程序头部包含了一个表，在其中列出可能传播到子程序之外的异常。

异常的传播

在大多数语言中，一个代码块可以由一组异常处理程序，在C++中：

try {

} catch(end_if_file) {

} catch(io_error_r) {

}

在出现异常时，处理程序将出现的顺序检查，控制传入第一个与异常匹配的处理程序。

表达式上的处理程序

在像Lisp一类的面向表达式语言中，异常处理程序被附着于表达式上，而不是语句上。在发生异常时，由于处理程序的执行将代替被保护代码中尚未结束的那一部分，因此附在表达式上的处理程序还必须为表达式提供一个值

val foo = (f(a) * b) handle Overflow => max_int

异常的实现

异常的最明显实现方式是维护一个处理程序的链接表栈。当控制进入一个受保护块时，将作用于这个块的处理程序被加到表的头部。当某个异常被引发时，语言运行时系统就弹出表中最内层的处理程序并且调用它。

在一种内部并没有提供异常的语言中，有时也可以模拟异常机制。

Scheme提供了一个名为call-with-current-continuation的通用函数。这个函数带有一个参数f，该参数本身也是函数。它调用f并将一个继续c（闭包）传给它作为参数。这个闭包包含当前的程序计数器和引用环境。在未来的任何时刻，f可以通过调用c来重新建立起所保存的环境。如果以前做过嵌套调用，控制机制就会弹出它们，就像异常所做的那样。

C的大多数版本提供了一对库例程setjmp和longjmp。setjmp以一个缓冲区作为参数，它将程序当前状态以某种形式存入其中。随后我们可以将这个缓冲区传给longjmp，要求恢复所保存的状态。

协程

有了对运行时栈的布局的理解后，我们可以考虑更一般的控制抽象的实现问题，协程。与继续一样，协程也需要用闭包表示，可以通过非局部的goto跳进来，关于协程的这种特定操作被称为transfer。这两种抽象之间的主要不同点在于：继续是一个常量，一旦创建之后就不会改变了，而协程在每次运行中都会变化。

从效果上看，一组协程在一些同时存在的上下文中执行，但在每个时刻只有一个正在执行，控制将通过命名方式在它们之间转移。协程可以用于实现迭代器和线程

栈分配

由于不同协程是并发的，因此它们不能共享同一个栈，因为作为一个整体看，它们的子程序调用和返回并不是按后进先出的顺序进行的。如果每个协程都放在词法嵌套的最外层声明处，那么它们的栈就是互不相交的

最简单的解决方案是给每个协程一块固定大小的静态分配的栈空间

转移

在从一个协程转移到另一个协程时，运行系统必须修改程序计数器、栈和处理器寄存器的内容。这些修改都被封装在transfer操作中。

对于栈的修改，最常见的方式就是简单的修改栈指针寄存器，避免在transfer中使用帧指针。在transfer开始，我们将返回地址和所有其它被调用所保存的寄存器压入当前栈，然后修改sp，由新栈中弹出新的指令地址和其它寄存器内容，然后返回

事件

事件就是在程序外部发生，出现的时间不可预测，但是需要运行中的程序相应某种情况。最常见的事件就是图形用户界面系统的输入：按键、鼠标活动。

顺序处理程序

传统上，顺序程序设计语言中事件处理程序是作为自发的子程序调用实现的，一般会使用语言之外由操作系统定义和实现的机制。为了准备好通过这种机制接受事件，一个程序将调用一个setup_handler库例程，在事件发生时将希望调用的子程序作为参数传递

在硬件层上，在P的执行期间异步设备的活动将触发一个中断机制，保持在P的寄存器，切换到一个不同的栈，并跳转到OS内核中的一个预先定义的地址上。类似的，如果另一个过程Q在中断发生时正在运行，则内核将在自己最后的时间段结束时，保存P的状态。

当一个中断发生时，主程序可能处于代码的任何位置，内核将保存状态，并通过正常的调用序列调用事件处理程序，最后恢复状态。

总结

这一篇集中关注控制抽象的问题，特别是子程序有关的问题。首先我们先了解了子程序调用栈的管理问题和维护栈的调用序列。在之后讨论了有关参数的问题，各种参数传递模型等。最后考察了异常处理机制、协程和事件。