計算機科學(xué)導(dǎo)論課件第3章-第三版VIP

引例a=a+1的執(zhí)行過程控制結(jié)構(gòu)的執(zhí)行關(guān)于python的函數(shù)調(diào)用函數(shù)調(diào)用過程的分析幾種通用的編程語言

1/TP

第3章程序是如何執(zhí)行的第1節(jié)引例

2計算機中有兩個核心部件，分別是CPU和“主存”。CPU是做運算的，主存存儲程序和相關(guān)的變量，每一條程序語句和每一個變量在內(nèi)存中都有相應(yīng)的內(nèi)存地址。a=a+1的意思是：將等號右邊的a+1計算出，然后將值賦予給等號左邊變量a。等號右邊的“a”是指變量a所存的值，而等號左邊的“a”是指變量的位置。第一、CPU先要讀程序，從地址300處讀取指令到CPU中，經(jīng)過CPU的分析，CPU知道接下來將要做的動作；第二、CPU會從地址1000處讀a里存的值；第三，CPU把這個值加1，第四，CPU將加1后的結(jié)果存回到地址1000的a處。第2節(jié)a=a+1的執(zhí)行過程

3分解“a=a+1”的執(zhí)行步驟CPU中的核心部件匯編指令的概念a=a+1的完整執(zhí)行過程分解“a=a+1”的執(zhí)行步驟

4主存存儲三條指令：讀取a到RR加1將R存回a寄存器是CPU內(nèi)的存儲單元，是有限存儲容量的高速存儲部件，每一種類的CPU的寄存器的個數(shù)和使用會有少許的不同。但是每一個CPU都會有通用寄存器來給程序使用的，編號R1~R32,代表有32個通用寄存器。在運算a=a+1時，首先要把變量a讀取到某一個寄存器R存儲，然后CPU再對寄存器R中的值進(jìn)行運算。運算完成之后，CPU才會將值存回主存?，F(xiàn)在很多CPU不能直接對內(nèi)存做運算，必須要先讀到寄存器里，然后在寄存器上做運算，運算完后，再把結(jié)果存回內(nèi)存里。分解“a=a+1”的執(zhí)行步驟

5第一步，CPU從地址300處讀取第一條語句，CPU執(zhí)行“讀取a到R”語句，就會從地址1000處讀取變量a的值到寄存器R中。第二步，CPU從地址301處讀取第二條語句，執(zhí)行“R加1”語句，CPU會對R執(zhí)行加1的操作。第三步，CPU再從地址302處讀取第三條語句，執(zhí)行“將R存回a”語句，就把寄存器R中變量a的值存回到主存中地址1000處。CPU中的核心部件

6語句地址的存儲——程序計數(shù)器PC(ProgramCounter)程序計數(shù)器PC是一個“特殊”寄存器部件。在計算機執(zhí)行程序時，PC始終指向主存中的某條指令語句(即該條語句在主存的地址)。CPU就是讀取（PC）所指向的那條指令來執(zhí)行。在順序執(zhí)行程序語句時，PC通過順序加“1”（對32位CPU，一個指令要占用4個字節(jié)，所以其實是加4；對64位CPU，是加8）自動指向下一條將要執(zhí)行的程序語句。對于一些控制結(jié)構(gòu)語句，如if,for,while等控制結(jié)構(gòu)，程序的執(zhí)行將會分叉，這時PC的值就不只是順序加1來指向下一條程序語句。CPU中的核心部件

7CPU中存儲程序語句——指令寄存器IR(InstructionRegister)指令寄存器IR也是個特殊寄存器，它是存放從主存中讀取的程序指令。CPU從主存中讀取程序指令到IR之后，由特定的部件來解讀這條程序指令，并執(zhí)行相應(yīng)的操作。執(zhí)行運算——算術(shù)邏輯單元ALU(arithmeticlogicunit)ALU是處理器中進(jìn)行真實運算的部件。執(zhí)行程序指令時，CPU把寄存器中的值輸入到ALU中，ALU做完運算后把結(jié)果存回寄存器。匯編指令的概念

8“讀取a到R”操作——load指令程序語句中的“讀取a到R”，表示CPU將變量a讀取到寄存器R中。我們設(shè)計指令“l(fā)oad”表示“讀取a到R”操作，那么load指令中需要有兩個“操作數(shù)”（operands），一個操作數(shù)是變量a的地址，另一個操作數(shù)是存儲的寄存器。匯編指令由“操作碼”和“操作數(shù)”組成。操作碼是指令執(zhí)行的基本動作。在loadR1,(address)指令中，load是操作碼，其后的寄存器R1和(address)都是操作數(shù)。操作碼的英文叫做operator,操作數(shù)的英文叫做operand。匯編指令的概念

9格式：loadR1,(address)

注：address是內(nèi)存地址，(address)表示這個地址內(nèi)存儲的值?！纠?】loadR1,(1000)該指令表示，將主存地址1000處的變量值讀取到寄存器R1中匯編指令的概念

10“R賦值”操作——mov指令程序語句中的“R賦值”，表示給寄存器R中賦一個值。我們設(shè)計指令“mov”表示“R賦值”操作，那么mov指令中需要有兩個操作數(shù)，一個操作數(shù)是賦給的值，另一個操作數(shù)是寄存器。格式1:movR1,constant注:mov指令有兩個操作數(shù)，前一個是寄存器，后一個是十六進(jìn)制的常數(shù)【例2】movR1,0Ah該指令執(zhí)行的操作，是將一個常數(shù)值0Ah(十進(jìn)制的10)賦給寄存器R1。格式2:movR2,R1注:mov指令有兩個寄存器操作數(shù)該指令執(zhí)行的操作，是將后一個寄存器R1中的值賦給寄存器R2中。匯編指令的概念

11“R加1”操作——add指令程序語句中的“R加1”，表示將寄存器R的值加1。我們設(shè)計指令“add”表示“R加1”操作，那么add指令中需要有三個操作數(shù)，一個操作數(shù)是與變量R相加的值，一個操作數(shù)是存儲變量R的寄存器，還有一個操作數(shù)是存儲運算結(jié)果的寄存器。匯編指令的概念

12格式1：addR2,R1,constant注:add指令有三個操作數(shù)，一個是常數(shù)，后一個是進(jìn)行運算的寄存器，前一個是存儲運算結(jié)果的寄存器。R2=R1+constand.

【例3】addR1,R1,01h該指令表示將寄存器R1中的數(shù)值加1，并將結(jié)果存回寄存器R2。如果寄存器R1中的值最初是06h，執(zhí)行該指令后，寄存器R1中的值就為07h。

格式2:：addR1,R1,R2注:add指令有三個寄存器操作數(shù)該指令執(zhí)行的操作，是將后兩個寄存器R1,R2中的值相加，結(jié)果賦給寄存器R1。也就是R1=R1+R2。匯編指令的概念

13減法指令sub：同add指令的格式一樣?！皊ubR2,R1，constant”，代表了R2=R1–constant。“subR3,R1,R2”代表了R3=R1-R2左移位指令shiftl，“shiftlR3,R1，05h”代表寄存器R1的二進(jìn)制數(shù)左移5位，移出的那5位填0。將最終值存入R3?！?5h’也可以用一個寄存器表示，例如，“shiftlR3,R1,R2”代表R1的二進(jìn)制值向左移（R2）位數(shù)，存入R3。左移指令就相當(dāng)于將R1做乘法。R1左移一位，R1值就相當(dāng)于乘2，R1左移2位，R1值就相當(dāng)于乘4。右移位指令shiftr，向右移位，移完后的那些最高位填0。匯編指令的概念

14“將R存回a”操作——store指令程序語句中的“存回”，表示CPU將寄存器R存回到主存中。我們設(shè)計指令“store”表示“存回R”操作，那么store指令中需要有兩個“操作數(shù)”，一個操作數(shù)是寄存器R，另一個操作數(shù)是要存回的地址a。格式:store(address),R1注：address是內(nèi)存地址，(address)表示要存回的地址，R1是寄存器。也就是(address)=R1?！纠?】store(500),R1該指令表示將寄存器R1中的值存回主存地址500處。a=a+1的完整執(zhí)行過程

15為了讓計算機執(zhí)行a=10,a=a+1程序語句，我們用幾條匯編指令來指示CPU的操作。先把a=10,a=a+1這兩條程序語句用相應(yīng)的匯編指令來表示，匯編指令的執(zhí)行步驟如下：程序開始執(zhí)行時，變量a存儲在主存地址1000處。a=10,a=a+1程序語句有五條匯編指令，從地址301處開始順序存儲每條指令。程序開始執(zhí)行時，PC指向匯編程序的首地址301處。a=a+1的完整執(zhí)行過程

16如右圖，CPU從地址301處開始執(zhí)行，PC值為301，CPU從地址301處讀取mov指令到IR，解讀并執(zhí)行mov指令，給寄存器R1中的變量a賦初值10，然后PC加1，指向下一條匯編指令。a=a+1的完整執(zhí)行過程

17如右圖，PC值為302，CPU從地址302處讀取store指令到IR，解讀并執(zhí)行store指令，將寄存器R1中變量a的值存回主存地址1000處，然后PC加1，指向下一條匯編指令。a=a+1的完整執(zhí)行過程

18如右圖，PC值為304，CPU從地址304處讀取add指令到IR，解讀并執(zhí)行add指令，將寄存器R1中變量a的值加1，并將結(jié)果再存回寄存器R1，然后PC加1，指向下一條匯編指令。第3節(jié)控制結(jié)構(gòu)的執(zhí)行

19if-else選擇語句分支跳轉(zhuǎn)指令if-else選擇語句的執(zhí)行while循環(huán)語句的執(zhí)行for循環(huán)語句的執(zhí)行

20if-else選擇語句不同的程序語言，定義了不同的if-else,for循環(huán)控制結(jié)構(gòu)的表達(dá)形式。但是if-else,for循環(huán)的執(zhí)行邏輯是不變的。如圖所示if-else的執(zhí)行邏輯是：先判斷if后面的表達(dá)式，如果表達(dá)式成立，則執(zhí)行語句塊A，否則就執(zhí)行語句塊B。if-else選擇語句，只選擇其中一個語句塊來執(zhí)行，之后執(zhí)行if-else結(jié)構(gòu)后面的語句塊。

21if-else選擇語句情況一，選擇順序執(zhí)行語句塊A，執(zhí)行完A的所有語句后“直接跳轉(zhuǎn)到語句塊C”；情況二，不執(zhí)行語句塊A，而是“選擇跳轉(zhuǎn)到語句塊B”，

執(zhí)行完B的所有語句后，順序執(zhí)行語句塊C。首先，我們需要比較x和y的大小，那么就有一條語句“比較x是否小于y”來告訴CPU應(yīng)該進(jìn)行判斷操作了。接下來，CPU應(yīng)該保存這個比較結(jié)果，根據(jù)比較結(jié)果，產(chǎn)生兩種執(zhí)行的情況。

22分支跳轉(zhuǎn)指令我們要新增幾條匯編指令，來指示CPU執(zhí)行的操作?！氨容^x是否小于y”，“選擇跳轉(zhuǎn)到語句塊B”操作，我們用相應(yīng)的匯編指令來表示。“比較x是否小于y”——slt指令指令“slt”來告訴CPU進(jìn)行比較操作，slt需要三個操作數(shù)，后兩個操作數(shù)依次是存儲變量x和變量y的寄存器，另一個寄存器用來保存比較結(jié)果

格式1：sltR4,R1,R2該指令執(zhí)行的操作，即比較寄存器R1中的數(shù)值是否小于R2中的數(shù)值，如果小于，則將寄存器R4置1，否則置0

23分支跳轉(zhuǎn)指令我們還希望slt能夠比較寄存器中的變量和一個數(shù)值的大小。那么slt的后兩個操作數(shù)分別是保存變量的寄存器，常數(shù)值，而另一個寄存器用來保存比較結(jié)果。格式2：sltR4,R1,constant該指令執(zhí)行的操作，即比較寄存器R1和常數(shù)值constant，如果R1中的數(shù)值小于constant，則寄存器R4置1，否則置0?！纠?】sltR4,R1,0Ah該指令表示，比較R1寄存器中的數(shù)值是否小于0Ah(即十進(jìn)制的10)，如果小于，則R4寄存器置1，否則置0

24分支跳轉(zhuǎn)指令判斷小于或等于指令sle指令和slt的格式完全一樣。例如“sleR4,R1，constant”。即比較寄存器R1和常數(shù)值constant，如果R1中的數(shù)值小于或等于constant，則寄存器R4置1，否則置0。

“選擇跳轉(zhuǎn)到語句塊”操作——beqz指令CPU已經(jīng)將比較的結(jié)果保存到寄存器，接下來，CPU根據(jù)寄存器中的值（0或1）來判斷執(zhí)行哪一個語句塊。指令“beqz”來查看寄存器中的值是否為0。如果為0，CPU將不再按順序執(zhí)行下一條語句，而是跳轉(zhuǎn)到另一個語句塊。對于將要跳轉(zhuǎn)到的語句塊，我們可以用一個“標(biāo)簽（label）”來標(biāo)記。beqz需要兩個操作數(shù)，前一個操作數(shù)是存儲比較結(jié)果的寄存器，另一個寄存器是一個標(biāo)簽。

25分支跳轉(zhuǎn)指令格式：beqzR4,label注：“標(biāo)簽”術(shù)語第一次在本書中提及，匯編程序中有些指令塊用標(biāo)簽label1,label2等標(biāo)記，執(zhí)行時就可以根據(jù)條件跳轉(zhuǎn)，或者直接跳轉(zhuǎn)到這些指令塊處執(zhí)行。beqz指令是根據(jù)條件來跳轉(zhuǎn)的指令。它有兩個操作數(shù)，一個是保存比較結(jié)果寄存器，另一個是標(biāo)簽?！纠?】beqzR4,label2該指令表示，如果寄存器R4中的數(shù)值為零，則跳轉(zhuǎn)到標(biāo)簽label2標(biāo)記的指令塊處。

26分支跳轉(zhuǎn)指令“直接跳轉(zhuǎn)到語句塊”操作——goto指令格式：gotolabel格式：gotolabel注：beqz指令是根據(jù)條件來選擇是否跳轉(zhuǎn)，goto指令是告訴CPU進(jìn)行直接跳轉(zhuǎn)的指令。它只有一個操作數(shù)，即“標(biāo)簽”label。執(zhí)行操作：跳轉(zhuǎn)到標(biāo)簽label標(biāo)記的指令處例：“gotolabel3”，表示跳轉(zhuǎn)到標(biāo)簽label3標(biāo)記的指令處執(zhí)行

27if-else選擇語句的執(zhí)行在前個小節(jié)的if-else結(jié)構(gòu)中，我們用到兩個變量x和y在ifx<y中。假定已經(jīng)把x和y分別讀取到寄存器R1和R2中。用匯編指令表示CPU在執(zhí)行if-else選擇語句時的操作，如圖所示

首先，slt指令比較x和y的大小，如果x小于y，則寄存器R4置1，否則置0；之后，beqz指令判斷R4的值，根據(jù)R4是否為0，有兩種執(zhí)行情況

28if-else選擇語句的執(zhí)行其一，R4為1，即x小于y，則順序執(zhí)行語句塊A，也就是程序中”if”之后的語句。執(zhí)行完語句塊A的所有語句后，會執(zhí)行g(shù)oto指令，直接跳轉(zhuǎn)到語句塊C，如圖中虛線(2)所示。其二，R4為0，即x不小于y，則跳轉(zhuǎn)到語句塊B執(zhí)行，也就是程序中”else”之后的語句，如圖中虛線(1)所示。執(zhí)行完語句塊B中的所有語句后，順序執(zhí)行語句塊C，如圖中虛線(3)所示。if-else選擇語句的執(zhí)行

29假定，if-else選擇語句翻譯后的匯編指令從地址304處開始存儲在主存，所使用到的變量x和y已經(jīng)從主存地址1000、1001處分別讀取到寄存器R1和R2中。如圖，執(zhí)行slt指令，CPU先將slt指令讀取到指令寄存器IR，進(jìn)行解讀。之后CPU將寄存器R1和寄存器R2中的數(shù)值轉(zhuǎn)移到ALU中。對于比較運算，ALU通過對兩個數(shù)值做減法來判斷。最終將比較的結(jié)果存回到寄存器R4中。PC加1，指向下一條指令beqz。if-else選擇語句的執(zhí)行

30如圖，執(zhí)行beqz指令，CPU先將beqz指令讀取到指令寄存器IR，進(jìn)行解讀。之后CPU判斷寄存器R4的值。變量x和y有兩種大小關(guān)系，若x不小于y（x>=y），CPU將按照下面的步驟5和步驟6執(zhí)行。否則，按照步驟7，8，9執(zhí)行。當(dāng)x>=y則R4中值為0，則跳轉(zhuǎn)到label0處執(zhí)行。如圖3.12中虛線(2)所示，PC值變?yōu)?01，指向label0處，即語句塊B的第一條語句。執(zhí)行完語句塊B中的所有語句后，結(jié)束if-else選擇語句。此后PC值為500，順序執(zhí)行語句塊C。當(dāng)x<y時，R4是1，執(zhí)行beqz指令，不跳轉(zhuǎn)到label0處執(zhí)行，而是順序執(zhí)行語句塊A的第一條語句。這時PC的值為306，指向語句塊A的第一條語句。x>y，則順序執(zhí)行完語句塊A中的所有語句后，PC值為400，指向goto指令。if-else選擇語句的執(zhí)行

31如上圖，CPU執(zhí)行g(shù)oto指令，跳轉(zhuǎn)到label1。如圖中虛線(2)所示，PC值變?yōu)?00，直接執(zhí)行語句塊C，結(jié)束if-else選擇語句。while循環(huán)語句的執(zhí)行

32while選擇語句根據(jù)表達(dá)式的真與假來選擇其中一個語句塊執(zhí)行。我們需要計算機循環(huán)執(zhí)行某一個語句塊，而循環(huán)都需要有一個終止條件，那么，我們也可以根據(jù)表達(dá)式的真與假，來決定是否終止。如果表達(dá)式的值為假，我們就終止執(zhí)行，否則繼續(xù)重復(fù)執(zhí)行。

33while循環(huán)語句的執(zhí)行比較變量x和y的大小，如果x小于y，則執(zhí)行語句塊A，否則執(zhí)行語句塊B重復(fù)判斷變量x是否小于y，如果小于，則重復(fù)執(zhí)行語句塊A。直到變量x不再小于y，此時不執(zhí)行語句塊A，而是結(jié)束while循環(huán)，執(zhí)行語句塊B。

34while循環(huán)語句的執(zhí)行CPU執(zhí)行slt指令，比較寄存器中的變量x和y的大小，并將比較結(jié)果保存到寄存器R4中。如果x小于y，則R4置1，否則置0。CPU執(zhí)行beqz指令，如果R4中值為0（就是R1不小于R2），就跳轉(zhuǎn)，到第五步。否則，R4=1（即R1小于R2），則不跳轉(zhuǎn)，順序執(zhí)行第3步。CPU順序執(zhí)行下一條語句，也就是語句塊A中的第一條語句，并順序執(zhí)行完語句塊A中的所有語句。CPU執(zhí)行g(shù)oto指令，執(zhí)行后的結(jié)果是跳轉(zhuǎn)到slt指令，如圖虛線(1)所示。即跳轉(zhuǎn)到第1步。結(jié)束while循環(huán)結(jié)構(gòu)。跳轉(zhuǎn)到label0處，執(zhí)行語句塊B，如圖虛線(2)所示。

35for循環(huán)語句的執(zhí)行不同的程序語言中，定義了不同的for循環(huán)語句形式，但for循環(huán)的執(zhí)行邏輯卻是大同小異。如圖為for循環(huán)語句的基本形式。通常，for循環(huán)語句會有一個變量i來控制循環(huán)次數(shù)，每執(zhí)行一次語句塊，變量i的值會做相應(yīng)的變化。假定需要循環(huán)執(zhí)行10次，變量i取初值0，執(zhí)行語句塊A。之后變量i取值1，執(zhí)行語句塊A。接下來變量i取值2，重復(fù)執(zhí)行語句塊A，直到變量i的值不再小于10，就不再重復(fù)執(zhí)行語句塊A，而是終止for循環(huán)，即執(zhí)行語句塊B。

36for循環(huán)語句的執(zhí)行第一步，我們有一個變量i來記錄循環(huán)次數(shù)，先決定一個寄存器來代表i。第二步，給變量i賦一個初值。第三步，比較變量i是否小于設(shè)定的常數(shù)，如果小于，則執(zhí)行第四步，否則跳轉(zhuǎn)到第五步。第四步，執(zhí)行語句塊A。然后變量i加1，之后直接跳轉(zhuǎn)到第三步。第五步，結(jié)束for循環(huán)。執(zhí)行語句塊B。

37for循環(huán)語句的執(zhí)行CPU執(zhí)行slt指令，比較寄存器R1中的變量i和10的大小，并將比較結(jié)果保存到寄存器R4。如果i小于10，則R4置1，否則置0；CPU執(zhí)行beqz指令，如果寄存器R4中值為1，則順序執(zhí)行第3步，否則跳轉(zhuǎn)到label0，如圖虛線(2)所示；CPU執(zhí)行語句塊A的第一條指令。之后，CPU順序執(zhí)行完語句塊A的所有語句；CPU執(zhí)行add指令，給寄存器R1中的變量i加1；CPU執(zhí)行g(shù)oto指令，執(zhí)行后的結(jié)果是跳轉(zhuǎn)到slt指令，如圖虛線(1)所示。即跳轉(zhuǎn)到第1步。

38for循環(huán)語句的執(zhí)行其實，for循環(huán)的執(zhí)行過程和while循環(huán)很相似。在圖3.15中，while循環(huán)的語句塊A中通常也有一條語句來更改循環(huán)變量x的值，否則變量x一直保持初值，就一直小于10，那么就會一直執(zhí)行語句塊A，這就是常說的“死循環(huán)”。在Python中，for循環(huán)和while循環(huán)里面可以出現(xiàn)“break”語句，只要碰到break語句，循環(huán)就馬上跳出去。后面還可以跟著“else”語句，假如跳出循環(huán)的原因是因為碰到了break而跳出的話，循環(huán)后的else就不會執(zhí)行；假如是正常離開循環(huán)的話，else后面的程序塊就會執(zhí)行。第4節(jié)關(guān)于python的函數(shù)調(diào)用

39函數(shù)的基本概念Python函數(shù)入門局部變量(Localvariables)與全局變量(Globalvariables)

40函數(shù)的基本概念程序語言中的函數(shù)和數(shù)學(xué)中的函數(shù)的基本概念是相似的。程序語言中的函數(shù)也有參數(shù)，和返回值，以及定義與調(diào)用。程序中的函數(shù)，就是將一些程序語句結(jié)合在一起的部件，通過多次調(diào)用，函數(shù)可以不止一次地在程序中運行。程序調(diào)用的好處第一、將大問題分成許多小問題。函數(shù)可以將程序分成多個子程序段，程序員可以獨立編寫各個子程序，實現(xiàn)了程序開發(fā)流程的分解。每個函數(shù)實現(xiàn)特定的功能，我們可以針對這個函數(shù)來撰寫程序第二、便于檢測錯誤。一個函數(shù)寫好之后，我們會驗證其實現(xiàn)的正確性。程序是由多個函數(shù)組成的。我們確定了每一個函數(shù)是正確后，總程序出錯的可能性，就會降低。另外函數(shù)的代碼量小，也便于檢測錯誤。

41函數(shù)的基本概念第三、實現(xiàn)“封裝”和“重用”。封裝的意思是隱蔽細(xì)節(jié)。例如函數(shù)GCD(x,y)是返回x和y的最大公約數(shù)。“封裝”的特點體現(xiàn)在，對于各個求兩數(shù)的最大公約數(shù)GCD的操作，都只需要傳遞兩個參數(shù)x和y給函數(shù)GCD，函數(shù)GCD會返回相應(yīng)的結(jié)果，而不必關(guān)注GCD操作的具體實現(xiàn)?！爸赜谩钡奶攸c體現(xiàn)在，各個程序都可以直接調(diào)用已經(jīng)寫好的GCD函數(shù)來實現(xiàn)最大公約數(shù)的計算，而不用重復(fù)編寫代碼。一個寫好的函數(shù)，可以被多次調(diào)用，這種“重用”提高了程序的開發(fā)效率。第四、便于維護(hù)。沒一個函數(shù)都必須要有清楚的界面和注釋，包含了功能、輸入的參數(shù)、返回值的解釋等。讓人知道怎樣調(diào)用這個函數(shù)。只要函數(shù)的界面不變，被調(diào)用函數(shù)的細(xì)節(jié)改變是不會影響全局的

42Python函數(shù)入門對于計算z+x×y2功能，數(shù)學(xué)中用函數(shù)表達(dá)：函數(shù)定義：f(x,y)=x×y2參數(shù)為x和y返回值是x×y2的結(jié)果調(diào)用方式為z+f(a,b)，a和b是分別傳遞給函數(shù)f的具體數(shù)值（1）Python函數(shù)表達(dá)：函數(shù)定義

deff(x,y):returnx*y*yPython函數(shù)的定義由關(guān)鍵字def開始，后面跟上函數(shù)名，和括號，括號里面是函數(shù)的參數(shù)，接著是冒號。最后就是函數(shù)體的內(nèi)容。Python函數(shù)定義的語法形式如下：def函數(shù)名(參數(shù)1,參數(shù)2,...):函數(shù)體

43Python函數(shù)入門（2）在上面定義的函數(shù)f中，參數(shù)也有兩個，即x和y，這些參數(shù)是函數(shù)f的“局部變量”。也就是他們的生命范圍只限制在這個函數(shù)中。（“局部變量”“全局變量”的相關(guān)概念，我們在后面會進(jìn)行更詳細(xì)的講解。）調(diào)用函數(shù)f時，會傳遞實際的值賦給函數(shù)f的參數(shù)。每一個函數(shù)中都可以有0個，1個，或更多個參數(shù)，相鄰參數(shù)之間用逗號隔開。形式如下：參數(shù)1,參數(shù)2,參數(shù)3,...（3）函數(shù)f中有一個關(guān)鍵字“return”，其后跟的值就是本函數(shù)將返回的值，即“返回值”。假設(shè)函數(shù)f0調(diào)用函數(shù)f，return語句是將被調(diào)用的函數(shù)f的計算結(jié)果返回給調(diào)用f的函數(shù)（f0）中的變量。return關(guān)鍵字后面可以是一個數(shù)值，也可以為一個表達(dá)式。在執(zhí)行return語句后函數(shù)結(jié)束。一個函數(shù)可能有多條return語句，執(zhí)行到第一條return語句時將結(jié)束函數(shù)。形式如下：return返回值或者表達(dá)式

44Python函數(shù)入門如果進(jìn)行調(diào)用的函數(shù)（f0）不需要被調(diào)函數(shù)（f）返回結(jié)果，那么被調(diào)函數(shù)就不需要return語句，即沒有返回值。當(dāng)然，python中的被調(diào)函數(shù)還可以返回多個值。（4）調(diào)用方式為c=f(a,b)。其中，a和b是傳遞給函數(shù)f的值。比如，在函數(shù)f0中有這樣一條語句”c=f(3,2)”，3和2就是函數(shù)f0傳遞給函數(shù)f的兩個參數(shù)，即在f函數(shù)中的局部變量x和y的值分別被設(shè)為為3和2。計算3×2×2的結(jié)果并返回，返回的值賦給函數(shù)f0的變量c。進(jìn)行函數(shù)調(diào)用時，函數(shù)f0稱為“主調(diào)函數(shù)”，而函數(shù)f稱為“被調(diào)用函數(shù)”。調(diào)用語句形式如下：主調(diào)函數(shù)中的變量=被調(diào)函數(shù)名(參數(shù)1,實數(shù)2,...)

#<程序：計算4+3*22>deff(x,y):returnx*y*y#主函數(shù)部分c=4+f(3,2)print(c)在計算4+3*2時，使用python函數(shù)的示例#<程序：計算4+3*22>。運行示例程序，將會輸出結(jié)果16

45局部變量與全局變量在函數(shù)中出現(xiàn)的變量，可以分為局部變量和全局變量。先記起來下面的規(guī)則：在函數(shù)中假如沒有g(shù)lobal語句，所有在等號左邊出現(xiàn)的變量以及參數(shù)都是“局部變量”，它只能被這個函數(shù)訪問，而不能被其它函數(shù)訪問。本書中的變量就是兩層，一層在函數(shù)內(nèi)，一層在函數(shù)外。在函數(shù)之外被賦值的變量是“全局變量”。我們把局部變量搞清楚后，自然那些在函數(shù)中出現(xiàn)的，不是局部變量的變量就是全局變量。局部變量與全局變量

46#<程序：打印局部變量a和全局變量a>a=10 #函數(shù)外deffunc():a=20#函數(shù)內(nèi)，局部變量的賦值，不會改變?nèi)肿兞?。print(a)#函數(shù)內(nèi)func()print(a)#函數(shù)外的a這里，func函數(shù)里面和外面的變量名是一樣的，都為a，但輸出結(jié)果卻是不同的。a=10語句中的變量a是函數(shù)外被賦值的變量，稱為這個文件的全局變量，而func()函數(shù)中a=20語句中的變量a，是在func()函數(shù)中被賦值的（在等號左邊），就是局部變量。外部的變量a和func()函數(shù)內(nèi)部的變量a是不同的變量，只是擁有相同的變量名而已。所以，前面的例子將會輸出20和10判斷函數(shù)內(nèi)部的變量a是否為局部變量的方法：1.不出現(xiàn)在global語句里面；2.出現(xiàn)在函數(shù)參數(shù)中，或者出現(xiàn)在函數(shù)語句的等號左邊。

47局部變量與全局變量如果在函數(shù)中使用global語句來聲明變量a，那么這個變量a就是全局變量a。如#<程序：關(guān)鍵字global引用全局變量>所示：global語句包含了關(guān)鍵字global，后面跟著一個或多個又逗號分開的變量名。在這個例子中，global語句后跟著變量a，表面后面使用的變量a是全局的。所以，func()函數(shù)中的a=20語句會修改全局變量a的值，程序會輸出20和20。#<程序：關(guān)鍵字global引用全局變量>a=10deffunc():globala#宣告這個是全局變量。a=20print(a)func()print(a)

48局部變量與全局變量在不使用global語句聲明某變量是全局時，如果這個變量出現(xiàn)在函數(shù)語句的等號左邊，那么它就是局部變量。#<程序：a,b,c是否為局部變量？>b,c=2,4defg_func(): a=b*c #a是局部變量d=a #d是局部變量，其他都是全局變量。print(a,d)g_func()print(b,c)>>>#輸出結(jié)果8824

49局部變量與全局變量這里的函數(shù)g_func中，變量a，d是局部變量，因為它們沒有被聲明為global。變量b和c是全局變量，盡管它們沒有被聲明為global，但是它們不是函數(shù)的參數(shù)，且只是出現(xiàn)函數(shù)中語句的等號右邊。#<程序：四則運算例子>defdo_div(a,b):c=a/b#a,b,c都是do_div()中的局部變量print(c)returncdefdo_mul(a,b):globalcc=a*b#a,b是do_mul()的局部變量，c是全局變量print(c)returncdefdo_sub(a,b):c=a-b #a,b,c都是do_sub()中的局部變量c=do_mul(c,c)c=do_div(c,2)print(c)returncdefdo_add(a,b): #參數(shù)a和b是do_add()中的局部變量globalcc=a+b #全局變量c，修改了c的值c=do_sub(c,1) #再次修改了全局變量c的值print(c)#所有函數(shù)外先執(zhí)行:a=3 #全局變量ab=2 #全局變量bc=1 #全局變量cdo_add(a,b)#全局變量a和b作為參數(shù)傳遞給do_add()print(c) #全局變量c

50局部變量與全局變量輸出的結(jié)果是16,8,8,8,8。這個程序的執(zhí)行過程如下：調(diào)用do_add()函數(shù)，將全局變量a和b傳遞給do_add()函數(shù)；do_add()中，聲明了全局變量c。全局變量c的值改為5。調(diào)用了do_sub()函數(shù)，將全局變量c和數(shù)字1傳遞給do_sub()，并將do_sub()的結(jié)果返回給全局變量c，即再次修改了c的值；do_sub()函數(shù)將參數(shù)a和b做減法，并將減法結(jié)果賦值給局部變量c，此時局部變量c的值為4。注意，此時全局變量c的值仍為5。調(diào)用了do_mul()函數(shù)，將局部變量c的值（為4）傳遞給do_mul()；do_mul()函數(shù)聲明了全局變量c，并將參數(shù)a和b相乘的結(jié)果賦值全局變量c，全局變量c的值變?yōu)?6。打印出本程序的第一個結(jié)果，即16。后將結(jié)果返回給do_sub()的局部變量c。也就是說，do_sub()里的局部變量c的值不再是4，而是16；

51局部變量與全局變量調(diào)用do_div()函數(shù)，并將局部變量c的值（為16）和數(shù)字2傳遞給do_div()。do_div()將參數(shù)a和b相除的結(jié)果賦值給局部變量c，局部變量c的值為8。注意，此時全局變量c的值仍為16。打印出本程序的第二個結(jié)果，即局部變量c的值8。后將局部變量c的值8返回給do_sub()的局部變量c；調(diào)用do_div()的過程結(jié)束，程序返回到do_sub()，打印出本程序的第三個結(jié)果，即do_sub()的局部變量c的值8；調(diào)用do_sub()的過程結(jié)束，并將do_sub()的局部變量c的值8返回到do_add()函數(shù)中，賦給全局變量c。打印出本程序的第四個結(jié)果，即全局變量c的值8；調(diào)用do_add()的過程結(jié)束，程序返回，打印出本程序的第5個結(jié)果，即全局變量c的值8。所以，程序最終輸出的結(jié)果依次為16,8,8,8,8第5節(jié)函數(shù)調(diào)用過程的分析

52返回地址的存儲函數(shù)調(diào)用時棧的管理棧

53棧是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，它按照先進(jìn)后出的原則存儲數(shù)據(jù)，即先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要取數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)。所以它的特色是“先進(jìn)后出”或“后進(jìn)先出”。棧的特別之處在于，我們只能從一端放數(shù)據(jù)和取數(shù)據(jù)，就像一個桶一樣，只能從桶口放東西和取東西。棧

54如上圖所示，（1）表示在棧中沒有數(shù)據(jù)，此時棧底和棧頂指向同一個位置；將數(shù)據(jù)1放入棧中，執(zhí)行壓入（push）操作，如（2）所示，1被放入棧中，棧頂向上移；將數(shù)據(jù)5放入棧中，執(zhí)行壓入（push）操作，如（3）所示，5被放入棧中，棧頂向上移。棧

55下面我們來看從棧中取數(shù)據(jù)的過程。如圖所示，初始狀態(tài)為（1），有3個數(shù)據(jù)存在棧中；執(zhí)行一次取數(shù)據(jù)（pop）操作，則在最頂上的數(shù)據(jù)8被彈出，得到數(shù)據(jù)8，此時棧中的情況如（2）所示；繼續(xù)執(zhí)行一次取數(shù)據(jù)（pop）操作，在最頂上的數(shù)據(jù)5被彈出，得到數(shù)據(jù)5，此時棧中的情況如（3）所示?？偨Y(jié)，棧的基本操作就是push和pop。返回地址的存儲

56執(zhí)行一條指令時，總是根據(jù)PC中存放的指令地址，將指令由內(nèi)存取到指令寄存器IR中。程序在執(zhí)行時按順序依次執(zhí)行每一條語句，即執(zhí)行完一條語句后，繼續(xù)執(zhí)行該語句的下一條語句。因此，PC每次都通過加1來指向下一條將要執(zhí)行的程序語句。但也有一些例外，遇到這些例外情況時，不按順序依次執(zhí)行程序中的語句。這些例外有：調(diào)用函數(shù)；函數(shù)調(diào)用后的返回；控制結(jié)構(gòu)，比如if、for、while等。返回地址的存儲

57主調(diào)函數(shù)是指調(diào)用其他函數(shù)的函數(shù)；被調(diào)函數(shù)是指被其他函數(shù)調(diào)用的函數(shù)。

一個函數(shù)很可能既調(diào)用別的函數(shù)，又被另外的函數(shù)調(diào)用。如圖所示的函數(shù)調(diào)用。fun0函數(shù)調(diào)用fun1函數(shù)，fun0函數(shù)就是主調(diào)函數(shù)，fun1函數(shù)就是被調(diào)函數(shù)。fun1函數(shù)又調(diào)用fun2函數(shù)，此時fun1函數(shù)就是主調(diào)函數(shù)，fun2函數(shù)就是被調(diào)函數(shù)。返回地址的存儲

58發(fā)生函數(shù)調(diào)用時，程序會跳轉(zhuǎn)到被調(diào)函數(shù)的第一條語句，然后按順序依次執(zhí)行被調(diào)函數(shù)中的語句。函數(shù)調(diào)用后返回時，程序會返回到主調(diào)函數(shù)中調(diào)用函數(shù)的語句的后一條語句繼續(xù)執(zhí)行。換句話說，也就是“從哪里離開，就回到哪里”。返回地址的存儲

59fun0函數(shù)從函數(shù)的第一條語句開始執(zhí)行，然后調(diào)用fun1函數(shù)，程序跳轉(zhuǎn)到fun1函數(shù)的第一條語句，順序執(zhí)行fun1函數(shù)中的語句；fun1函數(shù)調(diào)用fun2函數(shù)，程序跳轉(zhuǎn)到fun2函數(shù)的第一條語句，然后按順序執(zhí)行完fun2函數(shù)；fun2函數(shù)執(zhí)行完后，返回到fun1函數(shù)，繼續(xù)執(zhí)行fun1函數(shù)中“調(diào)用fun2函數(shù)語句”的下一條語句。在圖中我們將B標(biāo)示在該條語句旁邊，表示該條語句的地址為B。返回后按順序執(zhí)行fun1函數(shù)后面的語句；返回地址的存儲

60fun1函數(shù)調(diào)用fun3函數(shù)，程序跳轉(zhuǎn)到fun3函數(shù)的第一條語句，然后按順序執(zhí)行完fun3函數(shù)；fun3函數(shù)執(zhí)行完后，返回到fun1函數(shù)，繼續(xù)執(zhí)行fun1函數(shù)中“調(diào)用fun3函數(shù)語句”的下一條語句。在圖中我們將C標(biāo)示在該條語句旁邊，表示該條語句的地址為C。返回后按順序執(zhí)行fun1函數(shù)后面的語句；fun1函數(shù)執(zhí)行完后，返回到fun0函數(shù)，繼續(xù)執(zhí)行fun0函數(shù)中“調(diào)用fun1函數(shù)語句”的下一條語句。在圖中我們將A標(biāo)示在該條語句旁邊，表示該條語句的地址為A。返回后按順序執(zhí)行fun0函數(shù)后面的語句。執(zhí)行步驟與圖中(1)-(6)一一對應(yīng)。返回地址的存儲

61CPU執(zhí)行程序時，并不知道整個程序的執(zhí)行步驟是怎樣的，完全是“走一步，看一步”。前面我們提到過，CPU都是根據(jù)PC中存放的指令地址找到要執(zhí)行的語句。函數(shù)返回時，是“從哪里離開，就回到哪里”。但是當(dāng)函數(shù)要從被調(diào)函數(shù)中返回時，PC怎么知道調(diào)用時是從哪里離開的呢？答案就是——將函數(shù)的“返回地址”保存起來。因為在發(fā)生函數(shù)調(diào)用時的PC值是知道的。在主調(diào)函數(shù)中的函數(shù)調(diào)用的下一條語句的地址即為當(dāng)前PC值加1，也就是函數(shù)返回時需要的“返回地址”。我們只需將該返回地址保存起來，在被調(diào)函數(shù)執(zhí)行完成后，要返回主調(diào)函數(shù)中時，將返回地址送到PC。這樣，程序就可以往下繼續(xù)執(zhí)行了。返回地址的存儲

62函數(shù)調(diào)用的特點是：越早被調(diào)用的函數(shù)，越晚返回。比如fun1函數(shù)比fun2函數(shù)先被調(diào)用，fun1函數(shù)比fun2函數(shù)后返回；fun1函數(shù)比fun3函數(shù)先被調(diào)用，fun1函數(shù)比fun3函數(shù)后返回。這一特點剛好滿足“后進(jìn)先出”的要求，因此我們采用“?！眮肀４娣祷氐刂?。返回地址的存儲

63在圖3.20中，調(diào)用過程(1)發(fā)生時，需要壓入保存返回地址A，棧的狀態(tài)如圖3.21中(a)所示；調(diào)用過程(2)發(fā)生時，需要壓入保存返回地址B，棧的狀態(tài)如圖3.21中(b)所示；返回過程(3)發(fā)生時，需要彈出返回地址B，棧的狀態(tài)如圖3.21中(c)所示；調(diào)用過程過程(4)發(fā)生時，需要壓入保存返回地址C，棧的狀態(tài)如圖3.21中(d)所示；返回過程(5)發(fā)生時，需要彈出返回地址C，棧的狀態(tài)如圖3.21中(e)所示；返回過程(6)發(fā)生時，需要彈出返回地址A，此時棧被清空，圖中未畫出具體情況。函數(shù)調(diào)用時棧的管理

64在右圖的函數(shù)中，fun函數(shù)要調(diào)用do_add函數(shù)。fun函數(shù)里有變量a，a的值為10；在do_add函數(shù)里也有變量a，a的值為3。雖然這兩個函數(shù)中的變量a有相同的名字，但顯然兩個函數(shù)中a的值是不同的。fun函數(shù)里的變量a和do_add函數(shù)里的變量a是兩個不同的變量，即這兩個變量需要存放在不同的地方。函數(shù)調(diào)用時棧的管理

65局部變量a只在do_add函數(shù)內(nèi)才有意義；局部變量的存儲一定是和函數(shù)的開始與結(jié)束息息相關(guān)的。局部變量如同返回地址般也是存在棧里。當(dāng)函數(shù)開始執(zhí)行時，這個函數(shù)的局部變量在棧里被設(shè)立（壓入），當(dāng)函數(shù)結(jié)束時，這個函數(shù)的局部變量和返回地址都會被彈出。函數(shù)調(diào)用時棧的管理

66在調(diào)用有參數(shù)傳遞的函數(shù)時，變量c也是do_add函數(shù)里的局部變量，該局部變量由fun函數(shù)里的變量a來初始化。比如fun函數(shù)里變量a的值為10，當(dāng)調(diào)用do_add函數(shù)時，局部變量c就復(fù)制變量a的值10。因此，在do_add函數(shù)里局部變量c的初始值就為10。函數(shù)調(diào)用時棧的管理

67在do_add函數(shù)里，最后有一條返回語句：returnd。表明在執(zhí)行完do_add函數(shù)后，需要將局部變量d的值傳遞給主調(diào)函數(shù)fun函數(shù)的變量b。與參數(shù)傳遞同理，在傳遞返回值時，也是將局部變量d的值賦值給主調(diào)函數(shù)中的變量b。我們講過，局部變量只在函數(shù)內(nèi)有意義，離開函數(shù)后該局部變量就失效。比如do_add函數(shù)里的局部變量d，執(zhí)行do_add函數(shù)時d是有意義的。但執(zhí)行完do_add函數(shù)后，返回到fun函數(shù)中，do_add函數(shù)里的局部變量d就失效了。因此在彈出d時需要用一個寄存器將返回值d保存起來，所以在外面的調(diào)用函數(shù)可以來讀取這個值。函數(shù)調(diào)用時棧的管理

68局部變量是在函數(shù)執(zhí)行的時候才會存在。當(dāng)函數(shù)結(jié)束后，這些局部變量就不存在了。如前所述，局部變量的調(diào)用是和棧的操作模式“后進(jìn)先出”的形式是相同的。這就是為什么返回地址是壓入棧里，同樣的，局部變量也會壓到相對應(yīng)的棧里面。當(dāng)函數(shù)執(zhí)行時，這個函數(shù)的每一個局部變量就會在棧里有一個空間。在棧中存放此函數(shù)的局部變量和返回地址的這一塊區(qū)域叫做此函數(shù)的棧幀(frame)。當(dāng)此函數(shù)結(jié)束時，這一塊棧幀就會被彈出。函數(shù)調(diào)用時棧的管理

69調(diào)用do_add()函數(shù)前執(zhí)行的操作fun的局部變量a壓入棧中，其值為10；局部變量b壓入棧，由于b的值還未知，因此先為b預(yù)留出空間。調(diào)用do_add()函數(shù)時執(zhí)行的操作返回地址壓入棧中；局部變量c的值10壓入棧中。此處注意，c是do_add()函數(shù)中的局部變量，c的值是通過復(fù)制fun函數(shù)中的局部變量a的值得到的；壓入do_add()中的局部變量a，其值為3；執(zhí)行a+c，其中a=3，c=10，相加后得d的值為13。函數(shù)調(diào)用時棧的管理

70do_add()函數(shù)返回時執(zhí)行的操作do_add()函數(shù)執(zhí)行完后，依次彈出do_add()的局部變量，由于需要將d的值返回，因此在彈出d時需要用一個寄存器將返回值d保存起來；然后彈出返回地址，將返回地址傳到PC；返回到fun函數(shù)，fun中的局部變量b的值即為do_add()中的返回值d，此時將寄存器中的值賦值給b。函數(shù)調(diào)用時棧的管理

71在函數(shù)調(diào)用時，用一個寄存器將棧頂?shù)刂繁４嫫饋?，稱為棧頂指針SP。另外還有一個幀指針FP，用來指向棧中函數(shù)信息的底端。這樣，棧就被分成了一段一段的空間。每個棧幀對應(yīng)一次函數(shù)調(diào)用，在棧幀中存放了前面介紹的函數(shù)調(diào)用中的返回地址、局部變量值等。每次發(fā)生函數(shù)調(diào)用時，都會有一個棧幀被壓入棧的最頂端；調(diào)用返回后，相應(yīng)的棧幀便被彈出。當(dāng)前正在執(zhí)行的函數(shù)的棧幀總是處于棧的最頂端。函數(shù)調(diào)用時棧的管理

72首先在棧中將fun1函數(shù)的信息都存儲起來，SP與FP分別指向存儲fun1信息的棧空間的頂端和底端，如圖(1)；然后fun1函數(shù)調(diào)用fun2函數(shù)，在棧中將fun2函數(shù)的信息都存儲起來，存儲位置位于fun1函數(shù)的信息的頂部，SP與FP分別指向存儲fun2信息的?？臻g的頂端和底端，如圖(2)；fun2函數(shù)執(zhí)行完后，要返回到fun1函數(shù)中，fun2函數(shù)的信息被彈出，SP與FP分別指向存儲fun1信息的?？臻g的頂端和底端，如圖(3)；fun1函數(shù)又調(diào)用fun3函數(shù)，在棧中將fun3函數(shù)的信息都存儲起來，存儲位置位于fun1函數(shù)的信息的頂部，SP與FP分別指向存儲fun3信息的?？臻g的頂端和底端，如圖(4)；fun3函數(shù)和fun1函數(shù)執(zhí)行完后，也會分別返回，相應(yīng)的信息會從棧中彈出，棧的狀態(tài)未在圖中畫出。函數(shù)調(diào)用時棧的管理

73由于函數(shù)調(diào)用時，要不斷的將一些數(shù)據(jù)壓入棧中，SP的位置是不斷變化的，而FP的位置相對于局部變量的位置是確定的，因此函數(shù)的局部變量的地址一般通過幀指針FP來計算，而非棧指針SP。函數(shù)調(diào)用時棧的管理

74綜合前面所講到的知識，可以總結(jié)出：一個函數(shù)調(diào)用過程就是將數(shù)據(jù)（包括參數(shù)和返回值）和控制信息（返回地址等）從一個函數(shù)傳遞到另一個函數(shù)。在執(zhí)行被調(diào)函數(shù)的過程中，還要為被調(diào)函數(shù)的局部變量分配空間，在函數(shù)返回時釋放這些空間。這些工作都是由棧來完成的。所傳參數(shù)的地址可以簡單的從FP算出來。右圖展示了棧幀的通用結(jié)構(gòu)。函數(shù)調(diào)用時棧的管理

75為了使大家對函數(shù)調(diào)用時信息的存儲了解得更加清晰，下面通過右圖的遞歸函數(shù)的例子，將前面所講的需要存儲的信息綜合在一起，來研究函數(shù)調(diào)用時對棧的管理。函數(shù)調(diào)用時棧的管理

76pre函數(shù)調(diào)用fac(1)函數(shù)前執(zhí)行的操作pre的局部變量m壓入棧中，其值為1；局部變量f壓入棧，由于f的值還未知，因此先為f預(yù)留出空間。pre函數(shù)調(diào)用fac(1)函數(shù)時執(zhí)行的操作返回地址壓入棧中；fac(1)的局部變量n壓入棧中，其值為1；局部變量r壓入棧，由于r的值還未知，因此先為r預(yù)留出空間。函數(shù)調(diào)用時棧的管理

77fac(1)函數(shù)調(diào)用fac(0)時執(zhí)行的操作返回地址壓入棧中；fac(0)的局部變量n壓入棧中，其值為0；此時遞歸達(dá)到了終止條件（n==0），結(jié)束遞歸，局部變量r壓入棧，r值為1。函數(shù)調(diào)用時棧的管理

78fac(0)函數(shù)返回時執(zhí)行的操作fac(0)函數(shù)執(zhí)行完后，依次彈出fac(0)的局部變量。在彈出r時用一個寄存器將返回值r保存起來；彈出返回地址，將返回地址傳到PC；SP=FP，令SP指回fac(1)棧幀的頂部，令FP指回fac(1)棧幀的底部；繼續(xù)執(zhí)行函數(shù)fac(1)，fac(1)中的局部變量r的值即為fac(0)中的返回值乘以n。函數(shù)調(diào)用時棧的管理

79fac(1)函數(shù)返回時執(zhí)行的操作fac(1)函數(shù)執(zhí)行完后，依次彈出fac(1)的局部變量。在彈出r時用一個寄存器將返回值r保存起來；彈出返回地址，將返回地址傳到PC；SP=FP，令SP指回pre棧幀的頂部，令FP指回pre棧幀的底部；繼續(xù)執(zhí)行函數(shù)pre，pre中的局部變量f的值即為fac(1)中的返回值r，此時將寄存器中的值賦值給f。函數(shù)調(diào)用時棧的管理

80各類微處理器對函數(shù)調(diào)用的處理方式會有所差異，同一體系結(jié)構(gòu)中對不同語言的函數(shù)調(diào)用的處理方式也會有少許的差異。但通過棧存儲局部變量和返回地址等信息，這一點是共同的。我們不需要對函數(shù)調(diào)用中的每一個執(zhí)行的細(xì)節(jié)都了解清楚，大家只要對這個過程有一個初步的認(rèn)識：知道每一次函數(shù)調(diào)用對應(yīng)一個棧幀，棧幀中包含了返回地址、局部變量值等信息。還有一點要注意，在本書中所用的python語言屬于解釋性語言，python中發(fā)生函數(shù)調(diào)用時所建立的棧，不是編譯時建立的（像C語言等是在編譯時就建好了棧），是在有需要的時候再建立的。函數(shù)調(diào)用時棧的管理

81#<程序：因數(shù)分解>Printalltheprimefactors(>=2)ofx.ByEdwinShaimportmath #為了要調(diào)用平方根函數(shù)，此函數(shù)在math包里deffactors(x): #找到x的因數(shù)y=int(math.sqrt(x))foriinrange(2,y+1): #檢查從2到x的平方根是否為x的因數(shù)if(x%i==0):

#發(fā)現(xiàn)i是x的因數(shù)print("Factor:",i);factors(x//i) #遞歸調(diào)用自己，參數(shù)變小是x//ibreak #跳出for循環(huán)else:#假如離開循環(huán)正常，沒有碰到break，就執(zhí)行else內(nèi)的print，x是質(zhì)數(shù)print("PrimeFactor:",x)print("局部變量：參數(shù)x:%d,變量y:%d"%(x,y))return我們用以上的因數(shù)分解的python程序，來講解python程序運行時，棧的建立過程。這個例子是用遞歸的方式來調(diào)用函數(shù)。函數(shù)調(diào)用時棧的管理

82第一步，該程序從非函數(shù)定義的第一條語句開始執(zhí)行，即語句“factors(18)”開始執(zhí)行。首先建立一個main函數(shù)的棧幀，棧幀中保存的信息為main函數(shù)中的信息。如圖(1)所示。第二步，第一次調(diào)用函數(shù)factors(x)。先保存函數(shù)的返回地址。壓入局部變量x，值為18；壓入局部變量y，值為4（語句y=int(math.sqrt(x))表示：y的值等于x的值開平方根后取下整。事實上，調(diào)用math.sqrt(x)函數(shù)時也要建棧幀，大家知道即可，這里我們不詳細(xì)講解）；壓入局部變量i，值為2。此時程序執(zhí)行到if語句，if語句中的表達(dá)式值為真，因此會執(zhí)行print語句，由于局部變量i值為2，輸出“Factor：2”。棧的狀態(tài)如圖(2)所示。函數(shù)調(diào)用時棧的管理

83第三步，第二次調(diào)用函數(shù)factors(x)。先保存函數(shù)的返回地址。壓入局部變量x，值為9；壓入局部變量y，值為3；壓入局部變量i，值為2。由于if語句中的表達(dá)式值為假，i值會加1，變?yōu)?。此時if語句中的表達(dá)式值為真，因此會執(zhí)行print語句，由于局部變量i值為3，輸出“Factor：3”。棧的狀態(tài)如圖(3)所示。函數(shù)調(diào)用時棧的管理

84第四步，第三次調(diào)用函數(shù)factors(x)。先保存函數(shù)的返回地址。壓入局部變量x，值為3；壓入局部變量y，值為1。由于i值不能滿足大于等于2并且小于2，所以不執(zhí)行for循環(huán)，跳轉(zhuǎn)執(zhí)行else中的print語句，由于局部變量i值為3，所以輸出“PrimeFactor：3”。之后順序執(zhí)行下一條print語句，由于局部變量x值為3，y值為1，所以輸出“局部變量：參數(shù)x：3，變量y：1”。棧的狀態(tài)如圖(4)所示。函數(shù)調(diào)用時棧的管理

85第五步，程序順序執(zhí)行到return語句，彈出頂端的棧幀，返回到第二次調(diào)用函數(shù)factors(x)后的狀態(tài)。程序返回到語句factors(x//i)，順序執(zhí)行break語句，退出for循環(huán)。是由break跳出的所以不會執(zhí)行else中的print語句，由于局部變量x值為9，y值為3，所以輸出“局部變量：參數(shù)x：9，變量y：3”。棧的狀態(tài)如圖(5)所示。函數(shù)調(diào)用時棧的管理

86第六步，程序順序執(zhí)行到return語句，彈出頂端的棧幀，返回到第一次調(diào)用函數(shù)factors(x)后的狀態(tài)。程序返回到語句factors(x//i)，順序執(zhí)行break語句，退出for循環(huán)。是由break跳出的所以不會執(zhí)行else中的print語句，由于局部變量x值為18，y值為4，所以輸出“局部變量：參數(shù)x：18，變量y：4”。棧的狀態(tài)如圖(6)所示。第七步，程序順序執(zhí)行到return語句，彈出頂端的棧幀，返回到第一次調(diào)用函數(shù)factors(x)前的狀態(tài)。棧的狀態(tài)如圖(7)所示。程序返回到語句factors(18)。執(zhí)行完main函數(shù)后，彈出頂端的棧幀，此時?？眨▓D中未畫出）。函數(shù)調(diào)用時棧的管理

87在上述步驟中，第一步至第四步為函數(shù)的調(diào)用過程；第五步至第七步為函數(shù)的返回過程。程序運行的結(jié)果：Factor:2Factor:3PrimeFactor:3局部變量：參數(shù)x:3，變量y:1局部變量：參數(shù)x:9，變量y:3局部變量：參數(shù)x:18，變量y:4SEAL中函數(shù)調(diào)用時棧幀的建立

88

SEAL中函數(shù)調(diào)用時棧幀的建立

89我們通過一個使用函數(shù)調(diào)用對兩個數(shù)求和的示例進(jìn)行棧幀建立過程的描述。首先，給出使用函數(shù)調(diào)用對兩個數(shù)求和的python程序#<python代碼：函數(shù)調(diào)用兩個數(shù)求和>。#<python代碼：函數(shù)調(diào)用兩個數(shù)求和>defadd(a,b):c=a+breturncif__name__=="__main__":x=5y=6print(add(x,y))該示例中，我們假設(shè)調(diào)用函數(shù)稱作主函數(shù)，被調(diào)用函數(shù)稱作子函數(shù)。以上代碼中，主函數(shù)里會調(diào)用add子函數(shù)對兩個數(shù)求和。那么在主函數(shù)調(diào)用add子函數(shù)時，CPU是執(zhí)行了哪些指令，函數(shù)棧幀是如何一步步建立起來的？SEAL中函數(shù)調(diào)用時棧幀的建立

90現(xiàn)在我們先給出python程序#<python代碼：函數(shù)調(diào)用兩個數(shù)求和>所對應(yīng)的匯編程序#<匯編代碼：函數(shù)調(diào)用兩個數(shù)求和>。#<匯編代碼：函數(shù)調(diào)用兩個數(shù)求和>movR15,10000#R15表示fp，fp=10000movsp,R15#sp=fpsubsp,sp,2#sp從10000往下開辟2個空間給局部變量x，y，sp=sp-2movR2,5#x=5movR3,6#y=6store-1(R15),R3#xstore-2(R15),R2#y

pushR3#傳參數(shù)bpushR2#傳參數(shù)acallLadd#調(diào)用函數(shù)add(a,b),返回值存在R1中g(shù)otoLprint

#add函數(shù)有兩個參數(shù)a，b，將和放到R1中返回Ladd:#add(a,b)pushR15#將舊的fp值壓入棧內(nèi)movR15,sp#新的fp=spsubsp,sp,1#留一個空間，存放局部變量cpushR2#在函數(shù)中被更改，故先存入棧內(nèi)，在return之前會pop出來該值pushR3#在函數(shù)中被更改，故先存入棧內(nèi)，在return之前會pop出來該值loadR2,2(R15)#R2=aloadR3,3(R15)#R3=baddR1,R2,R3store-1(R15),R1#存放c

Lreturn:popR3#pop出初始R3中的值popR2#pop出初始R2中的值movsp,R15#sp=fppopR15#重置fp，成為舊的fpret

Lprint:_prR1SEAL中函數(shù)調(diào)用時棧幀的建立

91在函數(shù)調(diào)用中，需要用到對棧操作指令push、pop以及函數(shù)調(diào)用的指令call和返回的指令ret。在子函數(shù)開始執(zhí)行前，需要在棧的頂部建立一個棧幀(frame)，基本上，SP指針指向棧幀的頂部，F(xiàn)P指針指向棧幀的底部(SP和FP是兩個寄存器)。一個棧幀中保存了主函數(shù)所傳的參數(shù)值、函數(shù)內(nèi)的所有局部變量、函數(shù)返回的PC值(也就是主函數(shù)調(diào)用子函數(shù)后的下一條指令的位置)，以及主函數(shù)的FP值。總而言之，一個函數(shù)在執(zhí)行前必須要將現(xiàn)在函數(shù)的FP及SP建立起來。這個過程也就是本小節(jié)一開始提到的函數(shù)的連接(linkage)。在SEAL中我們假設(shè)把R15用作FP，SP是一個特殊的寄存器。當(dāng)然，你也可以將其他的寄存器設(shè)為FP，只要在編譯函數(shù)時有一個統(tǒng)一的規(guī)則就好了。SP的值可以用匯編指令add和sub來更改，也可以用push和pop指令來做加1或減1的更新。當(dāng)pushR時，該指令將SP減1，然后將寄存器R的值存入SP所指的地址；popR時，該指令會將SP所指地址的值load進(jìn)寄存器R，然后將SP加1。我們假設(shè)主函數(shù)已經(jīng)有一個棧幀了，棧底是FP，棧頂是SP，如圖3-28(a)所示。在主函數(shù)中有兩個局部變量x和y，x的地址是-2(R15)，y的地址是-1(R15)，大家可以參看主程序中關(guān)于x=5和y=6的匯編代碼。SEAL中函數(shù)調(diào)用時棧幀的建立

92接下去主函數(shù)要調(diào)用子函數(shù)add(x,y)，我們要在這里詳細(xì)描述函數(shù)調(diào)用時新棧幀建立的過程。一、參數(shù)的傳遞將參數(shù)以反向的順序push進(jìn)棧中，所以先pushy的值，再pushx的值，如圖3-28(b)所示。圖3-28執(zhí)行call指令前棧的狀態(tài)SEAL中函數(shù)調(diào)用時棧幀的建立

93二、執(zhí)行call指令call指令會做兩件事：第一，將PC值push進(jìn)入棧，如圖3-29(a)所示，這個PC值指向callLadd的下一條指令，也就是函數(shù)執(zhí)行完后返回的地址；第二，然后gotoLadd(就是把PC值設(shè)成Ladd的地址)。三、函數(shù)起始的三條指令這三條指令是所有函數(shù)開始時都會有的三條類似的指令：①pushR15,將主函數(shù)的FP值存入棧中；②movR15,sp，將新的FP指向SP的位置，也就是FP指向此時棧的頂端，如圖3-29(b)所示；③subsp,sp,1，將SP再往上移，留出局部變量的空間，此add函數(shù)只有一個局部變量，所以只要留一個位置，假如有n個局部變量，SP就要減n。經(jīng)過這三個指令之后，棧的狀態(tài)如圖3-29(c)所示。圖3-29執(zhí)行call指令之后棧的狀態(tài)SEAL中函數(shù)調(diào)用時棧幀的建立

94四、add函數(shù)中的計算一個函數(shù)的棧幀建立后，F(xiàn)P會固定住，SP會隨著函數(shù)中的push、pop指令而更改，所以我們通常是用FP做基準(zhǔn)位置來得到參數(shù)或函數(shù)內(nèi)的局部變量的地址。在add函數(shù)中的參數(shù)a的地址是2(R15)，參數(shù)b的地址是3(R15)，局部變量c的地址是-1(R15)，請參考匯編語言代碼的相關(guān)load,store語句。函數(shù)的結(jié)果用R1傳回主函數(shù)。五、函數(shù)結(jié)束的三條指令這三條指令會將棧幀返回主函數(shù)的棧幀狀態(tài)。①movsp,R15，將SP下拉到FP所指的位置；②popR15，返回主函數(shù)的FP值；③ret，相當(dāng)于poppc，也就是返回到主函數(shù)調(diào)用子函數(shù)的下一條指令。函數(shù)返回時棧的狀態(tài)如圖3-30所示。圖3-30函數(shù)返回時棧的狀態(tài)SEAL中函數(shù)調(diào)用時棧幀的建立

95經(jīng)驗談：(1)主函數(shù)將參數(shù)值壓入棧后，這些參數(shù)的位置就會被子函數(shù)當(dāng)作變量來使用，如例中子函數(shù)的a和b，其地址分別是2(R15)和3(R15)。所以，參數(shù)變量是屬于子函數(shù)的局部變量。(2)主函數(shù)是將參數(shù)的“值”傳遞給子函數(shù)，這種方式叫做“callbyvalue”，是一種較為通用的參數(shù)傳遞方式，比如C語言就是用這種方式。當(dāng)然，這個值也可以用來傳遞參數(shù)的地址，只不過子函數(shù)要做相應(yīng)的更改，就如同在C語言中傳遞一個指針，那么子函數(shù)中就要對指針做運算了，在此我們就不做額外的解釋了。(3)函數(shù)的返回值普通用寄存器R1返回，假如有多個返回值的話可以用多個寄存器返回，但是要事先約定好。(4)除了返回的寄存器R1之外，其他的寄存器應(yīng)該在函數(shù)調(diào)用后保持與函數(shù)調(diào)用之前相同的值，所以在函數(shù)計算開始前，需要將函數(shù)中會被更改的寄存器值push到棧中保存，在return前再一一pop回來，例如函數(shù)add更改了寄存器R2和R3，所以在更改之前先push進(jìn)棧，在return前再pop返回原來的R2與R3的值，請見匯編代碼。(5)返回后，參數(shù)仍然留在棧中，主函數(shù)可以將參數(shù)pop出，但是需要消耗pop指令的代價，所以主函數(shù)常常就坐視不管，讓其留在棧中。但是對于遞歸函數(shù)，需要將每次調(diào)用傳遞的參數(shù)彈出棧，否則后續(xù)的出棧可能會錯位。SEAL中函數(shù)調(diào)用時棧幀的建立

96至此，函數(shù)調(diào)用時函數(shù)棧幀的建立過程介紹完畢。我們看到在#<匯編代碼：函數(shù)調(diào)用兩個數(shù)求和>中最后一句指令：“_prR1”，這是我們?yōu)榱藢⒔Y(jié)果輸出在控制臺，在SEAL中添加并實現(xiàn)的一個打印指令，可以將你希望輸出的值打印出來。在介紹完使用函數(shù)調(diào)用對兩數(shù)求和時函數(shù)棧幀的建立過程，相信大家對函數(shù)調(diào)用已經(jīng)有了一個全面的了解。接下來我們使用一個更為復(fù)雜的示例介紹函數(shù)棧幀的建立過程，將會繼續(xù)介紹前一個示例中未涉及到的一些細(xì)節(jié)并詳細(xì)說明該示例每條指令執(zhí)行過程。SEAL中函數(shù)調(diào)用時棧幀的建立

97現(xiàn)在給出函數(shù)調(diào)用求三個數(shù)的最小值的python程序#<python代碼：三個數(shù)求最小值>和匯編程序#<匯編代碼：三個數(shù)求最小值>。#<python代碼：三個數(shù)求最小值>defget_min(x,y):ifx<=y:returnxelse:returnyif__name__=="__main__":a=7b=18c=9print(get_min(get_min(a,b),c))#<匯編代碼：三個數(shù)求最小值>movR15,300#R15表示fp，將基地址設(shè)置為300movsp,R15#sp=fpsubsp,sp,3#sp從300往下開辟3個空間給局部變量a,b,csp=