User:Nivel999/sandbox

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

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

Οι διαχωρισμένες ενώσεις συχνά συνοδεύονται από την έννοια του κατασκευαστή, η οποία είναι παρόμοια αλλά όχι ίδια με την έννοια του κατασκευαστή μιας τάξης. Οι κατασκευαστές παράγουν τιμές της διαχωρισμένης ένωσης, δοθέντων της αρχικής τιμής της ετικέτας και μιας τιμής του αντίστοιχου τύπου.

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

Στη θεωρία τύπων, η διαχωρισμένη ένωση καλείται τύπος αθροίσματος . Οι συμβολισμοί ποικίλουν αλλά ο τύπος αθροίσματος A+B συνήθως συνοδεύεται από δύο συναρτήσεις εισαγωγής \text{inj}_1 : A \to A+B και \text{inj}_2 : B \to A+B. Η συνάρτηση απαλοιφής είναι η ανάλυση περιπτώσεων, γνωστή ως ταίριασμα προτύπων σε γλώσσες προγραμματισμού παρόμοιες με την ML: αν το e έχει τύπο A+B και τα e_1, e_2 έχουν τύπο \tau υποθέτοντας ότι x:A και y:B αντίστοιχα, τότε ο όρος \texttt{case}\ e\ \texttt{of}\ x \Rightarrow e_1 | y \Rightarrow e_2 έχει τύπο \tau. Ο τύπος αθροίσματος αντιστοιχεί στην ιντουσιονιστική λογική διάζευξη υπό τον ισομορφισμό Curry-Howard.

Ο τύπος απαρίθμησης μπορεί να θεωρηθεί ως εκφυλισμένη περίπτωση: μια διαχωρισμένη ένωση από τύπους μονάδας (unit type). Αντιστοιχεί σε ένα σύνολο από μηδενικούς κατασκευαστές (nullary constructors) και μπορεί να υλοποιηθεί ως μια απλή μεταβλητή ετικέτας, αφού δεν περιέχει καμία πληροφορία πέραν της τιμής της ετικέτας.

Πλεονεκτήματα και μειονεκτήματα[edit]

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

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

Το κύριο μειονέκτημα των διαχωρισμένων ενώσεων είναι ότι η ετικέτα καταλαμβάνει χώρο. Επειδή, συνήθως, υπάρχουν λίγες εναλλακτικές περιπτώσεις η ετικέτα μπορεί να τοποθετηθεί σε 2 ή 3 bits όπου αυτά είναι διαθέσιμα. Βέβαια, μερικές φορές, ακόμα και αυτά τα bits δεν είναι διαθέσιμα. Σε αυτή την περίπτωση μια χρήσιμη εναλλακτική είναι οι αναδιπλωμένες (folded), υπολογιζόμενες (computed) ή κωδικοποιημένες (encoded) ετικέτες όπου η τιμή της ετικέτας μπορεί να υπολογιστεί δυναμικά από τα περιεχόμενα του πεδίου της ένωσης. Συνηθισμένα παραδείγματα αυτής της περίπτωσης είναι η χρήση προκαθορισμένων τιμών , όπου, για παράδειγμα, μια συνάρτηση που επιστρέφει θετικούς αριθμούς μπορεί να επιστρέψει -1 για να σηματοδοτήσει την αποτυχία, και η χρήση τιμών φρουρών (sentinel values), οι οποίες χρησιμοποιούνται συχνά στους δείκτες με ετικέτες (tagged pointers).

Μερικές φορές οι μη διαχωρισμένες ενώσεις χρησιμοποιούνται για την εκτέλεση μετατροπών επιπέδου bit μεταξύ τύπων, κάτι που ονομάζεται reinterpret cast στη C++. Οι διαχωρισμένες ενώσεις δεν προορίζονται γι αυτό το σκοπό. Συνήθως, εκχωρείται μια καινούρια τιμή, όποτε αλλάζει η ετικέτα.

Πολλές γλώσσες υποστηρίζουν, ως ένα βαθμό, έναν καθολικό τύπο δεδομένων (universal data type), ο οποίος είναι ένας τύπος που περιλαμβάνει όλες τις τιμές όλων των άλλων τύπων, και συχνά παρέχεται κάποιος τρόπος ελέγχου του πραγματικού τύπου μιας τιμής του καθολικού τύπου. Αυτές οι τιμές αναφέρονται συχνά ως variants. Αν και οι καθολικοί τύποι δεδομένων, στα πλαίσια του τυπικού ορισμού τους, είναι συγκρίσιμοι με τις διαχωρισμένες ενώσεις, οι τελευταίες συνήθως περιλαμβάνουν ένα σχετικά μικρό αριθμό περιπτώσεων, οι οποίες αποτελούν διαφορετικούς τρόπους έκφρασης μιας συγκεκριμένης έννοιας, όπως ο κόμβος μιας δομής δεδομένων ή μια εντολή. Επίσης, υπάρχει η προσδοκία ότι όταν χρησιμοποιείται μια διαχωρισμένη ένωση κάθε πιθανή περίπτωση της θα αντιμετωπίζεται κατάλληλα. Οι τιμές ενός καθολικού τύπου δεν σχετίζονται μεταξύ τους και δεν είναι εφικτό να αντιμετωπιστούν κατάλληλα όλες όταν αυτός χρησιμοποιείται.

Όπως οι τύποι επιλογών (option types) και ο χειρισμός εξαιρέσεων έτσι και οι διαχωρισμένες ενώσεις μπορούν να χρησιμοποιηθούν για τον χειρισμό της εμφάνισης "εξαιρετικών" αποτελεσμάτων. Συχνά αυτού του είδους οι ετικέτες ενσωματώνονται στον τύπο σαν "προκαθορισμένες τιμές" και η εμφάνιση τους δεν ελέγχεται επαρκώς, γεγονός που αποτελεί μια συνήθη πηγή προγραμματιστικών λαθών. Αυτή η χρήση των διαχωρισμένων ενώσεων μπορεί να οριστεί τυπικά ως μία μονάδα (monad) με τις ακόλουθες συναρτήσεις:

\text{return}\colon A \to \left( A + E \right) = a \mapsto \text{value} \, a
\text{bind}\colon \left( A + E \right) \to \left(A \to \left(B + E \right) \right) \to \left( B + E \right) = a \mapsto f \mapsto \begin{cases} \text{err} \, e & \text{if} \ a = \text{err} \, e\\ f \, a' & \text{if} \ a = \text{value} \, a' \end{cases}

όπου "value" και "err" είναι οι κατασκευαστές του τύπου ένωσης, Α και Β είναι έγκυροι τύποι αποτελεσμάτων και Ε είναι ο τύπος των σφαλμάτων. Εναλλακτικά, το ίδιο monad μπορεί να περιγραφεί από την return και δύο επιπρόσθετες συναρτήσεις, τις fmap και join:

\text{fmap} \colon (A \to B) \to \left( \left( A + E \right) \to \left( B + E \right) \right) = f \mapsto a \mapsto \begin{cases} \text{err} \, e & \text{if} \ a = \text{err} \, e \\ \text{value} \, f \, a' & \text{if} \ a = \text{value} \, a' \end{cases}
\text{join} \colon ((A + E ) + E) \to (A + E) = a \mapsto \begin{cases} \text{err} \, e & \mbox{if} \ a = \text{err} \, e\\ \text{err} \, e & \text{if} \ a = \text{value} \, \text{err} \, e \\ \text{value} \, a' & \text{if} \ a = \text{value} \, \text{value} \, a' \end{cases}

Παραδείγματα[edit]

Έστω ότι θέλουμε να φτιάξουμε ένα δυαδικό δέντρο με ακεραίους. Στην ML θα το φτιάχναμε δημιουργώντας έναν τύπο δεδομένων όπως ο ακόλουθος:

datatype tree = Leaf
              | Node of (int * tree * tree)

Αυτή είναι μια διαχωρισμένη ένωση με δύο περιπτώσεις: η πρώτη, το φύλλο (Leaf), χρησιμοποιείται για τον τερματισμό ενός μονοπατιού του δέντρου και για τον τερματισμό των συναρτήσεων (π.χ. βασική περίπτωση σε αναδρομικές συναρτήσεις), όπως περίπου χρησιμοποιείται και η κενή τιμή (null value) στις προστακτικές γλώσσες. Η δεύτερη περίπτωση ορίζει έναν κόμβο, ο οποίος περιέχει έναν ακέραιο και ένα αριστερό και δεξί υποδέντρο. Οι Leaf και Node είναι οι κατασκευαστές που μας επιτρέπουν να παράγουμε ένα συγκεκριμένο δέντρο, όπως για παράδειγμα το ακόλουθο:

Node(5, Node(1,Leaf,Leaf), Node(3, Leaf, Node(4, Leaf, Leaf)))

που αντιστοιχεί στο παρακάτω δέντρο:

Το δέντρο που παράγεται από τους παραπάνω κατασκευαστές

Τώρα μπορούμε να γράψουμε εύκολα μια ασφαλή ως προς τους τύπους συνάρτηση που, για παράδειγμα, μετράει τον αριθμό των κόμβων σε ένα δέντρο:

fun countNodes(Leaf) = 0
  | countNodes(Node(int,left,right)) =
      1 + countNodes(left) + countNodes(right)

Ιστορικό υποστήριξης από τις Γλώσσες Προγραμματισμού[edit]

1960s[edit]

Στην ALGOL 68 οι διαχωρισμένες ενώσεις αποκαλούνται united modes, η ετικέτα είναι έμμεση και η εντολή case χρησιμοποιείται για να καθορίσει ποιο πεδίο είναι ενεργό:

mode node = union (real, int, compl, string);

Παράδειγμα χρήσης:

node n := "1234";
 
case n in
  (real r):   print(("real:", r)),
  (int i):    print(("int:", i)),
  (compl c):  print(("compl:", c)),
  (string s): print(("string:", s))
  out         print(("?:", n))
esac

1970s & 1980s[edit]

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

Οι γλώσσες Pascal, Ada και Modula-2 τις αποκαλούν μεταβλητές εγγραφές (variant records, τυπικά στην Ada ονομάζονται διακριτοί τύποι) και απαιτούν να ορίζεται ρητά το πεδίο της ετικέτας και οι πιθανές τιμές της, όπως στο ακόλουθο παράδειγμα Pascal:

type shapeKind = (square, rectangle, circle);
     shape = record
                centerx : integer;
                centery : integer;
                case kind : shapeKind of
                   square : (side : integer);
                   rectangle : (length, height : integer);
                   circle : (radius : integer);
	      end;

Και στο ακόλουθο παράδειγμα Ada:

-- Ada example of discriminated record.
 
type Discriminant_Kind is (A_Foo, A_Bar, A_Who_Know_What);
 
type Discriminated_Type (Discriminant : Discriminant_Kind) is record
   case Discriminant is
      when A_Foo => Foo : Foo_Type;
      when A_Bar => Bar : Bar_Type;
      when A_Who_Know_What => Who_Know_What : Who_Know_What_Type;
   end case;
end record;
 
-- Any attempt to access a member whose existence depends
-- on a particular value of the discriminant, while the
-- discriminant is not the expected one, raise an error.

Στις γλώσσες C και C++ μια διαχωρισμένη ένωση μπορεί να δημιουργηθεί από μη διαχωρισμένες ενώσεις χρησιμοποιώντας έναν αυστηρό τρόπο πρόσβασης, σύμφωνα με τον οποίο η ετικέτα ελέγχεται πάντοτε:

enum ShapeKind { Square, Rectangle, Circle };
 
struct Shape {
    int centerx;
    int centery;
    enum ShapeKind kind;
    union {
        struct { int side; }           squareData;
        struct { int length, height; } rectangleData;
        struct { int radius; }         circleData;
    } shapeKindData;
};
 
int getSquareSide(struct Shape* s) {
    assert(s->kind == Square);
    return s->shapeKindData.squareData.side;
}
 
void setSquareSide(struct Shape* s, int side) {
    s->kind = Square;
    s->shapeKindData.squareData.side = side;
}
 
/* and so on */

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

Η C και η C++ υποστηρίζουν μια ειδική διαχωρισμένη ένωση: τον πιθανώς κενό δείκτη. Αυτή μπορεί να συγκριθεί με τον τύπο option της ML ή τον τύπο Maybe της Haskell και μπορεί να θεωρηθεί ως ένας δείκτης με ετικέτα (tagged pointer): μια διαχωρισμένη ένωση (με κωδικοποιημένη ετικέτα) δύο τύπων:

  • Έγκυροι δείκτες,
  • Ένας τύπος που μπορεί να πάρει μόνο μία τιμή, τη κενή (null), υποδεικνύοντας μια "εξαιρετική" κατάσταση.

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

2000s[edit]

Μια προηγμένη διάλεκτος της C με το όνομα Cyclone έχει εκτενή ενσωματωμένη υποστήριξη για διαχωρισμένες ενώσεις. Δείτε την ενότητα tagged union του on-line εγχειριδίου για περισσότερες πληροφορίες.


Η βιβλιοθήκη variant της συλλογής βιβλιοθηκών Boost έδειξε ότι ήταν εφικτό να υλοποιηθεί μια ασφαλής διαχωρισμένη ένωση ως βιβλιοθήκη στη C++:

struct display : boost::static_visitor<void>
{
    void operator()(int i)
    {
        std::cout << "It's an int, with value " << i << std::endl;
    }
 
    void operator()(const std::string& s)
    {
        std::cout << "It's a string, with value " << s << std::endl;
    }
};
 
boost::variant<int, std::string> v = 42;
boost::apply_visitor(display(), v);
 
boost::variant<int, std::string> v = "hello world";
boost::apply_visitor(display(), v);


Η γλώσσα Scala έχει τάξεις περιπτώσεων (case classes):

sealed abstract class Tree
case object Leaf extends Tree
case class Node(value: Int, left: Tree, right: Tree) extends Tree
 
val tree = Node(5, Node(1,Leaf,Leaf), Node(3, Leaf, Node(4, Leaf, Leaf)))

Επειδή η ιεραρχία των τάξεων δεν μπορεί να επεκταθεί περεταίρω (sealed), ο μεταγλωττιστής μπορεί να ελέγξει ότι σε ένα ταίριασμα προτύπων ο κώδικας χειρίζεται όλες τις περιπτώσεις:

tree match {
  case Node(x, _, _) => println("top level node value: " + x)
  case Leaf          => println("top level node is a leaf")
}

Οι τάξεις περιπτώσεων (case classes) της Scala επιτρέπουν την επαναχρησιμοποίηση μέσω σχέσεων υποτύπων:

sealed abstract class Shape(centerX: Int, centerY: Int)
case class Square(side: Int, centerX: Int, centerY: Int) extends Shape(centerX, centerY)
case class Rectangle(length: Int, height: Int, centerX: Int, centerY: Int) extends Shape(centerX, centerY)
case class Circle(radius: Int, centerX: Int, centerY: Int) extends Shape(centerX, centerY)

Ιεραρχίες τάξεων ως διαχωρισμένες ενώσεις[edit]

Σε μια τυπική ιεραρχία τάξεων στο αντικειμενοστραφές μοντέλο προγραμματισμού κάθε υποτάξη μπορεί να ενθυλακώσει δεδομένα μοναδικά σε αυτήν. Τα μεταδεδομένα (metadata) που χρησιμοποιούνται για την αναζήτηση εικονικών μεθόδων (για παράδειγμα ο δείκτης στο vtable του αντικειμένου στις περισσότερες υλοποιήσεις της C++) προσδιορίζουν την υποτάξη και έτσι ενεργούν ουσιαστικά ως μια ετικέτα που προσδιορίζει τα συγκεκριμένα δεδομένα που αποθηκεύονται από το στιγμιότυπο (βλέπε RTTI). Ο κατασκευαστής ενός αντικειμένου θέτει αυτή την ετικέτα, η οποία παραμένει αμετάβλητη για όλη τη διάρκεια ζωής του αντικειμένου.

Παρόλα αυτά, μια ιεραρχία τάξεων περιλαμβάνει πραγματικό πολυμορφισμό υποτύπων. Μπορεί να επεκταθεί δημιουργώντας περαιτέρω υποτάξεις του ίδιου βασικού τύπου, τις οποίες δεν θα μπορούσαμε να χειριστούμε σωστά σε ένα μοντέλο ετικετών. Ως εκ τούτου, δεν είναι συνήθως εφικτό να γίνει ανάλυση περιπτώσεων στην 'ετικέτα' ενός αντικειμένου, όπως θα γινόταν σε μια διαχωρισμένη ένωση. Ορισμένες γλώσσες, όπως η Scala, επιτρέπουν στις βασικές τάξεις να "σφραγιστούν" (sealed - απαγορεύεται η περαιτέρω επέκταση της τάξης με άλλες υποτάξεις) και ενοποιούν τις διαχωρισμένες ενώσεις με τις "σφραγισμένες" βασικές τάξεις.

Δείτε επίσης[edit]

Περαιτέρω διάβασμα[edit]

  • H boost::variant είναι μια ασφαλής ως προς τους τύπους διακριτή ένωση στη C++
  • H std.variant είναι μια υλοποίηση μεταβλητών τύπων στη γλώσσα προγραμματισμού D 2.0

Κατηγορία:Τύποι δεδομένων Κατηγορία:Θεωρία τύπων Template:Ενσωμάτωση κειμένου

en: Tagged union