読者です 読者をやめる 読者になる 読者になる

$shibayu36->blog;

株式会社はてなでエンジニアをしています。プログラミングや読書のことなどについて書いています。

「オブジェクト指向入門 第6章 抽象データ型」を読んだ

オブジェクト指向入門 第2版 原則・コンセプト (IT Architect’Archive クラシックモダン・コンピューティング)

オブジェクト指向入門 第2版 原則・コンセプト (IT Architect’Archive クラシックモダン・コンピューティング)

「オブジェクト指向入門 第3章モジュール性」メモ - $shibayu36->blog; の続きで、「第6章 抽象データ型」を読んだ。

この章では、オブジェクトを適切に表現する記述として、抽象データ型というものを紹介している。これが非常に参考になったので軽く読書メモをとっておく。

抽象データ型とは

抽象データ型の仕様の記述とは以下の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以外の時で使えるということが分かる

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

2016/05/04 15:00 追記補足

ブクマのコメントで「itemとremoveがよくわからない」という話があったので一応補足。

まず通常スタックといえば、pushとpopという関数が一番最初に考えつく。しかし、この本ではpush, popがスタックによく使われるからこそ、あえて使わないことで、記述を汎用的に説明しようとしている。これがpushとpopを使わない理由だ。

また、この本では関数というのを3つに分類している。1つ目は生成関数で、これはnewなどの型のインスタンスを生成する関数。2つ目は問い合わせ関数(query)で、これはインスタンスの情報を返す関数。3つ目はコマンド関数で、これはオブジェクトを修正する関数。この3つの違いを意識するために、popというものはitemというSTACKからの情報取り出し処理と、removeというSTACKの構造を変える関数の二つに分割されている。


「Postconditionを加えると契約プログラミングになるのかな?」というコメントもあった。これに関しては、事後条件という話もよく出てくるし、6章の最初の方に、「オブジェクト指向設計の大部分は、まさしく契約による設計なのである」と書かれていることから、それで正しいと思う。またこれに関してはさらに後の章で詳しく説明されるようだ。


「Axiomsの存在意義が今一つ分からない」というのは、今回定義したものがSTACKだから逆に分かりづらくなっていると思う。自分たちはSTACKというものを「よく知っている」ために、AXIOMSの部分はなくても理解できる。しかし、もし知らないオブジェクトの仕様について、もしAXIOMSが無くてTYPES、FUNCTIONS、PRECONDITIONSしかなければ、そのオブジェクトが満たす性質についてを理解することは出来ないだろう。そこでオブジェクトの性質を表すもので、必要十分に抽象化されたものをAXIOMSで定義していると考えられる。

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

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

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


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