抽象データ型とは？意味をやさしく解説

抽象データ型（ADT）とは

抽象データ型（Abstract Data Type: ADT）とは、データ構造とそれに対する操作をセットで定義したデータ型のことです。通常のデータ型では、変数に値を束縛しますが、抽象データ型では、データ構造と操作のまとまりが値に相当します。

抽象データ型を使用しない場合、データ構造や操作のアルゴリズムを変更すると、ソースコード全体に影響が及び、修正が困難になることがあります。しかし、抽象データ型では、データとその操作が一体化されているため、実装部分を変更するだけで修正が完了します。

抽象データ型の歴史

抽象データ型の概念は、1960年代の構造化プログラミングの時代に、すでにその萌芽が見られました。段階的詳細化や制御構造の利用とともに、データ構造とコードの連携、データ構造の変更によるソースコードの散在といった問題への対処が議論されました。

1974年、バーバラ・リスコフが提案したプログラミング言語CLUにおいて、データ抽象の具体的な手法として抽象データ型が導入されました。

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

抽象データ型は、実装を隠蔽するインターフェースを提供します。ユーザーは実装ではなくインターフェースに関心を持つため、実装は将来的に変更される可能性があります。

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

例えば、二分探索木という抽象データ型は、二分木、AVL木、赤黒木、配列など、様々な方法で実装できます。しかし、どの実装であっても、「挿入」「削除」「検索」といった同じ操作が可能です。

抽象データ構造

抽象データ構造とは、具体的なデータ構造の実装に依存せず、操作の集合とその計算量によって定義されるデータのための抽象的な領域のことです。具体的なデータ構造の選択は、アルゴリズムの効率的な実装に重要ですが、抽象データ構造の選択は、効率的なアルゴリズムの設計とその計算量の推定に不可欠です。

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

具体例：有理数の抽象データ型

有理数は、コンピュータ上で直接扱うことができません。そこで、有理数を抽象データ型として定義します。

コンストラクタ:
分子 a と分母 b の2つの整数を用いて、有理数のインスタンスを作成します。

関数:
加算、減算、乗算、除算、指数計算、比較、約分、実数への変換などの関数を定義します。

例えば、有理数 a/b と c/d の乗算は、ac/bd と定義されます。完全な記述のためには、それぞれの関数の入力、出力、実行前条件、実行後条件、抽象データ型に対する仮定も記述する必要があります。

まとめ

抽象データ型は、データの操作と構造を一体化し、実装の詳細を隠蔽することで、ソフトウェアの保守性、柔軟性、再利用性を高めるための重要な概念です。プログラミングにおける抽象化の原則を体現するものであり、大規模なソフトウェア開発において不可欠な要素となっています。

参考文献

落水浩一郎『ソフトウェア工学実践の基礎－分析・設計・プログラミング』日科技連出版社、1993年。
飯泉純子, 大槻繁『ずっと受けたかったソフトウェア設計の授業』翔泳社。
D.L.Parnas (1975), Use of the concept of transparency in the design of hierarchically structured systems
D.L.Parnas (1971), Information Distribution Aspects of Design Methodology
B.H.Liskov, S.N.Zilles (1974), Programming with Abstract Data Type
Niklaus Wirth (1971), Program Development by Stepwise Refinement
N.Gehani (1980), Program Development by Stepwise Refinement and Related Topics
二木厚吉 (1996), 代数モデルの基礎
鳥居宏次 , 二木厚吉 , 真野芳久 (1984), プログラミング方法論の展望
二木厚吉、中川中著「第４章：抽象データ型とOBJ２」、井田哲雄、田中二郎編『続新しいプログラミング・パラダイム』1990年。

抽象データ型