抄訳 PROGRAMMING WITH ABSTRACT DATA TYPES (1974)

December 28, 2022

高水準言語は、実装の詳細を意識せずに使える操作、データ構造、while文などの制御構造を提供する。 この3つは抽象とよばれる。 実装に必要なすべての抽象が言語から提供されることはないので、開発者は足りない抽象を実装しなければならない。 抽象データ型は、言語から提供される抽象を組合せて作るデータ構造であり、開発対象の問題領域にあてはまる抽象を実現する手段でもある。 抽象データ型に対する操作の実装は外部に公開されず、抽象データ型の特徴は抽象データ型に可能な操作によって決められる。 構造化プログラミングと抽象データ型を提供するプログラミング言語を開発し、抽象データ型を使うプログラムのソースコードを例示することで、ほとんどの処理を抽象データ型で実装できることを示唆した。

開発された言語は、抽象データ型の型、操作名、値の3組を指定することで、操作を呼び出す。 以下は、stack型の値sに別の抽象データ型の値tpushする操作と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)と抽象データ型を分けるのは、実装の可視性であり、抽象データ型のほうが実装の隠蔽を重視する。 そのためか、カプセル化と情報隠蔽と区別する書籍もある。 抽象データ型とオブジェクト指向を分けるのは、むしろポリモーフィズムにあるように見える。 抽象データ型の宣言は操作名と実装が同じ箇所にあり不可分であるから、抽象データ型はオブジェクト指向のインターフェースよりもクラスに近い。 操作名と操作の実装を分けて宣言できないため、開発された言語がポリモーフィズムをどう実現できるか簡単には想像できない。