抽象データ型とソフトウェアの危機

注意：これは、JavaScriptES6+で関数プログラミングと構成ソフトウェア技術を一から学ぶ「Composing Software」シリーズ（現在は書籍化！）の一部である。 ご期待ください。 まだまだ続きますよ!
Buy the Book | Index | < Previous | Next >

Not to be confused with:

Algebraic Data Types (ADT または AlgDT と略されることがある). 例えば、和型や積型などです。

代数的な構造。 代数的構造は、ADTと同様に、公理の代数的記述で一般的に指定される抽象代数から研究・応用されますが、コンピュータやコードの世界のずっと外側で適用されます。 代数的構造は、ソフトウェアで完全にモデル化することが不可能なものも存在しうる。

抽象データ型 (ADT) は、あるデータおよびそのデータに対する操作を表す公理によって定義された抽象的な概念である。 ADTは具体的なインスタンスで定義されておらず、実装で使用される具体的なデータ型、構造、アルゴリズムも指定されていない。

一般的な ADT の例

• List
• Stack
• Queue
• Set
• Map
• Stream

あらゆる種類のデータに対するあらゆる処理のセットを表すことが可能です。 言い換えれば、すべての可能なADTの網羅的なリストは、すべての可能な英語の文の網羅的なリストが無限であるのと同じ理由で、無限である。 ADTは不特定多数のデータに対する操作の集合という抽象的な概念であって、具体的なデータ型の特定の集合ではない。 よくある誤解は、多くの大学の講義やデータ構造の教科書で教えられているADTの具体例がADTの正体であるというものです。 そのようなテキストの多くは、データ構造を「ADT」とラベル付けした後、ADTをスキップして、データ型の実際の抽象表現に触れることなく、代わりに具体的な用語でデータ構造を記述しています。 おっと！

ADTは、半群、モノイド、ファンクター、モナドなど、多くの有用な代数的構造を表現することができます。 Fantasyland 仕様は、JavaScript における相互運用可能な実装を促進するために、ADT によって記述された代数構造の有用なカタログです。

Why ADTs?

抽象データ型は、数学的に健全で、正確かつ曖昧さのない方法で、再利用可能なモジュールを正式に定義する方法を提供するので、有用です。 これにより、有用なソフトウェア構築ブロックの広範な語彙を参照するための共通言語を共有することができます。

ADTの歴史

1960年代および1970年代初期に、多くのプログラマーおよびコンピューター サイエンスの研究者がソフトウェアの危機に関心を寄せていました。 Edsger Dijkstra がチューリング賞の講演で述べたように、

「ソフトウェア危機の主な原因は、マシンが数桁も強力になったことだ! 非常に率直に言うと、機械がない限り、プログラミングはまったく問題ありませんでした。弱いコンピューターがいくつかあったとき、プログラミングは軽い問題になり、巨大なコンピューターがある今、プログラミングは同様に巨大な問題になっています。 NASA のアポロ月着陸船と誘導装置の印刷物は、ファイリング キャビネットの高さほどもあります。 それは膨大なコードです。 そのすべての行を読んで理解しようとすることを想像してみてください。

現代のソフトウェアは、桁外れに複雑です。 Facebook は、2015 年におよそ 6,200 万行のコードでした。 1 ページあたり 50 行を印刷すると、124 万ページを埋めることになります。 それらのページを積み重ねると、1 フィートあたり約 1,800 ページ、つまり 688 フィートになります。

ソフトウェアの複雑性を管理することは、事実上すべてのソフトウェア開発者が直面する主要な課題の 1 つです。 1960 年代および 1970 年代には、今日私たちが当然と考えるような言語、パターン、およびツールはありませんでした。 リンター、インテリセンス、および静的解析ツールといったものは、まだ発明されていませんでした。

多くのソフトウェア エンジニアは、彼らが上に構築したハードウェアはほとんど機能すると指摘しています。

多くのソフトウェア エンジニアは、その上に構築したハードウェアはほとんど機能したが、ソフトウェアは複雑で絡み合い、もろかったと述べています。

• 予算オーバー
• 遅延
• バグだらけ
• 要件を満たしていない
• 保守が困難

ソフトウェアをモジュール単位で考えることさえできれば、システムの一部を動作させる方法を理解するためにシステム全体を理解する必要はありません。 ソフトウェア設計のその原則は、ローカリティとして知られています。 局所性を得るためには、システムの他の部分と切り離して理解できるようなモジュールが必要です。 モジュールは、その実装を過剰に規定することなく、曖昧さなく記述できる必要があります。

1960年代からほぼ今日に至るまで、ソフトウェアのモジュール化の状態を向上させることは、中核的な関心事でした。 バーバラ・リスコフ (SOLID OO 設計原則のリスコフ置換原則で言及されているのと同じリスコフ)、アラン・ケイ、バートランド・メイヤーなど、コンピューター サイエンスの伝説的な人々は、それらの問題を念頭に置いて、それぞれ ADT、オブジェクト指向プログラミング、およびデザイン バイ コントラクトなどのモジュラー ソフトウェアを可能にするさまざまなツールを記述および指定する作業に取り組んだのでした。 彼らはソフトウェアモジュール仕様、つまりソフトウェアモジュールが相互作用するためのインターフェイスを記述するために使用する言語の技術水準に大きく貢献しました。

リスコフは、データ抽象化、フォールトトレランス、および分散コンピューティングに関する研究により、2008 年にチューリング賞を受賞しています。 ADT はその業績において重要な役割を果たし、今日では、事実上すべての大学のコンピューター サイエンス コースに ADT がカリキュラムに含まれています。

ソフトウェアの危機は決して完全に解決されておらず、上記の問題の多くはプロの開発者なら誰でも知っているはずですが、オブジェクト、モジュール、ADT などのツールの使用方法を学ぶことは確かに役立ちます。

ADT仕様

ADT 仕様に適合性を判断するには、いくつかの基準を使用することができます。 私はこれらの基準を FAMED と呼んでいますが、このニーモニックは私が考案しただけです。 オリジナルの基準は、Liskov と Zilles が 1975 年に発表した有名な論文「Specification Techniques for Data Abstractions」で発表されました。 仕様は形式的でなければならない。 仕様の各要素の意味は、対象となるユーザーが仕様に準拠した実装を構築するのに十分なチャンスがあるように、十分に詳細に定義されていなければなりません。 仕様の各公理に対して、コードで代数的な証明を実装することが可能でなければならない

Applicable. ADTは広く適用可能であるべきである。 ADTは多くの異なる具体的なユースケースに対して一般的に再利用可能であるべきである。 コードの特定の部分に特定の言語での特定の実装を記述するADTは、おそらく物事をオーバースペックにしている。 むしろ、ADTは、一般的なデータ構造、ライブラリ部品、モジュール、プログラミング言語の機能などの動作を記述するのに最適なものである。 たとえば、スタック操作を記述する ADT や、プロミスの動作を記述する ADT などです。

最小。 ADTの仕様は最小限であるべきである。 仕様は、動作の興味深い部分や広く適用できる部分を含み、それ以上のものはないはずである。 各動作は正確かつ曖昧さなく記述されるべきだが、できるだけ具体的な、あるいは具体的な詳細を記述すべきではない。 ほとんどの ADT 仕様は、一握りの公理を使用して証明可能であるべきです。 ADT は拡張可能であるべきです。 要件の小さな変更は、仕様の小さな変更にしかつながらないはずです。

宣言型。 宣言的な仕様は、どのようにではなく、何を記述します。 ADT は、データ構造の作成手順や各操作が実行しなければならない特定の手順ではなく、物事が何であるか、および入力と出力の間の関係マッピングで記述されるべきです。

優れた ADT には以下が含まれます。 ADT は、人間が読める説明を伴わない場合、かなり簡潔なものになる可能性があります。 自然言語の説明と代数的定義を組み合わせると、仕様の誤りや読者の理解のあいまいさを解消するために、互いをチェックする役割を果たすことができます。 仕様で使用される用語を明確に定義し、曖昧さを回避します。

抽象的な署名。 具体的な型やデータ構造にリンクすることなく、期待される入力と出力を記述する。

公理（Axiom）。 Algebraic definitions of the axiom invariants used to prove that an implementation has satisfied the requirements of the specification.

Stack ADT Example

A stack is a Last In, First Out (LIFO) pile of items which allows users to interact with the stack by pushing a new item to the top of the stack, or popping the most recently pushed item from the top of the stack.

Stacks are commonly used in parsing, sorting, and data collation algorithms.

Definitions

• a: Any type
• b: Any type
• item: Any type
• stack(): an empty stack
• stack(a): a stack of a
• : a pair of item and stack

Abstract Signatures

The stack operation takes any number of items and returns a stack of those items. Typically, the abstract signature for a constructor is defined in terms of itself. Please don’t confuse this with a recursive function.

• stack(...items) => stack(...items)

Stack Operations (operations which return a stack)

• push(item, stack()) => stack(item)
• pop(stack) =>

Axioms

The stack axioms deal primarily with stack and item identity, the sequence of the stack items, and the behavior of pop when the stack is empty.

Identity

Pushing and popping have no side-effects. If you push to a stack and immediately pop from the same stack, the stack should be in the state it was before you pushed.

pop(push(a, stack())) = 

• Given: push a to the stack and immediately pop from the stack
• Should: return a pair of a and stack().

Sequence

Popping from the stack should respect the sequence: Last In, First Out (LIFO).

pop(push(b, push(a, stack())) = 

• Given: push a to the stack, then push b to the stack, then pop from the stack
• Should: return a pair of b and stack(a).

Empty

Popping from an empty stack results in an undefined item value. In concrete terms, this could be defined with a Maybe(item), Nothing, or Either. In JavaScript, it’s customary to use undefined. Popping from an empty stack should not change the stack.

pop(stack()) = 

• Given: pop from an empty stack
• Should: return a pair of undefined and stack().

Concrete Implementations

An abstract data type could have many concrete implementations, in different languages, libraries, frameworks, etc. Here is one implementation of the above stack ADT, using an encapsulated object, and pure functions over that object:

const stack = (...items) => ({
push: item => stack(...items, item),
pop: () => {
// create a item list
const newItems = ; // remove the last item from the list and
// assign it to a variable
const = newItems.splice(-1); // return the pair
return ;
},
// So we can compare stacks in our assert function
toString: () => `stack(${ items.join(',') })`
});const push = (item, stack) => stack.push(item);
const pop = stack => stack.pop();

And another that implements the stack operations in terms of pure functions over JavaScript’s existing Array type:

const stack = (...elements) => ;const push = (a, stack) => stack.concat();const pop = stack => {
const newStack = stack.slice(0);
const item = newStack.pop();
return ;
};

Both versions satisfy the following axiom proofs:

// A simple assert function which will display the results
// of the axiom tests, or throw a descriptive error if an
// implementation fails to satisfy an axiom.
const assert = ({given, should, actual, expected}) => {
const stringify = value => Array.isArray(value) ?
`` :
`${ value }`;
const actualString = stringify(actual);
const expectedString = stringify(expected);
if (actualString === expectedString) {
console.log(`OK:
given: ${ given }
should: ${ should }
actual: ${ actualString }
expected: ${ expectedString }
`);
} else {
throw new Error(`NOT OK:
given ${ given }
should ${ should }
actual: ${ actualString }
expected: ${ expectedString }
`);
}
};// Concrete values to pass to the functions:
const a = 'a';
const b = 'b';// Proofs
assert({
given: 'push `a` to the stack and immediately pop from the stack',
should: 'return a pair of `a` and `stack()`',
actual: pop(push(a, stack())),
expected: 
})assert({
given: 'push `a` to the stack, then push `b` to the stack, then pop from the stack',
should: 'return a pair of `b` and `stack(a)`.',
actual: pop(push(b, push(a, stack()))),
expected: 
});assert({
given: 'pop from an empty stack',
should: 'return a pair of undefined, stack()',
actual: pop(stack()),
expected: 
});

Conclusion

• An Abstract Data Type (ADT) is an abstract concept defined by axioms which represent some data and operations on that data.
• 抽象データ型は、どのようにではなく、何に焦点を合わせています (宣言的に枠組みされ、アルゴリズムやデータ構造を指定しません)。
• ADT は、数学的に健全で、正確で、曖昧さのない方法で、再利用可能なモジュールを正式に定義する方法を提供します。
• ADT は、1970 年代の CLU プログラミング言語に関する Liskov と学生たちの仕事から生まれました。
• ADT は、人間が読める記述、定義、抽象的な署名、および正式に検証可能な公理を含むべきです。

Bonus tip: 関数をカプセル化すべきかどうかわからない場合、自分のコンポーネント用の ADT にそれを含むかどうか自問します。 そのため、必須でない場合、他の操作との一貫性がない場合、またはその仕様が変わりそうな場合は、カプセル化します。

用語集

• 公理は数学的に正しい文で、必ず真であることが必要です。
• 数学的に正しいとは、各用語が数学的によく定義されており、それに基づいて曖昧さのない証明可能な事実の記述を行うことが可能であることを意味します

次のステップ

EricElliottJS.com には、このようなテーマに関する何時間もビデオレッスンや対話形式の練習があります。 このコンテンツが気に入ったら、ぜひ参加をご検討ください。