Abstract Data Types and the Software Crisis

Megjegyzés: Ez az írás a “Composing Software” sorozat része (most már könyv!), amely a funkcionális programozás és a kompozíciós szoftvertechnikák JavaScriptES6+-ban való elsajátításáról szól az alapoktól kezdve. Maradjon velünk! Még sok minden fog következni belőle!
Vásárolja meg a könyvet | Index | < Previous | Next >

Nem összekeverendő:

Algebraic Data Types (néha rövidítve ADT vagy AlgDT). Az Algebrai adattípusok a programozási nyelvek (pl. Rust, Haskell, F#) olyan komplex típusaira utalnak, amelyek bizonyos algebrai struktúrák bizonyos tulajdonságait jelenítik meg. pl. összeg típusok és szorzat típusok.

Algebrai struktúrák. Az algebrai struktúrákat az absztrakt algebrából kiindulva tanulmányozzák és alkalmazzák, amelyeket az ADT-khez hasonlóan szintén általában axiómák algebrai leírásaiban adnak meg, de a számítógépek és a kódok világán messze kívül alkalmazhatóak. Létezhet olyan algebrai struktúra, amelyet lehetetlen szoftverben teljesen modellezni. Ezzel szemben az absztrakt adattípusok specifikációként és útmutatóként szolgálnak a működő szoftverek formális ellenőrzéséhez.

Az absztrakt adattípus (ADT) egy axiómák által meghatározott absztrakt fogalom, amely bizonyos adatokat és az azokon végzett műveleteket reprezentál. Az ADT-k nem konkrét példányok formájában vannak definiálva, és nem határozzák meg az implementációkban használt konkrét adattípusokat, struktúrákat vagy algoritmusokat. Ehelyett az ADT-k csak az adattípusokat határozzák meg a műveleteik és az axiómák szempontjából, amelyeknek ezeknek a műveleteknek meg kell felelniük.

Gyakori ADT példák

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

Az ADT-k bármilyen típusú adaton végzett műveletek bármely halmazát reprezentálhatják. Más szóval, az összes lehetséges ADT kimerítő listája végtelen, ugyanazon okból, amiért az összes lehetséges angol mondat kimerítő listája végtelen. Az ADT-k a meg nem határozott adatokon végzett műveletek absztrakt fogalma, nem pedig konkrét adattípusok meghatározott halmaza. Gyakori tévhit, hogy a sok egyetemi kurzuson és adatszerkezeti tankönyvben tanított ADT-k konkrét példái jelentik az ADT-ket. Sok ilyen szöveg “ADT-ként” címkézi az adatszerkezeteket, majd kihagyja az ADT-t, és helyette konkrétan írja le az adatszerkezeteket, anélkül, hogy a hallgató valaha is megismerkedne az adattípus tényleges absztrakt reprezentációjával. Hoppá!

Az ADT-k sok hasznos algebrai struktúrát fejezhetnek ki, beleértve a félcsoportokat, monoidokat, funktorokat, monádokat stb. A Fantasyland specifikáció az ADT-k által leírt algebrai struktúrák hasznos katalógusa, amely elősegíti az interoperábilis JavaScript implementációkat. A könyvtárépítők a mellékelt axiómák segítségével ellenőrizhetik megvalósításaikat.

Miért ADT-k?

Az absztrakt adattípusok azért hasznosak, mert módot adnak arra, hogy matematikailag megalapozott, pontos és egyértelmű módon formálisan definiáljuk az újrafelhasználható modulokat. Ez lehetővé teszi, hogy közös nyelvet használjunk a hasznos szoftver-építőelemek széles körű szókincsére való hivatkozáshoz: Ötletek, amelyeket hasznos megtanulni és magunkkal vinni, amikor tartományok, keretrendszerek, sőt programozási nyelvek között mozogunk.

Az ADT-k története

A hatvanas években és a hetvenes évek elején sok programozót és informatikai kutatót érdekelt a szoftverek válsága. Ahogy Edsger Dijkstra fogalmazott Turing-díjas előadásában:

“A szoftverválság fő oka az, hogy a gépek nagyságrendekkel erősebbek lettek! Egészen nyersen fogalmazva: amíg nem voltak gépek, a programozás egyáltalán nem jelentett problémát; amikor volt néhány gyenge számítógépünk, a programozás enyhe problémává vált, és most, hogy óriási gépeink vannak, a programozás ugyanolyan gigantikus problémává vált.”

A probléma, amelyre utal, az, hogy a szoftverek nagyon bonyolultak. A NASA Apollo holdkompjának és irányítórendszerének nyomtatott változata körülbelül egy irattartószekrény magasságú. Ez rengeteg kód. Képzeljük el, hogy megpróbáljuk elolvasni és megérteni minden egyes sorát.

A modern szoftverek nagyságrendekkel bonyolultabbak. A Facebook 2015-ben nagyjából 62 millió sornyi kódot tartalmazott. Ha oldalanként 50 sort nyomtatnál ki, akkor 1,24 millió oldalt töltenél meg. Ha ezeket az oldalakat egymásra raknád, akkor körülbelül 1800 oldal jutna egy lábra, vagyis 688 láb. Ez magasabb, mint a San Francisco-i Millenium Tower, amely e cikk írásakor a legmagasabb lakóépület San Franciscóban.

A szoftverek összetettségének kezelése az egyik legnagyobb kihívás, amellyel gyakorlatilag minden szoftverfejlesztőnek szembe kell néznie. Az 1960-as és 1970-es években még nem rendelkeztek azokkal a nyelvekkel, mintákkal és eszközökkel, amelyeket ma már természetesnek veszünk. Az olyan dolgokat, mint a linterek, az intellisense és még a statikus elemző eszközök sem voltak még feltalálva.

Sok szoftverfejlesztő megjegyezte, hogy a hardver, amelyre dolgokat építettek, többnyire működött. A szoftverek azonban a legtöbbször összetettek, kuszák és törékenyek voltak. A szoftverek általában:

• Túllépték a költségvetést
• Későn
• Hibásak
• Kihagyott követelmények
• Nehéz karbantartani

Ha csak moduláris darabokban lehetne gondolkodni a szoftverekről, nem kellene megérteni az egész rendszert ahhoz, hogy megértsük, hogyan lehet a rendszer egy részét működésre bírni. A szoftvertervezésnek ezt az elvét lokalitásnak nevezik. A lokalitás eléréséhez olyan modulokra van szükség, amelyeket a rendszer többi részétől elszigetelten is meg lehet érteni. Egyértelműen le kell tudnia írni egy modult anélkül, hogy túlságosan részletezné a megvalósítását. Ezt a problémát oldják meg az ADT-k.

Az 1960-as évektől szinte napjainkig a szoftverek modularitásának fejlesztése volt az egyik legfontosabb feladat. E problémákat szem előtt tartva olyan emberek, mint Barbara Liskov (ugyanaz a Liskov, akire a SOLID OO tervezési elvekből a Liskov Substitution Principle hivatkozik), Alan Kay, Bertrand Meyer és az informatika más legendái dolgoztak a moduláris szoftvereket lehetővé tevő különböző eszközök, köztük az ADT-k, az objektumorientált programozás, illetve a szerződéses tervezés leírásán és specifikálásán.

Az ADT-k Liskov és tanítványainak a CLU programozási nyelven végzett 1974 és 1975 közötti munkájából születtek. Jelentősen hozzájárultak a szoftvermodul-specifikáció – vagyis a szoftvermodulok interakcióját lehetővé tevő interfészek leírására használt nyelv – fejlődéséhez. A formálisan bizonyítható interfész-megfelelőség jelentősen közelebb visz minket a szoftvermodularitáshoz és az interoperabilitáshoz.

Liskov 2008-ban Turing-díjat kapott az adatabsztrakcióval, a hibatűréssel és az elosztott számítástechnikával kapcsolatos munkájáért. Az ADT-k jelentős szerepet játszottak ebben az eredményben, és ma már gyakorlatilag minden egyetemi informatikai kurzus tananyagában szerepelnek az ADT-k.

A szoftverválság soha nem oldódott meg teljesen, és a fent leírt problémák közül sok minden profi fejlesztő számára ismerős lehet, de az olyan eszközök, mint az objektumok, modulok és ADT-k használatának megtanulása mindenképpen segít.

Az ADT-k specifikációja

Egy ADT specifikáció alkalmasságának megítéléséhez több kritérium is használható. Én ezeket a kritériumokat FAMED-nek nevezem, de csak a mnemonikát találtam ki. Az eredeti kritériumokat Liskov és Zilles publikálta 1975-ben a “Specification Techniques for Data Abstractions” című híres tanulmányában.”

• Formális. A specifikációknak formálisnak kell lenniük. A specifikáció minden egyes elemének jelentését elég részletesen meg kell határozni ahhoz, hogy a célközönségnek viszonylag jó esélye legyen arra, hogy a specifikációból megfelelő implementációt készítsen. Lehetővé kell tenni, hogy a specifikáció minden egyes axiómájára kódban megvalósítható legyen egy algebrai bizonyítás.
• Alkalmazható. Az ADT-knek széles körben alkalmazhatónak kell lenniük. Egy ADT-nek általában újrafelhasználhatónak kell lennie sok különböző konkrét felhasználási esetre. Egy olyan ADT, amely egy adott nyelven, a kód egy adott részében egy adott megvalósítást ír le, valószínűleg túlspecifikálja a dolgokat. Ehelyett az ADT-k a legalkalmasabbak a közös adatstruktúrák, könyvtári komponensek, modulok, programozási nyelvi jellemzők stb. viselkedésének leírására. Például egy ADT, amely a veremműveleteket írja le, vagy egy ADT, amely egy ígéret viselkedését írja le.
• Minimális. Az ADT specifikációknak minimálisnak kell lenniük. A specifikációnak a viselkedés érdekes és széles körben alkalmazható részeit kell tartalmaznia, és semmi többet. Minden viselkedést pontosan és egyértelműen kell leírni, de a lehető legkevesebb specifikus vagy konkrét részlettel. A legtöbb ADT specifikációnak egy maroknyi axióma segítségével bizonyíthatónak kell lennie.
• Bővíthető. Az ADT-knek bővíthetőnek kell lenniük. Egy követelmény kis változtatása csak kis változtatást kell, hogy eredményezzen a specifikációban.
• Deklaratív. A deklaratív specifikációk azt írják le, hogy mit, és nem azt, hogy hogyan. Az ADT-ket úgy kell leírni, hogy mik a dolgok, és a bemenetek és kimenetek közötti kapcsolati leképezések, nem pedig az adatstruktúrák létrehozásának lépéseit vagy az egyes műveletek konkrét lépéseit kell végrehajtani.

A jó ADT-nek tartalmaznia kell:

• Ember által olvasható leírást. Az ADT-k meglehetősen szűkszavúak lehetnek, ha nincs hozzájuk valamilyen ember által olvasható leírás. A természetes nyelvű leírás az algebrai definíciókkal kombinálva egymást ellenőrizve tisztázhatja a specifikációban lévő hibákat vagy az olvasó félreérthetőségét.
• Definíciók. Határozza meg egyértelműen a specifikációban használt kifejezéseket a félreértések elkerülése érdekében.
• Absztrakt aláírások. Írja le a várható bemeneteket és kimeneteket anélkül, hogy konkrét típusokhoz vagy adatstruktúrákhoz kötné őket.
• Axiómák. 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.
• Az absztrakt adattípusok arra koncentrálnak, hogy mit, és nem arra, hogy hogyan (deklaratívan vannak megfogalmazva, és nem határoznak meg algoritmusokat vagy adatstruktúrákat).
• Gyakori példák a listák, halmazok, halmazok stb.
• Az ADT-k módot adnak arra, hogy matematikailag megbízható, pontos és egyértelmű módon formálisan definiáljuk az újrafelhasználható modulokat.
• Az ADT-k Liskov és tanítványainak a CLU programozási nyelvvel kapcsolatos munkájából alakultak ki az 1970-es években.
• Az ADT-knek FAMED-nek kell lenniük. Formális, széles körben alkalmazható, minimális, bővíthető és deklaratív.
• Az ADT-knek tartalmazniuk kell egy ember által olvasható leírást, definíciókat, absztrakt aláírásokat és formálisan ellenőrizhető axiómákat.

Bonusz tipp: Ha nem vagy biztos benne, hogy egy függvényt kapszuláznod kell-e vagy sem, kérdezd meg magadtól, hogy belevennéd-e a komponensed ADT-jébe. Ne feledd, hogy az ADT-knek minimálisnak kell lenniük, tehát ha nem lényeges, hiányzik a kohézió a többi művelettel, vagy a specifikációja valószínűleg változni fog, kapszulázd be.

Glosszárium

• Az axiómák olyan matematikailag megalapozott állítások, amelyeknek igaznak kell lenniük.
• A matematikailag megalapozott azt jelenti, hogy az egyes kifejezések matematikailag jól definiáltak, így egyértelmű és bizonyítható tényállításokat lehet írni rájuk alapozva.

Következő lépések

Az EricElliottJS.com-on sok órányi videoleckét és interaktív gyakorlatokat találunk az ehhez hasonló témákban. Ha tetszik ez a tartalom, kérjük, fontolja meg a csatlakozást.