Standard MLパラダイムマルチパラダイム: 関数型、命令型
型付け強い、静的、推論あり
主な処理系MLton, MLWorks, Moscow ML, Poly/ML, SML/NJ, SML.NET
方言Alice
Standard ML (SML) は、プログラミング言語MLの標準ないし1方言である。The Definition of Standard ML で型付け規則と操作的意味論が与えられている。1990年に初版が出版され、1997年に単純化された改版が出版されている[1]。 Standard ML は基本的には関数型言語である。Standard ML で書かれたプログラムの大部分は、値を計算すべき式で構成されている。 他の関数型言語と同様、Standard ML の鍵となる機能は関数であり、それによって抽象化を行っている。例えば、階乗関数は次のように表される。fun factorial x = if x = 0 then 1 else x * factorial (x-1) Standard ML のコンパイラは、このようにユーザーが全くデータ型を指定していない記述から int -> int という型を静的に推論する必要がある。すなわち、x が整数の式でしか使われていないことから、それ自身も整数だと推論し、関数内の式で生み出される値も全て整数であると推論しなければならない。 同じ関数を節関数定義 (clausal function definition) で表現することもできる。その場合 if-then-else という条件分岐を 。で区切られた一連のテンプレートに置換し、個々のテンプレートは特定の値について評価される。各テンプレートは順番に試行され、一致するものを見つけることになる。fun factorial 0 = 1 。factorial n = n * factorial (n - 1) 局所関数を使い、この関数を末尾再帰に書き換えることもできる。fun factorial x = let fun tail_fact p 0 = p 。tail_fact p n = tail_fact (p * n) (n - 1) in tail_fact 1 x end let-式の値は、 in と end に挟まれた式の値になる。 Standard ML には高度なモジュールシステムがあり、プログラムを論理的に関連する型と値の宣言の structure による階層に分解することができる。SMLモジュールは単に名前空間を制御するだけでなく、抽象化の役割も持っており、プログラマはこれを使って抽象データ型を定義できる。 主に3つの構文要素でSMLモジュールシステムが構成される。signature と structure と functor である。structure はモジュールそのものである。型、式、値、structure (substructure) の集合体であり、それらを1つの論理単位にパッケージ化している。signature はインタフェースであり、一般にその structure の型として認識される。その structure が提供する全ての実体の名前を指定し、型要素のアリティ、値要素の型、substructure の signature も指定する。型要素の定義はエクスポートする場合もしない場合もある。定義を隠蔽した型要素を「抽象型 (abstract type)」と呼ぶ。functor は structure から structure への関数である。すなわち、functor は1つ以上の引数を受け付け（通常、signature で指定した structure）、結果として structure を生成する。functor はジェネリックなデータ構造とアルゴリズムを実装するのに使われる。 例えば、キューデータ構造の signature は次のようになる。signature QUEUE = sig type 'a queue exception Queue val empty : 'a queue val insert : 'a * 'a queue -> 'a queue val isEmpty : 'a queue -> bool val peek : 'a queue -> 'a val remove : 'a queue -> 'a * 'a queueend この signature はキューのパラメータ化された型 queue を提供するモジュールを記述しており、それには Queue という例外、キューの基本操作を提供する5つの値（うち4つは関数）を記述している。これを使ってキューデータ構造を実装した structure を書くことができる。structure TwoListQueue :> QUEUE = struct type 'a queue = 'a list * 'a list exception Queue val empty = ([],[]) fun insert (a,(ins,outs)) = (a::ins,outs) fun isEmpty ([],[]) = true 。isEmpty _ = false fun peek ([],[]) = raise Queue 。peek (ins,[]) = hd (rev ins) 。peek (ins,a::outs) = a fun remove ([],[]) = raise Queue 。remove (ins,[]) = let val newouts = rev ins in (hd newouts,([],tl newouts)) end 。remove (ins,a::outs) = (a,(ins,outs)) end この定義では、TwoListQueue が QUEUE という signature の実装であることを宣言している。さらに（:> で指定されている） opaque ascription により、この signature（すなわち queue）で定義が提供されていない型要素は抽象型として扱うことを示している。すなわち、ここではキューが2つのリストで定義されているが、それはモジュール外部には見せない。structure 本体には signature に挙げられている全要素に対応した実装が記述される。 structure を使うには、ドット記法でその型や値といったメンバーにアクセスすればよい。例えば、文字列のキューの型は string TwoListQueue.queue、空のキューは TwoListQueue.empty、q というキューの最初の要素を削除するには TwoListQueue.remove q と書けばよい。 SMLの処理系の多くは対話型のトップレベルを備えており、それに入力することで、コード断片は容易に実行できる。これは、入力された式の型を推論し評価する。例えば、SML/NJ では、次のように起動する。 $ sml Standard ML of New Jersey v110.52 [built: Fri Jan 21 16:42:10 2005] - コードは - のプロンプトの位置に入力する。例えば 1+2*3 を計算する場合、次のようになる。 - 1 + 2 * 3; val it = 7 : int トップレベルは式の型が int であると推論し、その値 7 を表示している。 次のようなプログラム hello.sml があるとする。print "Hello world!\n"; これをMLtonでコンパイルする場合、次のように入力する。$ mlton hello.sml 実行は次の通り。$ ./helloHello world!$ マージソートのアルゴリズムについては、当該記事を参照されたい。ここではマージソートを3つの関数 split、merge、MergeSort で実装している。 関数 split は、追加の引数を持つ局所関数 split_iter を使って実装している。これは末尾再帰の実装に便利な手法である。この関数はSMLのパターンマッチング構文を使っており、リストが空でないケース (x::xs) と空のケース ([]) を定義している。 (* 要素のリストを与えられ、それをほぼ同じサイズの * 2つに分割する。 * O(n) *) local fun split_iter (x::xs, left, right) = split_iter(xs, right, x::left) 。 split_iter ([], left, right) = (left, right) in fun split(x) = split_iter(x,[],[]) end; local-in-end という構文を let-in-end という構文に置き換えると、等価な定義が得られる。 fun split(x) = let fun split_iter (x::xs, left, right) = split_iter(xs, right, x::left) 。 split_iter ([], left, right) = (left, right) in split_iter(x,[],[]) end; split と同様、merge も局所関数 merge_iter を使って効率化する。merge_iterではいくつかのケース（渡されたリストがどちらも空でない場合、一方が空の場合、両方が空の場合）を定義している。 _ はワイルドカード・パターンを表している。 この関数は2つの昇順のリストを1つの降順のリストにマージする。逆転するのはSMLにおけるリストの構造によるものである。SMLではリストを非平衡2分木で実装しているため、要素を先頭に付与するのは容易だが、最後尾に付与するのは非効率的である。 (* 2つの昇順リストを1つの降順リストにマージする。 * 関数 lt(a,b) は a < b と同値 * O(n) *) local fun merge_iter (out, left as (x::xs), right as (y::ys), lt) = if lt(x, y) then merge_iter(x::out, xs, right, lt) else merge_iter(y::out, left, ys, lt) 。 merge_iter (out, x::xs, [], lt) = merge_iter( x::out, xs, [], lt) 。 merge_iter (out, [], y::ys, lt) = merge_iter( y::out, [], ys, lt) 。 merge_iter (out, [], [], _) = out in fun merge(x,y,lt) = merge_iter([],x,y,lt) end; 最後に、MergeSort関数を以下に示す。 (* リストを降順にソートする。順序は lt(a,b) <==> a < b で決定。 * O(n log n) *) fun MergeSort(empty as [], _) = empty 。 MergeSort(single as _::[], _) = single 。 MergeSort(x, lt) = let val (left, right) = split(x) val sl = MergeSort(left, lt) val sr = MergeSort(right, lt) val s = merge(sl,sr,lt) in rev s end; なお、見ての通りこのコードでは要素の型を規定していない。そのため、順序関数ltさえあれば、どんな型の要素でもソートできる。型推論により、コンパイラはlt関数のような複雑な型も含め、あらゆる変数の型を推論できる。 SMLでは、IntInf モジュールで任意精度（多倍長精度）の整数の算術を提供している。さらに言えば、コード内に現れる整数はどれだけ桁数があってもプログラマが気にする必要がない。 次のプログラム fact.sml は、任意精度の階乗関数を実装したもので、120の階乗を表示する。 fun fact n : IntInf.int = if n=0 then 1 else n * fact(n - 1) val () = print (IntInf.toString (fact 120)^"\n") コンパイルして実行すると次のようになる。 $ mlton fact.sml $ ./fact 66895029134491270575881180540903725867527463331380298102956713523016335 57244962989366874165271984981308157637893214090552534408589408121859898 481114389650005964960521256960000000000000000000000000000 SMLは関数型言語なので、関数を生成し処理することが容易である。これには様々な応用が考えられる。関数の数値微分もその1つである。以下のSML関数 d は与えられた関数 f の x における数値微分を計算する。 - fun d delta f x = (f (x + delta) - f (x - delta)) / (2.0 * delta); val d = fn : real -> (real -> real) -> real -> real この関数は小さい値 delta を必要とする。例えば、マシンイプシロンの立方根を delta として使うことができる。 関数 d の型は、型 (real -> real) -> real -> real を持つ別の関数へ real を与える、というものである。このように、「関数を、必要な全ての引数より少ない数の引数を取り、さらに残りの引数を取るような関数を返す関数にする」方式をカリー化と呼ぶ。これにより、引数を一部だけ適用する（部分適用という。部分適用のことないし「ある関数をカリー化し、それに部分適用したものを返す」ことについて誤って「カリー化」と言及されていることがあるので注意する）こともできるようになる。ここでは delta を具体的に指定し、より特化した関数を得る。 - val d = d 1E~8; val d = fn : (real -> real) -> real -> real ここで推論された型を見ると、置換された d は第一引数が real -> real という型の関数になっている。これを使って、例えば x^3-x-1 での x=3 のときの微分値の近似を計算する。 - d (fn x => x * x * x - x - 1.0) 3.0; val it = 25.9999996644 : real 正しい値は f′(x) = 3x2−1 ⇒ f′(3) = 27−1 = 26 である。 関数 d は別の関数 f を引数としてとるので、高階関数 (higher-order function) と呼ばれる。
概要
モジュールシステム
コード例
Hello world
マージソート
任意精度の階乗関数（ライブラリ）
数値微分（高階関数）
Size:20 KB
出典: フリー百科事典『ウィキペディア（Wikipedia）』
担当:undef