====================================================================== 2005年度「計算機ソフトウェア工学」(月曜2限) 住井担当部分予定 ====================================================================== 6/20(月) 関数型言語「ML」入門I (式・値・型、変数、関数、再帰関数) 6/27(月) 関数型言語「ML」入門II (高階関数、再帰型、多相型、多相関数) 7/ 4(月) 関数型言語の基礎理論I (型なしλ計算) 7/11(月) 関数型言語の基礎理論II (単純型つきλ計算、抽象型) ====================================================================== 追加説明: 変数定義のスコープ ====================================================================== MLでは、 let x = 式 のような変数定義は 新しい変数xを作って、その値を定義する という意味になる。もし以前に同名の変数xが定義されていても、そのxと新し いxは別々の変数とみなされる。 例: ---------------------------------------------------------------------- # let x = 3 ;; val x : int = 3 # let f () = x ;; val f : unit -> int = # let x = 7 ;; val x : int = 7 # f () ;; - : int = 3 ---------------------------------------------------------------------- 関数fは最初の変数xを参照しているので、後から別の変数xを定義しても、fの 返り値は変わらない。このような動作のことを「________________________」 という。 一般に、変数定義の有効範囲のことを「________________」という。スコープ を自分で制限したいときは、 let x = 式1 in 式2 のような式を書くこともできる。このように定義した変数xは、式2の中でのみ 使うことができる。 例: ---------------------------------------------------------------------- # let y = 2 in y * 5 ;; - : int = 10 # y ;; Characters 0-1: y ;; ^ Unbound value y ---------------------------------------------------------------------- 別の例: ---------------------------------------------------------------------- # let z = "foo" ;; val z : string = "foo" # let z = "bar" in z ^ z ;; - : string = "barbar" # z ^ z ;; - : string = "foofoo" ---------------------------------------------------------------------- さらに別の例: ---------------------------------------------------------------------- # let v = 3 in let v = v + 7 in v * v ;; - : int = 100 ---------------------------------------------------------------------- 今では珍しいが、fのような関数を呼び出したときに、後から定義したxの値が 使われる言語もある。そのような動作を「________________________」という。 動的スコープを採用している言語としては、たとえばEmacsでも利用されてい るLispがある。実際に、Emacsの*scratch*バッファに ---------------------------------------------------------------------- (let ((x 3)) ; 変数xの値を3と定義する (defun f () x) ; 「0個の引数を受け取り、xを返す」関数fを定義する (let ((x 7)) ; 別の変数xの値を7と定義する (f))) ; fを呼び出す ---------------------------------------------------------------------- というプログラムを入力し、C-jで実行すると、結果は3ではなく7になる。 ちなみに、Lispの動的スコープは当初から意図された動作ではなく、実装の 「バグ」が「仕様」になってしまったという歴史がある。 ====================================================================== 追加説明: 部分適用 ====================================================================== カリー化された関数では、引数の一部だけを先に与えることができる。これを 「________________」という。部分適用は、一部の引数だけを固定したいとき に便利である。 例: ---------------------------------------------------------------------- # let distance x y = sqrt (x *. x +. y *. y) ;; val distance : float -> float -> float = # let distance1 = distance 3.0 ;; val distance1 : float -> float = # distance1 0.0 ;; - : float = 3. # distance1 4.0 ;; - : float = 5. ---------------------------------------------------------------------- ただし、 ・(1番目の引数ではなく)2番目以降の引数を先に与えたいとき や ・カリー化されていない関数を部分適用したい場合 は、そのための関数を定義するか、後で述べる「無名関数」を利用する必要が ある。 例: ---------------------------------------------------------------------- # let distance x y = sqrt (x *. x +. y *. y) ;; val distance : float -> float -> float = # let distance2 x = distance x 3.0 ;; val distance2 : float -> float = ---------------------------------------------------------------------- 別の例: ---------------------------------------------------------------------- # let distance (x, y) = sqrt (x *. x +. y *. y) ;; val distance : float * float -> float = # let distance1 y = distance (3.0, y) ;; val distance1 : float -> float = # let distance2 x = distance (x, 3.0) ;; val distance2 : float -> float = ---------------------------------------------------------------------- なお、一般に「関数fに引数xを与えて呼び出す」ことを「fをxに________する」 という。「関数を引数に適用する」のであって、「引数を関数に適用する」と は言わないことに気をつける。 ====================================================================== 追加説明: 末尾呼び出し、末尾再帰、アキュムレータ ====================================================================== 一般に関数呼び出しにおいて、もし戻ってきてから行うべき計算がなければ、 レジスタや戻り先アドレスをセーブする必要もないので、スタックへの待避や 復帰を完全に省略することができる。たとえば、 let distance x y = sqrt (x *. x +. y *. y) という関数distanceでは、sqrtを呼び出した後に行うべき計算がないので、レ ジスタや戻り先アドレスをセーブせず、いきなり関数sqrtの先頭へジャンプし てしまってよい。このような関数呼び出しのことを「____________」という。 末尾呼び出しは、普通の関数呼び出しと違って、ただのジャンプのようにコン パイルできる。 特に、再帰呼び出しが末尾呼び出しになっていると、ただのループのようにコ ンパイルできる。このような再帰を________________という。たとえば let rec gcd m n = if m = n then m else if m < n then gcd m (n - m) else gcd (m - n) n という関数gcdは、C言語で int gcd(int m, int n) { while (m != n) if (m < n) n = n - m; else m = m - n; return m; } と書いたのと同じようにコンパイルされる。逆に、ループで書ける計算は、末 尾再帰でも書けることがわかっている。 末尾再帰はスタックを消費しないので、再帰が極めて深い（たとえばgcdでmや nが極めて大きい）場合でも、オーバーフローせず実行できる。 例: ---------------------------------------------------------------------- # let rec f x = f (x + 1) ;; (* 末尾再帰 *) val f : int -> 'a = # f 0 ;; (* 止まらないが、エラーも出ない *) Interrupted. # let rec f x = f (x + 1) + 2 ;; (* 末尾再帰ではない *) val f : int -> int = # f 0 ;; Stack overflow during evaluation (looping recursion?). ---------------------------------------------------------------------- 末尾でない再帰を、末尾再帰に書き換えられることもある。たとえば、 let rec sum n = if n = 0 then 0 else n + sum (n - 1) という関数sumは末尾再帰的でないので、大きな数を入れるとスタック・オー バーフローが起ってしまう。 # sum 100000 ;; Stack overflow during evaluation (looping recursion?). しかし、末尾再帰的な補助関数 let rec sum' a n = if n = 0 then a else sum' (n + a) (n - 1) を使って let sum = sum' 0 と定めれば、スタック・オーバーフローは起きない（ただし、答えが大きすぎ て、Objective Camlが32-bit CPUで扱える整数の範囲を越える）。 # sum 100000 ;; - : int = 705082704 この補助関数sum'は、nから1までの整数の和を、返値ではなく引数aに集めて いく、という関数である。このように、返値のかわりに答えを集めていく引数 のことを「____________________________」という。sumのように答えを集め ていく関数は、アキュムレータを使って末尾再帰的に書くことができる（ただ し (x + y) + z = x + (y + z) のような結合法則が必要となる）。 ====================================================================== レポート課題6 ====================================================================== 提出方法: sumii ＠ ecei ．tohoku ．ac ．jp までメール（紙は受け付けない） 期限: 2005/7/3(日) 形式: http://qube3.kb.ecei.tohoku.ac.jp/~koba/class/soft-eng/ に準じる 1. アキュムレータを使って、次の関数を末尾再帰的に書け。 let rec power m n = if n = 0 then 1 else if n mod 2 = 0 then power (m * m) (n / 2) else m * power m (n - 1) 2. 同じ関数を、再帰ではなくループを用いて、C言語で書け。ただし、本質 的なアルゴリズム（計算量のオーダー）を変えてはならない。 3. 1の答えと2の答えをよく見比べ、気づいたことをできるだけ詳しく述べよ。 ====================================================================== 追加説明: Objective Camlの終了方法 ====================================================================== UNIXの通常の端末（デフォルトの設定のktermなど）からocamlを起動した場合 は、「入力の終了」を表すC-d（コントロールキーを押しながらdを打つ）を打 てば、ocamlを正常に終了できる。これは標準入力を使用する、ほとんどのコ マンドに共通である。 ---------------------------------------------------------------------- Objective Caml version 3.08.2 # 1 + 2 ;; - : int = 3 # (* ここでC-dを打つ *) Process inferior-caml finished ---------------------------------------------------------------------- また、無限ループなど計算を中断したい場合は、「プロセスへの割り込み」を 表すC-cを打てばよい。これも、ほとんどのコマンドに共通である。 ---------------------------------------------------------------------- # let rec gcd m n = if m = n then m else if m > n then gcd (m - n) n else gcd m (n - m) ;; val gcd : int -> int -> int = # gcd 3 (-7) ;; (* リターンの後にC-cを打つ *) Interrupted. ---------------------------------------------------------------------- ただし、emacsのM-x run-camlなどでocamlを起動した場合は、まずC-cを打っ てから、C-dやC-cなどを打つ。これもemacsのバッファでコマンドを実行する ときは共通である（M-x shellなど）。 情報系ないし電気系の大学生は、UNIXぐらい使いこなせないと「恥ずかしい」 だけでなく、進学・就職してから必ず困るので、今のうちに慣れておこう！ ====================================================================== 追加説明: 高階関数としての微分・積分 ====================================================================== 数学にも出てくる高階関数の例として、微分や積分がある。たとえば、「浮動 小数から浮動小数への関数fを受け取り、その導関数f'を近似して返す」とい う高階関数diffは let diff f = let f' x = (* fの導関数f'を定義 *) let dx = 0.0000001 in (* 無限小を近似 *) let dy = f (x +. dx) -. f x in dy /. dx in f' と書ける。 [問] この関数diffの型は何になるか。 例: ---------------------------------------------------------------------- # let f x = x *. x ;; val f : float -> float = # let f' = diff f ;; val f' : float -> float = # f' 1.0 ;; - : float = 2.00000010108780657 # f' 2.0 ;; - : float = 4.00000009115331068 # f' 3.0 ;; - : float = 6.00000008788015293 ---------------------------------------------------------------------- また、「関数fと実数x0, x1を受け取って、fをx0からx1まで積分した結果を近 似して返す」という高階関数integralは let integral f x0 x1 = let dx = (x1 -. x0) /. 1000.0 in let rec sum x = (* fをx0からxまで積分する補助関数 *) if x <= x0 then 0.0 else sum (x -. dx) +. (f x *. dx) in sum x1 と書ける。 [問] この関数integralの型は何になるか。 例: ---------------------------------------------------------------------- # integral sin 0.0 3.14 ;; - : float = 1.99999958892671925 ---------------------------------------------------------------------- [問] 関数integralの中に現れる関数sumを末尾再帰で書き直せ。 ====================================================================== 追加説明: リストに関する高階・多相関数の例 ====================================================================== 関数List.mapは、関数fと、リストlを受け取り、lの個々の要素にfを適用した 結果のリストを返す。 List.map f [e1; e2; e3; ...] = [f e1; f e2; f e3; ...] 例: ---------------------------------------------------------------------- # let f x = (x < 3) ;; val f : int -> bool = # let l = [1; 2; 3; 4; 5] ;; val l : int list = [1; 2; 3; 4; 5] # List.map f l ;; - : bool list = [true; true; false; false; false] # List.map (fun x -> x < 3) [1; 2; 3; 4; 5] ;; - : bool list = [true; true; false; false; false] ---------------------------------------------------------------------- 悪い例: ---------------------------------------------------------------------- # List.map (fun x -> x + 1) ["foo"; "bar"; "baz"] ;; Characters 27-32: List.map (fun x -> x + 1) ["foo"; "bar"; "baz"] ;; ^^^^^ This expression has type string but is here used with type int ---------------------------------------------------------------------- List.mapの定義の例: ---------------------------------------------------------------------- let rec map f l = match l with [] -> [] | e :: l' -> f e :: map f l' ---------------------------------------------------------------------- 関数List.filterは、boolを返す関数fと、リストlを受け取り、fがtrueとなる 要素を選んでリストとして返す。たとえば、もし f e1 = true f e2 = false f e3 = true f e4 = false f e5 = true ... だったら List.filter f [e1; e2; e3; e4; e5; ...] = [e1; e3; e5; ...] 例: ---------------------------------------------------------------------- # List.filter (fun x -> x < 3) [1; 2; 3; 4; 5] ;; - : int list = [1; 2] # List.filter (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5] ;; - : int list = [2; 4] ---------------------------------------------------------------------- 悪い例: ---------------------------------------------------------------------- # List.filter (fun x -> x + 1) [1; 2; 3; 4; 5] ;; Characters 22-27: List.filter (fun x -> x + 1) [1; 2; 3; 4; 5] ;; ^^^^^ This expression has type int but is here used with type bool ---------------------------------------------------------------------- List.filterの定義の例 ---------------------------------------------------------------------- let rec filter f l = match l with [] -> [] | e :: l' -> if f e then e :: filter f l' else filter f l' ---------------------------------------------------------------------- 最後に、やや複雑な高階多相関数として、List.fold_leftがある。 List.fold_leftは、関数fと、初期値a0と、リスト[e1; e2; e3; e4; ...]を受 け取り、 let a1 = f a0 e1 in let a2 = f a1 e2 in let a3 = f a2 e3 in let a4 = f a3 e4 in ... を計算した結果を返す。これは、たとえば以下のような「よくある計算」をパ ターン化・一般化したものである。 ・整数リスト[e1; e2; e3; e4; ...]の要素の和を求める let a1 = 0 + e1 in let a2 = a1 + e2 in let a3 = a2 + e3 in let a4 = a3 + e4 in ... List.fold_leftで書くと List.fold_left (+) 0 [e1; e2; e3; e4; ...] ・整数リスト[e1; e2; e3; e4; ...]の要素の最大値を求める let a1 = max min_int e1 in (* min_int = OCamlで最小のint *) let a2 = max a1 e2 in let a3 = max a2 e3 in let a4 = max a3 e4 in ... List.fold_leftで書くと List.fold_left max min_int [e1; e2; e3; e4; ...] ・論理値リスト[e1; e2; e3; e4; ...]の要素中のtrueの数を求める let a1 = 0 + (if e1 then 1 else 0) in let a2 = a1 + (if e2 then 1 else 0) in let a3 = a2 + (if e3 then 1 else 0) in let a4 = a3 + (if e4 then 1 else 0) in ... List.fold_leftで書くと List.fold_left (fun a b -> a + (if b then 1 else 0)) 0 [e1; e2; e3; e4; ...] List.fold_leftの定義の例: ---------------------------------------------------------------------- let rec fold_left f a l = match l with [] -> a | e :: l' -> fold_left f (f a e) l' ---------------------------------------------------------------------- 参考: map, fold_left, filterといった関数には様々な性質がある。たとえば List.map (compose f g) = compose (List.map f) (List.map g) など。ただし、composeは関数を合成する高階関数。 # let compose f g = fun x -> g (f x) ;; val compose : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c = これらの性質を利用すると、「わかりやすいが効率の悪い」アルゴリズムから、 効率の良いアルゴリズムを導出できる場合がある（データマイニングなど）。 ====================================================================== 追加説明: その他の多相関数の例 ====================================================================== 多相関数は特に木やリストなどの多相データ型と関連して用いることが多いが、 先のcomposeのように、そうではない例もある。 例1: 恒等関数id let id x = x 例2: 「関数fと値xを受け取り、fをxに適用した結果を返す」高階関数apply let apply f x = f x [問] idとapplyの型はそれぞれ何になるか。 例3: 「カリー化されていない関数fを受け取り、カリー化して返す」高階関数curry # let curry f = fun x -> fun y -> f (x, y) ;; val curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c = 例4: 「カリー化された関数fを受け取り、非カリー化して返す」高階関数uncurry # let uncurry f = fun (x, y) -> f x y ;; val uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c =