Αφηρημένος τύπος δεδομένων

Στην πληροφορική, ο αφηρημένος τύπος δεδομένων (ΑΤΔ) είναι ένα μαθηματικό μοντέλο για μια συγκεκριμένη κλάση δομών δεδομένων με κοινή συμπεριφορά. Επίσης ο όρος θα μπορούσε να αναφέρεται σε ορισμένους τύπους δεδομένων μίας ή περισσότερων γλωσσών προγραμματισμού με παρόμοια σημασιολογία. Ένας Αφηρημένος Τύπος Δεδομένων ορίζεται έμμεσα, μέσω των πράξεων που μπορούν να εφαρμοστούν επ' αυτού και των μαθηματικών περιορισμών (πιθανότατα και του κόστους) των πράξεων αυτών.

Για παράδειγμα, ο ΑΤΔ Στοίβα θα μπορούσε να οριστεί μέσω τριών πράξεων: της ώθησης (push), με την οποία εισάγεται ένα αντικείμενο στην δομή, της εξαγωγής (pop), η οποία εξάγει ένα στοιχείο από τη δομή (με τον περιορισμό ότι σε κάθε εξαγωγή θα πρέπει να επιστρέφει το τελευταίο αντικείμενο που εισήχθη στη στοίβα και ακόμα δεν έχει εξαχθεί) και της ανάκτησης (peek), που επιστρέφει το περιεχόμενο του πιο πρόσφατα εισαχθέντος κόμβου, χωρίς να τον εξάγει από τη δομή. Αναλύοντας την αποδοτικότητα αλγορίθμων οι οποίοι χρησιμοποιούν στοίβες, θα μπορούσαμε να πούμε ότι όλες οι λειτουργίες διαρκούν το ίδιο ανεξάρτητα από το πλήθος των αντικειμένων που έχουν εισαχθεί στη στοίβα, και η στοίβα δεσμεύει σταθερό χώρο για κάθε αντικείμενο.

Οι ΑΤΔ αποτελούν καθαρά θεωρητικές οντότητες, οι οποίες χρησιμοποιούνται (πέραν των άλλων) στην απλοποίηση περιγραφής αφηρημένων αλγορίθμων, την ταξινόμηση και αξιολόγηση τύπων δεδομένων, και την τυπική περιγραφή συστημάτων τύπων γλωσσών προγραμματισμού. Εν τούτοις, ένας ΑΤΔ μπορεί να υλοποιηθεί με συγκεκριμένες δομές δεδομένων ή τύπους δεδομένων, με πολλούς τρόπους και σε πολλές γλώσσες προγραμματισμού, ή να περιγραφεί με μια τυπική γλώσσα προδιαγραφών. Οι ΑΤΔ συνήθως υλοποιούνται ως ξεχωριστά modules (ενότητες): Η διεπαφή (ή διαπροσωπεία) του module δηλώνει τις διαδικασίες που αντιστοιχούν στις πράξεις του ΑΤΔ, κάποιες φορές συνοδευόμενα από σχόλια που περιγράφουν τους περιορισμούς. Αυτή η στρατηγική απόκρυψης πληροφορίας επιτρέπει την αλλαγή της υλοποίησης της μονάδας, χωρίς αυτό να επηρεάσει τα προγράμματα πελάτη.

Ο όρος Αφηρημένος Τύπος Δεδομένων μπορεί επίσης να θεωρηθεί μια γενικευμένη προσέγγιση αρκετών αλγεβρικών δομών, όπως τα δικτυώματα, οι ομάδες και οι δακτύλιοι. Αυτό θα μπορούσε να θεωρηθεί υποπεριοχή του αντικειμένου της Τεχνητής Νοημοσύνης. Η έννοια του ΑΤΔ σχετίζεται με την έννοια της αφαίρεσης δεδομένων, έννοιας ιδιαίτερα σημαντικής στον Αντικειμενοστρεφή Προγραμματισμό και των design by contract μεθοδολογιών ανάπτυξης λογισμικού.

Ορισμός Αφηρημένου Τύπου Δεδομένων (ΑΤΔ)

Ένας ΑΤΔ ορίζεται ως ένα μαθηματικό μοντέλο των αντικειμένων που συνιστούν ένα τύπο δεδομένων, καθώς και το σύνολο των συναρτήσεων που εφαρμόζονται επ' αυτών. Δεν υπάρχουν συγκεκριμένες συμβάσεις για τον ορισμό των ΑΤΔ, αλλά μια ευρεία διάκριση θα μπορούσε να γίνει μεταξύ προστακτικών και συναρτησιακών τρόπων ορισμού τους.

Προστακτικοί Ορισμοί ΑΤΔ

Από την προστακτική προσέγγιση (πιο κοντά στην φιλοσοφία των προστακτικών γλωσσών προγραμματισμού) μια Αφηρημένη Δομή Δεδομένων μπορεί να γίνει αντιληπτή σαν μια μεταβλητή οντότητα, με την έννοια ότι μπορεί να βρίσκεται σε διαφορετική κατάσταση σε διαφορετικές χρονικές στιγμές. Κάποιες διαδικασίες μπορούν να αλλάξουν την κατάσταση του ΑΤΔ, συνεπώς, η σειρά αποτίμησης των διαδικασιών είναι σημαντική και η ίδια πράξη στο ίδιο αντικείμενο μπορεί να δώσει διαφορετικά αποτελέσματα αν εκτελεστεί διαφορετικές στιγμές (ακριβώς όπως οι εντολές ενός υπολογιστή ή οι εντολές και οι διαδικασίες μιας προστακτικής γλώσσας προγραμματισμού). Προκειμένου να τονιστεί αυτή η οπτική, είθισται να λέμε ότι οι πράξεις "εκτελούνται" ή "εφαρμόζονται" έναντι του "αποτιμούνται". Η προστακτική προσέγγιση συνήθως χρησιμοποιείται για την περιγραφή αφηρημένων αλγορίθμων, κάτι το οποίο περιγράφεται από τον Donald E. Knuth και μπορεί να βρεθεί εδώ: The Art Of Computer Programming.

Αφηρημένη Μεταβλητή

Οι ορισμοί των προστακτικών ΑΤΔ πολλές φορές εξαρτώνται από την έννοια μια αφηρημένης μεταβλητής, η οποία μπορεί να θεωρηθεί ο απλούστερος μη-τετριμμένος ΑΤΔ. Μια αφηρημένη μεταβλητή V είναι μια μεταβλητή οντότητα που υποστηρίζει δυο λειτουργίες:

store(V,x), όπου η x είναι μια τιμή απροσδιόριστης φύσης και
fetch(V), η οποία επιστρέφει μια τιμή,

με τον περιορισμό ότι η fetch(V) επιστρέφει την τιμή x που χρησιμοποιήθηκε στην πιο πρόσφατη εφαρμογή της store(V,x), επί της ίδιας μεταβλητής V.

Όπως σε πολλές γλώσσες προγραμματισμού, η λειτουργία store(V,x) συνήθως γράφεται V ← x (ή με κάποιο παρόμοιο συμβολισμό) και η fetch(V) υπονοείται όπου χρησιμοποιείται η τιμή της μεταβλητής V. Συνεπώς, για παράδειγμα, ο συμβολισμός V ← V+1 αποτελεί μια συντομογραφία του store(V,fetch(V) + 1). Σε αυτό τον ορισμό υπονοείται πως η ανάθεση μιας τιμής σε μια μεταβλητή U δεν επιφέρει καμία αλλαγή στην κατάσταση μιας άλλης μεταβλητής V. Προκειμένου να τεθεί αυτή η υπόθεση ρητά, θα μπορούσαμε να προσθέσουμε τον περιορισμό ότι, αν οι U και V είναι δυο διαφορετικές μεταβλητές, η ακολουθία { store(U,x); store(V,y) } είναι απολύτως ισοδύναμη με την { store(V,y); store(U,x) }.

Γενικότερα, οι ορισμό ΑΤΔ συνήθως θεωρούν ότι οποιαδήποτε λειτουργία η οποία αλλάζει την κατάσταση ενός στιγμιότυπου ενός ΑΤΔ δεν έχει καμία επίδραση στην κατάσταση οποιουδήποτε άλλου στιγμιότυπου (συμπεριλαμβανομένων των στιγμιότυπων του ίδιου ΑΤΔ), εκτός αν τα αξιώματα του ΑΤΔ υπονοούν ότι τα δυο στιγμιότυπα είναι συνδεδεμένα κατ' αυτή την έννοια. Για παράδειγμα, κατά την επέκταση του ορισμού μιας αφηρημένης μεταβλητής έτσι ώστε να υποστηρίζει αφηρημένες εγγραφές, η λειτουργία που επιλέγει ένα πεδίο από μια εγγραφή R θα πρέπει να επιστρέφει μια μεταβλητή V που αντιστοιχεί σε αυτό το κομμάτι της R.

Ο ορισμός μιας αφηρημένης μεταβλητής V μπορεί επίσης να περιορίσει τις τιμές x που μπορεί να αποθηκεύσει σε ένα συγκεκριμένο σύνολο X, το οποίο αποκαλείται εύρος ή τύπος του V. Όπως και στις γλώσσες προγραμματισμού, τέτοιοι περιορισμοί μπορούν να απλοποιήσουν την περιγραφή και την ανάλυση αλγορίθμων και να τους κάνουν πιο ευανάγνωστους.

Καλό θα ήταν να τονιστεί ότι αυτός ο ορισμός δεν υπονοεί τίποτα για το αποτέλεσμα της αποτίμησης του fetch(V) όταν η V δεν έχει αρχικοποιηθεί (δηλαδή πριν πραγματοποιηθεί κάποια πράξη εκχώρησης επί της V) και αλγόριθμοι που κάνουν κάτι τέτοιο θεωρούνται μη-αποδεκτοί, καθώς το αποτέλεσμά τους είναι μη ορισμένο. Εν τούτοις, υπάρχουν σημαντικοί αλγόριθμοι, των οποίων η αποδοτικότητα εξαρτάται σε μεγάλο βαθμό από την παραδοχή ότι επιτρέπονται τέτοια fetch, και επιστρέφουν κάποια αυθαίρετη τιμή στο εύρος της μεταβλητής.

Δημιουργία Στιγμιότυπου

Κάποιοι αλγόριθμοι χρειάζεται να δημιουργήσουν νέα στιγμιότυπα κάποιου ΑΤΔ (νέες μεταβλητές, νέες στοίβες κλπ). Για την περιγραφή τέτοιων αλγορίθμων, συνήθως συμπεριλαμβάνουμε στον ορισμό του ΑΤΔ μια λειτουργία create(), η οποία επιστρέφει ένα στιγμιότυπο του ΑΤΔ, για την οποία συνήθως ισχύει το παρακάτω αξίωμα:

Το αποτέλεσμα της create() είναι διαφορετικό από οποιοδήποτε στιγμιότυπο S που χρησιμοποιείται από τον αλγόριθμο.

Αυτό το αξίωμα μπορεί να ενδυναμωθεί έτσι ώστε να αποκλείει και τη μερική εξάρτηση με άλλα στιγμιότυπα. Από την άλλη, επιτρέπει υλοποιήσεις της create() να επιστρέφουν ένα στιγμιότυπο που έχει δημιουργηθεί παλιότερα και πλέον είναι μη προσβάσιμο από το πρόγραμμα.

Προσυνθήκες, Μετασυνθήκες και Αναλλοίωτες

Σε ορισμούς προστακτικού τύπου, τα αξιώματα συνήθως εκφράζονται με τις

προσυνθήκες, οι οποίες προσδιορίζουν πότε μπορεί να εκτελεστεί μια λειτουργία,
μετασυνθήκες, οι οποίες συνδέουν τις καταστάσεις του ΑΤΔ πριν και μετά την εκτέλεση κάθε λειτουργίας και
τις αναλλοίωτες, που προσδιορίζουν τις ιδιότητες του ΑΤΔ που δεν μεταβάλλονται από τις λειτουργίες.

Παράδειγμα: Αφηρημένη Στοίβα (προστακτική)

Ένας προστακτικός ορισμός μιας αφηρημένης στοίβας θα μπορούσε να ορίζει ότι η κατάσταση μιας στοίβας S μπορεί να μεταβληθεί μονάχα μέσω των πράξεων:

push(S,x), όπου η x είναι μια τιμή απροσδιόριστης φύσης και
pop(S), η οποία επιστρέφει μια τιμή,

με τον περιορισμό ότι

για κάθε τιμή x και αφηρημένη μεταβλητή V, η αλληλουχία { push(S,x); V ← pop(S) } είναι ισοδύναμη με την { V ← x };

Καθώς η ανάθεση { V ← x }, - εξ ορισμού - δεν μπορεί να αλλάξει την κατάσταση της S, η παραπάνω συνθήκη υπονοεί ότι η { V ← pop(S) } επαναφέρει την S στην κατάσταση που είχε πριν την { push(S,x) }. Από αυτή τη συνθήκη και τις ιδιότητες των αφηρημένων μεταβλητών προκύπτει ότι, για παράδειγμα, η ακολουθία: { push(S,x); push(S,y); U ← pop(S); push(S,z); V ← pop(S); W ← pop(S); }, όπου x,y, and z είναι κάποιες τιμές και οι U, V, W είναι ανά δυο διαφορετικές μεταβλητές, είναι ισοδύναμη με την ακολουθία: { U ← y; V ← z; W ← x }.

Στα παραπάνω υπονοείται ότι πράξεις επί ενός στιγμιότυπου της στοίβας δεν επηρεάζουν την κατάσταση οποιουδήποτε άλλου στιγμιότυπου του ΑΤΔ, συμπεριλαμβανομένων και των στιγμιότυπων στοίβας. Τυπικά:

Για κάθε τιμές x,y και διαφορετικές στοίβες S,T, η ακολουθία { push(S,x); push(T,y) } είναι ισοδύναμη με την { push(T,y); push(S,x) }.

Ο ορισμός του ΑΤΔ Στοίβα συνήθως περιλαμβάνει και μια λογική συνάρτηση empty(S) και μια λειτουργία create() η οποία επιστρέφει ένα στιγμιότυπο στοίβας, θεωρώντας αξιωματικά τα παρακάτω:

create() ≠ S για κάθε στοίβα S (μια ολοκαίνουρια στοίβα είναι διακριτή από όλες όσες έχουμε δημιουργήσει ως τώρα)
empty(create()) (μια στοίβα όταν δημιουργείται είναι άδεια)
not empty(push(S,x)) (η ώθηση στοιχείου δεν μπορεί να οδηγήσει σε άδεια στοίβα)

Προσέγγιση Μοναδικού Στιγμιότυπου

Κάποιες φορές ένας ΑΤΔ ορίζεται σαν να υπάρχει μόνο ένα στιγμιότυπο του κατά την εκτέλεση του αλγορίθμου και όλες οι πράξεις εφαρμόζονται επί τούτου, κάτι το οποίο δεν δηλώνεται ρητά. Για παράδειγμα, η παραπάνω αφηρημένη στοίβα θα μπορούσε να έχει οριστεί με λειτουργίες push(x) και pop(), οι οποίες εφαρμόζονται επί του μοναδικού στιγμιότυπου στοίβας. Ορισμοί ΑΤΔ αυτής της κατηγορίας μπορούν πολύ εύκολα να τροποποιηθούν έτσι ώστε να υποστηρίζεται ύπαρξη πολλαπλών στιγμιότυπων, προσθέτοντας μια παράμετρο στιγμιότυπου σε κάθε λειτουργία που χρησιμοποιεί/μεταβάλλει το στιγμιότυπο (όπως το S στο προηγούμενο παράδειγμα).

Από την άλλη, κάποιοι ΑΤΔ δεν έχει ιδιαίτερο νόημα να δηλωθούν χωρίς να υπονοείται δυνατότητα ύπαρξης πολλαπλών στιγμιότυπων. Αυτές είναι οι περιπτώσεις στις οποίες μια λειτουργία παίρνει ως παραμέτρους δυο διαφορετικά στιγμιότυπα του ΑΤΔ, όπως, για παράδειγμα, αν "επαυξήσουμε" την δήλωση του ΑΤΔ Στοίβα με μια λειτουργία compare(S,T), η οποία ελέγχει αν δυο στοίβες S και T περιέχουν τα ίδια μενα και με την ίδια σειρά.

Συναρτησιακοί Ορισμοί ΑΤΔ

Ένας άλλος τρόπος να ορίσουμε έναν ΑΤΔ - πιο κοντά στη φιλοσοφία του συναρτησιακού προγραμματισμού - είναι να θεωρήσουμε κάθε κατάσταση της δομής σαν μια ξεχωριστή οντότητα. Από αυτή τη σκοπιά, κάθε διαδικασία που μεταβάλλει τον ΑΤΔ μοντελοποιείται σαν μια μαθηματική συνάρτηση που δέχεται σαν όρισμα την παλιά κατάσταση και επιστρέφει την νέα σαν μέρος του αποτελέσματος. Εν αντιθέσει με τις "προστακτικές διαδικασίες", αυτές οι συναρτήσεις δεν έχουν παρενέργειες, συνεπώς, η σειρά με την οποία αποτιμούνται είναι άνευ σημασίας και η ίδια συνάρτηση εφαρμοζόμενη επί των ίδιων παραμέτρων (και των ίδιων καταστάσεων εισόδου) θα επιστρέφει πάντα τα ίδια αποτελέσματα (και τις ίδιες καταστάσεις εξόδου).

Από την συναρτησιακή προσέγγιση, δεν υπάρχει τρόπος (ούτε λόγος) να δηλώσουμε μια "αφηρημένη μεταβλητή" με την σημασιολογία των προστακτικών μεταβλητών (δηλαδή να υποστηρίζει τις λειτουργίες fetch και store). Αντί να αποθηκεύουμε τις τιμές σε μεταβλητές, απλά τις περνάμε σαν παραμέτρους σε συναρτήσεις.

Παράδειγμα: Αφηρημένη Στοίβα (συναρτησιακή)

Για παράδειγμα, ένας πλήρης ορισμός συναρτησιακού τύπου του ΑΤΔ Στοίβα θα μπορούσε να χρησιμοποιεί τις τρεις παρακάτω λειτουργίες:

push: Δέχεται κάποια κατάσταση στοίβας και μια τιμή, επιστρέφει μια νέα κατάσταση στοίβας,
top: δέχεται μια κατάσταση στοίβας, επιστρέφει μια τιμή,
pop: δέχεται μια κατάσταση στοίβας, επιστρέφει μια κατάσταση στοίβας, θεωρώντας αξιωματικά τα παρακάτω:
top(push(s,x)) = x (η ώθηση στοιχείου στη στοίβα το αφήνει στην κορυφή της)
pop(push(s,x)) = s (η pop "αναιρεί" την επίδραση της push)

Σε ένα συναρτησιακό ορισμό δεν υπάρχει ανάγκη για τη λειτουργία create καθώς δεν υπάρχει η έννοια του "στιγμιότυπου στοίβας". Οι καταστάσεις στοίβας μπορούν να θεωρηθούν δυνατές καταστάσεις μιας μοναδικής δομής στοίβας, και δυο καταστάσεις στοίβας οι οποίες περιέχουν τις ίδιες τιμές με την ίδια σειρά μπορούν να θεωρηθούν ίδιες. Αυτή η προσέγγιση αντικατοπτρίζει τη συμπεριφορά κάποιων απτών υλοποιήσεων, όπως οι συνδεδεμένες λίστες με hash cons.

Αντί της create, ένας συναρτησιακός ορισμός ενός ΑΤΔ Στοίβα θα μπορούσε να υποθέσει μια ειδική κατάσταση στοίβας, την κενή στοίβα, την οποία θα μπορούσε να συμβολίζει ως Λ ή "()". Επίσης, θα μπορούσε να ορίζει μια συνάρτηση bottom() η οποία δεν παίρνει καμία παράμετρο και επιστρέφει την ειδική αυτή κατάσταση στοίβας. Να τονιστεί ότι από τα αξιώματα συνεπάγεται ότι:

push(Λ,x) ≠ Λ

Σε έναν συναρτησιακό ορισμό της στοίβας δεν χρειάζεται το κατηγόρημα empty αλλά, έναντι αυτού, μπορούμε να ελέγξουμε αν είναι άδεια ελέγχοντας αν είναι ίση με τη Λ.

Αξίζει να τονιστεί ότι τα παραπάνω αξιώματα δεν ορίζουν το αποτέλεσμα της top(s) και της pop(s), εκτός αν η S είναι μια στοίβα που επιστράφηκε από κάποιο push. Καθώς το push δεν επιστρέφει άδεια στοίβα, αυτές οι δυο διαδικασίες είναι μη ορισμένες (δηλαδή μη-αποδεκτές) όταν s = Λ. Από την άλλη, τα αξιώματα υπονοούν ότι push(s,x) = push(t,y) αν και μόνο αν x = y and s = t.

Όπως σε κάποιους κλάδους των μαθηματικών, είθισται να θεωρούμε αποδεκτές καταστάσεις στοίβας μόνο αυτές των οποίων η ύπαρξη μπορεί να αποδειχτεί από τα αξιώματα σε πεπερασμένο αριθμό βημάτων. Στον παραπάνω ορισμό του ΑΤΔ Στοίβα, αυτό σημαίνει ότι κάθε στοίβα αποτελεί μια πεπερασμένη ακολουθία τιμών, η οποία καταλήγει σε άδεια στοίβα (Λ) μετά από πεπερασμένο αριθμό από pops. Από μόνα τους τα παραπάνω αξιώματα δεν απαγορεύουν την ύπαρξη άπειρων στοιβών (από τις οποίες θα μπορούσαμε να κάνουμε "άπειρα" pop, επιστρέφοντας κάθε φορά διαφορετική κατάσταση) ή κυκλικών στοιβών (οι οποίες επιστρέφουν στην ίδια κατάσταση μετά από κάποιο πεπερασμένο πλήθος pops). Ειδικότερα, δεν απαγορεύουν την ύπαρξη καταστάσεων s έτσι ώστε pop(s) = s ή push(s,x) = s για κάποιο x. Εν τούτοις, δεδομένων των παραπάνω λειτουργιών δεν είναι δυνατό να προκύψουν τέτοιες καταστάσεις στοίβας οπότε θεωρούνται μη-υπαρκτές.

Πλεονεκτήματα των Αφηρημένων Τύπων Δεδομένων

Ενθυλάκωση

Η αφαίρεση μας εγγυάται ότι κάθε υλοποίηση του ΑΤΔ έχει κάποιες ιδιότητες και κάποιες δυνατότητες και γνωρίζοντας αυτές, και μόνον αυτές, μπορεί κάποιος να χρησιμοποιήσει ένα αντικείμενο ΑΤΔ. Ο χρήστης δεν χρειάζεται καμία τεχνική γνώση ως προς την υλοποίηση για να χρησιμοποιήσει τον ΑΤΔ. Με αυτόν τον τρόπο, η υλοποίηση μπορεί να είναι πολύπλοκη αλλά θα είναι ενθυλακωμένη σε μια απλή διαπροσωπεία όταν πραγματικά χρησιμοποιείται.

Τοπικότητα των αλλαγών

Κώδικας ο οποίος χρησιμοποιεί ένα αντικείμενο ΑΤΔ δεν χρειάζεται να τροποποιηθεί σε περίπτωση αλλαγής της υλοποίησης του ΑΤΔ. Καθώς οποιαδήποτε αλλαγή στην υλοποίηση θα πρέπει να συνεχίζει να συμφωνεί με την διαπροσωπεία, και αφού ο κώδικας που χρησιμοποιεί έναν ΑΤΔ μπορεί μόνο να αναφερθεί στις ιδιότητες και τις δυνατότητες που καθορίζονται από την διαπροσωπεία, μπορούν να γίνουν αλλαγές στην υλοποίηση του ΑΤΔ χωρίς να απαιτούνται αλλαγές στον κώδικα που τον χρησιμοποιεί.

Ευελιξία

Διαφορετικές υλοποιήσεις ενός ΑΤΔ οι οποίες έχουν τις ίδιες ιδιότητες και τις ίδιες δυνατότητες είναι ισοδύναμες και μπορούν να χρησιμοποιηθούν αδιακρίτως σε κώδικα που χρησιμοποιεί τον ΑΤΔ. Αυτό μας παρέχει μεγάλο βαθμό ευελιξίας όταν χρησιμοποιούμε αντικείμενα ΑΤΔ σε διαφορετικές περιπτώσεις. Για παράδειγμα, διαφορετικές υλοποιήσεις ενός ΑΤΔ μπορεί να είναι πιο αποδοτικές σε διαφορετικές περιπτώσεις. Είναι πιθανό λοιπόν να χρησιμοποιηθεί κάθε υλοποίηση στην περίπτωση που είναι καταλληλότερη, αυξάνοντας την συνολική αποδοτικότητα.

Τυπικές Λειτουργίες

Κάποιες λειτουργίες που συχνά ορίζονται για ΑΤΔ (πιθανώς με παρόμοιο όνομα) είναι οι εξής:

compare(s,t), η οποία ελέγχει αν είναι δύο δομές ίδιες με βάση κάποια λογική,
hash(s), η οποία υπολογίζει κάποια συνάρτηση κατακερματισμού από την κατάσταση του στιγμιότυπου,
print(s) ή show(s), η οποία δημιουργεί μια αναγνώσιμη αναπαράσταση της κατάστασης της δομής

Σε δηλώσεις προστακτικών ΑΤΔ, συναντώνται επίσης συχνά και οι παρακάτω:

create(), η οποία επιστρέφει ένα νέο στιγμιότυπο του ΑΤΔ,
initialize(s), η οποία "ετοιμάζει" ένα νεοδημιουργηθέν στιγμιότυπο s για περαιτέρω λειτουργίες ή το θέτει σε μια αρχική κατάσταση
copy(s,t), η οποία θέτει το στιγμιότυπο s σε μια κατάσταση ισοδύναμη με αυτή του t,
clone(t), η οποία εκτελεί s ← new(), copy(s,t), και επιστρέφει το s;
free(s) ή destroy(s), η οποία ανακτά την μνήμη και τους άλλους πόρους που χρησιμοποιούσε η s

Η λειτουργία free δεν έχει λογική ή νοηματική συσχέτιση με όσα προαναφέραμε, καθώς οι ΑΤΔ είναι θεωρητικές οντότητες που δεν χρησιμοποιούν μνήμη. Εν τούτοις, μπορεί να είναι απαραίτητη κατά την ανάλυση της μνήμης που χρησιμοποιεί ένας αλγόριθμος ο οποίος χρησιμοποιεί ΑΤΔ. Σε αυτή την περίπτωση απαιτούνται επιπλέον αξιώματα που ορίζουν πόση μνήμη χρησιμοποιεί κάθε στιγμιότυπο του ΑΤΔ, συναρτήσει της κατάστασης στην οποία βρίσκεται, και πόση από αυτή αποδεσμεύεται με την free.

Παραδείγματα

Ορισμένοι κλασικοί ΑΤΔ που έχουν αποδειχτεί χρήσιμοι σε πολλές κατηγορίες εφαρμογών είναι οι εξής:

Κάθε ένας από τους παραπάνω ΑΤΔ μπορεί να οριστεί με πολλούς τρόπους και παραλλαγές, όχι απαραίτητα ισοδύναμες. Για παράδειγμα, ένας ΑΤΔ Στοίβα μπορεί να έχει ή να μην έχει μια λειτουργία count η οποία επιστρέφει το πλήθος των αντικειμένων που έχουν γίνει push στη στοίβα αλλά δεν έχουν γίνει ακόμα pop. Η επιλογή αυτή διαφοροποιεί τα πράγματα όχι μόνο για τους πελάτες αλλά και για την υλοποίηση.

Υλοποίηση

Υλοποίηση ενός ΑΤΔ ονομάζεται η δημιουργία διαδικασιών/συναρτήσεων για κάθε αφηρημένη λειτουργία του τύπου. Τα στιγμιότυπα του ΑΤΔ αναπαρίστανται με κάποια συγκεκριμένη δομή δεδομένων την οποία διαχειρίζονται οι διαδικασίες, σύμφωνα με τις προδιαγραφές του ΑΤΔ.

Συνήθως υπάρχουν πολλοί τρόποι να υλοποιηθεί ο ίδιος ΑΤΔ, χρησιμοποιώντας διαφορετικές δομές δεδομένων. Συνεπώς, για παράδειγμα, μια αφηρημένη στοίβα μπορεί να υλοποιηθεί με μια συνδεδεμένη λίστα ή με ένα πίνακα.

Η υλοποίηση ενός ΑΤΔ συνήθως "πακετάρεται" σε μία η περισσότερες ενότητες (modules), η διαπροσωπεία των οποίων περιέχει μονάχα την "υπογραφή" (πλήθος και τύποι παραμέτρων και αποτελεσμάτων) των λειτουργιών. Συνεπώς, η υλοποίηση του module - δηλαδή το σώμα των διαδικασιών και η δομή που χρησιμοποιείται - μπορεί πλέον να αποκρύπτεται από τους περισσότερους πελάτες που το χρησιμοποιούν. Αυτό κάνει δυνατή την αλλαγή της υλοποίησης χωρίς να επηρεαστεί ο τρόπος με τον οποίο χρησιμοποιείται το module από τους πελάτες.

Κατά την υλοποίηση ενός ΑΤΔ, κάθε στιγμιότυπο (αν αναφερόμαστε σε προστακτικού τύπου δηλώσεις) ή κάθε κατάσταση (αν αναφερόμαστε σε συναρτησιακού τύπου δηλώσεις) συνήθως αναπαρίσταται με κάποιου τύπου χειριστή (handle).

Οι σύγχρονες αντικειμενοστραφείς γλώσσες προγραμματισμού, όπως η C++ και η Java, υποστηρίζουν κάποιου είδους ΑΤΔ. Όταν μια κλάση χρησιμοποιείται σαν τύπος, αποτελεί έναν ΑΤΔ ο οποίος αναφέρεται σε μια κρυμμένη αναπαράσταση. Με βάση αυτό το μοντέλο, ένας ΑΤΔ τυπικά υλοποιείται με μια κλάση και κάθε στιγμιότυπο του ΑΤΔ είναι ένα αντικείμενο της κλάσης αυτής. Η διαπροσωπεία του module τυπικά δηλώνει τους κατασκευαστές σαν απλές διαδικασίες και τις περισσότερες πράξεις επί του ΑΤΔ σαν μεθόδους της κλάσης. Εν τούτοις, αυτή η προσέγγιση δεν ενσωματώνει εύκολα τις πολλαπλές παραλλαγές αναπαράστασης που συναντώνται σε έναν ΑΤΔ. Θα μπορούσε επίσης να υπονομεύσει την επεκτασιμότητα των αντικειμενοστραφών προγραμμάτων.

Σε ένα καθαρά αντικειμενοστραφές πρόγραμμα το οποίο χρησιμοποιεί τις διαπροσωπείες σαν τύπους, οι τύποι αναφέρονται σε συμπεριφορές κι όχι αναπαραστάσεις.

Παράδειγμα: Υλοποίηση του ΑΤΔ Στοίβα

Για παράδειγμα, παρακάτω παρουσιάζεται μια υλοποίηση του ΑΤΔ Στοίβα που περιγράφηκε παραπάνω, γραμμένη στη γλώσσα προγραμματισμού C.

Διαπροσωπεία προστακτικού τύπου

Μια διαπροσωπεία προστατικού τύπου θα μπορούσε να είναι η εξής:

typedef struct stack_Rep stack_Rep;        /* Type: instance representation (an opaque record). */
typedef stack_Rep *stack_T;                /* Type: handle to a stack instance (an opaque pointer). */
typedef void *stack_Item;                  /* Type: value that can be stored in stack (arbitrary address). */

stack_T stack_create(void);                /* Create new stack instance, initially empty. */
void stack_push(stack_T s, stack_Item e);  /* Add an item at the top of the stack. */
stack_Item stack_pop(stack_T s);           /* Remove the top item from the stack and return it . */
int stack_empty(stack_T ts);               /* Check whether stack is empty. */

Η υλοποίηση αυτή θα μπορούσε να χρησιμοποιηθεί ως εξής:

#include <stack.h>            /* Include the stack interface. */
stack_T t = stack_create();   /* Create a stack instance. */
int foo = 17;                 /* An arbitrary datum. */
t = stack_push(t, &foo);      /* Push the address of 'foo' onto the stack. */
…
void *e = stack_pop(t);       /* Get the top item and delete it from the stack. */
if (stack_empty(t)) { … }     /* Do something if stack is empty. */
…

Η διαπροσωπεία αυτή μπορεί να υλοποιηθεί με διάφορους τρόπους. Θα μπορούσε να είναι ιδιαίτερα μη-αποδοτική, καθώς ο τυπικός ορισμός του ΑΤΔ που φαίνεται παραπάνω δεν προσδιορίζει πόσο χώρο θα μπορούσε να καταλαμβάνει η στοίβα στο δίσκο, όπως επίσης το πόσο θα μπορούσε να μπορούσε να διαρκέσει η εκτέλεση κάθε λειτουργίας. Επίσης, δεν προσδιορίζει αν η κατάσταση στοίβας t συνεχίζει να υπάρχει (καταλαμβάνει χώρο στο δίσκο) μετά από μια κλήση της μορφής s ← pop(t). Στην πράξη, ο τυπικός ορισμός θα πρέπει να ορίζει πως ο χώρος είναι ανάλογος του πλήθους των στοιχείων που έχουν ωθηθεί στη στοίβα και δεν έχουν ακόμα εξαχθεί, όπως επίσης πως κάθε μια από τις παραπάνω λειτουργίες θα πρέπει να διαρκεί σταθερό χρόνο, ανεξάρτητα από το πλήθος των αντικειμένων αυτών. Προκειμένου να τηρηθούν οι επιπρόσθετοι αυτοί περιορισμοί, στην υλοποίηση θα μπορούσε να χρησιμοποιηθεί συνδεδεμένη λίστα, ή ένας πίνακας δυναμικού μεγέθους μαζί με δυο ακεραίους (έναν μετρητή για τα μενα και έναν για το μέγεθος του πίνακα).

Διαπροσωπεία συναρτησιακού τύπου

Οι συναρτησιακές δηλώσεις ΑΤΔ είναι καταλληλότερες για συναρτησιακές γλώσσες προγραμματισμού και αντίστροφα. Παρά ταύτα, μια διαπροσωπεία συναρτησιακού τύπου θα μπορούσε να δοθεί ακόμα και σε μια προστακτική γλώσσα όπως η C. Για παράδειγμα:

typedef struct stack_Rep stack_Rep;          /* Type: stack state representation (an opaque record). */
typedef stack_Rep *stack_T;                  /* Type: handle to a stack state (an opaque pointer). */
typedef void *stack_Item;                    /* Type: item (arbitrary address). */

stack_T stack_empty(void);                   /* Returns the empty stack state. */
stack_T stack_push(stack_T s, stack_Item x); /* Adds x at the top of s, returns the resulting state. */
stack_Item stack_top(stack_T s);             /* Returns the item currently at the top of s. */
stack_T stack_pop(stack_T s);                /* Remove the top item from s, returns the resulting state. */

Το βασικότερο πρόβλημα είναι πως η C δεν υποστηρίζει συλλογή απορριμμάτων και αυτό κάνει αυτό το στυλ προγραμματισμού μη πρακτικό. Επιπλέον, οι ρουτίνες δέσμευσης μνήμης στη C είναι αρκετά πιο αργές σε σχέση με τις αντίστοιχες ενός τυπικού συλλέκτη απορριμμάτων, συνεπώς, το υπολογιστικό κόστος τόσο πολλών δεσμεύσεων είναι ακόμα μεγαλύτερο.

Βιβλιοθήκες ΑΤΔ

Πολλές σύγχρονες γλώσσες προγραμματισμού όπως η C++ και η Java συνοδεύονται από βιβλιοθήκες που υλοποιούν αρκετούς συνηθισμένους ΑΤΔ, όπως αυτούς που αναφέραμε νωρίτερα.

Ενσωματωμένοι ΑΤΔ

Σε κάποιες γλώσσες προγραμματισμού, ο προσδιορισμός της εσωτερικής αναπαράστασης κάποιων ενσωματωμένων τύπων είναι σκόπιμα ασαφής, ορίζοντας μόνο τις λειτουργίες που μπορούν να εφαρμοστούν επ' αυτών. Συνεπώς, τέτοιοι τύπου μπορούν να θεωρηθούν "Ενσωματωμένοι ΑΤΔ". Τέτοια παραδείγματα είναι οι πίνακες σε πολλές γλώσσες σεναρίων (script languages), όπως η Awk, η Lua και η Perl, οι οποίοι μπορούν να θεωρηθούν υλοποιήσεις των ΑΤΔ Λεξικό ή ΑΤΔ Πίνακας.

Δείτε επίσης

Αναφορές

Περαιτέρω ανάγνωση

Mitchell, John C.; Plotkin, Gordon (July 1988). «Abstract Types Have Existential Type». ACM Transactions on Programming Languages and Systems 10 (3). http://theory.stanford.edu/~jcm/papers/mitch-plotkin-88.pdf.

Εξωτερικοί Σύνδεσμοι

Abstract data type in NIST Dictionary of Algorithms and Data Structures