北航研究生課程程序語言設計原理教程第章.ppt

《北航研究生課程程序語言設計原理教程第章.ppt》由會員分享，可在線閱讀，更多相關《北航研究生課程程序語言設計原理教程第章.ppt（23頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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