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

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

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

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

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

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

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

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

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

Υλοποίηση

Υλοποίηση ενός ΑΤΔ ονομάζεται η δημιουργία διαδικασιών/συναρτήσεων για κάθε αφηρημένη λειτουργία του τύπου. Τα στιγμιότυπα του ΑΤΔ αναπαρίστανται με κάποια συγκεκριμένη δομή δεδομένων την οποία διαχειρίζονται οι διαδικασίες, σύμφωνα με τις προδιαγραφές του ΑΤΔ.
Συνήθως υπάρχουν πολλοί τρόποι να υλοποιηθεί ο ίδιος ΑΤΔ, χρησιμοποιώντας διαφορετικές δομές δεδομένων. Συνεπώς, για παράδειγμα, μια αφηρημένη στοίβα μπορεί να υλοποιηθεί με μια συνδεδεμένη λίστα ή με ένα πίνακα.
Η υλοποίηση ενός ΑΤΔ συνήθως "πακετάρεται" σε μία η περισσότερες ενότητες (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, οι οποίοι μπορούν να θεωρηθούν υλοποιήσεις των ΑΤΔ Λεξικό ή ΑΤΔ Πίνακας.