2.2、计算机的发展

在上一篇《函数与闭包的前世今生(一)》中,我说过最早的计算机输入输出用的都是纸带。后来随着电磁元件技术的进步,纸带变成了容量更大的磁带,磁带又变成了磁盘。

磁盘不仅比磁带更轻便更易保存,而且读写速度可以比磁带快很多。例如同样存储 1000 个数,读完第 1 个数想读第 1000 个数,读磁带需要磁带移动很久,但读磁盘则只需要磁盘旋转一点加上读写头移动一点就好了。

磁盘又可分为容量较小、较易损坏的软磁盘和容量较大、不易损坏的硬磁盘(硬盘,英文 Hard Drive)。而到了今天我们还有速度更快的固态硬盘(英文 Solid State Drive,缩写 SSD)。

使用磁带的计算机:

磁带计算机
磁带计算机

软磁盘与读取软磁盘的软驱:

image

2.2.1、CPU 与 IO 设备的分离

为了更好的组件分工和更快的处理速度,首先,图灵机模型中的数据处理和内部状态存储部分与读写头部分分离开,数据处理和内部状态存储部分放在中央处理器(英文 Central Processing Unit,缩写 CPU)芯片中,而原本读写头的功能由 IO 芯片和硬盘承担。

image

有了 IO 芯片之后,输入输出设备也不仅限于硬盘了,输入设备还可以是键盘、鼠标、触摸板等等,输出设备还可以是屏幕、打印机等等。

2.2.2、内存

随着集成电路技术的发展,CPU 频率的逐渐地比硬盘快了成千上万倍,于是人们在 IO 芯片和 CPU 之间加了一层速度比硬盘快、但容量比硬盘小、而且只有通电的时候能存储的内存(学术名为随机访问存储器,英文 Random Access Memory,缩写 RAM)。

image

内存只有通电的时候能存储,断电之后存储的数据会马上丢失,这个特点被称为易失性(volatile)。而硬盘、软盘、U 盘等断电后还能存储数据的存储器则可被称为非易失性存储器。

现在的电子计算机(包括服务器、个人电脑以及智能手机)中,CPU 大多数情况下都是从内存中读取代码执行,从内存中读写数据,少部分时间才会从 IO 芯片读写数据。或许因为这个原因,内存才被称为存。而硬盘、软盘等其他存储设备则可以说是存(虽然硬盘现在也安装在电脑机壳里、智能手机里的非易失性存储芯片安装在手机里)。

为了提升 IO 速度,一些 IO 芯片也可以直接读写内存。

有了内存之后,读写数据不再需要移动纸带、磁带或者磁盘的读写头,而只需要一个某个内存存储单元的编号(内存地址)即可。

CPU 执行指令也不再是移动程序代码纸带,而是在每个 CPU 核心内有一个专门记录当前执行的指令的内存地址的寄存器(称为当前指令地址寄存器或者指令指针寄存器),CPU 会拿这个寄存器里的地址去内存中找接下来要执行的指令。

2.3、子程序与函数

计算机科学家和工程师很快就发现,有一些程序功能经常被用到,在很多地方都需要用到,例如计算某个数的正整数次方、排序一个数组(array)、将存储器的某一大块数据从一个地方复制到另一个地方等等。如果每次使用这些功能的时候都将实现这些功能的代码重新写一次,那么就很浪费代码的存储空间。所以计算机科学家和工程师决定将一些会反复用到的功能的代码抽离出来,抽离出来的这些小功能代码就叫做子程序 (subroutine) 或者函数。要用到这些功能的时候,先跳转到子程序的代码里执行,执行完再跳转回原来的地方继续执行。

  • PS:注意,在这里我们定义子程序或者函数为一些代码,而不包括这些代码所处理的数据。因此我在《函数与闭包的前世今生(一)》中倾向于把闭包定义成函数与其能访问的自由变量所组成的词法环境而不是能访问自由变量的函数

但是把一些代码抽离出来作子程序会带来 4 个问题:

  1. 这些子程序可能需要一些输入参数,这些输入参数如何从子程序的调用方传递给子程序?
  2. 子程序怎么知道执行完之后应该返回到什么地方(函数的返回地址)继续执行?
  3. 子程序的执行结果(函数的返回值)怎么传递给调用方?
  4. 子程序里面可能用到一些临时的存储空间(局部变量),这些存储空间应该如何分配?

在此解释一下第 4 条。在没有子程序的情况下,这些功能代码需要用到临时的存储空间时,可以使用全局的存储空间,即程序开始运行时就分配好的空间。但是有子程序而且子程序可能递归调用自己的话,如果用全局存储空间,那么在递归调用自己的时候,第二次调用就可能覆盖掉第一次调用的值。

2.2.1、函数的底层实现

由于函数调用具有先调用的函数后返回、后调用的函数先返回的 First In Last Out 的特点,我们自然而然地可以想到用栈 (stack) 这个数据结构来解决上述 4 个问题中的 1、2、4:

  1. 函数的输入参数由调用方压入栈中,函数中需要用到输入参数时从栈上获取;
  2. 函数调用方在调用函数前将返回地址也压入栈(push)中,函数返回时将返回地址从栈上弹出并写到当前指令地址寄存器中;
  3. 函数中要用到的局部变量在栈上分配空间,函数返回前将局部变量占用的栈空间释放掉。

用一段 JavaScript 代码举个例子。

当前准备执行第 16 行的函数调用:

image

将输入参数和返回地址压入栈中,在栈中开辟局部变量的空间,开始执行函数中的代码:

image

start = 0 小于 end = 1,跳过第 3、4、5 行。第 6 行计算出 mid 为 0。target = 2 大于 arr[mid] = 1,跳过第 7 到第 10 行,进入第 11 行:

image

再次将输入参数和返回地址压入栈中,在栈中开辟局部变量的空间,开始执行函数中的代码:

image

start = 1 不大于 end = 1,跳过第 3、4、5 行。第 6 行计算出 mid 为 1。target = 2 等于 arr[mid] = 2,进入第 8 行:

image

第二次函数调用返回(清理局部变量占用的栈空间,从栈上获取并跳转到返回地址,清理输入参数占用的栈空间):

image

第一次函数调用返回(清理局部变量占用的栈空间,从栈上获取并跳转到返回地址,清理输入参数占用的栈空间):

image