「モジュール (module)」は、データ構造とそれを操作する関数を一つにまとめるための仕組みです。最近は、モジュールに相当する機能を持つプログラミング言語が多くなりました。SML/NJ の場合、モジュールに相当する機能が「ストラクチャ (structure)」です。
簡単な例として「スタック (stack)」というデータ構造を考えてみましょう。次の図を見てください。
|-----| |[ A ]| |[ B ]| |[ A ]| |-----|
| | | |-----| |[ A ]| |-----| | | |
| | | | | | |-----| | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
+-----+ +-----+ +-----+ +-----+ +-----+
(1) 空の状態 (2) PUSH A (3) PUSH B (4) POP B (5) POP A
図 : スタックの動作例
上図は、バネがついた容器を表していて、上から品物を出し入れすることができます。初めは空の状態です。ここに品物を乗せると、重さによってバネを圧縮し、品物が容器に格納されます。さらにもう一つ品物を上に乗せると、さらにバネを圧縮し、その品物も容器に格納することができます。バネが限界まで圧縮されると、もう品物は追加できなくなります。取り出す場合は、上にある品物から行います。一つ取り出すと、その分バネが伸びて下にある品物が上に押し出されます。
この容器の動作が、スタックの動作なのです。スタックにデータを追加する操作をプッシュ (PUSH) といい、スタックからデータを取り出す操作をポップ (POP) といいます。品物をデータに見立てれば、データ A をスタックにプッシュし (2)、次にデータ B をプッシュします (3)。データを取り出す場合、あとから入れたデータ B が先にポップされ (4)、その次にデータ A がポップされてスタックが空になります (5)。このように、スタックはあとから入れたデータが先に取り出されるので、後入れ先出し (LIFO : Last-In, First-Out) と呼ばれます。
SML/NJ の場合、スタックはリストを使って簡単に実現することができます。データを追加するときはリストの先頭に追加し、データを取り出すときはリストの先頭から行うように操作を限定すると、それはスタックの動作と同じになります。
最初はストラクチャを使わずにプログラムを作ります。次のリストを見てください。
リスト : スタック (* 例外 *) exception Stack (* スタックの定義 *) datatype 'a stack = S of 'a list (* 空のスタック *) val create = S nil (* データの追加 *) fun push(S x, data) = S (data::x) (* データの削除 *) fun pop(S nil) = raise Stack | pop(S (_::xs)) = S xs (* データの取得 *) fun top(S nil) = raise Stack | top(S (x::_)) = x (* スタックは空か *) fun isEmpty(S nil) = true | isEmpty(S _ ) = false
最初に datatype でスタック 'a stack を定義します。空のスタックを返す create は関数ではなく変数として定義します。この理由は後で説明します。スタックの操作関数は簡単です。push はデータをリストの先頭に追加します。pop はリストの先頭要素を取り除きます。データの取得は関数 top で行います。スタックが空の場合、pop と top を適用することができないので、例外 Stack を送出します。関数 isEmpty はスタックが空かチェックする述語です。
簡単な使用例を示します。
- val a0 = create; val a0 = S [] : 'a stack - val a1 = push(a0, 1); val a1 = S [1] : int stack - val a2 = push(a1, 2); val a2 = S [2,1] : int stack - top a2; val it = 2 : int - val a3 = pop a2; val a3 = S [1] : int stack - isEmpty a3; val it = false : bool - val a4 = pop a3; val a4 = S [] : int stack - isEmpty a4; val it = true : bool
正常に動作していますね。関数型言語の場合、変数の値を書き換えることができないので、push や pop の返り値を別の変数に格納する必要があります。このとき、参照型の変数にスタックを格納すれば、値を書き換えることができるので便利なように思います。ところが、多相的なデータは参照にすることができません。
実をいうと、ML (SML/NJ や Ocaml など) の多相性には制限があるのです。create が関数ではなく変数なのも、多相性が制限されているからです。これはあとで説明します。
それでは、ストラクチャを使ってスタックを定義してみましょう。ストラクチャの定義は次のようになります。
structure 名前 = struct ..... end
struct ... end がストラクチャの本体です。この間にプログラムを書きます。そこで定義された変数、関数、例外はストラクチャに属します。structure を使うとストラクチャに名前を付けることができます。ストラクチャ名を Stack とすると、プログラムは次のようになります。
リスト : ストラクチャ structure Stack = struct (* 例外 *) exception Stack (* スタックの定義 *) datatype 'a stack = S of 'a list (* 空のスタック *) val create = S nil (* データの追加 *) fun push(S x, data) = S (data::x) (* データの削除 *) fun pop(S nil) = raise Stack | pop(S (_::xs)) = S xs (* データの取得 *) fun top(S nil) = raise Stack | top(S (x::_)) = x (* スタックは空か *) fun isEmpty(S nil) = true | isEmpty(S _ ) = false end
SML/NJ の場合、ストラクチャ名は英大文字で始める習慣があります。struct と end の間にスタックのプログラムを書いただけです。とても簡単ですね。実際に Stack を定義すると次のように表示されます。
structure Stack :
sig
exception Stack
datatype'a stack = S of 'a list
val create : 'a stack
val push : 'a stack * 'a -> 'a stack
val pop : 'a stack -> 'a stack
val top : 'a stack -> 'a
val isEmpty : 'a stack -> bool
end
sig ... end を「シグネチャ (signature)」といいます。シグネチャはストラクチャの仕様を記述するものです。ストラクチャを定義するとシグネチャが生成されますが、ユーザがシグネチャを定義して、それをストラクチャに設定することもできます。シグネチャは次節で詳しく説明します。
それでは実行してみましょう。
- val a0 = Stack.create; val a0 = S [] : 'a Stack.stack - val a1 = Stack.push(a0, 10); val a1 = S [10] : int Stack.stack - Stack.top a1; val it = 10 : int - Stack.isEmpty a1; val it = false : bool - val a2 = Stack.pop a1; val a2 = S [] : int Stack.stack - Stack.isEmpty a2; val it = true : bool
ストラクチャで定義された変数や関数は、Stack.create のように「ストラクチャ名 + ドット ( . ) + 名前」でアクセスすることができます。
シグネチャの定義は次のようになります。
signature 名前 = sig ..... end
sig ... end がシグネチャの本体です。この間にストラクチャの仕様を書きます。signature を使うとシグネチャに名前を付けることができます。主な仕様は次のように記述します。
シグネチャはストラクチャの仕様を記述したものですが、外部とのインターフェースの役割も持っています。たとえば、ストラクチャの内部だけで使用する変数や関数は、外部から使われることがないように隠した方がよいでしょう。このような場合、外部に公開する関数や変数だけをシグネチャに記述すればよいのです。シグネチャに記述されていない変数や関数は非公開となり、外部からアクセスすることができなくなります。
シグネチャにはもう一つ重要な機能があります。それはストラクチャの「型」としての機能です。たとえば、ストラクチャ Stack の型は 'a Stack.stack という多相型になります。データ型を特定したい場合、シグネチャに記述することで実現できます。簡単な例として、整数を格納するストラクチャ IntStack を作ってみましょう。次のプログラムを見てください。
リスト : シグネチャ signature INTSTACK = sig type 'a stack exception Stack val create : int stack val push : int stack * int -> int stack val pop : int stack -> int stack val top : int stack -> int val isEmpty : int stack -> bool end structure IntStack: INTSTACK = Stack
IntStack のシグネチャ INTSTACK を定義します。SML/NJ の場合、シグネチャの名前を英大文字で記述する習慣があります。type で指定するデータ型は Stack のデータ型 'a stack になります。そして、関数と変数の仕様を 'a stack から int stack に変更します。これで IntStack の仕様になります。
ストラクチャにシグネチャを指定する場合、ストラクチャ名の後ろにコロン ( : ) を付けて、その後ろにシグネチャを指定します。SML/NJ の場合、変数の型を指定するときは "変数名 : 型式" で行いました。シグネチャはストラクチャの型を表すので、"ストラクチャ名 : シグネチャ" でシグネチャを指定することができます。これで、データ型を int に特定した IntStack を生成することができます。
この他にも、シグネチャの指定方法はいくつかあります。また、シグネチャに名前を付けずに指定することもできます。簡単な例を示します。
structure Foo : sig ... end = struct ... end structure Foo = struct ... end : sig ... end
コロン ( : ) の後ろにシグネチャを指定するところは、どの方法でも同じです。
それでは、実際に IntStack を実行してみましょう。
- val a0 = IntStack.create; val a0 = S [] : int Stack.stack - val a1 = IntStack.push(a0, 10); val a1 = S [10] : int Stack.stack - val a2 = IntStack.pop a1; val a2 = S [] : int Stack.stack
IntStack.create のデータ型が int Stack.stack になっていますね。このように、シグネチャを使ってデータ型を特定したストラクチャを作ることができます。
たとえば、空リスト nil の参照を考えてみましょう。実際に ref nil で参照を生成すると次のようになります。
- val a = ref nil; stdIn:3.5-3.16 Warning: type vars not generalized because of value restriction are instantiated to dummy types (X1,X2,...) val a = ref [] : ?.X1 list ref
このように、'a list のような多相的な型ではなく、ダミーな型が割り当てられます。もしも、'a list のような多相的な型の参照を許すと、次のような代入操作が可能になります。
val a = ref nil (* 型が 'a list とする *) a := [1, 2, 3] (* int list に書き換える *) a := ["abc", "def"] (* string list に書き換える *)
変数 a の型が int list から string list に変わってしまいます。つまり、プログラムの実行中に変数の型が変化する可能性があるわけです。SML/NJ はコンパイル時にデータ型を厳密にチェックするプログラミング言語です。実行中にデータ型が変化するような処理は、SML/NJ には想定外のことです。参照を使う場合は多相性を制限する必要があるのです。
実際にはもう少し制限が厳しくて、変数に「値」を束縛するときに限り、多相性を許すようになっています。参考文献『Objective Caml 入門』によると、これを「値多相」といいます。この場合の「値」とは、変数、定数、関数定義、要素が値の組やレコードなどです。逆に、関数や ref の適用、if など評価が行われる式は「値」になりません。次の例を見てください。
- fun foo() = nil; val foo = fn : unit -> 'a list - val a = nil; val a = [] : 'a list - val b = foo(); stdIn:15.1-15.14 Warning: type vars not generalized because of value restriction are instantiated to dummy types (X1,X2,...) val b = [] : ?.X1 list
関数 foo は nil を返します。val a = nil の場合、変数 a の型は 'a list になりますが、val b = foo() は右辺が関数適用なので、変数 b の型は 'a list にはなりません。
ところで、シグネチャでデータ型を決定すれば、スタックを参照型の変数に格納することができます。次のリストを見てください。
リスト : スタック structure Stack = struct exception Stack datatype 'a stack = S of 'a list fun create() = ref(S nil) fun push(x as ref(S y), data) = x := S(data::y) fun pop(ref(S nil)) = raise Stack | pop(x as ref(S (y::ys))) = y before (x := S ys) fun top(ref(S nil)) = raise Stack | top(ref(S (x::_ ))) = x fun isEmpty(ref(S nil)) = true | isEmpty(ref(S _ )) = false end
create は空のスタックの参照を返す関数として定義します。操作関数はスタックを格納した参照型の変数を受け取ります。この変数を書き換えることで、スタックを操作することができます。つまり、「値渡し」ではなく「参照渡し」になります。
関数 pop は仕様を変更して、取り除いたデータを返すことにします。pop で使っている演算子 befor は Common Lisp の関数 prog1 と同じ働きをします。
expr1 before expr2
- op before; val it = fn : 'a * unit -> 'a
before は expr1 を評価し、その次に expr2 を評価します。そして、expr1 の評価結果が before の値になります。expr2 の返り値はユニットでなければいけません。before は変数の値を取り出しておいてから、変数の値を更新する処理などで役に立ちます。pop の場合、スタックの先頭データを求め、その後でスタックからデータを取り除きます。この処理は before を使うと簡単に実現できます。
次はシグネチャを定義してストラクチャ IntStack を作ります。プログラムは次のようになります。
リスト : シグネチャの定義
signature INTSTACK = sig
type 'a stack
exception Stack
val create : unit -> int stack ref
val isEmpty : int stack ref -> bool
val pop : int stack ref -> int
val push : int stack ref * int -> unit
val top : int stack ref -> int
end
structure IntStack : INTSTACK = Stack
データ型を決めているだけなので、難しいところないと思います。それでは、実行例を示します。
- val a = IntStack.create(); val a = ref (S []) : int Stack.stack ref - IntStack.push(a,10); val it = () : unit - a; val it = ref (S [10]) : int Stack.stack ref - IntStack.push(a,20); val it = () : unit - a; val it = ref (S [20,10]) : int Stack.stack ref - IntStack.pop(a); val it = 20 : int - a; val it = ref (S [10]) : int Stack.stack ref
正常に動作してますね。これで、real 用のシグネチャを定義すれば、real を格納するスタックができますし、string 用のシグネチャを定義すれば、string を格納するスタックを用意することができます。