抽象データ型

抽象データ型（ちゅうしょうデータがた、英: abstract data type、ADT）とは、データ構造とその操作手続きを定義したデータ型、またはデータ抽象^{[注釈 1]}の方法の1つ。通常のデータ型であれば変数宣言で変数に束縛されるものは値であるが、抽象データ型の世界において値に相当するものはデータ構造とその操作^{[注釈 2]}のまとまり^{[注釈 3]}である。

抽象データ型を用いない場合、データ構造またはデータの操作手続きのアルゴリズムの変更を行うとソースコード中にその変更部分が散在してしまい規模によっては修正困難となるが、データとその操作がひとまとめに記載されることになる抽象データ型においては、型の定義における実装部分を変更するだけで修正が完了する。

概要

1960年代の構造化プログラミングの時点で既に、（よく知られている）段階的詳細化といった手法や制御構造の利用の励行などの他、データ構造とコードを連携させ、データ構造の変更を行うと変更部分がソースコード中に散在してしまうというそれ以前のプログラミングにおける問題点への対処にもなる、データ抽象に関する議論は現れている（『構造化プログラミング』（日本版はサイエンス社、1975年）の、全体の約半分はダイクストラによる考察だが、残り約半分はホーアとダール（Simulaの設計者）によるデータ論である）。抽象データ型はデータ抽象の具体的手法として1974年にバーバラ・リスコフの提案した言語CLUにおいて提案された。

インタフェースと実装の分離

プログラムが実装されたとき、抽象データ型は実装を隠蔽するインタフェースを表す。実装は将来において変更されうるので、抽象データ型のユーザーは実装ではなくインタフェースに関心がある。

抽象データ型の強みはユーザーから実装が隠蔽されていることである。インタフェースのみが公開されるのである。このことは、抽象データ型がいろいろな方法で実装されうることを意味するが、インタフェースに忠実な限りユーザープログラムは影響を受けないのである。

例えば、二分探索木抽象データ型はいくつかの方法で実装できる。例えば、二分木、AVL木、赤黒木、配列である。しかし実装に関わらず二分探索木は「挿入」「削除」「検索」といった同じ操作が可能である。

抽象データ構造

抽象データ構造とは、実際のデータ構造による実装に関わらず、操作の集合とその計算量により定義されるデータのための抽象的な領域のことである。

具体的なデータ構造の選択がアルゴリズムの効率的な実装にとって重要である一方、抽象データ構造の選択は効率的なアルゴリズムの設計とその計算量の推定にとって極めて重要である。

この概念はプログラミング言語の理論で用いられる抽象データ型の概念に非常に近い。多くの抽象データ構造や抽象データ型の名前は具体的なデータ構造の名前と一致する。

具体例

抽象データ型としての有理数

有理数は計算機においてはそのまま扱うことはできない。有理数の抽象データ型は以下のように定義できる。

コンストラクタ: 2つの整数 $a$ 、 $b$ を用いて有理数の抽象データ型のインスタンスを作成する。ここで $a$ は分子で $b$ は分母である。

関数: 加算,減算,乗算,除算,指数計算,比較,約分,実数への変換

完全な記述にするためには、それぞれの関数はデータに言及して記述されるべきである。例えば、有理数 $a/b$ と $c/d$ を乗算するときには結果は $ac/bd$ と定義される。通常は入力、出力、実行前条件、実行後条件、抽象データ型に対する仮定も記述される。

脚注

[脚注の使い方]

注釈

^ データ抽象（英: data abstraction）とは、データ型の詳細定義とその操作に関する手続きを情報の局所性が高まるようにソースコード中の一カ所にまとめて記述するための記法のことを言う。情報が一カ所に局所的にまとめて記載されているため、非公開（private）部分の変更であればその定義部分の詳細を変更するだけでソースコード全体の修正が完了する。データ型の詳細定義とその操作手続きの局所的記述を実現する方法は複数あり、抽象データ型はその一例である。
^ 言語に応じて名称が異なり、C++であればメンバ関数（member function）、Javaであればメソッド（method）と呼ばれる
^ データ型の値に相当するこのまとまりのことを抽象データ型の実体（インスタンス , instance）と呼ぶ。

参考文献

落水浩一郎『ソフトウェア工学実践の基礎－分析・設計・プログラミング』日科技連出版社、1993年。
飯泉純子, 大槻繁『ずっと受けたかったソフトウェア設計の授業』翔泳社。https://books.google.co.jp/books?id=gJhtVWzM4BsC&printsec=frontcover&hl=ja&sa=X&ei=Z4ubUf_NL43mkgWD1YGoDQ&ved=0CDwQ6AEwAA*v=onepage&q&f=false。
D.L.Parnas (1975), Use of the concept of transparency in the design of hierarchically structured systems, http://ivizlab.sfu.ca/arya/Papers/SW/TranspDesignHierSys.pdf
D.L.Parnas (1971), Information Distribution Aspects of Design Methodology, http://cseweb.ucsd.edu/~wgg/CSE218/Parnas-IFIP71-information-distribution.PDF
B.H.Liskov, S.N.Zilles (1974), Programming with Abstract Data Type, http://www.znu.ac.ir/members/afsharchim/lectures/p50-liskov.pdf
Niklaus Wirth (1971), Program Development by Stepwise Refinement, Communications of the ACM, Vol. 14, No. 4, April 1971, pp. 221-227, http://sunnyday.mit.edu/16.355/wirth-refinement.html
N.Gehani (1980), Program Development by Stepwise Refinement and Related Topics, http://www3.alcatel-lucent.com/bstj/vol60-1981/articles/bstj60-3-347.pdf
二木厚吉 (1996), 代数モデルの基礎 (<特集>ソフトウェア工学の基礎), https://ci.nii.ac.jp/naid/110003743901
鳥居宏次 , 二木厚吉 , 真野芳久 (1984), プログラミング方法論の展望, https://ci.nii.ac.jp/naid/110002720633
二木厚吉、中川中著「第４章：抽象データ型とOBJ２」、井田哲雄、田中二郎編『続新しいプログラミング・パラダイム』1990年。