抽象データ型とは

抽象データ型の仕様の記述とは以下の4つを記述することであるようだ。

• TYPES(型)
• FUNCTIONS(関数) -> その抽象データ型に適用可能な操作の集合
• AXIOMS(公理) -> その抽象データ型が必ず満たす条件
• PRECONDITIONS(事前条件) -> 部分的な関数のソース集合の定義域

STACKの例を見ながら説明が書かれていて、STACKの抽象データ型の仕様記述は以下のとおりであるらしい。

- TYPES
    - STACK[G]
- FUNCTIONS
    - put: STACK[G] x G -> STACK[G]
    - remove: STACK[G] -/> STACK[G]
    - item: STACK[G] -/> G
    - empty: STACK[G] -> BOOLEAN
    - new: STACK[G]
- AXIOMS
    - 任意のx:G, s:STACK[G]に対して以下が成り立つ
    - 1. item(put(s,x)) = x
    - 2. remove(put(s,x)) = s
    - 3. empty(new)
    - 4. not empty(put(s,x))
- PRECONDITIONS
    - remove(s: STACK[G]) require not empty(s)
    - item(s: STACK[G]) require not empty(s)

この記述が表していることを簡単に説明すると以下の通り。

• TYPESで、STACKは任意の型Gのオブジェクトを保持できるものであることが分かる
• FUNCTIONSからSTACKにはput, remove, item, emptyという操作があり、生成関数としてnewがあることが分かる
• FUNCTIONSの->は全てのソース集合(引数)に対して関数を定義できることを表し、-/>はそうではないことを表している
  • 全てのソース集合に対して適用できない関数は部分関数と呼ばれる
  • 例えば、removeはSTACK[G]がemptyである時には適用できない関数であるので、-/>が使われている
• AXIOMSの1, 2からスタックはLIFOであるということがわかり、また3, 4からスタックには空の時と空でない時があるということが分かる
• 部分関数であるならば、どのソース集合に使えるか知りたい。PRECONDITIONSによって、removeはemptyの時以外で使える、itemもempty以外の時で使えるということが分かる

またこの記述に実装をしたもの(ただし部分的な実装でも良い)がクラスであり、この記述がそのままそのクラスが外部に公開したいものを表している、と書いてあった。

抽象データ型を知って面白いと思ったこと

この抽象データ型が面白いなあと思ったのは、自分が実装をしているときにいろいろ考えていることが、実際に言語化されているというところだ。

TYPESはまさにクラスそのもの。FUNCTIONSはそのクラスが最低限公開すべきインターフェースを考えているときに同じことを考えている。そのクラスは何をすべきものなのかということを考えていくと、最終的にAXIOMSのようなことをぼんやりイメージはしている。またそれぞれの関数を実装するときに、この場合はこのメソッドを使えないから例外を上げようとか考えていて、それはまさにPRECONDITIONSで宣言されている。さらにこのようなものを全部合わせて、このクラスではどこまで公開すべきか、どこからは隠蔽すべきかということを考えている。

実際に経験則でこのような考えをしているなあとぼんやりイメージしていることと、それを言語化できていることには大きな開きがある。そのため、いままではぼんやりと経験則でやっていたところが、抽象データ型の書き方が書かれたこの章を読んで、言語化されたというところが非常にためになった。