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

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

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

3、，也叫形式變元(argument)returntype 為函數(shù)返回值的類型 函數(shù)引用是應(yīng)用函數(shù)的唯一手段，它在同名的函數(shù)名之下給出實 在參數(shù)(實在變元)： func (ap1,ap2,.); 各種語言函數(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 /至少有一返回語句 end(b) pascal function fact (n:integer) :integ

4、er； /參數(shù)類型在變元表中定義， 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ù)值時，則調(diào)用語句為： call deg (r,theta,x,y) /入口在子程序頂部若theta是弧度值時，則： call rad（r，thera，x，y） /入口在子程序中fortran的指定返回subroutine rm（x，y，*，*，*） . . .return2 /返回語句標(biāo)號80 . . .return1 /返回語句標(biāo)號70 . . .re

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

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

8、 return float range 0.01.0;引用時， 若field已聲明為常量： result = random * field；random若無副作用result值不可能改變。6.2 參數(shù)機制語言中第一類對象均可作函數(shù)/過程參數(shù)。 由于變量的時空特性，傳遞的形-實參數(shù)可以有許多不同的實現(xiàn)結(jié)合的辦法，即參數(shù)機制。6.2.1 傳值調(diào)用（call-by-value）1實參表達式先求值2將值復(fù)制給對應(yīng)的形參。形參和實參有同樣大小的存儲3過程運行后一般不再將改變了的形參值復(fù)制回實參 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*$/% 堆 棧 幀 中 的 過 程 t est1 2 j2 a2 p2 130指針 束定傳值調(diào)用圖示6.2.2 傳名調(diào)用(call-by-name)傳名在過程/函數(shù)中加工的就是實參已分配的值，因此不需付出雙倍存儲代價。但傳名過程的虛實結(jié)合是將程序體中所有形參出現(xiàn)

10、的地方均以實參變元名置換。這樣出現(xiàn)幾次算幾次效率是低的。傳名調(diào)用程序示例由于pascal無傳名機制，此處作一點擴充：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 $*$/% 堆 杖 幀中 過 程 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ù)實現(xiàn)時， 編譯器在子程序堆棧中設(shè)許多中間指針， 將形參名束定于此指針，而該指針的值是實參變量的地址(在主程序堆?？蚣軆?nèi))，在子程序中每次對形參變量的存取都是自動地遞引用到實參存儲對象上。引用調(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*$/% 堆 棧 幀 中 的 過

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

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

14、p2p1p26.2.6 指針參數(shù)（call_by_point）指針作為參數(shù)其實現(xiàn)方式一般是復(fù)制機制，它復(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若急求值，第二子表達式未結(jié)合即失敗 正規(guī)求值，對應(yīng)名調(diào)

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

16、)(2 1)(7 9 3 6)。mapcar要求的實參函數(shù)用標(biāo)記，則有：表達式 解釋 返回表 (mapcar+1 x) 把加1函數(shù)用于x諸元素 (5 10 17 26) (mapcar+x y) 加對應(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)對應(yīng)的元素上 x y) (mapcar caar w) 消去每子表的頭項兩次并銷毀 (5(3 6) 將一個函數(shù)作為參數(shù)傳遞給另一函數(shù)是十分容易實現(xiàn)的， 只要傳一個指向函數(shù)的指針（c） c語言、c+其函數(shù)返回值可以是指向函數(shù)的指針。但c和c+均不能在函數(shù)中創(chuàng)建一個函數(shù)并把它作為返回值返回。 函數(shù)式語言作用于任何一變元返回值是新函數(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)是可用到表達式上的操作。閉包最有用和最容易理解的應(yīng)用是部分參數(shù)化。例