抄訳 PROGRAMMING WITH ABSTRACT DATA TYPES (1974)
December 28, 2022高水準言語は、実装の詳細を意識せずに使える操作、データ構造、while文などの制御構造を提供する。 この3つを抽象とよぶ。 プログラミング言語から提供される抽象だけではプログラムを実装できないので、開発者は、足りない抽象を実装しなければならない。 抽象データ型は、言語から提供される抽象を組合せて作るデータ構造である。 抽象データ型に対する操作の実装は外部に公開されず、抽象データ型の特徴は抽象データ型に可能な操作によって決まる。 構造化プログラミングと抽象データ型を提供するプログラミング言語を開発し、抽象データ型を使うプログラムのソースコードを例示することで、ほとんどの処理が抽象データ型だけで実装可能なことを示唆した。
開発された言語は、抽象データ型の型、操作名、値の3組を指定することで、操作を呼び出す。
以下は、stack型の値sに別の抽象データ型の値tをpushする操作とstackの宣言の一例である。
createは予約語であり、引数から抽象データ型を生成する関数名である。
stack$push(s, t)
stack: cluster(element_type: type)
...
create
s: rep(element_type);
s.tp := 0;
e.e_type := element_type;
return s;
end
push operation(s: rep, v:s.e_type);
s.top := s.top+1;
s.stk[s.tp] := v;
return;
end;
開発された言語と最も近い言語は、オブジェクト指向が最初に実装されたSIMULA67である。 抽象データ型の宣言とSIMULA67のクラスには多くの共通点があるが、内部の実装の可視性が両者を分ける。 SIMULA67は、クラス内の属性と関数がクラスを宣言したブロック内部からアクセスできる。
抽象データ型と構造化プログラミングは、ソースコードの理解に役立つが、時に実行速度を劣化させる。 ソースコードの構造化と実行速度のトレードオフはコンパイラが解決すべき課題とみなされている。
論文のリンク
雑記
抽象データ型の原点になる論文であり、著者は、リスコフ置換原則で知られるリスコフ。 抽象データ型との併用を想定したプログラミングパラダイムは構造化プログラミングであり、オブジェクト指向ではない。 実装を隠蔽しモジュールをデータではなく振る舞いに依存する設計のプラクティスは、抽象データ型にもあり、オブジェクト指向のカプセル化固有のものではない。 また、オブジェクト指向(SIMULA67)と抽象データ型を分けるのは、実装の可視性であり、抽象データ型のほうが実装の隠蔽を重視する。 そのためか、カプセル化と情報隠蔽と区別する書籍もある。 論文中の抽象データ型の宣言は操作名と実装が同じ箇所にあり不可分であるから、抽象データ型はオブジェクト指向のインターフェースよりもクラスに近い。