Standard ML

Standard ML

パラダイム	マルチパラダイム: 関数型、命令型
型付け	強い、静的、推論あり
主な処理系	MLton, MLWorks, Moscow ML, Poly/ML, SML/NJ, SML.NET
方言	Alice、Dependent ML
影響を受けた言語	ML

Standard ML (SML) は、プログラミング言語MLの標準ないし1方言である。The Definition of Standard ML で型付け規則と操作的意味論が与えられている。1990年に初版が出版され、1997年に単純化された改版が出版されている。

概要

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 queue
end

この 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 world

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

print "Hello world!\n";

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

$ mlton hello.sml

実行は次の通り。

$ ./hello
Hello 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) = 3x^2-1 => f'(3) = 27-1 = 26 である。

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

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

離散ウェーブレット変換（パターンマッチング）

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

  - fun haar l =
      let fun aux [s] [] d = s :: d
            | aux [] s d = aux s [] d
            | aux (h1::h2::t) s d =
              aux t (h1 + h2 :: s) (h1 - h2 :: d)
            | 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コンパイラはパターンマッチに最適化したコードを生成するので、単にコードが簡潔になるだけでなく高速である。

実装

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

• MLton[1] - 最適化コンパイラを中心とした処理系であり、他の処理系よりも性能がいいコードを生成する。
• Standard ML of New Jersey[2] (SML/NJ) - コンパイラ、ライブラリ、ツール、シェル、文書などが揃っている。
• 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言語と連携、レコード多相性などを実装。（マイクロソフトの.NETとは無関係）
• MLWorks[12] - かつて Harlequin という企業が商用製品として開発販売していた。同社は既に倒産したが、Ravenbrook によってオープンソース化されている。

これらはいずれもオープンソースである。多くは処理系自体がSMLで実装されている。SMLの商用製品は存在しない。

参考文献

• 大堀 淳『プログラミング言語Standard ML入門』共立出版、東京、2001年9月。ISBN 4-320-12024-8。 

外部リンク

• What is SML?
• What is SML '97?
• successor ML (sML) - Standard ML を出発点として ML を発展させようとしているサイト