Abstract datatype

Een abstract datatype (afgekort ADT) of abstract gegevenstype is een modelleerconcept uit de informatica. In een abstract datatype worden de waarden gedefinieerd die aangenomen kunnen worden en de mogelijke operaties op die waarden, zonder een concrete implementatie te geven.

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

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.

Opstelling van een ADT

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

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 ADT 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 ermee om te kunnen gaan.

Voorbeeld: De normale manier om een stack te implementeren in de meeste programmeertalen is met een array. Met een ADT kan een stack op die manier geïmplementeerd worden en voor een gebruikende programmeur toch een abstract ding zijn met operaties als push, pop, top en empty, zonder kennis van het feit dat de stack feitelijk een array is.

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 ADT's over meerdere programma's heen opnieuw te gebruiken zonder steeds dezelfde code te moeten schrijven, wat op zijn minst fouten scheelt.

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.

Voorbeeld: Een stack-ADT zou bijvoorbeeld de volgende types in kunnen voeren:

STACK(int) (een stack voor integers)
STACK(array of char) (een stack voor karakterarrays of strings)
STACK(float) (een stack voor floating point getallen)

In het geval een algemenere specificatie gewenst en mogelijk is, zou een specificatie ook kunnen spreken over bijvoorbeeld

STACK(T) (een stack voor objecten van generiek type T)

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.

Voorbeeld: Bij een stack zouden bijvoorbeeld de volgende functies gespecificeerd kunnen worden:

push: $STACK(T)\times T\rightarrow STACK(T)$
pop: $STACK(T)\not \rightarrow STACK(T)$
top: $STACK(T)\not \rightarrow T$
empty: $STACK(T)\rightarrow BOOLEAN$
new: $STACK(T)$

Hierbij zijn de functies pop en top partieel, omdat deze functies niet van toepassing zijn op stacks die leeg zijn.

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.

Voorbeeld: Gegeven de functiespecificaties in het vorige voorbeeld, zouden bij een stack de volgende axiomata opgesteld kunnen worden: Zij $t\in T$ en $s\in STACK(T)$

top(push(s, x)) = x
pop(push(s, x)) = s
empty(new())
not empty(push(s, x))

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).

Voorbeeld:Bij de functiespecificaties van hierboven zijn de volgende precondities nodig: Zij $s\in STACK(T)$

pre.pop(s) = not empty(s)
pre.top(s) = not empty(s)

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.

ADT's 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 haar weerslag gehad op de vorm van programmeertalen. Verschillende programmeertalen – waaronder Turbo Pascal en Oberon – werden aangepast en uitgebreid met faciliteiten om ADT's 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 ADT's 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.

ADT's als opstap

Hoewel de ADT's 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 ADT's (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 ADT's 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.

Bronnen

Object-oriented software construction 2nd edition
Bertrand Meyer
Prentice Hall PTR, 1997
ISBN 0-13629155-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