子程序是可被调用以执行特定任务的程序代码单元,通常接收给定的输入,并在执行后将控制权交回调用位置之后的程序位置。子程序是编程语言中的一种基本抽象:它允许一项操作只定义一次,就能在多个位置使用,同时将接口与实现分离。根据语言和使用场景的不同,子程序也可称为函数、过程、方法,或简称为例程。
用途与术语
子程序将一项操作封装在可调用的接口之后。程序不必重复编写执行该操作的指令,而是通过一次调用将控制权转交给子程序。发起调用的代码称为调用方,被调用的子程序称为被调用方。
子程序具有几项相互关联的用途:
- **分解:**将大型程序拆分为较小且易于理解的操作。
- **复用:**让多个调用方共享同一份实现。
- **抽象:**让调用方能够使用某项操作,而不必依赖其内部指令。
- **独立测试与维护:**划定边界,以便检查或修改程序行为。
不同语言使用的术语有所不同。函数通常返回一个值,而过程通常执行某项操作,但不直接返回值。这种区分并不普遍:例如,C编程语言将返回值的例程和返回类型为 void 的例程都称为函数。在面向对象编程中,方法是与类或对象关联的子程序;实例方法通常可以访问特定的接收者对象。
程序中的函数不一定是数学意义上的函数。它可能依赖可变状态、产生输出、修改数据,也可能在多次接收相同显式实参的调用中返回不同结果。相比之下,纯函数只依赖其输入来产生结果,且不会产生可观察的副作用。
定义、调用与返回
子程序的定义通常会指定名称或其他标识方式、形式参数、程序体,以及适用时的结果类型。调用则提供与这些参数相对应的实参。
例如,以下是用伪代码编写的示例:
function maximum(a, b):
if a > b:
return a
return b
largest = maximum(12, 7)
这里,a 和 b 是形式参数,即定义内部使用的名称。值 12 和 7 是调用时提供的实际参数,简称实参。返回值被赋给 largest。
子程序的签名描述名称、参数类型和结果类型等接口信息,不过“签名”的确切含义因语言而异。类型系统可以检查调用是否提供了合适的实参,以及结果的使用是否符合类型要求。
在普通的同步调用中,被调用方执行时,调用方会等待;被调用方返回后,调用方继续执行。返回时可以提供一个值、多个值,也可以不提供值。并非每次调用都会正常返回:执行也可能因引发异常、结束进程、将控制权转移至其他位置而终止,或无限持续下去。
调用子程序不同于控制流中的任意跳转。调用意味着预期会返回到某个特定的后续计算,也就是调用结束后应继续执行的计算,即使某次具体执行永远无法到达那里。
参数、结果与状态
不同语言有不同的实参传递规则。这些规则决定了被调用方会接收到什么,以及调用方能够观察到哪些变化。
- **按值传递:**被调用方接收一个值,用它来初始化形参。给该形参赋予新值,这一操作本身不会重新赋值给调用方的变量。
- **按引用传递:**形参提供对调用方存储位置的访问,因此通过形参赋值可以改变调用方的变量。
- **按共享传递:**调用方和被调用方可以引用同一个对象。修改该对象对双方都可能可见,但重新绑定形参不会重新绑定调用方的变量。
这些描述必须结合具体语言的语义来理解。例如,按值传递指针时,复制的是指针值,而不是它所指向的对象。因此,即使被调用方并未通过引用接收指针变量本身,也仍然可以修改该对象。
当多个参数或其他引用指向同一存储位置时,就会发生混叠。这可能使推理数据更新的影响变得复杂,并限制编译器优化。
子程序还可以访问未作为显式实参传入的信息,包括全局变量、对象字段或外围作用域中的变量。将函数与对其外围词法环境的访问能力封装在一起,就构成了闭包。这类环境的生存期可以超过最初创建它们的那次调用。
除产生返回值之外的可观察影响称为副作用,例如修改共享数据、写入文件或发送网络消息。对副作用的处理在函数式编程中尤为重要,其中通常会区分纯计算和带有副作用的操作。
运行时实现
语言对子程序语义的规定,并不要求采用某一种特定的机器实现。不过,许多实现会使用调用栈,通常将活动记录组织成栈(数据类型);活动记录也称为栈帧。
活动记录可能包含:
- 返回地址;
- 实参或用于传出实参的空间;
- 局部变量和临时值;
- 保存的处理器寄存器值;
- 用于异常处理或访问外围作用域的信息。
每次尚未结束的调用都可以拥有自己的记录。这样既能隔离嵌套调用的局部状态,也允许同一例程同时存在多个尚未结束的调用。
在机器码层面,调用可以使用记录返回地址并将执行转移至被调用方的指令。有些体系结构将返回地址放在寄存器中,另一些则通常将其放在栈上。编译器、解释器或虚拟机会根据各自的执行模型实现具体细节。
调用约定规定了实参和结果的存放位置、被调用方必须保留哪些寄存器,以及由哪一方调整栈存储空间等细节。调用约定是应用二进制接口的一部分,使分别编译的组件能够正确地相互调用。
源代码中存在子程序,并不意味着执行时必须创建实际的栈帧。编译器可以消除调用、将值保留在寄存器中、在其他位置分配环境,或变换控制流,只要保持程序所要求的行为即可。
递归与相关形式
如果子程序直接调用自身,或参与一个循环调用链,它就是递归的。递归适合用来表达对嵌套结构的操作,例如遍历一棵树(数据结构),也适合实现分治法算法。
每次尚未结束的递归调用通常都有各自独立的参数和局部状态。递归过深可能耗尽可用的栈空间。当调用方的最后一个动作是返回被调用方的结果时,就发生了尾调用。支持尾调用消除的实现可以在执行符合条件的调用时,无须额外保留一个活动栈帧。
子程序也有几种更专门的形式:
- **一等函数:**可以被存储、作为实参传递并作为结果返回的可调用值。
- **高阶函数:**接收可调用值或返回可调用值的例程。
- **回调:**提供给另一组件的例程,供其在事件发生或操作到达特定阶段时调用。
- **方法:**与类或对象关联的例程,有时会在运行时根据接收者的类型进行选择。
协程扩展了普通的调用与返回模式,允许执行暂停,随后在保留局部状态的情况下恢复。在异步编程中,调用异步函数可能会在底层操作完成之前,先产生一个任务、future 或 promise。调用、执行、暂停和完成之间的确切关系取决于语言和运行时。
历史发展
子程序随着早期存储程序计算机的发展而出现,用于复用指令序列和组织程序。早期实现必须解决从共享例程返回不同调用位置的问题,有时会采用修改指令或修改返回地址存储内容的技术。
EDSAC 编程环境是早期可复用子程序库的一个重要范例,产生了广泛影响。莫里斯·威尔克斯、戴维·惠勒和斯坦利·吉尔于 1951 年出版的《电子数字计算机程序的编制》,介绍了以这类可复用例程为核心的编程方法。
高级语言将子程序变成了明确的语言构造,而不再仅仅是机器层面的约定。Fortran编程语言区分函数和子程序,后来的语言则为嵌套过程、递归、可调用值以及与对象关联的方法提供了更丰富的支持。这些发展使子程序的表达作用不再局限于共享重复的指令序列。
应用与局限
子程序是软件工程中组织程序的基本单元。库对外提供可调用的操作,而应用程序编程接口通常会规定这些操作的参数、结果、错误和行为要求。只要保持承诺的行为,接口背后的实现就可以改变。
调用可能产生多方面的开销:转移控制权、传递实参、保存寄存器、分配活动记录存储空间,以及返回结果。内联会用根据被调用方程序体生成的代码替换调用,从而可能消除调用开销,并为进一步优化创造条件。但它也可能增大程序体积,增加指令缓存的压力。如何权衡取决于工作负载和实现方式。
子程序边界并不自动保证良好的模块化。严重依赖全局状态的例程可能难以单独理解。过于细小的例程可能使计算过程支离破碎,而过于庞大的例程则可能将互不相关的职责混在一起。
并发执行会带来额外的问题。如果一个例程在先前的调用完成之前可以再次进入,而且不会因此破坏其正常运行,那么它就是可重入的。可重入性并不等同于线程安全性:例程可能使用锁保护共享状态,但在某些情境下重新进入该例程仍然不安全。在并发计算中,无论源代码如何划分为例程,对可变共享状态的非同步访问都可能产生竞态条件。
子程序边界还可以通过前置条件和后置条件等契约支持形式验证。这些条件规定了调用前必须满足什么,以及例程完成时保证什么。要确立这些保证,仍需考虑终止性、异常退出、混叠以及共享状态的变化。