Abstract Data Types and the Software Crisis

Hinweis: Dies ist Teil der Serie „Composing Software“ (jetzt ein Buch!), in der es darum geht, funktionale Programmierung und kompositorische Softwaretechniken in JavaScriptES6+ von Grund auf zu lernen. Bleiben Sie dran. Es wird noch viel mehr davon kommen!
Buy the Book | Index | < Previous | Next >

Nicht zu verwechseln mit:

Algebraische Datentypen (manchmal abgekürzt mit ADT oder AlgDT). Algebraische Datentypen beziehen sich auf komplexe Typen in Programmiersprachen (z.B. Rust, Haskell, F#), die einige Eigenschaften spezifischer algebraischer Strukturen aufweisen, z.B. Summentypen und Produkttypen.

Algebraische Strukturen. Algebraische Strukturen werden aus der abstrakten Algebra erforscht und angewandt, die, wie ADTs, ebenfalls üblicherweise in Form von algebraischen Beschreibungen von Axiomen spezifiziert werden, aber weit außerhalb der Welt der Computer und des Codes anwendbar sind. Es kann eine algebraische Struktur existieren, die sich nicht vollständig in Software modellieren lässt. Im Gegensatz dazu dienen abstrakte Datentypen als Spezifikation und Leitfaden für die formale Überprüfung funktionierender Software.

Ein abstrakter Datentyp (ADT) ist ein abstraktes Konzept, das durch Axiome definiert ist, die bestimmte Daten und Operationen mit diesen Daten darstellen. ADTs sind nicht in Form von konkreten Instanzen definiert und spezifizieren nicht die konkreten Datentypen, Strukturen oder Algorithmen, die in Implementierungen verwendet werden. Stattdessen definieren ADTs Datentypen nur in Bezug auf ihre Operationen und die Axiome, denen diese Operationen entsprechen müssen.

Gängige ADT-Beispiele

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

ADTs können jede beliebige Menge von Operationen auf jeder Art von Daten darstellen. Mit anderen Worten, die erschöpfende Liste aller möglichen ADTs ist aus demselben Grund unendlich, aus dem die erschöpfende Liste aller möglichen englischen Sätze unendlich ist. ADTs sind das abstrakte Konzept eines Satzes von Operationen auf nicht spezifizierten Daten, nicht ein spezifischer Satz von konkreten Datentypen. Ein weit verbreiteter Irrglaube ist, dass die spezifischen Beispiele von ADTs, die in vielen Universitätskursen und Datenstrukturlehrbüchern gelehrt werden, das sind, was ADTs sind. Viele solcher Texte bezeichnen die Datenstrukturen als „ADTs“, lassen dann aber die ADTs weg und beschreiben die Datenstrukturen stattdessen in konkreten Begriffen, ohne dass der Student jemals eine tatsächliche abstrakte Darstellung des Datentyps zu Gesicht bekommt. Oops!

ADTs können viele nützliche algebraische Strukturen ausdrücken, einschließlich Halbgruppen, Monoide, Funktoren, Monaden usw. Die Fantasyland-Spezifikation ist ein nützlicher Katalog von algebraischen Strukturen, die durch ADTs beschrieben werden, um interoperable Implementierungen in JavaScript zu fördern. Bibliotheksersteller können ihre Implementierungen anhand der mitgelieferten Axiome überprüfen.

Warum ADTs?

Abstrakte Datentypen sind nützlich, weil sie eine Möglichkeit bieten, wiederverwendbare Module auf mathematisch fundierte, präzise und eindeutige Weise formal zu definieren. So können wir eine gemeinsame Sprache verwenden, um auf ein umfangreiches Vokabular nützlicher Software-Bausteine zu verweisen: Ideen, die wir lernen und mit uns tragen können, wenn wir zwischen Domänen, Frameworks und sogar Programmiersprachen wechseln.

Geschichte der ADTs

In den 1960er und frühen 1970er Jahren interessierten sich viele Programmierer und Informatikforscher für die Softwarekrise. Wie Edsger Dijkstra es in seiner Turing-Preis-Vorlesung formulierte:

„Die Hauptursache der Softwarekrise ist, dass die Maschinen um mehrere Größenordnungen leistungsfähiger geworden sind! Um es ganz offen zu sagen: Solange es keine Maschinen gab, war das Programmieren überhaupt kein Problem; als wir ein paar schwache Computer hatten, wurde das Programmieren zu einem leichten Problem, und jetzt haben wir gigantische Computer, und das Programmieren ist zu einem ebenso gigantischen Problem geworden.“

Das Problem, auf das er sich bezieht, ist, dass Software sehr kompliziert ist. Eine gedruckte Version der Apollo-Mondlandefähre und des Leitsystems der NASA ist etwa so groß wie ein Aktenschrank. Das ist eine Menge Code. Stellen Sie sich vor, Sie müssten versuchen, jede Zeile davon zu lesen und zu verstehen.

Moderne Software ist noch um Größenordnungen komplizierter. Facebook bestand 2015 aus rund 62 Millionen Codezeilen. Wenn man 50 Zeilen pro Seite ausdrucken würde, würde man 1,24 Millionen Seiten füllen. Wenn man diese Seiten stapelt, erhält man etwa 1.800 Seiten pro Fuß, also 688 Fuß. Das ist höher als der Millenium Tower in San Francisco, das derzeit höchste Wohngebäude in San Francisco.

Die Beherrschung der Softwarekomplexität ist eine der größten Herausforderungen für praktisch jeden Softwareentwickler. In den 1960er und 1970er Jahren gab es noch nicht die Sprachen, Muster oder Werkzeuge, die wir heute als selbstverständlich ansehen. Dinge wie Linters, Intellisense und sogar statische Analysewerkzeuge waren noch nicht erfunden.

Viele Software-Ingenieure stellten fest, dass die Hardware, auf die sie aufbauten, meistens funktionierte. Aber die Software war meistens komplex, verworren und spröde. Software war häufig:

• Über das Budget hinaus
• Zuspätkommen
• Buggy
• Fehlende Anforderungen
• Schwer zu warten

Wenn man Software nur in modularen Teilen denken könnte, müsste man nicht das ganze System verstehen, um zu wissen, wie ein Teil des Systems funktioniert. Dieses Prinzip der Softwareentwicklung ist als Lokalität bekannt. Um Lokalität zu erhalten, braucht man Module, die man isoliert vom Rest des Systems verstehen kann. Sie sollten in der Lage sein, ein Modul eindeutig zu beschreiben, ohne seine Implementierung übermäßig zu spezifizieren. Das ist das Problem, das ADTs lösen.

Von den 1960er Jahren bis fast in die heutige Zeit war die Verbesserung der Modularität von Software ein zentrales Anliegen. Mit diesen Problemen im Hinterkopf arbeiteten Leute wie Barbara Liskov (dieselbe Liskov, auf die im Liskov-Substitutionsprinzip der SOLID-OO-Entwurfsprinzipien Bezug genommen wird), Alan Kay, Bertrand Meyer und andere Legenden der Informatik an der Beschreibung und Spezifizierung verschiedener Werkzeuge, um modulare Software zu ermöglichen, darunter ADTs, objektorientierte Programmierung und Design by Contract.

ADTs entstanden aus der Arbeit von Liskov und ihren Studenten an der CLU-Programmiersprache zwischen 1974 und 1975. Sie trugen wesentlich zum Stand der Technik bei der Spezifikation von Softwaremodulen bei – der Sprache, die wir verwenden, um die Schnittstellen zu beschreiben, die die Interaktion von Softwaremodulen ermöglichen. Die formal nachweisbare Einhaltung von Schnittstellen bringt uns der Modularität und Interoperabilität von Software erheblich näher.

Liskov wurde 2008 mit dem Turing Award für ihre Arbeiten zu Datenabstraktion, Fehlertoleranz und verteiltem Rechnen ausgezeichnet. ADTs spielten dabei eine wichtige Rolle, und heute stehen ADTs in praktisch jedem Informatikkurs an einer Universität auf dem Lehrplan.

Die Softwarekrise wurde nie ganz gelöst, und viele der oben beschriebenen Probleme sollten jedem professionellen Entwickler bekannt sein, aber zu lernen, wie man Werkzeuge wie Objekte, Module und ADTs verwendet, ist sicherlich hilfreich.

Spezifikationen für ADTs

Es können mehrere Kriterien verwendet werden, um die Eignung einer ADT-Spezifikation zu beurteilen. Ich nenne diese Kriterien FAMED, aber ich habe nur die Eselsbrücke erfunden. Die ursprünglichen Kriterien wurden von Liskov und Zilles in ihrem berühmten Papier „Specification Techniques for Data Abstractions“ von 1975 veröffentlicht.

• Formal. Spezifikationen müssen formal sein. Die Bedeutung jedes Elements in der Spezifikation muss so detailliert definiert sein, dass die Zielgruppe eine einigermaßen gute Chance hat, aus der Spezifikation eine konforme Implementierung zu konstruieren. Es muss möglich sein, für jedes Axiom der Spezifikation einen algebraischen Beweis in Code zu implementieren.
• Anwendbar. ADTs sollten allgemein anwendbar sein. Ein ADT sollte generell für viele verschiedene konkrete Anwendungsfälle wiederverwendbar sein. Ein ADT, das eine bestimmte Implementierung in einer bestimmten Sprache in einem bestimmten Teil des Codes beschreibt, ist wahrscheinlich überspezifiziert. Stattdessen sind ADTs am besten geeignet, um das Verhalten von allgemeinen Datenstrukturen, Bibliothekskomponenten, Modulen, Programmierspracheneigenschaften usw. zu beschreiben. Zum Beispiel eine ADT, die Stapeloperationen beschreibt, oder eine ADT, die das Verhalten eines Versprechens beschreibt.
• Minimal. ADT-Spezifikationen sollten minimal sein. Die Spezifikation sollte die interessanten und allgemein anwendbaren Teile des Verhaltens enthalten und nicht mehr. Jedes Verhalten sollte präzise und eindeutig beschrieben werden, aber mit so wenig spezifischen oder konkreten Details wie möglich. Die meisten ADT-Spezifikationen sollten mit einer Handvoll von Axiomen beweisbar sein.
• Erweiterbar. ADTs sollten erweiterbar sein. Eine kleine Änderung in einer Anforderung sollte nur zu einer kleinen Änderung in der Spezifikation führen.
• Deklarativ. Deklarative Spezifikationen beschreiben das Was, nicht das Wie. ADTs sollten in Bezug auf das, was Dinge sind, und Beziehungsabbildungen zwischen Eingaben und Ausgaben beschrieben werden, nicht die Schritte zur Erstellung von Datenstrukturen oder die spezifischen Schritte, die jede Operation ausführen muss.

Eine gute ADT sollte enthalten:

• Menschenlesbare Beschreibung. ADTs können recht knapp sein, wenn sie nicht von einer von Menschen lesbaren Beschreibung begleitet werden. Die Beschreibung in natürlicher Sprache kann in Verbindung mit den algebraischen Definitionen als gegenseitige Kontrolle dienen, um Fehler in der Spezifikation oder Unklarheiten im Verständnis des Lesers zu beseitigen.
• Definitionen. Definieren Sie alle in der Spezifikation verwendeten Begriffe klar und deutlich, um Mehrdeutigkeiten zu vermeiden.
• Abstrakte Signaturen. Beschreiben Sie die erwarteten Eingaben und Ausgaben, ohne sie mit konkreten Typen oder Datenstrukturen zu verknüpfen.
• Axiome. 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.
• Abstrakte Datentypen konzentrieren sich auf das „Was“, nicht auf das „Wie“ (sie sind deklarativ formuliert und spezifizieren keine Algorithmen oder Datenstrukturen).
• Gängige Beispiele sind Listen, Stapel, Mengen, usw.
• ADTs bieten uns eine Möglichkeit, wiederverwendbare Module formal zu definieren, und zwar auf eine Weise, die mathematisch fundiert, präzise und eindeutig ist.
• ADTs sind aus der Arbeit von Liskov und Studenten an der CLU-Programmiersprache in den 1970er Jahren hervorgegangen.
• ADTs sollten FAMED sein. Formal, widely Applicable, Minimal, Extensible, and Declarative.
• ADTs sollten eine menschenlesbare Beschreibung, Definitionen, abstrakte Signaturen und formal überprüfbare Axiome enthalten.

Bonustipp: Wenn Sie sich nicht sicher sind, ob Sie eine Funktion kapseln sollten, fragen Sie sich, ob Sie sie in eine ADT für Ihre Komponente aufnehmen würden. Denken Sie daran, dass ADTs minimal sein sollten. Wenn sie also nicht essentiell ist, keine Kohäsion mit den anderen Operationen hat oder ihre Spezifikation sich wahrscheinlich ändern wird, kapseln Sie sie.

Glossar

• Axiome sind mathematisch fundierte Aussagen, die wahr sein müssen.
• Mathematisch fundiert bedeutet, dass jeder Begriff mathematisch gut definiert ist, so dass es möglich ist, auf seiner Grundlage eindeutige und beweisbare Aussagen zu machen.

Nächste Schritte

EricElliottJS.com bietet viele Stunden an Videolektionen und interaktiven Übungen zu Themen wie diesem. Wenn Ihnen diese Inhalte gefallen, sollten Sie eine Mitgliedschaft in Erwägung ziehen.