Abstrakti tietotyyppi

Abstrakti tietotyyppi (engl. abstract data type, ADT) on tyypin määrittely, joka määrittelee vain tyypin tietosisällön ja tyyppiin kuuluvat operaatiot, ei tyypin toteutustapaa. Toisin sanoen ADT määrittelee tarkalleen ja täydellisesti tyypin julkisen rajapinnan eikä mitään muuta. Esimerkiksi abstraktin tietotyypin Stack (pino) määrittely voisi kertoa muun muassa, että tallennettavat alkiot ovat kokonaislukuja, alkion pinon päällimmäiseksi lisäävä operaatio on push ja pinon päältä alkion poistava operaatio on pop. Tietorakenteen toteutustapaan ADT ei ota mitään kantaa.

ADT siis määrittelee eräänlaisen rakenneosan, jota voidaan käyttää muita ohjelmia rakennettaessa. Ohjelmoija voi (ja hänen pitääkin) kirjoittaa ohjelmansa siten, että se käyttää vain ADT:n määrittelyn mukaisia ominaisuuksia, jolloin ohjelma toimii edelleenkin vaikka esimerkiksi kokonaislukutaulukkoon perustuva pino vaihdettaisiinkin linkitettyyn listaan perustuvaksi pinoksi.

Abstraktit tietotyypit

Esimerkiksi kokonaisluvut ovat ADT, jotka määritellään arvoina ..., -2, -1, 0, 1, 2, ... sekä yhteen-, vähennys-, kerto- ja jakolaskutoimituksista sekä suurempi kuin, pienempi kuin jne., jotka käyttäytyvät tutun matematiikan mukaisesti (jakolasku huomioiden), riippumatta siitä, kuinka tietokone esittää kokonaisluvut. Käyttäytyminen sisältää erilaisten aksioomien noudattamisen (yhteenlaskujen assosiatiivisuus ja kommutatiivisuus jne.) sekä operaatioiden ennakkoehdot (ei voi jakaa nollalla). Tyypillisesti kokonaisluvut esitetään tietorakenteessa binäärilukuina, useimmiten kahden komplementtina, mutta ne voivat olla binäärikoodattuja desimaalilukuja tai yhden komplementteja. Useimmissa tarkoituksissa käyttäjä voi työskennellä abstraktion kanssa konkreettisen esitystavan sijaan ja käyttää tietoja ikään kuin tyyppi olisi abstrakti.

ADT ei koostu vain laskutoimituksista, vaan myös arvojen määrittelyjoukoista ja rajoituksista määriteltyjä laskutoimituksia varten. "Rajapinta" viittaa tyypillisesti vain laskutoimituksiin ja ehkä joihinkin toimintojen rajoituksiin, kuten ennakko- ja jälkiehtoihin; mutta ei muihin rajoituksiin, kuten toimintojen välisiin suhteisiin.

Esimerkiksi abstrakti pino, joka on viimeksi sisään, ensimmäiseksi ulos -rakenne, voidaan määrittää kolmella toiminnolla: push: lisää alkion pinon päällimmäiseksi; pop: poimii pinon päällimmäisen alkion; ja peek tai top: palauttaa pinon päällimmäisen alkion poistamatta sitä. Abstraktilla jonolla, joka on ensimmäiseksi sisään, ensimmäiseksi ulos -rakenne, on myös kolme toimintoa: enqueue: lisää alkion jonon viimeiseksi; dequeue: poimii jonon ensimmäisen alkion; ja front, joka käsittelee jonon ensimmäistä alkiota. Jos nämä olisivat rakenteiden koko määritelmät, näitä kahta tietorakennetta ja niiden erilaista odotettua järjestyskäyttäytymistä ei voitaisi erottaa toisistaan. Siten käyttöön otetaan rajoitus, joka pinolle määrittää, että jokainen pop- käsky palauttaa (ja poistaa) aina viimeksi työnnetyn alkion, johon ei ole vielä käytetty pop- käskyä, ja jonolle (päinvastoin) määrittää, että pop toimii ensimmäiseksi lisätylle alkiolle.

Algoritmien tehokkuutta analysoitaessa voidaan myös määritellä, että kaikki toiminnot vievät saman ajan riippumatta siitä, kuinka monta alkiota pinoon on työnnetty ja että pino käyttää vakiomäärää tallennustilaa kullekin elementille. Aikarajoja ei kuitenkaan aina pidetä osana ADT:n määritelmää.

Johdanto

Abstraktit tietotyypit ovat puhtaasti teoreettisia kokonaisuuksia, joita käytetään (muun muassa) yksinkertaistamaan abstraktien algoritmien kuvausta, luokittelemaan ja arvioimaan tietorakenteita sekä kuvaamaan muodollisesti ohjelmointikielten tyyppijärjestelmiä. ADT voidaan kuitenkin toteuttaa tietyillä tietotyypeillä tai tietorakenteilla, monin tavoin ja monilla ohjelmointikielillä; tai kuvailtuna virallisella määrityskielellä. ADT:t toteutetaan usein moduuleina: moduulin käyttöliittymä ilmoittaa ADT-toimintoja vastaavat proseduurit, joskus rajoituksia kuvaavilla kommenteilla. Tämä tiedon piilotus menetelmä mahdollistaa moduulin toteutuksen muuttamisen asiakasohjelmia häiritsemättä.

Termiä abstrakti tietotyyppi voidaan pitää myös useiden algebrallisten rakenteiden, kuten hilan, ryhmien ja renkaiden, yleisenä lähestymistapana. Abstraktien tietotyyppien käsite liittyy tiedon abstraktion käsitteeseen, joka on tärkeä olio-ohjelmoinnissa ja sopimuspohjaisessa ohjelmoinnissa.

Katso myös

• Geneerinen ohjelmointi

Aiheesta muualla

• Malmi, L. & Korhonen, A. & Karavirta V.: Tietorakenteiden luokittelua Elektroninen oppikirja / Opetusmoniste. HUT. Arkistoitu 2.7.2015. Viitattu 1.7.2015.
• Mäyrä, H.: ”3.1 Abstrakti tietotyyppi (ABSTRACT DATA TYPE)”, Tietorakenteet ja algoritmit. Määritä julkaisija! Teoksen verkkoversio (viitattu 1.7.2015). (Arkistoitu – Internet Archive)
• Wang, Peng & Cuellar, Santiago & Chlipala, Adam: Compiler verification meets cross-language linking via data abstraction. OOPSLA '14: Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, 2014. ACM. Artikkelin verkkoversio. (PDF) (englanniksi)
• Rudolf Lidl (2004). Abstract Algebra. Springer. ISBN 978-81-8128-149-4., Chapter 7, section 40.