Microsoft PowerPoint - 10control.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - 10control.ppt"

ともなりさんきち
6 years ago
Views:

1 プログラミング特論 (0) 制御櫻井彰人 Course web site: 話題構造化プログラミング (Structured Programmg) goto 文有害説 (Go to considered harmful) 例外 (Exceptions) 値をとりうる構造化ジャンプ例外処理部の動的スコープ継続 (Contuations) プログラムの残り部分を表現する関数末尾再帰の一般形評価順序の制御 ( 強制と遅延 ) これはスキップ. 興味があれば参考書を. Fortran の制御構造歴史となった議論 0 IF (X.GT ) GO TO 0 X = -X IF (X.LT ) GO TO 50 0 IF (X*Y.LT ) GO TO 30 X = X-Y-Y 30 X = X+Y 50 CONTINUE X = A Y = B-A GO TO Dijkstra, Go To Statement Considered Harmful Letter to Editor, C ACM, March 968 web でも : Knuth, goto 文のある構造化プログラム goto 文は使ってもよいが構造化した方法で議論再開 GOTO Considered Harmful considered harmful (987) 一般的な問題構文規則でよいプログラムスタイルが強制できるか? 手助けになるか? 計算機科学における進歩例外 : 構造化された脱出 (Exit) ジャンプを構造化する標準的な構成子 if thenelseend while doend for {} case 現代的なスタイル論理的なブロックにコードを纏める関数の戻りを除いて明示的なジャンプは避けるブロックの真中や関数本体への飛び込みはできない計算の一部を止める構成子から飛出る (jump) jump の一部としてデータを渡す例外処理用に用意した最新の場所に戻る不要な activation records は deallocate してもよいヒープや他の資源を手放す必要があるかも言語が用意する構成子個例外ハンドラ (exception handler) の宣言例外を提示する (raise) または投げる (throw) 文または式しばしば非正規のまたは例外的な事態に用いるがその必要はない

2 ML における例 exception Determant; (* 例外名称の宣言 *) fun vert (M) = (* 逆行列を求める関数 *) if then raise Determant (* exit if Det=0 *) else vert (mymatrix) handle Determant => ; 行列 mymatrix の行列式が 0 であったときに使う値 C++ における例 Matrix vert(matrix m) { if throw Determant; }; try { vert(mymatrix); } catch (Determant) { // エラーからの回復 } 例外 : C++ vs ML C++ 例外どんな型も投げることができる Stroustrup: I prefer to defe types with no other purpose than exception handlg. This mimizes confusion about their purpose. In particular, I never use a built- type, such as t, as an exception. -- The C++ Programmg Language, 3 rd ed. ML 例外例外は型とは異なる実体 (entity) である. 例外は使用前に宣言される C++ の推奨形に似た形を MLでは必須としている. ML の例外宣言 (Declaration) exception name of type により例外の名称と例外が提示されたときのデータの型が定まる例外を引起す (Raise) raise name parameters 例外を提示するときデータを渡す式形例外ハンドラ (Handler) exp handle pattern => exp 最初の式 exp を評価するもしパターン pattern に照合する例外が提示されると, 第二の式 exp が評価される一般形では複数のパターンが使える. どの例外ハンドラが使われるか? エラー発生を知らせるための例外 exception Ovflw; fun reciprocal(x) = if x<m then raise Ovflw else /x; (reciprocal(x) handle Ovflw=>0) / (reciprocal(y) handle Ovflw=>); ハンドラは動的スコープをもつ第一の呼び出しではある方法で例外を扱い第二の呼び出しでは別の方法で例外を扱う一般的な動的スコープ規則 run-time stack 上の最も最近に確立されたハンドラにジャンプする動的スコープを用いたのは偶然ではないエラーの取り扱いを知っているのはユーザであってライブラリの作成者が知っているわけではない - datatype 'a tree = LF of 'a ND of ('a tree)*('a tree); - exception No_Subtree; - fun lsub (LF x) = raise No_Subtree lsub (ND(x,y)) = x; > val lsub = fn : 'a tree -> 'a tree この関数は返すべき適当な値がないとき例外を提示する型付けについては後ほど

3 効率向上を図るための例外ハンドラの動的スコープ木の葉にある値を掛けあわせる関数 fun prod(lf x) = x prod(nd(x,y)) = prod(x) * prod(y); 例外を用いた最適化 fun prod(tree) = let exception Zero fun p(lf x) = if x=0 then (raise Zero) else x p(nd(x,y)) = p(x) * p(y) p(tree) handle Zero=>0 スコープ and g(h) = h() handle X => ハンドラどちらのハンドラが使われるか? ハンドラの動的スコープ変数の静的スコープとの比較 and g(h) = h() handle X => 動的スコープ : 最初の X ハンドラをみつけよ, X を上げるに到る call 鎖を上に向かって辿りながら. g(f) f() ハンドラ X 6 fun f fun g ハンドラ X 4 仮引数 h ハンドラ X 仮引数 y and g(h) = h() handle X => val x=6; (let fun f(y) = x and g(h) = let val x= h() end let val x=4 g(f) end end); 宣言の静的スコープ例外の型付け val x=6; (let fun f(y) = x and g(h) = let val x= h() end let val x=4 g(f) end end); 静的スコープ : 最初の x をみつけよ, x への参照からを辿りながら. g(f) f() val x 6 fun f fun g val x 4 仮引数 h val x 仮引数 y 型付け : raise exn 型付けの定義を思い出してみよう式 e が型 t を持つのは e が正常終了するときに返す値の型が t であるとき例外を提示するのは正常終了ではない例 : + raise X 型付け exn => value 例外を正常終了に変換する型の一致が必要例 + ((raise X) handle X => e) e の型は t でなければならない + (e handle X => e ) e, e の型は t でなければならない 3

4 例外と資源の割当て継続 (Contuations) (let val x = ref [,,3] let val y = ref [4,5,6] raise X end end) handle X => ハンドラと例外発行までの間で資源を割当ててもよい例外発行後ゴミとなりうる例メモリデータベースのロックスレッド高階関数を扱う一般的な技術関数呼出しでジャンプ (jump) や脱出 (exit) を許すコンパイラの最適化で用いられたプログラムの制御の流れを明示化する末尾再帰形 (tail recursive form) への汎用的な変換アイデア : ある式の継続は式の評価後にすべき仕事式 e の継続は e に適用された関数一般的な問題 : 単純な解はない例例 : 末尾再帰的階乗式 *x + 3*y + /x + /y /x の継続は? 除算後に残っている計算 (pseudo code) let val before = *x + 3*y fun contue(d) = before + d + /y contue (/x) end 標準的な再帰関数 fun fact(n) = if n=0 then else n*fact(n-); 末尾再帰的 fun f(n,k) = if n=0 then k else f(n-, n*k); fun fact(n) = f(n,); どうやったらこれが導出できるか? 継続を渡す (contuation-passg) 形への変換継続関数を最適化して一つの整数に階乗の継続的見方末尾再帰形の導出 fact(n) = if n=0 then else n*fact(n-) fact(9) fact(8) fact(7) n 9 n 8 n 7 fact(9) は起動されると fact(8) の結果に 9 を乗じ戻る. 従って, fact(8) 後の継続は λx. 9*x fact(7) に 8 を乗じ戻る fact(7) の継続は λy. (λx. 9*x) (8*y) fact(6) に 7 を乗じ戻る fact(6) の継続は λz. (λy. (λx. 9*x) (8*y)) (7*z) 標準的な関数 fact(n) = if n= then else n*fact(n-) 継続的な関数 contuation fact(n, k) = if n= then k() else fact(n-, λx.k (n*x) ) fact(n, λx.x) が計算するのは n! 計算の例 fact(3,λx.x) = fact(, λy.((λx.x) (3*y))) = fact(, λx.((λy.3*y)(*x))) = λx.((λy.3*y)(*x)) = 6 4

5 末尾再帰形継続の最適化 fact(n,a) = if n=0 then a else fact(n-, n*a ) 各継続は実効的にはある a についての λx.(a*x) 計算の例 fact(3,) = fact(, 3) はもともと fact(, λy.3*y) = fact(, 6) はもともと fact(, λx.6*x) = 6 第 7 回 ML より反転 (reverse) fun reverse nil = nil reverse (x::xs) = append ((reverse xs), [x]); 結合 (append) fun append(nil, ys) = ys append(x::xs, ys) = x :: append(xs, ys); 問題 reverse はどれほど効率的か? リストを一回なぞるだけでこのことができるか? より効率的な reverse 関数継続の他の用法 fun reverse xs = let fun rev (nil, z) = (nil, z) rev(y::ys, z) = rev(ys, y::z) val (u,v) = rev(xs,nil) v 制御を明示的に正常終了継続の呼出し異常終了他のことをするコンパイルの技法継続の呼出しは go to の関数記述継続渡しのスタイルは制御の流れを明示するコンパイル中の継続 SML contuation-based compiler [Appel, Steele] ) 字句解析構文解析型チェック ) λ- 計算の形に変換 3) 継続渡し形 (contuation-passg style (CPS)) に変換 4) CPS の最適化 5) 閉包変換自由変数の除去 6) スコープのネストの除去 7) レジスタ溢れ (Register spillg) n 個以上の自由変数をもつ式はなし 8) 目的とするアセンブリ言語のプログラムの生成 9) 目的とする機械語プログラムの生成まとめ構造化プログラミング Goto 文有害論 (Go to considered harmful) 例外値を返しうる構造化 (structured) ジャンプ例外ハンドラは動的スコープを使用継続プログラムの残りを表す関数末尾再帰の一般化 Lisp, ML コンパイラに使用されている 5

Microsoft PowerPoint - ProD0107.ppt

Microsoft PowerPoint - ProD0107.ppt プログラミング D M 講義資料教科書 :6 章中田明夫 nakata@ist.osaka-u.ac.jp 2005/1/7 プログラミング D -M- 1 2005/1/7 プログラミング D -M- 2 リスト 1 リスト : 同じ型の値の並び val h=[10,6,7,8,~8,5,9]; val h = [10,6,7,8,~8,5,9]: int list val g=[1.0,4.5,