操作系统–前言04--构造复杂的程序

构造复杂的程序

不支持递归的程序语言如何实现递归程序？

弄清楚这道题目，对程序有一个更深层次的认识，不仅仅停留在指令的执行层面，而是要灵活使用指令，去实现更加复杂的功能。

for 循环如何被执行

var i = 1, s = 0; for(; i <= 100; i++) { s+=i; }

for循环是通过标记,判断和跳转完成指令操作

if-else 翻译成指令，是比较简单的，你需要用跳转指令和比较指令处理它的跳转逻辑。自上而下的执行逻辑

switch-case是一种精准的匹配算法.

用1000个case,用 if-else 你需要一个个比较，最坏情况下需要比较 999 次；而如果用 switch-case ，就不需要一个个比较，通过算法就可以直接定位到对应的case

函数的执行过程

函数涉及到栈的数据结构

int add(int a, int b){ return a + b; } 参数a,b本质是内存中的数据,因此需要给他们发你配内存地址函数的返回值也是内存中的数据,也就是返回值也需要分配内存的地址调用函数其实就是跳转到函数体对应的指令

首先在调用方，我们将参数传递给栈；然后在函数执行过程中，我们从栈中取出参数。

函数执行过程中，先将执行结果写入栈中，然后在返回前把之前压入的参数出栈，调用方再从栈中取出执行结果。

将参数传递给 Stack 的过程，叫作压栈。取出结果的过程，叫作出栈。

假设要计算 11 和 15 的和

11 被写入内存，并且栈指针指向了 0x104 位置。

15被写入内存

11 和 15 都被放入了对应的内存位置，并且栈指针指向了 0x108。

将返回值压栈

完成压栈后,开始调用函数,用跳转指令直接跳转到函数的标签,加在栈中11和15,我们可以利用SP指针寻找数据,11距离当前SP指针3个位置,15距离2个位置这种寻址方式是一种复合寻址方式,是间接+偏移量寻址.

下面的代码完成将 11 和 15 导入寄存器的过程：

load $(SP - 12) -> R0 load $(SP - 8) -> R1

然后进行加和，将结果存入 R2。

load R0 R1 R2

再次利用数学关系将结果写入返回值所在的位置。

store R2 -> $(SP-4)

一种间接寻址的方式来进行加和运算，也就是利用 SP 中的地址做加减法操作内存。

经过函数调用的结果如下图所示，运算结果 26 已经被写入了返回值的位置：

64 位宽的 CPU，那么栈指针就需要自增 8。32位宽的 CPU，那么栈指针就需要自增 4。

在调用函数前，还需要将返回地址压栈。这样在函数计算完成前，就能跳转回对应的返回地址。翻译成指令，就是下面这样：

## 压栈返回值 add SP, 4 -> SP # 计算返回地址 # 我们需要跳转到清理堆栈那行，也就是16行 MOV PC+4*(参数个数*2+1) -> SP # 压栈参数的程序 …… # 执行函数，计算返回值 call function # 清理堆栈 add SP, -(参数个数+1)*4， SP

递归函数如何被执行

int sum(int n){ if(n == 1) {return 1;} return n + sum(n-1); }

每次递归的时候,都是形成一个栈的结构

sum(100)，就会形成一个复杂的栈，

堆在一块就会形成一个很大的栈

递归消耗了更多的空间,但是也保证了中间数据的独立性.

由此可见,栈这种结构同样适合递归的计算,计算机编程语言就是用这种结构来实现递归函数的.

类型（class）如何实现

变量是一个内存地址，所以只需要分配内存就好了；循环控制可以用跳转加判断实现；条件控制也可以用跳转加判断实现，只不过如果是 switch-case 还需要一定的数学计算；函数调用需要压栈参数、返回值和返回地址。

一个 class 会分成两个部分，一部分是数据（也称作属性），另一部分是函数（也称作方法）。

class 有一个特殊的方法叫作构造函数，它会为 class 分配内存。构造函数执行的时候，开始扫描类型定义中所有的属性和方法。

属性分配地址遇到方法的值,设置为方法指令所在的内存地址。

this关键字则是最先压入栈，这样任何函数都可以访问实例中的属性和函数

**个语言的能力和图灵机等价，**就说这个语言是图灵完备的语言。现在市面上的绝大多数语言都是图灵完备的语言，( HTML、正则表达式和 SQL 等不是完备语言)