Standard ML

Standard ML (SML) について

Standard ML（SML）は、関数型プログラミング言語MLの標準的な方言の一つです。その特徴は、厳密な型付け規則と操作的意味論にあります。1990年に最初の仕様が公開され、1997年には簡略化された改訂版が登場しました。

SMLの基本

SMLは基本的に関数型言語であり、プログラムは値を計算する式で構成されます。関数はSMLにおける重要な概念であり、抽象化を実現するための主要な手段です。例えば、階乗関数は以下のように記述できます。

sml
fun factorial x =
if x = 0 then 1 else x factorial (x - 1)


SMLコンパイラは、このコードから`int -> int`という関数型を静的に推論します。これは、`x`が整数としてのみ使われていることから、`x`自体が整数であり、関数の結果も整数であることを推論するものです。

節関数定義と局所関数

同じ関数を節関数定義で記述することも可能です。この場合、`if-then-else`による条件分岐を`|`で区切られた複数のテンプレートに置き換え、それぞれのテンプレートが特定の値について評価されます。

sml
fun factorial 0 = 1
| factorial x = x factorial (x - 1)


さらに、局所関数を用いることで、関数を末尾再帰として記述することもできます。これにより、スタックオーバーフローのリスクを低減できます。

sml
fun factorial x =
let
fun loop (n, acc) =
if n = 0 then acc else loop (n - 1, n acc)
in
loop (x, 1)
end

モジュールシステム

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

SMLのモジュールシステムは、`signature`、`structure`、`functor`の3つの主要な構文要素で構成されています。`structure`はモジュールそのもので、型、式、値、他の`structure`（サブストラクチャ）の集合体であり、これらを一つの論理単位にパッケージ化します。`signature`はインターフェースであり、`structure`の型として認識されます。`signature`は、`structure`が提供するすべての実体の名前、型要素のアリティ、値要素の型、サブストラクチャの`signature`を指定します。型要素の定義は公開することも隠蔽することもでき、定義を隠蔽した型要素は「抽象型」と呼ばれます。`functor`は、`structure`から別の`structure`への関数であり、一つ以上の引数（通常は`signature`で指定された`structure`）を受け取り、結果として新しい`structure`を生成します。`functor`は、ジェネリックなデータ構造やアルゴリズムの実装に利用されます。

例えば、キューデータ構造の`signature`は次のようになります。

sml
signature QUEUE =
sig
exception Queue
type 'a queue
val empty : 'a queue
val insert : 'a 'a queue -> 'a queue
val remove : 'a queue -> 'a 'a queue
val peek : 'a queue -> 'a
val isEmpty : 'a queue -> bool
end


この`signature`は、キューのパラメータ化された型`queue`と、キューの基本操作を提供する5つの値（うち4つは関数）を定義しています。この`signature`を用いて、キューデータ構造を実装した`structure`を記述できます。

sml
structure TwoListQueue :> QUEUE =
struct
exception Queue
type 'a queue = 'a list 'a list
val empty = ([], [])
fun insert (x, (inList, outList)) = (x :: inList, outList)
fun remove ([], []) = raise Queue
| remove (inList, []) = remove ([], rev inList)
| remove (inList, x :: outList) = (x, (inList, outList))
fun peek ([], []) = raise Queue
| peek (inList, []) = peek ([], rev inList)
| peek (inList, x :: outList) = x
fun isEmpty ([], []) = true
| isEmpty _ = false
end


`TwoListQueue`は`QUEUE`という`signature`の実装であることを宣言しています。`:> `によるopaque ascriptionによって、`signature`で定義が提供されていない型要素（ここでは`queue`）は抽象型として扱われます。つまり、キューが2つのリストで実装されていることはモジュール外からは隠蔽されます。`structure`本体には、`signature`に挙げられたすべての要素に対応する実装が記述されます。

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

コード例

SMLの処理系の多くは対話型のトップレベルを備えており、コードを容易に実行できます。トップレベルは、入力された式の型を推論し、その値を評価します。例えば、`1 + 2 3`を計算すると、次のようになります。

• - 1 + 2 3;

val it = 7 : int

Hello world

以下のような`hello.sml`というプログラムがあるとします。

sml
print "Hello, world!
";


このプログラムをMLtonでコンパイルするには、次のように入力します。


mlton hello.sml


実行は次の通りです。


./hello
Hello, world!

マージソート

マージソートは、SMLで効率的に実装できるアルゴリズムの一つです。

sml
fun mergeSort lt lst =
let
fun split lst =
let
fun split_iter (xs, ys, zs) =
case xs of
[] => (ys, zs)
| x::xs => split_iter(xs, x::zs, ys)
in
split_iter (lst, [], [])
end

fun merge (l1, l2) =
let
fun merge_iter ([], ys, acc) = revAppend(ys, acc)
| merge_iter (xs, [], acc) = revAppend(xs, acc)
| merge_iter (x::xs, y::ys, acc) =
if lt (x, y) then merge_iter (xs, y::ys, x::acc)
else merge_iter (x::xs, ys, y::acc)
in
merge_iter (l1, l2, [])
end

fun revAppend ([], acc) = acc
| revAppend (x::xs, acc) = revAppend (xs, x::acc)
in
case lst of
[] => []
| [_] => lst
| _ =>
let
val (l1,l2) = split lst
in
merge (mergeSort lt l1, mergeSort lt l2)
end
end


関数`split`は、追加の引数を持つ局所関数`split_iter`を使って実装されており、末尾再帰を実現しています。`merge`関数も同様に局所関数`merge_iter`を使って効率化を図っています。`MergeSort`関数は、`split`と`merge`関数を利用してソートを行います。

このコードは要素の型を規定していませんが、`lt`という順序関数があれば、任意の型の要素をソートできます。SMLの型推論により、コンパイラは`lt`関数のような複雑な型を含む、すべての変数の型を推論できます。

任意精度の階乗関数

SMLでは、`IntInf`モジュールを使用して、任意精度（多倍長精度）の整数演算を行うことができます。

sml
open IntInf;

fun fact n =
let
fun loop (x, acc) =
if x = 0 then acc
else loop (x - 1, x acc)
in
loop (n, 1)
end;

print (toString(fact 120) ^ "
");


このプログラムは、120の階乗を計算し、結果を表示します。

数値微分

SMLは関数型言語であるため、関数を生成し、操作することが容易です。例えば、関数の数値微分を計算する関数は以下のように記述できます。

sml
fun d f delta x = (f (x + delta) - f x) / delta;


この関数は、与えられた関数`f`の`x`における数値微分を計算します。関数`d`の型は、`(real -> real) -> real -> real`であり、これは「`real -> real`型の関数を受け取り、`real`を引数に取り、`real`を返す関数を返す」ことを意味します。このような関数をカリー化関数と呼びます。

sml
val dx = d (fn x => x x x - x - 1.0) 0.0001;
val result = dx 3.0;

離散ウェーブレット変換

2の整数乗の長さを持つ数列に対する1次元離散ウェーブレット変換は、SMLではパターンマッチングを使用して簡潔に実装できます。

sml
fun haar [] = []
| haar [h1, h2] = [h1 + h2, h1 - h2]
| haar (h1 :: h2 :: t) = h1 + h2 :: h1 - h2 :: haar t

実装

SMLには多くの実装が存在します。代表的なものとして、以下のようなものがあります。

MLton: 最適化コンパイラに重点を置いた処理系です。
Standard ML of New Jersey (SML/NJ): コンパイラ、ライブラリ、ツール、シェル、ドキュメントなどが包括的に提供されています。
Moscow ML: Caml Lightをベースにした軽量な実装です。
Poly/ML、TILT、HaMLet、ML Kit、SML.NET、SML2c、Poplog、SML#、MLWorks などがあります。

これらの実装は、多くがオープンソースであり、処理系自体がSMLで実装されている場合もあります。SMLの商用製品は存在しません。

参考文献

大堀 淳『プログラミング言語Standard ML入門 改訂版』共立出版、東京、2021年11月12日。

外部リンク

What is SML?
What is SML '97?
* successor ML (sML)

もう一度検索