笔记：函数和栈

从入门编程开始，我们一直在和函数打交道，但直到今天，我才勉强敢谈一谈对函数的认识。

在以C为代表的，绝大多数“正常”的编程语言中，函数都 是组织代码和组成程序的基本单位，甚至在CPU中也内建了对函数(过程)调用的支持。其他所谓面向对象风格 不过是对函数的进一步封装而已。

程序执行时的控制流，也是以函数为基本单位来进行调度的，每一次函数调用，就标志着一次控制流的转移。在经典的模型中，一个函数可以调用包括自己(调用自身的行为被称为递归)在内的任何函数，被调用的函数也可以再调用其他函数。函数间通过参数和返回值来传递信息，前者用于调用者向被调用信息发送信息，后者用于被调用函数向调用者返回信息。

那么我们如何在脑中构建一幅函数间互相调用的景象呢？这里我就不得不提到栈这个概念。栈是最简单最基础的数据结构之一，栈是一种线性的容器，但其特殊之处在于只能从其中一端插入或取出数据，这一端被称为栈顶。这使得栈具有这样的特征：先被插入栈的数据，要最后被取出；后加入栈的数据，将先被取出，即LIFO(Last In First Out, 后进先出).

函数调用存在着类似的性质：在某一时刻的同一调用树(而不是多个并行执行的函数)上，最先被调用的函数将最后被返回，因为它需要等待所有之后被调用的函数返回才行。 于是在计算机中，我们通过栈来维护函数间的调用状态，这种栈，也被称为运行栈，线程栈，函数栈。

栈上为单个函数所分配的区域，被称为栈帧。栈顶由一个栈顶指针来指示，栈顶指针在函数执行时会随时改变，因此还有另外一个帧指针指向当前栈帧的起始处，函数通常通过帧指针来访问数据。栈指针和帧指针被保存在单独的寄存器上。

函数执行时所定义的局部变量都将被分配在栈上，这些局部变量(和函数参数)决定了函数的执行状态。

当函数调用另一个函数时，首先要保存寄存器的值。因为寄存器是被多个函数所共享的自由，为了防止被调函数覆盖寄存器，主调函数必须负责将部分寄存器的值保存在栈上。然后将要传递给被调函数的参数插入栈中，在参数较少的情况下，也可能直接使用寄存器来传递参数。然后再插入下一条指令的地址，即被调函数返回时要返回到的地址。最后将控制权移交到被调函数的首地址。

被调函数开始执行，这也标志着调用者的栈帧已经结束。被调函数首先在栈上保存当前旧的帧指针，然后将帧指针甚至为栈指针减去1，即当前栈帧的第一项是旧的帧指针。 然后被调函数也开始保存寄存器，调用者和被调函数分别负责保存哪些寄存器是有约定的。

然后被调函数开始执行真正的代码，并通过帧指针来访问参数，参数在栈中的顺序是由调用约定决定的。在函数执行的过程中，函数也可能在栈上创建和销毁局部变量，但均遵循栈的后入先出原则。在函数执行即将结束时，将返回值保存在特定的寄存器中。

当被调函数返回时，首先恢复已保存的寄存器的值，然后将帧指针赋值给栈指针，即丢弃当前栈帧除了已保存的旧的帧指针的全部数据。然后从栈恢复旧的帧指针，至此被调函数已经完成了全部清理工作，帧指针指向调用者的栈帧头部，栈指针指向调用者栈帧的尾部。被调函数将控制权移交给当前栈指针指向的返回地址。

现在控制权回到了调用者，调用者首先弹出栈中的返回地址和参数，然后恢复寄存器的值，接着执行剩下的代码，被调函数的返回值在特定的寄存器中。

本文从栈的角度描述了一个函数的执行过程，着重介绍了4个关键的时间点：调用者调用被调函数、被调函数开始执行、被调函数返回前的清理工作、控制权返回到调用者。

可以看到函数的执行和栈的使用本来就是密不可分的。