抽象データ型

関数型プログラミングの精神に基づき、抽象データ構造の各状態は独立した実体または値として扱われます。この考え方では、各操作は副作用のない数学関数としてモデル化されます。抽象データ型を変更する操作は、古い状態を引数として受け取り、新しい状態を結果の一部として返す関数としてモデル化されます。操作の評価順序は重要ではなく、同じ引数（同じ入力状態を含む）に同じ操作を適用すると、常に同じ結果（および出力状態）が返されます。制約は、操作が満たさなければならない公理または代数法則として指定されます。

命令型プログラミングの精神に基づき、抽象データ構造は可変な実体として捉えられます。つまり、時間の概念が存在し、抽象データ構造は時間によって異なる状態をとる可能性があるということです。操作は時間の経過とともに抽象データ構造の状態を変化させるため、操作の評価順序が重要となり、同じ実体に対する同じ操作でも、実行されるタイミングによって異なる結果をもたらす可能性があります。これは、コンピュータの命令や命令型言語のコマンドとプロシージャに類似しています。この考え方を強調するために、抽象アルゴリズムを記述する際によく用いられる命令型スタイルと同様に、操作は評価されるのではなく、実行される、あるいは適用されると表現するのが一般的です。制約は通常、散文で記述されます。

抽象データ型（ADT）の説明は、多くの場合、主要な操作のみに限定されています。より詳細な説明では、ADTに対する補助的な操作が具体的に示されることが多く、例えば以下のようなものがあります。

• create()それによって、ADTの新しいインスタンスが生成されます。
• compare(s, t)これは、2つのインスタンスの状態が何らかの意味で同等であるかどうかをテストするものです。
• hash(s)インスタンスの状態から標準的なハッシュ関数を計算する。
• print(s)またはshow(s)、インスタンスの状態を人間が読みやすい形で表現する。

これらの名称は例示であり、著者によって異なる場合があります。命令型ADTの定義では、次のような記述もよく見られます。

• initialize(s)新しく作成されたインスタンスをs後続の操作のために準備するか、何らかの「初期状態」にリセットします。
• copy(s)、インスタンスを とs同等の状態にしますt。
• clone(t)s←を実行しcreate()、copy(s, t)を返しますs。
• free(s)またはdestroy(s)、によって使用されるメモリやその他のリソースを解放しますs。

ADTは理論上の実体であり「メモリを使用しない」ため、このfree操作は通常は関連性も意味もありません。ただし、ADTを使用するアルゴリズムが使用するストレージを分析する必要がある場合は、この操作が必要になることがあります。その場合、各ADTインスタンスがその状態に応じてどれだけのメモリを使用するか、そしてそのうちどれだけがプールに戻されるかを指定する追加の公理が必要になりますfree。

抽象データ型（ADT）の定義では、そのインスタンスに格納される値が、変数範囲と呼ばれる特定の集合Xの要素に限定されることがよくあります。例えば、抽象変数は整数のみを格納するように制約される場合があります。プログラミング言語と同様に、このような制約はアルゴリズムの記述と分析を簡素化し、可読性を向上させる可能性があります。

操作的なスタイルでは、複数のインスタンスがどのように処理されるか、また、あるインスタンスを変更すると他のインスタンスに影響するかどうかが不明確な場合が多い。ADT を定義する一般的なスタイルでは、アルゴリズムの実行中にインスタンスが 1 つだけ存在し、すべての操作がそのインスタンスに適用されるかのように操作を記述する。たとえば、スタックには、唯一の既存のスタックに対して操作する操作 ( x ) と () がある。pushこのスタイルのpopADT定義は、暗黙のインスタンスを使用または変更するすべての操作に明示的なインスタンス パラメータ (以下のスタックの例のSなど) を追加することで、ADT の複数の共存インスタンスを許容するように簡単に書き換えることができる。セットに対する操作やリストに対する操作のように、単一の操作が ADT の 2 つの異なるインスタンスをパラメータとして受け取る場合など、複数のインスタンスを許可しないと意味のある ADT を定義できない場合もある。unioncompare

複数インスタンス方式は、エイリアシング公理と組み合わされることがあります。つまり、() の結果は、createアルゴリズムによって既に使用されているインスタンスとは異なるということです。ADT の実装では、メモリを再利用し、create() の実装によって以前に作成されたインスタンスが生成される場合があります。ただし、そのようなインスタンスが「再利用」されていると定義することは、ADT の形式体系では困難です。

より一般的には、この公理は他のインスタンスとの部分的なエイリアシングも除外するように強化することができ、複合ADT（ツリーやレコードなど）と参照型ADT（ポインタなど）は完全に互いに排他的であると想定できます。たとえば、抽象変数の定義を拡張して抽象レコードを含める場合、レコード変数RのフィールドFに対する操作は、明らかにFに関係しますが、FはRとは別個のものであり、 Rの一部でもあります。部分的なエイリアシングの公理は、1つのレコード変数のフィールドを変更しても、他のレコードには影響しないことを示します。

アルゴリズムの分析を支援するために、各操作の計算複雑度（「コスト」）を、時間（演算の計算）と空間（値の表現）の両面から含める著者もいます。たとえば、ADTの状態に関係なく、各操作は同じ時間を要し、各値は同じ空間を要したり、ADTの「サイズ」があり、操作はADTのサイズに対して線形、二次などとなることを指定できます。C ++標準テンプレートライブラリの設計者であるAlexander Stepanovは、STL仕様に複雑度保証を含め、次のように主張しました。

抽象データ型の概念を導入した理由は、ソフトウェアモジュールの互換性を確保するためです。モジュールが同様の複雑性特性を共有していない限り、互換性のあるモジュールは実現できません。機能的には同じでも複雑性のトレードオフが異なるモジュールを別のモジュールに置き換えた場合、そのコードの利用者は不快な驚きを覚えるでしょう。データ抽象化についてどんなに詳しく説明しても、利用者はそのコードを使いたがらないでしょう。複雑性に関する記述は、インターフェースの一部として必ず含める必要があります。

他の著者たちはこれに異議を唱え、スタックADTは、操作コストの違いに関わらず、リンクリストで実装されても配列で実装されても同じであり、ADTの仕様は実装に依存しないべきだと主張している。

抽象変数は、命令型変数の意味論を持つ、最も単純な非自明な抽象データ型（ADT）とみなすことができる。抽象変数は、2つの演算、fetchおよびを許容するstore。演算定義は、抽象変数を用いて記述されることが多い。公理的意味論では、${\displaystyle V}$抽象変数の型であり、${\displaystyle X}$その内容の型はfetch関数である。${\displaystyle V\to X}$そして、store型は関数です${\displaystyle V\times X\to V}$主な制約は、常に同じ変数Vに対する直近の操作で使用されたfetch値xを返すことです。つまり、。また、値を完全に上書きすることも要求できます。storefetch(store(V,x)) = xstorestore(store(V,x1),x2) = store(V,x2)

操作的意味論では、fetch( V ) は位置Vの現在の値を返す手続きであり、store( V , xvoid ) は値xを位置Vに格納する戻り値の型を持つ手続きです。制約は、読み取りと書き込みが整合しているという形で非公式に説明されます。多くのプログラミング言語と同様に、操作store( V , x ) はV ← x (または同様の表記) と書かれることが多く、変数V がfetch値を必要とするコンテキストで使用される場合は常に( V ) が暗黙的に使用されます。したがって、たとえば、V ← V + 1 は、 ( V , ( V ) + 1)の省略形として一般的に理解されています。storefetch

この定義では、名前は常に異なることが暗黙のうちに前提とされています。つまり、変数Uに値を格納しても、別の変数Vの状態には影響しません。この前提を明示的にするために、次の制約を追加することができます。

• UとVが異なる変数である場合、シーケンス { store( U , x ); store( V , ystore ) } は { ( V , y ); store( U , x ) }と同等です。

この定義では、 Vが初期化されていないとき、つまりVに対して何らかの操作を実行する前にfetch( V )を評価した結果については何も述べていません。格納前にフェッチすることは、禁止することも、特定の結果となるように定義することも、未指定のままにすることもできます。このような操作が正当であるという前提に基づいて効率が決まるアルゴリズムもあり、変数の範囲内の任意の値を返します。storefetch

抽象スタックは後入れ先出し構造であり、一般的に次の3つの主要な操作によって定義されます。pushスタックにデータ項目を挿入する操作、popスタックからデータ項目を削除する操作、およびpeekスタックの最上位にあるデータ項目を削除せずにアクセスする操作です。完全な抽象スタック定義には、ブール値の関数（S）と、初期スタックインスタンスを返す操作（）topも含まれます。emptycreate

公理的意味論では、${\displaystyle S}$スタック状態のタイプであり、${\displaystyle X}$スタックに含まれる値の型は、次の型を持つことができます。${\displaystyle push:S\to X\to S}$、${\displaystyle pop:S\to (S,X)}$、${\displaystyle top:S\to X}$、${\displaystyle create:S}$、 そして${\displaystyle empty:S\to \mathbb {B} }$公理的意味論では、初期スタックの作成は「自明な」操作であり、常に同じ識別状態を返します。そのため、Λや"()"のような特別な記号で表されることがよくあります。empty操作述語は、次のように簡単に記述できます。${\displaystyle s=\Lambda }$または$\displaystyle s\neq \Lambda }$。

制約はpop(push(S,v))=(S,v)、 、top(push(S,v))=v、^{[ 9 ]}empty ( create) = T (新しく作成されたスタックは空である)、empty( push( S、x )) = F (スタックに何かをプッシュすると、スタックは空でなくなる) です。 これらの公理は、sが によって返されるスタックの状態でない限り、 top( s ) またはpop( s )の効果を定義しません。 はスタックを空にしないため、 s = Λの場合、これら 2 つの操作は無効であると定義できます。 これらの公理 (および副作用の欠如) から、(Λ、x ) ≠ Λ であることが推論できます。 また、( s、x ) = ( t、y )は、 x = yかつs = tの場合に限ります。pushpushpushpushpush

他の数学分野と同様に、スタックの状態は、公理から有限ステップで存在が証明できるものだけであると仮定するのが一般的です。この場合、すべてのスタックは有限個の値のシーケンスであり、有限回のpopsの後、空のスタック（Λ）になります。上記の公理だけでは、無限スタック（pop毎回異なる状態を生成する、永遠に実行可能なスタック）や循環スタック（有限回のsの後、同じ状態に戻るスタック）の存在を排除するものではありません。特に、 ( s ) = sまたは( s , x ) = sとなるような状態sを排除するものでpopはありません。しかし、与えられた操作では初期スタック状態からそのようなスタック状態を得ることができないため、それらは「存在しない」と仮定されます。poppush

抽象スタックの操作的定義では、push( S , x ) は何も返さず、pop( S ) は結果として値を返しますが、スタックの新しい状態は返しません。したがって、任意の値xと任意の抽象変数Vに対して、操作のシーケンス { push( S , x ); V ← pop( S )} はV ← xと同等であるという制約があります。定義により、代入V ← xはSの状態を変更できないため、この条件は、V ← pop( S )がS をpush( S , x )の前の状態に復元することを意味します。この条件と抽象変数の特性から、例えば、次のシーケンスが成り立ちます。

{ push( S , x ); push( S , y ); U ← pop( S ); push( S , z ); V ← pop( S ); W ← pop( S ) }

ここで、x、y、zは任意の値であり、U、V、Wは互いに異なる変数である。これは以下と同等である。

{ U ← y ; V ← z ; W ← x }

公理的意味論とは異なり、操作的意味論ではエイリアシングが発生する可能性があります。ここでは、スタックインスタンスに対する操作は、他のスタックを含む他のADTインスタンスの状態を変更しないことが暗黙のうちに想定されています。つまり、次のようになります。

• 任意の値x、y、および任意の異なるスタックSとTに対して、シーケンス { push( S、x ); push( T、ypush ) } は { ( T、y ); push( S、x ) }と同等です。

より複雑な例としては、Boom のバイナリ ツリー、リスト、バッグ、セットの抽象データ型の階層構造が挙げられます。[10] これらのデータ型はすべて、空のコンテナを構築する null、単一の要素からコンテナを構築する single、同じ型の 2 つのコンテナを結合する append という 3 つの操作によって宣言^{できます。}これらの操作に対して次のルールを順次追加することで、4 つのデータ型の完全な仕様を与えることができます。

データへのアクセスは、3つの操作に対するパターンマッチングによって指定できます。たとえば、これらのコンテナのメンバ関数は次のようになります。

関数がデータ型に関する関連規則の下で不変であることを確認するために、注意を払う必要があります。選択された方程式のサブセットによって示される各同値類において、関数はそのすべての要素に対して同じ結果を返す必要があります。

さまざまなアプリケーションで有用であることが証明されている一般的なADTには、次のようなものがあります。

これらの抽象データ型（ADT）はそれぞれ、必ずしも同等ではない、さまざまな方法やバリエーションで定義できます。たとえば、抽象スタックには、countプッシュされたがまだポップされていない項目の数を示す操作がある場合とない場合があります。この選択は、クライアントだけでなく実装にも影響を与えます。

抽象グラフィカルデータ型

コンピュータグラフィックス用のADTの拡張として、1979年に抽象グラフィカルデータ型（AGDT）が提案されました[ 11 ]。これはNadia Magnenat ThalmannとDaniel Thalmannによって導入されました^{。AGDTは、} ADTの利点に加えて、グラフィカルオブジェクトを構造的に構築する機能を提供します。

例として、上記の抽象スタックをC言語で実装した例を以下に示します。

// 型: スタックインスタンス表現 (不透明なレコード) typedef struct { // ここに実装} Stack ;// 型: スタックインスタンスに格納される値 (任意のアドレス) typedef void * Item ;// 新しい空のスタックインスタンスを作成しますStack * stack_create ( void );// スタックの先頭にアイテムを追加しますvoid stack_push ( Stack * s , Item x );// スタックの先頭の項目を削除して返しますItem stack_pop ( Stack * s );// スタックが空かどうかをチェックしますbool stack_is_empty ( Stack * s );

#include <stack.h>int main () { Stack * s = stack_create (); // 新しい空のスタックインスタンスを作成しますint x = 17 ;// x のアドレスをスタックの先頭に追加しますstack_push ( s , & x ); // x のアドレスをスタックから削除して返しますItem y = stack_pop ( s );if ( stack_is_empty ( s )) { // スタックが空の場合に何らかの処理を行うprintf ( "スタックは空です！" ); } }

// 型: スタックインスタンス表現 (不透明なレコード) typedef struct { // ここに実装} Stack ;// 型: スタックインスタンスに格納される値 (任意のアドレス) typedef void * Item ;// 空のスタック状態を返しますStack * stack_is_empty ( void );// スタック状態の先頭に項目を追加し、結果として得られるスタック状態を返しますStack * stack_push ( Stack * s , Item x );// スタック状態から最上位の項目を削除し、結果として得られるスタック状態を返しますStack * stack_pop ( Stack * s );// スタック状態の最上位項目を返しますItem stack_top ( Stack * s );