第3章
程序是如何执行的





本章讲授程序是如何在计算机里执行的，极为重要。一个计算系统至少包含了CPU和主存(Main Memory，或称为内存)。CPU是做运算的，主存是储存程序和变量(Variables)的。本章首先详细解释一行行的程序被CPU读后，如何控制CPU的运算和指示CPU去读写在主存中的变量； 然后解释函数调用是如何执行的，其中涉及一些重要概念，那就是返回地址、局部变量、全局变量和栈的管理； 接着介绍几种最常用的程序语言C、C++、Java和它们特性的比较； 最后在讲述对计算机程序的领悟时，我们用非常有趣的“猜数字”例子讲述什么是人工智能(其实智能是程序计算出来的)。本章的这些知识对程序编写、编译器、操作系统、信息安全中蠕虫病毒的理解至关重要。
本书作者提供一个精心研发的汇编语言模拟器供教学使用，叫作SEAL。学生可利用此工具来设计和执行汇编语言程序，与本章内容密切配合，更充分地理解本章内容。此工具可以从前言中列出的清华大学出版社官方网站下载。
3.1引例
程序员编写的程序（如Python、C、C++等）并不是计算机硬件可以直接识别的形式，计算机只能识别二进制的机器语言。


图31计算机执行a=a+1语句


本节就来探索一条程序语句在计算机中的执行过程。

程序的执行会牵扯到CPU和主存。如图31所示，计算机中有两个核心部件，分别是CPU和主存。CPU是做运算的，主存存储程序和相关的变量，每一条程序语句和每一个变量在内存中都有相应的内存地址。

现在以下面一个简单的程序为例。在这个程序中只有一条语句a=a+1。大家看到这种带有“=”等号的语句时，要将“=”号左边和右边分开来分析。a=a+1这句的意思是： 将等号右边的a+1计算出，然后将值赋给等号左边的变量a。等号右边的a是指变量a所存的值，而等号左边的a是指变量的位置。
接下来分析它是如何执行的。
第一，CPU先要读程序，从地址300处读取指令到CPU中，经过CPU的分析，CPU知道接下来将要做的动作(也就是接下来的第二步)； 第二，CPU会从地址1000处读变量a的值； 第三，CPU把这个值加1； 第四，CPU将加1后的结果存回到地址1000处的a。

3.2a=a+1的执行过程
其实，a=a+1不是只有一个指令，它包含了数个基本指令。在本节，通过循序渐进的讲解，大家就会更清楚a=a+1的执行过程。
3.2.1分解a=a+1的执行步骤
a=a+1的执行可以分为三步。首先是CPU从主存中读取a，接着CPU对a执行加1操作，最后CPU将运算后的结果存回主存。
如图32所示，主存中就会存储三条指令，依次是“读取a到R”“R加1”“将R存回a”。CPU中有通用寄存器(Register)R来存储变量a。


图32分解a=a+1执行步骤



CPU读取变量a后，先存到寄存器R中。寄存器是CPU内的存储单元，是有限存储容量的高速存储部件。每一种类的CPU的寄存器的个数和使用会有少许的不同，但是每一个CPU都会有通用寄存器来给程序使用，编号R1~R32代表有32个通用寄存器。我们在运算a=a+1时，首先要把变量a读取到某一个寄存器R，然后CPU再对寄存器R中的值进行运算。运算完成之后，CPU才会将值存回主存。现在很多CPU不能直接对内存做运算，必须要先读到寄存器里，然后在寄存器上做运算，运算完后，再把结果存回内存里。
第一步，CPU从地址300处读取第一条语句，CPU执行“读取a到R”语句，就会从地址1000处读取变量a的值到寄存器R中； 
第二步，CPU从地址301处读取第二条语句，执行“R加1”语句，CPU会对R执行加1的操作； 
第三步，CPU再从地址302处读取第三条语句，执行“将R存回a”语句，就把寄存器R中变量a的值存回主存中地址1000处。
3.2.2CPU中的核心部件
执行a=a+1时，讲到CPU需要从主存中相应地址处读取语句。这一节会解释以下问题： CPU如何知道语句的地址？从主存中读取的语句存放在哪里？CPU是怎样完成加法运算的？


图33CPU的核心部件



如图33所示，CPU中有寄存器R、PC、IR、ALU这些部件。现在我们来细看CPU中的这几个核心部件。
语句地址的存储——程序计数器(Program Counter，PC)
程序计数器PC是一个“特殊”寄存器部件。在计算机执行程序时，PC始终指向主存中的某条指令语句(即该条语句在主存的地址)。CPU就是读取PC所指向的那条指令来执行。
在顺序执行程序语句时，PC通过顺序加1(对32位CPU，一个指令要占用4字节，所以其实是加4； 对64位CPU，是加8)自动指向下一条将要执行的程序语句。对于一些控制结构语句，如if、for、while等控制结构，程序的执行将会分叉，这时PC的值就不只是顺序加1来指向下一条程序语句。在3.3节会讲到更多细节。
CPU中存储程序语句——指令寄存器(Instruction Register，IR)
指令寄存器IR也是个特殊寄存器，它被用来存放从主存中读取的程序指令。CPU从主存中读取程序指令到IR之后，由特定的部件来解读这条程序指令，并执行相应的操作。
执行运算——算术逻辑单元(Arithmetic Logic Unit，ALU)
ALU是处理器中进行真实运算的部件。执行程序指令时，CPU把寄存器中的值输入ALU中，ALU做完运算后把结果存回寄存器。
介绍了CPU中的核心部件后，我们就知道了CPU的主要作用。
3.2.3汇编指令的概念
为了便于理解程序执行的精髓，本章设计了几条CPU常用的“汇编指令”，来表达CPU的操作。实际的CPU中有各自的汇编指令集，功能强大而复杂。
在a=a+1之前再加入另一条程序语句a=10，也就是先给变量a赋值，然后让a加1。即

a=10

a=a+1

现在计算机顺序执行“a=10，a=a+1”语句，CPU需要做以下几个操作，即“R赋值”“将R存回a”“读取a到R”“R加1”和“将R存回a”。分别用下面几条指令来表示每个操作。

1.    “读取a到R”操作——load指令
程序语句中的“读取a到R”，表示CPU将变量a读取到寄存器R中。设计指令load表示“读取a到R”操作，那么load指令中需要有两个“操作数”，一个操作数是变量a的地址，另一个操作数是存储的寄存器。
格式： load R1, (address)  


小明： “操作数”是什么意思？
阿珍： 汇编指令由“操作码”和“操作数”组成。操作码是指令执行的基本动作。在
load R1, (address)指令中，load是操作码，其后的寄存器R1和(address)都是操作数。操作码的英文叫作operator, 操作数的英文叫作operand。


注： address是内存地址，(address)表示这个地址内存储的值。
【例31】load  R1, (1000)
该指令表示，将主存地址1000处的变量值读取到寄存器R1中。如图34中箭头所示是load指令执行的操作。（address）也可以用一个寄存器值加上一个偏移量（十六进制的常数）来表示，例如load R1, 04h(R2)。假设R2的值是996，那就是将主存地址996+4=1000处的值读取到寄存器R1中。


图34load指令


2.  “R赋值”操作——mov指令
程序语句中的“R赋值”，表示给寄存器R赋一个值。设计指令mov来完成“R赋值”操作，那么mov指令中需要有两个操作数，一个操作数是赋给的值； 另一个操作数是寄存器。
格式1： mov R1, constant  
注： mov指令有两个操作数，前一个是寄存器，后一个是十六进制的常数。
【例32】mov R1, 0Ah
该指令执行的操作，是将一个常数值0Ah(十进制的10)赋给寄存器R1。
我们希望，mov指令还可以把一个寄存器中的值赋给另一个寄存器，那么mov指令的两个操作数都是寄存器。
格式2： mov R2, R1 
注： mov指令有两个寄存器操作数。
该指令执行的操作，是将后一个寄存器R1中的值赋给寄存器R2中。

3.   “R加1”操作——add指令
程序语句中的“R加1”，表示将寄存器R的值加1。设计指令add来完成“R加1”操作，那么add指令中需要有三个操作数，一个操作数是与变量R相加的值，一个操作数是存储变量R的寄存器，还有一个操作数是存储运算结果的寄存器。
格式1： add  R2, R1, constant
注： add指令有三个操作数，一个是常数，还有两个是寄存器，这两个寄存器中后一个是进行运算的寄存器，前一个是存储运算结果的寄存器。该指令表示R2=R1+constant。
【例33】add R1,R1,01h
该指令表示将寄存器R1中的数值加1，并将结果存回寄存器R1。如果寄存器R1中的值最初是06h，执行该指令后，寄存器R1中的值就为07h。
我们希望，add指令还可以把两个寄存器中的值相加，赋给另一个寄存器中的变量，那么add指令的三个操作数都是寄存器。
格式2: add  R1, R1, R2
注： add指令有三个寄存器操作数。
该指令执行的操作，是将后两个寄存器R1、R2中的值相加，结果赋给寄存器R1，也就是R1=R1+R2。

4.  减法指令sub
同add指令的格式一样。“sub  R2, R1，constant”代表了R2 = R1 - constant,“sub  R3, R1, R2”代表了R3=R1-R2。
5.   左移位指令shiftl
“shiftl  R3,R1，05h”代表寄存器R1的二进制数左移5位，移出的那5位填0，再将最终值存入R3。05h也可以用一个寄存器表示，例如，“shiftl  R3, R1, R2”代表R1的二进制值向左移(R2)位数，存入R3。左移指令就相当于将R1做乘法。R1左移一位，R1值就相当于乘2，R1左移2位，R1值就相当于乘4。
6.  右移位指令shiftr
向右移位，移完后的那些最高位填0。
7.   “将R存回a”操作——store指令
程序语句中的“存回”，表示CPU将寄存器R中的值存回主存中。设计指令store表示“存回R”操作，那么store指令中需要有两个操作数，一个操作数是寄存器R； 另一个操作数是要存回的地址a。
格式: store  (address), R1
注： address是内存地址，(address)表示要存回的地址，R1是寄存器。也就是(address)=R1。
【例34】store  (500), R1
该指令表示将寄存器R1中的值存回主存地址500处。（address）也可以用一个寄存器值加上一个偏移量（十六进制的常数）来表示，例如store 04h(R2), R1。假设R2的值是496，那就是将R1的值存回主存地址496+4=500处。


小明： 程序执行时，为什么CPU先把变量读取到寄存器中，再转移到ALU中进行运算，而不是直接把变量读取到ALU中进行运算呢？
沙老师： 因为CPU和主存之间的数据读写速度远远比CPU与寄存器之间的速度慢。CPU寄存器的读写只要1个单位时间，而对主存的读写可能要高达50个单位时间。如果每次ALU运算的输入都要从主存读取，那就要花很长的时间了。用寄存器保存了程序执行时的中间运算结果，执行多次快速ALU运算后，再将结果存回内存中，这样会比每次运算都从内存来输入输出要快得多。


3.2.4a=a+1的完整执行过程
为了让计算机执行“a=10, a=a+1”程序语句，用几条汇编指令来指示CPU的操作。先把“a=10, a=a+1”这两条程序语句用相应的汇编指令来表示，汇编指令的执行步骤如下。 
(1) 程序开始执行时，变量a存储在主存地址1000处。a=10, a=a+1程序语句有五条汇编指令，从地址301处开始顺序存储每条指令。程序开始执行时，PC指向汇编程序的首地址301处。
(2) 如图35所示，CPU从地址301处开始执行，PC值为301，CPU从地址301处读取mov指令到IR，解读并执行mov指令，给寄存器R1中的变量a赋初值10，然后PC加1，指向下一条汇编指令。


图35mov指令的执行

(注： 图中的CPU和主存是实际的计算机部件的简单示意图。计算机的CPU中通常有32个寄存器，为简单起见，此处只画出R1、R2这两个寄存器)


(3) 如图36所示，PC值为302，CPU从地址302处读取store指令到IR，解读并执行store指令，将寄存器R1中变量a的值存回主存地址1000处，然后PC加1，指向下一条汇编指令。


图36store指令的执行


(4) 执行load指令，如图34所示，之后PC指向add指令。如图37所示，PC值为304，CPU从地址304处读取add指令到IR，解读并执行add指令，将寄存器R1中变量a的值加1，并将结果再存回寄存器R1，然后PC加1，指向下一条汇编指令。


小明： 好像第三个语句的store和第四个语句的load是可以去掉的，是吗？
沙老师： 没错。从高阶语言转换为低阶的汇编语言，这个过程是由一个程序叫作编译器来完成的。编译器会做进一步的优化，将这两个语句去掉。




图37执行add指令

(5) 执行store指令，同图36，该指令把寄存器R1中变量a加1后的值存回主存地址1000处。
小结
本节探索了“a=10, a=a+1”这种简单赋值语句在计算机中是如何执行的。首先，我们描述出计算机执行这些程序时，CPU需要做哪些操作。但计算机并不理解我们的描述，所以CPU设计者就设计了相应的“汇编指令”来指示CPU的操作。简单起见，我们并没有使用真实的某一种计算机体系下的汇编指令集，而是设计了可以表达相似功能的指令来为大家讲述基本概念。通过使用汇编指令，告诉CPU要进行的工作，从而正确地执行程序。
练习题3.2.1： CPU执行程序语句a=20时，基本的操作是什么？
练习题3.2.2： 指令“load  R2, (1200)”执行的操作是什么？
练习题3.2.3： 用shiftl指令将R1值乘以10h(十进制的16)，存入R3。
练习题3.2.4： 用shiftl和add指令将R1值乘以0ch(十进制的12)，存入R3。add指令用的越少越好。
练习题3.2.5： 假设变量x在主存地址600处，变量y在主存地址604处。请写出“x=x-y”的汇编程序。
练习题3.2.6： 对于向右移指令shiftr，我们是将移完后的那些位元填0，但是普通CPU还有一个向右移的指令，它是填上原来的最高位值，也就是原来的最高位是1，右移后所有的新位元就填1，原来的最高位是0，右移后就填0。这个指令叫“算数右移”，请问这个指令的作用是什么？
提示： 可能和负数的表示有关。
练习题3.2.7： 假设变量x存储在主存地址600处，执行完下列汇编指令后，地址600处存储的数据是多少？

loadR1, (600)

movR1, 09h

store(600), R1

3.3控制结构的执行
要解决一个问题，一定会用到控制语句，会用到一些分支判断的程序语句，如ifelse语句、for循环、while循环等。那么这些语句的执行逻辑是怎样的呢？本节我们来探索控制结构的执行过程，首先学习ifelse选择语句在计算机中是怎样执行的。
3.3.1ifelse选择语句
不同的程序语言定义了不同的ifelse选择、for循环等控制结构的表达形式。但是ifelse、for语句的执行逻辑是不变的。
如图38所示是ifelse选择语句的简化形式。


图38ifelse选择语句的

简化表达

ifelse的执行逻辑是： 先判断if后面的表达式，如果表达式成立，则执行语句块A，否则就执行语句块B。在图38中，如果x小于y，则执行语句块A，否则执行语句块B。ifelse选择语句，只选择其中一个语句块来执行，之后执行ifelse结构后面的语句块。
那么，我们怎么把ifelse的执行逻辑告诉计算机呢？
首先，我们需要比较x和y的大小，由一条语句“比较x是否小于y”来告诉CPU应该进行判断操作。
接下来，CPU应该保存这个比较结果，根据比较结果，产生以下两种执行的情况。其一，选择顺序执行语句块A，执行完A的所有语句后直接跳转到语句块C； 其二，不执行语句块A，而是选择跳转到语句块B，执行完B的所有语句后，顺序执行语句块C。


小明： “直接跳转到语句块C”和“选择跳转到语句块B”，这两个“跳转”操作有什么区别？
阿珍： “直接跳转到语句块C”表示必须跳转到语句块C； “选择跳转到语句块B”表示CPU先做判断工作，根据这个判断的结果，来选择是否要跳转到语句块B。


3.3.2分支跳转指令
我们用自己的语言描述了CPU在执行ifelse选择语句时的操作。现在需要新增几条汇编指令，来指示CPU执行的操作。本节将介绍“比较x是否小于y”“选择跳转到语句块B”操作如何用相应的汇编指令来表示。
1.   “比较x是否小于y”——slt指令
我们设计指令slt来告诉CPU进行比较操作，slt需要三个操作数，后两个操作数依次是存储变量x和变量y的寄存器，另一个寄存器用来保存比较结果。
格式1： slt  R4, R1, R2
该指令执行的操作，即比较寄存器R1中的数值是否小于R2中的数值，如果小于，则将寄存器R4置1，否则置0。
我们还希望slt能够比较寄存器中的变量和一个数值的大小。那么slt的后两个操作数分别是保存变量的寄存器、常数值，而另一个寄存器用来保存比较结果。
格式2： slt  R4, R1, constant
该指令执行的操作，即比较寄存器R1和常数值constant，如果R1中的数值小于constant，则寄存器R4置1，否则置0。

【例35】slt  R4, R1, 0Ah
该指令表示，比较R1寄存器中的数值是否小于0Ah(即十进制的10)，如果小于，则R4寄存器置1，否则置0。
2.   “判断小于或等于”——sle指令
sle和slt的格式完全一样。例如“sle R4, R1， constant”，即比较寄存器R1和常数值constant，如果R1中的数值小于或等于constant，则寄存器R4置1，否则置0。
3.  “选择跳转到语句块”操作——beqz指令
CPU已经将比较的结果保存到寄存器，接下来，CPU根据寄存器中的值(0或1)来判断执行哪一个语句块。指令beqz来查看寄存器中的值是否为0。如果为0，CPU将不再按顺序执行下一条语句，而是跳转到另一个语句块。对于将要跳转到的语句块，我们可以用一个“标签(Label)”来标记。beqz需要两个操作数，前一个操作数是存储比较结果的寄存器，另一个寄存器是一个标签。
这里beqz代表了branch if equals zero的意思。
格式： beqz  R4, label
注： “标签”术语第一次在本书中提及，汇编程序中有些指令块用标签label1、label2等标记，执行时就可以根据条件跳转，或者直接跳转到这些指令块处执行。beqz指令是根据条件来跳转的指令。它有两个操作数，一个是保存比较结果寄存器; 另一个是标签。
【例36】beqz  R4, label2
该指令表示，如果寄存器R4中的数值为零，则跳转到标签label2标记的指令块处。
4.    “直接跳转到语句块”操作——goto指令
格式： goto label
注： beqz指令是根据条件来选择是否跳转，goto指令是告诉CPU进行直接跳转的指令。它只有一个操作数，即“标签”label。
执行操作： 跳转到标签label标记的指令处。
【例37】goto  label3
表示跳转到标签label3标记的指令处执行。
3.3.3ifelse选择语句的执行



图39汇编指令表述ifelse

的执行


现在，我们把ifelse选择语句翻译为汇编指令。在前个小节的ifelse结构中，我们用到两个变量x和y在if x<y中。假定已经把x和y分别读取到寄存器R1和R2中。用汇编指令表示CPU在执行ifelse选择语句时的操作，如图39所示。
slt指令比较x和y的大小，如果x小于y，则寄存器R4置1，否则置0； 
beqz指令判断R4的值，根据R4是否为0，有两种执行情况。
其一，R4为1，即x小于y，则顺序执行语句块A，也就是程序中if之后的语句。执行完语句块A的所有语句后，会执行goto指令，直接跳转到语句块C，如图39中虚线(2)所示。
其二，R4为0，即x不小于y，则跳转到语句块B执行，也就是程序中else之后的语句，如图39中虚线(1)所示。执行完语句块B中的所有语句后，顺序执行语句块C，如图39中虚线(3)所示。
现在我们来细看ifelse选择语句的执行过程。
(1) 我们假定，ifelse选择语句翻译后的汇编指令从地址304处开始存储在主存，所使用到的变量x和y已经从主存地址1000、1001处分别读取到寄存器R1和R2中。
(2) 如图310所示，执行slt指令，CPU先将slt指令读取到指令寄存器IR，进行解读。之后CPU将寄存器R1和寄存器R2中的数值转移到ALU中。对于比较运算，ALU通过对两个数值做减法来判断。最终将比较的结果存回到寄存器R4中。PC加1，指向下一条指令beqz。


图310执行slt指令


(3) 如图311所示，执行beqz指令，CPU先将beqz指令读取到指令寄存器IR，进行解读，之后CPU判断寄存器R4的值。


图311执行beqz指令，假如x≥y


(4) 变量x和y有两种大小关系，若x不小于y(x≥y)，CPU将按照下面的步骤(5)和步骤(6)执行。否则，按照步骤(7)~(9)执行。
(5) 当x≥y时R4中值为0，则跳转到label 0处执行。如图311中虚线(2)所示，PC值变为401，指向label 0处，即语句块B的第一条语句。
(6) 执行完语句块B中的所有语句后，结束ifelse选择语句。此后PC值为500，顺序执行语句块C。
(7) 当x<y时，R4是1，执行beqz指令，不跳转到label0处执行，而是顺序执行语句块A的第一条语句。这时PC的值为306，指向语句块A的第一条语句。
(8)  执行至语句块A的最后一条语句时，PC值为400，指向goto指令。
(9) 如图312所示，CPU执行goto指令，跳转到label1。如图312中虚线(2)所示，PC值变为500，直接执行语句块C，结束ifelse选择语句。


图312执行goto指令


3.3.4while循环语句的执行
ifelse选择语句能够使我们选择执行某一个语句块，接下来，我们需要考虑如何重复执行语句。我们希望计算机能够重复执行某一个语句块。
在程序设计语言中，通常有两种循环控制结构，即while循环和for循环。我们先来了解一下while循环的执行逻辑。
基本while语句
ifelse选择语句根据表达式的真与假来选择其中一个语句块执行。我们需要计算机循环执行某一个语句块，而循环都需要有一个终止条件，那么，我们也可以根据表达式的真与假，来决定是否终止。如果表达式的值为假，我们就终止执行，否则继续重复执行。


图313while循环结构

的例子

图313是一个while循环的例子。我们通过这个例子来了解while循环的执行过程，如下： 
(1) 比较变量x和y的大小，如果x小于y，则执行语句块A，否则执行语句块B。
(2) 重复判断变量x是否小于y，如果小于，则重复执行语句块A。直到变量x不再小于y，此时不执行语句块A，而是结束while循环，执行语句块B。
汇编指令描述while语句的执行
下面我们来看一下，用汇编指令如何表述while循环的执行逻辑。
如图314所示，假定变量x和y已经分别读取到寄存器R1和R2中。我们将计算机执行while循环语句时CPU需要做的操作翻译为汇编指令，如图314所示。


图314用汇编指令表述while循环的执行

(注： 完整的汇编指令还应该包括，将变量x和y分别读取到寄存器R1、R2中并赋值的操作，之后变量x和y就分别有了初值)


此后，CPU将执行图314所示的汇编指令。步骤如下。 
(1)  CPU执行slt指令，比较寄存器中的变量x和y的大小，并将比较结果保存到寄存器R4中。如果x小于y，则R4置1，否则置0。
(2)  CPU执行beqz指令，如果R4中值为0(就是R1不小于R2)，就跳转到步骤(5)。否则，R4=1(即R1小于R2)，则不跳转，顺序执行步骤(3)。
(3)  CPU顺序执行下一条语句，也就是语句块A中的第一条语句，并顺序执行完语句块A中的所有语句。
(4)  CPU执行goto指令，执行后的结果是跳转到slt指令，如图虚线(1)所示。即跳转到步骤（1）。
(5) 结束while循环结构。跳转到label0处，执行语句块B，如图虚线(2)所示。
3.3.5for循环语句的执行
编写程序时，for循环很常用。通常，for循环是用来告诉计算机要重复执行语句块达到多少次，但是一些程序语言，如Python中的for循环有时也不需要在程序中表示需要执行的次数。
1.  基本for循环结构
不同的程序语言中，定义了不同的for循环语句形式，但for循环的执行逻辑却是大同小异。如图315所示为for循环语句的基本形式。通常，for循环语句会有一个变量i来控制循环次数，每执行一次语句块，变量i的值会做相应的变化。假定需要循环执行10次，变量i取初值0，执行语句块A。之后变量i取值1，执行语句块A。接下来变量i取值2，重复执行语句块A，直到变量i的值不再小于10，就不再重复执行语句块A，而是终止for循环，即执行语句块B。


图315基本for循环结构

(注： 语句“for i in range(0,10)”表示0≤i<10，i取值0，1，2，…，9)


现在，我们来细看for循环结构的执行逻辑。
（1） 我们有一个变量i来记录循环次数，先决定一个寄存器来代表i。
（2） 给变量i赋一个初值。
（3） 比较变量i是否小于设定的常数，如果小于，则执行步骤（4），否则跳转到步骤（5）。
（4） 执行语句块A。然后变量i加1，之后直接跳转到步骤（3）。
（5） 结束for循环。执行语句块B。


沙老师： 虽然while循环可以取代for循环，但是for循环比较明白易懂，所以“遍历”就用for循环，能用for循环就用for循环，尤其是Python更要多用for循环。另外，while循环的条件语句可繁可简。当while循环的条件语句太复杂时，请把这个条件语句用函数来表示，会比较清楚。


2.  for循环执行过程
下面，我们也用汇编指令的形式表达出CPU执行for循环语句时应该做的动作，如图316所示。


图316汇编指令表述for

循环的执行

(1)  CPU执行slt指令，比较寄存器R1中的变量i和10的大小，并将比较结果保存到寄存器R4。如果i小于10，则R4置1，否则置0。
(2)  CPU执行beqz指令，如果寄存器R4中值为1，则顺序执行步骤(3)，否则跳转到label0，如图316虚线(2)所示。
(3)  CPU执行语句块A的第一条指令。之后，CPU顺序执行完语句块A的所有语句。
(4)  CPU执行add指令，给寄存器R1中的变量i加1。
(5)  CPU执行goto指令，执行后的结果是跳转到slt指令，如图虚线(1)所示，即跳转到步骤（1）。
其实，for循环的执行过程和while循环很相似。在图314中，while循环的语句块A中通常也有一条语句来更改循环变量x的值，否则变量x一直保持初值，就一直小于10，那么就会一直执行语句块A，这就是常说的“死循环”。


沙老师： 其实在汇编语言里跳转指令中的label并不是绝对地址。例如“goto X”，在真实的指令集里这些X是相对于现在指令地址的正负偏移量。
CPU要算出目标地址就是PC=PC+偏移量X。各位把我下面这句话记下来，这非常重要： CPU执行两种计算： 第一，地址的计算； 第二，程序中变量的计算。地址的计算隐藏在程序执行后面，是CPU一直在做的计算，你们不可不知道啊！


在Python中，for循环和while循环里面可以出现break语句，只要碰到break语句，就马上跳出循环。后面还可以跟着else语句，假如跳出循环的原因是因为碰到了break而跳出，循环后的else就不会执行； 假如是正常离开循环，else后面的程序块就会执行。详情请参阅第4章的Python介绍。
小结
本节逐步探索了ifelse选择语句、while循环语句、for循环语句在计算机中的执行过程。我们还是先描述出计算机执行这些程序时CPU需要执行的操作，然后用相应的汇编指令来表示这些操作。在本小节，我们又添加了slt、goto label、beqz R label这些指令来表示CPU执行的操作。执行程序时，CPU总是一条一条地取指令，解读，最后执行相应的操作。程序的执行，就是CPU不断取指令、执行指令的过程。
3.4关于Python的函数调用
我们已经学习了基本语句a=a+1和控制结构语句(ifelse选择语句、while循环语句、for循环语句)的执行过程，下一步我们就要探索函数调用在计算机中的执行过程了。在此之前，我们需要了解什么是函数，什么是函数调用，函数调用中的一些变量的作用范围等。本小节，我们将初步了解到Python中函数调用的相关内容。
3.4.1函数的基本概念
回顾一下高中数学中的函数。在数学中，假设要实现z+xy2这个计算。对于乘法计算，定义一个函数f(x, y)=xy2，它有两个参数x和y。计算xy2后得到一个值，作为函数的返回值，赋给f(x,y)。这样就可以用z+f(x, y)来表示上面的运算，对于f(x, y)运算，将会调用到已经定义的函数f(x, y)=xy2。
可以看到，数学中的函数有参数，有返回值，需要先定义，后调用。另外，还可以多处调用。也就是说，一旦定义了函数f(x, y)=xy2，我们在后面用到式子xy2时，都可以用f(x, y)代替，即所说的“多次调用”。
程序语言中的函数和数学中的函数的基本概念是相似的。程序语言中的函数也有参数和返回值，以及定义与调用。我们稍后将会看到，程序中的函数，就是将一些程序语句结合在一起的部件，通过多次调用，函数可以不止一次地在程序中运行。那么程序中使用函数会有什么好处呢？
第一，将大问题分成许多小问题。函数可以将程序分成多个子程序段，程序员可以独立编写各个子程序，实现了程序开发流程的分解。每个函数实现特定的功能，我们可以针对这个函数来撰写程序。
第二，便于检测错误。一个函数写好之后，我们会验证其实现的正确性。程序是由多个函数组成的。我们确定了每一个函数是正确后，总程序出错的可能性就会降低。另外函数的代码量小，也便于检测错误。


小明： 有没有什么程序是不用函数的？
沙老师： 有意义的程序都会用函数。我想一个程序的结果总要输出吧！不管是输出到屏幕或硬盘的文件系统，都要调用I/O输出函数，例如print函数。操作系统提供了这类函数供程序来调用。操作系统的功能之一就是提供一大堆的系统函数来“服务”程序。为了安全，程序不能直接使用I/O硬件，一定要请求操作系统的服务，让操作系统来使用I/O硬件。我们在操作系统的章节会做解释的。


第三，实现“封装”和“重用”。封装的意思是隐蔽细节。例如函数GCD(x, y)是返回x和y的最大公约数。“封装”的特点体现在，对于各个求两数的最大公约数GCD的操作，都只需要传递两个参数x和y给函数GCD，函数GCD会返回相应的结果，而不必关注GCD操作的具体实现。“重用”的特点体现在，各个程序都可以直接调用已经写好的GCD函数来实现最大公约数的计算，而不用重复编写代码。一个写好的函数，可以被多次调用，这种“重用”提高了程序的开发效率。
第四，便于维护。每一个函数都必须要有清楚的界面和注释，包含了功能、输入的参数、返回值的解释等。让人知道怎样调用这个函数。只要函数的界面不变，被调用函数的细节改变是不会影响全局的。


小明： 函数真的这么有用啊？
沙老师： 函数是非常有用的。一个好的编程的诀窍是： 先从上而下，再从下而上。从上而下(TopDown)决定了架构，要编写哪些函数和每一个函数的功能。再从下而上(BottomUp)，编写和检错每一个函数。这样程序就编成了。一个程序的美丑基本上就看你的程序是怎么分工、怎么定义和怎么使用函数了。


3.4.2Python函数入门
对于计算z+xy2，数学中用函数表达如下： 
(1) 函数定义： f(x, y)= xy2。
(2) 参数为x和y。
(3) 返回值是xy2的结果。
(4) 调用方式为z+f(a, b)，a和b是分别传递给函数f的具体数值。
Python函数表达如下。
(1) 函数定义

def  f(x, y):

return x*y*y

Python函数的定义由关键字def开始，后面跟上函数名和括号，括号里面是函数的参数，接着是冒号，最后就是函数体的内容。Python函数定义的语法形式如下： 

def 函数名(参数1,参数2,…):

函数体

(2) 在上面定义的函数f中，参数也有两个，即x和y，这些参数是函数f的“局部变量”，也就是它们的生命范围只限制在这个函数中(“局部变量”“全局变量”的相关概念，我们在后面会进行更详细的讲解)。调用函数f时，会传递实际的值赋给函数f的参数。每一个函数中都可以有0个、1个或更多个参数，相邻参数之间用逗号隔开。形式如下： 

参数1,参数2,参数3,…

(3) 函数f中有一个关键字return，其后跟的值就是本函数将返回的值，即“返回值”。假设函数f0调用函数f，return语句是将被调用的函数f的计算结果返回给调用f的函数f0中的变量。return关键字后面可以是一个数值，也可以为一个表达式，在执行return语句后函数结束。一个函数可能有多条return语句，执行到第一条return语句时将结束函数。形式如下： 

return返回值或者表达式

如果进行调用的函数f0不需要被调函数f返回结果，那么被调函数就不需要return语句，即没有返回值。当然，Python中的被调函数还可以返回多个值。
(4) 调用方式为“c=f(a, b)”。其中，a和b是传递给函数f的值。比如，在函数f0中有这样一条语句“c=f(3, 2)”，3和2就是函数f0传递给函数f的两个参数，即在f函数中的局部变量x和y的值分别被设为3和2。之后执行函数f，计算3×2×2的结果并返回，返回的值赋给函数f0的变量c。进行函数调用时，函数f0称为“主调函数”，而函数f称为“被调函数”。调用语句形式如下： 

主调函数中的变量=被调函数名(参数1,实数2,…)




#<程序： 计算4+3*22>

def  f(x, y):

return x*y*y

#主函数部分

c=4+f(3, 2)

print (c)




在计算4+3×22时，使用Python函数的示例#<程序： 计算4+3*22>。运行示例程序，将会输出结果16。
3.4.3局部变量与全局变量
在函数中出现的变量，可以分为局部变量和全局变量。先记下这条规则： 在函数中假如没有global语句，所有在等号左边出现的变量以及参数都是“局部变量(Local variables)”，它只能被这个函数访问，而不能被其他函数访问。在有些程序中，还有“嵌套函数”，嵌套函数是指在函数中再定义函数，但本书不使用这个功能，所以本书不谈“嵌套函数”。在本书中的变量就是两层，一层在函数内，一层在函数外，在函数之外被赋值的变量是“全局变量(Global variables)”。我们把局部变量搞清楚后，那些在函数中出现的变量，不是局部变量，就是全局变量。需要注意的是，在Python中，非函数和类里写的变量都是全局变量。
先来看这样一个例子#<程序： 打印局部变量a和全局变量a>。



#<程序： 打印局部变量a和全局变量a>

a=10#函数外

def func():

a=20    #函数内，局部变量的赋值，不会改变全局变量

print(a)  #函数内

func()

print(a)   #函数外的a




这里，func()函数里面和外面的变量名是一样的，都为a，但输出结果却是不同的。a=10语句中的变量a是函数外被赋值的变量，它为这个文件的全局变量，而func()函数中a=20语句中的变量a，是在func()函数中被赋值的(在等号左边)，就是局部变量。外部的变量a和func()函数内部的变量a是不同的变量，只是拥有相同的变量名而已。所以，前面的例子将会输出20和10。
判断函数内部的变量a是否为局部变量的方法： ①不出现在global语句里面； ②出现在函数参数中，或者出现在函数语句的等号左边。
在前面这个例子中，如果在函数中使用global语句来声明变量a，那么这个变量a就是全局变量a，如#<程序： 关键字global引用全局变量>所示。



#<程序： 关键字global引用全局变量>

a=10

def func():

global  a#宣告这个是全局变量

a=20

print(a)

func()

print(a)




global语句包含了关键字global，后面跟着一个或多个用逗号分开的变量名。
在这个例子中，global语句后跟着变量a，表明该函数内使用的变量a是全局的。所以，func()函数中的a=20语句会修改全局变量a的值，程序会输出20和20。
然而，在不使用global语句声明某变量是全局时，如果这个变量出现在函数语句的等号左边，那么它就是局部变量。请看例子#<程序： a, b, c是否为局部变量？>。



#<程序： a, b, c是否为局部变量？>

b,c=2,4

def g_func():

a=b*c#a是局部变量

d=a		#d是局部变量，其他都是全局变量

print(a,d)

g_func()

print(b,c)

>>> #输出结果

8  8

2  4




这里的函数g_func()中，变量a和d是局部变量，因为它们没有被声明为global且出现在等号左边。变量b和c是全局变量，尽管它们没有被声明为global，但是它们不是函数的参数，且只是出现函数中语句的等号右边。
练习题3.4.1： 运行下面这个程序，将会输出什么？在gfunc()函数中哪些是局部变量？

b, c=2, 4

def g_func(d):

global a

a=d*c

g_func(b)

print(a)

练习题3.4.2： 运行下面这个程序，将会输出什么？

a=10

def func():

x=a

print(x)

func()

print(a)

练习题3.4.3： 变量a，b是否为局部变量？再分析这个程序会输出什么？

a=10           

def func(b):

c=a+b     

print(c)

func(1)

接下来，为加深理解，我们给出一个更复杂的Python程序#<程序： 四则运算例子>。



#<程序： 四则运算例子>

def do_div(a, b):

c=a/b#a, b, c都是do_div()函数中的局部变量

print (c)   

return c

def do_mul(a, b):     

global c

c=a*b               #a, b是do_mul()函数的局部变量，c是全局变量

print (c)

return c

def do_sub(a, b):       

c=a-b           		 #a, b, c都是do_sub()函数中的局部变量

c=do_mul(c, c)     

c=do_div(c, 2)     

print (c)           

return c          

def do_add(a, b):      		 #参数a和b是do_add()函数中的局部变量

global c           

c=a+b             		 #全局变量c，修改了c的值

c=do_sub(c, 1)      	 #再次修改了全局变量c的值

print (c)         

#所有函数外先执行:

a=3                   	 #全局变量a

b=2                   	 #全局变量b

c=1                   	 #全局变量c

do_add(a, b)             #全局变量a和b作为参数传递给do_add()函数

print (c)     			 #全局变量c




输出的结果是16, 8, 8, 8, 8。我们来分析一下这个程序的执行过程。
(1) 调用do_add()函数，将全局变量a和b传递给do_add()函数。
(2)  do_add()函数中，声明了全局变量c。全局变量c的值改为5。调用了do_sub()函数，将全局变量c和数字1传递给do_sub()函数，并将do_sub()函数的结果返回给全局变量c，即再次修改了c的值。
(3)  do_sub()函数将参数a和b做减法，并将减法结果赋值给局部变量c，此时局部变量c的值为4。注意，此时全局变量c的值仍为5。调用do_mul()函数，将局部变量c的值(为4)传递给do_mul()函数。
(4)  do_mul()函数声明了全局变量c，并将参数a和b相乘的结果赋值全局变量c，全局变量c的值变为16。打印出本程序的第一个结果，即16。然后将结果返回给do_sub()函数的局部变量c。也就是说，do_sub()函数里的局部变量c的值不再是4，而是16。
(5) 调用do_div()函数，并将局部变量c的值(为16)和数字2传递给do_div()函数。
do_div()函数将参数a和b相除的结果赋值给局部变量c，局部变量c的值为8。注意，此时全局变量c的值仍为16。打印出本程序的第二个结果，即局部变量c的值8。然后将局部变量c的值8返回给do_sub()函数的局部变量c。
(6) 调用do_div()函数的过程结束，程序返回到do_sub()函数，打印出本程序的第三个结果，即do_sub()函数的局部变量c的值8。
(7) 调用do_sub()函数的过程结束，并将do_sub()函数的局部变量c的值8返回到do_add()函数中，赋给全局变量c。打印出本程序的第四个结果，即全局变量c的值8。
(8) 调用do_add()函数的过程结束，程序返回，打印出本程序的第五个结果，即全局变量c的值8。
所以，程序最终输出的结果依次为16, 8, 8, 8, 8。



沙老师： “global a”语句的目的是让全局变量a出现在函数里被赋值改变！这是不美的编程方法。函数应该像是一个黑盒子，它只有参数的输入和return的输出，细节过程是被隐蔽的。这个黑盒子不应该偷偷地改变了外部的全局变量。大家尽量不要用global语句，好吗？


上面这个程序是函数调用中稍微复杂的情形，并且用了global语句来声明全局变量。如果把global语句放在不同的函数中，输出结果会发生什么变化呢?
练习题3.4.4： 修改前面的程序，去掉do_add()函数中的“global c”语句，分析程序将会输出什么？
练习题3.4.5： 执行下面的程序会出现什么错误？

#<程序： 参数a能成为global>

a=10

def  func(a):

global a

a=20

print (a)

func(a)

print (a)

练习题3.4.6： 结合下面的程序，思考一下，如果func()函数中的某个等号左边和右边出现一个同样的变量名，如同下一个程序，为什么会出现错误？

local variable 'a' referenced before assignment.





#<程序： 打印变量a>

a=10

def func():

a=a+10

print(a)

func()

print(a)




提示： Python语句中，首先决定出现在等号左边的a为局部变量,然后运算右边的a+10，而这时a是没有值的。
关于局部变量和全局变量的更多细节，本小节就不过多讲解。如果大家遇到了这些问题，可以进行进一步的探索。如果有同学对Python中内置的_builtin_模块或者嵌套函数的使用感兴趣，也可以查阅资料，进行深入的学习。
小结
在本小节，我们先简单介绍了程序中的函数是什么，Python函数的基本特点，以及函数的定义、调用、参数传递等。我们重点讲解了Python函数中的局部变量，当一个变量不出现在global语句里面，且出现在函数参数中，或者出现在函数语句的等号左边时，才能够被称为本函数的局部变量。其实，我们很少用到global语句，因为这样会在某一个函数中修改全局变量，对其他函数来说是隐藏的，可能会引起程序出错。局部变量、全局变量的概念对我们编写程序起着极其重要的作用。
3.5函数调用过程的分析	
在3.4节，我们了解了Python函数调用的相关内容，下面我们继续探索函数调用在计算机中的执行过程。在分析函数调用过程之前，我们先讲一下“栈(Stack)”的基础知识。
栈是一种非常重要的数据结构，它按照先进后出的原则存储数据，即先进入的数据被压入栈底，最后的数据在栈顶，需要取数据的时候从栈顶开始弹出数据。所以它的特色是“先进后出”或“后进先出”。
栈的特别之处在于，我们只能从一端放数据和取数据，就像一个桶一样，只能从桶口放东西和取东西。图317(a)表示在栈中没有数据，此时栈底和栈顶指向同一个位置； 将数据1放入栈中，执行压入(push)操作，如图317(b)所示，1被放入栈中，栈顶向上移； 将数据5放入栈中，执行压入(push)操作，如图317(c)所示，5被放入栈中，栈顶向上移。


图317一个栈连续放入数据的过程


图317所示为连续放入数据的过程，下面我们来看从栈中取数据的过程。如图318所示为初始状态，有3个数据存在栈中； 执行一次取数据(pop)操作，则在最顶上的数据8被弹出，得到数据8，此时栈中的情况如图318(b)所示； 继续执行一次取数据(pop)操作，在最顶上的数据5被弹出，得到数据5，此时栈中的情况如图318(c)所示。总之，栈的基本操作就是push和pop。


图318一个栈连续取数据的过程


由于栈的这种特殊的结构，在我们计算机科学中有着非常广泛的应用。例如给定一个单词stack，想要把这个单词中的字母翻转，应用栈是很容易实现的，只需要将s，t，a，c，k这5个字母依次存入栈中，然后再取出就可以得到k，c，a，t，s了。


沙老师： 用编程来解决问题时，我们常用的一些数据结构包含了数组(Array)、栈(Stack)、队列(Queue)、树(Tree)、图(Graph)等。Stack是后进先出，Queue是先进先出。有趣的是计算机里Stack用得多，而在人类社会里Queue用得多。想想我们在排队时，假如用Stack的方式，最后进的人最先得到服务，会怎么样？ 
小明： 那也不错，大家都礼让别人，“抢着”做最后一个。


3.5.1返回地址的存储
通过前面的学习，我们知道当执行一条指令时，总是根据PC中存放的指令地址，将指令由内存取到指令寄存器IR中。程序在执行时按顺序依次执行每一条语句，即执行完一条语句后，继续执行该语句的下一条语句。因此，PC每次都通过加1来指向下一条将要执行的程序语句。
但也有一些例外，遇到这些例外情况时，不按顺序依次执行程序中的语句。这些例外如下。
(1) 调用函数； 
(2) 函数调用后的返回； 
(3) 控制结构，比如if、for、while等。
在本小节中，我们主要讲解函数调用及函数调用后的返回。
首先要明白一个基本概念： 主调函数和被调函数。主调函数是指调用其他函数的函数； 被调函数是指被其他函数调用的函数。一个函数很可能既调用别的函数，又被另外的函数调用。如图319所示的函数调用中，fun0函数调用fun1函数，fun0函数就是主调函数，fun1函数就是被调函数。fun1函数又调用fun2函数，此时fun1函数就是主调函数，fun2函数就是被调函数。
发生函数调用时，程序会跳转到被调函数的第一条语句，然后按顺序依次执行被调函数中的语句。函数调用后返回时，程序会返回到主调函数中调用函数的语句的后一条语句继续执行。换句话说也就是“从哪里离开，就回到哪里”。


图319函数调用

例如，图319中的函数调用执行顺序如下。
(1)  fun0函数从函数的第一条语句开始执行，然后调用fun1函数，程序跳转到fun1函数的第一条语句，顺序执行fun1函数中的语句； 
(2)  fun1函数调用fun2函数，程序跳转到fun2函数的第一条语句，然后按顺序执行fun2函数； 
(3)  fun2函数执行完后，返回到fun1函数，继续执行fun1函数中“调用fun2函数语句”的下一条语句。在图中我们将B标示在该条语句旁边，表示该条语句的地址为B。返回后按顺序执行fun1函数后面的语句； 
(4)  fun1函数调用fun3函数，程序跳转到fun3函数的第一条语句，然后按顺序执行完fun3函数； 
(5)  fun3函数执行完后，返回到fun1函数，继续执行fun1函数中“调用fun3函数语句”的下一条语句。在图中我们将C标示在该条语句旁边，表示该条语句的地址为C。返回后按顺序执行fun1函数后面的语句； 
(6)  fun1函数执行完后，返回到fun0函数，继续执行fun0函数中“调用fun1函数语句”的下一条语句。在图中我们将A标示在该条语句旁边，表示该条语句的地址为A。返回后按顺序执行fun0函数后面的语句。执行步骤与图319中(1)~(6)一一对应。
我们在看具体的函数时，很容易看出发生函数调用时会跳转到哪一条语句，也很容易看出函数返回时会返回到哪一条语句。但是，这是因为我们是作为一个“局外人”来看，我们可以纵观整个程序。而CPU执行程序时，并不知道整个程序的执行步骤是怎样的，完全是“走一步，看一步”。前面我们提到过，CPU都是根据PC中存放的指令地址找到要执行的语句。函数返回时，是“从哪里离开，就回到哪里”。但是当函数要从被调函数中返回时，PC怎么知道调用时是从哪里离开的呢？
答案就是——将函数的“返回地址”保存起来。
因为在发生函数调用时的PC值是知道的。在主调函数中的函数调用的下一条语句的地址即为当前PC值加1，也就是函数返回时需要的“返回地址”。我们只需将该返回地址保存起来，在被调函数执行完成、要返回主调函数中时，将返回地址送到PC。这样，程序就可以往下继续执行了。
我们要合理地管理返回地址。观察函数调用及返回过程可发现，函数调用的特点是： 越早被调用的函数，越晚返回。比如fun1函数比fun2函数先被调用，fun1函数比fun2函数后返回； fun1函数比fun3函数先被调用，fun1函数比fun3函数后返回。这一特点刚好满足“后进先出”的要求，因此我们采用“栈”来保存返回地址。栈的基本操作就是压入和弹出。“压入a”就是存放a在栈顶上； “弹出”就是将栈顶的值取出来，而后栈中就少了一个数据了。
图320给出了保存返回地址的过程。在图319中，调用过程(1)发生时，需要压入保存返回地址A，栈的状态如图320中(a)所示； 调用过程(2)发生时，需要压入保存返回地址B，栈的状态如图320中(b)所示； 返回过程(3)发生时，需要弹出返回地址B，栈的状态如图320中(c)所示； 调用过程(4)发生时，需要压入保存返回地址C，栈的状态如图320中(d)所示； 返回过程(5)发生时，需要弹出返回地址C，栈的状态如图320中(e)所示； 返回过程(6)发生时，需要弹出返回地址A，此时栈被清空，图中未画出具体情况。所以函数调用时系统用栈来管理。


图320返回地址的存储


3.5.2函数调用时栈的管理
事实上，函数的局部变量也是和返回地址绑定在一起用栈来管理。在本小节中，我们先为大家讲解局部变量的存储情况。
局部变量
我们用图321中的函数调用的例子来讨论变量的存储情况。


图321函数调用实例

在图321的函数中，fun函数要调用do_add()函数。fun函数里有变量a，a的值为10； 在do_add()函数里也有变量a，a的值为3。虽然这两个函数中的变量a有相同的名字，但显然两个函数中a的值是不同的。fun函数里的变量a和do_add()函数里的变量a是两个不同的变量，即这两个变量需要存放在不同的地方。
do_add()函数中的局部变量a只有在函数内才有意义； 局部变量的存储一定是和函数的开始与结束息息相关的。局部变量与返回地址一样，也是存在栈里，当函数开始执行时，这个函数的局部变量在栈里被设立(压入)，当函数结束时，这个函数的局部变量和返回地址都会被弹出。
参数传递
在图321的例子中，调用函数时有参数的传递。fun函数调用do_add()函数时，需将fun函数里变量a的值传递给do_add()函数里的变量c。那么fun函数是怎样把变量a的值传递给变量c的呢？事实上，在调用有参数传递的函数时，变量c也是do_add()函数里的局部变量，该局部变量由fun函数里的变量a来初始化。比如fun函数里变量a的值为10，当调用do_add()函数时，局部变量c就复制变量a的值10。因此，在do_add()函数里局部变量c的初始值就为10。
返回值
在do_add()函数中，最后有一条返回语句“return d”。表明在执行完do_add()函数后，需要将局部变量d的值传递给主调函数fun函数的变量b。与参数传递同理，在传递返回值时，也是将局部变量d的值赋值给主调函数中的变量b。我们讲过，局部变量只在函数内有意义，离开函数后该局部变量就失效。比如do_add()函数里的局部变量d，执行do_add()函数时d是有意义的。但执行完do_add()函数后，返回到fun函数中，do_add()函数里的局部变量d就失效了。因此在弹出d时需要用一个寄存器将返回值d保存起来，所以在外面的调用函数可以来读取这个值。
局部变量是在函数执行的时候才会存在。当函数结束后，这些局部变量就不存在了。如前所述，局部变量的调用和栈的操作模式“后进先出”的形式是相同的。这就是为什么返回地址是压入栈里，同样地，局部变量也会压到相对应的栈里面。当函数执行时，这个函数的每一个局部变量就会在栈里有一个空间。在栈中存放此函数的局部变量和返回地址的这一块区域叫作此函数的栈帧(Frame)。当此函数结束时，这一块栈帧就会被弹出。
接下来通过图321的例子来说明函数调用时这些信息的存储情况。图322展示了该例执行过程中栈的变化情况。


图322函数调用时栈的状态变化


在该例中，从函数fun开始执行(在函数fun之前，可能还有其他函数调用fun，栈中也还存有其他数据，这里不详细讨论)。
(1) 调用do_add()函数前执行的操作(该执行步骤中的(1)~(3)分别与图322(a)、图322(b)、图322(c)中栈的状态一一对应)。
①  fun的局部变量a压入栈中，其值为10； 
② 局部变量b压入栈，由于b的值还未知，因此先为b预留出空间。
(2) 调用do_add()函数时执行的操作。
① 返回地址压入栈中； 
② 局部变量c的值10压入栈中。此处注意，c是do_add()函数中的局部变量，c的值是通过复制fun函数中的局部变量a的值得到的； 
③ 压入do_add()函数中的局部变量a，其值为3； 
④ 执行a+c，其中a=3，c=10，相加后得d的值为13。
(3)  do_add()函数返回时执行的操作。
①  do_add()函数执行完后，依次弹出do_add()函数的局部变量，由于需要将d的值返回，因此在弹出d时需要用一个寄存器将返回值d保存起来； 
② 然后弹出返回地址，将返回地址传到PC； 
③ 返回到fun函数，fun中的局部变量b的值即为do_add()函数中的返回值d，此时将寄存器中的值赋值给b。
在将数据压入和弹出栈时，都需要用到栈顶的地址，因此需要将栈顶地址记录下来。在函数调用时，用一个寄存器将栈顶地址保存起来，称为栈顶指针SP。另外还有一个帧指针FP，用来指向栈中函数信息的底端。这样，栈就被分成了一段一段的空间，这样的一段空间我们就称为栈帧。
每个栈帧对应一次函数调用，在栈帧中存放了前面介绍的函数调用中的返回地址、局部变量值等。每次发生函数调用时，都会有一个栈帧被压入栈的最顶端； 调用返回后，相应的栈帧便被弹出。当前正在执行的函数的栈帧总是处于栈的最顶端。
以图319中函数fun1依次调用fun2和fun3为例，图323中(a)~(d)为调用过程中栈空间的信息情况。首先在栈中将fun1函数的信息都存储起来，SP与FP分别指向存储fun1信息的栈空间的顶端和底端，如图323(a)所示； 然后fun1函数调用fun2函数，在栈中将fun2函数的信息都存储起来，存储位置位于fun1函数的信息的顶部，SP与FP分别指向存储fun2信息的栈空间的顶端和底端，如图323(b)所示； fun2函数执行完后，要返回到fun1函数中，fun2函数的信息被弹出，SP与FP分别指向存储fun1信息的栈空间的顶端和底端，如图323(c)所示； fun1函数又调用fun3函数，在栈中将fun3函数的信息都存储起来，存储位置位于fun1函数的信息的顶部，SP与FP分别指向存储fun3信息的栈空间的顶端和底端，如图323(d)所示； fun3函数和fun1函数执行完后，也会分别返回，相应的信息会从栈中弹出，栈的状态未在图中画出。


图323函数调用时栈空间的信息


由于函数调用时，要不断地将一些数据压入栈中，SP的位置是不断变化的，而FP的位置相对于局部变量的位置是确定的，因此函数的局部变量的地址一般通过帧指针FP来计算，而非栈顶指针SP。
综合前面所讲到的知识，可以总结出： 一个函数调用过程就是将数据(包括参数和返回值)和控制信息(返回地址等)从一个函数传递到另一个函数。在执行被调函数的过程中，还要为被调函数的局部变量分配空间，在函数返回时释放这些空间。这些工作都是由栈来完成的，所传参数的地址可以简单地从FP算出来。图324展示了栈帧的通用结构。
为了使大家对函数调用时信息的存储了解得更加清晰，下面通过图325中递归函数的例子，将前面所讲的需要存储的信息综合在一起，来研究函数调用时对栈的管理。
在该例中，从函数pre()开始执行(该执行步骤中的(1)~(5)分别与图326的(a)~(e)中栈的状态一一对应)。
(1)  pre()函数调用fac(1)函数前执行的操作。
①  pre()的局部变量m压入栈中，其值为1； 
② 局部变量f压入栈，由于f的值还未知，因此先为f预留出空间。
(2)  pre()函数调用fac(1)函数时执行的操作。
① 返回地址压入栈中； 



图324栈帧结构



图325递归调用实例




图326递归函数调用的栈示意图


②  fac(1)的局部变量n压入栈中，其值为1； 
③ 局部变量r压入栈，由于r的值还未知，因此先为r预留出空间。
(3)  fac(1)函数调用fac(0)时执行的操作。
① 返回地址压入栈中； 
②  fac(0)的局部变量n压入栈中，其值为0； 
③ 此时递归达到了终止条件(n==0)，结束递归，局部变量r压入栈，r值为1。
(4)  fac(0)函数返回时执行的操作。
① fac(0)函数执行完后，依次弹出fac(0)的局部变量。在弹出r时用一个寄存器将返回值r保存起来； 
② 弹出返回地址，将返回地址传到PC； 
③ SP=FP，令SP指回fac(1)栈帧的顶部，令FP指回fac(1)栈帧的底部； 
④ 继续执行fac(1)函数，fac(1)中的局部变量r的值即为fac(0)函数中的返回值乘以n。
(5)  fac(1)函数返回时执行的操作。
① fac(1)函数执行完后，依次弹出fac(1)的局部变量。在弹出r时用一个寄存器将返回值r保存起来； 
② 弹出返回地址，将返回地址传到PC； 
③ SP=FP，令SP指回pre()栈帧的顶部，令FP指回pre()栈帧的底部； 
④ 继续执行函数pre()，pre()中的局部变量f的值即为fac(1)函数中的返回值r，此时将寄存器中的值赋值给f。
各类微处理器对函数调用的处理方式会有所差异，同一体系结构中对不同语言的函数调用的处理方式也会有少许的差异。但通过栈存储局部变量和返回地址等信息，这一点是共同的。我们不需要对函数调用中的每一个执行的细节都了解清楚，大家只要对这个过程有一个初步的认识，知道每一次函数调用对应一个栈帧，栈帧中包含了返回地址、局部变量值等信息。还有一点需要注意，在本书中所用的Python语言属于解释性语言，Python中发生函数调用时所建立的栈不是编译时建立的(像C语言等是在编译时就建好了栈)，是在有需要的时候再建立的。
我们用一个因数分解的Python程序，来讲解Python程序运行时栈的建立过程。这个例子是用递归的方式来调用函数。



#<程序： 因数分解>   Print all the prime factors (>=2) of x.  By Edwin Sha

import math#为了要调用平方根函数，此函数在math包里

def factors(x):  		#找到x的因数

y=int(math.sqrt(x))

for i in range(2,y+1):		#检查从2 到 x的平方根是否为x的因数

if (x %i ==0):　　		#发现i是x的因数

print("Factor:",i);

factors(x//i)		#递归调用自己，参数变小是x//i

break  		#跳出for循环

else:  #假如正常离开循环，没有碰到break，就执行else内的print，
#x是质数

print("Prime Factor:",x)

print("局部变量： 参数x:%d, 变量y:%d" %(x,y))

return





#函数外，先执行的部分

factors(18)#找出18的所有因数

运行该因数分解的Python程序后，会输出什么呢？我们先要先讨论这个Python程序的执行顺序以及栈的建立过程。
第1步，该程序从非函数定义的第一条语句开始执行，即语句factors(18)开始执行。首先建立一个main函数的栈帧，栈帧中保存的信息为main函数中的信息。如图327(a)所示。
第2步，第一次调用函数factors(x)。先保存函数的返回地址。压入局部变量x，值为18； 压入局部变量y，值为4(语句y=int(math.sqrt(x))表示： y的值等于x的值开平方根后取下整。事实上，调用math.sqrt(x)函数时也要建栈帧，大家知道即可，这里我们不详细讲解)； 压入局部变量i，值为2。此时程序执行到if语句，if语句中的表达式值为真，因此会执行print语句，由于局部变量i值为2，输出“Factor： 2”。栈的状态如图327(b)所示。
第3步，第二次调用函数factors(x)。先保存函数的返回地址。压入局部变量x，值为9； 压入局部变量y，值为3； 压入局部变量i，值为2。由于if语句中的表达式值为假，i值会加1，变为3。此时if语句中的表达式值为真，因此会执行print语句，由于局部变量i值为3，输出“Factor： 3”。栈的状态如图327(c)所示。
第4步，第三次调用函数factors(x)。先保存函数的返回地址。压入局部变量x，值为3； 压入局部变量y，值为1。由于i值不能满足大于或等于2并且小于2，所以不执行for循环，跳转执行else中的print语句，由于局部变量i值为3，所以输出“Prime Factor： 3”。之后顺序执行下一条print语句，由于局部变量x值为3，y值为1，所以输出“局部变量： 参数x： 3，变量y： 1”。栈的状态如图327(d)所示。
第5步，程序顺序执行到return语句，弹出顶端的栈帧，返回到第二次调用函数factors(x)后的状态。程序返回到语句factors(x//i)，顺序执行break语句，退出for循环。是由break跳出的所以不会执行else中的print语句，由于局部变量x值为9，y值为3，所以输出“局部变量： 参数x： 9，变量y： 3”。栈的状态如图327(e)所示。
第6步，程序顺序执行到return语句，弹出顶端的栈帧，返回到第一次调用函数factors(x)后的状态。程序返回到语句factors(x//i)，顺序执行break语句，退出for循环。是由break跳出的所以不会执行else中的print语句，由于局部变量x值为18，y值为4，所以输出“局部变量： 参数x： 18，变量y： 4”。栈的状态如图327(f)所示。
第7步，程序顺序执行到return语句，弹出顶端的栈帧，返回到第一次调用函数factors(x)前的状态。栈的状态如图327(g)所示。程序返回到语句factors(18)。执行完main函数后，弹出顶端的栈帧，此时栈为空(图中未画出)。


图327因数分解程序的栈示意图


在上述步骤中，第1步至第4步为函数的调用过程，第5步至第7步为函数的返回过程。
程序运行的结果： 

Factor: 2

Factor: 3

Prime Factor: 3

局部变量： 参数x:3，变量y:1

局部变量： 参数x:9，变量y:3

局部变量： 参数x:18，变量y:4

经过之前的分析，我们知道程序运行的顺序，知道每一步输出的结果，也了解函数调用时建立栈帧的过程。程序运行的结果与我们的分析一致。
3.5.3SEAL中函数调用栈帧的建立
本书配套了一个笔者开发的汇编语言模拟器，称为SEAL（Simple Educational Assembly Language）。通过SEAL，读者可以撰写并执行本章所描述的汇编语言程序，并便于侦错除虫。从前言中介绍的出版社网站可以免费下载此工具，请读者根据所附的使用手册及范例程序进行学习。SEAL实现了24条“高级”汇编语言指令，同时模拟了容量为10000的内存及18个寄存器，其中包含16个64位通用寄存器R0~R15（可存储的数据大小为-263~263-1，支持十进制整型数和十六进制数）、1个PC寄存器和1个SP堆栈指针寄存器。
3.5.2节只简单描述了函数调用时栈的管理，还有一些细节需要读者进一步了解，尤其是在函数结束后FP如何返回主调函数的栈帧部位。本节将详细介绍SEAL中编写的函数调用是如何建立栈帧的。建立栈帧的过程叫作函数的连接（linkage）。SEAL所使用的linkage规则与x86基本一致（x86是工业界非常通用的CPU类型），读者可以由本节的学习了解到函数调用时关于栈帧建立的所有细节，这对奠定读者的计算机基础有莫大的助益。

接下来通过一个使用函数调用对两个数求和的示例来描述栈帧的建立过程。首先，给出使用函数调用对两个数求和的Python程序#<Python代码： 函数调用两个数求和>。



#<Python代码：函数调用两个数求和>

def add(a,b):

c = a + b

return c

if __name__=="__main__":

x = 5

y = 6

print(add(x,y))




在本例中，假设调用函数称为主函数，被调用函数称为子函数。在以上代码中，主函数调用add子函数对两个数求和。那么在主函数调用add()子函数时，CPU执行了哪些指令？函数的栈帧是如何一步步地建立起来的？下面先给出以上Python程序#<Python代码： 函数调用两个数求和>所对应的汇编程序#<汇编代码： 函数调用两个数求和>。



#<汇编代码：函数调用两个数求和>

mov R15,10000   #R15表示fp，fp = 10000

mov sp,R15      #sp = fp

sub sp,sp,2       #sp从10000开始向下开辟2个空间给局部变量x和y，sp = sp-2

mov R2,5        #x = 5

mov R3,6        #y = 6

store -1(R15),R3   #x

store -2(R15),R2   #y



push R3         #传参数b

push R2         #传参数a

call Ladd        #调用函数add(a,b), 返回值存储在R1中

goto Lprint



#add函数有两个参数a和b，将和放到R1中返回

Ladd:  #add(a,b)

push R15        #将旧的fp值压入栈内

mov R15,sp      #新的fp = sp

sub sp,sp,1       #留一个空间，用于存储局部变量c

push R2        #R2将在函数中被更改，故先存入栈内，在return之前会pop出来该值

push R3         #R3将在函数中被更改，故先存入栈内，在return之前会pop出来该值

load R2,2(R15)   #R2 = a

load R3,3(R15)   #R3 = b

add R1,R2,R3

store -1(R15),R1  #存储c



Lreturn:

pop R3           #pop出初始R3中的值

pop R2           #pop出初始R2中的值

mov sp,R15       #sp = fp

pop R15          #重置fp为旧的fp

ret



Lprint:

_pr R1




在函数调用中，需要用到栈操作指令push、pop及函数调用指令call、调用返回指令ret。在子函数开始执行前，需要在栈的顶部建立一个栈帧，SP指针指向栈帧的顶部，FP指针指向栈帧的底部（SP和FP是两个寄存器）。一个栈帧中保存了主函数所传的参数值、函数内的所有局部变量、函数返回的PC值（也就是主函数调用子函数后的下一条指令的位置），以及主函数的FP值。总而言之，一个函数在执行前必须要将该函数的FP与SP建立起来，这个过程也就是本节一开始提到的函数的连接（linkage）。
在SEAL中假设将R15作为FP，而SP是一个专用的寄存器。当然，也可以将其他寄存器作为FP，只要在编译函数时有一个统一的规则即可。SP的值可以用汇编指令add和sub来更改，也可以用push或pop指令进行加1或减1运算。当执行push R时，该指令将SP减1，然后将寄存器R的值存入SP所指的地址； 当执行pop R时，该指令会将SP所指地址的值load进寄存器R，然后将SP加1。假设主函数已经有一个栈帧，栈底是FP，栈顶是SP，如图328(a)所示。在主函数中有两个局部变量x和y，x的地址是-2(R15)，y的地址是-1(R15)，读者可以参阅主程序中关于x=5和y=6的汇编代码。
接下去主函数将调用子函数add(x,y)，下面详细描述函数调用时建立新栈帧的过程。
1. 参数的传递
将参数以反向的顺序push入栈中，所以先push y的值，再push x的值，如图328(b)所示。


图328执行call指令前栈的状态


2. 执行call指令
call指令会做两件事： 第一，将PC值push入栈，如图329(a)所示，这个PC值指向call Ladd的下一条指令，也就是子函数执行完后返回的地址； 第二，执行goto Ladd（即把PC值设成Ladd的地址）。
3. 函数起始的三条指令
这三条指令是所有函数开始时都会有的三条类似的指令： ①“push R15”,将主函数的FP值存入栈中； ②“mov R15, sp”，将新的FP指向SP的位置，即令FP指向此时栈的顶端，如图329(b)所示； ③“sub sp,sp,1”，将SP再上移，留出局部变量的空间，这里的add函数只有一个局部变量，所以只需要留一个位置，如果有n个局部变量，SP就要减n。执行这三条指令之后，栈的状态如图329(c)所示。


图329执行call指令之后栈的状态


4. add函数中的计算
一个函数的栈帧建立之后，FP会固定，SP会随着函数中的push、pop指令而更改，所以通常是用FP作为基准位置来得到参数或函数内的局部变量的地址。在add函数中参数a的地址是2(R15)，参数b的地址是3(R15)，局部变量c的地址是-1(R15)，请参阅汇编代码中的相关load、store语句。函数的结果用R1传回主函数。
5. 函数结束的三条指令
这三条指令会将栈帧返回主函数的栈帧状态： ①“mov sp,R15”，将SP下拉到FP所指的位置； ②“pop R15”，返回主函数的FP值； ③ret，相当于“pop pc”，也就是返回到主函数调用子函数的下一条指令。函数返回时栈的状态如图330所示。


图330函数返回时栈的状态




经验谈

(1) 主函数将参数值压入栈后，这些参数的位置就会被子函数作为变量来使用，如本例中子函数的参数a和b，其地址分别是2(R15)和3(R15)。所以，参数变量是属于子函数的局部变量。
(2)主函数是将参数的“值”传递给子函数，这种方式叫作“call by value”（值传递），是一种较为通用的参数传递方式，C语言就采用这种方式。当然，这个值也可以用来传递参数的地址，只不过子函数要进行相应的更改，就如同在C语言中传递一个指针，那么子函数中就是对指针做运算，这里不再额外说明。
(3) 函数的返回值一般用寄存器R1返回，假如有多个返回值，可以用多个寄存器返回，但是要事先约定好。

(4) 除了返回的寄存器R1之外，其他的寄存器应该在函数调用后保持与函数调用之前相同的值，所以在函数计算开始前，需要将函数中会被更改的寄存器值push到栈中保存，在return前再逐一pop回来。例如，函数add更改了寄存器R2和R3，所以在更改之




前先将R2、R3的值push入栈，在return前再pop返回原来的R2、R3的值，参见上述汇编代码。
(5) 返回主函数后，参数仍然留在栈中，主函数可以将参数pop出栈，但是需要付出消耗pop指令的代价，所以主函数常常“坐视不管”，让其留在栈中。但是对于递归函数，每次调用返回后必须将传递的参数pop出栈，否则后续的出栈操作可能会错位。




至此，函数调用时函数栈帧的建立过程介绍完毕。可以看到#<汇编代码： 函数调用两个数求和>中的最后一条指令“_pr R1”，这是为了将结果输出到控制台，在SEAL中添加并实现的一个打印指令，可以将希望输出的值打印出来。
介绍了使用函数调用对两数求和时函数栈帧的建立过程之后，相信大家对函数调用已经有了一个全面的了解。接下来使用一个更复杂的示例介绍函数栈帧的建立过程，继续介绍前一个示例中未涉及的一些细节并详细说明该示例中每条指令的执行过程。
先给出函数调用求三个数中最小值的Python程序#<Python代码： 三个数求最小值>和汇编程序#<汇编代码： 三个数求最小值>。



#<Python代码：三个数求最小值>

def get_min(x,y):

if x<=y:

return x

else:

return y

if __name__=="__main__":

a = 7

b = 18

c = 9

print(get_min(get_min(a,b),c))


#<汇编代码：三个数求最小值>

mov R15,300#R15表示fp，将基地址设置为300

mov sp,R15      #sp = fp

sub sp,sp,3       #sp从300开始向下开辟3个空间给局部变量a、b、c,sp = sp-3



mov R2,7        #a = 7 

mov R3,18       #b = 18

mov R4,9        #c = 9

store -1(R15),R4

store -2(R15),R3

store -3(R15),R2



push R3         #传参数b

push R2         #传参数a



call Lget_min    #调用函数get_min(a,b), 返回值存储在R1中



push R4        #传参数c

push R1        #传a和b中的较小值







call Lget_min   #再次调用get_min(R1,c), 返回值存储在R1中

goto Lprint   



#get_min函数有两个参数a和b，将最小值放到R1中返回

Lget_min:   #get_min(a,b)

push R15    #将旧的fp值存入栈内

mov R15,sp  #新的fp等于sp

#sub sp,sp,0  #由于此函数没有局部变量，所以可以去掉

push R2     #R2将在函数中被更改，所以先存入栈内，在return之前会pop出来

push R3     #R3将在函数中被更改，所以先存入栈内，在return之前会pop出来

push R4     #R4将在函数中被更改，所以先存入栈内，在return之前会pop出来

load R2, 2(R15)   #R2存放x的值

load R3, 3(R15)   #R3存放y的值

sle R4, R2, R3    #R4 = (R2<=R3)

beqz R4, L100    #if (R4 == 0) goto L100

mov R1,R2      #R1=R2，结果存储在R1中

goto Lreturn  



L100:

mov R1,R3      #R1=R3，结果存在R1中



Lreturn:

pop R4         #返回初始R4中的值

pop R3

pop R2

mov sp,R15     #sp = R15

pop R15       #重设R15的值为原有的R15

ret            #pop pc



Lprint:

_pr R1        #打印最后的结果





在本例中，主调函数要调用子函数get_min()找出三个数中的最小值，需要比较两次才可以求得，因此子函数要被调用两次。
同样，要先设置主函数的FP、SP且初始时SP与FP指向同一地址，本例中将初始的FP和SP设置为300。同时还需要为主函数的局部变量开辟足够的空间，本例中主函数有3个局部变量，所以需要开辟3个空间，使用sub指令对SP进行减3操作，于是SP指向开辟空间后的栈顶。将三个局部变量使用store指令按照从高到低的地址依次进行存储，此时栈的状态如图331(a)所示。
接着第一次调用get_min()子函数，子函数被调用前需要将前两个数作为参数传递给子函数，使用两条push指令进行参数的传递。这里所传参数为a和b，所以将a和b分别入栈，此时栈的状态如图331(b)所示。


传完参数之后执行指令“call Lget_min”，开始对get_min()函数进行调用。
执行call指令之后，依然需要进行两步操作，第一步是将返回地址PC值压入栈中，第二步是跳转到子函数开始执行，此时栈的状态如图332(a)所示。在子函数开始时，依然需要进行三步操作： ①将主函数栈帧的FP存储起来； ②将SP的值赋给FP，作为子函数栈帧的FP； ③假设子函数的局部变量需要n个空间，则将SP上移n个位置。


图331执行call指令前栈的状态


先将主函数的FP压入栈中，此时栈的状态如图332(b)所示； 再将SP的值赋给FP，即将FP上移到SP所指的位置，此时栈的状态如图332(c)所示； 在本例中子函数没有局部变量，所以SP不需要上移进行空间预留，因此栈的状态保持不变。


图332执行call指令后栈的状态



紧接着执行三条push指令，分别将R2、R3、R4压入栈中，以确保数据的干净与安全，此时栈的状态如图333所示。参数x的地址是2(R15)，参数y的地址是3(R15)，比较后较小的值由R1返回。
接下来将要返回时需要执行三条指令。指令“mov sp, R15”把FP值赋给SP，即令SP下移，如图334(a)所示； 指令“pop R15”返回主函数的FP值，如图334(b)所示； 指令ret相当于“pop pc”，也就是返回到主函数调用子函数的下一条指令，在本例中是第二次调用子函数时进行传参的指令，如图334(c)所示。
这里假设主函数不将原来的两个参数a和 b弹出，这样并不会影响程序的正确性。接下来将两个新的参数c和R1依次压入栈中，如图335所示，然后再执行“call Lget_min”，栈帧的建立方式如前所述，这里不再赘述。最后得到的最小值由R1返回。


图333push需要保护的寄存器的值




图334函数返回时栈的状态





图335第二次函数调用传参后栈的状态



经验谈

由本例可知，只要遵循函数连接的标准规则，一个函数可以被多次调用而依旧能正确地执行。同学们也可以尝试如何依次建立和返回递归函数的栈帧。但是需要注意，在程序执行前，栈中要保留足够的空间，使得每个函数在调用时能够有足够的空间来建立它的栈帧，尤其对于递归函数而言，栈空间的大小更为重要。




练习题3.5.1： 将<程序： 因数分解>中的break改为return，factors(18)会输出什么结果？用Python运行试试看。
练习题3.5.2： 将<程序： 因数分解>中的if块改写成如下程序，factors(18)的输出结果是什么？用Python运行试试看。



if (x %i ==0):

print("Factor:",i)

x=x//i

factors(x)

break




练习题3.5.3： 请阅读SEAL模拟器的使用文档，练习其中的范例。
练习题3.5.4： 请描述建立函数栈帧时一开始的三个指令的功能分别是什么。
练习题3.5.5： 假设main函数调用子函数f，子函数f结束后需要返回main函数，请问SP和FP如何变化才能实现返回主调用函数的栈帧？
练习题3.5.6： 请参照SEAL的函数调用、栈帧建立方式，完成如下计算： 输入三个数值，返回中间大小的值。请实现函数median(a,b,c)，其中a、b、c是整数，返回的值存储在R1中。
练习题3.5.7： 按照SEAL的栈帧建立方式，函数内部的局部变量的地址是如何获得的？例如，函数f中有a、b、c三个局部变量，变量定义的顺序为a、b、c（即存储a的地址最小），请问a的地址在SEAL中是多少（用FP来描述）？
练习题3.5.8： 有递归函数f(n)=f(n-1)+n，f(0)=0。假设每次调用函数f时，会产生k字节的栈帧，现在主函数调用f(100)，请问在此计算过程中共产生多少字节的栈帧？

小结
本小节讨论计算机在执行函数调用时需要存储的信息(返回地址、局部变量)，以及如何用栈管理这些信息。通过解决这些问题，我们进一步清楚了执行函数调用的过程。
3.6几种通用的编程语言
语言是工具，是用来沟通的工具。沟通的内容重要，工具也是重要，否则无法准确地沟通内容。所谓“工欲善其事，必先利其器”。据了解现在人类社会有5000多种语言，和计算机相关的语言也非常多，有些是历久弥新，有些是老态龙钟，有些是渐渐消失，有些是异军突起，不一而足。计算机相关的语言可以分成通用型的语言和专用型的语言。专用型的语言是为了某种特殊用途而使用的语言。例如，在设计硬件时，现在工业界都会使用VHDL或Verilog这类语言，计算机专业学生将来上“数字逻辑电路”课程时会用到，也就是设计逻辑电路就如同编写程序般简单。在设计数据库时，最通用的是SQL语言。在设计网页时，HTML、JavaScript、PHP、ASP等语言常会使用。在设计并行程序给多核系统执行时，MPI、openMP等语言(或语言库)常被使用。而通用型的语言也是非常多，如C、C++、Java、Python、Ruby、Smalltalk、ObjectiveC、C#、Basic、Perl、Delphi、Ada、Lisp、ML、Fortran、COBOL等。
我们先来看一下TIOBE 2020年4月发布的编程语言排行榜（如表31所示）。


表31TIOBE编程语言排行榜



Apr 2020Apr 2019ChangeProgramming LanguageRatings/%

11Java16.73
22C16.72
34Python9.31
43C++6.78
56C#4.74
65Visual Basic4.72
77JavaScript2.38
89PHP2.37
98SQL2.17
1016R1.54
1119Swift1.52
1218Go1.36
1313Ruby1.25
1410Assembly language1.16
1522PL/SQL1.05
1614Perl0.97

TIOBE排行榜能显示当下最热门、使用最多的编程语言。在本节中，我们将简单介绍C、C++、Java这几种编程语言。


小明： 沙老师，我想谈谈英文这个语言。我是中国人，堂堂正正的中国人，我为什么要学英文？
沙老师： 你是中国人和你学不学英文有关系吗？大部分的现代知识都是用英文撰写的，我们学了英文这个工具，才能第一手地接触到这些知识。更现实的原因是这个世界越来越小了，你要与世界交流就必须要学好英文。我语重心长地说，你把中文和英文学好，你这一生前途光明。不要等你吃亏后，你才想到沙老师说的话。


每一种语言都有相应的编译器，只有在相应的编译器环境下，程序员才能编写相应的程序并运行。
程序是为了实现某一种功能。在本书中，我们介绍的程序功能都是最基本的测试效果，并不是这个编程语言的应用。实现输出“Hello,world!”的功能只是我们学习这门编程语言的基础，这类功能与真正的应用开发相差很远。同学们如果想深入某一种语言，还需要自己不断参与实际的应用开发，才能更好地理解这门语言的精髓。
1.    C语言
C语言于1972年由美国贝尔实验室的D.M.Ritchie开发成功。C语言最初只是作为编写UNIX操作系统的一种工具，只在贝尔实验室内部使用。经过后来的不断改进，功能更丰富，应用也更广泛。到20世纪80年代，C语言已经风靡全世界，大多数系统软件和许多应用软件都是用C语言编写的。
提到语言，必须要讲的一个概念就是结构化编程语言或叫作面向过程语言(Procedure Oriented Programming)和面向对象的编程语言(Object Oriented Programming)的区别。C语言就是典型的结构化编程语言，二者的区别需要我们认真学习了不同的语言之后，加以比较才能真正领会。通俗地讲，面向过程的编程侧重设计一步步的“过程”来解决一个事件； 而面向对象的编程侧重描述一个对象，且描述这个对象的代码可以被多次使用。
例如，我们要计算一个砖头的体积。在面向过程的C语言里面，我们就需要输入长、宽、高这三个数据，相乘之后输出来结果。这个计算乘积的函数与砖头的关联并不明显。在面向对象的编程中，我们可以定义一个变量形态叫作砖头“类”，这个砖头除了有长宽高这些数据外，还有计算体积(volumn())、表面积(surface())等的函数(这些函数叫作“方法”——Method)，这些函数是属于这个类的。在程序里可以方便地宣告任何变量为砖头类(例如变量x)，这个变量x叫作一个对象(Object)。这个变量x不仅代表了数据，同时也包含了所有和砖头相关的方法。我们要计算x的体积，就用x.volumn()来计算。这只是面向过程和面向对象编程中较小的一个差别，即封装的特征，还有面向对象编程中继承和多态这两个特征，也需要我们真正使用这种语言之后才能理解清楚。
最早的面向对象程序设计语言就是C++语言。C++是由AT&T公司贝尔实验室的Bjarne Stroustrup博士及其同事于20世纪80年代初在C语言的基础上开发成功的。C++保留了C语言原有的所有优点，增加了面向对象的机制。
当然，面向过程和面向对象并不是相互对立的，而是相互补充的。C++也可以用来进行面向过程的编程。例如在面向对象编程中，对象的方法需要使用面向过程的思想来编写。
【例38】最小的C程序，只执行一个标准输出。



#<程序： C中的输出>

#include<stdio.h>

void main(){

printf("%s","hello world.");

}




stdio.h头文件包含了C标准输入输出库函数相关的定义和声明，所有需要输入或输出的C程序都需要使用这个头文件。main是主函数，即程序的入口点，大括号“{…}”表示main的函数体。printf是标准输出函数，其参数分别表示输出格式和输出语句。“%s”表示将输出一个字符串，而“hello world.”是将要输出的字符串。
接下来我们看C语言如何实现这个简单Python程序： 



#<程序： Python数组连起来>

mx=［1,2,3］

my=［8,9］

print(mx+my)#输出是［1,2,3,8,9］




以下是C语言的实现。读者有个感觉就好，我们不加解释。

#include<stdio.h>

#include<malloc.h>

void main(){

int mx［3］={1,2,3};

int my［2］={8,9};

int i,j;

int * x = (int*)malloc(sizeof(int)*(3+2)); //动态产生一个新数组x,长度是5

for(i=0;i<3;i++){　　//i从0 到2

x［i］=mx［i］;

}

for(j=0;j<2;j++){	　　//i从0到1

x［i+j］=my［j］;

}

for(i=0;i<5;i++){	　　//i从0到4

printf("%d ",x［i］);

}

printf("＼n");

}

2.    C++
C++是目前使用最广泛的面向对象程序设计语言。实际上，C++同时支持面向过程的程序设计和面向对象的程序设计。如前所述，C到C++的演进是由Bjarne Stroustrup博士完成的。他在C语言的基础上增加了类的概念，包括类的访问属性、构造方法等。


小明： 沙老师，我还是想问问怎么学好英文。我真的很用功，我甚至背英文字典。你说我用不用功?
沙老师： 傻孩子！字典是用来查的，不是用来背的。看小说学英文是对的。背字典学英文？恰好背道而驰。我曾经写了一篇文章叫作《学好英文的秘诀》，在网上或许可以找到。这个秘诀就是“不要学”，通俗地讲就是不要用“逻辑”“思维”来学语言，要浑然天成，要自然。唯一的方法就是多读、多讲、多写。你们学编程语言也是如此，要多写！


C++提供两种定义类型的构造，即类和结构体。结构体的概念与C语言中的相似。C++与C语言的关系很密切，熟悉C语言的人也可以很快掌握C++。
【例39】最小的C++程序，只执行一个标准输出。



#<程序： C++中的输出>

#include  <iostream>

int main(){

std::cout<<"hello world.＼n";

}




这个函数实现输出“hello world.”到屏幕上。
程序的iostream提供了输入输出流设施，任何需要有输入或输出的C++程序都需要包含这个头文件。程序入口点则是int main()，main就是函数名，大括号“{…}”表示main的函数体。后花括号“}”就是程序结束处。std是“名空间”，cout是标准输出设备的名称，“<<”是操作命令，表示将其后的字符串输出到屏幕上。“std::cout”表示是开发环境提供的标准库中的cout，而不是程序员自己定义的cout。
以下是将两个数组连起来的C++程序。读者有个感觉就好，我们不加解释。

#include<iostream>

#include<vector> //vector 是C++已经有的类模板，比较好用，有点像Python的list

using namespace std;



int main(){

int mx［3］={1,2,3};

int my［2］={8,9};

vector<int>x(mx,mx+3);    //将mx复制到x 里面

for(int i=0;i<2;i++){

x.push_back(my［i］);    //将my依序压入x的末尾

}

for(vector<int>::iterator it=x.begin();it!=x.end();it++){  //将x从开始依次输出

cout<<*it<<" ";

}

cout<<endl;

return 0;

}

3.    Java语言
Java起源于20世纪90年代初。在Sun公司的Green项目中，项目小组成员使用C++开发系统时遇到了很多问题，另辟蹊径，开发了这个小型的计算机语言。相对于C++，这款语言提供了更好的简单性和可靠性。最初它被命名为Oak，即橡树。1995年，这款语言正式更名为Java。
Java是印度尼西亚爪哇岛的英文名称，因盛产咖啡而闻名。Java语言的标志就是一杯正冒着热气的咖啡，而且Java语言中的许多类库名称也与咖啡有关，如JavaBeans(咖啡豆)、NetBeans(网络豆)、ObjectBeans(对象豆)等。
对于Java，我们需要知道它有3个开发平台，即JavaSE(Java2 Platform Standard Edition,Java平台标准版)、JavaEE(Java2 Platform Enterprise Edition,Java平台企业版)、JavaME(Java2 Platform Micro Edition,Java平台微型版)。开发平台，可以简单地理解为开发应用软件时使用到的一系列的工具(所说的工具涉及接口、库等概念，暂时不做详细介绍)。这三种应用平台针对不同的开发需求，如JavaME主要是为在移动设备和嵌入式设备(如手机、电视机顶盒和打印机)上运行的应用程序提供一个健壮、灵活的环境。
关于开发环境Eclipse、Myeclipse，以及Java Web应用的Web服务器——Tomcat等，在此也不做详细介绍。但是我们要知道，Java语言既可以编写应用程序(即在自己的计算机上独立运行，像C语言一样)，也可以编写小程序(Applet)，存储在服务器上并由浏览器运行，即Web开发。
不同于C++语言，Java是纯面向对象的，程序都是由类组成的。
【例310】最小的Java程序，只执行一个标准输出。



#<程序： Java中的输出>

public class doOut{

Public static void main(String［］ args){

System.out.println("hello world.");

}

}




System.out.println是标准输出函数，且输出语句后换行。输出语句中不限制输出格式，Java对于所有的输出都作为一个字符串来原样输出。
接下来是Java实现数组连起来的程序。读者有个感觉就好，我们不加解释。

import java.util.Vector;

public class MergeClass{

public static void main(String［］ args){

int mx［］ = {1,2,3} ;

int my［］ = {8,9};

int len_y = my.length;

Vector x=new Vector();     //x 是个Vector对象(object)

for(int i = 0;i<mx.length;i++){

x.add(mx［i］);      // 加入(append)mx的值到x

}

for(int i = 0;i<my.length;i++){

x.add(my［i］);　　// 加入(append)my的值到x

}

for(int index=0;index<x.size();index++){

System.out.print(x.elementAt(index)+" ");

}

System.out.print("＼n");

}

}

小结
本小节，我们介绍了C、C++、Java语言的起源、特点等。程序语言的学习过程是相通的，学习了一门语言之后，再学习其他语言就变得非常容易。每一门语言都有其独到之处。同学们在今后的实际演练中，会更加深刻地意识到，其实并不存在所谓的“最好的程序语言”。
3.7对计算机程序的领悟
程序的英文是Program，程序语言是Programming Language，而算法的英文是Algorithms。语言、程序和算法是三位一体的。语言是工具，算法是解题的想法，而程序是用某种语言来实现算法的技术。本章主要是谈程序和计算机语言。计算机有了计算机语言以后，才有了程序，才有了多彩多姿的生命，就像是人类有了语言和文字后才有了蓬勃的文明发展。人类的语言文字在描述如何解决问题时，是不清楚的，是有缺陷的。程序是人类文明中第一次有方法能清楚地描述解决问题的步骤，这是个伟大的进步。
在第5章我们会有一个有趣的例子讲如何解决走迷宫的问题。一个复杂的迷宫，可以想象是由n×n的方格所组成，有些方格是面墙，有些方格是通路，如何让你朋友从起点走到终点？你和你朋友都不知道迷宫内的组合情形，你的朋友只有走进去后，依照当时的情形来决定如何走下去。请问你要如何向你的朋友来描述他应该依循的解决方案，使得他能遵循你的方案来走过任何复杂的迷宫？大家当作一个练习题试试看，是不是用人类语言很难去描述你们心中的解法？但是计算机语言就清楚了，例如第5章用Python语言来解迷宫问题，短短的一段程序就能清楚无误地描述应该遵循的方法，你的朋友只要遵循Python程序描述的方法，他就能走过任何复杂的迷宫。
程序和计算机语言具备了清晰的语义、严谨的逻辑、巧妙的结构，这是本节所要谈的领悟。另外，我们谈谈智能和程序的关系。人工智能的英文为artificial intelligence，也就是人所造的智能。大家不要把智能看得太神秘了。有一个电视节目叫作“最强大脑”，展示出人类似乎匪夷所思的智能来，例如念给你100个任意数字，你先按从头到尾的顺序念出来，再从尾到头地念出来，我不相信你能做得到，太难了！又如给你两面墙，第一面墙是1000个魔术方块所拼构而成的，第二面墙是第一面墙的翻版，除了有一个魔术方块是不一样的，其他的方块都完全一样，请你在10分钟内找到这个不一样的魔术方块。你行吗？(你认为计算机要用多久找到这个不同的方块，1秒内吧！)再举一个例子，在国际象棋和围棋的比赛中，计算机的表现已经超过人类最顶尖的棋手了。这些智能不神秘，都是程序所表现出来的智能。人工智能就是程序所计算出来的罢了。本节用一个例子来展现“智能”不过就是程序计算出来的罢了！
3.7.1清晰的语义
首先，计算机语言必须要非常清晰明了。我们在生活中互相交流、传达信息，需要借助语言，但是生活中的语言往往表达得不够准确。比如当有人问路时，我们可能会说： “超市再往前走一段路，一会儿就到了。”这里的“一段”和“一会儿”所传达出的信息就不够明确，可能是1分钟的路程，也可能是5分钟的路程。英文中也存在语言描述模糊的现象。英文的slim表示“瘦”，fat表示“胖”。按照我们的思维习惯，会认为slim chance是“机会小”的意思，而fat chance是“机会大”的意思。但事实上，slim chance和fat chance意思完全相同，都表示“机会小”。同样地，我们与计算机通信，也需要有计算机语言。但是，计算机可不像我们人脑一样灵活。为了能够清楚地将我们的意思传达给它，同时从它那里得到正确的反馈信息，计算机语言不能是模棱两可的，更不能具有歧义，必须清晰准确。因此，在计算机语言中，我们的思想是用清楚的、无二义性的方式来描述的。这种清晰明了的语言形式，使得计算机语言有一种不同于其他语言的明了之美。有些人会问，清楚明了有什么美的？在男女朋友交往时，如果一方说话也像计算机语言一样明确清晰，也许很多时候另外一方就不会这么苦恼了。
3.7.2严谨的逻辑
除了语义清晰，计算机语言具有严谨但不乏灵活的逻辑之美。众所周知，数学的逻辑非常严谨。计算机语言的逻辑亦是如此，用计算机语言来解决问题时，我们的解题思路是非常清晰的，并且可以用完全逻辑性的形式语言来描述。因此，在解决某些问题时，计算机语言有很大的优势。比如将一串数字2、8、4、12、5按递增的方式进行排序，通用的数学模型只是讲“what”——什么是递增序列，而没有讲“how”——如何转变一个非递增序列为递增序列。与数学逻辑相比，计算机语言可以清楚地描述“how”。因为它有循环语句，有条件控制流程等。语言形式严谨，兼具结构组合灵活，这样的语言怎能不美！
3.7.3巧妙的结构
说完了计算机程序在语言风格和逻辑上的美，现在我们来看看它在结构上的美。计算机程序在结构上有一个非常有趣的特点，那就是采用了函数的调用，这使得计算机程序具有一种精巧的美。如第2章所言，简单的开关构建了复杂的计算机硬件系统。同理，一个复杂的软件也是由许多简单的函数一层一层调用而形成的，层次结构非常清晰。比如网络系统以及Linux、Windows等操作系统皆是如此。
一个大系统中，一个程序可能有上百万行代码、上万个函数调用，是上千人合作数年完成的。如果仅仅因为一个人改一个函数中的一行代码，难道就要牵一发而动全身，所有的函数都需要更改吗？
遇到这种问题时，函数调用的巧妙就发挥得淋漓尽致了。
计算机程序中，函数的实现千变万化。函数调用中，即使函数的实现改变了，只要函数的调用方式不变，调用它的程序就无须做任何改变。如图336所示，factors()函数调用sqrt(n)函数。在sqrt(n)函数中，即使其中的程序改变了，只要sqrt()还是正确的和对sqrt(n)的调用方式不变，我们完全可以按照原来的方式继续调用，factors()函数无须做任何改变。


图336函数调用示例

这种函数调用的结构，使得程序的主函数精巧、明了，使得程序的修改更加容易，程序的结构变得具有一种排列紧凑、疏密得当的美感。
一段程序其实也可以折射出人生的许多道理和启示。如果将程序比作人生，那么里面的每一个语句都是我们人生路上不可或缺的经历。那些看似简单的指令在CPU中有条不紊地一步一步执行，最后能够让计算机完成很多复杂的工作。由此可以看到，我们在做事的时候，不可以因为它简单而忽视它，应该脚踏实地地做好每一件事，一件一件的小事做好了，才能完成最终的目标。做人也是同样的道理，一步一个脚印，脚踏实地地走下去，才会守得云开见月明。
3.7.4智能是程序计算出来的
计算机被广泛应用于日常生活，我们可以用计算机搜索想要知道的信息，可以用计算机求解数学问题。那么计算机是怎么做到这些的呢？难道计算机也是有智能的，也可以像人一样思考吗？在没有学过计算机科学的人看来，计算机真是太可怕了，它能做很多人都做不来的事，将来会不会有一天就像很多美国科幻电影里演的，人类被计算机所取代？
下面我们通过一个简单的游戏来看看计算机的智能是什么样的。
这个游戏叫猜数字，由两个人都各自选定一个秘密的三位数(也可以是四位数或更多位数)，然后相互猜对方的数字。用几个A来表示对方猜的三位数中有几个数是完全正确的，用几个B来表示有几个数正确但是位置不对。对于重复的数字不可以重复计算，看谁先猜到对方的数字。
比如： 我选了一个秘密数字732。
对方猜: 057。
我回答: 0 A 1 B (1B是因为7在我的数字里，但是它的位置不对)。
对方猜: 582。
我回答: 1 A 0 B (A是因为2是完全正确的)。
对方猜: 563。
我回答: 0 A 1 B。
对方猜: 672。
我回答: 1 A 1 B。
对方猜: 732。
我回答: 3 A 0 B(答对了)。
游戏的规则如上面所述，有兴趣的同学可以做一下这个游戏，看看谁能先猜出来，能用几步猜出来。
可能有人会觉得这完全是靠运气嘛！其实不完全是靠运气，这里面可是有技巧的，仔细想想你是怎么猜的呢？
一个简单的方法如下。
首先随便猜数字，直到出现不是“0A0B”的时候，后面的数字就不完全是随便猜的了。比如猜“057”之后，对方回答“0A1B”，那么下面猜测的数字要和“057”是“0A1B”的关系，因为正确答案一定就在这些数字里。
“582”与“057”是“0A1B”的关系，猜测“582”之后，对方回答“1A0B”，下面猜测的数字要与“057”是“0A1B”的关系，而与“582”是“1A0B”的关系。
“563”与“057”是“0A1B”的关系，而与“582”是“1A0B”的关系。猜测“563”之后，对方回答“0A1B”。下面要猜的数字要与“057”和“563”是“0A1B”的关系，而与“582”是“1A0B”关系。
可以猜“672”，对方回答“1A1B”。然后找到与“057”和“563”是“0A1B”的关系，和“582”是“1A0B”关系，和“672”是“1A1B”的数字。进而找到“732”，得到3A0B。
上述方法就是一个能够解决猜数字问题的计算思维。那么怎么将它应用于计算机呢？根据上述计算思维，计算机对猜数字问题的“思维”如图337所示。


图337计算机解决猜数字问题的“思维”图


首先，计算机会将所有可能的三位数(000~999)全部列举出来。在这1000个三位数中，随机选择“057”进行猜测。
根据“057”给出的结果“0A1B”，对列举出来的000~999进行筛选。符合与“057”形成“0A1B”关系的数字被筛选出来，共有315个候选数字。从这些候选数字中，选择排在中间的数字“582”进行猜测。
根据“582”给出的结果“1A0B”，对上次的315个候选数字进行筛选。符合与“582”形成“1A0B”关系的数字被筛选出来，共有61个候选数字。继续从这些候选数字中，选择排在中间的数字“563”进行猜测。
根据“563”给出的结果“0A1B”，对上次的61个候选数字进行筛选。符合与“563”形成“1A0B”关系的数字被筛选出来。依次类推，直至猜到正确数字“732”为止。
应用上述的计算思维，计算机利用它强大的计算能力，能够在非常短的时间内得到正确的结果。
当然，另一方面，我们也应该谨记，我们是创造程序的人，千万不要变成CPU，变成机器人——只是根据指示做事。要多思考，有创新意识，做一个有思想的人。别忘了，计算机程序是我们所写出来的。
其实，智能还是神秘难测的，或许应该叫作智慧吧。深层的智慧有哲学层面的意义。我们前面所讲的智能是计算机程序能展现出的“人工智能”。那么是否还有人工智能外的智慧呢？也就是计算机无法展现出来的智慧呢？科学家可以证明计算机不能解决所有的问题(或计算机不能证明出所有的定理)，有些问题是计算机解决不了的，例如Halting Problem(停机问题)。这个问题是输入一个程序，假如这个程序被断定总是能停止就输出yes，假如被断定有可能永不停止就输出no。科学家证明世界上没有任何程序能100%解决这个问题。其实这个证明很短，通过构筑自相矛盾的递归来证明，几句话罢了(第10章会给出完整的证明过程)，然而在哲学层面上的意义是很深的。
在哲学层面的“智慧”是不一样的，例如佛教中的智慧被称为“般若”，和俗称的“智慧”有所区别。佛教中认为真正的般若智慧是离开文字、离开语言、离开分别、离开思维，甚至离开智慧，无可言说后的“所得”，然而所得也不可所得，一旦“有所得”后就不是般若了，所以也是“无所得”。所谓“色即是空，空即是色，色不异空，空不异色，无智亦无得，以无所得故”。大家看看就是，有个基本认识就好，知道程序所显现的人工智能和哲学层面上的智慧是有差异的。
练习题3.7.1： 拿牌游戏。假设面前有三堆扑克牌，其中每堆各有10张牌。两个人交替从某一堆中拿牌，谁拿到最后一张牌谁就输，请找出所有必赢的拿牌方式。
练习题3.7.2： 用Python实现猜数字游戏。在这个作业里不考虑有重复数字的3位数(例如335)。
小结
本节我们对计算机是否具有智能给出了解答。其实，计算机的智能是计算出来的。我们以猜数字的游戏为例，向大家展示了计算机的“思路”。这种“思路”其实是计算机程序的编写者赋予的。计算机应用人类赋予的计算思维和其强大的计算能力，可以又快又准确地解决很多问题。
习题3
习题3.1： 假设寄存器R1中存储的数值为10，执行完下面两条指令后，寄存器R2中存储的值是什么？

mov R2, R1

add R2, R2, 10

习题3.2： 假设寄存器R1中存储的数值为20，执行完下面两条指令后，主存地址800处存储的值是什么？

add R2, R1, 30

store (800), R2

习题3.3： 假设寄存器R1、R2中的值分别为10和15，执行完下面这段汇编指令后，寄存器R2中存储的值是什么？

slt R1, R2, R1

beqz R1,label0

mov R2, R1

label0:

add R2, R1, 10

习题3.4： 假设变量a、b、c分别读取到寄存器R1、R2、R3中，请写出下面这段程序对应的汇编指令。

if a<b

c=a+b

else

c=b

习题3.5： 在习题3.4中，修改程序的第一条语句为“if a<=b”，请写出修改后的程序对应的汇编指令。
习题3.6： 假设变量a、b、c分别读取到寄存器R1、R2、R3中，请写出下面这段程序对应的汇编指令。

if a<b

c=a+b

else

c=b

while c<10

c=c+10

习题3.7： 有如下汇编代码： 

mov R1,02h

将寄存器R1中的值左移1位后存入寄存器R2中

将寄存器R2中的值左移2位后存入寄存器R3中

add R4，R3，R2

(1) 根据旁边的注释，写出对应的汇编指令。
(2) 这4条指令执行结束后，各寄存器中的值为多少？
(3) 说明这段汇编代码完成的功能。
习题3.8： 假设变量a、b分别被读取到寄存器R1、R2中，请写出下面这段汇编指令完成了什么功能。

loop:

slt R4,R1,0Ah

beqz R4,label0

add R1,R1,R2

goto loop

label0:

add R2,R2,01h

习题3.9： 假设寄存器R1、R2中的值分别为20和30，执行完下面这段汇编指令后，主存中地址1000处存储的值是什么？

loop:

slt R4,R2, R1

beqz R4,label0

add R1, R1, 15

goto loop

label0:

store (1000), R1

习题3.10： 假设变量i、a、b分别读取到寄存器R1、R2、R3中，分析下面这段汇编指令。

loop:

slt R4,R1, 0Ah

beqz R4,label0

add R2, R2, R3

sub R3, R3, 01h

add R1, R1, 01h

goto loop

label0:

(1) 说明这段汇编指令执行的功能。
(2) 假设变量a和b的值分别为10和20，这段汇编指令执行完成后，寄存器R2、R3中的内容分别是多少？
习题3.11： 假设变量a、b分别存储在主存地址1000、1008处，现在要执行a右移b位的操作，并把结果存回地址1024处，写出相应的汇编指令。
习题3.12： 请写出下面程序中的局部变量、全局变量，并写出程序的运行结果。

a=10

b=30

deffunc():

 globala

 a=b

 print(a)

func()

print(a)

习题3.13： 在习题3.12的程序中，func()函数中去掉“global a”语句，程序的运行结果会有什么变化吗？
习题3.14： 请写出下面程序的运行结果。

a=10

b=30

deffunc():

 global a

 a=a+b

 return a

b=func()

print(a,b)

习题3.15： 将习题3.14的程序稍做修改，请写出下面程序的运行结果。

a=10

b=30

deffunc(a,b):

 a=a+b

 return a

b=func(a,b)

print(a,b)

习题3.16： 请写出下面程序输出的结果。

deffunc(b):

 a=b+10

 print(b)

 b=15

 print(a,b)

func(20)

习题3.17： 结合栈的特点，讲一讲在进行函数调用时，为什么要用栈来保存调用函数的信息？
习题3.18： 请写出下面递归函数的输出结果。

deffunc(a):

 if a==1:

 return 1

 return a*func(a-1)

b=func(5)

print(b)

习题3.19： 给定如下Python程序： 

defdo_sub(y):

 z=4

 z=y-z

 return z

x=do_sub(13)

(1) 画出调用do_sub()函数后的栈帧示意图。
(2) 画出返回后的栈帧示意图。
习题3.20： 给定如下Python程序： 

x=3

y=4

deffunc():

 globalx

 x=y

 z=x*y

func()

画出调用func()函数后的栈帧示意图。
习题3.21： 给定如下两个Python程序： 
(1)  
y=5

deffunc(z):

 globalx

 x=z-y

 print (x)

func(11)

(2)  
deffunc(z):

 y=5

 x=z-y

 print (x)

func(11)

(1) 以上两个程序分别会输出什么？
(2) 两个程序的栈帧中存储的数据相同吗？为什么？