研究生課程程序語(yǔ)言設(shè)計(jì)原理教程第06章

1、第第6 6章章 函數(shù)和過(guò)程函數(shù)和過(guò)程 命令式語(yǔ)言中子程序有兩種形式：函數(shù)(必須返回值)也叫函數(shù)，過(guò)程(實(shí)施一組動(dòng)作)也叫子例程subroutine。它們是程序的第一次分割，這種分割的好處：實(shí)施的功能單一，便于調(diào)試；相對(duì)獨(dú)立，便于多人分工完成，且時(shí)間不受約束；相對(duì)封閉，人們易于控制，是分解復(fù)雜性的有力措施。 子程序和主程序聯(lián)系的接口特別重要。在這個(gè)界面上要指出該例程的數(shù)據(jù)特征， 即輸入什么輸出什么。而整個(gè)子程序體是完成從輸入到輸出的實(shí)現(xiàn)手段。界面指出“做什么？”，而子程序體回答“怎么做”。80年代程序完成第二次分割： 將子程序定義(即界面)和子程序體顯式的分開， 成為相對(duì)獨(dú)立的規(guī)格說(shuō)明(spec

2、ification)和體(body)。6.1 6.1 函數(shù)和過(guò)程抽象函數(shù)和過(guò)程抽象 函數(shù)抽象是用一個(gè)簡(jiǎn)單的名字抽象代表一個(gè)函數(shù)。函數(shù)由函數(shù)型構(gòu)(signature)和函數(shù)體(body)組成。函數(shù)計(jì)算的目的是求值。函數(shù)體等同于一個(gè)復(fù)合的表達(dá)式。函數(shù)抽象是對(duì)表達(dá)式的抽象 過(guò)程抽象是用一個(gè)簡(jiǎn)單的名字抽象代表一個(gè)計(jì)算過(guò)程。過(guò)程由過(guò)程型構(gòu)和過(guò)程體組成。過(guò)程調(diào)用的目的是執(zhí)行一組命令過(guò)程抽象是對(duì)命令(即語(yǔ)句)集的抽象 函數(shù)由函數(shù)型構(gòu)和函數(shù)體組成。形式是： function func (fp1,fp2,.)：returntype；/函數(shù)型構(gòu) b; /函數(shù)體，可包括任何聲明和語(yǔ)句 其中fp1，fp2，為形式參數(shù)

3、，也叫形式變?cè)?argument)returntype 為函數(shù)返回值的類型 函數(shù)引用是應(yīng)用函數(shù)的唯一手段，它在同名的函數(shù)名之下給出實(shí) 在參數(shù)(實(shí)在變?cè)?： func (ap1,ap2,.); 各種語(yǔ)言函數(shù)定義(a) fortran integer function fact(n) /前綴指明返回類型 integer n,i,f /參數(shù)類型在此聲明 f = 1 do 10 i = 2,n f = f*1 10 continue fact = f /必須至少定義函數(shù)名一次 return /至少有一返回語(yǔ)句 end(b) pascal function fact (n:integer) :integ

4、er； /參數(shù)類型在變?cè)碇卸x， begin /后綴指明返回類型 fact = 1； if n = 1 or n = 0 then return else fact = n*fact(n-1)； /也要定義函數(shù)名 end(c) c int fact (n) /前綴指明返回類型 int n; /參數(shù)在體中聲名類型 int i, f; /ansi c改參數(shù)原型 f = 1; if(n1) for (i = 2; i /用函數(shù)定義值 if n = 1 then 1 else n*fact (n-1)續(xù) 多重入口和指定返回fortran 的多重入口示例 subroutine deg(r,theta,

5、x,y) c = 3.14159/180.0 theta = c * theta entry rad (r,theta,x,y) x = r * cos(theta) y = r * sin(theta) return end若theta是度數(shù)值時(shí)，則調(diào)用語(yǔ)句為： call deg (r,theta,x,y) /入口在子程序頂部若theta是弧度值時(shí)，則： call rad（r，thera，x，y） /入口在子程序中fortran的指定返回subroutine rm（x，y，*，*，*） . . .return2 /返回語(yǔ)句標(biāo)號(hào)80 . . .return1 /返回語(yǔ)句標(biāo)號(hào)70 . . .re

6、turn3 /返回語(yǔ)句標(biāo)號(hào)120 . . .end call rm(a,b,70,80,120) 形實(shí)參數(shù)表中元素個(gè)數(shù)，次序，類型應(yīng)一致。早期語(yǔ)言都嚴(yán)格遵此準(zhǔn)則。近代語(yǔ)言提供了較多的靈活表示法。 ada引入缺省參數(shù)，實(shí)參個(gè)數(shù)可少于形參個(gè)數(shù)；指明參數(shù)結(jié)合不考慮次序；ada引入?yún)?shù)模式in,out,inout指明只讀，只寫，讀寫參數(shù)。 c語(yǔ)言允許任意多個(gè)參數(shù)的調(diào)用。如內(nèi)定義函數(shù)printf()調(diào)用時(shí)可以寫任意個(gè)輸出，只是第一參數(shù)中的格式個(gè)數(shù)與參數(shù)個(gè)數(shù)對(duì)應(yīng)。 過(guò)程定義與調(diào)用 過(guò)程子程序定義形式 procedure proc (fp1,fp2,.) /過(guò)程型構(gòu) b; /子程序體包含局聲明 對(duì)應(yīng)的過(guò)程調(diào)

7、用是： proc (ap1, ap2, .)； c語(yǔ)言一切過(guò)程，包括主程序都是函數(shù)過(guò)程。它以void(無(wú)值)關(guān)鍵字代替函數(shù)類型指明符，實(shí)施子程序過(guò)程語(yǔ)義 引用或調(diào)用的形式 無(wú)參過(guò)程- 函數(shù)和過(guò)程的參數(shù)表均可為空。有的語(yǔ)言保留()，有的只有一個(gè)名字。一般無(wú)參過(guò)程也要更新過(guò)程內(nèi)部的值。函數(shù)過(guò)程還會(huì)返回不同的值。全局量在函數(shù)中有效。改變了全局量?jī)纱握{(diào)用結(jié)果值當(dāng)然不一樣。這就是函數(shù)的副作用(side effect)。 - 有副作用的函數(shù) c 在很大程度上利用函數(shù)副作用，例如，當(dāng)需要跳過(guò)空白時(shí)寫： while (c = getch() = )； - ada中常用的隨機(jī)數(shù)： function random

8、 return float range 0.01.0;引用時(shí)， 若field已聲明為常量： result = random * field；random若無(wú)副作用result值不可能改變。6.2 參數(shù)機(jī)制語(yǔ)言中第一類對(duì)象均可作函數(shù)/過(guò)程參數(shù)。 由于變量的時(shí)空特性，傳遞的形-實(shí)參數(shù)可以有許多不同的實(shí)現(xiàn)結(jié)合的辦法，即參數(shù)機(jī)制。6.2.1 傳值調(diào)用（call-by-value）1實(shí)參表達(dá)式先求值2將值復(fù)制給對(duì)應(yīng)的形參。形參和實(shí)參有同樣大小的存儲(chǔ)3過(guò)程運(yùn)行后一般不再將改變了的形參值復(fù)制回實(shí)參 pascal中的傳值調(diào)用 procedure test1(j2,a2:integer;p2:list) beg

9、inwriteln(j2,a2,p2.value);j2= j2 + 1;p2= p2.next;writeln(j2,a2,p2.value) end. 調(diào)用程序有： test1(j1,a1j1,p1.next);第一次打印為： 1 30 %第二次打印為： 2 30 $堆 棧 幀中 的 調(diào)用 程 序 j1 a1 p1 1264530*$/% 堆 棧 幀 中 的 過(guò) 程 t est1 2 j2 a2 p2 130指針 束定傳值調(diào)用圖示6.2.2 傳名調(diào)用(call-by-name)傳名在過(guò)程/函數(shù)中加工的就是實(shí)參已分配的值，因此不需付出雙倍存儲(chǔ)代價(jià)。但傳名過(guò)程的虛實(shí)結(jié)合是將程序體中所有形參出現(xiàn)

10、的地方均以實(shí)參變?cè)脫Q。這樣出現(xiàn)幾次算幾次效率是低的。傳名調(diào)用程序示例由于pascal無(wú)傳名機(jī)制，此處作一點(diǎn)擴(kuò)充：procedure test2(name j2,a2:integer;name p2:list); 函數(shù)體同test1執(zhí)行同樣調(diào)用：test2(j1,a1j1,p1.next);名結(jié)合后打?。?1 30 %執(zhí)行后結(jié)果是： 2 45 $*$/% 堆 杖 幀中 過(guò) 程 t e st2 就是 j2 就是 a2 就是 p2 j1p1。 n exta1j1 傳名調(diào)用圖示堆 棧 幀中 的 調(diào)用 程 序 j1 2 a1 p1 12645306.2.3 6.2.3 引用調(diào)用引用調(diào)用(call_b

11、y_reference)引用參數(shù)實(shí)現(xiàn)時(shí)， 編譯器在子程序堆棧中設(shè)許多中間指針， 將形參名束定于此指針，而該指針的值是實(shí)參變量的地址(在主程序堆?？蚣軆?nèi))，在子程序中每次對(duì)形參變量的存取都是自動(dòng)地遞引用到實(shí)參存儲(chǔ)對(duì)象上。引用調(diào)用的pascal示例： procedure test3(var j2,a2:integer;var p2:list); 函數(shù)體同test1相應(yīng)的調(diào)用程序是：test3(j1,a1j1,p1.next); 第一次打印是： 1 30 %第二次打印是： 2 30 $引用調(diào)用圖示堆 棧 幀中 的 調(diào)用 程 序 2 j1 a1 p1 11264530*$/% 堆 棧 幀 中 的 過(guò)

12、程 t est1 j2 a2 p2 6.2.4 參數(shù)模式與返回調(diào)用(call-by-return)顯式指明參數(shù)傳遞模式,可以為編譯實(shí)現(xiàn)提供信息 fun_name(x,y:real; var s,q:integer).x，y傳值實(shí)現(xiàn)，它只讀。s，q引用實(shí)現(xiàn)，可讀/寫ada只規(guī)定參數(shù)模式in，out，inout，傳遞方向的模式(mode)。由編譯選擇實(shí)現(xiàn)方式： proc_name (x，y:in real;s:inout integer;q:outinteger)in模式可不寫出(缺省)。 函數(shù)只能有in的模式，過(guò)程都有，且出現(xiàn)次序不受限制。x，y因在子程序中只讀,傳值實(shí)現(xiàn)可保證不受破壞。s讀/寫

13、用引用實(shí)現(xiàn)，而q是只寫參數(shù)，傳值和引用都不能保證”只”寫實(shí)現(xiàn)返回調(diào)用機(jī)制有兩種辦法:其一是復(fù)制。另一種辦法是引用實(shí)現(xiàn)增加”只寫”保護(hù)6.2.5 值-返回調(diào)用（call-by-value-and-return）是對(duì)by-reference的改進(jìn)，因多進(jìn)程競(jìng)爭(zhēng)數(shù)據(jù)資源時(shí)多重引用(束定)易于引起混亂p2返回值由p2定 返回值由p1定 正常順序執(zhí)行對(duì)于并發(fā)多任務(wù)宜只讀只寫 值與返回調(diào)用機(jī)制是把值調(diào)用和返回調(diào)用組合起來(lái),實(shí)現(xiàn)調(diào)用程序雙向通道,這對(duì)于有多個(gè)存儲(chǔ)器的多處理器系統(tǒng)和網(wǎng)絡(luò)分布式系統(tǒng)值調(diào)用極度安全在子程序執(zhí)行期間因不是束定， 形參變量的值不會(huì)中途改變， 復(fù)制回去和拷貝進(jìn)來(lái)處可設(shè)斷點(diǎn)檢查p1p2p1

14、p2p1p26.2.6 指針參數(shù)（call_by_point）指針作為參數(shù)其實(shí)現(xiàn)方式一般是復(fù)制機(jī)制，它復(fù)制的是地址(指針內(nèi)容)注意和引用調(diào)用之同異例：指針pascal引用版： 交換兩變量的內(nèi)容procedure swap1( var a,b:integer)； var t:integer;begin t = a; a = b; b = tend;調(diào)用程序片斷： j = 3; k = 5; swap1(j,k); /結(jié)果j = 5， k = 3j =3k=5caller-frame= a= t= b3=0，t/n0.5) 若n=0，t=0.8若急求值，第二子表達(dá)式未結(jié)合即失敗 正規(guī)求值，對(duì)應(yīng)名調(diào)

15、用，支持遞歸 if n0 then t/n 0.5 else false 上述調(diào)用等效代入置換后再求值cand=false 懶求值可實(shí)現(xiàn)短路求值也支持遞歸 上例用懶求值等效于正規(guī)求值 c、ada，及近代函數(shù)式語(yǔ)言均采用懶求值6.4 高階函數(shù) 以函數(shù)或過(guò)程作為實(shí)參變?cè)蚍祷刂档暮瘮?shù)或過(guò)程，我們統(tǒng)稱高階函數(shù) 函數(shù)作為變?cè)猯isp有映射函數(shù)(mapping function)它把單目、雙目運(yùn)算擴(kuò)充到多個(gè)數(shù)據(jù)對(duì)象的數(shù)組或表上。映射函數(shù)本身以簡(jiǎn)單運(yùn)算函數(shù)和表(或數(shù)組)作實(shí)參變?cè)猯isp 的mapcar函數(shù)設(shè)程序上文已有四個(gè)表 x:(4 9 16 25)，y:(1 2 3 4),z：nilw:(3 4 5

16、)(2 1)(7 9 3 6)。mapcar要求的實(shí)參函數(shù)用標(biāo)記，則有：表達(dá)式 解釋 返回表 (mapcar+1 x) 把加1函數(shù)用于x諸元素 (5 10 17 26) (mapcar+x y) 加對(duì)應(yīng)諸元素 (5 11 19 29) (mapcar+1 z) 把加1函數(shù)用于空表 nil(不知應(yīng)加幾次)(mapcar(lambda 把函數(shù)(3*a)-b)應(yīng)用到x y (11 25 45 71) (a b)(-(* 3 a)b)對(duì)應(yīng)的元素上 x y) (mapcar caar w) 消去每子表的頭項(xiàng)兩次并銷毀 (5(3 6) 將一個(gè)函數(shù)作為參數(shù)傳遞給另一函數(shù)是十分容易實(shí)現(xiàn)的， 只要傳一個(gè)指向函數(shù)的指針（c） c語(yǔ)言、c+其函數(shù)返回值可以是指向函數(shù)的指針。但c和c+均不能在函數(shù)中創(chuàng)建一個(gè)函數(shù)并把它作為返回值返回。 函數(shù)式語(yǔ)言作用于任何一變?cè)祷刂凳切潞瘮?shù)fun f(x)(y)(z) = f(x,y,z)= f1(y,z) = f2(z)= f3 f1 x=x0 x=x0 x=x0 y=y0 y=y0 f2 z=z0 即函數(shù)閉包函數(shù)作為返回值 閉包(closure)是可用到表達(dá)式上的操作。閉包最有用和最容易理解的應(yīng)用是部分參數(shù)化。例