プログラミング D ML 大阪大学基礎工学部情報科学科中田明夫 nakata@ist.osaka-u.ac.jp 教科書 プログラミング言語 Standard ML 入門 1,2 章 講義のねらい 関数型プログラムを知る 関数型プログラムの特徴 利点 : 数学的な裏づけ プログラムの正しさの証明が容易 リスト処理, 高階関数, 再帰関数定義 リストやツリーなどのデータ構造は再帰的に定義 再帰関数で扱うとプログラミングが容易 再帰を用いないと記述が困難な関数の存在 欠点 : 実行速度やメモリ効率は手続き型プログラムに劣る 正しいプログラムを手っ取り早く作成したい場合に有用 動作確認後に手続き型プログラムに変換すれば 効率化もできるという立場 2005/11/28 プログラミングD -ML- 3 関数型プログラミング言語 LISP, scheme, ML, Haskell など 詳細は http://www.cs.nott.ac.uk/~gmh/faq.html http://www.score.is.tsukuba.ac.jp/~minamide /functional.html 参照 2005/11/28 プログラミング D -ML- 4 授業の進め方 教科書 プログラミング言語 Standard ML に沿って進める 参考書 プログラミング言語 ML の例題で説明することもある 授業スライド 以下のURLに順次アップロードする http://www-tani.ist.osaka-u.ac.jp/moodle/ はじめに 関数型プログラムはどこで使われているか? Emacs sawfish Microsoft Excel Pascal Cなどの言語でも関数型プログラミングのセンスは有用 なぜ (Standard) MLか? 処理系がしっかりしている (Standard ML) 型定義 型が正しいかコンパイル時に検査 ( 型検査 ) Pascalと同じ 変数の型 関数の引数や返り値の型などをいちいち宣言しなくてもよい ( 型推論 ) 純粋な関数型言語の中では使用人口が多い 多くの大学で教えられている 2005/11/28 プログラミング D -ML- 5 2005/11/28 プログラミング D -ML- 6
Standard ML(SML/NJ) ML のすぐれた処理系 ( のひとつ ) http://www.smlnj.org/ 他には CAML MoscowML など 対話的な使用環境 インタプリタのように使用できる 即座に実行し結果を確認 動作確認しながらプログラミング可能 実際には入力毎に自動コンパイル プログラムをまとめてファイルに記述し 一括コンパイル & 実行も可 システムの起動 終了 対話モードでの使用 UNIXのシェルプロンプトから起動 % sml ( リターン ) Standard ML 起動時のメッセージ - ML 処理系のプロンプト ( トップレベル ) 以降 MLプログラムを入力 文の末尾に ; ( セミコロン ) 文の途中で改行 プロンプトが = に変化( ; の入力で元に戻る ) 終了はCtrl-D 無限ループなどでプログラムが止まらない場合は まずCtrl-Cでトップレベルに戻す 2005/11/28 プログラミング D -ML- 7 2005/11/28 プログラミング D -ML- 8 Emacs での利用 Emacs で利用する利点 対話的に打ち込んだプログラムを容易に保存可能 あらかじめプログラムを作成 編集してからの実行も容易 拡張子.sml EmacsでのSML 支援環境 sml-mode 3.3 以下のサイトで配布 ftp://ftp.research.belllabs.com/dist/smlnj/contrib/emacs/sml-mode-3.3.tar.z ドキュメント ( 英文 ) http://www.smlnj.org/doc/emacs/sml-mode.html sml-mode 3.3 のインストール 以下の URL からダウンロード http://www-higashi.ist.osakau.ac.jp/~nakata/pro-d/sml-mode-3.3.tar.z 以下のドキュメントに従ってインストール http://www-higashi.ist.osaka- u.ac.jp/~nakata/pro-d/sml-mode-3.3- install.txt 2005/11/28 プログラミング D -ML- 9 2005/11/28 プログラミング D -ML- 10 式の入力と評価 MLプログラム = 式 ( または宣言文 ) MLプログラムの実行 = 式の評価 ( 値を計算 ) MLにおける 式 定数 整数 (int 型 ) 実数(real 型 ) 真理値(bool 型 ) 文字列(string 型 ) など 演算子を用いた式 四則演算 比較演算など 条件式 if then else etc. 2005/11/28 プログラミング D -ML- 11 式 ( 整数 :int 型 ) 50; val it = 50 : int 1+3; val it = 4 : int 3*5; val it = 15 : int 60-100; val it = ~40 : int -100; エラーメッセージ ~100; val it = ~100 : int 式の評価 ( 計算 ) 結果およびその型 足し算 掛け算 引き算は普通に書ける マイナス記号は ~ - はマイナス記号としては使えない 2005/11/28 プログラミング D -ML- 12
式 ( 整数 :int 型割り算 ) 50/4; Error: overloaded variable not defined at type symbol: / type int 50 div 4; val it = 12 : int 100 mod 7 ; val it = 2 : int 整数の割り算は / ではなく div ( 商 ) mod ( 余り ) を使う 式 ( 実数 :real 型 ) 2.0-3; Error: operator and operand don t agree operator domain real * real operand : real * int 2.0-3.0; val it = ~1.0: real 2.0 / 4.5; val it = 0.444444444444 : real 20.0 mod 5.0; エラーメッセージ 3.1415999E40; 実数と整数の演算はできない + - * は整数 実数両方に対して使える 実数の割り算は / を使う x.xxeyy は val it = 3.1415999E40 : real (x.xx)*10^(yy) を表す 2005/11/28 プログラミング D -ML- 13 2005/11/28 プログラミング D -ML- 14 式 ( 比較 :bool 型 ) 3=4-1; val it = true : bool 5-6=3-3; val it = false : bool 3 > ~4; val it = true: bool 3 <> 7; val it =true: bool 2.0 = 2.0 ; Error: operator and operand don t agree [equality type required] operator domain Z * Z operand : real * real 2.0 >= 3.0; val it = false: bool 整数の比較 : 任意の等号 不等号が使用可 実数の比較 : 大小比較のみ可 2005/11/28 プログラミング D -ML- 15 式 ( 比較 :bool 型 ) 実数型の値同士は =, <> による比較はできない SML の仕様 実数の浮動小数点演算には一般に誤差あり 例 ) (1.0/3.0)*3.0 = 1.0 は数学的には真だが 浮動小数点演算では真になるとは限らない 等しいか否かの比較は余り意味がない 実数 x,y が等しいことを比較したいとき x-y <epsilon を調べる epsilon: 任意に決めた小さな正の実数 2005/11/28 プログラミング D -ML- 16 式 ( 文字 :char 型 ) #"c"; val it = #"c": char #"string"; Error: character constant not length 1 ord #"t"; val it =116: int chr 67 ; val it = #"C" : char 文字定数は #"( 文字 )" と書く 2 以上の長さの文字列は文字定数に指定できない ( エラー ) 文字定数からその文字コード ( 整数 ) を返す関数 ord 文字コードからそれが表す文字を返す関数 chr 2005/11/28 プログラミング D -ML- 17 式 ( 文字列 :string 型 ) "begin end"; val it = "begin end" :string "begin" ^ "end"; val it = "beginend" :string "c"; val it = "c" : string 文字列定数は "( 文字列 )" と書く 2 つの文字列を連結した文字列を返す演算子 ^ 一文字でも文字列 ( 文字定数 #"c" とは型が異なる ) 2005/11/28 プログラミング D -ML- 18
式 ( 型変換 ) trunc 1.5; val it = 1: int round 1.5; val it =2 : int 他に, floor, ceil real 5; val it=5.0: real 実数から整数への変換 整数から実数への変換 式 ( 論理式 :bool 型 ) 1 > 2 andalso 3< 4; 論理演算子 val it = false: bool andalso,orelse,notを用いて 1< 2 orelse 3 > 4; 論理式を記述可能 val it =true : bool not( 1.0 < 3.0) andalso 4< 5 orelse 5 < 6; val it=true: bool true andalso false orelse true; val it=true : bool ("cat" ^ "dog") = "catdog" andalso round(1.5)=2; val it=true : bool and, or でないことに注意 2005/11/28 プログラミング D -ML- 19 2005/11/28 プログラミング D -ML- 20 式 (if then else ) if (1 > 2 andalso 3< 4) then #"C" else #"F"; val it = #"F": char if (1< 2 orelse 3 > 4) then 3+4 else 5+6; val it =7 : int if ( 3 < 4) then (3 > 4) else (5<6); val it=false: bool 式 (if then else ) if 1 then #"C" else #"F"; Error: case object and rules don t agree. if の後は bool 型でなくてはいけない if (1< 2) then 3 else 5.0; Error: type of rules don t agree. then 節と else 節は同じ型でなくてはいけない if false then true else false; val it=false:bool if ( 論理式 ) then ( 式 1) else ( 式 2) ( 論理式 ) が真なら ( 式 1) 偽なら ( 式 2) の値を返す 2005/11/28 プログラミング D -ML- 21 2005/11/28 プログラミング D -ML- 22 練習問題 1 変数の束縛 次の式に対して ML はどう応答するか? 5.0-4.2/1.4; "foo"^"bar"^""; if 6<10 then 6.0 else 10.0; 次の ML の式はエラーを含む どこが間違っているか説明せよ if 2<3 then 4; 6+7 DIV 2; 1.0<2.0 or 3>4; 2005/11/28 プログラミング D -ML- 23 名前 ( 識別子 ) に値を結びつける (val 宣言 ) val ( 名前 ) =( 式 ) ; 一般の手続き型における代入とよく似ている val radius = 5.0; val radius = 5.0: real val circumference = radius * 2.0 * 3.1415; val circumference = 31.415 : real 式だけを書くと it という識別子に値を束縛 5; val it = 5 : int; 2005/11/28 プログラミング D -ML- 24
束縛と代入の違い 一般の手続き型における代入との違い 結び付けているだけなので型が変わってもよい val radius = 5.0; val radius = 5.0: real val radius = 15; val radius = 15 : int val radius = cat ; val radius = cat : string 2005/11/28 プログラミング D -ML- 25 環境 環境 = 各変数と束縛された値の対応関係 例 :{x 1, y 2.5, radius cat, } トップレベルの環境 ML 処理系の起動時の環境 基本的な演算や入出力などを行う関数があらかじめ定義 ( 束縛 ) されている ユーザによる代入 ( 束縛 ) によって変化 それ以外の環境 関数実行時の環境など ( 詳細は後述 ) 2005/11/28 プログラミング D -ML- 26 ファイルからのプログラム入力 use file ; file: プログラムが書かれたテキストファイル 拡張子は.sml 練習問題 2 次のval 宣言の列を順番に実行して最終的に作られる環境 ( 各変数名と値の対応 ) を示せ ( 簡単のため 下記実行前のトップレベルの環境は空であるとする ) val a=3; val b=98.6; val a= three ; val c=a^(chr (round b)); 2005/11/28 プログラミング D -ML- 27 2005/11/28 プログラミング D -ML- 28 関数の定義 例 ) 整数を 2 倍する関数 - fun double x = x * 2; val double = fn : int -> int 一般に double という名前に 整数から整数への関数 を束縛 fun f p = body ; 引数 p をとる関数 f の定義は body である 関数適用 ( 関数の実行 ) -double 2; val it = 4 : int 引数の括弧は省略可能 上は double(2); と同じ - double 3 + 1; val it = 7 : int 上の double の引数は (3+1) ではなく 3 -double (3+1); val it = 8 : int 2005/11/28 プログラミング D -ML- 29 2005/11/28 プログラミング D -ML- 30
関数適用 : 括弧省略時の解釈 - double (double 2) + 3; val it = 11 : int - double double 2 + 3; エラーメッセージ ((double double) 2) + 3; と解釈された 関数 double の引数に関数 double を適用 関数 doubleの型は整数から整数を返す関数 型エラー 関数適用は左結合 f g h x; は (((f g) h) x); と解釈 2005/11/28 プログラミング D -ML- 31 関数適用 : ML での慣習 なぜ普通に f(x) と書かないのか? 普通に書いても OK( 文法的に正しい ) ただし 後に述べる高階関数 ( 関数を返す関数 ) を扱うとき便利 f x y; ((f x) y) 関数 f は引数 xをとり ある関数を返す その関数の引数にyを適用 f (x,y); という書き方もOK 関数 f に引数の組 (x,y) を適用 MLでは慣習として (f x) という書き方を用いる λ 計算 ( 関数型言語の計算モデル ) に由来 この授業では 原則として教科書に従い (f x) という書き方をする 2005/11/28 プログラミング D -ML- 32 式の評価 Eval(E,exp)=v 環境 E={x 1 v 1,,x i v i, } の下で式 exp を評価した値が v 例 ) E={y 2} Eval(E,y+2) =Eval(E,y)+Eval(E,2) =2+2=4 式の評価 : 関数適用を含む場合 Eval(E,exp)=v 環境 E={x 1 v 1,,x i v i } の下で式 expを評価した値がv 例 ) E={y 2,double (xからx*2への関数 )} Eval(E,double y + 4) =Eval(E,double y)+eval(e,4) =Eval(E,double 2)+4 Eval(E,y)=2, Eval(E,4)=4より =Eval(E {x 2},x*2)+4 関数 doubleの仮引数 xに実引数 yの値を束縛した環境で評価 元の環境 Eは変更しない ( 関数の評価が終わると元に戻る ) = 2*2+4 = 8 2005/11/28 プログラミング D -ML- 33 2005/11/28 プログラミング D -ML- 34 局所変数 : let 構文 val pi = 3.141592 fun f r = 2.0*pi*r f 10.0 end; val it=62.83184 : real 式 : 一時的に変数や関数を束縛し その環境で in ~ end の間に書かれた式を評価 終了すると元の環境に戻る この構文自体が式なので 式の中にも書ける 2005/11/28 プログラミング D -ML- 35 局所変数の使用例 以下の実行結果を予想し 実際に確認してみよう val x=3; val x=2 x*4 end * x; 2005/11/28 プログラミング D -ML- 36
局所変数の使用例 以下の実行結果を予想し 実際に確認してみよう val x=3; val x=2 x*4 end * x; この時点の環境 ( トップレベル ) は E={x 3, } ここで局所的な環境 E が作られる E =(E\{x 3}) {x 2} (x の値を上書き ) ここから end までは環境 E で評価 Eval(E,x*4)=Eval(E,x)*Eval(E,4)=2*4=8 ここで環境はEに戻る (xの値は元に戻る) Eval(E,(let val x=2 in x*4 end)*x) =Eval(E,x*4)*Eval(E,x) (let 式の中はE で評価 ) =8*3=24 2005/11/28 プログラミングD -ML- 37 練習問題 3 次の関数を定義せよ 身長と体重から 肥満度の尺度 BMI= 体重 (kg) 身長 (m) 2 を求める関数 bmi 身長と体重から BMI<18.5 なら Underweight, 18.5<=BMI<25.0 ならば Normal, 25.0<=BMI ならば Overweight という文字列を返す関数 bmicategory [let 式を用いて 関数 bmi を局所関数として使用せよ ] 3 つの整数から それらの最大値を返す関数 max3 2005/11/28 プログラミング D -ML- 38 再帰的関数 fun factorial n = if n=0 then 1 else n*(factorial (n-1)); val factorial = fn : int -> int factorial 6; val it = 720 : int nの階乗 n! を求める関数 factorial 一般に関数本体で自分自身を呼び出す関数 2005/11/28 プログラミング D -ML- 39 再帰的関数の等式トレース fun factorial n = if n=0 then 1 else n*(factorial (n-1)); factorial 2 == if 2=0 then 1 else 2*(factorial (2-1)) == 2*(factorial 1) == 2*(if 1=0 then 1 else 1*(factorial (1-1))) == 2*(1*(factorial 0)) == 2*(1*(if 0=0 then 1 else 1*(factorial 0-1))) == 2*(1*(1)) == 2 2005/11/28 プログラミング D -ML- 40 再帰的関数の評価 fun factorial n = if n=0 then 1 else n*(factorial (n-1)); Eval({},factorial 2) = Eval({n 2},if n=0 then 1 else n*(factorial (n-1)) ) = 2*(factorial 1) = 2*Eval({n 1},if n=0 then 1 else n*(factorial (n-1)) ) = 2*1*(factorial 0) = 2*1*Eval({n 0},if n=0 then 1 else n*(factorial(n-1)) ) = 2*(1*(1)) = 2 練習問題 4 次の関数 fに対して (f 2 3) の値を予想せよ fun f x y= fun g z = if z<=0 then 1 else x*(g (z-1)) y+(g (y-x)) end; 2005/11/28 プログラミング D -ML- 41 2005/11/28 プログラミング D -ML- 42