北航研究生課程程序語言設(shè)計(jì)原理教程第章.ppt

第6章函數(shù)和過程 命令式語言中子程序有兩種形式 函數(shù) 必須返回值 也叫函數(shù) 過程 實(shí)施一組動作 也叫子例程subroutine 它們是程序的第一次分割 這種分割的好處 實(shí)施的功能單一 便于調(diào)試 相對獨(dú)立 便于多人分工完成 且時間不受約束 相對封閉 人們易于控制 是分解復(fù)雜性的有力措施 子程序和主程序聯(lián)系的接口特別重要 在這個界面上要指出該例程的數(shù)據(jù)特征 即輸入什么輸出什么 而整個子程序體是完成從輸入到輸出的實(shí)現(xiàn)手段 界面指出 做什么 而子程序體回答 怎么做 80年代程序完成第二次分割 將子程序定義 即界面 和子程序體顯式的分開 成為相對獨(dú)立的規(guī)格說明 Specification 和體 body 6 1函數(shù)和過程抽象 函數(shù)抽象是用一個簡單的名字抽象代表一個函數(shù) 函數(shù)由函數(shù)型構(gòu) Signature 和函數(shù)體 body 組成 函數(shù)計(jì)算的目的是求值 函數(shù)體等同于一個復(fù)合的表達(dá)式 函數(shù)抽象是對表達(dá)式的抽象過程抽象是用一個簡單的名字抽象代表一個計(jì)算過程 過程由過程型構(gòu)和過程體組成 過程調(diào)用的目的是執(zhí)行一組命令過程抽象是對命令 即語句 集的抽象函數(shù)由函數(shù)型構(gòu)和函數(shù)體組成 形式是 functionFUNC fp1 fp2 returntype 函數(shù)型構(gòu)B 函數(shù)體 可包括任何聲明和語句其中fp1 fp2 為形式參數(shù) 也叫形式變元 argument returntype為函數(shù)返回值的類型 函數(shù)引用是應(yīng)用函數(shù)的唯一手段 它在同名的函數(shù)名之下給出實(shí)在參數(shù) 實(shí)在變元 FUNC ap1 ap2 各種語言函數(shù)定義 a FORTRANINTEGERFUNCTIONFACT N 前綴指明返回類型INTEGERN I F 參數(shù)類型在此聲明F 1DO10I 2 NF F 110CONTINUEFACT F 必須至少定義函數(shù)名一次RETURN 至少有一返回語句END b PascalFUNCTIONfact n Integer Integer 參數(shù)類型在變元表中定義 BEGIN 后綴指明返回類型fact 1 IFn 1ORn 0THENReturnELSEFact n fact n 1 也要定義函數(shù)名END c Cintfact n 前綴指明返回類型intn 參數(shù)在體中聲名類型inti f ANSIC改參數(shù)原型f 1 if n 1 for i 2 i 用函數(shù)定義值ifn 1then1elsen fact n 1 續(xù) 多重入口和指定返回 FORTRAN的多重入口示例SUBROUTINEDEG R THETA X Y C 3 14159 180 0THETA C THETAENTRYRAD R THETA X Y X R COS THETA Y R SIN THETA RETURNEND若THETA是度數(shù)值時 則調(diào)用語句為 CALLDEG R THETA X Y 入口在子程序頂部若THETA是弧度值時 則 CALLRAD R THERA X Y 入口在子程序中 FORTRAN的指定返回SUBROUTINERM X Y RETURN2 返回語句標(biāo)號80 RETURN1 返回語句標(biāo)號70 RETURN3 返回語句標(biāo)號120 ENDCALLRM A B 70 80 120 形 實(shí)參數(shù)表中元素個數(shù) 次序 類型應(yīng)一致 早期語言都嚴(yán)格遵此準(zhǔn)則 近代語言提供了較多的靈活表示法 Ada引入缺省參數(shù) 實(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)用過程子程序定義形式procedurePROC fp1 fp2 過程型構(gòu)B 子程序體包含局聲明對應(yīng)的過程調(diào)用是 PROC ap1 ap2 C語言一切過程 包括主程序都是函數(shù)過程 它以void 無值 關(guān)鍵字代替函數(shù)類型指明符 實(shí)施子程序過程語義 引用或調(diào)用的形式 無參過程 函數(shù)和過程的參數(shù)表均可為空 有的語言保留 有的只有一個名字 一般無參過程也要更新過程內(nèi)部的值 函數(shù)過程還會返回不同的值 全局量在函數(shù)中有效 改變了全局量兩次調(diào)用結(jié)果值當(dāng)然不一樣 這就是函數(shù)的副作用 sideeffect 有副作用的函數(shù)C在很大程度上利用函數(shù)副作用 例如 當(dāng)需要跳過空白時寫 while c getch Ada中常用的隨機(jī)數(shù) functionRANDOMreturnFLOATrange0 0 1 0 引用時 若FIELD已聲明為常量 RESULT RANDOM FIELD RANDOM若無副作用RESULT值不可能改變 6 2參數(shù)機(jī)制 語言中第一類對象均可作函數(shù) 過程參數(shù) 由于變量的時空特性 傳遞的形 實(shí)參數(shù)可以有許多不同的實(shí)現(xiàn)結(jié)合的辦法 即參數(shù)機(jī)制 6 2 1傳值調(diào)用 call by value 1 實(shí)參表達(dá)式先求值 2 將值復(fù)制給對應(yīng)的形參 形參和實(shí)參有同樣大小的存儲 3 過程運(yùn)行后一般不再將改變了的形參值復(fù)制回實(shí)參 Pascal中的傳值調(diào)用PROCEDUREtest1 J2 A2 Integer P2 list BEGINWriteln J2 A2 P2 value J2 J2 1 P2 P2 next Writeln J2 A2 P2 value END 調(diào)用程序有 test1 J1 A1 J1 P1 next 第一次打印為 130 第二次打印為 230 王超 6 2 2傳名調(diào)用 call by name 傳名在過程 函數(shù)中加工的就是實(shí)參已分配的值 因此不需付出雙倍存儲代價 但傳名過程的虛實(shí)結(jié)合是將程序體中所有形參出現(xiàn)的地方均以實(shí)參變元名置換 這樣出現(xiàn)幾次算幾次效率是低的 傳名調(diào)用程序示例由于Pascal無傳名機(jī)制 此處作一點(diǎn)擴(kuò)充 PROCEDUREtest2 NAMEJ2 A2 Integer NAMEP2 List 函數(shù)體同test1執(zhí)行同樣調(diào)用 test2 J1 A1 J1 P1 next 名結(jié)合后打印 130 執(zhí)行后結(jié)果是 245 6 2 3引用調(diào)用 call by reference 引用參數(shù)實(shí)現(xiàn)時 編譯器在子程序堆棧中設(shè)許多中間指針 將形參名束定于此指針 而該指針的值是實(shí)參變量的地址 在主程序堆?？蚣軆?nèi) 在子程序中每次對形參變量的存取都是自動地遞引用到實(shí)參存儲對象上 引用調(diào)用的Pascal示例 PROCEDUREtest3 VARJ2 A2 Integer VARP2 List 函數(shù)體同test1相應(yīng)的調(diào)用程序是 test3 J1 A1 J1 P1 next 第一次打印是 130 第二次打印是 230 引用調(diào)用圖示 王超 6 2 4參數(shù)模式與返回調(diào)用 call by return 顯式指明參數(shù)傳遞模式 可以為編譯實(shí)現(xiàn)提供信息fun name x y Real VARs 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 inReal S inoutInteger Q outInteger in模式可不寫出 缺省 函數(shù)只能有in的模式 過程都有 且出現(xiàn)次序不受限制 x y因在子程序中只讀 傳值實(shí)現(xiàn)可保證不受破壞 s讀 寫用引用實(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 是對by reference的改進(jìn) 因多進(jìn)程競爭數(shù)據(jù)資源時多重引用 束定 易于引起混亂 P2 返回值由P2定返回值由P1定正常順序執(zhí)行對于并發(fā)多任務(wù)宜只讀 只寫值與返回調(diào)用機(jī)制是把值調(diào)用和返回調(diào)用組合起來 實(shí)現(xiàn)調(diào)用程序雙向通道 這對于有多個存儲器的多處理器系統(tǒng)和網(wǎng)絡(luò)分布式系統(tǒng)值調(diào)用極度安全在子程序執(zhí)行期間因不是束定 形參變量的值不會中途改變 復(fù)制回去和拷貝進(jìn)來處可設(shè)斷點(diǎn)檢查 P1 P2 P1 P2 P1 P2 6 2 6指針參數(shù) call by point 指針作為參數(shù)其實(shí)現(xiàn)方式一般是復(fù)制機(jī)制 它復(fù)制的是地址 指針內(nèi)容 注意和引用調(diào)用之同異 例 指針Pascal引用版 交換兩變量的內(nèi)容PROCEDUREswap1 VARa b Integer VARt Integer BEGINT a a b b tEND 調(diào)用程序片斷 j 3 k 5 swap1 j k 結(jié)果j 5 k 3 J 3 K 5 Caller frame a t b 3 Swapl frame 指針版 變換兩變量的內(nèi)容TYPEint ptr Integer VARjp kp int ptr PROCEDUREswap2 a b int ptr VARt Integer BEGINt a a b b tEND 相應(yīng)調(diào)用程序片斷 NEW jp jp 3 NEW kp kp 5 Swap2 jp kp 王超 C語言的指針參數(shù)傳遞voidswap3 int a int b intt t a a b b t 形參是兩指針 實(shí)參不用指針的版本 main intj 3 k 5 聲明并初始化兩整數(shù)swap3 類型匹配嗎 王超 實(shí)參是指針的版本 main intj 3 k 5 int jp 6 3變元求值策略ML funsqr n int n n若p 2 q 5有調(diào)用sqr p q sqr 2 5 7 7 49急求值 表達(dá)式先求值再入體 正規(guī)求值 p q p q 2 5 2 5 7 7 49按 演算 先置換原表達(dá)式 體中代入值計(jì)算懶求值 p q p q 2 5 2 5 2 5 7 49只在界面置換原表達(dá)式 何時用該值何時計(jì)算 相同的只算一次Church Rosser性質(zhì) 表達(dá)式的完全求值 僅當(dāng)它前后一致地按正規(guī)順序求值 幾種求值方式得的結(jié)果應(yīng)一致 若一表達(dá)式能以幾種不同的求值次序求值 包括混合使用幾種求值方案 則所有這些求值次序得到的結(jié)果值應(yīng)該是一樣的 急求值是嚴(yán)格求值 對應(yīng)值調(diào)用 最安全funcand b1 bool b2 bool ifb1thenb2elsefalse有調(diào)用cand n 0 t n 0 5 若n 0 t 0 8若急求值 第二子表達(dá)式未結(jié)合即失敗 正規(guī)求值 對應(yīng)名調(diào)用 支持遞歸ifn 0thent n 0 5elsefalse上述調(diào)用等效代入置換后再求值cand false 懶求值可實(shí)現(xiàn)短路求值也支持遞歸上例用懶求值等效于正規(guī)求值C Ada 及近代函數(shù)式語言均采用懶求值 6 4高階函數(shù) 以函數(shù)或過程作為實(shí)參變元或返回值的函數(shù)或過程 我們統(tǒng)稱高階函數(shù)函數(shù)作為變元LISP有映射函數(shù) mappingfunction 它把單目 雙目運(yùn)算擴(kuò)充到多個數(shù)據(jù)對象的數(shù)組或表上 映射函數(shù)本身以簡單運(yùn)算函數(shù)和表 或數(shù)組 作實(shí)參變元 LISP的mapcar函數(shù)設(shè)程序上文已有四個表x 491625 y 1234 z NILw 345 21 7936 mapcar要求的實(shí)參函數(shù)用 標(biāo)記 則有 表達(dá)式 解釋 返回表 mapcar 1x 把加1函數(shù)用于x諸元素 5101726 mapcar xy 加對應(yīng)諸元素 5111929 mapcar 1z 把加1函數(shù)用于空表 NIL 不知應(yīng)加幾次 mapcar lambda 把函數(shù) 3 a b 應(yīng)用到xy 11254571 ab 3a b 對應(yīng)的元素上 xy mapcar caarw 消去每子表的頭項(xiàng)兩次并銷毀 5 36 將一個函數(shù)作為參數(shù)傳遞給另一函數(shù)是十分容易實(shí)現(xiàn)的 只要傳一個指向函數(shù)的指針 C C語言 C 其函數(shù)返回值可以是指向函數(shù)的指針 但C和C 均不能在函數(shù)中創(chuàng)建一個函數(shù)并把它作為返回值返回 函數(shù)式語言作用于任何一變元返回值是新函數(shù)funF x y z F x y z F1 y z F2 z F3F1x x0 x x0 x x0y y0y y0F2z z0即函數(shù)閉包 函數(shù)作為返回值 閉包 closure 是可用到表達(dá)式上的操作 閉包最有用和最容易理解的應(yīng)用是部分參數(shù)化 例如 有n個變元的函數(shù) 我們將其中一個變元束定于局部定義的值上就得到一個n 1個變元的新函數(shù) ML閉包的應(yīng)用 funpowerC n b ifn 0then1 0elseb powerC n 1 b 可以顯式給出valsqr powerC2andcube powerC3sqr b cube b b3顯示的新函數(shù)閉包c(diǎn)losure產(chǎn)生一系列函數(shù)如 f a b c fa b c fb a c fc b a fab c fbc a fca b fabc 隱式返回函數(shù)