ATSプログラミング入門:
Prev	Chapter 7. モジュール性	Next

抽象型

抽象型 という名前は、型の利用者から完全に隠した型の値の表現方法に由来します。このような情報の隠蔽は、抽象の実装に対する変更が抽象型を使っている型安全なコードで型エラーを引き起こさないよう保証する努力です。多くの他のプログラミング言語と同様に、ATS でも抽象型はモジュールプログラミングをサポートする重要な役割をはたします。抽象型の実際的で典型的な使用の例を次に示します。

整数の有限集合に対する様々な機能を提供するパッケージを実装しているとしましょう。まずはじめに、整数の有限集合を表現する値のために次のような抽象型 intset を宣言します:

abstype intset // a boxed abstract type

キーワード abstype は宣言された抽象型 intset がボックス化されていることを指示します。つまり intset のサイズはポインタのサイズと同じです。関連したキーワード abst@ype はアンボックス化された抽象型の開始で、別の章で説明します。パッケージで実装したいそれぞれの関数と値のインターフェイスを次に示します:

// empty set
val intset_empty : intset

// singleton set of [x]
fun intset_make_sing (x: int): intset

// turning a list into a set
fun intset_make_list (xs: list0 int): intset

// turning a set into a list
fun intset_listize (xs: intset): list0 (int)

// membership test
fun intset_ismem (xs: intset, x: int): bool

// computing the size of [xs]
fun intset_size (xs: intset): size_t

// adding [x] into [xs]
fun intset_add (xs: intset, x: int): intset

// deleting [x] from [xs]
fun intset_del (xs: intset, x: int): intset

// union of [xs1] and [xs2]
fun intset_union (xs1: intset, xs2: intset): intset

// intersection of [xs1] and [xs2]
fun intset_inter (xs1: intset, xs2: intset): intset

// difference between [xs1] and [xs2]
fun intset_differ (xs1: intset, xs2: intset): intset

ここでは intset の宣言と上記のインターフェイスは全て intset.sats と名前のつけられたファイルに格納されているものとしましょう。

通常、有限集合の現実的な実装はなんらかの平衡木 (例えば AVL 木や赤黒木) を使います。説明のために、ここでは整数の順序付きリストを使って表現される整数の有限集合を実装します。この実装は intset.dats という名前のファイルに保存されており、このファイルはオンラインから取得できます。抽象型の値をコンストラクトするために、次のような宣言を使って一時的にそれを具体化させる必要があります:

assume intset = list0 (int)

assume キーワードを使いました。この assume 宣言は intset と型 list0 (int) を同一に扱うように指示します。この結び付きは、それが導入されたスコープの終了まで有効です。 intset.dats のトップレベルに assume 宣言があるので、intset と list0 (int) が等価だという前提はファイル末尾まで有効です。 ATS には、それぞれの抽象型は最大でも1度までしか assume 宣言によって具体化することができないという、グローバルな制限があります。より具体的には、もし抽象型が2つのファイル foo1.dats と foo2.dats で具体化されていたら、これらの2つのファイルを一緒にして1つの実行ファイルで使うことはできません。 intset の残りの実装は全て一般的なものです。例えば、2つの整数の有限集合の合併は次のような実装になります:

implement
intset_union
  (xs1, xs2) = (
case+ (xs1, xs2) of
| (list0_cons (x1, xs11),
   list0_cons (x2, xs21)) =>
  let
    val sgn = compare (x1, x2)
  in
    case+ 0 of
    | _ when sgn < 0 =>
        list0_cons{int}(x1, intset_union (xs11, xs2))
    | _ when sgn > 0 =>
        list0_cons{int}(x2, intset_union (xs1, xs21))
    | _ (* sgn = 0 *) =>
        list0_cons{int}(x1, intset_union (xs11, xs21))
    // end of [case]
  end // end of [(cons, cons)]
| (list0_nil (), _) => xs2
| (_, list0_nil ()) => xs1
) (* end of [intset_union] *)

intset.sats で宣言されている関数の使用に対するいらかのテストコードがオンラインから入手できます。しばしばこのようなテストコードを、パッケージで宣言されている様々な関数と値のインターフェイスの直後でコンストラクトすることがあります。これらのインターフェイスが実際に実装される前に試すことで、欠陥をすぐに発見することができます。

Prev	Home	Next
特殊テンプレート実装	Up	例: 有理数パッケージ