Standard ML

Standard ML  は、プログラミング言語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 

Standard ML のコンパイラは、このようにユーザーが全くデータ型を指定していない記述から int int という型を静的に推論する必要がある。すなわち、//x// が整数の式でしか使われていないことから、それ自身も整数だと推論し、関数内の式で生み出される値も全て整数であると推論しなければならない。

同じ関数を「節関数定義 」で表現することもできる。その場合 //if//-//then//-//else// という条件分岐を '|' で区切られた一連のテンプレートに置換し、個々のテンプレートは特定の値について評価される。各テンプレートは順番に試行され、一致するものを見つけることになる。 fun factorial 0 = 1 | factorial n = n * factorial 

局所関数を使い、この関数を末尾再帰に書き換えることもできる。 fun factorial x = let fun tail_fact p 0 = p | tail_fact p n = tail_fact   in tail_fact 1 x end

let-式の値は、in と end に挟まれた式の値になる。

1.1. モジュールシステム
--------------

Standard ML には高度なモジュールシステムがあり、プログラムを論理的に関連する型と値の宣言の //structure// による階層に分解することができる。SMLモジュールは単に名前空間を制御するだけでなく、抽象化の役割も持っており、プログラマはこれを使って抽象データ型を定義できる。

主に3つの構文要素でSMLモジュールシステムが構成される。//signature// と //structure// と //functor// である。//structure// はモジュールそのものである。型、式、値、//structure//  の集合体であり、それらを1つの論理単位にパッケージ化している。//signature// はインタフェースであり、一般にその //structure// の型として認識される。その //structure// が提供する全ての実体の名前を指定し、型要素のアリティ、値要素の型、//substructure// の //signature// も指定する。型要素の定義はエクスポートする場合もしない場合もある。定義を隠蔽した型要素を「抽象型 」と呼ぶ。//functor// は //structure// から //structure// への関数である。すなわち、//functor// は1つ以上の引数を受け付け、結果として //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 queue end

この //signature// はキューのパラメータ化された型 queue を提供するモジュールを記述しており、それには Queue という例外、キューの基本操作を提供する5つの値を記述している。これを使ってキューデータ構造を実装した //structure// を書くことができる。 structure TwoListQueue :> QUEUE = struct type 'a queue = 'a list * 'a list exception Queue val empty =  fun insert ) =  fun isEmpty  = true | isEmpty _ = false fun peek  = raise Queue | peek  = hd  | peek  = a fun remove  = raise Queue | remove  = let val newouts = rev ins in ) end | remove  = ) end

この定義では、TwoListQueue が QUEUE という //signature// の実装であることを宣言している。さらに //opaque ascription// により、この //signature//で定義が提供されていない型要素は抽象型として扱うことを示している。すなわち、ここではキューが2つのリストで定義されているが、それはモジュール外部には見せない。//structure// 本体には //signature// に挙げられている全要素に対応した実装が記述される。

//structure// を使うには、「ドット記法」でその型や値といったメンバーにアクセスすればよい。例えば、文字列のキューの型は string TwoListQueue.queue、空のキューは TwoListQueue.empty、q というキューの最初の要素を削除するには TwoListQueue.remove q と書けばよい。

2. コード例
-------

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" を表示している。

2.1. Hello world
----------------

次のようなプログラム "hello.sml" があるとする。 print "Hello world! ";

これをMLtonでコンパイルする場合、次のように入力する。 $ mlton hello.sml

実行は次の通り。 $ ./hello Hello world! $

2.2. マージソート
-----------

マージソートのアルゴリズムについては、当該記事を参照されたい。ここではマージソートを3つの関数 split、merge、MergeSort で実装している。

関数 split は、追加の引数を持つ局所関数 split_iter を使って実装している。これは末尾再帰の実装に便利な手法である。この関数はSMLのパターンマッチング構文を使っており、リストが空でないケース  と空のケース  を定義している。 (* 要素のリストを与えられ、それをほぼ同じサイズの

2つに分割する。
O
)local fun split_iter  = split_iter | split_iter  =  in fun split = split_iter end;<WtXmlEndTag />

local-in-end という構文を let-in-end という構文に置き換えると、等価な定義が得られる。 fun split = let fun split_iter  = split_iter | split_iter  =  in split_iter end;

split と同様、merge も局所関数 merge_iter を使って効率化する。merge_iter ではいくつかのケースを定義している。'_' はワイルドカード・パターンを表している。

この関数は2つの昇順のリストを1つの降順のリストにマージする。逆転するのはSMLにおけるリストの構造によるものである。SMLではリストを非平衡2分木で実装しているため、要素を先頭に付与するのは容易だが、最後尾に付与するのは非効率的である。 (* 2つの昇順リストを1つの降順リストにマージする。

関数 lt は a < b と同値
O
)local fun merge_iter , right as , lt) = if lt then merge_iter else merge_iter | merge_iter  = merge_iter | merge_iter  = merge_iter | merge_iter  = out in fun merge = merge_iter end;<WtXmlEndTag />

最後に、MergeSort 関数を以下に示す。  <==> a < b で決定。

O
)fun MergeSort = empty | MergeSort = single | MergeSort = let val  = split val sl = MergeSort val sr = MergeSort val s = merge in rev s end;<WtXmlEndTag />

なお、見ての通りこのコードでは要素の型を規定していない。そのため、順序関数 lt さえあれば、どんな型の要素でもソートできる。型推論により、コンパイラは lt 関数のような複雑な型も含め、あらゆる変数の型を推論できる。

2.3. 任意精度の階乗関数
--------------

SMLでは、IntInf モジュールで任意精度の整数の算術を提供している。さらに言えば、コード内に現れる整数はどれだけ桁数があってもプログラマが気にする必要がない。

次のプログラム "fact.sml" は、任意精度の階乗関数を実装したもので、120の階乗を表示する。 fun fact n : IntInf.int = if n=0 then 1 else n * fact

val  = print ^" ")<WtXmlEndTag />

コンパイルして実行すると次のようになる。 $ mlton fact.sml $ ./fact 66895029134491270575881180540903725867527463331380298102956713523016335 57244962989366874165271984981308157637893214090552534408589408121859898 481114389650005964960521256960000000000000000000000000000

2.4. 数値微分
---------

SMLは関数型言語なので、関数を生成し処理することが容易である。これには様々な応用が考えられる。関数の数値微分もその1つである。以下のSML関数 "d" は与えられた関数 "f" の "x" における数値微分を計算する。

- fun d delta f x =  - f ) / ; val d = fn : real  real real

この関数は小さい値 "delta" を必要とする。例えば、マシンイプシロンの立方根を delta として使うことができる。

関数 "d" の型は、型 " real real" を持つ別の関数へ "real" を与える、というものである。このように、「関数を、必要な全ての引数より少ない数の引数を取り、さらに残りの引数を取るような関数を返す関数にする」方式をカリー化と呼ぶ。これにより、引数を一部だけ適用することもできるようになる。ここでは "delta" を具体的に指定し、より特化した関数を得る。

- val d = d 1E~8; val d = fn :  real real

ここで推論された型を見ると、置換された "d" は第一引数が "real real" という型の関数になっている。これを使って、例えば x^3-x-1 での x=3 のときの微分値の近似を計算する。

- d  3.0; val it = 25.9999996644 : real

正しい値は f' = 3x^2-1 => f' = 27-1 = 26 である。

関数 "d" は別の関数 "f" を引数としてとるので、「高階関数 」と呼ばれる。

カリー化と高階関数は冗長コードを排除できる。例えば、ライブラリに a -> b という型の関数が必要だとする。しかし、a 型と c 型のオブジェクトに固定的な関係がある場合、a * c -> b という型の関数を書くほうが便利である。  という型の高階関数を使えば、共通点を取り除くことができる。これは Adapter パターンの一例である。

2.5. 離散ウェーブレット変換
----------------

2の整数乗の長さの数列の1次元離散ウェーブレット変換はSMLでは簡単に実装でき、リスト上のパターンマッチの好例となっている。リストの先頭から2つの要素 を取り出し、その総和をリスト "s" に、差分をリスト"d" に格納する。

- fun haar l = let fun aux [s] [] d = s :: d | aux [] s d = aux s [] d | aux  s d = aux t   | aux _ _ _ = raise Empty in aux l [] [] end; val haar = fn : int list int list

実行例は次の通り。

- haar [1, 2, 3, 4, ~4, ~3, ~2, ~1]; val it = [0,20,4,4,~1,~1,~1,~1] : int list

パターンマッチは複雑な変換を明確かつ簡潔に表現できる。さらに、SMLコンパイラはパターンマッチに最適化したコードを生成するので、単にコードが簡潔になるだけでなく高速である。

3. 実装
-----

様々な実装があるが、ここでは一部を紹介する。

MLton[1] - 最適化コンパイラを中心とした処理系であり、他の処理系よりも性能がいいコードを生成する。
Standard ML of New Jersey[2]  - コンパイラ、ライブラリ、ツール、シェル、文書などが揃っている。
Moscow ML[3] - Caml Light をベースにした軽量な実装。
Poly/ML[4]
TILT[5] - 型付きの中間言語を使った実装。
HaMLet[6] - インタプリタ実装。
ML Kit[7] - ガベージコレクション機能を備え、リアルタイム処理に対応。
SML.NET[8] - マイクロソフトのCLRを生成でき、他の.NETコードとのリンクを可能にする拡張もある。
SML2c[9] - モジュールレベルの宣言をC言語に変換する。
Poplog[10] - POP-11という言語を中心としたシステムで、Standard ML、Common Lisp、Prolog をその上で使用できる。
SML#[11] - 東北大学電気通信研究所の大堀淳研究室が開発。C言語と連携、レコード多相性などを実装。
MLWorks[12] - かつて Harlequin という企業が商用製品として開発販売していた。同社は既に倒産したが、Ravenbrook によってオープンソース化されている。これらはいずれもオープンソースである。多くは処理系自体がSMLで実装されている。SMLの商用製品は存在しない。

4. 参考文献
-------

5. 脚注
-----

6. 外部リンク
--------

[13]
[14]
[15] - Standard ML を出発点として ML を発展させようとしているサイト