Standard ML
パラダイム | マルチパラダイム: 関数型、命令型 |
---|---|
型付け | 強い、静的、推論あり |
主な処理系 | MLton, MLWorks, Moscow ML, Poly/ML, SML/NJ, SML.NET |
方言 | Alice、Dependent ML |
影響を受けた言語 | 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
に挟まれた式の値になる。
モジュールシステム
編集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 を使うには、ドット記法でその型や値といったメンバーにアクセスすればよい。例えば、文字列のキューの型は str
ing TwoListQueue.queue
、空のキューは Tw
oListQueue.empty
、q
というキューの最初の要素を削除するには TwoListQueue.remove q
と書けばよい。
コード例
編集 $ 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!
$
マージソート
編集split
、merge
、Merg
eSort
で実装している。
関数 split
は、追加の引数を持つ局所関数 split_it
er
を使って実装している。これは末尾再帰の実装に便利な手法である。この関数は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
数値微分(高階関数)
編集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
を与える、というものである。このように、﹁関数を、必要な全ての引数より少ない数の引数を取り、さらに残りの引数を取るような関数を返す関数にする﹂方式をカリー化と呼ぶ。これにより、引数を一部だけ適用する︵部分適用という。部分適用のことないし﹁ある関数をカリー化し、それに部分適用したものを返す﹂ことについて誤って﹁カリー化﹂と言及されていることがあるので注意する︶こともできるようになる。ここでは de
lta
を具体的に指定し、より特化した関数を得る。
- 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) と呼ばれる。
カリー化と高階関数は冗長コードを排除できる。例えば、ライブラリに a ->b
という型の関数が必要だとする。しかし、a
型と c
型のオブジェクトに固定的な関係がある場合、a * c ->b
という型の関数を書くほうが便利である。(a * c -> b) -> (a -> b)
という型の高階関数を使えば、共通部分を取り除くことができる。これは Adapter パターンの一例である。
離散ウェーブレット変換(パターンマッチング)
編集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コンパイラはパターンマッチに最適化したコードを生成するので、単にコードが簡潔になるだけでなく高速である。
実装
編集参考文献
編集- 大堀 淳『プログラミング言語Standard ML入門 改訂版』共立出版、東京、2021年11月12日。ISBN 9-78432012480-6。
脚注
編集- ^ Milner, R.; M. Tofte, R. Harper and D. MacQueen. (1997年) (PDF). The Definition of Standard ML (Revised). MIT Press. ISBN 0-262-63181-4
外部リンク
編集- What is SML?
- What is SML '97?
- successor ML (sML) - Standard ML を出発点として ML を発展させようとしているサイト