Abstract datatype

Van Wikipedia

Een abstract datatype (afgekort ADT) of abstract gegevenstype is een modelleerconcept uit de informatica. De term is afgeleid van de Engelse term abstract data type.

ADTs worden gebruikt om bestaande programmeertalen uit te breiden met datatypes die niet in die talen ingebouwd zijn. Deze datatypes zijn van een hoger abstractieniveau dan de types die ingebouwd zijn in de programmeertaal die voor implementatie gebruikt wordt en zijn ieder voorzien van specifieke operaties om instanties van het ADT te bewerken.

Het is van belang op te merken dat de term abstract bij ADTs verwijst naar het abstractieniveau van het ADT (als in abstractie in de wiskunde, het abstracte denken) en niet naar de mogelijkheid om stukken implementatie weg te laten (zoals bij abstracte klassen).

Inhoud 1 Achtergronden 2 Opstelling van een ADT 2.1 Het concept 2.2 Specificatie van een ADT 3 ADTs als concept en als taalonderdeel 4 ADTs als opstap 5 Bronnen 6 Bronnen en referenties

[bewerk] Achtergronden

Het concept van een ADT is op komen zetten in de jaren 1960 en '70, toen de eerste programmeertalen met een duidelijk hoger abstractieniveau dan machinetaal en assembly gemeengoed werden. In dezelfde periode begon de informatica zich langzaam te onderscheiden als specifieke tak van de wiskunde en begonnen onderzoekers als John McCarthy, Tony Hoare, Donald Knuth en Edsger Dijkstra een stevige, formele basis op te bouwen voor het ontwerpen van computerprogramma's.

Naarmate het inzicht in dit ontwerpproces groeide, bleek het steeds wenselijker te zijn om op een hoger abstractieniveau te kunnen redeneren over datastructuren die in een programma gebruikt worden. Om een programma zo te modelleren dat de oplossing van een gegeven probleem inzichtelijk wordt, werd het bijvoorbeeld wenselijk gevonden om over een conceptuele stack te praten en niet alleen maar over een "array dat op een bepaalde manier gebruikt wordt". Het invoeren van dergelijke concepten maakte het mogelijk om op een hoger niveau te redeneren over het functioneren van (delen van) een programma en over de behandeling van gegevens binnen een programma.

Naarmate programma's groter en complexer werden, werd echter ook meer en meer de noodzaak gevoeld om het abstractieniveau niet alleen op papier te verhogen (in het ontwerp), maar om dezelfde abstracties ook door te voeren in de programma's zelf: om het mogelijk te maken binnen een computerprogramma te programmeren met types die rijker en abstracter zijn dan alleen de types die een programmeertaal biedt en om zo het verschil tussen het concept van een datastructuur en zijn uiteindelijke implementatie te verstoppen voor de gebruiker. De programmastructuren die opgesteld werden om deze conceptuele uitbreiding van het typesysteem van een programmeertaal mogelijk te maken, worden abstracte datatypen genoemd.

De term abstract datatype is wellicht (maar niet zeker) terug te voeren op een publicatie in de Communications of the ACM uit 1974 van Barbara Liskov en John Zilles en op een publicatie uit 1977 van John Guttag.

[bewerk] Opstelling van een ADT

Heel plat gezegd is een ADT een conceptuele datastructuur die in een programmeertaal geïmplementeerd wordt en daarna letterlijk als datastructuur in broncode gebruikt kan worden.

[bewerk] Het concept

De essentie van een ADT is dat een programmeur kan werken met de conceptuele datastructuur en zich niet langer hoeft te bekommeren om hoe die structuur intern in elkaar zit (want uiteraard moet de ATD geïmplementeerd worden met de datastructuren die in de programmeertaal ingebouwd zitten). Om dit mogelijk te maken, bestaat een ADT uit een heel "pakket" van zaken die ertoe dienen om de abstractie voor de gebruiker in stand te houden. Uiteraard is een van deze zaken de interne implementatie van de datastructuur, waar de gebruiker uiteindelijk een verwijzing naar krijgt om met de ADT te kunnen werken. Maar om de abstractie in stand te houden, hoort bij een gegeven ADT ook een verzameling functies en procedures die bewerkingen op een (instantie van een) ADT uit kunnen voeren. Door van deze functies gebruik te maken, hoeft de gebruiker van een ADT niet "in de ADT te kijken" om er mee om te kunnen gaan.

Het onderscheid tussen concept en implementatie dat zo bereikt wordt, heeft een aantal voordelen. Niet alleen wordt het mogelijk om op een hoog niveau te redeneren over programma's en programmabouw, maar het wordt ook mogelijk voor een programmeur om makkelijk om te gaan met een datastructuur die door iemand anders ontwikkeld is zonder het risico te lopen zijn programma stuk te maken omdat de programmeur de datastructuur verkeerd gebruikt. Het wordt ook mogelijk om de interne implementatie van de ADT (met mate) aan te passen om bijvoorbeeld een efficiëntere structuur te verkrijgen, zonder dat de rest van het programma omvalt. En in een programmeertaal die het toestaat om een programma te verdelen in losse modules wordt het ook mogelijk om ADTs over meerdere programma's heen opnieuw te gebruiken zonder steeds dezelfde code te moeten schrijven (wat op zijn minst fouten scheelt).

[bewerk] Specificatie van een ADT

Richting de "buitenwereld" is het belangrijkste onderdeel van een ADT ongetwijfeld de specificatie. De specificatie legt de eigenschappen van het ADT vast: de naam van het nieuwe "type", de operaties die erop gedefinieerd zijn, de werking van die operaties en de voorwaarden die de operaties stellen om correct te werken. Deze specificatie vertelt aan de programmeurs "buiten" het ADT hoe ze met instanties van het ADT om moeten gaan.

Voor degene die het ADT implementeert, is het van belang om de specificatie op een abstract niveau te houden en niet in implementatiedetails te treden. Bertrand Meyer geeft in zijn Object-Oriented Software Construction een voorbeeld van de vereisten aan de opstelling en specificatie van een ADT en wijst erop dat een goede specificatie van een ADT vooral aan drie voorwaarden moet voldoen:

• De specificatie moet precies zijn en niet ambigu.
• De specificatie moet compleet zijn in zijn beschrijving van het effect van operaties.
• De specificatie mag niet overcompleet zijn, in die zin dat de specificatie de ADT niet op een bepaalde implementatie vast moet pinnen.

Een goede specificatie van een ADT bestaat in hoofdlijnen uit vier onderdelen (hoewel deze onderdelen niet altijd los van elkaar gepresenteerd worden):

Het type

Het eerste stuk van een specificatie moet vastleggen welke type(s) door een ADT beschikbaar gesteld worden aan gebruikers.

De functies

Een abstracte specificatie van de functies die bij het ADT horen. Deze functies moeten dusdanig gespecificeerd worden dat hun effect duidelijk is, maar dat ze niet de ADT op een implementatie vastpinnen. Een mogelijkheid hiervoor is om functies vast te leggen met woorden, maar ook een specificatie in de stijl van de wiskunde is mogelijk. Hierbij kan het nodig zijn om met partiële functies te werken, omdat er gevallen kunnen zijn waarin een functie niet toegepast kan worden op een ADT.

De functie new in het voorgaande voorbeeld is een typisch voorbeeld van een functie die een ADT onderscheidt van een constructie in de pure wiskunde: het is de functie waarmee een nieuwe instantie van een stack-ADT aangemaakt wordt. In de wiskunde is zoiets uiteraard niet nodig, binnen een computerprogramma is deze functie onmisbaar: niet alleen maakt een dergelijke functie het mogelijk om een nieuwe instantie van een ADT correct te initialiseren, een dergelijke functie is ook nodig om een nieuwe instantie aan te kunnen maken zonder het binnenwerk van een ADT zichtbaar te moeten maken voor de gebruiker.

De axiomata

Aangezien de functies niet tot op dat niveau gespecificeerd mogen worden dat hun interne werking uit de specificatie blijkt, is het vaak noodzakelijk om de functies te omschrijven in plaats van helemaal uit te specificeren. Middels axiomata kunnen eigenschappen van functies en functiecatenaties vastgelegd worden op een manier die de abstractie van een ADT niet openbreekt.

De precondities

Zoals eerder opgemerkt is het soms nodig om bij een ADT partiële functies op te stellen en niet totale functies: in sommige gevallen kan een functie gewoon niet toegepast worden op een specifieke instantie van een ADT. In deze gevallen is het nodig om vast te leggen wanneer een gegeven functie wel en niet van toepassing is. Dit wordt gedaan middels de precondities (zie ook Hoarelogica).

Het is, nogmaals, belangrijk dat een specificatie zo opgesteld wordt dat een gebruiker zonder ambiguïteit precies uit de specificatie kan halen wat hij met een ADT kan en hoe hij ermee om moet gaan, maar dat hij geen verwachtingen kan scheppen over hoe de ADT intern werkt.

[bewerk] ADTs als concept en als taalonderdeel

Het concept van een ADT is primair ontwikkeld uit de wens om programmeertalen (die normaal gesproken alleen uitgerust zijn met vrij simpele, primitieve datatypes) uit te breiden met types die een hoger abstractieniveau kennen dan wat in de talen van de jaren '60 en '70 gebruikelijk was — dat wil zeggen, hoger dan wat vrijwel direct af te beelden is op het geheugenmodel van de gemiddelde computer.

De invoering van de ADT als concept heeft echter ook zijn weerslag gehad op de vorm van programmeertalen. Verschillende programmeertalen (waaronder Turbo Pascal en Oberon) werden aangepast en uitgebreid met faciliteiten om ADTs te implementeren. Turbo Pascal bijvoorbeeld werd uitgebreid met het idee van een unit, een losse module (of bibliotheek) die functies, procedures, variabelen of zelfs hele ADTs kon bevatten. Binnen een dergelijke unit bestaat de mogelijkheid om een expliciete scheiding aan te brengen tussen wat wel en niet zichtbaar moet zijn aan de gebruiker van de unit: de interface voor het zichtbare en de implementatie voor het onzichtbare. Een stack-ADT in een dergelijke unit zou er als volgt uit kunnen zien:

UNIT StackADT;

INTERFACE
 CONST capacity = 128;
 TYPE stack = array[0..capacity - 1] of integer;

 PROCEDURE push(var s : stack, num: integer);
 PROCEDURE pop(var s : stack);
 FUNCTION top(s : stack) : integer;
 FUNCTION empty(s : stack) : boolean;
 FUNCTION new():stack;

IMPLEMENTATION
 CONST
   empty_flag = -32768;

 PROCEDURE push(var s : stack, num: integer);
  VAR
   counter : integer;
  BEGIN
   counter := capacity;
   while (s[counter - 1] = empty_flag) do counter := counter - 1;
   {s[counter] is nu de eerste vrije ruimte}
   s[counter] := num
  END

 PROCEDURE pop(var s : stack);
  VAR
   counter : integer;
  BEGIN
   counter := capacity - 1;
   while (s[counter] = empty_flag) do counter := counter - 1;
   {s[counter] is nu de top}
   s[counter] := empty_flag
  END

 FUNCTION top(s : stack) : integer;
  VAR
   counter : integer;
  BEGIN
   counter := capacity - 1;
   while (s[counter] = empty_flag) do counter := counter - 1;
   {s[counter] is nu de top}
   top := s[counter]
  END

 FUNCTION empty(s : stack) : boolean;
  BEGIN
   empty := s[0] = empty_flag
  END

 FUNCTION new():stack;
  VAR
   s : stack;
   counter : integer;
  BEGIN
   counter := 0;
   while counter < capacity do
    begin
     s[counter] := empty_flag;
     counter := counter + 1
    end
  END

Merk bij het voorgaande voorbeeld op dat deze niet geheel voldoet aan de specificatie in het eerdere hoofdstuk: we kunnen bij de voorgaande implementatie niet eeuwig elementen blijven toevoegen, op een gegeven moment is de stack vol. Een specificatie van deze ADT zou dat mee moeten nemen. Daarnaast geldt uiteraard dat het voorbeeld de waarde van empty_flag misbruikt als vlag en dus eigenlijk niet geschikt is om alle elementen van het type integer te bevatten. Ook dat zou gespecificeerd moeten worden.

[bewerk] ADTs als opstap

Hoewel de ADTs een belangrijke, conceptuele toevoeging vormden aan de bestaande programmeertalen, bleek bij gebruik al snel dat er toch nadelen aan kleven. Met name het nadeel dat het wellicht wel mogelijk is om een ADT te gebruiken zonder in de implementatie te "spieken", maar dat het toch meestal ook weer niet verboden is om te spieken. Daarnaast bleek al gauw dat het soms onhandig werd om een ADT door een groter programma heen te gebruiken en daarbij de juiste functies erbij te halen. Daarbij kwamen zowel problemen om de hoek kijken die betrekking hadden op het doorgeven van ADTs (als een ADT uit meerdere variabelen bestaat, hoe houd je ze dan bij elkaar als je een ADT doorgeeft als parameter?) als naamgevingsconflicten (als je meerdere modules invoert in een programma, kan het voorkomen dat twee modules dezelfde naam gebruiken voor een functie).

Daarnaast werd het, naarmate men meer met ADTs en dus met steeds grotere, conceptuele blokken werkte, steeds wenselijk om nog meer eigenschappen van dergelijke blokken in te voeren en als ondersteunende mechanismen in programmeertalen te verwerken. De mogelijkheid om een gegeven ADT uit te breiden bijvoorbeeld, zonder de bestaande implementatie open te moeten breken. Of om delen van een ADT opnieuw te gebruiken en andere delen aan te passen.

In 1967 verscheen de eerste versie van Simula, een programmeertaal om simulaties mee te schrijven. Deze taal gooide het over een heel andere boeg dan eerdere talen en maakte de ADT het centrale mechanisme in de taal. In plaats van een uitbreiding op het typesysteem te zijn, werd de ADT de manier om het programma te schrijven: het typesysteem werd uitgebreid om heel het programma te omvatten. Weg was de scheiding tussen data en functies, de functies en data werden samengepakt in een pakket dat niet meer los te trekken was. Dergelijke pakketten konden uitgebreid worden en tegelijkertijd aangepast. Het idee sloeg aan, eerst in de academische instellingen en zo'n vijftien jaar later ook commercieel. Meer en meer eigenschappen werden toegevoegd aan de samengepakte data en functies en zo werd de ADT, middels Simula, de opstap naar de klasse, het object en het objectgeoriënteerd programmeren.

[bewerk] Bronnen

Bronnen en referenties:

Object-oriented software construction 2nd edition Bertrand Meyer Prentice Hall PTR, 1997 ISBN 0-130629155-4 Programmeren deel 2: Het ontwerpen van algoritmen Anne Kaldewaij Bohn Stafleu van Loghum 1992 ISBN 90-313-1352-1 Programmeren deel 3: Datastructuren en standaardalgoritmen Anne Kaldewaij Bohn Stafleu van Loghum 1993 ISBN 90-313-1584-2 Learn Programming Today with turbo pascal Borland Visions Series John Wiley & Sons, 1991