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

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

2、的規(guī)格說明(specification)和體(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ù)體，可包括任何聲明和語句

3、 其中fp1，fp2，為形式參數(shù)，也叫形式變元(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

4、 (n:integer) :integer； /參數(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 的多重入口示例 s

5、ubroutine deg(r,theta,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 . .

6、 . return1 /返回語句標(biāo)號70 . . . return3 /返回語句標(biāo)號120 . . . end call rm(a,b,70,80,120) 形實參數(shù)表中元素個數(shù)，次序，類型應(yīng)一致。早期語言都嚴格遵此準 則。近代語言提供了較多的靈活表示法。 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,

7、fp2,.) /過程型構(gòu) b; /子程序體包含局聲明 對應(yīng)的過程調(diào)用是： 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 = ge

8、tch() = )； - ada中常用的隨機數(shù)： function random 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ù) 制回實參 pasc

9、al中的傳值調(diào)用 procedure test1(j2,a2:integer;p2:list) begin writeln(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 1 264530 *$ /% 堆 棧 幀 中 的 過 程 t est1 2 j2 a2 p2 1 30 指針 束定 傳值調(diào)用圖示 6.2.2 傳名調(diào)用(call-

10、by-name) 傳名在過程/函數(shù)中加工的就是實參已分配的值，因此不需付出雙倍存儲代 價。但傳名過程的虛實結(jié)合是將程序體中所有形參出現(xiàn)的地方均以實參變元 名置換。這樣出現(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 j1 p1

11、。 n ext a1j1 傳名調(diào)用圖示 堆 棧 幀中 的 調(diào)用 程 序 j1 2 a1 p1 1 264530 6.2.3 6.2.3 引用調(diào)用引用調(diào)用(call_by_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.nex

12、t); 第一次打印是： 1 30 % 第二次打印是： 2 30 $ 引用調(diào)用圖示 堆 棧 幀中 的 調(diào)用 程 序 2 j1 a1 p1 11 264530 *$ / % 堆 棧 幀 中 的 過 程 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 r

13、eal;s:inout integer;q:outinteger) in模式可不寫出(缺省)。 函數(shù)只能有in的模式，過程都有，且 出現(xiàn)次序不受限制。x，y因在子程序中只讀,傳值實現(xiàn)可保證不 受破壞。s讀/寫用引用實現(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ù)宜只讀只寫 值與返

14、回調(diào)用機制是把值調(diào)用和返回調(diào)用組合起來,實現(xiàn)調(diào)用程序雙 向通道,這對于有多個存儲器的多處理器系統(tǒng)和網(wǎng)絡(luò)分布式系統(tǒng)值調(diào) 用極度安全 在子程序執(zhí)行期間因不是束定， 形參變量的值不會中途改變， 復(fù)制 回去和拷貝進來處可設(shè)斷點檢查 p1 p2 p1p2 p1 p2 6.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 = t e

15、nd; 調(diào)用程序片斷： j = 3; k = 5; swap1(j,k); /結(jié)果j = 5， k = 3 j = 3 k= 5 caller-frame = a = t = b 3 = 0，t/n0.5) 若n=0，t=0.8 若急求值，第二子表達式未結(jié)合即失敗 正規(guī)求值，對應(yīng)名調(diào)用，支持遞歸 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ù)作

16、為變元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：nil w:(3 4 5)(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)加

17、幾次) (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ù)化。例如